Chapter 15 of 33

SLR Parsing

In LR(0) Items & LR(0) Parsing we built a parser that decides when to reduce without looking at the input at all. As soon as a state contains a completed item A → α •, an LR(0) parser reduces, whatever the next token is. That is simple, but it is also blind. Even the ordinary expression grammar that every textbook uses is not LR(0).

The fix is small and clever: before reducing by A → α, peek at the next input token and ask, "can this token ever come right after an A?" If not, reducing would be pointless, so don't. The set of tokens that can follow A is exactly FOLLOW(A), which we learned to compute in FIRST & FOLLOW Sets. This gives the SLR (Simple LR) parser, introduced by Frank DeRemer in 1971.

An SLR(1) parser uses the canonical collection of LR(0) items as its states. In a state containing a complete item A → α •, it reduces by A → α only when the next input token is in FOLLOW(A). A grammar is SLR(1) if this table has no conflicts.

Every state, table and trace in this chapter was produced by a small Python LR-table generator and checked against hand calculation, so you can use them to verify your own answers.


Why LR(0) Is Not Enough

Take the classic expression grammar, augmented with E' → E and numbered so we can refer to each production:

(0) E' → E
(1) E → E + T
(2) E → T
(3) T → T * F
(4) T → F
(5) F → ( E )
(6) F → id

One of its LR(0) states (we will list all of them shortly) is:

I2:
    E → T •
    T → T • * F

This state is reached after the parser has recognised a T. The first item says "a complete E → T is on the stack, reduce". The second says "maybe this T is the start of T * F, so shift a *". An LR(0) parser must reduce on every token, so on input * it has both a reduce and a shift: a shift-reduce conflict. The same thing happens in state I9 (E → E + T • and T → T • * F).

But think about what reducing would mean. If we turn T into E while the next token is *, we would need a sentential form in which E is immediately followed by *. Look at the grammar: E is only ever followed by +, ) or the end of input. So on *, the reduce is guaranteed to lead to an error. The only sensible move is to shift.

Key intuition: reduce by A → α only if the next token can legally appear after A. Otherwise the reduction can never be part of a successful parse.


How the SLR Table Is Built

The SLR parser uses exactly the same automaton as LR(0): same items, same states, same GOTO transitions. Only the way the reduce entries are placed in the ACTION table changes.

1. Augment the grammar with S' → S (S is the old start symbol).
2. Build C = {I0, I1, ..., In}, the canonical collection of LR(0) item sets,
   using CLOSURE and GOTO.
3. Compute FOLLOW(A) for every nonterminal A.
4. For each state Ii:
   a. If A → α • a β is in Ii, a is a terminal and GOTO(Ii, a) = Ij:
         ACTION[i, a] = shift j                 (written sj)
   b. If A → α • is in Ii and A ≠ S':
         for every terminal a in FOLLOW(A):
         ACTION[i, a] = reduce A → α            (written rk, k = production number)
   c. If S' → S • is in Ii:
         ACTION[i, $] = accept
5. For each nonterminal A, if GOTO(Ii, A) = Ij:   GOTO[i, A] = j
6. Every entry not filled is "error".
7. If any ACTION cell gets two different entries, the grammar is NOT SLR(1).

Compare with LR(0): in step 4b, an LR(0) table writes the reduce under every terminal (and $). SLR writes it only under the terminals in FOLLOW(A). Shift entries, accept and the GOTO part are identical.

The two kinds of conflict

Conflict

Items in the same state

It occurs in SLR when

Shift-reduce (S/R)

A → α • and B → β • a γ

a ∈ FOLLOW(A)

Reduce-reduce (R/R)

A → α • and B → β •

FOLLOW(A) ∩ FOLLOW(B) ≠ ∅

There is no such thing as a shift-shift conflict: GOTO(Ii, a) is a single state, so the shift target on a terminal is always unique.


Worked Example 1: The Expression Grammar

Step 1: FOLLOW sets

FOLLOW(E) = { +, ), $ }
FOLLOW(T) = { +, *, ), $ }
FOLLOW(F) = { +, *, ), $ }

Quick reasoning: $ ∈ FOLLOW(E) because E is the start symbol; E → E + T and F → ( E ) put + and ) in FOLLOW(E). FOLLOW(T) gets everything in FOLLOW(E) (from E → T) plus * (from T → T * F). FOLLOW(F) equals FOLLOW(T) because of T → F and T → T * F.

Step 2: The LR(0) item sets

These are the same 12 states you get in the LR(0) chapter. States are numbered in the order they are discovered: from each state we take the symbols after the dot in the order they appear, and every new item set gets the next number.

I0:
    E' → • E
    E → • E + T
    E → • T
    T → • T * F
    T → • F
    F → • ( E )
    F → • id
    on E → I1   on T → I2   on F → I3   on ( → I4   on id → I5

I1:
    E' → E •
    E → E • + T
    on + → I6

I2:
    E → T •
    T → T • * F
    on * → I7

I3:
    T → F •

I4:
    F → ( • E )
    E → • E + T
    E → • T
    T → • T * F
    T → • F
    F → • ( E )
    F → • id
    on E → I8   on T → I2   on F → I3   on ( → I4   on id → I5

I5:
    F → id •

I6:
    E → E + • T
    T → • T * F
    T → • F
    F → • ( E )
    F → • id
    on T → I9   on F → I3   on ( → I4   on id → I5

I7:
    T → T * • F
    F → • ( E )
    F → • id
    on F → I10   on ( → I4   on id → I5

I8:
    F → ( E • )
    E → E • + T
    on ) → I11   on + → I6

I9:
    E → E + T •
    T → T • * F
    on * → I7

I10:
    T → T * F •

I11:
    F → ( E ) •

Step 3: Fill the table

Let's fill a few rows by hand to see the rule at work.

  • I0 has no complete item. Shifts: ( → I4 and id → I5. GOTO: E → 1, T → 2, F → 3.

  • I1 has E' → E •, so ACTION[1, $] = accept. E → E • + T gives shift 6 on +.

  • I2 has E → T • (production 2). FOLLOW(E) = { +, ), $ }, so r2 goes under those three. T → T • * F gives s7 under *. The cell [2, *] gets only s7, so the LR(0) conflict is gone.

  • I3 has T → F • (production 4): r4 under FOLLOW(T) = { +, *, ), $ }.

  • I9 has E → E + T • (production 1): r1 under { +, ), $ }, and s7 under *. Again no conflict.

The complete SLR(1) table (blank = error):

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 this grammar is SLR(1), even though it is not LR(0).

Notice how the table encodes precedence and associativity without anyone writing them down. In state 2 (a T is on top) the parser shifts * but reduces on +: multiplication binds tighter. In state 9 (E + T on top) it reduces on +, so a + b + c groups as (a + b) + c: left associativity.

Step 4: Parse id * id + id

The parser keeps states and grammar symbols on the stack (states alone are enough; the symbols are shown to make it readable). At each step it looks up ACTION[top state, next token].

Stack                     Input   Action
0                id * id + id $   s5: shift id, go to 5
0 id 5              * id + id $   r6: reduce F → id, goto[0, F] = 3
0 F 3               * id + id $   r4: reduce T → F, goto[0, T] = 2
0 T 2               * id + id $   s7: shift *, go to 7
0 T 2 * 7             id + id $   s5: shift id, go to 5
0 T 2 * 7 id 5           + id $   r6: reduce F → id, goto[7, F] = 10
0 T 2 * 7 F 10           + id $   r3: reduce T → T * F, goto[0, T] = 2
0 T 2                    + id $   r2: reduce E → T, goto[0, E] = 1
0 E 1                    + id $   s6: shift +, go to 6
0 E 1 + 6                  id $   s5: shift id, go to 5
0 E 1 + 6 id 5                $   r6: reduce F → id, goto[6, F] = 3
0 E 1 + 6 F 3                 $   r4: reduce T → F, goto[6, T] = 9
0 E 1 + 6 T 9                 $   r1: reduce E → E + T, goto[0, E] = 1
0 E 1                         $   accept

Read the reductions from top to bottom: F → id, T → F, F → id, T → T * F, E → T, F → id, T → F, E → E + T. Reverse that list and you get the rightmost derivation of id * id + id. This is true of every LR parser: it traces out a rightmost derivation in reverse.

Also notice what happened at the *. With T on the stack and * next, the parser was in state 2 and shifted, keeping id * id together before the addition was even seen.

What an error looks like

For the bad input id + * id:

Stack             Input   Action
0           id + * id $   s5: shift id, go to 5
0 id 5         + * id $   r6: reduce F → id, goto[0, F] = 3
0 F 3          + * id $   r4: reduce T → F, goto[0, T] = 2
0 T 2          + * id $   r2: reduce E → T, goto[0, E] = 1
0 E 1          + * id $   s6: shift +, go to 6
0 E 1 + 6        * id $   blank entry [6, *]: syntax error

The parser stops at the first token that cannot extend a valid prefix. In state 6 it expects the start of a T (an id or (), and * is neither. LR parsers never shift a token that cannot be part of some valid sentence: this is called the valid prefix property.


Worked Example 2: A Small Exam Favourite

Grammars like this appear often in exams because they are small enough to do by hand:

(0) E' → E
(1) E → E + n
(2) E → E * n
(3) E → n

FOLLOW(E) = { +, *, $ }. The item sets:

I0:
    E' → • E
    E → • E + n
    E → • E * n
    E → • n
    on E → I1   on n → I2

I1:
    E' → E •
    E → E • + n
    E → E • * n
    on + → I3   on * → I4

I2:
    E → n •

I3:
    E → E + • n
    on n → I5

I4:
    E → E * • n
    on n → I6

I5:
    E → E + n •

I6:
    E → E * n •

State

+

n

*

$

E

0

s2

1

1

s3

s4

acc

2

r3

r3

r3

3

s5

4

s6

5

r1

r1

r1

6

r2

r2

r2

Parsing n + n * n:

Stack                 Input   Action
0               n + n * n $   s2: shift n, go to 2
0 n 2             + n * n $   r3: reduce E → n, goto[0, E] = 1
0 E 1             + n * n $   s3: shift +, go to 3
0 E 1 + 3           n * n $   s5: shift n, go to 5
0 E 1 + 3 n 5         * n $   r1: reduce E → E + n, goto[0, E] = 1
0 E 1                 * n $   s4: shift *, go to 4
0 E 1 * 4               n $   s6: shift n, go to 6
0 E 1 * 4 n 6             $   r2: reduce E → E * n, goto[0, E] = 1
0 E 1                     $   accept

Here there is no precedence between + and *: the grammar simply evaluates left to right, so n + n * n is grouped as (n + n) * n. The handles reduced, in order, are n, E + n, E * n. Questions of the form "which of these is a handle of the right sentential form…" are really asking you to run this trace.


Worked Example 3: A Reduce-Reduce Conflict That SLR Fixes

(0) S' → S
(1) S → a A c
(2) S → a B d
(3) A → z
(4) B → z

After reading a z, the parser is in this LR(0) state:

I5:
    A → z •
    B → z •

LR(0) would write both r3 and r4 in every column: a reduce-reduce conflict. But FOLLOW(A) = { c } and FOLLOW(B) = { d }. These are disjoint, so SLR puts r3 only under c and r4 only under d. On input a z d the parser reduces z to B, because the next token is d. The grammar is SLR(1) but not LR(0).


When SLR Is Not Enough

FOLLOW(A) contains every token that can follow A anywhere in any sentential form. But inside a particular state, only some of those tokens can actually follow. SLR ignores the state, and sometimes that costs it.

The classic example: assignments with pointers

This grammar describes C-like assignments where L is an l-value (something you can assign to) and R is an r-value:

(0) S' → S
(1) S → L = R
(2) S → R
(3) L → * R
(4) L → id
(5) R → L
FOLLOW(S) = { $ }
FOLLOW(L) = { =, $ }
FOLLOW(R) = { =, $ }

Why is = in FOLLOW(R)? Because S → L = R puts = in FOLLOW(L), and R → L passes FOLLOW(R) into FOLLOW(L), while L → * R passes FOLLOW(L) into FOLLOW(R). Concretely, S ⇒ L = R ⇒ * R = R, and here R is followed by =. So the SLR rule is correct that "R can be followed by =" somewhere.

The LR(0) item sets:

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 → I8   on * → I4   on id → I5

I7:
    L → * R •

I8:
    R → L •

I9:
    S → L = R •

Now look at state I2, reached right after the parser has read an L at the very beginning of the input:

I2:
    S → L • = R      → shift on =
    R → L •          → reduce on FOLLOW(R) = { =, $ }

On = the cell gets both s6 and r5:

State

=

*

id

$

S

L

R

0

s4

s5

1

2

3

1

acc

2

s6 / r5

r5

3

r2

4

s4

s5

8

7

5

r4

r4

6

s4

s5

8

9

7

r3

r3

8

r5

r5

9

r1

So the grammar is not SLR(1). Yet it is not ambiguous, and the conflict is fake. In state I2 the L is at the start of the statement. If we reduced it to R we would get a sentential form beginning with R =, and no such form exists (an R at the start must be the entire statement, S → R). In this state, R can only be followed by $. SLR cannot see that, because it uses the global FOLLOW set instead of a per-state lookahead.

The cure is to carry the precise lookahead inside each item. That is the idea behind CLR (Canonical LR) Parsing, and its space-saving cousin LALR Parsing, the next two chapters. Both handle this grammar with no conflict.

A reduce-reduce failure

(0) S' → S
(1) S → A a A b
(2) S → B b B a
(3) A → ε
(4) B → ε

In I0 the parser must immediately reduce an empty A or an empty B. FOLLOW(A) = FOLLOW(B) = { a, b }, so both r3 and r4 land in [0, a] and [0, b]. The grammar is not SLR(1), even though it is LL(1) (the two alternatives of S start with different tokens). Again, the true lookahead is state-specific: at the very start, an empty A must be followed by a and an empty B by b.


Checking Whether a Grammar Is SLR(1): A Fast Method

In exams you rarely need the whole table. You only need the states with a complete item:

  1. Build the LR(0) item sets (or at least the ones that have an item with the dot at the end).

  2. For each such state, list the terminals after the dot in its other items (shift symbols).

  3. For each complete item A → α •, check FOLLOW(A) against those shift symbols (S/R) and against the FOLLOW sets of other complete items in the same state (R/R).

  4. Any overlap means the grammar is not SLR(1). No overlap anywhere means it is.

A state with a single complete item and nothing else can never cause a conflict, so you can skip it.


LR(0) vs SLR(1)

Feature

LR(0)

SLR(1)

States

Canonical LR(0) collection

Same collection, same number of states

Reduce A → α placed under

Every terminal and $

Only terminals in FOLLOW(A)

Lookahead used

None

1 token, through global FOLLOW sets

Grammars accepted

LR(0) grammars

All LR(0) grammars and more (e.g. the expression grammar)

Shift entries, GOTO part

Identical

Error detection

May reduce a few times before noticing an error

Notices earlier, since blank cells appear in reduce rows

Since SLR only removes reduce entries compared with LR(0), every conflict-free LR(0) table is also a conflict-free SLR table. So every LR(0) grammar is SLR(1), and the expression grammar shows the inclusion is strict.


Common Mistakes

  • Using FIRST instead of FOLLOW for reduce entries. The reduce A → α goes under FOLLOW(A), the left-hand side, not anything to do with α.

  • Forgetting $ in FOLLOW of the start symbol. Without it, the final reductions (like E → T at the end of input) go missing.

  • Building new item sets for SLR. SLR uses the same LR(0) items. Only the reduce placement changes.

  • Writing a reduce for S' → S. The augmented production gives accept on $, never a reduce.

  • Concluding "ambiguous" from an SLR conflict. Every SLR(1) grammar is unambiguous, but the converse fails: the L = R grammar is unambiguous and still not SLR(1).

  • Using production numbers inconsistently. In rk, k is the production number from your numbered list; in sj, j is a state number. Mixing the two is the most common table error.


Practice Questions

Q1. How many states does the SLR(1) parser for the grammar E → E + T | T, T → T * F | F, F → ( E ) | id have?

12 (I0 to I11). An SLR parser always has exactly as many states as the canonical LR(0) collection, because it uses that collection.

Q2. A state contains A → b • and B → b • c. FOLLOW(A) = { a, $ }. Is there an SLR conflict in this state?

No. The reduce A → b goes under { a, $ } and the shift goes under c. They don't overlap. (If c were in FOLLOW(A), there would be a shift-reduce conflict.)

Q3. Is S → A a A b | B b B a, A → ε, B → ε SLR(1)? Is it LL(1)?

Not SLR(1): I0 contains A → • and B → •, and FOLLOW(A) ∩ FOLLOW(B) = { a, b } ≠ ∅, a reduce-reduce conflict. It is LL(1): FIRST(A a A b) = { a } and FIRST(B b B a) = { b } are disjoint. So an LL(1) grammar need not be SLR(1).

Q4. Which entries differ between the LR(0) and SLR(1) tables of the same grammar?

Only reduce entries. LR(0) puts each reduce in every column; SLR keeps it only under FOLLOW of the left side. Shift, accept and GOTO entries are identical.

Q5. Can an ambiguous grammar be SLR(1)?

No. An ambiguous grammar always produces at least one conflict in any LR table (SLR, CLR or LALR), because some sentence has two rightmost derivations and the parser would have to follow both. Parser generators such as Yacc let you resolve those conflicts with precedence rules (see Yacc & Bison), but then the table no longer follows the pure SLR/LR rules.

Q6. Why does SLR report a conflict on S → L = R | R, L → * R | id, R → L?

State I2 = { S → L • = R, R → L • }. FOLLOW(R) contains = (because of derivations like * R = R), so SLR puts r5 under =, clashing with shift 6. In that specific state, though, R could only be followed by $. SLR's FOLLOW set is too coarse; CLR/LALR lookaheads solve it.


Summary

  • SLR(1) = LR(0) automaton + FOLLOW sets for reduce decisions.

  • In a state with A → α •, reduce only on tokens in FOLLOW(A). Shift, accept and GOTO are filled as in LR(0).

  • Conflicts: S/R when a shift symbol is in FOLLOW(A); R/R when two completed items have overlapping FOLLOW sets.

  • The expression grammar has 12 states and is SLR(1) but not LR(0).

  • Every LR(0) grammar is SLR(1); every SLR(1) grammar is unambiguous.

  • FOLLOW is global, not per state, so SLR can report conflicts that are not real (the L = R grammar). CLR and LALR fix this with per-item lookaheads.

SLR reduces only when the next token is allowed to follow: same states as LR(0), smarter reduce entries.