In bottom-up compiler design, deterministic shift-reduce parsers form a strict hierarchy of parsing power: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ Canonical LR(1). Canonical LR(1), often called CLR, provides the highest precision by pairing every grammar production and dot position with an exact lookahead token. However, for full programming language grammars like C or Java, canonical LR(1) tables explode in size, demanding thousands of states.
LALR(1) (Look-Ahead LR) solves this table explosion by merging canonical states that share the exact same LR(0) core. This compression reduces the state count down to the size of an LR(0) automaton, making practical parser generators like Yacc and Bison feasible.
Yet merging states comes with a theoretical catch: while merging identical cores never introduces shift/reduce conflicts into a conflict-free LR(1) grammar, it can introduce reduce/reduce conflicts. Understanding why this happens is a classic midterm and final exam question in compiler courses.
All state collections, action tables, and parse traces in this guide were computed using the site's compiler library. You can experiment with this exact grammar in the interactive LR parser. We write end for the end-of-input marker.
Canonical LR(1) items and closures
An LR(0) item records a production and how much of its right-hand side has been read: A → α • β. Because an LR(0) item carries no forward context, an SLR(1) parser must fall back to the global FOLLOW(A) set to decide when a reduction is safe. This global set is frequently too broad, generating false conflicts.
A canonical LR(1) item sharpens this decision by adding a second component:
[A → α • β, a]
Here A → α • β is the production and dot position (called the core), and a is a lookahead token (either a terminal or end).
The lookahead a means: if this production eventually reduces (when the dot reaches the end, A → α β •), the reduction by A → α β is only valid if the next incoming input token is exactly a.
The closure operation
To build state item sets, the parser repeatedly computes closures:
- Initial items: Any item already in the state belongs to its closure.
- Expansion: If an item
[A → α • B β, a]is in the closure, then for every productionB → γin the grammar and every terminalbinFIRST(β a), add[B → • γ, b]to the closure. - Repeat until no new items can be added.
Notice how FIRST(β a) restricts the lookaheads. The lookahead b depends directly on what immediately follows B in this specific rule (β), backed up by the outer lookahead a only when β derives ε. This contextual lookahead is vastly more precise than SLR's global FOLLOW(B).
Use our FIRST and FOLLOW calculator to check prerequisite first sets when working through homework derivations.
The GOTO operation
For an item set I and any grammar symbol X (terminal or non-terminal), GOTO(I, X) finds every item [A → α • X β, a] in I, shifts the dot past X to get [A → α X • β, a], and computes the closure of that set.
What is an LR(0) core and how LALR(1) merges states
The core of an LR(1) item is simply the production and dot position A → α • β, ignoring the lookahead. The core of an LR(1) state is the set of all its item cores.
During canonical LR(1) construction, different parsing paths often arrive at states with identical cores that differ only in their lookahead sets. For example, one state might contain [C → c • C, c/d] while another contains [C → c • C, end]. Both states are waiting to see the exact same grammatical structure; they differ only in what input tokens are allowed to follow.
The LALR(1) merging algorithm
- Construct the complete canonical LR(1) collection of states.
- Group together all canonical states that possess the exact same LR(0) core.
- Replace each group with a single merged LALR(1) state:
- The core items remain unchanged.
- For each core item, the merged lookahead set is the mathematical union of its lookaheads across all states in the group.
- Redirect all transitions to point to the merged states.
Because the number of distinct cores equals the number of LR(0) states, an LALR(1) parser always has the exact same number of states as an LR(0) or SLR(1) parser. For large languages, this slashes state counts by a factor of 10 or more.
Why LALR merging never creates shift/reduce conflicts
A major theorem of compiler construction states: If a grammar is canonical LR(1), merging states with identical cores can never introduce a shift/reduce conflict.
Here is the proof intuition:
Suppose, for the sake of contradiction, that merging states created a shift/reduce conflict on terminal x in a merged state S. For a shift/reduce conflict to exist in S, the merged state must contain:
- A shift item:
[A → α • x β, c](which demands shifting onx). - A reduce item:
[B → γ •, x](which demands reducing byB → γon lookaheadx).
The shift item originated from some canonical state I_1 in the merge group. The reduce item originated from some canonical state I_2 in the merge group.
However, I_1 and I_2 have identical LR(0) cores. Because I_1 contains A → α • x β in its core, I_2 must also contain A → α • x β in its core, with some lookahead d!
This means canonical state I_2 already contained both:
[A → α • x β, d](demanding a shift onx)[B → γ •, x](demanding a reduction onx)
Therefore, canonical state I_2 would already have possessed a shift/reduce conflict on terminal x before any merging took place.
If the grammar was conflict-free in canonical LR(1), no such canonical state could exist. Hence, LALR(1) state merging can never introduce a new shift/reduce conflict.
When LALR merging introduces reduce/reduce conflicts
While shift actions are determined entirely by core productions, reduce actions depend directly on lookahead sets.
When two canonical states with identical cores are merged, their lookaheads are unioned. If two different complete items A → c • and B → c • appear in the same core with disjoint lookaheads in different canonical states, unioning their lookaheads can cause them to overlap on the same terminal token.
When that happens, the merged LALR state cannot determine whether to reduce by production A or production B upon seeing that token. This is a reduce/reduce conflict caused purely by state merging.
Worked grammar: LR(1) but not LALR(1)
To observe this conflict mechanism step by step, we examine the classic textbook grammar (Dragon Book Example 4.58).
The augmented grammar
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 → c
This grammar generates four valid strings: a c d, b c d, a c e, and b c e.
The non-terminals A and B both derive the single terminal c. Notice the context:
- After
a, if the trailing token isd,cmust reduce toA(rule 1). - After
a, if the trailing token ise,cmust reduce toB(rule 3). - After
b, if the trailing token isd,cmust reduce toB(rule 2). - After
b, if the trailing token ise,cmust reduce toA(rule 4).
Prerequisite FIRST and FOLLOW sets
FIRST(S) = { a, b },FIRST(A) = { c },FIRST(B) = { c }FOLLOW(S) = { end },FOLLOW(A) = { d, e },FOLLOW(B) = { d, e }
Because FOLLOW(A) and FOLLOW(B) both contain d and e, an SLR(1) parser fails immediately with reduce/reduce conflicts on both d and e.
Canonical LR(1) item sets (14 states)
The site's compiler library builds 14 canonical LR(1) states:
State 0 (Start state)
[S' → • S, end]
[S → • a A d, end]
[S → • b B d, end]
[S → • a B e, end]
[S → • b A e, end]
Transitions: S → I1, a → I2, b → I3.
State 1
[S' → S •, end]
Transitions: none (Accept on end).
State 2 (After shifting a)
[S → a • A d, end]
[S → a • B e, end]
[A → • c, d]
[B → • c, e]
Transitions: A → I4, B → I5, c → I6.
Notice the closure lookaheads: FIRST(d end) = { d } for A, and FIRST(e end) = { e } for B.
State 3 (After shifting b)
[S → b • B d, end]
[S → b • A e, end]
[B → • c, d]
[A → • c, e]
Transitions: B → I7, A → I8, c → I9.
Here FIRST(d end) = { d } belongs to B, and FIRST(e end) = { e } belongs to A.
State 4
[S → a A • d, end]
Transitions: d → I10.
State 5
[S → a B • e, end]
Transitions: e → I11.
State 6 (Reached from State 2 on c)
[A → c •, d]
[B → c •, e]
Transitions: none.
Key observation: In State 6, reduction by A → c (r5) occurs only on lookahead d. Reduction by B → c (r6) occurs only on lookahead e. Because { d } ∩ { e } = ∅, there is zero conflict in State 6!
State 7
[S → b B • d, end]
Transitions: d → I12.
State 8
[S → b A • e, end]
Transitions: e → I13.
State 9 (Reached from State 3 on c)
[B → c •, d]
[A → c •, e]
Transitions: none.
Key observation: In State 9, reduction by B → c (r6) occurs only on lookahead d. Reduction by A → c (r5) occurs only on lookahead e. Because { d } ∩ { e } = ∅, there is zero conflict in State 9!
States 10 through 13
I10: [S → a A d •, end] (reduce r1 on end)
I11: [S → a B e •, end] (reduce r3 on end)
I12: [S → b B d •, end] (reduce r2 on end)
I13: [S → b A e •, end] (reduce r4 on end)
Transitions: none.
Canonical LR(1) parsing table
In the table below, s denotes shift, r denotes reduce by rule number, and acc denotes accept.
| State | a | b | c | d | e | end | S | A | B |
|---|---|---|---|---|---|---|---|---|---|
| 0 | s2 | s3 | — | — | — | — | 1 | — | — |
| 1 | — | — | — | — | — | acc | — | — | — |
| 2 | — | — | s6 | — | — | — | — | 4 | 5 |
| 3 | — | — | s9 | — | — | — | — | 8 | 7 |
| 4 | — | — | — | s10 | — | — | — | — | — |
| 5 | — | — | — | — | s11 | — | — | — | — |
| 6 | — | — | — | r5 | r6 | — | — | — | — |
| 7 | — | — | — | s12 | — | — | — | — | — |
| 8 | — | — | — | — | s13 | — | — | — | — |
| 9 | — | — | — | r6 | r5 | — | — | — | — |
| 10 | — | — | — | — | — | r1 | — | — | — |
| 11 | — | — | — | — | — | r3 | — | — | — |
| 12 | — | — | — | — | — | r2 | — | — | — |
| 13 | — | — | — | — | — | r4 | — | — | — |
The canonical table has 0 conflict cells. The grammar is definitively canonical LR(1).
Parse traces in canonical LR(1)
Here are the library's step-by-step parse traces on valid inputs:
Parsing a c d
| Stack | Remaining input | Action |
|---|---|---|
| 0 | a c d end | Shift a, go to state 2 |
| 0 a 2 | c d end | Shift c, go to state 6 |
| 0 a 2 c 6 | d end | Reduce by A → c (r5) |
| 0 a 2 A 4 | d end | Shift d, go to state 10 |
| 0 a 2 A 4 d 10 | end | Reduce by S → a A d (r1) |
| 0 S 1 | end | Accept |
Parsing b c d
| Stack | Remaining input | Action |
|---|---|---|
| 0 | b c d end | Shift b, go to state 3 |
| 0 b 3 | c d end | Shift c, go to state 9 |
| 0 b 3 c 9 | d end | Reduce by B → c (r6) |
| 0 b 3 B 7 | d end | Shift d, go to state 12 |
| 0 b 3 B 7 d 12 | end | Reduce by S → b B d (r2) |
| 0 S 1 | end | Accept |
Notice how State 6 correctly reduced c to A when followed by d, while State 9 correctly reduced c to B when followed by d. The two states remembered their left-hand context (a versus b).
Merging into LALR(1): the reduce/reduce conflict
Now inspect the cores of all 14 canonical states.
Only one pair of states shares an identical LR(0) core: State 6 and State 9. Both have the core:
A → c •
B → c •
All other twelve states have unique cores and map directly to LALR states 0–5 and 7–12.
When LALR(1) merges State 6 and State 9 into a single merged State 6, it takes the union of their lookahead sets:
A → c •lookaheads:{ d } ∪ { e } = { d, e }B → c •lookaheads:{ e } ∪ { d } = { d, e }
The merged item set for State 6 becomes:
[A → c •, d/e]
[B → c •, d/e]
The resulting LALR(1) table
| State | a | b | c | d | e | end | S | A | B |
|---|---|---|---|---|---|---|---|---|---|
| 0 | s2 | s3 | — | — | — | — | 1 | — | — |
| 1 | — | — | — | — | — | acc | — | — | — |
| 2 | — | — | s6 | — | — | — | — | 4 | 5 |
| 3 | — | — | s6 | — | — | — | — | 8 | 7 |
| 4 | — | — | — | s9 | — | — | — | — | — |
| 5 | — | — | — | — | s10 | — | — | — | — |
| 6 | — | — | — | r5 / r6 | r5 / r6 | — | — | — | — |
| 7 | — | — | — | s11 | — | — | — | — | — |
| 8 | — | — | — | — | s12 | — | — | — | — |
| 9 | — | — | — | — | — | r1 | — | — | — |
| 10 | — | — | — | — | — | r3 | — | — | — |
| 11 | — | — | — | — | — | r2 | — | — | — |
| 12 | — | — | — | — | — | r4 | — | — | — |
The LALR(1) table has 2 reduce/reduce conflict cells in State 6:
- On terminal
d: should the parser reduce byA → c(r5) orB → c(r6)? - On terminal
e: should the parser reduce byA → c(r5) orB → c(r6)?
By merging State 6 and State 9, the parser lost the memory of whether it previously shifted a or b. Without knowing the left context, it cannot determine whether c represents non-terminal A or non-terminal B.
Thus, the grammar is canonical LR(1), but not LALR(1).
Comparison: LR(0) vs SLR(1) vs LALR(1) vs Canonical LR(1)
| Feature | LR(0) | SLR(1) | LALR(1) | Canonical LR(1) |
|---|---|---|---|---|
| State count | N (baseline core states) | N (same as LR(0)) | N (same as LR(0)) | Much larger (often 5× to 20× N) |
| Lookahead attachment | None (reduces in all columns) | Global FOLLOW(A) |
Exact FIRST(β a) merged by core |
Exact FIRST(β a) kept distinct |
| Shift/reduce from merge? | No | No | Never | None |
| Reduce/reduce from merge? | No | No | Yes, possible on same core | None |
| Parsing power | Smallest | Moderate | High (practical industry standard) | Highest deterministic context-free |
| Industry adoption | Teaching only | Educational tools | Yacc, Bison, Menhir | Specialized parsers, IELR tools |
How to explore this in ToolSphere
You can verify these exact calculations directly in your browser:
- Open the LR parser.
- Click the preset dropdown and select LR(1) but not LALR(1).
- Switch the table mode between CLR / LR(1) and LALR(1).
- Observe the conflict badge: CLR reports 0 conflicts and parses
a c dcleanly, while LALR(1) highlights the two reduce/reduce conflicts in State 6. - Use the LL(1) parser to see why top-down predictive parsers also fail on this grammar due to common prefixes.
Frequently asked questions
Can LALR(1) state merging ever create a shift/reduce conflict?
No. Merging states with identical cores can never introduce a shift/reduce conflict that did not already exist in the canonical LR(1) automaton. Because shift actions depend solely on core items of the form A → α • a β, any state in the merge group that contains a reduction on a and shares that core already contained the shift action on a prior to the merge.
Why does state merging only introduce reduce/reduce conflicts?
Reduce actions depend on the lookahead component of an LR(1) item. When two states with the same core are merged, their lookahead sets are unioned. If two different productions derive the same right-hand side, unioning their lookaheads can cause both productions to become valid reductions on the same lookahead token, producing a reduce/reduce conflict.
Does an LALR(1) parser ever accept an invalid string?
No. An LALR(1) parser accepts the exact same language as a canonical LR(1) parser. It will never shift an illegal token or accept an invalid string. However, due to merged lookahead sets, an LALR(1) parser may perform a few extra reductions before detecting a syntax error and halting.
Why did Yacc and Bison historically adopt LALR(1) instead of canonical LR(1)?
Table size and memory efficiency. In the 1970s when Yacc was developed, typical computers had tens of kilobytes of memory. A canonical LR(1) table for C would require thousands of states and megabytes of storage, whereas LALR(1) compressed the table to a few hundred states that easily fit into memory while parsing virtually all standard programming language constructs.
What is the difference between the core of an LR(1) state and the state itself?
The core is the set of productions and dot positions without their associated lookahead sets. Two states have the same core if they have the exact same dotted rules, even if their lookaheads are completely different.
How can I tell if an LALR conflict is caused by state merging or grammar ambiguity?
Build the canonical LR(1) table for the grammar. If the canonical LR(1) table has zero conflicts in that state, the conflict was caused purely by LALR state merging (the grammar is LR(1) but not LALR(1)). If the canonical LR(1) table also contains conflicts, the grammar is either ambiguous or requires more than 1 token of lookahead.
Can every SLR(1) grammar be parsed by LALR(1)?
Yes. The grammar classes form a strict hierarchy: every SLR(1) grammar is LALR(1), and every LALR(1) grammar is canonical LR(1). If a grammar can be parsed by SLR(1) with 0 conflicts, its LALR(1) and canonical LR(1) tables are guaranteed to be conflict-free as well.
How do modern compiler engineers resolve LALR(1) reduce/reduce conflicts?
Engineers typically refactor the grammar to distinguish the left contexts earlier, merge the non-terminals into a single rule and disambiguate during semantic analysis (type checking), or use modern parser generator modes like GNU Bison's IELR(1) (Minimal LR(1)), which selectively splits only the conflicting states while keeping the rest merged.
For a related walkthrough, read LALR and CLR Parsing Table Worked Example.