LR(1) Items and Lookahead
What you'll learn: How adding lookahead symbols to LR(0) items enables the parser to make more precise, conflict-free parsing decisions.
The Problem with LR(0)
In LR(0) parsing, items track where you are in recognizing a production, but they don't look ahead at what's coming next. This causes shift-reduce or reduce-reduce conflicts when the automaton can't decide which action to take based solely on the stack state.
What is an LR(1) Item?
An LR(1) item extends the LR(0) item by adding a lookahead symbol—a terminal that could legally follow this production. It has the form:
[A → α·β, a]
Where:
A → α·βis the core LR(0) item (dot shows parsing position)ais the lookahead symbol (what can legally come after we reduce byA → αβ)
Analogy: If LR(0) items are like reading a recipe step-by-step, LR(1) items are like reading the recipe while checking the next ingredient to make sure you're on the right path.
Why Lookahead Helps
The lookahead symbol prevents spurious reductions. You only reduce by A → αβ when:
- The dot is at the end (
A → αβ·) - AND the next input symbol matches the lookahead
a
This eliminates many conflicts that plague SLR(1) and LR(0) parsers, because you have more context about whether a reduction is actually valid in this specific situation.
Computing Lookaheads
When building LR(1) item sets, lookaheads propagate through the closure and goto operations, tracking which terminals can legally follow each production in each state.
Key Takeaway: LR(1) items augment parsing items with lookahead symbols, allowing the parser to defer decisions until seeing the next token, dramatically reducing conflicts and enabling correct parsing of a broader class of grammars.