Chapter 9

CLR — Canonical LR(1) Parsing

The most powerful practical LR parser. Each item carries an exact lookahead, eliminating false conflicts that trouble SLR — at the cost of more states.

🔬 CLR — Canonical LR(1): The Full Solution
Problem SLR uses global FOLLOW sets — too imprecise, still has conflicts even on unambiguous grammars.
Fix Embed exact lookaheads inside each LR item: [A → α•β, a] means reduce only when next symbol is exactly a.
Cost Many more states than SLR — for large grammars, CLR can have 2–10× more states. This is called state explosion.
Fixed by LALR (next page) — merges compatible CLR states that share the same LR(0) core, recovering SLR's state count while keeping most of CLR's power.
Section 1

LR(1) Item Structure

An LR(1) item has three components: a production, a dot position, and a lookahead terminal.

Format: [Production, Dot, Lookahead]
[S → L •=R, $]
Production: S → L=R  |  Dot after L (position 1)  |  Lookahead: $ (reduce only when next is $)
[C → •cC, c]
Production: C → cC
Dot position: 0 (before c)
Lookahead: c
When C→cC completes, next symbol will be 'c'
[C → •cC, $]
Production: C → cC
Dot position: 0 (before c)
Lookahead: $
Same production, but next will be '$' when complete
Key Insight: Two items with the same production and dot position but different lookaheads are different LR(1) items. This is why CLR has more states than LR(0)/SLR — it distinguishes these situations, allowing precise reduce decisions and eliminating false conflicts.
Grammar We'll Use: The classic SLR conflict grammar: S' → S  |  S → L=R  |  S → R  |  L → *R  |  L → id  |  R → L This grammar has a genuine SLR conflict in state I2 (both shift on '=' and reduce R→L). CLR resolves it by tracking that the lookahead for R→L is only {$}, not {=, $}.
Section 2

LR(1) Closure with Lookahead Propagation

The closure rule for LR(1) extends an item set by propagating exact lookaheads through the grammar rules — this is the critical difference from LR(0) closure.

LR(1) Closure Rule
If [A → α•Bβ, a] is in the set, and B → γ is a production,
then add [B → •γ, b] for each b ∈ FIRST(βa)
The lookahead 'b' = FIRST(β followed by a) — this binds the future context to the current item's context. When β is empty, FIRST(βa) = {a}, so the lookahead propagates directly.

Interactive: Computing I0 Closure Step by Step

Starting from: [S' → •S, $] — press Next to follow each closure step.

Step 1 / 6

Final I0 — Complete Item Set

I0 (8 items — includes both '=' and '$' lookaheads for L)
Section 3

LR(1) Goto and The Key Insight

Computing Goto(I0, L) reveals why CLR resolves the SLR conflict: the lookahead {$} on R→L• excludes '='.

Goto(I0, L) — Construction

Collect items with dot before L, advance dot:
[S→•L=R, $]  →  [S→L•=R, $]
[R→•L, $]  →  [R→L•, $]
Close result: dot before '=' (terminal) → no new items.
Dot at end in R→L• → reduce item (lookahead = $).

I2 (CLR) — Result

I2 — CLR State
[S → L•=R, $]
[R → L•, $] ← reduce only on $
🔑 The Key Insight: Why CLR Beats SLR Here
⚠ SLR — I2 (CONFLICT)
S → L•=R
R → L•
FOLLOW(R) = {=, $} ← both included!
On token '=':
• Shift → go to next state (for S→L=R)
• Reduce → R→L (because = ∈ FOLLOW(R))
SHIFT/REDUCE CONFLICT ✗
✓ CLR — I2 (NO CONFLICT)
[S → L•=R, $]
[R → L•, $]
Lookahead of R→L• = {$} ← exact, not FOLLOW!
On token '=':
• Only Shift (for S→L=R) — no conflict
On token '$': Only Reduce R→L
FULLY RESOLVED ✓
Section 4

Full LR(1) Canonical Collection

All states computed by the engine. Click any state card to expand its items and transitions.

Computing states…
Section 5

LR(1) Automaton — Interactive DFA

Nodes represent LR(1) states; edges are labeled by grammar symbols. Hover a node to see its items.

Loading DFA visualization…
Section 6

CLR Parse Table

Built from the LR(1) collection. Each reduce entry uses the item's exact lookahead rather than the full FOLLOW set — this prevents false conflicts.

Shift (s#) Reduce (r#) Goto (#) Accept Conflict
Productions (for reduce entries):
Building CLR table…
Section 7

Parsing Simulation

Simulating input id = id $ with the CLR table. Derivation: S → L=R → id=R → id=L → id=id

Input tokens: id  =  id  $
Stack (state) Remaining Input Action Note
Section 8

CLR Advantages and Costs

Understanding when to use CLR versus SLR or LALR.

✓ Advantages of CLR

  • Most powerful practical LR family member
  • Almost no conflicts on non-ambiguous grammars
  • Exact lookaheads prevent false conflicts that SLR has
  • Resolves all grammars that LALR resolves (+ more)
  • Mathematical ideal: if a grammar is LR(1), CLR handles it

✗ Costs of CLR

  • State explosion: many more states than SLR
  • Larger memory footprint for parse tables
  • Parser generator time is longer
  • Rarely used alone — usually LALR is preferred
  • State count can be 2–10× more for large grammars
State Count Comparison (this grammar):
Historical note: CLR was described by Donald Knuth in 1965 and proved that every deterministic context-free language can be recognized by an LR(k) parser. However, the state explosion problem led DeRemer (1969) to develop the practical LALR approach, which is what yacc, bison, and most real parser generators use today.