alleryStart learning →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)._
Keep practising Compiler Design
Browse all Compiler Design questions for GATE CSE, or explore more Computer Science topics.
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 whenLL parsers (recursive descent) parse from thePANIC MODE error recovery in a parser works byWhat is a SYNTAX ERROR?How does a parser typically encode OPERATOR PRECEDENCE in the grammar?