At the end of SLR Parsing we met a grammar that is perfectly unambiguous, yet the SLR table has a conflict. The problem was FOLLOW: it lists every token that can follow a nonterminal anywhere, while in a particular state only some of those tokens are really possible.
The canonical LR(1) parser, usually called CLR(1) or simply LR(1), fixes this at the root. Instead of looking up a global FOLLOW set when it is time to reduce, it carries the exact lookahead along inside every item, from the moment the item is created. This is the most powerful of the LR methods with one token of lookahead. The theory comes from Donald Knuth's 1965 paper that introduced LR(k) parsing.
An LR(1) item is a pair [A → α • β, a], where A → α • β is an LR(0) item and a is a terminal or $ called the lookahead. The CLR(1) parser reduces by A → α in a state containing [A → α •, a] only when the next input token is a.
All item sets, tables and traces below were generated by a Python LR(1) builder and cross-checked by hand.
What the Lookahead Means
Read [A → α • β, a] as: "we are in the middle of recognising A; we have seen α, we expect β next, and once this whole A is finished, the token after it will be a."
While β is not empty, the lookahead plays no role. Shifts are decided by the symbol after the dot, exactly as in LR(0).
When β is empty, i.e. the item is [A → α •, a], the lookahead decides when to reduce: only on a.
The lookahead of an item is always a subset of FOLLOW(A), and often a much smaller one. That is where the extra power comes from.
Items with the same LR(0) part are usually written together: [C → c • C, c / d] is shorthand for the two items [C → c • C, c] and [C → c • C, d]. The LR(0) part of an item is called its core.
CLOSURE and GOTO for LR(1) Items
CLOSURE
CLOSURE(I):
repeat
for each item [A → α • B β, a] in I (B is a nonterminal)
for each production B → γ
for each terminal b in FIRST(β a)
add [B → • γ, b] to I
until nothing new is addedWhy FIRST(β a)? We are about to start recognising a B. What comes right after this B? Whatever β begins with. If β can vanish (β ⇒* ε), or is empty, then what follows B is whatever follows A, which is a. FIRST(β a) captures both cases in one expression. Since a is a single terminal, FIRST(β a) never contains ε.
Small check: for S → A B, A → a | ε, B → b, the closure of [S' → • S, $] is:
S' → • S, $
S → • A B, $
A → • a, b FIRST(B $) = { b }
A → •, bGOTO
GOTO(I, X) = CLOSURE( { [A → α X • β, a] : [A → α • X β, a] is in I } )Moving the dot never changes the lookahead. Lookaheads are created only by CLOSURE.
The canonical collection
Start with I0 = CLOSURE({[S' → • S, $]}) and keep applying GOTO on every grammar symbol until no new item set appears, exactly as for LR(0). Two item sets are the same state only if they have the same items including lookaheads.
Building the CLR(1) Parsing Table
For each state Ii:
1. If [A → α • a β, b] is in Ii (a a terminal) and GOTO(Ii, a) = Ij:
ACTION[i, a] = shift j
2. If [A → α •, a] is in Ii and A ≠ S':
ACTION[i, a] = reduce A → α (only under its own lookahead a)
3. If [S' → S •, $] is in Ii:
ACTION[i, $] = accept
4. If GOTO(Ii, A) = Ij for a nonterminal A:
GOTO[i, A] = j
5. All other entries are errors.
If any cell has two entries, the grammar is not LR(1).The only difference from SLR is rule 2: the reduce goes under the item's own lookahead instead of under all of FOLLOW(A).
Worked Example 1: S → C C
This small grammar describes strings cm d cn d (m, n ≥ 0): two blocks, each made of some c's followed by a d.
(0) S' → S
(1) S → C C
(2) C → c C
(3) C → dFIRST(S) = { c, d }
FIRST(C) = { c, d }Computing I0 step by step
Start: [S' → • S, $].
The dot is before S, followed by nothing, so the lookahead for S-items is FIRST($) = { $ }: add [S → • C C, $].
In that item the dot is before the first C, followed by C, then $. Lookahead for C-items is FIRST(C $) = FIRST(C) = { c, d }: add [C → • c C, c / d] and [C → • d, c / d].
The new items have terminals after the dot, so nothing more is added.
The full collection has 10 states:
I0:
S' → • S, $
S → • C C, $
C → • c C, c / d
C → • d, c / d
on S → I1 on C → I2 on c → I3 on d → I4
I1:
S' → S •, $
I2:
S → C • C, $
C → • c C, $
C → • d, $
on C → I5 on c → I6 on d → I7
I3:
C → c • C, c / d
C → • c C, c / d
C → • d, c / d
on C → I8 on c → I3 on d → I4
I4:
C → d •, c / d
I5:
S → C C •, $
I6:
C → c • C, $
C → • c C, $
C → • d, $
on C → I9 on c → I6 on d → I7
I7:
C → d •, $
I8:
C → c C •, c / d
I9:
C → c C •, $Look at I3 and I6. Both contain C → c • C, C → • c C and C → • d. Their cores are identical; only the lookaheads differ. I3 is used for the c's of the first block (after its C comes another C, so lookahead c / d), while I6 is used for the second block (after its C comes the end of input, so lookahead $). The pairs (I4, I7) and (I8, I9) are split the same way. The LR(0) automaton for this grammar has only 7 states; the extra three come purely from different lookaheads.
The CLR(1) table
State | c | d | $ | 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 |
Row 4 is a good one to check: I4 = [C → d •, c / d], so r3 appears under c and d but not under $. A d that ends the first block can't be the last token, because the second block must still follow.
Parsing c d c c d
Stack Input Action
0 c d c c d $ s3: shift c, go to 3
0 c 3 d c c d $ s4: shift d, go to 4
0 c 3 d 4 c c d $ r3: reduce C → d, goto[3, C] = 8
0 c 3 C 8 c c d $ r2: reduce C → c C, goto[0, C] = 2
0 C 2 c c d $ s6: shift c, go to 6
0 C 2 c 6 c d $ s6: shift c, go to 6
0 C 2 c 6 c 6 d $ s7: shift d, go to 7
0 C 2 c 6 c 6 d 7 $ r3: reduce C → d, goto[6, C] = 9
0 C 2 c 6 c 6 C 9 $ r2: reduce C → c C, goto[6, C] = 9
0 C 2 c 6 C 9 $ r2: reduce C → c C, goto[2, C] = 5
0 C 2 C 5 $ r1: reduce S → C C, goto[0, S] = 1
0 S 1 $ acceptThe first block c d is handled by states 3, 4 and 8; the second block c c d by states 6, 7 and 9. The parser always knows which block it is in.
Early error detection
For the incomplete input c c d (only one block):
Stack Input Action
0 c c d $ s3: shift c, go to 3
0 c 3 c d $ s3: shift c, go to 3
0 c 3 c 3 d $ s4: shift d, go to 4
0 c 3 c 3 d 4 $ blank entry [4, $]: syntax errorThe error is caught the moment $ is seen in state 4, before any reduction. A canonical LR parser detects an error at the earliest possible point, without performing any reduction on the erroneous lookahead. As we will see in LALR Parsing, LALR and SLR parsers may first perform a few extra reductions before reporting the same error.
Worked Example 2: The Grammar SLR Could Not Handle
(0) S' → S
(1) S → L = R
(2) S → R
(3) L → * R
(4) L → id
(5) R → LLet's compute I0 carefully, because this is where the precise lookaheads are born.
[S' → • S, $] gives [S → • L = R, $] and [S → • R, $].
From [S → • L = R, $]: the dot is before L, followed by
= R. FIRST(= R $) = { = }. So add [L → • * R, =] and [L → • id, =].From [S → • R, $]: FIRST($) = { $ }, so add [R → • L, $].
From [R → • L, $]: L is followed by nothing, so lookahead $. Add [L → • * R, $] and [L → • id, $].
The full LR(1) collection has 14 states:
I0:
S' → • S, $
S → • L = R, $
S → • R, $
L → • * R, = / $
L → • id, = / $
R → • L, $
on S → I1 on L → I2 on R → I3 on * → I4 on id → I5
I1:
S' → S •, $
I2:
S → L • = R, $
R → L •, $
on = → I6
I3:
S → R •, $
I4:
L → * • R, = / $
R → • L, = / $
L → • * R, = / $
L → • id, = / $
on R → I7 on L → I8 on * → I4 on id → I5
I5:
L → id •, = / $
I6:
S → L = • R, $
R → • L, $
L → • * R, $
L → • id, $
on R → I9 on L → I10 on * → I11 on id → I12
I7:
L → * R •, = / $
I8:
R → L •, = / $
I9:
S → L = R •, $
I10:
R → L •, $
I11:
L → * • R, $
R → • L, $
L → • * R, $
L → • id, $
on R → I13 on L → I10 on * → I11 on id → I12
I12:
L → id •, $
I13:
L → * R •, $Now state I2, which caused the SLR conflict, is:
I2:
S → L • = R, $ → shift 6 on =
R → L •, $ → reduce R → L only on $The reduce sits only under $, the shift only under =. No conflict. The item R → L • could only have come from [R → • L, $] in I0, so the lookahead correctly records that this R would be the whole statement.
State | = | * | id | $ | S | L | R |
|---|---|---|---|---|---|---|---|
0 | s4 | s5 | 1 | 2 | 3 | ||
1 | acc | ||||||
2 | s6 | r5 | |||||
3 | r2 | ||||||
4 | s4 | s5 | 8 | 7 | |||
5 | r4 | r4 | |||||
6 | s11 | s12 | 10 | 9 | |||
7 | r3 | r3 | |||||
8 | r5 | r5 | |||||
9 | r1 | ||||||
10 | r5 | ||||||
11 | s11 | s12 | 10 | 13 | |||
12 | r4 | ||||||
13 | r3 |
Parsing * id = id:
Stack Input Action
0 * id = id $ s4: shift *, go to 4
0 * 4 id = id $ s5: shift id, go to 5
0 * 4 id 5 = id $ r4: reduce L → id, goto[4, L] = 8
0 * 4 L 8 = id $ r5: reduce R → L, goto[4, R] = 7
0 * 4 R 7 = id $ r3: reduce L → * R, goto[0, L] = 2
0 L 2 = id $ s6: shift =, go to 6
0 L 2 = 6 id $ s12: shift id, go to 12
0 L 2 = 6 id 12 $ r4: reduce L → id, goto[6, L] = 10
0 L 2 = 6 L 10 $ r5: reduce R → L, goto[6, R] = 9
0 L 2 = 6 R 9 $ r1: reduce S → L = R, goto[0, S] = 1
0 S 1 $ acceptNote the two different paths: the * and id on the left of = use states 4, 5, 7, 8 (lookahead = / $), while the id on the right uses states 12 and 10 (lookahead $ only). This grammar is LR(1) but not SLR(1).
Worked Example 3: A Reduce-Reduce Conflict Disappears
(0) S' → S
(1) S → A a A b
(2) S → B b B a
(3) A → ε
(4) B → εSLR gave a reduce-reduce conflict in I0 because FOLLOW(A) = FOLLOW(B) = { a, b }. With LR(1) items:
I0:
S' → • S, $
S → • A a A b, $
S → • B b B a, $
A → •, a
B → •, b
on S → I1 on A → I2 on B → I3[A → •, a] comes from S → • A a A b (A is followed by a), and [B → •, b] from S → • B b B a. So ACTION[0, a] = r3 and ACTION[0, b] = r4. One token of lookahead is enough to decide which empty string to "create". Parsing b a:
Stack Input Action
0 b a $ r4: reduce B → ε, goto[0, B] = 3
0 B 3 b a $ s5: shift b, go to 5
0 B 3 b 5 a $ r4: reduce B → ε, goto[5, B] = 7
0 B 3 b 5 B 7 a $ s9: shift a, go to 9
0 B 3 b 5 B 7 a 9 $ r2: reduce S → B b B a, goto[0, S] = 1
0 S 1 $ acceptHow Powerful Is CLR(1)?
Every SLR(1) grammar is LR(1). (The LR(1) lookaheads of an item are always a subset of FOLLOW, so they can only remove conflicts, never create them.)
Every LL(1) grammar is LR(1), but not necessarily SLR(1) (Worked Example 3 is LL(1)).
Every LR(1) grammar is unambiguous. An ambiguous grammar always gives a conflict.
The languages with an LR(1) grammar are exactly the deterministic context-free languages, the languages accepted by deterministic pushdown automata. Allowing k > 1 lookahead tokens does not add any new languages, only more grammars.
Grammar classes (each strictly contains the one before):
LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1) = CLR(1)LALR(1) sits between SLR and CLR. It is covered in the next chapter.
The Price: Many More States
Because states are split by lookahead, a CLR(1) parser can have many more states than an LR(0)/SLR parser for the same grammar:
Grammar | LR(0) / SLR / LALR states | CLR(1) states |
|---|---|---|
S → C C, C → c C | d | 7 | 10 |
S → L = R | R, L → * R | id, R → L | 10 | 14 |
S → a S b | a b | 6 | 10 |
E → E + T | T, T → T * F | F, F → ( E ) | id | 12 | 22 |
For a full programming language the gap is much bigger: the Dragon Book notes that a language like C needs a few hundred SLR/LALR states but several thousand canonical LR states. That memory cost is why practical tools such as Yacc and Bison use LALR(1) by default.
SLR(1) vs CLR(1)
Feature | SLR(1) | CLR(1) |
|---|---|---|
Items | LR(0) items | LR(1) items (core + lookahead) |
Reduce A → α placed under | All of FOLLOW(A) | Only the item's lookahead(s) |
Lookahead is | Global (same for every state) | Specific to each state and item |
Number of states | Smallest | Largest |
Grammars handled | Fewest | All LR(1) grammars |
Error detection | May do extra reductions first | Immediate (no reduction on an erroneous token) |
Common Mistakes
Using FOLLOW for lookaheads. Lookaheads come from FIRST(β a) during closure. If you write FOLLOW(B) you have built an SLR table with extra steps.
Forgetting the nullable case. If β ⇒* ε, the lookahead a of the parent item must also be included. FIRST(β a) handles this automatically; FIRST(β) alone does not.
Changing lookaheads in GOTO. Moving the dot keeps the lookahead. Only closure adds new lookaheads.
Treating I3 and I6 as the same state. In CLR, item sets with different lookaheads are different states. Merging them is LALR, not CLR.
Using the lookahead for shifts. The shift on a terminal x comes from an item with x after the dot, regardless of that item's lookahead.
Practice Questions
Q1. What does the lookahead in [A → α • β, a] tell the parser when β ≠ ε?
Nothing immediately. It is carried along through GOTO and only used when the dot reaches the end, where it decides the column of the reduce entry. It also helps compute lookaheads of new items during closure (through FIRST(β a)).
Q2. I contains [A → a • B c, $] and the productions are B → b B | ε. Write CLOSURE(I).
FIRST(c $) = { c }, so add [B → • b B, c] and [B → •, c]. The new items have b or nothing after the dot, so we stop: { [A → a • B c, $], [B → • b B, c], [B → •, c] }.
Q3. How many states do the LR(0) and CLR(1) automata of S → a S b | a b have?
6 LR(0) states and 10 LR(1) states. The states reached after an inner a (expecting b afterwards) and after the outermost a (expecting $ afterwards) get different lookaheads and split.
Q4. Is the grammar S → L = R | R, L → * R | id, R → L SLR(1)? CLR(1)?
Not SLR(1): a shift-reduce conflict on = in the state { S → L • = R, R → L • }, because = ∈ FOLLOW(R). It is CLR(1): in the LR(1) collection that state has [R → L •, $], so the reduce is only under $.
Q5. Can CLR(1) parse an ambiguous grammar without conflicts?
No. Every grammar whose LR(1) table has no conflicts is unambiguous. Ambiguous grammars are handled in practice by resolving the conflicts with precedence and associativity declarations, as Yacc/Bison do.
Q6. If the CLR(1) table for G has no conflict, does the SLR(1) table also have none?
Not necessarily. The L = R grammar and the A a A b | B b B a grammar are both CLR(1) but not SLR(1). The implication holds the other way: SLR(1) conflict-free implies CLR(1) conflict-free.
Summary
An LR(1) item is [A → α • β, a]. The lookahead a is used only when the dot is at the end.
CLOSURE adds [B → • γ, b] for every b in FIRST(β a). GOTO moves the dot and keeps the lookahead.
Reduce by A → α only on the item's own lookahead, not on all of FOLLOW(A).
CLR(1) handles every LR(1) grammar, catches errors as early as possible, and recognises exactly the deterministic CFLs.
The cost is size: states with the same core but different lookaheads are kept separate, so CLR tables are much larger than SLR/LALR tables.
CLR remembers, inside every item, exactly which token may come next. Maximum precision, maximum table size.