Some rules are not actually LL(1)

Although the Python grammar is technically an LL(1) grammar (because it is parsed by an LL(1) parser) several rules are not LL(1) and several workarounds are implemented in the grammar and in other parts of CPython to deal with this. For example, consider the rule for assignment expressions:

namedexpr_test: NAME [':=' test]

This simple rule is not compatible with the Python grammar as NAME is among the elements of the first set of the rule test. To work around this limitation the actual rule that appears in the current grammar is:

namedexpr_test: test [':=' test]

Which is a much broader rule than the previous one allowing constructs like [x for x in y] := [1,2,3]. The way the rule is limited to its desired form is by disallowing these unwanted constructions when transforming the parse tree to the abstract syntax tree. This is not only inelegant but a considerable maintenance burden as it forces the AST creation routines and the compiler into a situation in which they need to know how to separate valid programs from invalid programs, which should be a responsibility solely of the parser. This also leads to the actual grammar file not reflecting correctly what the actual grammar is (that is, the collection of all valid Python programs).

Similar workarounds appear in multiple other rules of the current grammar. Sometimes this problem is unsolvable. For instance, bpo-12782: Multiple context expressions do not support parentheses for continuation across lines shows how making an LL(1) rule that supports writing:

with (
    open("a_really_long_foo") as foo,
    open("a_really_long_baz") as baz,
    open("a_really_long_bar") as bar
):
  ...

is not possible since the first sets of the grammar items that can appear as context managers include the open parenthesis, making the rule ambiguous. This rule is not only consistent with other parts of the language (like the rule for multiple imports), but is also very useful to auto-formatting tools, as parenthesized groups are normally used to group elements to be formatted together (in the same way the tools operate on the contents of lists, sets…).

Complicated AST parsing

Another problem of the current parser is that there is a huge coupling between the AST generation routines and the particular shape of the produced parse trees. This makes the code for generating the AST especially complicated as many actions and choices are implicit. For instance, the AST generation code knows what alternatives of a certain rule are produced based on the number of child nodes present in a given parse node. This makes the code difficult to follow as this property is not directly related to the grammar file and is influenced by implementation details. As a result of this, a considerable amount of the AST generation code needs to deal with inspecting and reasoning about the particular shape of the parse trees that it receives.

Lack of left recursion

As described previously, a limitation of LL(1) grammars is that they cannot allow left-recursion. This makes writing some rules very unnatural and far from how programmers normally think about the program. For instance this construct (a simpler variation of several rules present in the current grammar):

expr: expr '+' term | term

cannot be parsed by an LL(1) parser. The traditional remedy is to rewrite the grammar to circumvent the problem:

expr: term ('+' term)*

The problem that appears with this form is that the parse tree is forced to have a very unnatural shape. This is because with this rule, for the input program a + b + c the parse tree will be flattened (['a', '+', 'b', '+', 'c']) and must be post-processed to construct a left-recursive parse tree ([['a', '+', 'b'], '+', 'c']). Being forced to write the second rule not only leads to the parse tree not correctly reflecting the desired associativity, but also imposes further pressure on later compilation stages to detect and post-process these cases.

Intermediate parse tree

The last problem present in the current parser is the intermediate creation of a parse tree or Concrete Syntax Tree that is later transformed to an Abstract Syntax Tree. Although the construction of a CST is very common in parser and compiler pipelines, in CPython this intermediate CST is not used by anything else (it is only indirectly exposed by the parser module and a surprisingly small part of the code in the CST production is reused in the module). Which is worse: the whole tree is kept in memory, keeping many branches that consist of chains of nodes with a single child. This has been shown to consume a considerable amount of memory (for instance in bpo-26415: Excessive peak memory consumption by the Python parser).

Having to produce an intermediate result between the grammar and the AST is not only undesirable but also makes the AST generation step much more complicated, raising considerably the maintenance burden.

Left recursion

PEG parsers normally do not support left recursion but we have implemented 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

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.

rule_name: first_rule second_rule

rule_name[return_type]:
    | first_alt
    | second_alt

rule_name: (e)

rule_name: (e1 e2)*

rule_name: [e]

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

rule_name: (e1 e2)*

rule_name: (e1 e2)+

rule_name: ','.e+

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

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

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 proposed 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 new proposed 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 and C code is being generated, then there are two different possibilities:

1. If there’s a single name in the alternative, this gets returned.
2. If not, a dummy name object gets returned (this case should be avoided).

If the action is omitted and Python code is being generated, then a list with all the parsed expressions gets returned (this is meant for debugging).

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* $ { Module(a, NULL, p->arena) }
expr_stmt[stmt_ty]: a=expr NEWLINE { _Py_Expr(a, EXTRA) }
expr[expr_ty]:
    | l=expr '+' r=term { _Py_BinOp(l, Add, r, EXTRA) }
    | l=expr '-' r=term { _Py_BinOp(l, Sub, r, EXTRA) }
    | t=term { t }

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

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

atom[expr_ty]:
    | n=NAME { n }
    | n=NUMBER { n }
    | s=STRING { s }

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: expr NEWLINE? ENDMARKER { ast.Expression(expr) }
expr:
    | expr '+' term { ast.BinOp(expr, ast.Add(), term) }
    | expr '-' term { ast.BinOp(expr, ast.Sub(), term) }
    | term { term }

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

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

atom:
    | NAME { ast.Name(id=name.string, ctx=ast.Load()) }
    | NUMBER { ast.Constant(value=ast.literal_eval(number.string)) }

Validation

To start with validation, we regularly compile the entire Python 3.8 stdlib and compare every aspect of the resulting AST with that produced by the standard compiler. (In the process we found a few bugs in the standard parser’s treatment of line and column numbers, which we have all fixed upstream via a series of issues and PRs.)

We have also occasionally compiled a much larger codebase (the approx. 3800 most popular packages on PyPI) and this has helped us find a (very) few additional bugs in the new parser.

(One area we have not explored extensively is rejection of all wrong programs. We have unit tests that check for a certain number of explicit rejections, but more work could be done, e.g. by using a fuzzer that inserts random subtle bugs into existing code. We’re open to help in this area.)

Performance

We have tuned the performance of the new parser to come within 10% of the current parser both in speed and memory consumption. While the PEG/packrat parsing algorithm inherently consumes more memory than the current LL(1) parser, we have an advantage because we don’t construct an intermediate CST.

Below are some benchmarks. These are focused on compiling source code to bytecode, because this is the most realistic situation. Returning an AST to Python code is not as representative, because the process to convert the internal AST (only accessible to C code) to an external AST (an instance of ast.AST) takes more time than the parser itself.

All measurements reported here are done on a recent MacBook Pro, taking the median of three runs. No particular care was taken to stop other applications running on the same machine.

The first timings are for our canonical test file, which has 100,000 lines endlessly repeating the following three lines:

1 + 2 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + ((((((11 * 12 * 13 * 14 * 15 + 16 * 17 + 18 * 19 * 20))))))
2*3 + 4*5*6
12 + (2 * 3 * 4 * 5 + 6 + 7 * 8)

• Just parsing and throwing away the internal AST takes 1.16 seconds with a max RSS of 681 MiB.
• Parsing and converting to ast.AST takes 6.34 seconds, max RSS 1029 MiB.
• Parsing and compiling to bytecode takes 1.28 seconds, max RSS 681 MiB.
• With the current parser, parsing and compiling takes 1.44 seconds, max RSS 836 MiB.

For this particular test file, the new parser is faster and uses less memory than the current parser (compare the last two bullets).

We also did timings with a more realistic payload, the entire Python 3.8 stdlib. This payload consists of 1,641 files, 749,570 lines, 27,622,497 bytes. (Though 11 files can’t be compiled by any Python 3 parser due to encoding issues, sometimes intentional.)

• Compiling and throwing away the internal AST took 2.141 seconds. That’s 350,040 lines/sec, or 12,899,367 bytes/sec. The max RSS was 74 MiB (the largest file in the stdlib is much smaller than out canonical test file).
• Compiling to bytecode took 3.290 seconds. That’s 227,861 lines/sec, or 8,396,942 bytes/sec. Max RSS 77 MiB.
• Compiling to bytecode using the current parser took 3.367 seconds. That’s 222,620 lines/sec, or 8,203,780 bytes/sec. Max RSS 70 MiB.

Comparing the last two bullets we find that the new parser is slightly faster but uses slightly (about 10%) more memory. We believe this is acceptable. (Also, there are probably some more tweaks we can make to reduce memory usage.)