SLR(1) Parsing
You'll learn how SLR(1) parsing resolves ambiguities in LR(0) tables using FOLLOW sets.
The Problem with Pure LR(0)
When you built your LR(0) parsing tables, you may have encountered reduce-reduce conflicts — situations where multiple reductions are possible in the same state. Pure LR(0) parsing doesn't know which reduction to choose because it only looks at the current state, not the next input token.
How SLR(1) Adds Intelligence
SLR(1) stands for "Simple LR with 1 token lookahead." It refines LR(0) by asking: "Should I reduce by this production right now?"
Here's the key insight: only perform a reduction if the next input token could legally follow the non-terminal you're reducing to.
In other words, when you have a complete item like A → β· in some state, you should only reduce using that production if the lookahead token is in FOLLOW(A).
The Decision Rule
Instead of blindly reducing whenever you see a complete item:
- Check your lookahead token
- Only reduce by
A → βif the lookahead ∈ FOLLOW(A) - If the lookahead isn't in FOLLOW(A), you know that reduction path is wrong
This eliminates many conflicts because different productions often have different FOLLOW sets.
An Analogy
Think of FOLLOW sets as a "permission slip." Just because you can complete a phrase (you've seen all its parts) doesn't mean you should — you need permission from what comes next. FOLLOW sets provide that permission.
Key Takeaway: SLR(1) parsing resolves LR(0) reduce conflicts by only allowing reductions when the next input token belongs to the FOLLOW set of the non-terminal being reduced.