Overview
GLR parsing splits parse stacks when conflicts occur and later merges compatible states, producing a shared parse forest when ambiguity remains.
SpecializedSource checked
GLR Parsing
Parses ambiguous or nondeterministic grammars by following multiple LR parse paths.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Parsing
- Difficulty
- Advanced
- Family
- Generalized Bottom-Up Parsing
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
parse stack splitshared packed parse forestlr itemambiguity handling
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n^3)
Worst
O(n^3)
Space
O(parse forest)
When to Use
- Use when language parsing needs parse stack split.
- Use when the input matches the assumptions behind generalized Bottom-Up Parsing.
When Not to Use
- Avoid when the grammar class does not match the parser's assumptions.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Parses ambiguous or nondeterministic grammars by following multiple LR parse paths
- Uses parse stack split and shared packed parse forest to guide the work.
- Produces parse tree.
Use Cases
- Language parsing
- Compiler front ends
- Structured text processing
Inputs
- Tokens or grammar
- Parser state
Outputs
- Parse tree
- Automaton
- Grammar table or parse result
Pseudocode
- 1.Prepare the inputs and state needed for GLR Parsing.
- 2.Apply the parse stack split step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return parse tree.
Canonical Example
- Input
- GLR Parsing input with a small representative case
- Output
- Parse tree
- Explanation
- GLR Parsing applies parse stack split to produce parse tree.
Implementation Notes
- Report errors with token position and expected grammar symbols.
- Keep the parse stack split step separate enough to test independently.
Common Pitfalls
- Ambiguity and left recursion must be handled according to the parser type.
- Forgetting to check edge cases can make GLR Parsing look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow grammar items, parser states, and consumed input as parsing progresses.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Prepare the inputs and state needed for GLR Parsing.
parsing-mechanismNotes
GLR Parsing should be used with the assumptions and tradeoffs of generalized Bottom-Up Parsing in mind.
Sources (1)
What each reference supports for this entry.
Generalized LR Parsing
BookParsing reference for generalized LR parsing, graph-structured stacks, and ambiguous context-free grammars.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofLR Parsing
GLR parsing extends LR parsing to handle nondeterminism and ambiguous grammars.
Related Algorithms
Tags
ParsingBottom-Up ParsingGrammarAmbiguous Grammar