Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 59 ยท Context-Free Grammars

Ambiguity in Context-Free Grammars and Languages

Learn what makes a context-free grammar ambiguous, how to detect it, how to remove ambiguity with precedence and associativity, and what inherent ambiguity means.

A grammar is supposed to define the structure of a sentence, not just whether it is valid. In natural language, "I saw the man with the telescope" has two readings. In a programming language such an ambiguity would be a disaster: should 1 + 2 * 3 be 7 or 9? A grammar with this problem is called ambiguous.

Definition

A context-free grammar G is ambiguous if some string in L(G) has two or more different parse trees. Equivalent formulations: the string has two different leftmost derivations, or two different rightmost derivations. (Different derivation orders for the same tree do not count; only different trees do.) A grammar is unambiguous if every string has exactly one parse tree.

The classic example

TEXT
E -> E + E | E * E | ( E ) | id

This grammar generates arithmetic expressions, but id + id * id has two parse trees: one groups it as (id + id) * id, the other as id + (id * id). The grammar says nothing about precedence (which operator is stronger) or associativity (how id + id + id groups). The two readings of a + a * a:

flowchart TB
    subgraph T1["Tree 1: (a + a) * a"]
        A1["E"] --> A2["E"]
        A1 --> A3["*"]
        A1 --> A4["E"]
        A2 --> A5["E (a)"]
        A2 --> A6["+"]
        A2 --> A7["E (a)"]
        A4 --> A8["a"]
    end
    subgraph T2["Tree 2: a + (a * a)"]
        B1["E"] --> B2["E"]
        B1 --> B3["+"]
        B1 --> B4["E"]
        B2 --> B5["a"]
        B4 --> B6["E (a)"]
        B4 --> B7["*"]
        B4 --> B8["E (a)"]
    end

Same input, two different shapes. A compiler needs exactly one.

Counting parse trees in code

A program can count how many parse trees a grammar gives a string: for each variable and substring, add up the number of ways to split the substring among the right-hand side. We use the letter a for id. (This works for grammars without ฮต-rules and without cycles of unit productions.)

Python Count parse trees: ambiguous versus layered grammar

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ambiguous grammar gives 1, 1, 2, 2, 5 and 14 trees as the expression grows: those are Catalan numbers, which grow exponentially. The layered grammar always gives exactly one tree. It is a different grammar for the same language, one that happens to be unambiguous.

Removing ambiguity

There is no mechanical algorithm that removes ambiguity from every grammar, but several patterns solve common cases.

1. Encode precedence by layering. Introduce one variable per precedence level, with the strongest operators at the deepest level: E for +, T for *, F for atoms.

2. Encode associativity by recursion direction. The rule E โ†’ E + T is left-recursive and makes + left-associative: a+a+a groups as (a+a)+a. Using E โ†’ T + E would make it right-associative. For exponentiation, which is right-associative, you would write P โ†’ A ^ P | A.

3. Make a choice explicit. The dangling else problem is a famous case:

TEXT
S -> if b then S | if b then S else S | other

The string if b then if b then other else other can attach the else to either if. Most languages declare that else attaches to the nearest unmatched if, which is implemented by splitting statements into "matched" and "unmatched" forms:

TEXT
S         -> Matched | Unmatched
Matched   -> if b then Matched else Matched | other
Unmatched -> if b then S | if b then Matched else Unmatched
Python Dangling else: count the trees before and after

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the string with a single else and two ifs, the ambiguous grammar gives two trees (the else may go with either if), while the matched/unmatched grammar gives exactly one: the else attaches to the inner if.

Inherent ambiguity

Sometimes ambiguity is not the grammar's fault. A context-free language is inherently ambiguous if every grammar for it is ambiguous. The standard example is

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

The strings with i = j and the strings with j = k overlap on a^n b^n c^n, and any grammar must derive those strings via both reasons, so they get two parse trees. No rewriting can fix it.

Ambiguity is undecidable

You might hope for a program that reads a grammar and says "ambiguous" or "unambiguous". No such program exists. Deciding whether a given CFG is ambiguous is undecidable (it can be reduced from Post's correspondence problem). In practice, parser generators like Yacc and Bison detect conflicts in the grammars they accept, which are warnings of possible ambiguity for restricted classes (LL, LR), and language designers write grammars that fit those classes.

Why it matters

  • Compilers need one parse tree per program so that the meaning is unique.
  • Natural language processing tolerates ambiguity and ranks the trees by probability.
  • Grammar design includes deciding precedence and associativity on purpose instead of by accident.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A grammar is ambiguous if...

    Ambiguity is about two distinct parse trees for one string, equivalently two different leftmost derivations.
  2. 2. How does the grammar E โ†’ E + T | T, T โ†’ T * F | F, F โ†’ a enforce that * binds tighter than +?

    Operators generated at deeper levels become subtrees of operators at higher levels, so they are evaluated first.
  3. 3. Which rule makes + left-associative?

    Left recursion E โ†’ E + T makes the tree grow to the left, so a+a+a groups as (a+a)+a.
  4. 4. What does it mean for a CFL to be inherently ambiguous?

    No rewriting of the grammar can remove the ambiguity; the language itself forces two parse trees for some strings.
  5. 5. Is there an algorithm that decides whether an arbitrary CFG is ambiguous?

    Ambiguity of CFGs is undecidable in general, though many restricted grammar classes can be checked.

Summary

  • A CFG is ambiguous if some string has two different parse trees (two leftmost derivations).
  • Precedence is built by layering variables; associativity by choosing left or right recursion.
  • Ambiguity can often be removed (arithmetic, dangling else), but some languages are inherently ambiguous.
  • Deciding whether a grammar is ambiguous is undecidable; parser generators use restricted classes to be safe.

Next: Simplifying Context-Free Grammars