LR Parsing Power: SLR(1), CLR(1), and LALR(1) (Low → High)

In the LR parsing family, the “power” of a parser class is commonly understood as how many grammars it can parse using the class’s $k=1$ lookahead construction. For the standard hierarchy among SLR(1), LALR(1), and CLR(1), the containment is:

[ \text{SLR(1)} \subset \text{LALR(1)} \subset \text{CLR(1)} ]

So, from low to high power, the correct order is:

[ \boxed{\text{SLR, LALR, CLR}} ]

Thus the correct multiple-choice option is (ii) LALR, SLR, CLR? Not quite—option (ii) is LALR, SLR, CLR, which is not consistent with the correct low→high ordering. The option that matches SLR, LALR, CLR is:

• Correct ordering (low → high): SLR, LALR, CLR

Therefore, none of the listed options matches exactly the standard containment order.
(If forced to choose among the provided permutations, the closest consistent relative placement would be keeping CLR last, but SLR and LALR are swapped in every offered choice relative to the correct hierarchy.)

Key terms: LR(1) SLR(1) LALR(1) CLR(1).

3

Why the hierarchy holds (intuition)

SLR(1) uses relatively coarse lookahead: for a reduction by $A \to \alpha$, SLR(1) reduces on terminals in $\text{FOLLOW}(A)$, which may include strings where reduction is invalid—so SLR(1) can introduce conflicts earlier. CLR(1) uses full canonical LR(1) lookahead, yielding the most precise reduce/shift decisions. LALR(1) sits between: it refines lookahead compared to SLR by starting from LR(1)-style information, but merges states to reduce size, yielding fewer conflicts than SLR but (in general) no more than CLR.

Key terms: lookahead FOLLOW set canonical LR(1) items state merging.

3