ToolSphere
Back to all articles
student

LALR and CLR Parsing Table Worked Example

2026-11-0212 min read

Try it: free LR Parser (LR(0), SLR, LALR, CLR)

Build LR parsing tables and trace shifts and reductions

Open →

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.

Looking for other tools?

Explore ToolSphere Homepage →