GATE CS 2003 Q17 — Parsing (LL, LR)

To find the relationship between the number of states in an SLR parser ($n_1$) and an LALR parser ($n_2$) for any grammar $G$, we can analyze how their state machines are constructed:

1. SLR(1) Parser: The SLR(1) parser is constructed directly from the LR(0) collection of items. The lookahead sets are only used during the table construction phase (specifically for reduction actions using the $FOLLOW$ sets). Thus, the number of states in the SLR(1) parser ($n_1$) is exactly equal to the number of states in the LR(0) automaton.
2. LALR(1) Parser: The LALR(1) parser is constructed by taking the CLR(1) parser (which uses LR(1) items) and merging states that have the same core (i.e., the same set of LR(0) items, differing only in their lookahead sets). Since every state in the LR(0) automaton represents a unique core, merging all CLR(1) states with identical cores results in a state machine that has the exact same state structure as the LR(0) automaton. Thus, the number of states in the LALR(1) parser ($n_2$) is also exactly equal to the number of states in the LR(0) automaton.

Since both $n_1$ and $n_2$ are equal to the number of states in the LR(0) automaton for the grammar $G$, we have:

Therefore, $n_1$ is necessarily equal to $n_2$.