How many shift-reduce conflicts exist in the LR(0) ACTION table for GATE CS 2026 Set-2 Q41?

There are 5 shift-reduce conflicts (Option D). They occur in: I0 (A→epsilon vs shift a), I1 (C→epsilon vs shift c), I2 (A→epsilon vs shift a again in recursive A state), I5 (C→epsilon vs shift c in recursive C state), and I8 (B→b complete vs B→b•B shift b). The epsilon productions of A and C each contribute 2 conflicts each, and B contributes 1.

What causes shift-reduce conflicts in LR(0) parsing?

A shift-reduce conflict in LR(0) occurs when a parser state contains both a complete item (dot at the rightmost position, indicating reduce) and an item with the dot before a terminal (indicating shift). Since LR(0) uses no lookahead, the parser cannot decide whether to shift or reduce. Epsilon productions are a common source because they introduce complete items into states that also have shift items.

Why do epsilon productions cause shift-reduce conflicts in LR(0)?

An epsilon production like A→ε generates the complete LR(0) item A→• immediately in the closure of any state where A is expected. If that same state also contains an item with the dot before a terminal (like A→•aA), both a reduce action and a shift action are valid in that state — creating a shift-reduce conflict. Since LR(0) has no lookahead to resolve the ambiguity, the conflict is unavoidable.

LR(0) Shift-Reduce Conflicts ACB Grammar | GATE CS 2026 Set-2 Q41

Computer Sciences > GATE 2026 SET-2 > Compiler Design

Consider the canonical 𝐿𝑅(0) parsing of the grammar below using terminals {𝑎,𝑏,𝑐} and non-terminals {𝐴,𝐵,𝐶,𝑆} with 𝑆 as the start symbol.
S→𝐴𝐶𝐵
A→𝑎𝐴 | 𝜖
C→𝑐𝐶 | 𝜖
B→𝑏𝐵 | 𝑏
Which one of the following options gives the number of shift-reduce conflicts that will occur in the 𝐿𝑅(0) ACTION table?

Correct : d

The correct answer is Option D — 5 shift-reduce conflicts.
A shift-reduce conflict in an LR(0) state occurs when the state contains both a complete item (dot at the end → reduce) and an item with the dot before a terminal (→ shift). The grammar has ε-productions for A and C, which introduce complete items into states alongside shift items, creating conflicts.
State I0 contains A→• (reduce A→ε) and A→•aA (shift ''''a'''') → Conflict 1.
State I1 = GOTO(I0, A) contains C→• (reduce C→ε) and C→•cC (shift ''''c'''') → Conflict 2.
State I2 = GOTO(I0, a) contains A→• (reduce A→ε) and A→•aA (shift ''''a'''') → Conflict 3.
State I5 = GOTO(I1, c) contains C→• (reduce C→ε) and C→•cC (shift ''''c'''') → Conflict 4.
State I8 = GOTO(I4, b) contains B→b• (reduce) and B→b•B (shift ''''b'''') → Conflict 5.
No other states produce shift-reduce conflicts. The B production B→bB|b causes a conflict because both B→b• and B→b•B appear in the same state. The ε-productions of A and C each cause conflicts in two states — one at the initial state and one in the recursive state.

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev