Chapter 18 of 34

Derivations, Parse Trees & Ambiguity

In the Context-Free Grammars chapter we generated strings by applying productions one after another. But when a sentential form has several variables, which one should we replace first? And does that choice change the meaning of the string?

For a compiler, meaning is everything. The expression 2 + 3 * 4 must be read as 2 + (3 * 4) = 14, not (2 + 3) * 4 = 20. A grammar that allows both readings is called ambiguous, and it is a real problem.

A parse tree shows the structure a grammar gives to a string. A grammar is ambiguous if some string in its language has two or more different parse trees.

In this chapter we will study leftmost and rightmost derivations, draw parse trees, recognise ambiguity, and learn the standard ways to remove it. All parse-tree counts in this chapter were computed by a program, and every "unambiguous" grammar was checked on all strings up to length 7 to 12.


Leftmost and Rightmost Derivations

When a sentential form contains more than one variable, we have a choice. Two systematic choices are standard:

In a leftmost derivation (⇒lm), every step replaces the leftmost variable of the sentential form. In a rightmost derivation (⇒rm), every step replaces the rightmost variable.

Take the expression grammar:

E → E + T | T
T → T * F | F
F → ( E ) | a

and the string a + a * a.

Leftmost derivation

E ⇒lm E + T
  ⇒lm T + T
  ⇒lm F + T
  ⇒lm a + T
  ⇒lm a + T * F
  ⇒lm a + F * F
  ⇒lm a + a * F
  ⇒lm a + a * a

Rightmost derivation

E ⇒rm E + T
  ⇒rm E + T * F
  ⇒rm E + T * a
  ⇒rm E + F * a
  ⇒rm E + a * a
  ⇒rm T + a * a
  ⇒rm F + a * a
  ⇒rm a + a * a

Both use the same 8 productions, only in a different order. A sentential form that appears in a leftmost derivation is called a left-sentential form; similarly for right.

These two orders matter in compilers: top-down parsers (LL) build a leftmost derivation, and bottom-up parsers (LR) build a rightmost derivation in reverse. The Compiler Design tutorial uses exactly these ideas.


Parse Trees

A derivation is a sequence; a parse tree is a picture of the same derivation that forgets the order of steps and keeps only the structure.

A parse tree (derivation tree) for a grammar G is a tree in which: the root is labelled with the start symbol; every interior node is labelled with a variable; every leaf is labelled with a terminal or ε; and if an interior node A has children X1, X2, …, Xk from left to right, then A → X1X2…Xk is a production of G. (A leaf labelled ε must be the only child of its parent, for a production A → ε.)

The yield of the tree is the string formed by reading its leaves from left to right (ignoring ε). The yield of a complete parse tree is a string of L(G).

Parse tree for a + a * a in the expression grammar:

              E
            / | \
           E  +  T
           |   / | \
           T  T  *  F
           |  |     |
           F  F     a
           |  |
           a  a

The * is grouped under a T that sits below the +. So the tree "says" a + (a * a): multiplication first. A compiler evaluates the tree bottom-up, so the structure of the tree is the meaning of the expression.

Trees and derivations: the exact relationship

  • Every parse tree corresponds to exactly one leftmost derivation and exactly one rightmost derivation.

  • Every derivation (in any order) corresponds to exactly one parse tree.

  • But one parse tree can correspond to many derivations that mix the order of steps.

Example: with S → AB, A → a, B → b, the string ab has two derivations, S ⇒ AB ⇒ aB ⇒ ab and S ⇒ AB ⇒ Ab ⇒ ab. They are just leftmost and rightmost versions of the same tree. Having two derivations does not make a grammar ambiguous. Having two trees (equivalently, two leftmost derivations) does.


Ambiguity

A CFG G is ambiguous if there is at least one string w ∈ L(G) that has two or more distinct parse trees. Equivalently, w has two distinct leftmost derivations, or two distinct rightmost derivations. Otherwise G is unambiguous.

One string with two trees is enough to make the whole grammar ambiguous.

Example 1: the "natural" expression grammar

E → E + E | E * E | a

The string a + a * a has two parse trees:

   Tree 1: a + (a * a)               Tree 2: (a + a) * a

         E                                     E
       / | \                                 / | \
      E  +  E                               E  *  E
      |   / | \                           / | \   |
      a  E  *  E                         E  +  E  a
         |     |                         |     |
         a     a                         a     a

and therefore two leftmost derivations:

Tree 1:  E ⇒ E + E ⇒ a + E ⇒ a + E * E ⇒ a + a * E ⇒ a + a * a
Tree 2:  E ⇒ E * E ⇒ E + E * E ⇒ a + E * E ⇒ a + a * E ⇒ a + a * a

With a = 2, 3, 4 from left to right, Tree 1 evaluates to 2 + 12 = 14 and Tree 2 to 5 * 4 = 20. Same string, two meanings. This is why ambiguity is unacceptable in a programming language.

Ambiguity also hides in a single operator. For a + a + a, the trees (a + a) + a and a + (a + a) both exist. That is harmless for + on integers, but not for subtraction: (8 − 4) − 2 = 2 while 8 − (4 − 2) = 6.

How many trees?

In E → E + E | a, a string with k plus signs has as many trees as there are ways to fully parenthesise it, which is the Catalan number Ck = (2k)! / ((k+1)! k!).

String

Operators k

Parse trees

a + a

1

1

a + a + a

2

2

a + a + a + a

3

5

a + a + a + a + a

4

14

a + a + a + a + a + a

5

42

The same count applies to E → E + E | E * E | a whatever the mix of operators: a * a + a * a also has 5 trees.

Example 2: S → aS | Sa | a

The string aa has two trees: S ⇒ aS ⇒ aa and S ⇒ Sa ⇒ aa. In general an has 2n−1 trees (each a except the last one can be added from the left or from the right). The language is just a+, and S → aS | a generates it unambiguously.

Example 3: S → aSbS | bSaS | ε

This grammar (equal numbers of a's and b's, from the previous chapter) is ambiguous. The string abab has two leftmost derivations:

1)  S ⇒ aSbS ⇒ abS ⇒ abaSbS ⇒ ababS ⇒ abab        (first S → ε, second S → ab)
2)  S ⇒ aSbS ⇒ abSaSbS ⇒ abaSbS ⇒ ababS ⇒ abab    (first S → ba, second S → ε)

In derivation 1 the outer a is matched with the first b; in derivation 2 with the last b. ababab has 5 trees.

Example 4: the dangling else

A famous ambiguity from real languages (C, Java, Pascal):

S → if C then S | if C then S else S | other

Consider:

if C1 then if C2 then s1 else s2

Which if does the else belong to?

Tree 1 (else with inner if):   if C1 then [ if C2 then s1 else s2 ]
Tree 2 (else with outer if):   if C1 then [ if C2 then s1 ] else s2
Tree 1:                                   Tree 2:
        S                                         S
   _____|______                         __________|_____________
  if C1 then   S                       if C1 then  S   else   s2
        _______|________                       ____|____
       if C2 then s1 else s2                  if C2 then s1

When C1 is true and C2 is false, Tree 1 runs s2 but Tree 2 runs nothing. Real languages resolve this with the rule "an else matches the nearest unmatched then" (Tree 1).


Removing Ambiguity

There is no general algorithm that removes ambiguity (see below), but the common cases have standard fixes.

Fix 1: precedence and associativity by layering

Give each precedence level its own variable. Lower precedence operators are generated nearer the root; higher precedence ones deeper down:

E → E + T | T          (+ : lowest precedence)
T → T * F | F          (* : higher precedence)
F → ( E ) | a          (atoms and brackets)
  • Precedence: a T can contain * but never an unbracketed +. So in a + a * a, the * is forced inside a T, below the +. Only Tree 1 is possible.

  • Associativity: E → E + T is left-recursive, so a + a + a must be (a + a) + a: the right operand of + is a T, which cannot contain an unbracketed +. For a right-associative operator such as exponentiation, use right recursion: P → F ^ P | F.

  • Brackets restart at E, so (a + a) * a is still expressible.

The layered grammar generates exactly the same strings as E → E + E | E * E | (E) | a, but every string has exactly one tree (checked by program for all strings up to length 7).

Fix 2: matched and unmatched statements (dangling else)

Split statements into matched ones (every then has its else) and unmatched ones:

S → M | U
M → if C then M else M | other
U → if C then S | if C then M else U

Only a matched statement may appear between then and else. So in if C1 then if C2 then s1 else s2, the part if C2 then s1 is unmatched and cannot sit before the else. The else is forced onto the inner if, exactly the "nearest then" rule. (Checked by program: same language as the ambiguous grammar, and one tree per string, up to length 9 with C abstracted away.) In practice, parser generators like Yacc/Bison often keep the short ambiguous grammar and resolve the conflict by preferring shift, which has the same effect.

Fix 3: rewrite the recursion

Ambiguous

Unambiguous, same language

Language

S → (S) | SS | ε

S → (S)S | ε

balanced parentheses

S → aS | Sa | a

S → aS | a

a+

S → aSb | aS | ε

S → aS | A, A → aAb | ε

ambn, m ≥ n

The idea in each case is to make every choice forced. In S → (S)S | ε, the first ( must match the bracket that closes the first balanced block, so there is only one way to split. In the last row, all the extra a's are produced first, then the matched pairs; in S → aSb | aS | ε the extra a's could be inserted at any level, so aab already has two trees (S ⇒ aSb ⇒ aaSb ⇒ aab and S ⇒ aS ⇒ aaSb ⇒ aab).

(S → (S) | SS | ε is ambiguous in an extreme way: S ⇒ SS ⇒ S lets us insert useless SS → S steps, so every string has infinitely many trees.)


Inherent Ambiguity

Ambiguity is usually a property of a grammar, not of a language. But some context-free languages can only be generated by ambiguous grammars.

A context-free language is inherently ambiguous if every grammar that generates it is ambiguous.

The standard example:

L = { a^i b^j c^k  |  i = j  or  j = k }

A natural grammar is S → XC | AY, X → aXb | ε, C → cC | ε, A → aA | ε, Y → bYc | ε. Strings with i = j = k, like abc and aabbcc, are generated both through XC (matching a's with b's) and through AY (matching b's with c's), so they get two trees. It is a known theorem, proved in the standard textbooks (Hopcroft–Ullman; it is also a classic exercise in Sipser), that every grammar for L gives two parse trees to infinitely many strings of the form anbncn. The proof is long and not needed for exams; just remember the example.

Ambiguity is undecidable

There is no algorithm that takes an arbitrary CFG and decides whether it is ambiguous. This is proved by reduction from the Post Correspondence Problem (see the Post Correspondence Problem chapter). Whether a CFL is inherently ambiguous is also undecidable. In practice, grammars that pass an LL(1) or LR(1) parser-generator test are guaranteed unambiguous, which is how compiler writers get certainty.


Comparison Table

Concept

What it is

Count for one string (unambiguous grammar)

Derivation (any order)

sequence of steps

possibly many

Leftmost derivation

always expand leftmost variable

exactly one

Rightmost derivation

always expand rightmost variable

exactly one

Parse tree

structure, order-free

exactly one

Term

Property of

Decidable?

Ambiguous grammar

a grammar

No (in general)

Inherently ambiguous language

a language

No (in general)


Common Mistakes

  • "Two derivations, so ambiguous." Wrong. A leftmost and a rightmost derivation of the same tree are different sequences but the same structure. Compare leftmost with leftmost, or compare trees.

  • Calling a language ambiguous. Grammars are ambiguous. A language is only "inherently ambiguous" if every grammar for it is.

  • Assuming an ambiguous grammar generates the wrong language. E → E + E | E * E | a generates exactly the right strings. The problem is structure, not membership.

  • Using right recursion for a left-associative operator. E → T + E | T generates the same strings but groups a − a − a as a − (a − a).

  • Testing only one string. A grammar is unambiguous only if every string has one tree. One good-looking example proves nothing; one string with two trees proves ambiguity.


GATE and Interview Questions

Q1. Is S → SS | a ambiguous? How many parse trees does aaaa have?

Yes. aaa already has two trees: (aa)a and a(aa). aaaa has 5 trees, the Catalan number C3. In general an has Cn−1 trees.

Q2. Which of these is ambiguous? (a) S → aSb | ab (b) S → aSb | aS | ε (c) S → (S)S | ε (d) E → E + T | T, T → a

(b). The string aab has two leftmost derivations: S ⇒ aSb ⇒ aaSb ⇒ aab and S ⇒ aS ⇒ aaSb ⇒ aab. The others give every string exactly one tree.

Q3. A grammar has a string with one leftmost derivation but two rightmost derivations. Is that possible?

No. Leftmost derivations, rightmost derivations and parse trees are in one-to-one correspondence. Two rightmost derivations mean two trees, which mean two leftmost derivations.

Q4. Give an inherently ambiguous context-free language.

{ aibjck | i = j or j = k }. Strings anbncn belong to both parts, and every grammar for the language gives some of them two parse trees.

Q5. How do you make an operator right-associative in a grammar?

Use right recursion for it, e.g. P → F ^ P | F. Then a ^ a ^ a can only be grouped as a ^ (a ^ a), because the left operand of ^ is an F, which cannot contain an unbracketed ^.

Q6. Is there an algorithm to check if a CFG is ambiguous?

No, CFG ambiguity is undecidable (by reduction from the Post Correspondence Problem). We can only prove ambiguity by finding a string with two trees, or prove unambiguity for particular grammars, e.g. by showing they are LL(1) or LR(1).

Q7. In E → E + E | E * E | a, how many parse trees does a + a * a + a have?

5. It has three operators, and every full parenthesisation of three binary operators is a valid tree: C3 = 5.


Summary

  • A leftmost derivation always replaces the leftmost variable; a rightmost one the rightmost variable.

  • A parse tree shows the structure of a derivation; its leaves read left to right give the yield.

  • Parse trees, leftmost derivations and rightmost derivations are in one-to-one correspondence.

  • A grammar is ambiguous if some string has two parse trees (two leftmost derivations).

  • Classic ambiguous grammars: E → E + E | E * E | a, S → SS | a, S → aSbS | bSaS | ε, and the dangling else.

  • Fixes: layer the grammar by precedence, use left or right recursion for associativity, use matched/unmatched statements for else.

  • Some languages are inherently ambiguous, e.g. { aibjck | i = j or j = k }. Deciding ambiguity is undecidable.

A string tells you what was written. Its parse tree tells you what it means. An ambiguous grammar gives one string two meanings.