SLR(1) Parsing Tables & Conflict Resolution
“FOLLOW-set guided reductions, Shift-Reduce (SR) and Reduce-Reduce (RR) conflict diagnosis.”
1.The Power and Conflict Taxonomy of SLR(1)
§ 3.1.The Simple LR (SLR(1)) parser significantly strengthens LR(0) by using 1 token of lookahead from the context-free grammar to guard reduction actions.
In an LR(0) parser, whenever an item is completed (A o alpha cdot), the parser unconditionally reduces on any lookahead token. This generates false conflicts whenever a shift transition is also available.
SLR(1) Resolution Principle: When in state I_k with completed item A o alpha cdot, reduction is logically permissible only if the incoming lookahead token could legitimately follow A in some valid derivation. Hence, the parser writes r_i into column a if and only if a in FOLLOW(A).
Conflict Taxonomy:
1. Shift-Reduce (SR) Conflict: The parser cannot decide whether to shift the current input token onto the stack or reduce the current stack contents using a production.
2. Reduce-Reduce (RR) Conflict: The parser identifies two different productions whose handles are both complete on top of the stack and cannot decide which production to reduce.
2. Worked Analysis: Identifying SLR(1) Shift-Reduce Conflict
Check if the shift terminal symbol appears in the FOLLOW set of the non-terminal being reduced.
Consider the classic assignment grammar:
S -> L = R | R
L -> * R | id
R -> L
Show that this grammar is NOT SLR(1) by finding the exact conflict in its canonical LR(0) items.
Step 1: Compute FOLLOW sets:
- FOLLOW(S) = {$}
- In S -> L = R: symbol '=' follows L. Also S -> R and R -> L, so FOLLOW(L) contains FOLLOW(R).
- FOLLOW(R) contains FOLLOW(S) = {} and from S -> L = R, FOLLOW(R) contains FOLLOW(S) = {}.
- Since R -> L, FOLLOW(L) contains FOLLOW(R) = {$, =}.
- Therefore, FOLLOW(R) = {, =} and FOLLOW(L) = {, =}.
Step 2: Generate State I0 and Transitions:
- I0 = CLOSURE({S' -> . S}) contains:
S' -> . S
S -> . L = R
S -> . R
L -> . * R
L -> . id
R -> . L
Step 3: Compute GOTO(I0, L) = I2:
- Advance dot past L in items containing '. L':
S -> L . = R
R -> L .
Step 4: Check for conflicts in State I2:
- Item 1: S -> L . = R (wants to SHIFT on symbol '=')
- Item 2: R -> L . (completed item, wants to REDUCE by R -> L on all symbols in FOLLOW(R))
- Does symbol '=' belong to FOLLOW(R)?
- Yes! We determined FOLLOW(R) = {$, =}.
- Therefore, on input symbol '=', State I2 has BOTH:
- Action[I2, =] = Shift
- Action[I2, =] = Reduce by R -> L
Conclusion: State I2 contains a Shift-Reduce conflict on '='. The grammar is NOT SLR(1).
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused with worked FIRST/FOLLOW and LR parsing table numericals.
Exam-oriented explanations of ambiguous grammars and parser conflicts.
University-depth treatment of the full compiler pipeline — build a real compiler.