Home › GATE CSE › computerscience › Compiler Design › A SHIFT/REDUCE CONFLICT in an LR parser occurs w…
A SHIFT/REDUCE CONFLICT in an LR parser occurs when
Aparser cannot pick shift or reduce in a state
Btwo different tokens overlap
Cthe input file has shifted
Dthe grammar has too many rules
Answer & Solution
Correct answer: A. parser cannot pick shift or reduce in a state
1. At each step, an LR parser must decide: SHIFT (consume more input) or REDUCE (apply a grammar rule)?
2. SHIFT/REDUCE CONFLICT: in some state with some lookahead, the parser cannot decide between shifting and reducing — the grammar is AMBIGUOUS at that point.
3. CLASSIC EXAMPLE: the 'dangling else' problem.
`if (x) if (y) a; else b;`
Should the else match the outer if or the inner if?
4. yacc/bison resolve by preferring SHIFT (matches the inner if — the common convention).
5. Some grammars can be rewritten to remove conflicts; others (truly ambiguous) cannot.
6. Other options misstate the conflict.
_Source: Bob Nystrom, "Crafting Interpreters", Ch 6 — referenced + standard compiler theory._
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 typicallyWhich 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 byWhat is a SYNTAX ERROR?