GATE CS 2005 Q60 — Parsing (LL, LR)

To find the relationship between the number of states in SLR(1), LR(1), and LALR(1) parsers, we use the following standard properties of LR parsers:

1. SLR(1) and LALR(1) States: The state construction of both SLR(1) and LALR(1) is based on the LR(0) state machine. LALR(1) is formed by merging the states of the LR(1) parser that share the same core (LR(0) items). Therefore, the number of states in SLR(1) ($n_1$) is always exactly equal to the number of states in LALR(1) ($n_3$).
   Thus, $n_1 = n_3$.
2. LR(1) States: An LR(1) parser keeps states with the same core but different lookaheads separate. For the given grammar $S \rightarrow (S) \mid a$, nested parentheses introduce different lookaheads for the same core items. For example:
   • After seeing the first (, the lookahead for $S$ is $.
   • After seeing the second (, the lookahead for $S$ is ).
   This splits the LR(1) states, making $n_2 > n_1$.

Combining these, we get the relationship: $n_1 = n_3 < n_2$.