We now have two LR parsers with opposite problems. SLR has a small table but uses coarse FOLLOW sets, so it rejects many reasonable grammars. CLR(1) accepts every LR(1) grammar, but splitting states by lookahead can blow the table up from hundreds of states to thousands.
LALR(1) (LookAhead LR) is the compromise that won in practice. It starts from the CLR(1) states and merges every group of states that differ only in their lookaheads. The result has exactly as many states as SLR, but keeps most of CLR's precise lookahead information. Yacc and GNU Bison build LALR(1) parsers by default, which is why this is the LR method you are most likely to use in real life. The method was introduced by Frank DeRemer in his 1969 PhD thesis.
An LALR(1) parser is obtained from the canonical LR(1) collection by merging all item sets that have the same core (the same LR(0) items), taking the union of their lookaheads. A grammar is LALR(1) if the resulting table has no conflicts.
As in the previous two chapters, every item set, table and trace here was produced by a Python generator and checked by hand.
The Idea: Same Core, Merge
Recall the CLR(1) automaton for S → C C, C → c C | d from CLR (Canonical LR) Parsing. It had 10 states, and three pairs looked suspiciously alike:
I3: C → c • C, c/d C → • c C, c/d C → • d, c/d
I6: C → c • C, $ C → • c C, $ C → • d, $
I4: C → d •, c/d
I7: C → d •, $
I8: C → c C •, c/d
I9: C → c C •, $Each pair has the same core (strip the lookaheads and they are identical); only the lookaheads differ. LALR merges each pair into one state whose items carry the union of the lookaheads. I3 and I6 become I36, I4 and I7 become I47, I8 and I9 become I89.
Why is this safe for GOTO? If two states have the same core, then moving the dot over a symbol X in both gives two states that again have the same core. So the targets of merged states are themselves merged, and the GOTO function stays well defined.
Constructing the LALR(1) Table
1. Build the canonical collection of LR(1) item sets C = {I0, I1, ..., In}.
2. Group the sets by core. Replace each group by one set whose items are the
union of the group's items (same cores, lookaheads combined).
Call the new collection C' = {J0, J1, ..., Jm}.
3. Fill ACTION exactly as for CLR(1):
[A → α • a β, b] in Ji → ACTION[i, a] = shift to GOTO(Ji, a)
[A → α •, a] in Ji, A ≠ S' → ACTION[i, a] = reduce A → α
[S' → S •, $] in Ji → ACTION[i, $] = accept
4. GOTO(Ji, X) = the merged state that contains GOTO(Ik, X) for any Ik in Ji's group.
5. If there is a conflict, the grammar is not LALR(1).This "build CLR, then merge" method is the one used in exams. Real tools never build the big CLR collection first: they compute LALR lookaheads directly on the LR(0) automaton, by propagating lookaheads between kernel items (Dragon Book method) or with the DeRemer-Pennello algorithm (1982) that Bison uses. All methods give the same table.
An important consequence of step 2: the merged collection has the same cores as the LR(0) collection, so
Number of LALR(1) states = number of SLR(1) states = number of LR(0) states ≤ number of CLR(1) states.
Worked Example 1: S → C C
(0) S' → S
(1) S → C C
(2) C → c C
(3) C → dAfter merging, the 10 CLR states become 7:
I0:
S' → • S, $
S → • C C, $
C → • c C, c / d
C → • d, c / d
on S → I1 on C → I2 on c → I36 on d → I47
I1:
S' → S •, $
I2:
S → C • C, $
C → • c C, $
C → • d, $
on C → I5 on c → I36 on d → I47
I36:
C → c • C, c / d / $
C → • c C, c / d / $
C → • d, c / d / $
on C → I89 on c → I36 on d → I47
I47:
C → d •, c / d / $
I5:
S → C C •, $
I89:
C → c C •, c / d / $The LALR(1) table, with merged states named by their original numbers:
State | c | d | $ | S | C |
|---|---|---|---|---|---|
0 | s36 | s47 | 1 | 2 | |
1 | acc | ||||
2 | s36 | s47 | 5 | ||
36 | s36 | s47 | 89 | ||
47 | r3 | r3 | r3 | ||
5 | r1 | ||||
89 | r2 | r2 | r2 |
Compare it with the CLR table. Row 47 has r3 under c, d and $, because it combines I4 (c / d) and I7 ($). No cell holds two entries, so the grammar is LALR(1). Parsing c d c c d gives the same moves as CLR, with merged state numbers:
Stack Input Action
0 c d c c d $ s36: shift c, go to 36
0 c 36 d c c d $ s47: shift d, go to 47
0 c 36 d 47 c c d $ r3: reduce C → d, goto[36, C] = 89
0 c 36 C 89 c c d $ r2: reduce C → c C, goto[0, C] = 2
0 C 2 c c d $ s36: shift c, go to 36
0 C 2 c 36 c d $ s36: shift c, go to 36
0 C 2 c 36 c 36 d $ s47: shift d, go to 47
0 C 2 c 36 c 36 d 47 $ r3: reduce C → d, goto[36, C] = 89
0 C 2 c 36 c 36 C 89 $ r2: reduce C → c C, goto[36, C] = 89
0 C 2 c 36 C 89 $ r2: reduce C → c C, goto[2, C] = 5
0 C 2 C 5 $ r1: reduce S → C C, goto[0, S] = 1
0 S 1 $ acceptThe price of merging: delayed error detection
Merging made some reduce entries appear under more lookaheads. On correct input this never matters, but on wrong input the parser may reduce a bit before noticing the problem. Take the incomplete input c c d. CLR stopped immediately:
Stack Input Action
0 c c d $ s3: shift c, go to 3
0 c 3 c d $ s3: shift c, go to 3
0 c 3 c 3 d $ s4: shift d, go to 4
0 c 3 c 3 d 4 $ blank entry [4, $]: syntax errorLALR does three extra reductions first:
Stack Input Action
0 c c d $ s36: shift c, go to 36
0 c 36 c d $ s36: shift c, go to 36
0 c 36 c 36 d $ s47: shift d, go to 47
0 c 36 c 36 d 47 $ r3: reduce C → d, goto[36, C] = 89
0 c 36 c 36 C 89 $ r2: reduce C → c C, goto[36, C] = 89
0 c 36 C 89 $ r2: reduce C → c C, goto[0, C] = 2
0 C 2 $ blank entry [2, $]: syntax errorBoth parsers report the error while looking at the same token, $, and neither ever shifts a wrong token; LALR simply reaches that point after a few harmless reductions. An LALR parser never shifts a token that the CLR parser would reject, so the error is still found on the same input token.
Worked Example 2: The L = R Grammar
(0) S' → S
(1) S → L = R
(2) S → R
(3) L → * R
(4) L → id
(5) R → LIts CLR collection had 14 states. Four pairs share a core: (I4, I11), (I5, I12), (I7, I13) and (I8, I10). Merging each pair (and keeping the smaller number) gives 10 states:
I0:
S' → • S, $
S → • L = R, $
S → • R, $
L → • * R, = / $
L → • id, = / $
R → • L, $
on S → I1 on L → I2 on R → I3 on * → I4 on id → I5
I1:
S' → S •, $
I2:
S → L • = R, $
R → L •, $
on = → I6
I3:
S → R •, $
I4:
L → * • R, = / $
R → • L, = / $
L → • * R, = / $
L → • id, = / $
on R → I7 on L → I8 on * → I4 on id → I5
I5:
L → id •, = / $
I6:
S → L = • R, $
R → • L, $
L → • * R, $
L → • id, $
on R → I9 on L → I8 on * → I4 on id → I5
I7:
L → * R •, = / $
I8:
R → L •, = / $
I9:
S → L = R •, $The crucial state I2 was not merged with anything, so it still says: reduce R → L only on $. The table:
State | = | * | id | $ | S | L | R |
|---|---|---|---|---|---|---|---|
0 | s4 | s5 | 1 | 2 | 3 | ||
1 | acc | ||||||
2 | s6 | r5 | |||||
3 | r2 | ||||||
4 | s4 | s5 | 8 | 7 | |||
5 | r4 | r4 | |||||
6 | s4 | s5 | 8 | 9 | |||
7 | r3 | r3 | |||||
8 | r5 | r5 | |||||
9 | r1 |
No conflicts: the grammar is LALR(1) but not SLR(1). In fact this table is exactly the SLR table from SLR Parsing with one entry removed, the r5 under = in row 2. LALR has the same states as SLR; it just has sharper lookaheads.
Worked Example 3: LALR(1) but Not SLR(1)
Here is another standard grammar, a favourite in textbook exercises:
(0) S' → S
(1) S → A a
(2) S → b A c
(3) S → d c
(4) S → b d a
(5) A → dFOLLOW(S) = { $ }
FOLLOW(A) = { a, c }Two LR(0) states contain the item A → d • together with a shift:
I4:
S → d • c
A → d •
on c → I8
I7:
S → b d • a
A → d •
on a → I10SLR puts r5 (A → d) under FOLLOW(A) = { a, c }. In I4 that clashes with the shift on c, and in I7 with the shift on a: two shift-reduce conflicts, so the grammar is not SLR(1).
The LR(1) versions of these states carry precise lookaheads:
I4:
S → d • c, $
A → d •, a
on c → I8
I7:
S → b d • a, $
A → d •, c
on a → I10In I4 the reduce is only on a (from S → • A a), in I7 only on c (from S → b • A c). No conflicts. This grammar's LR(1) collection has 11 states, the same as its LR(0) collection, so there is nothing to merge and the LALR(1) table equals the CLR(1) table. The grammar is LALR(1) but not SLR(1).
When Merging Creates a Conflict
Merging can only add lookaheads to items, so it can, in principle, create a conflict that CLR did not have. Let's see what kind.
Merging never creates a new shift-reduce conflict
Suppose a merged state has a shift-reduce conflict on token a: it contains [A → α •, a] and an item [B → β • a γ, b].
The item [A → α •, a] came from one of the original CLR states, say Ik.
All states in the group have the same core, so Ik also contains the core B → β • a γ (with some lookahead).
Shifts don't depend on lookaheads, so Ik already had both "reduce on a" and "shift on a".
So the conflict was already in the CLR table. If the grammar is CLR(1), LALR(1) can have no shift-reduce conflicts.
But it can create a reduce-reduce conflict
(0) S' → S
(1) S → a A d
(2) S → b B d
(3) S → a B e
(4) S → b A e
(5) A → c
(6) B → cThe language is just { acd, bcd, ace, bce }. In the CLR collection, after a c and after b c we reach two different states:
I6:
A → c •, d
B → c •, e
I9:
B → c •, d
A → c •, eEach state is conflict-free: after a c, a following d means A and e means B; after b c it is the other way round. The grammar is CLR(1). But I6 and I9 have the same core { A → c •, B → c • }, so LALR merges them:
I6,9:
A → c •, d / e
B → c •, d / eNow both reductions are under both d and e: two reduce-reduce conflicts. The grammar is CLR(1) but not LALR(1). (Bison reports exactly this: "2 reduce/reduce conflicts", as we will see in Yacc & Bison.)
If a grammar is CLR(1), its LALR(1) table can contain reduce-reduce conflicts, but never shift-reduce conflicts.
SLR vs LALR vs CLR
Feature | SLR(1) | LALR(1) | CLR(1) |
|---|---|---|---|
Items | LR(0) | LR(1), merged by core | LR(1) |
Reduce A → α placed under | FOLLOW(A) | Union of lookaheads of the merged items | Exact lookahead of the item |
Number of states | n (LR(0) count) | n (same as SLR) | ≥ n, often much more |
Power | Lowest | Middle | Highest (all LR(1) grammars) |
Conflicts possible | S/R and R/R | S/R and R/R; for a CLR(1) grammar, only R/R | None for an LR(1) grammar |
Error detection | May reduce before detecting | May reduce before detecting | Immediate |
Used by | Teaching, simple tools | Yacc, Bison (default), many generators | Bison with |
Grammar classes: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1)
Table sizes (states): LR(0) = SLR(1) = LALR(1) ≤ CLR(1)Each inclusion is strict:
Expression grammar: SLR(1), not LR(0).
L = R grammar and the S → A a | b A c | d c | b d a grammar: LALR(1), not SLR(1).
S → a A d | b B d | a B e | b A e: CLR(1), not LALR(1).
Common Mistakes
Merging states whose cores differ. Merge only if the LR(0) parts are exactly equal, item for item. Same lookaheads with different cores is not a reason to merge.
Forgetting to rename GOTO targets. After merging I3 and I6 into I36, every transition that went to I3 or to I6 must now go to I36.
Using FOLLOW sets. LALR lookaheads are unions of LR(1) lookaheads within a group, which are usually smaller than FOLLOW. If you use FOLLOW you get SLR.
Claiming LALR can introduce shift-reduce conflicts. Relative to CLR, it can introduce only reduce-reduce conflicts.
Thinking LALR misses errors. It detects the same errors on the same token; it may just perform some reductions first.
Practice Questions
Q1. A grammar has n1 states in its SLR(1) parser, n2 in its LALR(1) parser and n3 in its CLR(1) parser. What is the relation?
n1 = n2 ≤ n3. SLR and LALR both have one state per LR(0) core. CLR can split one core into several states by lookahead (for S → C C: 7, 7 and 10).
Q2. A grammar is CLR(1). Which conflicts can its LALR(1) table have?
Only reduce-reduce conflicts. A shift-reduce conflict in a merged state would already exist in one of the original CLR states, because shifts don't depend on lookaheads and all merged states share the same core.
Q3. Two CLR(1) states are I = { [A → x •, a], [B → x •, b] } and J = { [A → x •, b], [B → x •, c] }. What happens in LALR?
They have the same core, so they merge into { [A → x •, a / b], [B → x •, b / c] }. Both reductions are under b: a reduce-reduce conflict. The grammar is not LALR(1) (although these two states are fine in CLR).
Q4. Is every SLR(1) grammar LALR(1)?
Yes. For every item in a merged LALR state, the lookaheads are a subset of FOLLOW of its left-hand side, and the shifts are the same as SLR's. So LALR's reduce entries are a subset of SLR's, and it cannot have a conflict SLR doesn't have.
Q5. On the input c c d (not in the language of S → C C), what does the LALR parser do before reporting the error, compared with CLR?
CLR reports the error in state 4 as soon as it sees $. LALR, in state 47, has r3 under $, so it reduces C → d, then C → c C twice, reaching state 2, and only then finds the blank entry [2, $]. Same error token, three extra reductions.
Q6. Which parser does Bison generate by default, and how can you ask for others?
LALR(1) by default. %define lr.type ielr gives IELR(1) (full LR(1) power, with tables usually close to LALR size) and %define lr.type canonical-lr gives canonical LR(1).
Summary
LALR(1) = canonical LR(1) states merged by identical core, with lookaheads combined.
It has the same number of states as SLR / LR(0), but much sharper lookaheads than FOLLOW.
LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1), with examples showing each step is strict.
Merging never adds a shift-reduce conflict to a CLR(1) grammar, but may add reduce-reduce conflicts.
LALR may perform a few extra reductions before reporting an error, but never shifts an erroneous token.
Yacc and Bison generate LALR(1) parsers by default.
LALR keeps SLR's small table and most of CLR's power: merge the look-alike states, union their lookaheads.