SLR(1) parsing is the bottom-up method most compiler courses teach first: build the canonical collection of LR(0) items, then fill an ACTION/GOTO table using FOLLOW sets. This page does it for the classic expression grammar from the Dragon Book. Unlike LL(1), bottom-up parsing handles the left-recursive grammar directly.
The grammar, augmented
Add a new start symbol E′ → E and number the productions; reduce actions refer to these numbers.
0. E′ → E
1. E → E + T
2. E → T
3. T → T * F
4. T → F
5. F → ( E )
6. F → id
LR(0) items and the canonical collection
An item is a production with a dot showing how much has been seen: E → E • + T means E has been read and + is expected next. Each state is a set of items, built with two operations:
- closure: if the dot is before a non-terminal B, add every B → • γ (and repeat).
- goto(I, X): move the dot over X in every item of I where X is next, then take the closure.
Starting from closure({E′ → • E}) and applying goto on every symbol gives 12 states:
| State | Items |
|---|---|
| I0 | E' → • E E → • E + T E → • T T → • T * F T → • F F → • ( E ) F → • id |
| I1 | E' → E • E → E • + T |
| I2 | E → T • T → T • * F |
| I3 | T → F • |
| I4 | F → ( • E ) E → • E + T E → • T T → • T * F T → • F F → • ( E ) F → • id |
| I5 | F → id • |
| I6 | E → E + • T T → • T * F T → • F F → • ( E ) F → • id |
| I7 | T → T * • F F → • ( E ) F → • id |
| I8 | F → ( E • ) E → E • + T |
| I9 | E → E + T • T → T • * F |
| I10 | T → T * F • |
| I11 | F → ( E ) • |
Why LR(0) isn't enough here
State I2 holds both E → T • (a complete item, so "reduce") and T → T • * F (so "shift *"). Pure LR(0) reduces in every column for a complete item, so it puts both r2 and s7 under * : a shift/reduce conflict. State I9 has the same problem. The grammar is not LR(0).
The SLR(1) fix: reduce only on FOLLOW
SLR reduces by A → α only on terminals in FOLLOW(A). FOLLOW(E) = { +, ), $ }, which doesn't contain *, so in I2 the * column keeps only the shift. The rules:
- If goto(Iᵢ, a) = Iⱼ for a terminal a: ACTION[i, a] = shift j (sj).
- If A → α • is in Iᵢ (A ≠ E′): ACTION[i, a] = reduce by A → α for every a in FOLLOW(A).
- If E′ → E • is in Iᵢ: ACTION[i, $] = accept.
- If goto(Iᵢ, A) = Iⱼ for a non-terminal A: GOTO[i, A] = j.
With FOLLOW(E) = { +, ), $ } and FOLLOW(T) = FOLLOW(F) = { +, *, ), $ }:
| State | + | * | ( | ) | id | $ | E | T | F |
|---|---|---|---|---|---|---|---|---|---|
| 0 | s4 | s5 | 1 | 2 | 3 | ||||
| 1 | s6 | acc | |||||||
| 2 | r2 | s7 | r2 | r2 | |||||
| 3 | r4 | r4 | r4 | r4 | |||||
| 4 | s4 | s5 | 8 | 2 | 3 | ||||
| 5 | r6 | r6 | r6 | r6 | |||||
| 6 | s4 | s5 | 9 | 3 | |||||
| 7 | s4 | s5 | 10 | ||||||
| 8 | s6 | s11 | |||||||
| 9 | r1 | s7 | r1 | r1 | |||||
| 10 | r3 | r3 | r3 | r3 | |||||
| 11 | r5 | r5 | r5 | r5 |
No cell has two entries, so the grammar is SLR(1).
Parsing id * id + id
The stack alternates states and symbols, starting with state 0. Look up ACTION[top state, next input]: shift pushes the symbol and the new state; reduce by A → α pops 2|α| entries, then pushes A and GOTO[exposed state, A].
| Stack | Input | Action |
|---|---|---|
| 0 | id * id + id $ | Shift id, go to state 5 |
| 0 id 5 | * id + id $ | Reduce by F → id (r6) |
| 0 F 3 | * id + id $ | Reduce by T → F (r4) |
| 0 T 2 | * id + id $ | Shift *, go to state 7 |
| 0 T 2 * 7 | id + id $ | Shift id, go to state 5 |
| 0 T 2 * 7 id 5 | + id $ | Reduce by F → id (r6) |
| 0 T 2 * 7 F 10 | + id $ | Reduce by T → T * F (r3) |
| 0 T 2 | + id $ | Reduce by E → T (r2) |
| 0 E 1 | + id $ | Shift +, go to state 6 |
| 0 E 1 + 6 | id $ | Shift id, go to state 5 |
| 0 E 1 + 6 id 5 | $ | Reduce by F → id (r6) |
| 0 E 1 + 6 F 3 | $ | Reduce by T → F (r4) |
| 0 E 1 + 6 T 9 | $ | Reduce by E → E + T (r1) |
| 0 E 1 | $ | Accept |
Accepted in 14 steps. Notice that * binds tighter than +: T → T * F is reduced (step 7) before E → E + T (step 13), exactly as the grammar intends.
Common mistakes
- Forgetting to augment the grammar with E′ → E; the accept action comes from E′ → E •.
- Putting reduce actions in every column (that's LR(0)); SLR uses FOLLOW of the left-hand side.
- Skipping closure after goto, which drops states and leaves the table incomplete.
- Popping |α| symbols instead of 2|α| entries when the stack holds both states and symbols.
Check your own answers
The LR parser builds the canonical collection, the LR(0), SLR(1), LALR(1) and LR(1) tables, names every conflict and the items that cause it, and traces a parse. It needs the FOLLOW sets explained in FIRST and FOLLOW sets, which the FIRST and FOLLOW calculator computes for any grammar.