SLR(1) Parser and Conflicts: LR(0) Items, FOLLOW Sets and a Full Parse

Building LR(0) states is only half the work. Every completed item must reach the correct ACTION columns without colliding with a shift or another reduction. The worked grammar runs from augmentation and FOLLOW sets through a six-state table, then accepts aab$ with the epsilon move shown. Start with the broader Parsing in Compiler Design: Top-Down and Bottom-Up Explained overview if shifts, reductions, or handles are unfamiliar.

Related reading: LR parser comparison and Top-down and bottom-up parsing.

What an SLR(1) parser adds to LR(0) items

An LR(0) item A -> alpha . beta records progress through a production. closure(I) adds productions for the non-terminal after a dot. GOTO(I, X) moves the dot across X, then takes closure.

SLR keeps those states and transitions, but places a completed item's reduction only in FOLLOW(A) columns. S' -> S . accepts only under $. The order is: augment and number, find FIRST and FOLLOW, build LR(0), map edges, add reductions and accept, then check every ACTION cell. The 1 means one table lookahead, not an item-specific lookahead.

SLR grammar and its six LR(0) states

The numbered grammar is:

(0) S' -> S
(1) S  -> A b
(2) A  -> a A
(3) A  -> epsilon

Terminals are {a, b, $} and non-terminals are {S, A}. The language is {a^n b | n >= 0}, with members b, ab, and aab:

S => A b => a A b => a a A b => a a b

Productions 2 and 3 give FIRST(A) = {a, epsilon}. Because A may disappear before b, FIRST(S) = {a, b}. The start symbol gives FOLLOW(S) = {$}, while S -> A b gives FOLLOW(A) = {b}. The last A in A -> a A only passes FOLLOW(A) to itself.

The canonical collection is:

I0: S' -> . S      S -> . A b      A -> . a A      A -> .
I1: S' -> S .
I2: S  -> A . b
I3: A  -> a . A    A -> . a A      A -> .
I4: S  -> A b .
I5: A  -> a A .

Non-empty transitions are I0 --S--> I1, I0 --A--> I2, I0 --a--> I3, I2 --b--> I4, I3 --a--> I3, and I3 --A--> I5. A -> . is the completed epsilon production. Epsilon is not an input symbol and creates no edge.

LR(0) conflict and the SLR ACTION/GOTO table

LR(0) places a completed-item reduction under every terminal. In I0 and I3, A -> . a A shifts on a, while A -> . also places r3: A -> epsilon there. Thus ACTION[0,a] and ACTION[3,a] contain s3/r3 conflicts.

SLR restricts r3 to FOLLOW(A) = {b}. Let r1: S -> A b, r2: A -> a A, and r3: A -> epsilon:

The a edges give s3, I2's b edge gives s4, and non-terminal edges give GOTO 1, 2, and 5. States 0 and 3 use r3 only on b; I4 uses r1 on $; I5 uses r2 on b; I1 accepts on $. No ACTION cell has two actions, so the grammar is SLR(1).

SLR parse of aab$, including epsilon and GOTO

A bottom-up parse recognises handles in reverse: epsilon, aA, aA, Ab. The stack alternates symbols and states.

At step 2, epsilon consumes nothing and pops zero entries, but still pushes A and goto(3,A)=5. At step 3, a A removes four entries because each symbol has a paired state. The sequence is s3, s3, r3, r2, r2, s4, r1, accept.

Shift-reduce and reduce-reduce conflicts

A conflict means one state and lookahead demand multiple actions. Shift-reduce combines a shift with a reduction; reduce-reduce combines two reductions. An error cell has zero actions.

LR(0) had s3/r3 under a in states 0 and 3. SLR moved r3 to {b}. Choose neither arbitrarily without declared precedence or associativity.

For reduce-reduce, take (0) S'->S, (1) S->A, (2) S->B, (3) A->x, (4) B->x. After x, a state contains A->x. and B->x.. Since FOLLOW(A)=FOLLOW(B)={$}, its $ cell demands r3 and r4. This grammar has two derivations for x, but conflicts do not always prove ambiguity.

Why FOLLOW can be too coarse for SLR

Take (0) S'->S, (1) S->A a, (2) S->b A c, (3) S->d c, (4) S->b d a, (5) A->d. Productions 1 and 2 give FOLLOW(A)={a,c}. After initial d, a state contains S->d.c and A->d., demanding shift and r5 under c. After b d, S->b d.a and A->d. demand both under a. The grammar is not SLR(1).

FOLLOW loses state context. Canonical LR(1) keeps lookahead a after initial d and c after b d, avoiding both collisions here. This grammar needs FOLLOW to remove the LR(0) reductions; the SLR, CLR and LALR parser comparison instead follows one assignment grammar across all three parser families to compare state counts, parser power, and conflict behaviour. Not every non-SLR grammar is CLR(1).

How practice questions test SLR

Practise SLR through closure and GOTO calculations, FOLLOW-set reductions, individual ACTION cells, conflict diagnosis, complete traces, and comparisons with CLR or LALR. For each form, write the state, lookahead, and exact competing actions before choosing an answer.

Rapid checks: FOLLOW(A)={b}; GOTO(I0,a)=I3; ACTION[3,b]=r3; A->aA pops four entries; 0 A 2 b 4 on $ becomes 0 S 1 through r1 and goto(0,S)=1.

The short version and the next concrete step

Remember seven verbs: augment, number, follow, close, move, table, trace. The chain is FOLLOW(A)={b} -> six LR(0) states -> LR(0) conflicts at [0,a] and [3,a] -> SLR moves r3 to b only -> aab$ accepted.

Now parse b$. State 0 applies zero-pop r3 to reach 0 A 2; s4 reaches 0 A 2 b 4; r1 reaches 0 S 1; and $ is accepted. Empty input $ is rejected immediately because every string in this grammar needs the final b.

Use GATE Guidance by Sanchit Sir for structured preparation. Zero to Hero provides a broader core-CS path, while the CS Fundamentals category is the neutral subject hub.