Canonical LR(1) (CLR) items with lookaheads

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• In SLR, on which tokens does A → α• reduce? from Lesson 2.4.3
• Which actions can a shift-reduce parser take? from Lesson 2.4.1
• Is an ambiguous grammar ever LL(1) or LR(k)? from Lesson 2.1.2

1 · The Story

📖

A note on every card

The L = R rulebook keeps tripping Kabir’s follower lists. His fix: each progress card carries a small note, “I may fold only if the next word is …”. The note is not the category’s whole follower list. It is written when the card is laid out, from what actually comes after it on this path.

When Kabir lays out fresh cards for a category B because some card waits for “B then x”, the new cards get the note: whatever can start “x” on the waiting card, or, if x can be empty, the waiting card’s own note.

The wall of bundles grows bigger, because two bundles with the same cards but different notes are now different states. But no false alarms remain.

2 · Predict First

🤔

For S → C C, C → c C | d, the LR(0) collection has 7 states. Will the collection of cards-with-notes have more, fewer or the same? Write your guess down. The answer is in the vault.

3 · Core Concept

LR(1) items

An LR(1) item is [A → α•β, a]: an LR(0) item plus one lookahead terminal a (or $). The lookahead matters only when the dot reaches the end: [A → α•, a] means “reduce A → α if the next token is a”. Items with the same core and different lookaheads are often written together: [A → α•β, a/b].

CLOSURE and GOTO with lookaheads

CLOSURE(I): for each [A → α•Bβ, a] in I, each production B → γ, and each terminal b ∈ FIRST(βa), add [B → •γ, b]. Repeat until nothing new.

GOTO(I, X): advance the dot over X in every item that expects X, keeping each item’s lookahead; then take CLOSURE.

Start state: CLOSURE({[S′ → •S, $]}).

The canonical LR(1) table

• [A → α•aβ, b] ∈ Iᵢ, GOTO(Iᵢ, a) = Iⱼ: shift j on a;
• [A → α•, a] ∈ Iᵢ (A ≠ S′): reduce A → α on a only;
• [S′ → S•, $]: accept on $;
• GOTO for nonterminals as before.

A grammar is LR(1) (canonical LR, CLR) if this table has no multiple entries. CLR is the most powerful of the LR(1)-lookahead methods, but its tables can be much larger than LR(0)/SLR tables.

Story → compiler term

4 · Visual

(0) S' → S
(1) S → C C
(2) C → c C
(3) C → d

Canonical LR(1) collection of S → C C, C → c C | d: 10 states. States with the same items but different lookaheads (for example the two “C → d•” states) are kept apart.

5 · Worked Examples

Example 1 Easy

Compute I₀ of the canonical LR(1) collection for S → C C, C → c C | d.

Solution

Start with [S′ → •S, $]. The dot is before S with nothing after it: add [S → •CC, $]. The dot is before C, followed by C, so the lookaheads are FIRST(C$) = { c, d }: add [C → •cC, c/d] and [C → •d, c/d]. The note on each C card says: the next word after this first C starts the second C.

Example 2 Medium

How many states does the canonical LR(1) collection of S → C C, C → c C | d have, and which pairs have the same core?

Solution

10 states (graph above). The pairs with the same LR(0) items but different lookaheads are the states reached on c, on d, and the C → cC• states, once with lookaheads c/d (inside the first C) and once with $ (inside the second C). Merging them is the next lesson.

Example 3 GATE

Show that S → L = R | R, L → * R | id, R → L is LR(1) though not SLR(1).

Solution

In the CLR collection, GOTO(I₀, L) = { [S → L•=R, $], [R → L•, $] }. The reduce R → L is on $ only, and the shift is on =: no conflict. The note on the R card says $, because this R would be a whole statement. The full CLR table has 14 states and no conflicts (computed).

6 · Shortcuts

⚡

Lookahead for new items: from [A → α•Bβ, a], new B-items get FIRST(β) − ε, plus a itself if β is nullable or empty. Valid when: every CLOSURE step in LR(1).

⚡

CLR conflict check: in a state, a complete item’s lookahead must not equal any terminal after a dot (S/R), nor any other complete item’s lookahead (R/R). Valid when: deciding LR(1) once the collection is built.

7 · GATE Traps

⚠️

• Lookaheads are computed from FIRST(βa), not from FOLLOW.
• The lookahead does not change when GOTO moves the dot.
• Same core with different lookaheads means different CLR states.
• CLR tables can be much larger than SLR tables (10 vs 7 here; often hundreds more in real languages).
• An LR(1) grammar can still be ambiguous? No: every LR(1) grammar is unambiguous.

8 · Memory Hook

🧠

LR(1) item = LR(0) item + a note saying who may come next. The note is born in CLOSURE from FIRST(β a).

9 · Connect the Dots

Canonical LR(1) is precise but big. The next lesson merges states that differ only in their notes, getting an automaton as small as LR(0) but almost as precise as CLR.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksStates

How many states does the canonical LR(1) collection of S → C C, C → c C | d have?

Numerical answer: ________

Q2MCQ1 markLookahead

From the item [A → α•Bβ, a], CLOSURE adds items [B → •γ, b] for b in:

• (A) FOLLOW(B)
• (B) FIRST(β a)
• (C) FIRST(B)
• (D) FOLLOW(A)

Q3MCQ1 markReduce

In a CLR table, [A → α•, a] in state i gives:

• (A) reduce on all terminals
• (B) reduce on FOLLOW(A)
• (C) reduce on a only
• (D) shift on a

Q4NAT2 marksStates

How many states does the canonical LR(1) collection of S → L = R | R, L → * R | id, R → L have?

Numerical answer: ________

Q5MSQ2 marksFacts

Which are true?

• (A) Every SLR(1) grammar is LR(1).
• (B) The CLR collection never has fewer states than the LR(0) collection.
• (C) Every LR(1) grammar is unambiguous.
• (D) CLR uses FOLLOW sets to place reductions.

11 · Rule Card

• LR(1) item [A → α•β, a].
• CLOSURE: [A → α•Bβ, a] ⇒ [B → •γ, b] for b ∈ FIRST(βa).
• GOTO keeps lookaheads.
• Reduce [A → α•, a] only on a; accept [S′ → S•, $].
• CLR (canonical LR(1)) ⊇ SLR; states ≥ LR(0) states; S → CC: 10 vs 7.

12 · Concept Ledger

LR(1) itemlookahead (of an item)canonical LR(1) collectionCLR parsing tableLR(1) grammar

13 · Answer Vault