An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and…
2008
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
- A.
the SLR(1) parser for G has S-R conflicts
- B.
the LR(1) parser for G has S-R conflicts
- C.
the LR(0) parser for G has S-R conflicts
- D.
the LALR(1) parser for G has reduce-reduce conflicts
Attempted by 58 students.
Show answer & explanation
Correct answer: B
Answer: the LR(1) parser for G has S-R conflicts
Reasoning:
LALR(1) is produced by merging LR(1) states that have the same LR(0) core.
Shift actions depend only on the LR(0) core (the presence of an item with the dot before a terminal). If a shift on a symbol exists in one LR(1) state with a given core, it exists in every LR(1) state with that core.
Reduce actions depend on LR(1) lookahead sets. When merging states, lookahead sets are unioned; this can produce reduce-reduce conflicts by bringing different reductions under the same lookahead symbol.
Because shift actions are determined by the core and are present in all states with that core, any shift-reduce conflict that appears after merging must already have existed in some LR(1) state. Conversely, an S-R conflict in LR(1) remains after merging. Therefore shift-reduce conflicts occur in LALR(1) exactly when they occur in LR(1).
Conclusion: LALR(1) can have shift-reduce conflicts if and only if the LR(1) parser for the grammar has shift-reduce conflicts.
A video solution is available for this question — log in and enroll to watch it.