GATE CS 1998 Q1.26 — Parsing (LL, LR)

The power of different LR parsers is determined by the class of grammars they can successfully parse without encountering shift-reduce or reduce-reduce conflicts.

The hierarchy of parsing power is as follows:

$$\text{LR}(0) \subsetneq \text{SLR}(1) \subsetneq \text{LALR}(1) \subsetneq \text{LR}(1)$$

Where $\text{LR}(1)$ is the Canonical LR (CLR) parser.

• Canonical LR (CLR) is the most powerful because it keeps lookaheads separate for each state, avoiding conflicts.
• LALR(1) is obtained by merging states in CLR that have the same core items but different lookaheads. This merging can introduce reduce-reduce conflicts, making LALR strictly less powerful than CLR.
• SLR(1) is less powerful than LALR because it uses the $Follow$ set of the non-terminal for reduction decisions, which is less precise than LALR's specific lookaheads.

Therefore, the Canonical LR parser is strictly more powerful than the LALR parser.