← 🌳 Context-Free Grammars & Languages
Subtopic 2 of 5

3.2Ambiguity

The idea

A grammar is ambiguous if some string has two different parse trees.

Think of it like this: "Time flies" can be read two ways; each reading is a different tree.

Why it exists

Ambiguity is a problem for compilers: 2 + 3 × 4 must have one meaning.

How it works

  1. Find a string and build two different trees (or two leftmost derivations).
  2. Fix by layering the grammar: tighter operators deeper in the tree.
  3. Some languages are inherently ambiguous: every grammar for them is ambiguous.
  4. Deciding ambiguity is undecidable.

Worked example: E → E + E | E * E | id on id + id * id

Two trees: (id + id) * id and id + (id * id). The layered grammar E → E + T | T, T → T * F | F gives one.

Now play with it

  • →Count the parse trees for each grammar and look at the bracketed trees.
  • →Try the dangling-else grammar.
E -> E + E | E * E | id
Distinct parse trees2
Verdict for this stringAMBIGUOUS
  • tree 1: (E (E id) + (E (E id) * (E id)))
  • tree 2: (E (E (E id) + (E id)) * (E id))

A grammar is ambiguous if some string has two parse trees (equivalently two leftmost derivations). Two trees for the same string means two different groupings, so possibly two different meanings.

Check yourself

E → E + E | E * E | id is

Remember: Two parse trees for one string = ambiguous. Layering fixes precedence.
Exam notes (the dense version)

A grammar is ambiguous if some string has two parse trees (two leftmost derivations). A language is inherently ambiguous if every grammar for it is ambiguous (e.g. {aⁱbʲcᵏ : i = j or j = k}). Deciding whether a CFG is ambiguous is undecidable.

Previous year questions: Context-Free Grammars & Languages (13)

PYQs are grouped by topic, so this is the full set for Context-Free Grammars & Languages; try the ones that match this subtopic. Open all 13 on the topic page.