Chapter 08 of 33

Ambiguity, Left Recursion & Left Factoring

In Syntax Analysis & Context-Free Grammars we wrote grammars and drew parse trees. We also mentioned that some grammars give a string more than one parse tree. For a compiler, that is a serious problem: the tree decides what the program means, so two trees can mean two different programs.

This chapter is about getting a grammar into a shape a parser can use. We look at three properties, all of them GATE favourites:

  • Ambiguity: a string with two or more parse trees. We will see how to detect it and how to rewrite grammars using precedence and associativity to remove it.

  • Left recursion: a non-terminal that can derive a string starting with itself. It sends top-down parsers into an infinite loop, and there is a mechanical algorithm to remove it.

  • Left factoring: removing common prefixes among alternatives, so a top-down parser can choose the right production by looking at the next token.

Every transformation in this chapter was checked by a program: the old and new grammars were compared string by string (all strings up to 9 to 14 tokens), and parse trees were counted by enumeration.


Ambiguous Grammars

A grammar G is ambiguous if some string in L(G) has two or more distinct parse trees. Equivalently, if some string has two or more distinct leftmost derivations (or two or more distinct rightmost derivations).

Note the word "some": a single string with two trees is enough to make the whole grammar ambiguous. And note that it is the grammar that is ambiguous, not the language; the same language usually has unambiguous grammars too.

The Classic Example

E → E + E | E * E | ( E ) | id

This grammar is short and generates exactly the right expressions. But id + id * id has two parse trees:

        Tree 1                           Tree 2
          E                                E
        / | \                            / | \
       E  +  E                          E  *  E
       |   / | \                      / | \   |
       id E  *  E                    E  +  E  id
          |     |                    |     |
          id    id                   id    id

   id + (id * id)                   (id + id) * id

Their leftmost derivations are different:

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

Why does it matter? Suppose the ids are 2, 3 and 4. A compiler that evaluates according to Tree 1 computes 2 + 12 = 14; one that follows Tree 2 computes 5 × 4 = 20. The grammar does not tell us which program the programmer wrote.

Associativity causes the same trouble even with one operator. id - id - id could be (a - b) - c or a - (b - c), which give different answers.

How Many Parse Trees?

For E → E op E | id, a string with n operands can be split at any of its operators at the top, and each side again in every possible way. The number of trees is the Catalan number Cn−1:

String

Operands n

Parse trees

id + id

2

1

id + id * id

3

2

id + id * id + id

4

5

id * id * id * id * id

5

14

The count depends only on the number of operands, not on which operators appear, because the grammar treats all operators alike. (Ck = (2k)! / ((k + 1)! k!), so C1 = 1, C2 = 2, C3 = 5, C4 = 14.)

The Dangling Else

The most famous ambiguity in real languages:

S → if E then S
  | if E then S else S
  | other

Consider if E1 then if E2 then S1 else S2. Which if does the else belong to?

Tree 1 (else with the inner if)          Tree 2 (else with the outer if)
  if E1 then                               if E1 then
      if E2 then S1                            if E2 then S1
      else S2                              else S2

Both are valid parse trees. Every major language (C, C++, Java, Pascal) chooses Tree 1:

Match each else with the closest previous unmatched then.

Python avoids the problem using indentation, and languages like Ada and Bash avoid it with explicit closing keywords (end if, fi).


Removing Ambiguity

There is no general algorithm for removing ambiguity (more on that below), but for expressions and the dangling else there are standard rewrites.

Precedence: One Non-Terminal per Level

Give each precedence level its own non-terminal. Lower precedence operators are introduced closer to the root, higher ones closer to the leaves:

E → E + T | T          (level 1: +, lowest precedence)
T → T * F | F          (level 2: *)
F → ( E ) | id         (level 3: atoms and parentheses)

A + can only appear in an E node, and an E can only appear under a * through parentheses. So in id + id * id the * is forced to sit lower in the tree, and is evaluated first. Our checker confirmed that this grammar generates exactly the same strings as the ambiguous one (all 257 strings of up to 9 tokens), and every one of them has exactly one parse tree.

Associativity: Choose the Direction of Recursion

  • Left recursion (E → E + T) makes the tree grow down to the left, so a - b - c is parsed as (a - b) - c: left-associative.

  • Right recursion (F → P ^ F) makes it grow to the right, so a ^ b ^ c is parsed as a ^ (b ^ c): right-associative, which is what we want for exponentiation and assignment.

A full grammar with four levels:

E → E + T | E - T | T          left-assoc, lowest
T → T * F | T / F | F          left-assoc
F → P ^ F | P                  right-assoc, highest operator
P → ( E ) | id
id - id - id                         id ^ id ^ id
       E                                  F
     / | \                              / | \
    E  -  T     ← left side grows      P  ^  F      ← right side grows
  / | \   |                            |   / | \
 E  -  T  id                           id P  ^  F
 |     |                                  |     |
 T     id                                 id    P
 |                                              |
 id                                             id

(To keep the pictures small, chains of single-child nodes such as T → F → P → id are drawn as one step, and the right picture starts at the F node below E → T → F.)

Each of the 2780 strings this grammar generates with up to 9 tokens has exactly one parse tree.

Recipe: n precedence levels need n + 1 non-terminals (one per level plus one for atoms). Left-associative operators use left recursion (A → A op B | B); right-associative ones use right recursion (A → B op A | B).

Fixing the Dangling Else

Split statements into matched ones (every then has its else) and unmatched ones, and allow only a matched statement between then and else:

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

Now in if E1 then if E2 then S1 else S2, the part between the outer then and the else would be if E2 then S1, which is unmatched, so Tree 2 is impossible. Only the "closest if" tree remains. We checked this by abbreviating if E then as i, else as e and other as a: both grammars generate the same 289 strings of up to 13 symbols, and the new one gives each exactly one tree.

In practice, many parser generators keep the short ambiguous grammar and resolve the conflict with a rule instead ("prefer shift"), which gives the same closest-if behaviour. You will see this in the LR parsing chapters.

Inherent Ambiguity and Undecidability

  • Some context-free languages are inherently ambiguous: every grammar for them is ambiguous. The standard example is { aibjck | i = j or j = k }. Strings with i = j = k belong to both "halves", and it can be proved that any grammar must give some of them two trees.

  • Whether an arbitrary CFG is ambiguous is undecidable: no algorithm can answer it for all grammars. So in exams you show ambiguity by finding one string with two trees, and you argue unambiguity from the grammar's structure.

  • On the positive side, every grammar that is LL(1) or LR(k) is unambiguous. So if a parser generator builds a conflict-free table, the grammar is unambiguous.

Spotting Ambiguity Quickly

These shapes are red flags. Each grammar below is ambiguous, with a short witness string:

Grammar

Pattern

Witness (2 trees)

E → E + E | id

Same non-terminal on both sides of an operator

id + id + id

S → a S | S a | a

Can grow on the left and on the right

aa

S → S S | a

Concatenation of the same symbol

aaa

S → a S b S | b S a S | ε

Several ways to split

abab

S → if E then S | if E then S else S | other

Optional trailing part

if E then if E then other else other


Left Recursion

A grammar is left-recursive if it has a non-terminal A such that A ⇒+ Aα for some string α. If this happens in one step, through a production A → Aα, it is immediate (direct) left recursion; otherwise it is indirect left recursion.

Why Top-Down Parsers Cannot Handle It

A top-down parser, as we will see in Top-Down Parsing & Recursive Descent, turns each non-terminal into a procedure. For E → E + T | T, the procedure for E would start like this:

void E(void) {
    E();              /* first symbol of E → E + T is E itself ... */
    match('+');       /* ... never reached */
    T();
}

E() calls E() without consuming any input, which calls E() again, and so on until the stack overflows. Looking at the next token does not help either: it is the same token at every level. Bottom-up (LR) parsers have no problem with left recursion; in fact they prefer it. The issue is specific to top-down parsing.

Removing Immediate Left Recursion

Look at what A → Aα | β generates: a β followed by any number of α's, that is, β α α ... α. We can generate the same strings from left to right instead: first β, then a new non-terminal A' that produces the α's.

Replace A → Aα1 | Aα2 | ... | Aαm | β1 | β2 | ... | βn (where no βi starts with A) by:
A → β1A' | β2A' | ... | βnA'
A' → α1A' | α2A' | ... | αmA' | ε

Worked Example 1: The Expression Grammar

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

For E: α = + T, β = T. For T: α = * F, β = F. F is not left-recursive.

E  → T E'
E' → + T E' | ε
T  → F T'
T' → * F T' | ε
F  → ( E ) | id

This is the grammar used throughout the LL(1) chapters. Both grammars generate the same 257 strings of up to 9 tokens.

Worked Example 2: Several Alternatives

A → A a | A b | c | d

α1 = a, α2 = b, β1 = c, β2 = d. The language is "c or d, followed by any string of a's and b's":

A  → c A' | d A'
A' → a A' | b A' | ε

Worked Example 3: A GATE-Style Grammar

S → S 0 S 1 | 0 1

Here α = 0 S 1 (everything after the leading S) and β = 0 1:

S  → 0 1 S'
S' → 0 S 1 S' | ε

A common mistake is to take α = 0 only. The whole remainder of the production after the leading A is α.

Removing Indirect Left Recursion

Indirect left recursion hides behind other non-terminals:

A → B x | y
B → C z | w
C → A v | u

No production starts with its own left side, yet A ⇒ B x ⇒ C z x ⇒ A v z x. The algorithm: order the non-terminals, and make sure every production Ai → Ajγ has j > i. Whenever a production starts with an earlier non-terminal, substitute that non-terminal's productions; then remove immediate left recursion.

Arrange the non-terminals in some order A1, A2, ..., An.
for i = 1 to n:
    for j = 1 to i - 1:
        replace each production Ai → Aj γ by Ai → δ1 γ | δ2 γ | ... | δk γ,
            where Aj → δ1 | δ2 | ... | δk are the current Aj-productions
    eliminate immediate left recursion among the Ai-productions

The algorithm is guaranteed to work if the grammar has no cycles (A ⇒+ A) and no ε-productions; those can be removed first if needed.

Apply it with the order A, B, C:

  1. i = A: no earlier non-terminals. A has no immediate left recursion. Unchanged.

  2. i = B: does any B-production start with A? No (C z, w). No immediate left recursion. Unchanged.

  3. i = C, j = A: C → A v starts with A, so substitute A's productions:
    C → B x v | y v | u

  4. i = C, j = B: C → B x v starts with B, so substitute B's productions:
    C → C z x v | w x v | y v | u

  5. Now C has immediate left recursion with α = z x v and β ∈ {w x v, y v, u}. Remove it:

A  → B x | y
B  → C z | w
C  → w x v C' | y v C' | u C'
C' → z x v C' | ε

No non-terminal can now reach itself at the left end: A starts with B, B with C, and C only with terminals. The new grammar generates exactly the same strings as the original (checked by program).

Watch out for hidden left recursion through nullable symbols: in A → B A c | d with B → ε | b, A ⇒ B A c ⇒ A c, so A is left-recursive even though the production starts with B. That is why the algorithm requires ε-productions to be removed first.


Left Factoring

Suppose a top-down parser is expanding A and sees the next token if, and the grammar says:

S → if E then S else S
  | if E then S

Both alternatives start with if E then S, so one token of lookahead cannot decide between them. (It could guess and backtrack, but that is slow.) The fix is to postpone the decision until the parser has read the common part.

Replace A → αβ1 | αβ2 | ... | αβn | γ (where α is the longest prefix common to two or more alternatives and γ stands for the alternatives that do not start with α) by:
A → αA' | γ
A' → β1 | β2 | ... | βn
Repeat until no two alternatives of any non-terminal share a common prefix.

Worked Example 1: If-Then-Else

Abbreviating if as i, then as t, else as e:

S → i E t S | i E t S e S | a
E → b

The common prefix of the first two alternatives is α = i E t S, with β1 = ε and β2 = e S:

S  → i E t S S' | a
S' → e S | ε
E  → b

Important: left factoring does not remove ambiguity. This grammar still has the dangling-else problem, now hidden inside S': when the parser is in S' and sees e, both S' → e S and S' → ε are possible. The LL(1) chapter shows how this shows up as a table conflict.

Worked Example 2: Factoring in Several Rounds

A → a b c | a b d | a e | f

Round 1. Three alternatives start with a. Factor it out:

A  → a A' | f
A' → b c | b d | e

Round 2. In A', two alternatives start with b. Factor again:

A   → a A' | f
A'  → b A'' | e
A'' → c | d

Now every non-terminal's alternatives start with different terminals, so one token of lookahead always picks the right one. (Taking the longest common prefix a b first and then a gives an equivalent grammar; either way, keep going until no common prefixes remain.)

Left Factoring vs Left Recursion Removal

Aspect

Left recursion removal

Left factoring

Problem fixed

Infinite recursion in top-down parsers

Not knowing which alternative to choose with limited lookahead

Pattern

A → Aα | β

A → αβ1 | αβ2

Result

A → βA', A' → αA' | ε

A → αA', A' → β1 | β2

Changes the language?

No

No

Changes the parse trees?

Yes (left-leaning trees become right-leaning)

Yes (an extra level for A')

Removes ambiguity?

No

No

Needed for bottom-up (LR) parsers?

No

No

One side effect of left recursion removal is worth noticing: the new grammar for a - b - c produces a right-leaning tree, which by itself suggests the wrong associativity. Compilers handle this in the translation (by passing the left operand down the tree as an inherited attribute), as the syntax-directed translation chapters show.

Getting a Grammar Ready for Top-Down Parsing

  1. Remove ambiguity (precedence levels, associativity, matched/unmatched statements), or decide on a disambiguating rule.

  2. Remove left recursion, both immediate and indirect.

  3. Left factor.

The result is often, but not always, suitable for a predictive parser. Whether it really is gets checked with FIRST and FOLLOW sets, the topic of the next chapter.


Common Mistakes

  • Showing two derivations instead of two parse trees. Two derivations that differ only in order (one leftmost, one rightmost) prove nothing. You need two different trees, or two different leftmost derivations.

  • Taking only one symbol as α in A → Aα. α is everything after the leading A.

  • Forgetting the ε alternative for A' when removing left recursion. Without it, A' can never stop and the language becomes empty.

  • Forgetting the β's: each non-left-recursive alternative gets A' appended, not just the first one.

  • Thinking left factoring or left recursion removal fixes ambiguity. Both preserve the language and keep an ambiguous grammar ambiguous.

  • Missing indirect left recursion. Check chains like A → B..., B → A..., and nullable prefixes.


GATE and Interview Questions

Show that S → a S | S a | a is ambiguous.

The string aa has two parse trees: S → a S with S → a, and S → S a with S → a. Their leftmost derivations are S ⇒ aS ⇒ aa and S ⇒ Sa ⇒ aa, which use different productions at the first step.

How many parse trees does id + id * id - id have under E → E + E | E * E | E - E | id?

4 operands, so the Catalan number C3 = 5.

Remove left recursion from S → S a b | S c | d e | f.

α1 = a b, α2 = c, β1 = d e, β2 = f. Result: S → d e S' | f S', S' → a b S' | c S' | ε.

Left factor A → x y z | x y w | x v.

A → x A', A' → y A'' | v, A'' → z | w.

In an unambiguous expression grammar, how do you make an operator right-associative?

Use right recursion for its level: for example F → P ^ F | P. The recursive non-terminal appears on the right of the operator, so a ^ b ^ c groups as a ^ (b ^ c).

Is it decidable whether a given CFG is ambiguous?

No, it is undecidable. Some context-free languages, such as { aibjck | i = j or j = k }, are even inherently ambiguous.

Why do LR parsers not need left recursion removal?

An LR parser builds the tree bottom-up and only reduces by A → Aα after it has seen the whole α on its stack, so it never calls anything recursively without consuming input. Left recursion actually keeps an LR parser's stack small for long lists.

Does left factoring make a grammar LL(1)?

Not necessarily. It removes common prefixes, but the grammar can still be ambiguous (like the dangling else) or have FIRST/FOLLOW conflicts. Every LL(1) grammar is unambiguous, not left-recursive and left-factored, but the converse does not hold.


Summary

  • A grammar is ambiguous if some string has two parse trees (two leftmost derivations). Ambiguity means the grammar does not fix the program's meaning.

  • Expression ambiguity is removed with one non-terminal per precedence level; left recursion gives left associativity, right recursion gives right associativity.

  • The dangling else is resolved by matching each else with the closest unmatched then, using matched/unmatched statements or a parser rule.

  • Ambiguity is undecidable in general, and some languages are inherently ambiguous.

  • Left recursion (A ⇒+ Aα) makes top-down parsers loop. Remove it with A → βA', A' → αA' | ε, after substituting earlier non-terminals for indirect recursion.

  • Left factoring (A → αA', A' → β1 | β2) postpones a choice until the common prefix has been read.

  • None of these transformations changes the language, and none removes ambiguity by itself.

Ambiguity is about meaning, left recursion is about termination, and left factoring is about making a decision with one token of lookahead. Fix all three and a grammar is ready for top-down parsing.