Assume that the SLR parser for a grammar G has n1 states and the LALR parser…
2003
Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is:
- A.
n1 is necessarily less than n2
- B.
n1 is necessarily equal to n2
- C.
n1 is necessarily greater than n2
- D.
none of these
Attempted by 65 students.
Show answer & explanation
Correct answer: B
Answer: n1 is necessarily equal to n2.
Explanation:
SLR(1) constructs parser states from LR(0) item sets; the number of these states is n1.
Canonical LR(1) builds states with lookahead and may produce many more states, but LALR(1) is formed by merging canonical LR(1) states that share the same LR(0) core.
Each distinct LR(0) core corresponds to exactly one SLR(1) state, and LALR(1) produces exactly one state per such core by merging LR(1) states with that core. Therefore the number of LALR(1) states is n2 = n1.
In short: SLR(1) and LALR(1) have the same state-count; canonical LR(1) can have equal or greater number of states.
A video solution is available for this question — log in and enroll to watch it.