Following system colour scheme - Python 增强提案 Selected dark colour scheme - Python 增强提案 Selected light colour scheme - Python 增强提案

Python 增强提案

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年3月24日
Python 版本:
3.9
发布历史:
2020年4月2日
目录

重要

本 PEP 是一份历史文档。最新、规范的文档现可在完整语法规范中找到。

×

有关如何提出更改，请参阅 PEP 1。

概述

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

LL(1) 解析器背景

当前的 Python 语法是基于 LL(1) 的语法。如果一个语法能够被 LL(1) 解析器解析，那么它就可以被称为 LL(1) 语法。LL(1) 解析器则定义为一种自顶向下、从左到右解析输入、执行最左推导、只向前看一个 token 的解析器。构建或生成 LL(1) 解析器的传统方法是生成一个**解析表**，该表编码了解析器所有可能状态之间的转换。这些表通常由语法的**First 集合**和**Follow 集合**构建而成。

  • 给定一个规则，**First 集合**是该规则完整推导中可能首先出现的所有终结符的集合。直观地，这有助于解析器在规则中的备选项之间做出决定。例如，给定规则
    rule: A | B

    如果只有 A 可以以终结符 *a* 开头，只有 B 可以以终结符 *b* 开头，并且解析器在解析此规则时看到 token *b*，它就知道需要跟随非终结符 B。

  • 当一个规则可能扩展到空字符串时，需要扩展这个简单概念。给定一个规则，**Follow 集合**是部分推导中可能紧跟在该规则右侧出现的所有终结符的集合。直观地，这解决了空备选项的问题。例如，给定此规则
    rule: A 'b'

    如果解析器有 token *b* 且非终结符 A 只能以 token *a* 开头，那么解析器可以判断这是一个无效程序。但如果 A 可以扩展到空字符串（称为 ε-产生式），那么解析器就会识别一个有效的空 A，因为下一个 token *b* 在 A 的 **Follow 集合**中。

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

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

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

rule: A | B

如果 A 和 B 的 First 集合有一些共同元素，则会产生歧义。当解析器在输入程序中看到一个 token，并且 *A* 和 *B* 都可以以此 token 开头时，它不可能推断出应该扩展哪个选项，因为无法检查程序的更多 token 来消除歧义。该规则可以转换为等效的 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 解析器具有无限前瞻（这意味着它们在决定一个规则之前可以考虑任意数量的 token）。通常，PEG 解析器通过一种称为“packrat parsing”[1] 的技术来避免这种指数级时间复杂性，该技术不仅在解析前将整个程序加载到内存中，而且还允许解析器任意回溯。通过记忆每个位置已匹配的规则，这种方式变得高效。记忆化缓存的代价是解析器将比简单的 LL(1) 解析器（通常基于表）自然使用更多的内存。我们将在本文档后面解释为什么我们认为这个代价是可以接受的。

基本原理

在本节中，我们描述了 CPython 中当前解析器机制存在的一系列问题，这些问题促使我们需要一个新的解析器。

有些规则实际上不是 LL(1)

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

namedexpr_test: [NAME ':='] test

这个简单的规则与 Python 语法不兼容，因为 _NAME_ 在规则 _test_ 的 First 集合中。为了解决这个限制，当前语法中出现的实际规则是

namedexpr_test: test [':=' test]

这是一个比前一个规则更宽泛的规则，允许像 [x for x in y] := [1,2,3] 这样的构造。该规则被限制为所需形式的方式是通过在将解析树转换为抽象语法树时禁用这些不需要的构造。这不仅不优雅，而且是一个相当大的维护负担，因为它迫使 AST 创建例程和编译器处于一种需要知道如何将有效程序与无效程序分开的情况，这应该是解析器唯一的责任。这也导致实际的语法文件未能正确反映**实际**语法（即所有有效 Python 程序的集合）。

类似的变通方法出现在当前语法的其他多个规则中。有时这个问题无法解决。例如，bpo-12782: 多个上下文表达式不支持跨行继续的括号 显示了如何创建一个支持编写的 LL(1) 规则

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

是不可能的，因为可以作为上下文管理器出现的语法项的 First 集合包括左括号，使得规则产生歧义。这个规则不仅与其他语言部分（如多重导入规则）一致，而且对自动格式化工具也非常有用，因为带括号的组通常用于将元素分组以便一起格式化（就像这些工具对列表、集合的内容进行操作一样）。

复杂的 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+

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

rule_name: ','.e+
&e

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

!e

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

一个取自提议的 Python 语法的例子指出，一个 primary 由一个 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 代码，则有两种不同的可能性：

  1. 如果备选项中只有一个名称，则返回该名称。
  2. 如果没有，则返回一个虚拟名称对象（应避免这种情况）。

如果省略了动作并且正在生成 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 的解析器时的迁移计划。迁移将分一系列步骤执行，以便在需要时最初可以回退到以前的解析器

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

性能和验证

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

验证

为了开始验证，我们定期编译整个 Python 3.8 标准库，并将生成的 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)（例如 Bison 和 Yacc）。原因主要是情感上的（直觉、预感），基于过去在其他项目中使用 Yacc 的经验，当时语法开发比预期花费了更多精力（部分原因是移位-归约冲突）。对 Bison 和 Yacc 的一个仍然成立的特定批评是，它们的元语法（用于将语法输入解析器生成器的表示法）不支持 EBNF 的便利性，如 [optional_clause] 或 (repeated_clause)*。使用自定义解析器生成器，可以自动生成与语法结构匹配的语法树，并且使用 EBNF，该树可以与语法的“人类友好”结构匹配。

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

参考资料

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

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

最后修改：2025-02-01 07:28:42 GMT