SLR(1)

0 · Recall Warm-up

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

• What makes a grammar not LR(0)? from Lesson 2.4.2
• Where does A → ε go in an LL(1) table? from Lesson 2.3.3
• How many steps does a derivation of a sentence take, in terms of its parse tree? from Lesson 2.1.1

1 · The Story

📖

A smarter fold

Kabir’s bundle I2 for expressions holds two cards: “E → T •” (fold now) and “T → T • * F” (wait for *). LR(0) Kabir panics: fold or wait?

He remembers Chetan’s follower lists. If he folds T into E, the next word must be something that can come right after an E: a +, a closing bracket, or the end. A * can never follow an E. So when the next word is *, folding is pointless: wait. When it is +, ) or $, fold.

This one look at the next word, checked against the follower list, removes the panic in most rulebooks. Not in all of them.

2 · Predict First

🤔

In the grammar S → L = R | R, L → * R | id, R → L, a state holds S → L • = R and R → L •. Is = in FOLLOW(R)? Write your guess down. The answer is in the vault.

3 · Core Concept

The SLR(1) rule

SLR(1) (simple LR) uses the LR(0) automaton but places reductions more carefully:

• shift entries: as in LR(0);
• for a complete item A → α• in state Iᵢ: ACTION[i, a] = reduce A → α only for a ∈ FOLLOW(A);
• accept and GOTO: as in LR(0).

A grammar is SLR(1) if this table has no multiple entries.

Conflict conditions

In a state I, an SLR conflict occurs if

• (S/R) A → α• ∈ I and B → β•aγ ∈ I with a ∈ FOLLOW(A);
• (R/R) A → α• and B → β• in I with FOLLOW(A) ∩ FOLLOW(B) ≠ ∅.

What SLR gains and what it misses

Every LR(0) grammar is SLR(1); SLR fixes the expression grammar. But FOLLOW(A) collects every token that can follow A anywhere in the grammar, not only after this particular state. In S → L = R | R, L → * R | id, R → L, = follows R in some contexts (after * R inside L = R) but not when R was reached from S → R. SLR cannot tell these apart, so it reports a conflict the grammar does not really have.

Story → compiler term

4 · Visual

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

The LR(0) automaton of the expression grammar (12 states). SLR uses the same states.

SLR(1) table: reductions only under FOLLOW. FOLLOW(E) = { ), +, $ }, FOLLOW(T) = { ), *, +, $ }, FOLLOW(F) = { ), *, +, $ }.

5 · Worked Examples

Example 1 Easy

How does SLR resolve state I2 = { E → T•, T → T•*F } of the expression grammar?

Solution

Shift on * (from T → T•*F). Reduce E → T only on FOLLOW(E) = { ), +, $ }. Since * ∉ FOLLOW(E), the clash disappears: Kabir waits when * comes, folds when +, ) or $ comes.

Example 2 Medium

Parse id * id + id with the SLR table.

Solution

14 rows: 5 shifts (one per token), 8 reduces (one per interior node), 1 accept.

Example 3 GATE

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

Solution

State I2 = GOTO(I0, L) = { S → L • = R, R → L • }. Shift on = from S → L•=R; reduce R → L on FOLLOW(R) = { =, $ }. Since = ∈ FOLLOW(R): shift/reduce conflict on =. Yet the grammar is unambiguous: in I2 the R can only be a whole statement, which is followed by $, never by =. The follower list is too coarse here.

6 · Shortcuts

⚡

SLR test: for each state with a complete item A → α•: (1) no terminal after a dot in that state may lie in FOLLOW(A); (2) any two complete items must have disjoint FOLLOW sets. Valid when: deciding SLR(1) once the LR(0) states and FOLLOW sets are known.

⚡

States(SLR) = states(LR(0)); only the reduce entries differ. Valid when: questions about table sizes.

7 · GATE Traps

⚠️

• SLR uses the LR(0) items (no lookaheads inside items); only the table is different.
• FOLLOW is grammar-wide, so SLR can report false conflicts (the L = R grammar).
• Every LR(0) grammar is SLR(1), not the other way round.
• Unambiguous does not imply SLR(1).
• An SLR table never has more states than the LR(0) automaton.

8 · Memory Hook

🧠

SLR = LR(0) states + FOLLOW-filtered reduces. “Fold only if the next word may follow.”

9 · Connect the Dots

FOLLOW is too coarse when the right next token depends on how the parser reached a state. The next lesson builds a finer automaton whose items carry their own lookahead.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markSLR

In an SLR(1) table, a complete item A → α• in state i produces reduce entries in columns:

• (A) all terminals and $
• (B) FIRST(A)
• (C) FOLLOW(A)
• (D) only $

Q2MCQ2 marksConflicts

For S → L = R | R, L → * R | id, R → L, the SLR(1) table has:

• (A) no conflicts
• (B) a shift/reduce conflict on =
• (C) a reduce/reduce conflict on $
• (D) conflicts in every state

Q3NAT1 markTrace

An SLR parser parses id * id + id with the expression grammar. How many shift moves does it make?

Numerical answer: ________

Q4MSQ2 marksClassification

Which grammars are SLR(1)?

• (A) E → E + T | T, T → T * F | F, F → ( E ) | id
• (B) S → L = R | R, L → * R | id, R → L
• (C) S → x A y | x B z, A → q, B → q
• (D) S → a S | a

Q5MCQ1 markStates

Compared with the LR(0) automaton, the SLR(1) parser for the same grammar has:

• (A) more states
• (B) the same number of states
• (C) fewer states
• (D) twice as many states

11 · Rule Card

• SLR(1) = LR(0) automaton + reduce A → α only on FOLLOW(A).
• S/R conflict: A → α• and B → β•aγ with a ∈ FOLLOW(A).
• R/R conflict: A → α•, B → β• with FOLLOW(A) ∩ FOLLOW(B) ≠ ∅.
• LR(0) ⊂ SLR(1); same number of states.
• Weakness: FOLLOW is global (false conflicts, e.g. L = R).

12 · Concept Ledger

SLR(1)SLR parsing tableFOLLOW-based reduceSLR conflict

13 · Answer Vault