Canonical LR(1) Parsing
What you'll learn: How to build the most powerful deterministic bottom-up parser by incorporating full lookahead information into every state.
The Core Idea
Canonical LR(1) parsing extends what you learned about LR(1) items by constructing a complete automaton where every state tracks all possible lookahead symbols. Unlike SLR(1), which computes lookahead globally using FOLLOW sets, Canonical LR(1) computes lookahead locally for each item in each state. This precision eliminates many conflicts that SLR(1) cannot resolve.
Think of it like having a GPS that doesn't just know your destination, but also knows exactly which turn comes next from your current position. The automaton becomes larger, but far more accurate.
Building the Full LR(1) Automaton
Each state contains LR(1) items of the form [A → α·β, a], where a is a lookahead token. When you build the automaton:
- Start with
[S' → ·S, $](the augmented start production with end-marker lookahead) - Compute closure by adding items for all non-terminals after the dot, calculating their specific lookahead using FIRST sets
- Compute goto transitions by advancing the dot and taking closure again
- Each state may have many more items than LR(0) or SLR(1), because the same production with different lookaheads creates distinct items
The result is an automaton with maximum parsing power among deterministic LR techniques—it accepts all deterministic context-free languages.
The Trade-off
Canonical LR(1) automatons can be very large—potentially exponentially more states than SLR(1). This is why LALR(1) parsers (which merge compatible states) are often preferred in practice despite being slightly less powerful.
Key Takeaway: Canonical LR(1) parsing builds the complete automaton with precise per-item lookahead, achieving maximum deterministic parsing power at the cost of potentially many more states.