vault

The PEG Parser

15 min read

The PEG Parser

Since Python 3.9, CPython parses your source code with a Parsing Expression Grammar (PEG) parser generated from Grammar/python.gram, replacing the hand-tuned LL(1) parser that had served since the language’s beginning. The change was specified in PEP 617, made the default in 3.9, and the old parser was deleted outright in 3.10. The motivation was not speed — both parsers are comparable — but expressiveness: an LL(1) grammar can only look one token ahead and cannot express left recursion, which forced years of “grammar hacks” where the grammar accepted more than the language allowed and a later pass rejected the surplus. A PEG parser lifts those restrictions, letting the grammar itself be the precise, single source of truth for Python’s syntax — and, as a bonus, enabling dramatically better syntax-error messages.

This note covers how text becomes a tree. The companion notes describe the Python Tokenizer that produces the token stream this parser consumes, and the Python Abstract Syntax Tree that this parser produces as output. For where parsing sits in the whole pipeline, see CPython Compilation Pipeline.

Mental Model

The cleanest way to think about a PEG parser is as a recursive-descent parser whose backtracking is made safe and fast by a memo cache. Each grammar rule becomes a function. A rule succeeds (consuming some input tokens and returning a result) or fails (consuming nothing). Where a context-free grammar’s | means “any of these alternatives, figure out which,” PEG’s | is an ordered choice: try the first alternative; only if it fails, fall through to the second, and so on, in written order. The first alternative that matches wins, full stop — there is no ambiguity to resolve, because “if a string parses, it has exactly one valid parse tree” (PEP 617).

flowchart TD
    SRC["Source text<br/>x = a + b * 2"] --> TOK[["Tokenizer<br/>(Python Tokenizer)"]]
    TOK -->|"token stream<br/>NAME '=' NAME '+' NAME '*' NUMBER NEWLINE"| PARSE
    subgraph PARSE["PEG parser — parser.c, generated from python.gram"]
        RULE["Each rule = a C function<br/>e.g. sum_rule(), term_rule()"]
        MEMO[("memo cache<br/>(rule, pos) → result")]
        RULE <-->|"on backtrack:<br/>reuse cached result"| MEMO
        RULE -->|"action block { ... }<br/>calls _PyAST_BinOp(...)"| AST
    end
    AST["Abstract Syntax Tree<br/>Module(body=[Assign(...)])"]

Figure: the parser sits between the tokenizer and the AST. Each grammar rule compiles to a C function; ordered-choice alternatives are tried in order, backtracking is made cheap by the memo cache keyed on (rule, token-position), and each successful alternative runs an action that constructs an AST node. The insight: the grammar file and the tree it builds are now one artifact — there is no intermediate concrete syntax tree and no second “validate the surplus” pass.

Why LL(1) Had To Go

The old parser was LL(1): it scanned Left-to-right, produced a Leftmost derivation, and used exactly 1 token of lookahead. That single-token horizon is the root of every limitation PEP 617 cites.

Grammar/code mismatch from limited lookahead. Because LL(1) must decide which alternative to take after seeing only one token, the grammar frequently could not be written to mean what Python actually allows. The canonical example is the named expression (the walrus :=). The natural rule namedexpr_test: [NAME ':='] test is not LL(1) — seeing a NAME, the parser cannot tell whether a := follows. So the real grammar was written loosely as namedexpr_test: test [':=' test], accepting many constructs that are not legal walrus targets, and a separate later pass rejected the illegal ones. The parser, which is supposed to define the syntax, no longer did; correctness was smeared across the parser plus ad-hoc validation code (PEP 617).

No left recursion. A grammar rule is left-recursive when it can call itself without first consuming a token, e.g. expr: expr '+' term | term. An LL(1) recursive-descent parser would recurse into expr forever and stack-overflow, so left recursion is forbidden. The workaround is to rewrite the rule iteratively as expr: term ('+' term)*. That parses, but it flattens the tree — ('+' term)* is just a list — losing the natural left-associative nesting that a + b + c should have ((a + b) + c). The intended associativity then had to be reconstructed in post-processing (PEP 617).

Intermediate concrete syntax tree (CST) overhead. The LL(1) parser first built a CST — a verbose tree mirroring the grammar exactly, including long chains of single-child nodes (expr → term → factor → power → atom for a bare name) — and only then walked the CST to build the AST that the rest of the compiler actually wants. The CST was pure overhead: memory for nodes nobody downstream consumed (PEP 617).

Resolved (2026-06-01)

Confirmed against PEP 617’s “Rationale”: its actual list of LL(1) problems is exactly four — “Some rules are not actually LL(1)”, “Complicated AST parsing”, “Lack of left recursion”, and “Intermediate parse tree” — which the three subsections above cover (the AST-parsing complication is folded into the grammar/code-mismatch discussion). Python 2’s print >>file, x redirect is not an LL(1) limitation: print-as-statement was removed by PEP 3105 in Python 3.0, a statement-grammar change unrelated to lookahead. The genuine PEG win in this area is the improved error message for print x (see “Error Messages” below), not a parsing-capability gap.

How a PEG Parser Works

Ordered choice and no ambiguity. In a context-free grammar, rule: A | B | C is a set — the parser must deduce which member produced the input, the source of grammar ambiguity and the reason LL/LR parsers need elaborate conflict resolution. In PEG, the same line is an ordered instruction: “the parser will check if the first alternative succeeds and only if it fails will it continue with the second or the third one, in the order in which they are written” (PEP 617). This makes the grammar deterministic by construction — but it also means alternative order is semantically load-bearing: swapping two alternatives can change what parses.

Backtracking. When an alternative partway through a rule fails, the parser backtracks: it resets the token position to where the alternative began and tries the next one. Naive backtracking is the recursive-descent parser’s classic weakness — it can re-parse the same sub-string exponentially many times.

Memoization — but selective, not full packrat. PEG’s textbook fix is packrat parsing: memoize the result of every (rule, position) pair so each is computed at most once, trading memory for a linear-time guarantee. CPython does not memoize everything. It memoizes (a) all left-recursive rules (required for the left-recursion algorithm below to terminate), and (b) rules the grammar author has explicitly tagged with the (memo) marker — performance-sensitive rules reached down many backtracking paths. You can see these markers directly in Grammar/python.gram: simple_stmt[stmt_ty] (memo):, block[asdl_stmt_seq*] (memo):, factor[expr_ty] (memo):, type_param[type_param_ty] (memo):, and the pattern-matching rules closed_pattern (memo) / star_pattern (memo). So CPython is best described as a recursive-descent PEG parser with selective memoization, not a full packrat parser.

Left recursion via the memo cache. PEG normally also forbids left recursion, but CPython supports it (so sum: sum '+' term can be written directly). The technique, “similar to the one described in Medeiros et al. but using the memoization cache instead of static variables” (PEP 617), seeds the memo entry for the left-recursive rule with a failure, then re-evaluates the rule repeatedly, each time letting it consume one more '+' term, growing the match until it stops getting longer. Because the parse is grown left-to-right and re-nested at each step, the resulting tree is correctly left-associative — a + b + c becomes BinOp(BinOp(a, +, b), +, c) with no post-processing. Both direct and indirect (mutual) left recursion are handled.

No separate grammar class. Crucially, PEG imposes no LL/LR-style restriction on the grammar. There is no “is this grammar LL(1)?” check to satisfy, no FIRST/FOLLOW sets, no shift/reduce conflicts. If you can write the rule, the generator can build a parser for it. That is the freedom that let the walrus rule, structural pattern matching (match/case, 3.10), and other features be expressed precisely in the grammar.

The pegen Generator and python.gram

CPython does not ship a hand-written parser. It ships a grammar file, Grammar/python.gram, and a parser generator, pegen, that compiles the grammar into C. The header comment of python.gram lays out the metasyntax (verbatim):

# * Strings with double quotes (") denote SOFT KEYWORDS
# * Strings with single quotes (') denote KEYWORDS
# * Upper case names (NAME) denote tokens in the Grammar/Tokens file
# * Rule names starting with "invalid_" are used for specialized syntax errors

The operators, from the same header and from the language reference grammar page:

  • e1 e2 — sequence: match e1, then e2.
  • e1 | e2 — ordered choice (see above).
  • ( e ) — grouping, so operators can apply to a sub-expression.
  • [ e ] or e? — optional.
  • e* / e+ — zero-or-more / one-or-more.
  • s.e+ — one-or-more e separated by s, with the separator dropped from the tree; “otherwise identical to (e (s e)*).”
  • &e — positive lookahead: succeed if e parses, without consuming input.
  • !e — negative lookahead: fail if e parses, without consuming input.
  • ~ — the cut: “commit to the current alternative, even if it fails to parse.” Once the parser passes a ~, it will not backtrack out of this alternative; if the rest fails, the whole rule fails. Cuts are used for speed (prune dead backtracking paths) and for better errors (commit early so the failure points at the right place). The reference notes “Python mainly uses cuts for optimizations or improved error messages.”

A rule may declare a return type in brackets: rule_name[return_type]: .... In C this becomes the function’s return type; if omitted, the C function returns void *.

Each alternative ends with an action in { ... }: a snippet of C (or Python, for the meta-grammar) evaluated when the alternative matches, whose value becomes the rule’s result. Actions are how the parser builds AST nodes directly, with no intermediate CST. Here are the four top-level start rules, verbatim from python.gram:

file[mod_ty]: a=[statements] ENDMARKER { _PyPegen_make_module(p, a) }
interactive[mod_ty]: a=statement_newline { _PyAST_Interactive(a, p->arena) }
eval[mod_ty]: a=expressions NEWLINE* ENDMARKER { _PyAST_Expression(a, p->arena) }
func_type[mod_ty]: '(' a=[type_expressions] ')' '->' b=expression NEWLINE* ENDMARKER { _PyAST_FunctionType(a, b, p->arena) }

Line-by-line: file declares return type mod_ty (the C type of a mod AST node — see Python Abstract Syntax Tree). It binds a to optional statements, then requires the ENDMARKER token (end of input), then runs the action _PyPegen_make_module(p, a) to build a Module node. The other three are the entry points for eval() (a single expression), interactive REPL input, and PEP 484 function-type comments. The C trailer at the top of python.gram dispatches to one of file_rule/interactive_rule/eval_rule/func_type_rule based on p->start_rule.

The real prize is the left-recursive arithmetic rules — impossible under LL(1), trivial here (verbatim):

sum[expr_ty]:
    | a=sum '+' b=term { _PyAST_BinOp(a, Add, b, EXTRA) }
    | a=sum '-' b=term { _PyAST_BinOp(a, Sub, b, EXTRA) }
    | term

term[expr_ty]:
    | a=term '*' b=factor { _PyAST_BinOp(a, Mult, b, EXTRA) }
    | a=term '/' b=factor { _PyAST_BinOp(a, Div, b, EXTRA) }
    | a=term '//' b=factor { _PyAST_BinOp(a, FloorDiv, b, EXTRA) }
    | a=term '%' b=factor { _PyAST_BinOp(a, Mod, b, EXTRA) }

sum calls itself in its first two alternatives (left recursion) and constructs a BinOp(left, op, right) node via _PyAST_BinOp. EXTRA is a macro expanding to the source-location arguments (lineno, col_offset, end_lineno, end_col_offset, arena) that every node carries — this is how the parser attaches positions to nodes (see Python Abstract Syntax Tree for what those attributes mean). The split into sum → term → factor is exactly operator precedence: * and / bind tighter than + and - because term is reached inside sum. Because sum is left-recursive, a - b - c parses as (a - b) - c — correct left associativity, for free.

Generating and Building the Parser

The generator lives in the source tree at Tools/peg_generator/ (the pegen package), with C-runtime support in Parser/pegen.c. When a developer changes python.gram, they regenerate the parser with make regen-pegen, whose recipe (from Makefile.pre.in, verbatim) is:

regen-pegen:
	PYTHONPATH=$(srcdir)/Tools/peg_generator $(PYTHON_FOR_REGEN) -m pegen -q c \
		$(srcdir)/Grammar/python.gram \
		$(srcdir)/Grammar/Tokens \
		-o $(srcdir)/Parser/parser.c.new
	$(UPDATE_FILE) --create $(srcdir)/Parser/parser.c $(srcdir)/Parser/parser.c.new

It runs python -m pegen -q c over python.gram (plus Grammar/Tokens, the token list) and writes Parser/parser.c. The generated file is checked into the repository and its first line announces its provenance: // @generated by pegen from python.gram. So the build artifact is C source — there is no grammar interpretation at runtime; CPython runs compiled parser.c. (pegen is bootstrapped: an early Python build of the generator builds the C parser, but the generator itself is just a Python package.) The _PyPegen_* and _PyAST_* functions the actions call are runtime helpers and AST constructors compiled alongside.

Error Messages — What PEG Enabled

The single most visible payoff of PEG for everyday users is better SyntaxError messages, made possible by the invalid_ rule convention. The python.gram header explains the mechanism precisely (verbatim):

# * Rule names starting with "invalid_" are used for specialized syntax errors
#     - These rules are NOT used in the first pass of the parser.
#     - Only if the first pass fails to parse, a second pass including the invalid
#       rules will be executed.
#     - If the parser fails in the second phase with a generic syntax error, the
#       location of the generic failure of the first pass will be used (this avoids
#       reporting incorrect locations due to the invalid rules).

So CPython parses twice on error: a fast first pass with only the valid grammar; and, only if that fails, a second pass that also tries invalid_ rules whose actions raise targeted, human-readable errors. The classic example is the Python-2-print-statement helper (verbatim):

invalid_legacy_expression:
    | a=NAME !'(' b=star_expressions {
        _PyPegen_check_legacy_stmt(p, a) ? RAISE_SYNTAX_ERROR_KNOWN_RANGE(a, b,
            "Missing parentheses in call to '%U'. Did you mean %U(...)?", a->v.Name.id, a->v.Name.id) : NULL}

When someone writes print x (a NAME not followed by (, then more expression), this rule fires on the second pass and produces Missing parentheses in call to 'print'. Did you mean print(...)? instead of a bare invalid syntax. The RAISE_SYNTAX_ERROR_KNOWN_RANGE helper attaches the error to the exact token span a..b, which is why modern CPython underlines the offending region with carets. Dozens of such invalid_ rules exist (e.g. invalid_arguments raises “Generator expression must be parenthesized”), each a precise diagnostic the LL(1) parser, lacking arbitrary lookahead and a clean two-pass structure, could not easily produce.

Performance and Memory

PEG’s reputation for memory bloat (full packrat caches every position) does not bite CPython badly, because of selective memoization and because the parser builds the AST directly instead of a CST. PEP 617’s benchmarks: parsing 100,000 lines of expressions and compiling to bytecode took the new parser 1.28 s / 681 MiB versus the old parser’s 1.44 s / 836 MiB — the new parser was faster and used less memory there. On the full Python 3.8 standard library (1,641 files, ~749K lines), throughput was comparable (~227,861 vs ~222,620 lines/sec), and PEP 617 characterizes peak memory as “about 10% more” in some cases — “acceptable.” The headline: PEG did not make parsing slower, despite the common assumption that packrat parsing trades speed for memory.

Timeline and Removal of the Old Parser

PEP 617 staged the migration to avoid disruption:

  • Python 3.9 — the PEG parser shipped and became the default. A command-line flag and an environment variable let you fall back to the old LL(1) parser (PEP 617). During 3.9, no new grammar feature requiring PEG was added, so both parsers accepted the same language.
  • Python 3.10 — the old parser was removed, along with its command-line flag, environment variable, and the long-deprecated parser standard-library module. PEG became the only parser, and new syntax that PEG enables (structural pattern matching, match/case) shipped in this release.

From 3.10 onward there is no LL(1) parser to fall back to; Grammar/python.gram is the definitive, executable specification of Python’s syntax.

Common Misunderstandings

“CPython is a packrat parser.” Only partly. It uses packrat-style memoization selectively — left-recursive rules plus (memo)-tagged rules — not on every (rule, position) pair. Describing it as “full packrat” overstates the memory cost and misreads the source.

“PEG was adopted for speed.” No. PEP 617’s rationale is expressiveness and maintainability (one precise grammar, no surplus-rejecting passes). The performance was merely shown to be no worse; the small speedups in some benchmarks are incidental.

“Alternative order doesn’t matter.” It is decisive. PEG’s ordered choice means A | B and B | A can parse the same input differently (or one can shadow the other). This is why the python.gram header warns that “the order of the alternatives involving invalid rules matter.”

“The grammar is interpreted at runtime.” No. pegen compiles python.gram to C (Parser/parser.c) at build time; the running interpreter executes compiled code, not the grammar text.

See Also

Graph View

Backlinks