SLR, CLR and LALR Parsers Compared for GATE: LR Item Sets, Conflicts and Parser Power

GATE-style Compiler Design questions commonly ask three things: how many states a parser has, which table entries clash, and which of SLR(1), CLR(1) and LALR(1) accepts a given grammar. All three run the same shift-reduce engine; only the lookahead information in the item sets changes. So we will build all three machines on one shared grammar and watch where they diverge.

LR item sets: the machinery all three parsers share

An LR(0) item is a production with a dot marking how much of the right-hand side has been seen: A → α·β says α is matched and β is expected next. An LR(1) item adds a lookahead terminal: [A → α·β, a] also records that once this A is reduced, the next input symbol should be a.

States of the automaton are sets of items, built with two operations you must run by hand:

• Closure. If A → α·Bβ is in the set, add B → ·γ for every production of B. In the LR(1) construction, the new items get lookahead FIRST(βa).

• Goto. goto(I, X) moves the dot across X wherever possible, then takes the closure. Each distinct result is a new state.

The parsers differ only at reduce time. SLR(1) builds LR(0) items and reduces A → α on every terminal in Follow(A). CLR(1), the canonical LR(1) parser, builds LR(1) items and reduces only on the item's own lookahead. LALR(1) builds the CLR(1) machine, then merges states with the same core (the same items ignoring lookaheads), taking the union of lookaheads.

The shared grammar: assignments with l-values

This grammar, the classic witness for the SLR versus LALR gap, models assignments whose left side can be a pointer dereference:

S → L = R
S → R
L → * R
L → id
R → L

Read it as: a statement is an assignment L = R or a bare expression R; an l-value L is a dereference * R or a plain id; and R → L says every l-value is also an r-value. Augment with S' → S before building.

SLR(1) on the grammar: 10 states and one fatal conflict

Building the canonical LR(0) collection gives exactly ten states. The kernels (closure items omitted) are:

Now the SLR reduce rule needs Follow sets. Follow(S) = {$}. S → L = R puts = into Follow(L), and R → L pours Follow(R) into Follow(L); S → R contributes $ to Follow(R), and L → * R pours Follow(L) into Follow(R). Solving together: Follow(L) = Follow(R) = {=, $}.

Look at I2. S → L·=R wants to shift on =, while R → L· must reduce on everything in Follow(R). Since = is in Follow(R), the entry at (I2, =) holds both a shift and a reduce: a shift/reduce conflict, so the grammar is not SLR(1). The conflict is semantically spurious, but SLR cannot see that: Follow sets aggregate contexts from the whole grammar.

CLR(1) on the same grammar: 14 states, conflict dissolved

Rebuild with LR(1) items. In the start state, R → ·L arises only from S → ·R with lookahead $, so I2 becomes { [S → L·=R, $], [R → L·, $] }. The reduce now fires only on $, the shift on =, and the two actions never meet. Follow was too coarse; precise lookaheads dissolve the conflict, and CLR(1) accepts the grammar.

The price is states. After L =, every downstream item carries lookahead $ alone, while the same cores reached from I0 carry {=, $}. Four cores split into pairs (L → *·R, L → id·, L → *R· and R → L·), so ten plus four gives 14 CLR(1) states against 10 for SLR.

LALR(1): merge back to 10 states and keep the acceptance

LALR(1) merges every same-core pair, unioning lookaheads. The four split pairs collapse and we land back on exactly 10 LALR states. Not a coincidence: merging by core reproduces the LR(0) collection, so the LALR(1) machine always has the SLR(1) state count.

Does merging bring the conflict back? No. The conflicted core exists in only one CLR state, so nothing merges into it, and the merged R → L· state carries lookaheads {=, $} but no shift item, so nothing clashes. LALR(1) accepts with an SLR-sized table, which is why Yacc and Bison chose it.

One theorem GATE tests directly: merging same-core states can create reduce/reduce conflicts but never a new shift/reduce conflict, because shift actions depend only on the core, and merged states share it.

Which parser accepts: the reduce/reduce drill

That was the shift/reduce gap between SLR and LALR. The second drill grammar exhibits the reduce/reduce gap between LALR and CLR:

S → a A d | b B d | a B e | b A e
A → c
B → c

After a c the CLR state is { [A → c·, d], [B → c·, e] }; after b c it is { [A → c·, e], [B → c·, d] }. Each is conflict-free, so the grammar is LR(1). But they share a core, so LALR merges them, producing a reduce/reduce conflict on both d and e. The grammar is LR(1) but not LALR(1); these two shapes are what which-parser-accepts questions probe.

Parser power and state counts: the comparison table

The hierarchy to memorise: LR(0) grammars are a strict subset of SLR(1), SLR(1) of LALR(1), and LALR(1) of LR(1). On state counts, SLR and LALR always match (the LR(0) count); CLR has at least as many, strictly more when lookaheads split a core.

How GATE tests SLR, CLR and LALR parsers

Three patterns cover almost every question this topic produces:

1. Count the states. Usually numeric answer: build the LR(0) automaton and count, or count CLR states, which means spotting which cores split. Practise until the ten-state construction above takes under five minutes.

2. Which parser accepts. A single- or multi-select listing SLR(1), CLR(1) and LALR(1) against a short grammar. Check SLR by intersecting Follow sets with shift symbols in reduce states; check LALR by testing whether merging creates a reduce/reduce clash. MSQ variants are unforgiving; our guide to GATE question types (MCQ, MSQ and NAT) covers how partial knowledge plays out.

3. Fill or fault the table. Given a parsing-table fragment, identify or classify the conflicting entry. The same skill as pattern 2, cell by cell.

Compiler Design is compact and scoring, and bottom-up parsing is its densest question source; the GATE CS subject weightage analysis shows where it sits in the paper. For topic-wise practice, the bottom-up parsing module of GATE Guidance by Sanchit Sir walks LR(0), SLR(1), CLR(1) and LALR(1) with previous-year questions on each subtopic. For cycle-specific paper rules and scoring, use the official GATE portal.

The short version, and your next step

Five facts to hold. Closure and goto build every machine. The shared grammar: 10 LR(0)/SLR/LALR states, 14 CLR states. SLR fails because = sits in Follow(R); CLR and LALR accept. Merging creates at worst reduce/reduce conflicts, never shift/reduce. Power rises strictly: LR(0), SLR(1), LALR(1), CLR(1).

Then convert theory into marks under a clock. The GATE Test Series includes a dedicated Compiler Design subject test alongside full-length mocks, with rank lists and detailed analysis, so you learn now whether your state counting is fast and correct. Still mapping the wider syllabus? Start from the GATE CS exam category page and return to this drill when parsing reaches your revision list.