Overview
LR(1) item-set construction computes closure and goto sets over dotted grammar productions plus one-symbol lookahead. The resulting automaton drives canonical LR parsing tables.
CoreSource checked
LR(1) Item Set Construction
Builds canonical LR(1) parser states from grammar items with lookahead symbols.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Parsing
- Difficulty
- Intermediate
- Family
- Parser Generation
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
lr parser constructionparser generationautomata statesparsing
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when full LR(1) precision is needed and table size is acceptable.
- Use when grammar conflicts need clearer lookahead context than SLR or LALR provides.
When Not to Use
- Avoid when table size would be too large for the grammar.
- Avoid when a simpler precedence parser or recursive-descent parser is sufficient.
What It Does
- Computes closure for LR(1) items
- Moves dots over grammar symbols with goto transitions
- Builds canonical parser states with lookahead context
Use Cases
- Canonical LR parser generators
- Diagnosing shift-reduce and reduce-reduce conflicts
- Teaching bottom-up parsing with explicit lookahead
Inputs
- Context-free grammar productions G = (V, Σ, R, S)
- Lookahead token set and FIRST/FOLLOW tables
Outputs
- Canonical collection of LR(1) item sets and automaton transitions
- ACTION and GOTO parsing tables
Pseudocode
- 1.Augment the grammar with a new start production
- 2.Create the initial LR(1) item and compute its closure
- 3.For each unprocessed item set and grammar symbol, compute goto
- 4.Add nonempty goto sets as parser states
- 5.Repeat until no new item sets appear
- 6.Use the states to build action and goto tables
Canonical Example
- Input
- grammar E -> E + T | T with end-marker lookahead
- Output
- canonical LR(1) item sets and goto transitions
- Explanation
- Closure adds productions expected after the dot and carries lookahead symbols into reduce contexts.
Implementation Notes
- Represent items as production, dot position, and lookahead.
- Cache closure and goto results for repeatable state construction.
- Report conflicts with the item set and lookahead that caused them.
Common Pitfalls
- Computing lookahead propagation incorrectly creates wrong reduce actions.
- Failing to canonicalize item sets creates duplicate states.
- Confusing LR(0), SLR, LALR, and LR(1) item semantics leads to table errors.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow closing and transitioning item sets with one-symbol lookahead on a small lr parser construction example.
Input:ABABABCABAB
Window:ABAB
Step 1 of 6: Augment the grammar with a new start production
parsing-mechanismNotes
LR(1) precision reduces conflicts but can produce many parser states.
Sources (2)
What each reference supports for this entry.
Knuth LR Parsing
PaperOriginal LR parsing reference for LR item sets and deterministic bottom-up parsing.
Open sourceCompilers: Principles, Techniques, and Tools
BookCompiler textbook support for LR(1) Item Set Construction's grammar analysis, parser construction, and implementation constraints.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageLR(1) closure uses FIRST-style lookahead propagation.
GeneralizesLALR Parsing
LALR parsing merges compatible LR(1) states to reduce table size.
Related Algorithms
Tags
Parsing