Syntax: BNF, derivation, parse tree and ambiguity

This topic is the part that brings the most points on the midterm. The question types are fixed: write a leftmost derivation with a given grammar, draw a parse tree, prove that a grammar is ambiguous, read precedence and associativity from a grammar, convert EBNF to BNF. All of it is mechanical. Whoever knows the recipe does not lose.

Golden rules:

1. Leftmost derivation: on each line replace only the leftmost single nonterminal.
2. In the tree, what is lower is computed first. A high-precedence operator is deep in the tree.
3. Left recursion gives left associativity, right recursion gives right associativity.
4. Proof of ambiguity = one sentence + two different trees. “There are two alternatives in the rule” is not a proof.
5. EBNF adds no expressive power. Every EBNF rule can be written in BNF.

Syntax and semantics

The definition of a language has two parts. Syntax is the form of expressions: which character sequences are valid programs? Semantics is what those expressions do. That while (x < 5) x++; is written correctly is syntax; that the loop increases x until it is 5 is semantics.

The smallest meaningful unit of a program is the lexeme: sum, =, 17, ;. Each lexeme belongs to a category, and this category is called a token. sum and total are different lexemes but the same token: IDENT.

There are two ways to define a language. A recognizer takes a sentence and decides “does it belong to the language?”; the compiler’s syntax analyzer is this. A generator produces the sentences of the language; a grammar is this.

BNF

BNF (Backus-Naur Form) was used for ALGOL 58/60 in the late 1950s and has the same power as Chomsky’s class of context-free grammars. A rule (production) has this form:

<if_stmt> -> if <logic_expr> then <stmt>
           | if <logic_expr> then <stmt> else <stmt>

• The left side (LHS) is a single nonterminal: an abstraction in angle brackets, like <if_stmt>.
• The right side (RHS) is a sequence of terminals and nonterminals. Terminals are the actual symbols of the language: if, then, +.
• | means an alternative for the same LHS.
• The start symbol is usually the LHS of the first rule: <program>, <assign>.

BNF has no loops for repetition. Lists are written with recursion:

<ident_list> -> ident | ident , <ident_list>

This rule produces x, x , y, x , y , z …

Derivation

A derivation starts from the start symbol and applies rules to reach a sentence. Each intermediate line is a sentential form, and the last line, consisting only of terminals, is a sentence. Our standard grammar:

<assign> -> <id> = <expr>
<id>     -> A | B | C
<expr>   -> <expr> + <term> | <term>
<term>   -> <term> * <factor> | <factor>
<factor> -> ( <expr> ) | <id>

Leftmost derivation for A = B + C * A:

<assign> => <id> = <expr>
         => A = <expr>
         => A = <expr> + <term>
         => A = <term> + <term>
         => A = <factor> + <term>
         => A = <id> + <term>
         => A = B + <term>
         => A = B + <term> * <factor>
         => A = B + <factor> * <factor>
         => A = B + <id> * <factor>
         => A = B + C * <factor>
         => A = B + C * <id>
         => A = B + C * A

13 steps. How did you decide which rule to choose? Look at the top-level operator of the sentence. Here + is at the top (multiplication will be computed before it), so <expr> was first expanded as <expr> + <term>. In the sentence B = ( A + C ) * B, the only operator outside the parentheses is *, so you take the path <expr> => <term> => <term> * <factor>.

Rightmost derivation does the same job starting from the rightmost nonterminal. It corresponds to the same tree, only the order of expansion differs:

<assign> => <id> = <expr>
         => <id> = <expr> + <term>
         => <id> = <expr> + <factor>
         => <id> = <expr> + <id>
         => <id> = <expr> + C
         ...
         => A = B + C

PITFALL · one change per line. Expanding two nonterminals in one step, or taking a shortcut that is not in the rules (like <expr> => B; there are <term>, <factor>, <id> in between) loses points. Apply exactly one rule on each line.

Parse tree

The hierarchical form of a derivation. The root is the start symbol, each interior node is a nonterminal whose children are the RHS of the applied rule (left to right), and the leaves are terminals. For A = B + C * A:

<assign>
├── <id> ── A
├── =
└── <expr>
    ├── <expr> ── <term> ── <factor> ── <id> ── B
    ├── +
    └── <term>
        ├── <term> ── <factor> ── <id> ── C
        ├── *
        └── <factor> ── <id> ── A

Read the leaves left to right: A = B + C * A. If it matches, the tree is correct. The tree has another use: it shows the meaning. C * A is in a subtree, so it is computed first, and the result is added to B.

Ambiguity

A grammar is ambiguous if it can produce two different parse trees for at least one sentence. Equivalent definition: that sentence has two different leftmost derivations.

<E> -> <E> + <E> | <E> * <E> | x

For x + x * x there are two trees: + at the root (x + (x * x)) or * at the root ((x + x) * x). The difference shows when you plug in values: 2 + 3 * 4 is 14 in the first tree and 20 in the second. The compiler cannot know which code to generate; this is why ambiguity is bad.

Proof recipe:

1. Choose a short sentence with two of the same operator (a - b - a) or two different operators (a + b * c).
2. Draw the two trees, with a different operator at the root.
3. Show that the leaves of both trees give the same sentence.

Removing ambiguity: precedence and associativity

Use a separate nonterminal for each precedence level. The low-precedence operator is near the start symbol (higher in the tree), and the high-precedence one is lower.

Associativity comes from which side the recursion is on:

• Left recursion (<expr> -> <expr> + <term>): the LHS repeats on the left of the RHS. The operation on the left stays deep. It associates to the left: 9 - 4 - 2 = (9 - 4) - 2 = 3.
• Right recursion (<t> -> <f> ^ <t>): it associates to the right: 2 ^ 3 ^ 2 = 2 ^ (3 ^ 2) = 512. This is the right choice for exponentiation.

<e> -> <e> - <t> | <t>          - associates to the left, low precedence
<t> -> <f> ^ <t> | <f>          ^ associates to the right, high precedence
<f> -> NUM

With this grammar 10 - 2 ^ 3 - 1 = (10 - (2 ^ 3)) - 1 = 1.

PITFALL · the grammar imposes the rule. On exams a “reversed” grammar is sometimes given: <e> -> <e> * <t>, <t> -> <t> + <f>. Here + is lower, so it is computed first: 2 * 3 + 4 = 2 * (3 + 4) = 14. Apply the tree, not the rule you know from mathematics. Likewise, since <e> -> <t> - <e> is right recursive, 10 - 4 - 3 = 10 - (4 - 3) = 9.

Dangling else

<stmt> -> if c then <stmt> | if c then <stmt> else <stmt> | s

if c then if c then s else s has two trees: the else may belong to the inner or the outer if. The rule of Java, C, C++: the else attaches to the nearest unmatched if. To enforce it with a grammar, statements are split into <matched> (every if has its else) and <unmatched>; then the same sentence is left with a single tree. Python solves the problem in syntax with indentation, Ruby and Ada with end / end if, and Perl by requiring curly braces on every branch.

EBNF

EBNF (Extended BNF) does not increase power; it shortens rules and makes them readable.

EBNF:  <expr> -> <term> { (+ | -) <term> }
BNF:   <expr> -> <expr> + <term> | <expr> - <term> | <term>

EBNF:  <args> -> ( [ id { , id } ] )
BNF:   <args> -> ( ) | ( <list> )
       <list> -> id | id , <list>

When converting a repetition written with { } to BNF, choosing left recursion preserves the usual left associativity for + and -. { } does not mean “at least one”; zero repetitions are included. For “at least one”, write X { X }.

Writing grammars

Two patterns that come up often:

one or more a, then one or more b:
<S> -> <A> <B>
<A> -> a <A> | a
<B> -> b <B> | b

a^n b^2n, n >= 1 (counts tied):
<S> -> a <S> b b | a b b

If the counts are tied (“equal number”, “twice as many”), the two ends are produced together in the same rule. If they are independent, separate nonterminals are placed side by side. After writing, check with two or three sentences, and also think about whether a sentence that doesn’t belong to the language is generated.

Which sentences are generated?

<S> -> a <S> | <B>
<B> -> b <B> c | b c

First describe the language: zero or more a’s at the front, then an equal number (at least one) of b’s and c’s. aabc ✔, abbcc ✔, bc ✔, abcc ✘ (the number of b’s and c’s differ), aab ✘ (no c).

Common mistakes

<assign> -> <id> = <expr>
<id>     -> A | B | C
<expr>   -> <expr> + <term> | <term>
<term>   -> <term> * <factor> | <factor>
<factor> -> ( <expr> ) | <id>

<assign> => <id> = <expr> => A = <expr>
=> A = <expr> + <term> => A = <term> + <term>
=> A = <factor> + <term> => A = <id> + <term> => A = B + <term>
=> A = B + <term> * <factor> => A = B + <factor> * <factor>
=> A = B + <id> * <factor> => A = B + C * <factor>
=> A = B + C * <id> => A = B + C * A

<assign> -> <id> = <expr>
<id>     -> A | B | C
<expr>   -> <expr> + <term> | <term>
<term>   -> <term> * <factor> | <factor>
<factor> -> ( <expr> ) | <id>

<S> -> a <S> | <B>
<B> -> b <B> c | b c

<E> -> <E> + <E> | <E> * <E> | x

<e> -> <e> - <t> | <t>
<t> -> <f> ^ <t> | <f>
<f> -> NUM

<e> -> <e> * <t> | <t>
<t> -> <t> + <f> | <f>
<f> -> NUM

<e> -> <t> - <e> | <t>
<t> -> NUM

<stmt> -> if c then <stmt> | if c then <stmt> else <stmt> | s