PEP 617 – CPython 的新 PEG 解析器

作者:: Guido van Rossum <guido at python.org>，Pablo Galindo <pablogsal at python.org>，Lysandros Nikolaou <lisandrosnik at gmail.com>
讨论对象:: Python-Dev 邮件列表
状态:: 最终
类型:: 标准化轨道
创建日期:: 2020-03-24
Python 版本:: 3.9
历史记录:: 2020-04-02

重要

此 PEP 是一个历史文档。最新的规范文档现在可以在完整的语法规范中找到。

有关如何提出更改的建议，请参见 PEP 1。

概述

此 PEP 提出用新的基于 PEG 的解析器替换 CPython 的当前基于 LL(1) 的解析器。此新的解析器将允许消除当前语法中为规避 LL(1) 限制而存在的多个“技巧”。它将大幅降低编译管道中某些与语法、解析器和 AST 生成相关的区域的维护成本。新的 PEG 解析器还将解除当前 Python 语法对 LL(1) 的限制。

当前的 Python 语法是基于 LL(1) 的语法。如果语法可以被 LL(1) 解析器解析，则可以称该语法为 LL(1) 语法，而 LL(1) 解析器则被定义为自顶向下的解析器，它从左到右解析输入，执行句子的最左推导，并且仅具有一个标记的超前查看。构建或生成 LL(1) 解析器的传统方法是生成一个解析表，该表对解析器所有可能状态之间的可能转换进行编码。这些表通常是从语法的首符集和后缀集构建的。

给定一个规则，首符集是该规则在完整推导中可能出现的第一个终结符的集合。直观地说，这有助于解析器在规则中的备选方案之间做出决定。例如，给定规则
```
rule: A | B
```
如果只有 A 可以以终结符a开头，而只有 B 可以以终结符b开头，并且解析器在解析此规则时看到了标记b，则它知道它需要遵循非终结符 B。
当一个规则可以扩展为空字符串时，需要对这个简单想法进行扩展。给定一个规则，后缀集是在部分推导中紧接在该规则右侧可能出现的终结符的集合。直观地说，这解决了空备选方案的问题。例如，给定此规则
```
rule: A 'b'
```
如果解析器具有标记b，而非终结符 A 只能以标记a开头，则解析器可以判断这是一个无效的程序。但是，如果 A 可以扩展为空字符串（称为 ε-产生式），则解析器将识别一个有效的空 A，因为下一个标记b在 A 的后缀集中。

当前的 Python 语法不包含 ε-产生式，因此在创建解析表时不需要后缀集。目前，在 CPython 中，一个解析器生成器程序会读取语法并生成一个解析表，该解析表表示一组确定性有限自动机 (DFA)，这些自动机可以包含在一个 C 程序（解析器）中。解析器是一个下推自动机，它使用这些数据来生成一个具体语法树 (CST)，有时直接称为“解析树”。在此过程中，首符集在生成 DFA 时被间接使用。

LL(1) 解析器和语法通常高效且易于实现和生成。但是，在 LL(1) 限制下，不可能以对语言设计者和读者自然的方式表达某些常见的构造。这包括 Python 语言中的一些构造。

由于 LL(1) 解析器只能查看一个标记来区分可能性，因此语法中的某些规则可能存在歧义。例如，规则

rule: A | B

如果 A 和 B 的首符集都有一些共同元素，则存在歧义。当解析器在输入程序中看到一个标记时，A 和 B 都可以以此标记开头，它无法推断出要扩展哪个选项，因为无法检查程序的任何其他标记来消除歧义。该规则可以转换为等效的 LL(1) 规则，但这可能会使人类读者难以理解其含义。本文档后面的示例表明，当前基于 LL(1) 的语法在这方面存在很多问题。

LL(1) 排除的另一大类规则是左递归规则。如果一个规则可以推导出一个以自身为最左侧符号的句子形式，则该规则是左递归的。例如，此规则

rule: rule 'a'

是左递归的，因为该规则可以扩展到一个以自身开头的表达式。正如稍后将要描述的那样，左递归是以语法中直接表达某些期望的语言属性的自然方式。

PEG 解析器的背景

PEG（解析表达式语法）语法与上下文无关语法（如当前语法）不同，因为它的编写方式更密切地反映了解析器在解析它时的操作方式。根本的技术差异在于选择运算符是有序的。这意味着在编写

rule: A | B | C

上下文无关语法解析器（如 LL(1) 解析器）将生成构造，这些构造在给定一个输入字符串时将推断哪个备选方案（A、B 或 C）必须扩展，而 PEG 解析器将检查第一个备选方案是否成功，并且只有在失败的情况下，它才会按编写顺序继续使用第二个或第三个备选方案。这使得选择运算符不具有交换性。

与 LL(1) 解析器不同，基于 PEG 的解析器不会出现歧义：如果一个字符串解析成功，那么它只有一个有效的解析树。这意味着基于 PEG 的解析器不会出现上一节中描述的歧义问题。

PEG 解析器通常被构建为递归下降解析器，其中语法中的每条规则对应于实现解析器的程序中的一个函数，而解析表达式（规则的“扩展”或“定义”）表示该函数中的“代码”。每个解析函数在概念上将输入字符串作为其参数，并生成以下结果之一：

“成功”结果。此结果表示该表达式可以通过该规则解析，并且该函数可以选择向前移动或使用提供给它的输入字符串消耗一个或多个字符。
“失败”结果，在这种情况下，不会消耗任何输入。

请注意，“失败”结果并不意味着程序不正确或解析失败，因为由于选择运算符是有序的，因此“失败”结果仅仅表示“尝试以下选项”。将 PEG 解析器直接实现为递归下降解析器，与 LL(1) 解析器相比，在最坏情况下将呈现指数级时间性能，因为 PEG 解析器具有无限超前查看（这意味着它们可以在决定规则之前考虑任意数量的标记）。通常，PEG 解析器使用一种名为“packrat 解析”[1] 的技术来避免这种指数级时间复杂度，该技术不仅在解析之前将整个程序加载到内存中，而且还允许解析器任意地回溯。这可以通过记忆已经匹配的每个位置的规则来实现效率。记忆缓存的代价是解析器自然会比简单的 LL(1) 解析器占用更多内存，而 LL(1) 解析器通常是基于表的。我们将在本文档的后面解释为什么我们认为这种代价是可以接受的。

理由

在本节中，我们将描述 CPython 当前解析器机制中存在的一系列问题，这些问题说明了对新解析器的需求。

一些规则实际上并非 LL(1)

尽管 Python 语法在技术上是 LL(1) 语法（因为它被 LL(1) 解析器解析），但许多规则并非 LL(1) 规则，并且在语法和 CPython 的其他部分中实施了许多解决方法来处理这个问题。例如，考虑赋值表达式的规则

namedexpr_test: [NAME ':='] test

此简单规则与 Python 语法不兼容，因为NAME 是test 规则的首符集中的元素之一。为了解决这个限制，出现在当前语法中的实际规则是

namedexpr_test: test [':=' test]

这比先前的规则更广泛，允许诸如 [x for x in y] := [1,2,3] 的构造。通过在将解析树转换为抽象语法树时不允许这些不需要的构造，该规则被限制为其所需的表单。这不仅不优雅，而且是相当大的维护负担，因为它迫使 AST 创建例程和编译器处于一种需要了解如何区分有效程序和无效程序的情况，而这应该是解析器唯一的职责。这也会导致实际的语法文件无法正确地反映实际的语法（即所有有效的 Python 程序的集合）。

类似的解决方法出现在当前语法的多个其他规则中。有时这个问题无法解决。例如，bpo-12782：多个上下文表达式不支持使用括号跨行继续展示了如何使一个支持写入

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

的 LL(1) 规则是不可能的，因为可能出现在上下文管理器中的语法项的首符集包括左括号，这使得规则存在歧义。此规则不仅与语言的其他部分一致（如多个导入的规则），而且对于自动格式化工具也很有用，因为括号组通常用于将要一起格式化的元素进行分组（与这些工具在列表、集合等内容上的操作方式相同）。

复杂的 AST 解析

当前解析器另一个问题是 AST 生成例程与生成的解析树的特定形状之间存在高度耦合。这使得生成 AST 的代码特别复杂，因为许多操作和选择是隐式的。例如，AST 生成代码知道特定规则的哪些备选方案是根据给定解析节点中存在的子节点数量生成的。这使得代码难以理解，因为此属性与语法文件没有直接关系，并且受实现细节的影响。因此，相当一部分 AST 生成代码需要处理检查和推理接收到的解析树的特定形状。

缺乏左递归

如前所述，LL(1) 语法的局限性是它们不允许左递归。这使得编写某些规则变得很不自然，并且远离程序员通常对程序的思考方式。例如，这个结构（当前语法中存在的一些规则的更简单变体）

expr: expr '+' term | term

无法被 LL(1) 解析器解析。传统的解决方法是重写语法以规避此问题

expr: term ('+' term)*

这种形式出现的问题是，解析树被迫具有很不自然的形状。这是因为使用此规则，对于输入程序 a + b + c，解析树将被扁平化（['a', '+', 'b', '+', 'c']），并且必须进行后处理以构建左递归解析树（[['a', '+', 'b'], '+', 'c']）。被迫编写第二个规则不仅会导致解析树不能正确反映所需的结合性，还会给后期的编译阶段带来进一步的压力，以检测和后处理这些情况。

中间解析树

当前解析器中存在的最后一个问题是，中间创建解析树或具体语法树，然后将其转换为抽象语法树。虽然在解析器和编译器管道中构建 CST 非常普遍，但在 CPython 中，此中间 CST 没有被其他任何东西使用（它只是被 *parser* 模块间接公开，并且 CST 生成代码中只有很小的一部分在模块中被重用）。更糟糕的是：整棵树保留在内存中，保留了许多由具有单个子节点的节点链组成的分支。这已被证明会消耗大量的内存（例如在 bpo-26415: Python 解析器内存峰值过高中）。

必须在语法和 AST 之间生成一个中间结果不仅不可取，而且还使 AST 生成步骤变得更加复杂，从而大大增加了维护负担。

新的提议的 PEG 解析器

新的提议的 PEG 解析器包含以下部分

一个解析器生成器，可以读取语法文件并生成用 Python 或 C 编写的 PEG 解析器，可以解析该语法。
一个 PEG 元语法，它自动生成一个 Python 解析器，该解析器用于解析器生成器本身（这意味着没有手动编写的解析器）。
一个生成的解析器（使用解析器生成器），可以直接生成 C 和 Python AST 对象。

左递归

PEG 解析器通常不支持左递归，但我们已经实现了一种类似于 Medeiros 等人 [2] 中描述的技术，但使用记忆缓存而不是静态变量。这种方法更接近 Warth 等人 [3] 中描述的方法。这使我们能够编写不仅简单的左递归规则，而且还可以编写更复杂的规则，这些规则涉及间接左递归，例如

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

以及“隐藏左递归”，例如

rule: 'optional'? rule '@' some_other_rule

语法

语法由一系列规则组成，其形式为

rule_name: expression

可选地，可以在规则名称后面立即包含一个类型，该类型指定与规则相对应的 C 或 Python 函数的返回类型

rule_name[return_type]: expression

如果省略返回类型，则在 C 中返回 void *，在 Python 中返回 Any。

语法表达式

`# 注释`

Python 风格的注释。

`e1 e2`

匹配 e1，然后匹配 e2。

rule_name: first_rule second_rule

`e1 | e2`

匹配 e1 或 e2。

第一个备选方案也可以出现在规则名称后的行中，以用于格式化目的。在这种情况下，必须在第一个备选方案之前使用 |，如下所示

rule_name[return_type]:
    | first_alt
    | second_alt

`( e )`

匹配 e。

rule_name: (e)

一个稍微复杂且有用的示例包括将分组运算符与重复运算符一起使用

rule_name: (e1 e2)*

`[ e ] 或 e?`

可选地匹配 e。

rule_name: [e]

一个更有用的示例包括定义尾随逗号是可选的

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

`e*`

匹配 e 的零个或多个出现。

rule_name: (e1 e2)*

`e+`

匹配 e 的一个或多个出现。

rule_name: (e1 e2)+

`s.e+`

匹配 e 的一个或多个出现，用 s 分隔。生成的解析树不包括分隔符。这与 (e (s e)*) 相同。

rule_name: ','.e+

`&e`

如果 e 可以被解析，则成功，但不消耗任何输入。

`!e`

如果 e 可以被解析，则失败，但不消耗任何输入。

从提议的 Python 语法中获取的一个示例指定，一个 primary 由一个 atom 组成，该 atom 之后不跟着 . 或 ( 或 [

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

`~`

承诺当前备选方案，即使它无法解析。

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

在此示例中，如果解析了左括号，则不会考虑另一个备选方案，即使 some_rule 或 ‘)’ 无法解析。

语法中的变量

可以通过在子表达式之前添加一个标识符和一个 = 符号来命名子表达式。然后可以在操作中使用该名称（见下文），例如

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

语法动作

为了避免混淆语法和 AST 生成之间关系的中间步骤，提议的 PEG 解析器允许通过语法操作直接为规则生成 AST 节点。语法操作是特定于语言的表达式，当语法规则成功解析时会对其进行评估。这些表达式可以用 Python 或 C 编写，具体取决于解析器生成器的预期输出。这意味着如果有人想用 Python 生成一个解析器，另一个人用 C 生成一个解析器，则应该编写两个语法文件，每个文件都有一组不同的操作，除了这些操作之外，所有其他内容在两个文件中都相同。作为具有 Python 操作的语法的示例，解析语法文件的解析器生成器的部分是从一个具有 Python 操作的元语法文件引导的，该操作在解析的结果中生成语法树。

在提议的用于 Python 的新 PEG 语法的特定情况下，使用操作允许直接在语法中描述 AST 是如何组成的，使其更加清晰和可维护。AST 生成过程通过使用一些帮助函数来支持，这些函数将常见的 AST 对象操作和其他一些与语法没有直接关系的必要操作分解出来。

为了指示这些操作，每个备选方案都可以后跟花括号内的操作代码，该代码指定备选方案的返回值

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

如果省略了操作并且正在生成 C 代码，则有两种不同的可能性

如果备选方案中只有一个名称，则返回该名称。
如果不是，则返回一个虚拟名称对象（应避免这种情况）。

如果省略了操作并且正在生成 Python 代码，则返回一个包含所有已解析表达式的列表（这是为了调试）。

PEG 生成器支持的语法的完整元语法为

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 }
    | "?" { "?" }
    | ":" { ":" }

作为一个说明性的示例，这个简单的语法文件允许直接生成一个完整的解析器，该解析器可以解析简单的算术表达式并返回一个有效的基于 C 的 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 }

这里 EXTRA 是一个宏，展开为 start_lineno, start_col_offset, end_lineno, end_col_offset, p->arena，这些变量是解析器自动注入的；p 指向一个对象，该对象保存解析器的所有状态。

一个类似的语法，编写为针对 Python AST 对象

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)) }

迁移计划

本节描述将此 PEP 接受后移植到新的基于 PEG 的解析器时的迁移计划。迁移将按一系列步骤执行，这些步骤允许最初在需要时回退到以前的解析器

从 Python 3.9 alpha 6 开始，在 CPython 中包含新的基于 PEG 的解析器机制，使用一个命令行标志和环境变量，允许在新的解析器和旧的解析器之间切换，以及允许独立调用新的解析器和旧的解析器的显式 API。在此步骤中，所有 Python API（如 ast.parse 和 compile）将使用标志或环境变量设置的解析器，默认解析器将是新的基于 PEG 的解析器。
在 Python 3.9 和 Python 3.10 之间，旧的解析器和相关代码（如“parser”模块）将保留，直到发布新的 Python 版本（Python 3.10）。在此期间，在删除旧的解析器之前，**不会添加任何需要 PEG 解析器的新 Python 语法添加**。这意味着语法将保留为 LL(1)，直到旧的解析器被删除。
在 Python 3.10 中，删除旧的解析器、命令行标志、环境变量和“parser”模块以及相关代码。

性能和验证

我们已经对新的解析器进行了广泛的计时和验证，这使我们相信新的解析器具有足够高的质量来替换当前的解析器。

验证

首先进行验证，我们定期编译整个 Python 3.8 stdlib，并将生成的 AST 的各个方面与标准编译器生成的 AST 进行比较。（在此过程中，我们在标准解析器处理行号和列号的方式中发现了一些错误，我们已经通过一系列问题和 PR 在上游修复了所有这些错误。）

我们还偶尔编译了一个更大的代码库（PyPI 上大约 3800 个最流行的包），这帮助我们在新的解析器中发现了一些（非常少的）额外错误。

（我们没有广泛探索的一个领域是拒绝所有错误的程序。我们有一些单元测试可以检查一定数量的显式拒绝，但可以做更多工作，例如使用一个模糊测试器，该模糊测试器将随机的细微错误插入到现有代码中。我们很乐意在这方面提供帮助。）

性能

我们已经调整了新解析器的性能，使其在速度和内存消耗方面都能够与当前的解析器相差 10% 以内。虽然 PEG/packrat 解析算法本质上比当前的 LL(1) 解析器消耗更多内存，但我们有一个优势，因为我们没有构建中间 CST。

以下是一些基准测试。这些测试侧重于将源代码编译为字节码，因为这是最现实的情况。将 AST 返回到 Python 代码并不具有代表性，因为将内部 AST（仅 C 代码可访问）转换为外部 AST（ast.AST 的实例）的过程比解析器本身花费的时间更长。

此处报告的所有测量结果均在最近的 MacBook Pro 上完成，取三次运行的中位数。未特别注意停止在同一台机器上运行的其他应用程序。

第一个时间用于我们的规范测试文件，该文件有 100,000 行，无限重复以下三行

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)

仅解析并丢弃内部 AST 使用 1.16 秒，最大 RSS 为 681 MiB。
解析并转换为 ast.AST 使用 6.34 秒，最大 RSS 为 1029 MiB。
解析并编译为字节码使用 1.28 秒，最大 RSS 为 681 MiB。
使用当前解析器，解析和编译使用 1.44 秒，最大 RSS 为 836 MiB。

对于此特定测试文件，新解析器比当前解析器更快，并且使用更少的内存（比较最后两行）。

我们还使用更真实的负载进行了计时，即整个 Python 3.8 标准库。此负载包含 1,641 个文件、749,570 行、27,622,497 字节。（尽管由于编码问题，11 个文件无法被任何 Python 3 解析器编译，有时是故意的。）

编译并丢弃内部 AST 使用 2.141 秒。这相当于 350,040 行/秒，或 12,899,367 字节/秒。最大 RSS 为 74 MiB（标准库中最大的文件远小于我们的规范测试文件）。
编译为字节码使用 3.290 秒。这相当于 227,861 行/秒，或 8,396,942 字节/秒。最大 RSS 为 77 MiB。
使用当前解析器编译为字节码使用 3.367 秒。这相当于 222,620 行/秒，或 8,203,780 字节/秒。最大 RSS 为 70 MiB。

比较最后两行，我们发现新解析器略快，但使用略多（约 10%）的内存。我们认为这是可以接受的。（此外，我们可能还可以进行一些额外的调整以减少内存使用量。）

拒绝的替代方案

我们没有认真考虑实现新解析器的替代方法，但这里简要讨论一下 LALR(1)。

三十年前，第一作者决定在 Python 的解析器中走自己的路，而不是使用 LALR(1)，而 LALR(1) 当时是行业标准（例如 Bison 和 Yacc）。原因主要是情感上的（直觉、直觉），基于过去在其他项目中使用 Yacc 的经验，其中语法开发比预期花费了更多精力（部分原因是移进-归约冲突）。对 Bison 和 Yacc 的具体批评仍然成立，即它们的元语法（用于将语法输入解析器生成器的表示法）不支持 EBNF 的便利性，例如 [optional_clause] 或 (repeated_clause)*。使用自定义解析器生成器，可以自动生成与语法结构匹配的语法树，并且使用 EBNF，该树可以匹配语法的“人性化”结构。

没有考虑 LR 的其他变体，也没有考虑 LL（例如 ANTLR）。选择 PEG 是因为它在理解递归下降解析的基础知识的情况下很容易理解。

参考资料

[4] 圭多关于 PEG 解析的系列文章 https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60

版权

本文已置于公有领域。

来源： https://github.com/python/peps/blob/main/peps/pep-0617.rst

最后修改： 2023-12-18 21:39:13 GMT

Python 增强提案

PEP 617 – CPython 的新 PEG 解析器

概述

LL(1) 解析器的背景

PEG 解析器的背景

理由

一些规则实际上并非 LL(1)

复杂的 AST 解析

缺乏左递归

中间解析树

新的提议的 PEG 解析器

左递归

语法

语法表达式

`# 注释`

`e1 e2`

`e1 | e2`

`( e )`

`[ e ] 或 e?`

`e*`

`e+`

`s.e+`

`&e`

`!e`

`~`

语法中的变量

语法动作

迁移计划

性能和验证

验证

性能

拒绝的替代方案

参考资料

版权