Canonical LR(1), also called CLR, keeps a lookahead with each item. LALR(1) merges canonical states that have the same LR(0) core, taking the union of their item lookaheads. The merge can save states, but it must be checked for conflicts rather than assumed valid.
Every item set, action, state number and parse trace below comes from the site's compiler library. Enter the grammar in the LR parser to explore it. State numbers depend on traversal order; compare item contents when your textbook uses different numbers. We write end for the parser's end-of-input marker, not an extra grammar terminal.
Start with the augmented grammar
0. S' → S
1. S → C C
2. C → c C
3. C → d
The two C symbols must each derive a sequence ending in d. An LR(1) item records a production, dot position and the tokens on which that completed production may reduce. For closure of A → α • B β with lookahead a, use FIRST(βa) for B's added items. This is more precise than attaching the entire FOLLOW(B) set everywhere.
Use the FIRST and FOLLOW calculator to check the prerequisite sets. FIRST is used while building LR(1) closure; FOLLOW is the broader context used by SLR reductions.
Canonical LR(1) item sets
The library builds 10 states. A slash separates lookaheads belonging to the same production and dot position.
I0
[S' → • S, end]
[S → • C C, end]
[C → • c C, c/d]
[C → • d, c/d]
Transitions: S → I1, C → I2, c → I3, d → I4.
I1
[S' → S •, end]
Transitions: none.
I2
[S → C • C, end]
[C → • c C, end]
[C → • d, end]
Transitions: C → I5, c → I6, d → I7.
I3
[C → c • C, c/d]
[C → • c C, c/d]
[C → • d, c/d]
Transitions: C → I8, c → I3, d → I4.
I4
[C → d •, c/d]
Transitions: none.
I5
[S → C C •, end]
Transitions: none.
I6
[C → c • C, end]
[C → • c C, end]
[C → • d, end]
Transitions: C → I9, c → I6, d → I7.
I7
[C → d •, end]
Transitions: none.
I8
[C → c C •, c/d]
Transitions: none.
I9
[C → c C •, end]
Transitions: none.
Canonical ACTION and GOTO table
s followed by a state means shift. r followed by a production number means reduce using the numbered augmented grammar above. acc means accept; a dash means no action or transition. The S and C columns are GOTO entries, while the terminal and end columns are ACTION entries.
| State | c | d | end | S | C |
|---|---|---|---|---|---|
| 0 | s3 | s4 | — | 1 | 2 |
| 1 | — | — | acc | — | — |
| 2 | s6 | s7 | — | — | 5 |
| 3 | s3 | s4 | — | — | 8 |
| 4 | r3 | r3 | — | — | — |
| 5 | — | — | r1 | — | — |
| 6 | s6 | s7 | — | — | 9 |
| 7 | — | — | r3 | — | — |
| 8 | r2 | r2 | — | — | — |
| 9 | — | — | r2 | — | — |
There are 0 conflict cells. This result is about this grammar and construction, not a claim that every context-free grammar has a conflict-free canonical table.
Merge equal cores to form LALR(1)
Strip away lookaheads when comparing cores. Merge only states with identical sets of production/dot pairs; sharing one completed production is not enough. Union the corresponding lookaheads and redirect transitions to the merged states.
| LALR state | Canonical members |
|---|---|
| 0 | I0 |
| 1 | I1 |
| 2 | I2 |
| 3 | I3, I6 |
| 4 | I4, I7 |
| 5 | I5 |
| 6 | I8, I9 |
The resulting collection has 7 states. Compare the merged item sets with their canonical members:
I0
[S' → • S, end]
[S → • C C, end]
[C → • c C, c/d]
[C → • d, c/d]
Transitions: S → I1, C → I2, c → I3, d → I4.
I1
[S' → S •, end]
Transitions: none.
I2
[S → C • C, end]
[C → • c C, end]
[C → • d, end]
Transitions: C → I5, c → I3, d → I4.
I3
[C → c • C, end/c/d]
[C → • c C, end/c/d]
[C → • d, end/c/d]
Transitions: C → I6, c → I3, d → I4.
I4
[C → d •, end/c/d]
Transitions: none.
I5
[S → C C •, end]
Transitions: none.
I6
[C → c C •, end/c/d]
Transitions: none.
LALR ACTION and GOTO table
| State | c | d | end | S | C |
|---|---|---|---|---|---|
| 0 | s3 | s4 | — | 1 | 2 |
| 1 | — | — | acc | — | — |
| 2 | s3 | s4 | — | — | 5 |
| 3 | s3 | s4 | — | — | 6 |
| 4 | r3 | r3 | r3 | — | — |
| 5 | — | — | r1 | — | — |
| 6 | r2 | r2 | r2 | — | — |
The merged table has 0 conflict cells. These smaller states preserve the needed distinctions for this grammar. In general, merging a conflict-free canonical collection can introduce reduce/reduce conflicts, so LALR(1) and canonical LR(1) are not interchangeable grammar classes.
Parse cdd with the merged table
The following is the library's actual parse trace, including its stack and remaining input. Each reduction pops the production's right-hand side and follows GOTO on its left-hand side; reducing does not consume the next input token.
| Stack | Remaining input | Action |
|---|---|---|
| 0 | c d d end | Shift c, go to state 3 |
| 0 c 3 | d d end | Shift d, go to state 4 |
| 0 c 3 d 4 | d end | Reduce by C → d (r3) |
| 0 c 3 C 6 | d end | Reduce by C → c C (r2) |
| 0 C 2 | d end | Shift d, go to state 4 |
| 0 C 2 d 4 | end | Reduce by C → d (r3) |
| 0 C 2 C 5 | end | Reduce by S → C C (r1) |
| 0 S 1 | end | Accept |
The result is accepted. Read the trace against the numbered productions and LALR table rather than matching an arbitrary sequence of state numbers from another implementation.
A grammar that is LALR(1) but not SLR(1)
S -> L = R | R
L -> * R | id
R -> L
Its computed FOLLOW sets are:
| Nonterminal | FOLLOW |
|---|---|
| S | end |
| L | end, = |
| R | end, = |
The SLR table has 1 conflict cell. In state I2, on terminal =, the construction tries these actions:
s6: shift, because of S → L • = R
r5: reduce by R → L, because R → L • is complete and = ∈ FOLLOW(R)
SLR allows the completed R → L item to reduce on every member of FOLLOW(R), including equals. But the state also has an item that must shift equals to continue an assignment. This is a shift/reduce conflict caused by the overly broad reduction lookahead, not proof that the grammar is ambiguous.
In the corresponding LALR state, the completed R → L item has only end as its lookahead:
[S → L • = R, end]
[R → L •, end]
The shift on equals and reduction on end occupy different cells. The computed LALR and canonical tables each have 0 conflict cells for this grammar.
Parse id=id
| Stack | Remaining input | Action |
|---|---|---|
| 0 | id = id end | Shift id, go to state 5 |
| 0 id 5 | = id end | Reduce by L → id (r4) |
| 0 L 2 | = id end | Shift =, go to state 6 |
| 0 L 2 = 6 | id end | Shift id, go to state 5 |
| 0 L 2 = 6 id 5 | end | Reduce by L → id (r4) |
| 0 L 2 = 6 L 8 | end | Reduce by R → L (r5) |
| 0 L 2 = 6 R 9 | end | Reduce by S → L = R (r1) |
| 0 S 1 | end | Accept |
The LALR parser accepts the assignment. Here id is a single terminal token, not two letters to parse separately.
Checks that catch common exam errors
- Augment and number productions before assigning reduce actions. Otherwise a correct item set can still produce a wrongly numbered table.
- Use FIRST of the suffix plus inherited lookahead in canonical closure. Do not replace it with FOLLOW just because FOLLOW was used in an earlier SLR exercise.
- Compare complete LR(0) cores before merging; combine lookaheads of matching items, not dots at different positions.
- Rebuild transition targets after merging and inspect every ACTION cell for multiple actions.
- Keep acceptance separate from reduction by an ordinary production. Acceptance requires the completed augmented start item and end marker.
For the LR(0)/SLR baseline, continue with the SLR worked example. For predictive parsing, compare the FIRST and FOLLOW example. Neither a smaller table nor a successful sample parse alone proves that all inputs have been classified correctly: the conflict check and construction rules matter.