Guide to the parser

Abstract

The Parser in CPython is currently a PEG (Parser Expression Grammar) parser. The first version of the parser used to be an LL(1) based parser that was one of the oldest parts of CPython implemented before it was replaced by PEP 617. In particular, both the current parser and the old LL(1) parser are the output of a parser generator. This means that the way the parser is written is by feeding a description of the Grammar of the Python language to a special program (the parser generator) which outputs the parser. The way the Python language is changed is therefore by modifying the grammar file and developers rarely need to interact with the parser generator itself other than use it to generate the parser.

How PEG parsers work

A PEG (Parsing Expression Grammar) grammar (like the current one) differs from a context-free grammar in that the way it is written more closely reflects how the parser will operate when parsing it. The fundamental technical difference is that the choice operator is ordered. This means that when writing:

rule: A | B | C

a context-free-grammar parser (like an LL(1) parser) will generate constructions that given an input string will deduce which alternative (A, B or C) must be expanded, while a PEG 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. This makes the choice operator not commutative.

Unlike LL(1) parsers, PEG-based parsers cannot be ambiguous: if a string parses, it has exactly one valid parse tree. This means that a PEG-based parser cannot suffer from the ambiguity problems that can arise with LL(1) parsers and with context-free grammars in general.

PEG parsers are usually constructed as a recursive descent parser in which every rule in the grammar corresponds to a function in the program implementing the parser and the parsing expression (the “expansion” or “definition” of the rule) represents the “code” in said function. Each parsing function conceptually takes an input string as its argument, and yields one of the following results:

• A “success” result. This result indicates that the expression can be parsed by that rule and the function may optionally move forward or consume one or more characters of the input string supplied to it.

• A “failure” result, in which case no input is consumed.

Notice that “failure” results do not imply that the program is incorrect, nor do they necessarily mean that the parsing has failed. Since the choice operator is ordered, a failure very often merely indicates “try the following option”. A direct implementation of a PEG parser as a recursive descent parser will present exponential time performance in the worst case, because PEG parsers have infinite lookahead (this means that they can consider an arbitrary number of tokens before deciding for a rule). Usually, PEG parsers avoid this exponential time complexity with a technique called “packrat parsing” [1] which not only loads the entire program in memory before parsing it but also allows the parser to backtrack arbitrarily. This is made efficient by memoizing the rules already matched for each position. The cost of the memoization cache is that the parser will naturally use more memory than a simple LL(1) parser, which normally are table-based.

Key ideas

Important

Don’t try to reason about a PEG grammar in the same way you would to with an EBNF or context free grammar. PEG is optimized to describe how input strings will be parsed, while context-free grammars are optimized to generate strings of the language they describe (in EBNF, to know if a given string is in the language, you need to do work to find out as it is not immediately obvious from the grammar).

• Alternatives are ordered ( A | B is not the same as B | A ).

• If a rule returns a failure, it doesn’t mean that the parsing has failed, it just means “try something else”.

• By default PEG parsers run in exponential time, which can be optimized to linear by using memoization.

• If parsing fails completely (no rule succeeds in parsing all the input text), the PEG parser doesn’t have a concept of “where the SyntaxError is”.

Consequences of the ordered choice operator

Although PEG may look like EBNF, its meaning is quite different. The fact that in PEG parsers alternatives are ordered (which is at the core of how PEG parsers work) has deep consequences, other than removing ambiguity.

If a rule has two alternatives and the first of them succeeds, the second one is not attempted even if the caller rule fails to parse the rest of the input. Thus the parser is said to be “eager”. To illustrate this, consider the following two rules (in these examples, a token is an individual character):

first_rule:  ( 'a' | 'aa' ) 'a'
second_rule: ('aa' | 'a'  ) 'a'

In a regular EBNF grammar, both rules specify the language {aa, aaa} but in PEG, one of these two rules accepts the string aaa but not the string aa. The other does the opposite – it accepts the string aa but not the string aaa. The rule ('a'|'aa')'a' does not accept aaa because 'a'|'aa' consumes the first a, letting the final a in the rule consume the second, and leaving out the third a. As the rule has succeeded, no attempt is ever made to go back and let 'a'|'aa' try the second alternative. The expression ('aa'|'a')'a' does not accept aa because 'aa'|'a' accepts all of aa, leaving nothing for the final a. Again, the second alternative of 'aa'|'a' is not tried.

Caution

The effects of ordered choice, such as the ones illustrated above, may be hidden by many levels of rules.

For this reason, writing rules where an alternative is contained in the next one is in almost all cases a mistake, for example:

my_rule:
    | 'if' expression 'then' block
    | 'if' expression 'then' block 'else' block

In this example, the second alternative will never be tried because the first one will succeed first (even if the input string has an 'else' block that follows). To correctly write this rule you can simply alter the order:

my_rule:
    | 'if' expression 'then' block 'else' block
    | 'if' expression 'then' block

In this case, if the input string doesn’t have an 'else' block, the first alternative will fail and the second will be attempted without said part.

Syntax

The grammar consists of a sequence of rules of the form:

rule_name: expression

Optionally, a type can be included right after the rule name, which specifies the return type of the C or Python function corresponding to the rule:

rule_name[return_type]: expression

If the return type is omitted, then a void * is returned in C and an Any in Python.

Grammar expressions

# comment

Python-style comments.

e1 e2

Match e1, then match e2.

rule_name: first_rule second_rule

e1 | e2

Match e1 or e2.

The first alternative can also appear on the line after the rule name for formatting purposes. In that case, a | must be used before the first alternative, like so:

rule_name[return_type]:
    | first_alt
    | second_alt

( e )

Match e.

rule_name: (e)

A slightly more complex and useful example includes using the grouping operator together with the repeat operators:

rule_name: (e1 e2)*

[ e ] or e?

Optionally match e.

rule_name: [e]

A more useful example includes defining that a trailing comma is optional:

rule_name: e (',' e)* [',']

e*

Match zero or more occurrences of e.

rule_name: (e1 e2)*

e+

Match one or more occurrences of e.

rule_name: (e1 e2)+

s.e+

Match one or more occurrences of e, separated by s. The generated parse tree does not include the separator. This is otherwise identical to (e (s e)*).

rule_name: ','.e+

&e

Succeed if e can be parsed, without consuming any input.

!e

Fail if e can be parsed, without consuming any input.

An example taken from the Python grammar specifies that a primary consists of an atom, which is not followed by a . or a ( or a [:

primary: atom !'.' !'(' !'['

~

Commit to the current alternative, even if it fails to parse (this is called the “cut”).

rule_name: '(' ~ some_rule ')' | some_alt

In this example, if a left parenthesis is parsed, then the other alternative won’t be considered, even if some_rule or ) fail to be parsed.

Left recursion

PEG parsers normally do not support left recursion but CPython’s parser generator implements a technique similar to the one described in Medeiros et al. [2] but using the memoization cache instead of static variables. This approach is closer to the one described in Warth et al. [3]. This allows us to write not only simple left-recursive rules but also more complicated rules that involve indirect left-recursion like:

rule1: rule2 | 'a'
rule2: rule3 | 'b'
rule3: rule1 | 'c'

and “hidden left-recursion” like:

rule: 'optional'? rule '@' some_other_rule

Variables in the grammar

A sub-expression can be named by preceding it with an identifier and an = sign. The name can then be used in the action (see below), like this:

rule_name[return_type]: '(' a=some_other_rule ')' { a }

Grammar actions

To avoid the intermediate steps that obscure the relationship between the grammar and the AST generation the PEG parser allows directly generating AST nodes for a rule via grammar actions. Grammar actions are language-specific expressions that are evaluated when a grammar rule is successfully parsed. These expressions can be written in Python or C depending on the desired output of the parser generator. This means that if one would want to generate a parser in Python and another in C, two grammar files should be written, each one with a different set of actions, keeping everything else apart from said actions identical in both files. As an example of a grammar with Python actions, the piece of the parser generator that parses grammar files is bootstrapped from a meta-grammar file with Python actions that generate the grammar tree as a result of the parsing.

In the specific case of the PEG grammar for Python, having actions allows directly describing how the AST is composed in the grammar itself, making it more clear and maintainable. This AST generation process is supported by the use of some helper functions that factor out common AST object manipulations and some other required operations that are not directly related to the grammar.

To indicate these actions each alternative can be followed by the action code inside curly-braces, which specifies the return value of the alternative:

rule_name[return_type]:
    | first_alt1 first_alt2 { first_alt1 }
    | second_alt1 second_alt2 { second_alt1 }

If the action is omitted, a default action is generated:

• If there’s a single name in the rule, it gets returned.

• If there is more than one name in the rule, a collection with all parsed expressions gets returned (the type of the collection will be different in C and Python).

This default behaviour is primarily made for very simple situations and for debugging purposes.

Warning

It’s important that the actions don’t mutate any AST nodes that are passed into them via variables referring to other rules. The reason for mutation being not allowed is that the AST nodes are cached by memoization and could potentially be reused in a different context, where the mutation would be invalid. If an action needs to change an AST node, it should instead make a new copy of the node and change that.

The full meta-grammar for the grammars supported by the PEG generator is:

start[Grammar]: grammar ENDMARKER { grammar }

grammar[Grammar]:
    | metas rules { Grammar(rules, metas) }
    | rules { Grammar(rules, []) }

metas[MetaList]:
    | meta metas { [meta] + metas }
    | meta { [meta] }

meta[MetaTuple]:
    | "@" NAME NEWLINE { (name.string, None) }
    | "@" a=NAME b=NAME NEWLINE { (a.string, b.string) }
    | "@" NAME STRING NEWLINE { (name.string, literal_eval(string.string)) }

rules[RuleList]:
    | rule rules { [rule] + rules }
    | rule { [rule] }

rule[Rule]:
    | rulename ":" alts NEWLINE INDENT more_alts DEDENT {
            Rule(rulename[0], rulename[1], Rhs(alts.alts + more_alts.alts)) }
    | rulename ":" NEWLINE INDENT more_alts DEDENT { Rule(rulename[0], rulename[1], more_alts) }
    | rulename ":" alts NEWLINE { Rule(rulename[0], rulename[1], alts) }

rulename[RuleName]:
    | NAME '[' type=NAME '*' ']' {(name.string, type.string+"*")}
    | NAME '[' type=NAME ']' {(name.string, type.string)}
    | NAME {(name.string, None)}

alts[Rhs]:
    | alt "|" alts { Rhs([alt] + alts.alts)}
    | alt { Rhs([alt]) }

more_alts[Rhs]:
    | "|" alts NEWLINE more_alts { Rhs(alts.alts + more_alts.alts) }
    | "|" alts NEWLINE { Rhs(alts.alts) }

alt[Alt]:
    | items '$' action { Alt(items + [NamedItem(None, NameLeaf('ENDMARKER'))], action=action) }
    | items '$' { Alt(items + [NamedItem(None, NameLeaf('ENDMARKER'))], action=None) }
    | items action { Alt(items, action=action) }
    | items { Alt(items, action=None) }

items[NamedItemList]:
    | named_item items { [named_item] + items }
    | named_item { [named_item] }

named_item[NamedItem]:
    | NAME '=' ~ item {NamedItem(name.string, item)}
    | item {NamedItem(None, item)}
    | it=lookahead {NamedItem(None, it)}

lookahead[LookaheadOrCut]:
    | '&' ~ atom {PositiveLookahead(atom)}
    | '!' ~ atom {NegativeLookahead(atom)}
    | '~' {Cut()}

item[Item]:
    | '[' ~ alts ']' {Opt(alts)}
    |  atom '?' {Opt(atom)}
    |  atom '*' {Repeat0(atom)}
    |  atom '+' {Repeat1(atom)}
    |  sep=atom '.' node=atom '+' {Gather(sep, node)}
    |  atom {atom}

atom[Plain]:
    | '(' ~ alts ')' {Group(alts)}
    | NAME {NameLeaf(name.string) }
    | STRING {StringLeaf(string.string)}

# Mini-grammar for the actions

action[str]: "{" ~ target_atoms "}" { target_atoms }

target_atoms[str]:
    | target_atom target_atoms { target_atom + " " + target_atoms }
    | target_atom { target_atom }

target_atom[str]:
    | "{" ~ target_atoms "}" { "{" + target_atoms + "}" }
    | NAME { name.string }
    | NUMBER { number.string }
    | STRING { string.string }
    | "?" { "?" }
    | ":" { ":" }

As an illustrative example this simple grammar file allows directly generating a full parser that can parse simple arithmetic expressions and that returns a valid C-based Python AST:

start[mod_ty]: a=expr_stmt* ENDMARKER { _PyAST_Module(a, NULL, p->arena) }
expr_stmt[stmt_ty]: a=expr NEWLINE { _PyAST_Expr(a, EXTRA) }

expr[expr_ty]:
    | l=expr '+' r=term { _PyAST_BinOp(l, Add, r, EXTRA) }
    | l=expr '-' r=term { _PyAST_BinOp(l, Sub, r, EXTRA) }
    | term

term[expr_ty]:
    | l=term '*' r=factor { _PyAST_BinOp(l, Mult, r, EXTRA) }
    | l=term '/' r=factor { _PyAST_BinOp(l, Div, r, EXTRA) }
    | factor

factor[expr_ty]:
    | '(' e=expr ')' { e }
    | atom

atom[expr_ty]:
    | NAME
    | NUMBER

Here EXTRA is a macro that expands to start_lineno, start_col_offset, end_lineno, end_col_offset, p->arena, those being variables automatically injected by the parser; p points to an object that holds on to all state for the parser.

A similar grammar written to target Python AST objects:

start[ast.Module]: a=expr_stmt* ENDMARKER { ast.Module(body=a or [] }
expr_stmt: a=expr NEWLINE { ast.Expr(value=a, EXTRA) }

expr:
    | l=expr '+' r=term { ast.BinOp(left=l, op=ast.Add(), right=r, EXTRA) }
    | l=expr '-' r=term { ast.BinOp(left=l, op=ast.Sub(), right=r, EXTRA) }
    | term

term:
    | l=term '*' r=factor { ast.BinOp(left=l, op=ast.Mult(), right=r, EXTRA) }
    | l=term '/' r=factor { ast.BinOp(left=l, op=ast.Div(), right=r, EXTRA) }
    | factor

factor:
    | '(' e=expr ')' { e }
    | atom

atom:
    | NAME
    | NUMBER

Pegen

Pegen is the parser generator used in CPython to produce the final PEG parser used by the interpreter. It is the program that can be used to read the python grammar located in Grammar/python.gram and produce the final C parser. It contains the following pieces:

• A parser generator that can read a grammar file and produce a PEG parser written in Python or C that can parse said grammar. The generator is located at Tools/peg_generator/pegen.

• A PEG meta-grammar that automatically generates a Python parser that is used for the parser generator itself (this means that there are no manually-written parsers). The meta-grammar is located at Tools/peg_generator/pegen/metagrammar.gram.

• A generated parser (using the parser generator) that can directly produce C and Python AST objects.

The source code for Pegen lives at Tools/peg_generator/pegen but normally all typical commands to interact with the parser generator are executed from the main makefile.

How to regenerate the parser

Once you have made the changes to the grammar files, to regenerate the C parser (the one used by the interpreter) just execute:

make regen-pegen

using the Makefile in the main directory. If you are on Windows you can use the Visual Studio project files to regenerate the parser or to execute:

./PCbuild/build.bat --regen

The generated parser file is located at Parser/parser.c.

How to regenerate the meta-parser

The meta-grammar (the grammar that describes the grammar for the grammar files themselves) is located at Tools/peg_generator/pegen/metagrammar.gram. Although it is very unlikely that you will ever need to modify it, if you make any modifications to this file (in order to implement new Pegen features) you will need to regenerate the meta-parser (the parser that parses the grammar files). To do so just execute:

make regen-pegen-metaparser

If you are on Windows you can use the Visual Studio project files to regenerate the parser or to execute:

./PCbuild/build.bat --regen

Grammatical elements and rules

Pegen has some special grammatical elements and rules:

• Strings with single quotes (’) (e.g. 'class') denote KEYWORDS.

• Strings with double quotes (”) (e.g. "match") denote SOFT KEYWORDS.

• Uppercase names (e.g. NAME) denote tokens in the Grammar/Tokens file.

• 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).

  • The order of the alternatives involving invalid rules matter (like any rule in PEG).

Tokenization

It is common among PEG parser frameworks that the parser does both the parsing and the tokenization, but this does not happen in Pegen. The reason is that the Python language needs a custom tokenizer to handle things like indentation boundaries, some special keywords like ASYNC and AWAIT (for compatibility purposes), backtracking errors (such as unclosed parenthesis), dealing with encoding, interactive mode and much more. Some of these reasons are also there for historical purposes, and some others are useful even today.

The list of tokens (all uppercase names in the grammar) that you can use can be found in the