tangledgroup Parsing Expression Grammars (PEG)
Overview
A Parsing Expression Grammar (PEG), introduced by Bryan Ford in 2004, is a recognition-based formal grammar that describes languages through rules for recognizing strings rather than generating them. Unlike context-free grammars (CFGs) where choice is nondeterministic, PEGs use ordered choice (/ or |) — the first matching alternative wins and others are discarded. This makes PEGs unambiguous by construction: every valid string has exactly one parse tree.
PEGs unify lexical analysis (tokenization) and syntactic parsing into a single grammar, eliminating the traditional lexer/parser split. They support unlimited lookahead via syntactic predicates (& and !), can express some non-context-free languages, and admit linear-time parsing through packrat memoization.
Non-regex example: {a^n b^n : n ≥ 0} is not a regular language but trivially a PEG:
start ← AB !.
AB ← ('a' AB 'b')?
Non-context-free example: {a^n b^n c^n : n ≥ 0} is provably not context-free but expressible as PEG:
S ← &(A !('a'/'b')) 'a'* B !.
A ← ('a' A 'b')?
B ← ('b' B 'c')?
PEGs are used in production by CPython (since 3.9, default from 3.10 via PEP 617), DuckDB (experimental PEG parser since v1.5), Lua (LPeg), Guile Scheme, jq, and various parser generator tools including Mouse (Java-based, limited backtracking with recursive ascent left-recursion support).
When to Use
- Designing a new programming language or DSL where grammar clarity matters
- Replacing LL(1)/LALR parsers that suffer from ambiguity, shift-reduce conflicts, or limited lookahead
- Implementing scannerless parsing where lexical rules depend on syntactic context
- Building runtime-extensible parsers (e.g., SQL dialect plugins, Wasm deployments)
- Prototyping language syntax before committing to a specific parser generator
- Resolving ambiguities like dangling else that require hand-crafted CFG workarounds
- Migrating from YACC/bison when reduce-reduce conflicts become maintenance hazards
Core Operators
| Operator | Syntax | Precedence | Description |
|---|---|---|---|
| Grouping | (e) |
5 (highest) | Parenthesized expression |
| Optional | e? or [e] |
4 | Zero or one match (greedy) |
| Zero-or-more | e* |
4 | Zero or more matches (always greedy) |
| One-or-more | e+ |
4 | One or more matches (always greedy) |
| Exact repetition | {n} |
4 | Exactly n matches (PeppaPEG) |
| Gather | s.e+ |
4 | One or more e separated by s (pegen) |
| And-predicate | &e |
3 | Succeed if e matches, consume nothing |
| Not-predicate | !e |
3 | Succeed if e fails, consume nothing |
| Cut/commit | ~ |
3 | Commit to current alternative (pegen) |
| Sequence | e1 e2 |
2 | Match e1 then e2, backtrack on failure |
| Ordered choice | e1 / e2 or e1 | e2 |
1 (lowest) | Try e1 first; if succeeds, discard e2 |
| Failure | _ or failure |
— | Always fails, matches nothing (some variants) |
Key semantics:
- Ordered choice is not commutative:
A / B≠B / A. Place longer/more-specific alternatives first. - Repetition is always greedy:
a*consumes all availableas. Unlike regex, no non-greedy mode.(a* a)always fails. - Predicates consume nothing:
&eand!eonly check — they never advance the input position. - Failure is not error: A rule returning failure means "try the next alternative", not "syntax error".
- Cut (
~): Once passed, the parser commits to the current alternative even if it later fails. Prevents backtracking past this point.
Minimal Example: Arithmetic Expressions
Idiomatic right-recursive form (no left recursion):
Expr ← Sum
Sum ← Product (('+' / '-') Product)*
Product ← Value (('*' / '/') Value)*
Value ← [0-9]+ / '(' Expr ')'
Operator precedence is encoded through layered rules. The * repetition produces a flat list — left-associativity must be imposed during AST construction.
Left-recursive form with pegen grammar actions (CPython):
expr[expr_ty]:
| l=expr '+' r=term { _Py_BinOp(l, Add, r, EXTRA) }
| t=term { t }
term[expr_ty]:
| l=term '*' r=factor { _Py_BinOp(l, Mult, r, EXTRA) }
| f=factor { f }
Named captures (l=, r=) bind subexpression results. The {...} action (Python mode) or #{...}# (C mode) builds the AST node directly, eliminating intermediate parse trees. Each left-recursion iteration wraps the previous result as the left operand, producing a properly left-associative tree during parsing.
Advanced Topics
Core Concepts: Formal definitions, operator semantics, precedence, PEG vs CFG differences, midpoint problem, self-describing meta-grammar → Core Concepts
Parsing Algorithms: Recursive descent infrastructure, packrat parsing with memoization, selective caching, tokenizer integration, context manager approach → Parsing Algorithms
Left Recursion and Associativity: The left recursion problem, idiomatic workarounds, Ford/Warth fixed-point algorithm, expression clusters, associativity control → Left Recursion and Associativity
Grammar Design Patterns: Mindset shift from EBNF, ordered choice consequences (eager matching, subsumed alternatives), whitespace strategies, soft vs hard keywords → Grammar Design Patterns
Error Handling and Actions: Error location problem, YACC all-or-nothing behavior, two-pass recovery, annotated recovery rules, semantic actions (Python/C modes) → Error Handling and Actions
Practical Implementations: CPython pegen (PEP 617, LL(1) workarounds eliminated), DuckDB extensible parser, LPeg (Lua, parser combinators), PeppaPEG (ANSI C), peg/leg, Guile (ice-9 peg) → Practical Implementations
PEG vs Alternatives: CFG comparison, regex comparison, advantages and disadvantages summary → PEG vs Alternatives
Advanced Topics: Pika bottom-up parsing, runtime-extensible grammars, unified scannerless parsing, expression clusters, theory and undecidability → Advanced Topics