Ambiguity
1. Definition
A grammar is ambiguous if some string has two or more distinct parse trees (two leftmost derivations). Means two meanings — compiler cannot choose. Example: E → E+E | E*E | id gives id+id*id two trees ( + at root vs * at root).
2. Detecting and Proving
- Find a string with two leftmost derivations or two parse trees.
- Classic: dangling else —
if E then if E then S else Sattaches else to inner or outer if. - Ambiguity is undecidable in general (no algorithm for all grammars).
3. Removing Ambiguity (exam skill)
ambiguous: E → E+E | E*E | (E) | id
unambiguous (layers enforce precedence):
E → E+T | T | T → T*F | F | F → (E) | id
Techniques: stratify by precedence (separate non-terminals per level), fix associativity (left-recursive = left-assoc), add delimiters (endif, braces).
4. Ambiguity vs Conflicts
Ambiguous grammar ⇒ no deterministic parser (never LL(1)/LR). But conflicts in a table do not prove ambiguity — may just need more lookahead.
5. Exam Points
- Define ambiguity + give two trees for expression — 5-7 marks, very frequent.
- Remove ambiguity from given grammar — 5-7 marks, very frequent.
- Dangling else example + fix — 5 marks, frequent.