2.4.6 Power and state-count comparison of LL(1), LR(0), SLR, LALR, CLR; grammar-classification drills

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

Which kind of conflict can LALR merging create? from Lesson 2.4.5
How does SLR place a reduce for A → α•? from Lesson 2.4.3
Is a grammar with an ε-alternative and a FOLLOW overlap LL(1)? from Lesson 2.3.2

1 · The Story

📖

Which method for which rulebook?

Mrs. Desai asks Kabir for a league table. Each method has a cost (the size of the chart on the wall) and a reach (how many rulebooks it can handle without clashes).

Chetan’s chart (one word, top-down) is the simplest but rejects any rulebook with rules that start with themselves. Kabir’s blind folding (LR(0)) is small but panics often. Folding with follower lists (SLR) is just as small and panics less. Pinned bundles with notes (LALR) are still small and panic only rarely. Full notes (CLR) never panic falsely but need the biggest wall.

And one rule rules them all: a two-faced rulebook (ambiguous) defeats every method.

2 · Predict First

🤔

Is every LL(1) grammar also SLR(1)? Write your guess down. The answer is in the vault.

3 · Core Concept

Inclusions between grammar classes

LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1) (each inclusion strict).
LL(1) ⊂ LR(1) (strict).
LL(1) is not contained in SLR(1) or even LALR(1); and LR(0) is not contained in LL(1). These classes overlap.
No ambiguous grammar is in any of them.

Table sizes

Method	Automaton	Number of states	Reduce entries placed by
LR(0)	LR(0) items	n	all columns
SLR(1)	LR(0) items	n (same)	FOLLOW(A)
LALR(1)	LR(1) items merged by core	n (same)	merged lookaheads
CLR (LR(1))	LR(1) items	≥ n, often much more	item lookahead
LL(1)	none (table of nonterminals × terminals)	—	FIRST / FOLLOW

A quick classification procedure

Ambiguous? Then nothing.
LL(1)? Check FIRST/FOLLOW disjointness (left recursion or common prefixes give an instant no).
Build the LR(0) automaton. No state with a complete item plus anything else? LR(0).
Conflicting states resolved by FOLLOW? SLR(1).
Otherwise compute lookaheads: no conflict after merging? LALR(1). Conflict only before merging … impossible; conflict only after merging? LR(1) but not LALR(1).

Story → compiler term

In the story	In the compiler
the league table	comparison of parsing methods
size of the wall	number of states / table size
reach	class of grammars accepted
Chetan’s chart	LL(1)
blind folding	LR(0)
follower lists	SLR(1)
pinned bundles with notes	LALR(1)
full notes	CLR / LR(1)

4 · Visual

Grammar	LL(1)	LR(0)	SLR(1)	LALR(1)	CLR(1)	States LR(0)/CLR
`E → E+T	T, T → T*F	F, F → (E)	id`	✘	✘	✔
`S → AA, A → aA	b`	✔	✔	✔	✔	✔
`S → L=R	R, L → *R	id, R → L`	✘	✘	✘	✔
`S → aAd	bBd	aBe	bAe, A → c, B → c`	✘	✘	✘
`S → Aa	bAc	dc	bda, A → d`	✘	✘	✘
`S → AaAb	BbBa, A → ε, B → ε`	✔	✘	✘	✔	✔
`S → xAy	xBz, A → q, B → q`	✘	✘	✔	✔	✔
`S → (L)	a, L → L,S	S`	✘	✔	✔	✔
`S → Aa, A → bA	ε`	✔	✘	✔	✔	✔
`S → iEtSS'	a, S' → eS	ε, E → b`	✘	✘	✘	✘

Every cell computed by building the corresponding table. The last grammar is ambiguous (dangling else), so it fails everywhere.

5 · Worked Examples

Example 1 Easy

Classify S → x A y | x B z, A → q, B → q.

Solution

Not LL(1) (both S-alternatives start with x). LR(0): after x q, one state holds A → q• and B → q• (R/R). SLR: FOLLOW(A) = {y}, FOLLOW(B) = {z} are disjoint, so the reduces separate: SLR(1), hence also LALR(1) and LR(1).

Example 2 Medium

Classify S → A a A b | B b B a, A → ε, B → ε.

Solution

LL(1): the S-alternatives start with a and b respectively: yes. LR(0)/SLR: the start state contains A → • and B → •, and FOLLOW(A) = FOLLOW(B) = {a, b}: R/R, not SLR. LALR/CLR: in the start state the lookaheads are a for A and b for B: LALR(1). Kabir’s league table in one grammar: LL(1) does what SLR cannot.

Example 3 GATE

Classify S → A a | b A c | d c | b d a, A → d.

Solution

Not LL(1) (FIRST(Aa) and FIRST(dc) both contain d). In the LR(0) state after d, items A → d• and S → d•c: FOLLOW(A) contains c (from b A c), so SLR has an S/R conflict on c. With lookaheads, A → d• in that state has lookahead a only: no conflict. Answer: LALR(1) and LR(1), not SLR(1) (computed).

6 · Shortcuts

⚡

Fast eliminations: ambiguous → none; left recursive or common prefixes → not LL(1) (LR still possible); ε-productions in many states → LR(0) usually fails. Valid when: MSQs listing the classes a grammar belongs to.

⚡

State counts: LR(0) = SLR = LALR; CLR ≥ them. Valid when: NAT questions on table sizes.

7 · GATE Traps

⚠️

LL(1) and SLR(1) are incomparable: neither contains the other.
Every LL(1) grammar is LR(1), but not necessarily LALR(1).
Left recursion is harmless for LR parsing.
A grammar that is LR(1) but not LALR(1) fails LALR with an R/R conflict.
Ambiguous grammars belong to no LL or LR class.

8 · Memory Hook

🧠

Power: LR(0) < SLR < LALR < CLR, and LL(1) < CLR. Size: LR(0) = SLR = LALR ≤ CLR.

9 · Connect the Dots

Real parser generators accept even some ambiguous grammars, if you tell them how to break ties. The last lesson of the chapter covers that, plus a fast special-purpose method for expressions and how parsers recover from errors.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MSQ2 marksClassification

S → A a A b | B b B a, A → ε, B → ε belongs to which classes?

(A) LL(1)
(B) SLR(1)
(C) LALR(1)
(D) LR(1)

Q2MCQ1 markInclusions

Which inclusion is false?

(A) LR(0) ⊂ SLR(1)
(B) SLR(1) ⊂ LALR(1)
(C) LL(1) ⊂ SLR(1)
(D) LALR(1) ⊂ LR(1)

Q3MCQ2 marksClassification

S → A a | b A c | d c | b d a, A → d is:

(A) SLR(1)
(B) LALR(1) but not SLR(1)
(C) LR(1) but not LALR(1)
(D) not LR(1)

Q4NAT1 markStates

The grammar S → ( L ) | a, L → L , S | S has how many canonical LR(1) states? (Its LR(0) automaton has 9.)

Numerical answer: ________

Q5MCQ1 markSizes

For any grammar, which pair always has the same number of states?

(A) SLR(1) and CLR(1)
(B) LALR(1) and LR(0)
(C) LL(1) and LR(0)
(D) CLR(1) and LALR(1)

11 · Rule Card

LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1); LL(1) ⊂ LR(1); LL(1) and SLR/LALR overlap without inclusion.
States: LR(0) = SLR = LALR ≤ CLR.
Ambiguous ⇒ in no class.
Classify in order: ambiguity, LL(1), LR(0), SLR, LALR, CLR.

12 · Concept Ledger

grammar classesstate-count comparisonclassification procedure

13 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Warm-up

Only reduce/reduce.
Under FOLLOW(A).
No: if β ⇒* ε and FIRST(α) ∩ FOLLOW(A) ≠ ∅, the cell M[A, a] gets two productions.

Predict First

No. S → A a A b | B b B a, A → ε, B → ε is LL(1) but not SLR(1) (and not LR(0)): reduce/reduce conflicts on a and b in the start state. It is LALR(1) and LR(1).