CLR

CLR(1) stands for Canonical LR with 1 token of lookahead. It is the most powerful parser in the LR family — every deterministic context-free grammar that can be parsed with one lookahead token can be parsed by a CLR(1) parser.

The price is table size: CLR(1) often produces 5–10× more states than SLR(1) or LALR(1) for the same grammar. For decades that was too expensive on real hardware, so LALR(1) became the practical default. But CLR(1) is the theoretical maximum — and the right starting point for understanding LALR(1) too.

The Core Idea — Lookaheads on Items

In LR(0)/SLR, every item is of the form A → α · β. CLR adds a lookahead to each item:

Read it as: "we have parsed α, expect β next, and after reducing this production we expect to see terminal a." That terminal a is what makes the item LR(1).

A complete item [A → α · , a] triggers reduce A → α only when the next input token is exactly a — never on any other terminal.

Why This Beats SLR

SLR's FOLLOW set is computed globally over the grammar — it lumps together every context where a non-terminal might appear. A particular state of the parser usually doesn't allow all of FOLLOW(A) to follow — only a context-dependent subset.

CLR avoids the overshoot by storing exact lookaheads inside each item. Two parser states that contain the same LR(0) item but with different lookaheads become different CLR states. That fine granularity is precisely what resolves grammars like S → L = R that SLR cannot handle.

The Construction Pipeline

Same overall shape as SLR — only the items, the CLOSURE, and the reduce rule change.

Before building the table we need three definitions: the item format, CLOSURE for LR(1), and GOTO for LR(1).

LR(1) Item Format

When we write [A → α · β, a/b] (with a slash) it is shorthand for two items, one with lookahead a and one with lookahead b.

CLOSURE for LR(1)

If a state already contains [A → α · B β , a] (dot before a non-terminal B), then somewhere "soon" the parser will start matching a B production. So for every production B → γ we must add:

FIRST(β a) is the set of terminals that can appear right after the new B. If β can derive ε, the inherited a is included.

Keep applying the rule until no new items are added — that is the closure.

Worked CLOSURE Example

Grammar fragment: A → · B C , $, productions B → b and B → c, with C deriving a non-ε string.

The lookahead chains — the things that follow the new non-terminal become the lookaheads of the items added by closure.

GOTO for LR(1)

GOTO works the same way as in LR(0), but lookaheads are carried along:

In words: take every item in I whose dot precedes X, shift the dot one position past X, keep the same lookahead, then close the result.

Why More States?

Because two parser states with the same LR(0) items but different lookaheads are now considered different. CLR splits states that LR(0) would have merged — that is exactly where the extra precision comes from, and also where the extra states come from.

We use the same grammar as the SLR topic so the two table constructions can be compared side by side.

For SLR, this grammar produced 7 states. For CLR, we will see it explode to 10 states — three more than SLR — because the lookaheads split some states apart.

(For the L = R grammar where SLR fails outright, CLR succeeds — but the example above is small enough to write the entire DFA on one page.)

Start from the kernel of the augmented start production and apply closure repeatedly.

State I₀

Kernel:

Closure (dot before S, so add S productions with lookahead = FIRST($) = {$}):

Closure again (dot before C, lookahead = FIRST(C $) = FIRST(C) = {c, d}):

So I₀ is:

Transitions out of I₀

Notice already: states I₂ and I₃ share the same LR(0) core (C → · c C, C → · d) but different lookaheads ($ vs c/d). CLR keeps them separate. LALR will eventually merge them — but that is the next topic.

Transitions out of I₂

I₆ and I₃ share their LR(0) core but differ in lookaheads ($ vs c/d) — another future merge.

Transitions out of I₃

Transitions out of I₆

I₄/I₇ share an LR(0) core, and I₈/I₉ share an LR(0) core — three pairs total that LALR will eventually merge.

Summary — All 10 States

Visual Diagram of the DFA

Each box is a state with its LR(1) items inside — the lookahead follows the comma. Arrows are transitions labelled by the symbol that triggers them.

How to read it:

• Blue — the start state (I₀).
• Cyan — the accept state (I₁, on lookahead $).
• Amber — reduce states (I₄, I₅, I₇, I₈, I₉).
• Arrow labels — the grammar symbol that triggers the transition.

Notice the lookahead-driven splits: I₂/I₃ and I₆/I₃ share the LR(0) core {C → ·cC, C → ·d} but differ only in lookahead ($ vs c/d); likewise I₄/I₇ and I₈/I₉. Those splits are exactly why CLR has 10 states where SLR had 7 — and exactly the states LALR will merge back in the next topic.

With the DFA built, the table follows the standard LR recipe — but the reduce rule uses the lookahead carried in each item.

Shift and GOTO Entries

Identical to SLR — read straight off the DFA transitions.

Accept Entry

Reduce Entries — The CLR(1) Rule

That's it — one cell per item, not one cell per terminal in FOLLOW. Going through our reduce states:

Each reduction fires on a specific subset of terminals — never the full FOLLOW set.

The Complete CLR(1) Parse Table

Every cell has at most one entry — the grammar is CLR(1).

Compare With SLR

Both parsers accept the same language for this grammar, but CLR distinguishes contexts that SLR collapses together. That extra precision is exactly what saves grammars like S → L = R from rejection.

Same input as the SLR trace — input c d d — but using the CLR(1) table.

The parser took the same sequence of shifts and reduces as the SLR trace, but went through different intermediate states (3 ➝ 8 ➝ 2 ➝ 7) instead of (3 ➝ 6 ➝ 2 ➝ 4). The CLR DFA encodes more information per state — and that is the entire trade-off.

CLR(1) is the gold standard of deterministic parsing — at a price.

Advantages

Cost

When to Reach for CLR(1)

In practice, almost never — LALR(1) does the same job with a fraction of the table size. CLR's role is mostly:

1. A teaching tool to introduce lookahead-bearing items.
2. A theoretical reference when proving things about LR languages.
3. A starting point for LALR(1) — every LALR(1) table can be derived by merging CLR(1) states.

If you understand CLR, LALR is one merge step away — which is exactly the topic of the next lesson.