Show understanding of how the grammar of a language can be expressed using syntax diagrams or Backus-Naur Form (BNF) notation

16.2 Translation Software

Objective

Show understanding of how the grammar of a language can be expressed using syntax diagrams or Backus‑Naur Form (BNF) notation.

1. Why Grammar Matters in Translation Software

Translation software (compilers, interpreters, assemblers) must recognise whether a sequence of symbols forms a valid program. This is achieved by defining the grammar of the source language – a set of rules that describe the syntactic structure of legal programs.

2. Formal Ways to Describe Grammar

• Syntax diagrams (also called railroad diagrams) – visual representations that show the flow of tokens.
• Backus‑Naur Form (BNF) – a textual notation using production rules.

3. Syntax Diagrams

A syntax diagram consists of a start point, a series of nodes (terminals or non‑terminals), and an end point. The path from start to end represents one valid construction.

4. Backus‑Naur Form (BNF)

BNF expresses grammar as a set of production rules. Each rule has the form:

\$\langle\text{non‑terminal}\rangle ::= \text{definition}\$

where the definition may contain terminals (written in quotes) and other non‑terminals (enclosed in angle brackets).

5. Example Language – Simple Arithmetic Expressions

Consider a language that allows integer literals, addition, subtraction, multiplication, division and parentheses.

5.1 BNF for the language

<expr>   ::= <term> { ("+" | "-") <term> }
<term>   ::= <factor> { ("*" | "/") <factor> }
<factor> ::= <integer> | "(" <expr> ")"
<integer> ::= <digit> { <digit> }
<digit>  ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

5.2 Corresponding Syntax Diagrams

Each BNF rule can be turned into a diagram. Below is a textual description of the diagram for <expr>:

• Start → <term> → Loop:

  • Optional branch: "+" or "-" → <term>
  • Repeat loop zero or more times.

• End

6. Comparing Syntax Diagrams and BNF

7. From BNF to Syntax Diagrams (and vice‑versa)

1. Identify each non‑terminal in the BNF.
2. For each production, draw a linear path from start to end.
3. Use branching to represent alternatives (the “|” operator).
4. Use loops to represent repetitions (the “{ }” notation).
5. Conversely, read a diagram left‑to‑right and translate each segment back into BNF symbols.

8. Practical Use in Translation Software

When building a compiler:

• The grammar is first written in BNF (or an extended form such as EBNF).
• Tools like yacc or ANTLR consume the BNF to generate a parser.
• Syntax diagrams are useful in documentation, teaching, and for manual inspection of the language structure.

9. Summary

Both syntax diagrams and BNF provide a formal way to describe the grammar of a programming language. BNF is concise and machine‑readable, making it ideal for implementing translators. Syntax diagrams give a visual intuition that helps learners and developers verify the language structure.

10. Practice Questions

1. Write BNF rules for a language that supports while loops with the syntax while ( condition ) statement.
2. Convert the following BNF rule into a textual description of a syntax diagram:
   

   <assignment> ::= <identifier> "=" <expr> ";"

3. Identify two advantages of using BNF over syntax diagrams when creating a large‑scale compiler.
4. Given the syntax diagram for an if‑else statement (see suggested diagram in section 3), write the equivalent BNF rule.