Overview
LR Parsing reads tokens left to right and reduces recognized symbol sequences into grammar rules.
CoreSource checked
LR Parsing
Parses input bottom-up with shift and reduce actions.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Parsing
- Difficulty
- Advanced
- Family
- Bottom-Up Parsing
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 8
- Code example
- Not ready
- Visualization
- Ready
- Aliases
- LR Parser
Core Concepts
parse statebottom-up reductiongrammar productionstack statebottom-up parsingtoken streamgrammar rule
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)
When to Use
- Use LR Parsing when you need to shifts tokens onto a stack.
- Use it for programming language parsers with inputs like token stream.
- Use it when text or tokens must be turned into a reliable structured representation.
- Use it when the Bottom-Up Parsing tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when the grammar is ambiguous or left-recursive in ways the parser cannot handle.
- Avoid it when the required output is not parse tree.
What It Does
- Shifts tokens onto a stack
- Reduces stack symbols into grammar productions
Use Cases
- Programming language parsers
- Parser generators
- Complex grammar handling
Inputs
- Token stream
- LR parse tables
Outputs
- Parse tree
- Syntax error
Pseudocode
- 1.Start with an initial parser state
- 2.Read parser action for the current state and token
- 3.Shift tokens onto the stack when requested
- 4.Reduce stack symbols by grammar rules
- 5.Accept when the start rule is complete
Canonical Example
- Input
- tokens = ['2', '+', '3', '*', '4']
- Output
- structured expression tree or evaluated result
- Explanation
- LR Parsing: The parser uses grammar or precedence rules to recover structure from tokens.
Implementation Notes
- Keep the input contract explicit: Token stream; LR parse tables.
- Keep tokenization separate from parsing unless the algorithm explicitly combines them.
- Keep lexical analysis separate from parsing unless the method explicitly combines them.
Common Pitfalls
- LR parsers handle a large class of deterministic context-free grammars.
- Small grammar changes can introduce ambiguity or precedence mistakes.
- Producing unclear errors that do not point to the token or rule that failed.
- Handle empty, invalid, and boundary inputs before trusting parse tree.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow tokens shifting and grammar handles reducing on a stack.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Start with an initial parser state
shift-reduce-stackNotes
LR Parsing operates in O(n) time and O(n) space within the Bottom-Up Parsing family. Often compared with LL Parsing and Operator Precedence Parsing.
Sources (1)
What each reference supports for this entry.
Compilers: Principles, Techniques, and Tools
BookCompiler construction reference for LR Parsing grammar transformation, parser construction, or syntax-tree workflow.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsCanonical LR Parsing
Parsing · Core
Canonical LR Parsing is a named variant of LR Parsing with a more specific construction or operating tradeoff.
Compare with thisHas variantsLALR Parsing
Parsing · Core
LALR parsing merges LR item sets to reduce parse table size.
Compare with thisHas variantsSLR Parsing
Parsing · Core
SLR Parsing is a named variant of LR Parsing with a more specific construction or operating tradeoff.
Compare with thisHas variantsGLR Parsing
Parsing · Specialized
GLR parsing extends LR parsing to handle nondeterminism and ambiguous grammars.
Compare with thisRelationships
View full relationship pageAlternative toLL Parsing
LR parsing handles bottom-up shift-reduce parsing, unlike top-down LL parsing.
Related Algorithms
Tags
ParsingBottom-Up ParsingGrammarStack