Overview
Parsing Expression Grammar parsing treats alternatives as ordered choices, often making grammar behavior deterministic and suitable for recursive descent or packrat parsing.
CoreSource checked
PEG Parsing
Parses text using ordered-choice grammar rules that describe one intended parse.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Parsing
- Difficulty
- Intermediate
- Family
- Grammar Parsing
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
ordered choiceparsing expressiontop-down parsememoization
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n) with memoization
Worst
Exponential without memoization in some grammars
Space
O(n * rules) with memoization
When to Use
- Use when the grammar should encode deterministic ordered choices directly.
- Use when domain-specific languages is a central requirement.
When Not to Use
- Avoid when ambiguous grammar analysis or all possible parses are required.
- Avoid when the grammar style does not match the parser's assumptions.
What It Does
- Computes grammar parsing within Grammar Parsing workloads (O(n) with memoization time, O(n * rules) with memoization space).
- Works by Parses text using ordered-choice grammar rules that describe one intended parse.
- Maintains key invariants across ordered choice, parsing expression, top-down parse.
Use Cases
- Domain-specific languages
- Configuration formats
- Expression-heavy parsers
Inputs
- Token or character stream
- PEG grammar
Outputs
- Parse tree or parse failure
Pseudocode
- 1.Start at the grammar's root expression
- 2.Try sequence, repetition, and predicate expressions recursively
- 3.For ordered choice, accept the first matching alternative
- 4.Return a parse tree when the root consumes valid input
Canonical Example
- Input
- rule = "ab" / "a", input = "ab"
- Output
- match = "ab"
- Explanation
- The first successful ordered alternative wins.
Implementation Notes
- Use memoization for packrat-style performance when rules can revisit positions.
- Separate tokenization, parse state, and error reporting.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Putting a broad alternative before a specific one can make the specific rule unreachable.
- Ambiguity, left recursion, and token boundaries can break otherwise simple parsers.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow ordered alternatives being tried left to right until one succeeds.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Start at the grammar's root expression
parse-flowNotes
Ordered choice means grammar alternative order changes the language accepted.
Sources (2)
What each reference supports for this entry.
Parsing Techniques: A Practical Guide
BookParsing reference for PEG recognition behavior, prioritized choice, and practical parser control flow.
Parsing Expression Grammars
PaperOriginal reference for PEG recognition semantics, prioritized choice, and parser behavior for parsing expression grammars.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageOften paired withPackrat Parsing
PEG parsers are often implemented with packrat memoization for linear-time recognition.
Related Algorithms
Tags
ParsingPEGTop-Down ParsingGrammar