Which of the following statements about CLR(1) and LALR(1) parsers is correct?
Which of the following statements about CLR(1) and LALR(1) parsers is correct?
Answer: A. If a grammar is CLR(1) but not LALR(1), then the LALR(1) parsing table must contain a reduce-reduce conflict. — Correct answer: If a grammar is CLR(1) but not LALR(1), then the LALR(1) parsing table must contain a reduce-reduce conflict. In LALR(1), CLR(1) item sets…
- A.
If a grammar is CLR(1) but not LALR(1), then the LALR(1) parsing table must contain a reduce-reduce conflict.
- B.
If a grammar is CLR(1) but not LALR(1), then the LALR(1) parser must contain a shift-reduce conflict.
- C.
If a grammar has no conflicts under CLR(1), then it cannot have any conflicts under LALR(1).
- D.
None of these
Attempted by 40 students.
Show answer & explanation
Correct answer: A
Correct answer: If a grammar is CLR(1) but not LALR(1), then the LALR(1) parsing table must contain a reduce-reduce conflict.
In LALR(1), CLR(1) item sets with the same LR(0) core are merged, and their lookahead sets are unioned. This merging cannot introduce a new shift-reduce conflict because shift actions depend on the LR(0) core. If a shift on a terminal existed in the merged core, it already existed in each CLR(1) state with that core.
However, merging can make two different reduce items acquire overlapping lookaheads. That creates a reduce-reduce conflict. Therefore, if a grammar is CLR(1) but not LALR(1), the conflict introduced during LALR merging is a reduce-reduce conflict.
A video solution is available for this question — log in and enroll to watch it.