5.3 SLR(1) Parsing: Follow Set Lookaheads & Conflict Resolution

Back to DBMS Notes

📚Module 01SLR(1) Parsing & Conflict Resolution⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Discerning Passport Inspector

In pure LR(0) parsing, the parser operates with total blindness during reductions:

• Whenever a state contains a completed assembly ($A \to \alpha \cdot$), it writes Reduce across every single terminal column in that table row.
• This is like an immigration officer stamping every single traveler's passport with an entry visa without checking their boarding pass! If a traveler holds a ticket for another sovereign terminal, an unnecessary conflict or a false entry occurs.

Simple LR (SLR(1)) introduces a sharp, common-sense lookahead gate:

• A reduction by $A \to \alpha$ should ONLY occur if the next incoming terminal token $a$ is a symbol that can legally appear immediately after $A$ in the language:

  $$a \in \text{FOLLOW}(A)$$

• If $a \notin \text{FOLLOW}(A)$, performing reduction $A \to \alpha$ is futile because non-terminal $A$ could never legally connect to $a$ in any valid derivation.

• By placing reductions strictly under $\text{FOLLOW}(A)$ columns, SLR(1) eliminates the vast majority of false conflicts that paralyze LR(0).

💻 Bridging to Computer Science: Restricting Reductions via FOLLOW Lookaheads

In bottom-up syntax analysis:

• SLR(1) retains the exact same DFA state machine and identical canonical collection of LR(0) items as an LR(0) parser.
• However, during parsing table generation, each complete item $[A \to \alpha \cdot]$ consults the global context of the grammar: $\text{FOLLOW}(A)$.
• Lookahead token $a$ acts as a gatekeeper: if $a \in \text{FOLLOW}(A)$, the reduction is scheduled; if $a \notin \text{FOLLOW}(A)$, the cell remains blank.

📑Table of Contents

• 🏗️ Architectural Foundations: The SLR(1) Reduction Filter
  • ⚖️ LR(0) vs SLR(1): Side-by-Side Comparison
• 📐 Formal Mathematical Foundations: SLR(1) Table Construction
• 🤼 SLR(1) Conflict Conditions
  • ⚔️ Shift/Reduce Conflict in SLR(1)
  • 💥 Reduce/Reduce Conflict in SLR(1)
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: Resolving an LR(0) Shift/Reduce Conflict via SLR(1)
  • Example 2: The Canonical Assignment Grammar That Fails SLR(1)
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: The SLR(1) Reduction Filter

Architecture Flow

The SLR(1) Reduction Gating Mechanism

Filtering out illegal reduction conflicts using grammar FOLLOW sets as gatekeepers

📥Input

Lookahead Token (a)

Next unconsumed terminal token from input buffer.

→

Encountered

🎯State

Complete Item A → α •

State contains a handle ready for grammatical reduction.

→

Checks Gate

🛡️Gatekeeper

a ∈ FOLLOW(A)?

Can terminal 'a' legally appear immediately after non-terminal A?

→

Decision

✅Action

ACTION[i, a] = rk

If YES: write reduce action. If NO: reject reduction and avoid conflict.

⚖️ LR(0) vs SLR(1): Side-by-Side Comparison

LR(0) vs SLR(1): The Lookahead Filter

Contrasting blind row-wide reductions against targeted FOLLOW-set filtering

Zero Lookahead

LR(0) Parser

🙈

Dominant Architecture / DomainUnconditional Reductions

• •Places Reduce A -> α in ALL terminal columns in the state's row.
• •Zero lookahead check; completely blind to incoming tokens.
• •Generates spurious Shift/Reduce conflicts on almost all real grammars.
• •State machine and table dimensions identical to SLR(1).

"Stamp reductions unconditionally across every single column."

1 Lookahead

SLR(1) Parser

🎯

Dominant Architecture / DomainFOLLOW-Guided Reductions

• •Places Reduce A -> α ONLY under columns a ∈ FOLLOW(A).
• •Uses 1 token of lookahead to filter out illegal reductions.
• •Resolves massive numbers of LR(0) Shift/Reduce conflicts.
• •Same number of states as LR(0); significantly more expressive.

"Only reduce when the next token can legally follow the produced variable."

---

📐 Formal Mathematical Foundations: SLR(1) Table Construction

SLR(1) uses the exact same canonical collection of LR(0) items and the exact same DFA states as LR(0). The difference lies entirely in step 2 of table construction:

Given canonical collection $\mathcal{C} = \{ I_0, I_1, \dots, I_n \}$ for augmented grammar $G'$:

1. Shift Actions: If $[A \to \alpha \cdot a \beta] \in I_i$ where $a \in \Sigma$ is a terminal, and $\text{GOTO}(I_i, a) = I_j$:

   $$\text{ACTION}[i, a] = \text{Shift } j \quad (\text{written } s_j)$$

2. SLR(1) Reduce Actions (The Targeted Filter): If $[A \to \alpha \cdot] \in I_i$ where $A \neq S'$ and $A \to \alpha$ is production rule $k$:

   $$\text{ACTION}[i, a] = \text{Reduce } k \quad (\text{written } r_k) \quad \text{\bf for all } a \in \text{FOLLOW}(A)$$

   (All terminal columns $b \notin \text{FOLLOW}(A)$ remain empty error cells!).

3. Accept Action: If $[S' \to S \cdot] \in I_i$:

   $$\text{ACTION}[i, \$] = \text{Accept}$$

4. GOTO Transitions: If $\text{GOTO}(I_i, A) = I_j$ for non-terminal $A \in V$:

   $$\text{GOTO}[i, A] = j$$

---

🤼 SLR(1) Conflict Conditions

An SLR(1) parsing table exhibits a conflict if and only if one of the following conditions is satisfied:

⚔️ Shift/Reduce Conflict in SLR(1)

A state $I_i$ contains a shift item for terminal $a$ ($A \to \alpha \cdot a \beta$) AND a completed reduce item ($B \to \gamma \cdot$) such that:

$$a \in \text{FOLLOW}(B)$$

(If $a \notin \text{FOLLOW}(B)$, the conflict is successfully eliminated by the SLR(1) lookahead filter!).

💥 Reduce/Reduce Conflict in SLR(1)

A state $I_i$ contains two distinct completed reduce items $A \to \alpha \cdot$ and $B \to \beta \cdot$ such that their follow sets share at least one common terminal:

$$\text{FOLLOW}(A) \cap \text{FOLLOW}(B) \neq \emptyset$$

---

🏭 Real-World Production Context: How Industry Builds This

While pure SLR(1) parsers are rarely used directly in modern production compilers (having been superseded by LALR(1) in tools like GNU Bison, Yacc, and Menhir):

Understanding why SLR(1) fails on unambiguous constructs (such as pointer dereference assignment statements) is the core intellectual foundation of bottom-up parsing theory:

• SLR(1) computes FOLLOW sets globally across the entire grammar.
• Global FOLLOW sets merge lookaheads from independent derivation branches, polluting the lookahead set with tokens that can never legally appear in the current derivation context.
• This limitation directly inspired Canonical LR(1) (context-specific lookaheads) and LALR(1) (merging LR(1) states with identical cores).

Because SLR(1) uses the exact same DFA states as LR(0):

• Memory footprint in the runtime executable is identical to LR(0).
• Parser performance is $O(n)$ with zero backtracking.

---

📐 Numerical Applications & Worked Examples

Example 1: Resolving an LR(0) Shift/Reduce Conflict via SLR(1)

Recall the arithmetic expression grammar from Module 05 Topic 2 that suffered a Shift/Reduce conflict in LR(0):

$$\begin{aligned} S &\to E \\ E &\to E + T \mid T \\ T &\to \text{id} \end{aligned}$$

1. Augment the grammar and compute FOLLOW sets.
2. Evaluate state $I_1$ and prove that SLR(1) completely eliminates the Shift/Reduce conflict.

Step-by-Step Analytical Solution:

Step 1: Augmented Grammar & Numbered Productions

• (0) $S' \to S$
• (1) $S \to E$
• (2) $E \to E + T$
• (3) $E \to T$
• (4) $T \to \text{id}$

Step 2: Compute FOLLOW Sets

• For Start Symbol $S$:

$$\text{FOLLOW}(S) = \{ \$ \}$$

• For $E$:
  • In $S \to E$: $E$ is at the end:

$$\text{FOLLOW}(S) \subseteq \text{FOLLOW}(E) \implies \$ \in \text{FOLLOW}(E)$$

• In $E \to E + T$: $E$ is followed by +:

$$+ \in \text{FOLLOW}(E) \implies \text{FOLLOW}(E) = \{ +, \$ \}$$

• For $T$:
  • In $E \to E + T$ and $E \to T$: $T$ is at the end:

$$\text{FOLLOW}(E) \subseteq \text{FOLLOW}(T) \implies \text{FOLLOW}(T) = \{ +, \$ \}$$

Step 3: Evaluate State $I_1$ From initial state $I_0 = \text{CLOSURE}(\{ S' \to \cdot S \})$, transitioning across non-terminal $E$ yields state $I_1$:

$$I_1 = \text{GOTO}(I_0, E) = \{ S \to E \cdot, \quad E \to E \cdot + T \}$$

In state $I_1$:

1. Item $E \to E \cdot + T$ is a shift item on terminal +. It requests a Shift on column +.
2. Item $S \to E \cdot$ is a completed reduce item (production 1: $S \to E$).
   • In LR(0): $r_1$ was written into both columns + and $, creating a fatal conflict on +!
   • In SLR(1): $r_1$ is written ONLY under columns in $\text{FOLLOW}(S)$:

$$\text{FOLLOW}(S) = \{ \$ \}$$

• Crucially, $+ \notin \text{FOLLOW}(S)$!

Table Population for Row 1:

• Column +: Contains Shift to state $\text{GOTO}(I_1, +)$.
• Column $: Contains Reduce 1 ($S \to E$).

The conflict has vanished! Every cell contains at most one action. The grammar is strictly SLR(1)!

---

Example 2: The Canonical Assignment Grammar That Fails SLR(1)

Consider the unambiguous pointer-assignment grammar:

$$\begin{aligned} S &\to L = R \mid R \\ L &\to * R \mid \text{id} \\ R &\to L \end{aligned}$$

Prove analytically that this grammar is NOT SLR(1) by identifying the exact state where an unresolved Shift/Reduce conflict occurs.

Step-by-Step Analytical Proof:

Step 1: Compute FOLLOW Sets

• $S$ is start symbol:

$$\text{FOLLOW}(S) = \{ \$ \}$$

• In $S \to L = R$: $L$ is followed by = $\implies = \in \text{FOLLOW}(L)$.
• In $S \to R$: $R$ is at the end:

$$\text{FOLLOW}(S) \subseteq \text{FOLLOW}(R) \implies \$ \in \text{FOLLOW}(R)$$

• In $L \to * R$: $R$ is at the end $\implies \text{FOLLOW}(L) \subseteq \text{FOLLOW}(R)$.
• In $R \to L$: $L$ is at the end $\implies \text{FOLLOW}(R) \subseteq \text{FOLLOW}(L)$.
• Therefore, the follow sets of $L$ and $R$ merge:

$$\text{FOLLOW}(R) = \text{FOLLOW}(L) = \{ =, \$ \}$$

Step 2: Construct State $I_2$ (Transition on symbol $L$) Starting from $I_0 = \text{CLOSURE}(\{ S' \to \cdot S \})$:

• Includes $S' \to \cdot S$
• Includes $S \to \cdot L = R$ and $S \to \cdot R$
• Includes $L \to \cdot * R$ and $L \to \cdot \text{id}$
• Includes $R \to \cdot L$

Compute $\text{GOTO}(I_0, L) = \mathbf{I_2}$:

• Advancing dot over $L$ in $S \to \cdot L = R$ yields: $S \to L \cdot = R$
• Advancing dot over $L$ in $R \to \cdot L$ yields: $R \to L \cdot$
• $\mathbf{I_2} = \{ S \to L \cdot = R, \quad R \to L \cdot \}$

Step 3: Analyze Conflict in State $I_2$ In state $I_2$:

1. Item $S \to L \cdot = R$ is a shift item on terminal =. It demands Shift on column =.
2. Item $R \to L \cdot$ is a complete reduce item for production $R \to L$.
   • In SLR(1), reduce $R \to L$ is placed in all columns belonging to $\text{FOLLOW}(R)$:

$$\text{FOLLOW}(R) = \{ =, \$ \}$$

• Because = belongs to $\text{FOLLOW}(R)$, the reduction $R \to L$ MUST be placed in column =!

Table Population for Cell $\text{ACTION}[I_2, =]$:

$$\text{ACTION}[I_2, =] = \{ \text{Shift}, \quad \text{Reduce } R \to L \}$$

An unresolved Shift/Reduce Conflict exists in cell $[I_2, =]$!
Even though this grammar is completely unambiguous, it is NOT SLR(1).

Root Cause of SLR(1) Failure: $\text{FOLLOW}(R)$ contains = because of the valid rightmost derivation $S \Rightarrow L = R \Rightarrow R = R$. However, in state $I_2$, the stack has observed prefix $L$. In this specific context, an = can only be legally followed if $L$ remains on the left side of the assignment; an reduction $R \to L$ at this position would create an invalid prefix $R =$. Because SLR(1) uses global follow sets rather than context-specific lookaheads, it cannot see this distinction.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Does SLR(1) have more states or a larger parsing table than LR(0)?"
Key Focus Points:

• Strict Rule: No. The number of states and the dimensions of the parsing table in SLR(1) are identically equal to those in LR(0).
• Reason: Both parsers use the exact same canonical collection of LR(0) items. SLR(1) differs solely in filtering out which cells receive reduction entries.

Question 2: "If a grammar has an $\epsilon$-production, can it be SLR(1)?"
Key Focus Points:

• Yes. Grammars with $\epsilon$-productions can certainly be SLR(1), provided that the empty reduction item $A \to \cdot$ does not conflict with shift items or other reduce items under lookaheads in $\text{FOLLOW}(A)$.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Assuming that an unambiguous grammar is always SLR(1).
Answer: Classic trap. Unambiguity does not guarantee SLR(1) compatibility. The assignment grammar ($S \to L = R \mid R$) is unambiguous and has a unique parse tree for every valid string, yet it fails SLR(1) because global FOLLOW sets are too coarse.

Trap 2: Claiming that SLR(1) eliminates all Shift/Reduce conflicts.
Answer: False. SLR(1) eliminates an S/R conflict if and only if the shift terminal $a$ does NOT belong to the FOLLOW set of the reducing non-terminal ($a \notin \text{FOLLOW}(B)$). If $a \in \text{FOLLOW}(B)$, the S/R conflict survives.

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic5.2 LR(0) Parsing: Canonical Collection of Items, Closure, GOTO & Table ConstructionNext Topic →5.4 CLR(1) & LALR(1) Parsing: LR(1) Items, State Merging & Parser Hierarchy