An AMBIGUOUS grammar is one where
Adifferent programs produce the same output
Bthe grammar generates infinitely many strings
Cthe grammar is incomplete
Dsome string has TWO OR MORE distinct parse trees
Answer & Solution
Correct answer: D. some string has TWO OR MORE distinct parse trees
1. AMBIGUITY: a CFG that admits more than one parse tree for the same string.
2. Each parse tree means a DIFFERENT INTERPRETATION of the program — bad for compilers.
3. Classic example: arithmetic expression $a + b * c$. Without precedence, it could parse as $(a + b) * c$ or $a + (b * c)$.
4. SOLUTION: rewrite the grammar to encode precedence as nesting levels:
- $E \to E + T \mid T$
- $T \to T * F \mid F$
- $F \to id \mid (E)$
5. Other options misstate ambiguity.
_Source: Bob Nystrom, "Crafting Interpreters", Ch 6.1 (Ambiguity and the Parsing Game)._
Related questions
The FOLLOW(A) set in LL parsing isThe FIRST(α) set of a string α in LL parsing isAfter the parser produces an AST, the next compiler phase is typicallyA SHIFT/REDUCE CONFLICT in an LR parser occurs whenWhich of these is a BOTTOM-UP (LR) parser feature?An LL(1) grammar requires that, given the leftmost non-terminal and ONE token of lookaheadLL parsers (recursive descent) parse from thePANIC MODE error recovery in a parser works by