解析器指南

摘要

CPython 中的解析器目前是 PEG（解析器表达式语法） 解析器。解析器的第一个版本曾经是 LL(1) 解析器，这是 CPython 中最古老的部分之一，在被 PEP 617 替换之前实现。特别是，当前解析器和旧的 LL(1) 解析器都是 解析器生成器 的输出。这意味着解析器编写的过程是将 Python 语言的语法描述提供给一个特殊程序（解析器生成器），该程序输出解析器。因此，Python 语言的更改方式是修改语法文件，并且开发人员很少需要与解析器生成器本身进行交互，除了使用它生成解析器之外。

PEG 解析器的工作原理

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

rule: A | B | C

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

与 LL(1) 解析器不同，基于 PEG 的解析器不会产生歧义：如果一个字符串可以解析，它就只有一个有效的解析树。这意味着基于 PEG 的解析器不会遭受 LL(1) 解析器和一般上下文无关语法中可能出现的歧义问题。

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

• “成功”结果。此结果表明该表达式可以按该规则解析，并且该函数可以选择向前移动或使用提供给它的输入字符串消耗一个或多个字符。

• “失败”结果，在这种情况下不会消耗任何输入。

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

关键思想

重要

不要尝试以与 EBNF 或上下文无关语法相同的方式推理 PEG 语法。PEG 经过优化，可以描述如何解析输入字符串，而上下文无关语法经过优化，可以生成它们描述的语言的字符串（在 EBNF 中，要了解给定的字符串是否在语言中，你需要做一些工作来找出，因为它从语法中并不明显）。

• 备选方案是有序的（A | B 不等于 B | A）。

• 如果规则返回失败，并不意味着解析失败，它只是意味着“尝试其他方法”。

• 默认情况下，PEG 解析器以指数时间运行，可以通过使用记忆化优化为线性时间。

• 如果解析完全失败（没有规则成功解析所有输入文本），PEG 解析器没有“SyntaxError 在哪里”的概念。

有序选择运算符的后果

虽然 PEG 看起来像 EBNF，但它的含义却大不相同。PEG 解析器中备选方案是有序的（这是 PEG 解析器工作原理的核心）这一事实除了消除歧义之外，还有深远的影响。

如果一个规则有两个备选方案，并且第一个备选方案成功，则即使调用规则无法解析输入的其余部分，也不会尝试第二个备选方案。因此，解析器被称为“急切的”。为了说明这一点，请考虑以下两个规则（在这些示例中，令牌是一个单独的字符）

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

在常规 EBNF 语法中，这两个规则都指定语言 {aa, aaa}，但在 PEG 中，这两个规则之一接受字符串 aaa，但不接受字符串 aa。另一个则相反——它接受字符串 aa，但不接受字符串 aaa。规则 ('a'|'aa')'a' 不接受 aaa，因为 'a'|'aa' 消耗第一个 a，让规则中的最后一个 a 消耗第二个 a，并省略第三个 a。由于规则已成功，因此永远不会尝试返回并让 'a'|'aa' 尝试第二个备选方案。表达式 ('aa'|'a')'a' 不接受 aa，因为 'aa'|'a' 接受所有 aa，没有为最后一个 a 留出任何内容。同样，第二个备选方案 'aa'|'a' 没有被尝试。

注意

有序选择的影响，例如上面说明的影响，可能会被多层规则隐藏。

出于这个原因，编写包含备选方案的规则几乎在所有情况下都是一个错误，例如

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

在此示例中，第二个备选方案永远不会被尝试，因为第一个备选方案将首先成功（即使输入字符串有 'else' block 紧随其后）。要正确编写此规则，你可以简单地更改顺序

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

在这种情况下，如果输入字符串没有 'else' block，第一个备选方案将失败，第二个备选方案将尝试没有该部分。

语法

语法由如下形式的规则序列组成

rule_name: expression

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

rule_name[return_type]: expression

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

语法表达式

# comment

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 ] or 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 !'.' !'(' !'['

~

提交到当前备选方案，即使它无法解析（这称为“cut”）。

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

在此示例中，如果解析了一个左括号，那么即使 some_rule 或 ) 无法解析，也不会考虑其他备选方案。

左递归

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

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

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

rule: 'optional'? rule '@' some_other_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 中将不同）。

此默认行为主要针对非常简单的情况和调试目的而设计。

警告

重要的是，操作不会通过引用其他规则的变量将传递给它们的任何 AST 节点进行更改。不允许更改的原因是 AST 节点通过记忆化进行缓存，并且可能会在不同的上下文中重复使用，在这种情况下，更改将无效。如果操作需要更改 AST 节点，则应该创建一个新节点副本并对其进行更改。

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* 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

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

为目标 Python AST 对象编写的类似语法

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 是 CPython 中用于生成解释器使用的最终 PEG 解析器的解析器生成器。它是一个程序，可用于读取位于 Grammar/python.gram 中的 Python 语法并生成最终的 C 解析器。它包含以下部分

• 一个解析器生成器，它可以读取语法文件并生成一个用 Python 或 C 编写的 PEG 解析器，该解析器可以解析所述语法。该生成器位于 Tools/peg_generator/pegen。

• 一个 PEG 元语法，它自动生成一个 Python 解析器，该解析器用于解析器生成器本身（这意味着没有手动编写的解析器）。元语法位于 Tools/peg_generator/pegen/metagrammar.gram。

• 一个生成的解析器（使用解析器生成器），它可以直接生成 C 和 Python AST 对象。

Pegen 的源代码位于 Tools/peg_generator/pegen，但通常与解析器生成器交互的所有典型命令都是从主 makefile 执行的。

如何重新生成解析器

对语法文件进行更改后，要重新生成 C 解析器（解释器使用的解析器），只需执行

make regen-pegen

使用主目录中的 Makefile。如果您使用的是 Windows，则可以使用 Visual Studio 项目文件重新生成解析器或执行

./PCbuild/build.bat --regen

生成的解析器文件位于 Parser/parser.c。

如何重新生成元解析器

元语法（描述语法文件本身语法的语法）位于 Tools/peg_generator/pegen/metagrammar.gram。虽然你几乎不可能需要修改它，但如果你对这个文件进行任何修改（为了实现新的 Pegen 特性），你需要重新生成元解析器（解析语法文件的解析器）。只需执行

make regen-pegen-metaparser

如果你在 Windows 上，可以使用 Visual Studio 项目文件重新生成解析器或执行

./PCbuild/build.bat --regen

语法元素和规则

Pegen 有一些特殊的语法元素和规则

• 带单引号 (’) 的字符串（例如 'class'）表示关键字。

• 带双引号 (”) 的字符串（例如 "match"）表示软关键字。

• 大写名称（例如 NAME）表示 Grammar/Tokens 文件中的标记。

• 以 invalid_ 开头的规则名称用于专门的语法错误。

  • 这些规则不会在解析器的第一遍中使用。

  • 只有当第一遍解析失败时，才会执行包括无效规则的第二遍。

  • 如果解析器在第二阶段以通用语法错误失败，则将使用第一遍通用失败的位置（这避免了因无效规则而报告不正确的位置）。

  • 涉及无效规则的备选方案的顺序很重要（就像 PEG 中的任何规则一样）。

标记化

在 PEG 解析器框架中，解析器通常同时执行解析和标记化，但 Pegen 中不会发生这种情况。原因是 Python 语言需要一个自定义标记器来处理缩进边界、一些特殊关键字（如 ASYNC 和 AWAIT（出于兼容性目的）、回溯错误（如未闭合的括号）、处理编码、交互模式等。其中一些原因也是出于历史目的，而另一些原因即使在今天也很有用。

你可以在 Grammar/Tokens 文件中找到你可以使用的标记列表（语法中的所有大写名称）。如果你更改此文件以添加新标记，请务必通过执行以下操作重新生成文件

make regen-token

如果你在 Windows 上，可以使用 Visual Studio 项目文件重新生成标记或执行

./PCbuild/build.bat --regen

标记如何生成以及支配此过程的规则完全取决于标记器（Parser/lexer/ 和 Parser/tokenizer/）；解析器只是从它那里接收标记。

记忆化

如前所述，为了避免解析器中的指数时间复杂度，使用了记忆化。

Python 使用的 C 解析器经过高度优化，记忆化在内存和时间方面都可能很昂贵。虽然内存成本很明显（解析器需要内存来存储缓存中的先前结果），但执行时间成本来自于持续检查给定规则是否有缓存命中。在许多情况下，重新解析它可能会更快。Pegen 默认情况下禁用记忆化，但规则名称（以及类型，如果存在）后带有特殊标记 memo 的规则除外

rule_name[typr] (memo):
    ...

通过有选择地为少数规则启用记忆化，解析器变得更快并使用更少的内存。

注意

左递归规则始终使用记忆化，因为左递归的实现依赖于它。

要了解新规则是否需要记忆化，需要进行基准测试（比较有和没有记忆化的某些相当大文件的执行时间和内存使用情况）。生成的 C 解析代码中提供了一个非常简单的仪表 API，可以用来测量每个规则使用记忆化的程度（查看 Parser/pegen.c 文件以获取更多信息），但需要手动激活它。

自动变量

为了简化编写操作，Pegen 在编写操作时将一些自动变量注入到可用命名空间中。在 C 解析器中，其中一些自动变量名称是

• p：解析器结构。

• EXTRA：这是一个宏，它扩展为 (_start_lineno, _start_col_offset, _end_lineno, _end_col_offset, p->arena)，通常用于创建 AST 节点，因为几乎所有构造函数都需要提供这些属性。所有位置变量都取自当前标记的位置信息。

硬关键字和软关键字

注意

在语法文件中，关键字使用单引号定义（例如 'class'），而软关键字使用双引号定义（例如 "match"）。

pegen 语法中允许两种关键字：硬关键字和软关键字。硬关键字和软关键字的区别在于，硬关键字始终是保留字，即使在它们没有意义的位置（例如 x = class + 1），而软关键字只有在上下文中才具有特殊含义。尝试将硬关键字用作变量将始终失败

>>> class = 3
File "<stdin>", line 1
    class = 3
        ^
SyntaxError: invalid syntax
>>> foo(class=3)
File "<stdin>", line 1
    foo(class=3)
        ^^^^^
SyntaxError: invalid syntax

如果在定义为关键字的上下文中以外使用软关键字，则没有此限制

>>> match = 45
>>> foo(match="Yeah!")

match 和 case 关键字是软关键字，因此它们分别在 match 语句或 case 块的开头被识别为关键字，但允许在其他地方用作变量或参数名称。

您可以从 Python 中获取语法中定义的所有关键字列表

>>> import keyword
>>> keyword.kwlist
['False', 'None', 'True', 'and', 'as', 'assert', 'async', 'await', 'break',
'class', 'continue', 'def', 'del', 'elif', 'else', 'except', 'finally', 'for',
'from', 'global', 'if', 'import', 'in', 'is', 'lambda', 'nonlocal', 'not', 'or',
'pass', 'raise', 'return', 'try', 'while', 'with', 'yield']

以及软关键字

>>> import keyword
>>> keyword.softkwlist
['_', 'case', 'match']

注意

软关键字可能有点难以管理，因为它们可能出现在您不希望出现的地方，鉴于 PEG 解析器中顺序备选方案的行为（有关此内容的背景信息，请参阅 有序选择的后果部分）。一般来说，请尝试在没有太多备选方案的地方定义它们。

错误处理

当 pegen 生成的解析器检测到引发异常时，它将自动停止解析，无论解析器的当前状态如何，它将展开堆栈并报告异常。这意味着如果 规则操作 引发异常，所有解析都将在该确切点停止。这样做是为了正确传播通过调用 Python 的 C API 函数设置的任何异常。这也包括 SyntaxError 异常，这是解析器用于报告自定义语法错误消息的主要机制。

注意

标记器错误通常通过引发异常来报告，但一些特殊的标记器错误（例如未闭合的括号）将仅在解析器完成且未返回任何内容后报告。

如何报告语法错误

如 PEG 解析器工作方式部分 中前面所述，PEG 解析器没有定义语法中错误发生的位置的概念，因为规则失败并不意味着像在上下文无关语法中那样的解析失败。这意味着必须使用一些启发式方法来报告通用错误，除非在语法中明确声明某事为错误。

为了报告通用的语法错误，pegen 在 PEG 解析器中使用了一个常见的启发式方法：通用语法错误的位置报告在尝试匹配但失败的最远标记中。仅在解析失败（解析器在 C 中返回 NULL 或在 Python 中返回 None）但未引发异常时才执行此操作。

注意

正向和负向前瞻将尝试匹配标记，因此它们会影响通用语法错误的位置。在规则之间的边界处小心使用它们。

由于 Python 语法最初是作为 LL(1) 语法编写的，因此此启发式方法的成功率极高，但一些 PEG 特性可能会产生一些影响，例如 正向前瞻 和 负向前瞻。

为了生成更精确的语法错误，使用自定义规则。在上下文无关语法中，这也是一种常见做法：解析器将尝试接受一些已知不正确的结构，只是为了报告该结构的特定语法错误。在 pegen 语法中，这些规则以 invalid_ 前缀开头。这是因为尝试匹配这些规则通常会对解析产生性能影响（并且在某些棘手的情况下还会影响“正确”的语法本身，具体取决于规则的顺序），因此生成的解析器分两个阶段进行

1. 第一阶段将尝试解析输入流，而不考虑以 invalid_ 前缀开头的规则。如果解析成功，它将返回生成的 AST，并且不会尝试第二阶段。

2. 如果第一阶段失败，则会执行第二次解析尝试，包括以 invalid_ 前缀开头的规则。通过设计，此尝试无法成功，并且仅执行以给无效规则一个机会来检测可以引发自定义、更精确语法错误的特定情况。这也允许以一点性能来换取精确报告错误：鉴于我们知道输入文本无效，因此无需快速，因为解释器无论如何都会停止。

重要

在定义无效规则时

• 确保所有自定义无效规则都会引发 SyntaxError 异常（或其子类）。

• 确保所有无效规则都以 invalid_ 前缀开头，以免影响解析正确 Python 代码的性能。

• 确保当您引入无效规则时，解析器不会对常规规则表现得不同（有关更多信息，请参见 PEG 解析器工作原理部分）。

您可以在 Parser/pegen.h 头文件中找到用于引发特定语法错误的宏集合。这些宏还允许报告自定义错误的范围，这些范围将在报告错误时显示的回溯中突出显示。

提示

测试无效规则是否会在您期望时触发的一种好方法是测试在有效代码之后引入语法错误是否会触发该规则。例如

<valid python code> $ 42

应该触发 $ 字符中的语法错误。如果您的规则未正确定义，则不会发生这种情况。例如，如果您尝试定义一个规则来匹配 Python 2 风格的 print 语句以生成更好的错误消息，并且将其定义为

invalid_print: "print" expression

这看起来可行，因为解析器将正确解析 print(something)，因为它是一个有效的代码，并且第二阶段将永远不会执行，但是如果您尝试解析 print(something) $ 3，解析器的第一遍将失败（因为 $），在第二阶段，规则将匹配 print(something) 为 print，后跟括号中的变量 something，并且错误将报告在那里，而不是 $ 字符。

生成 AST 对象

CPython 使用的 C 解析器的输出由 Grammar/python.gram 语法文件生成，该输出是一个 Python AST 对象（使用 C 结构）。这意味着语法文件中的动作在成功时会生成 AST 对象。构造这些对象可能相当繁琐（有关如何构造这些对象以及编译器如何使用这些对象的更多信息，请参见 AST 编译器部分），因此使用了特殊的帮助器函数。这些函数在 Parser/pegen.h 头文件中声明，并在 Parser/action_helpers.c 文件中定义。这些函数允许您连接 AST 序列，从中获取特定元素或对生成的树进行额外的处理。

注意

操作绝不能用于接受或拒绝规则。在某些情况下，编写一个非常通用的规则，然后检查生成的 AST 以决定它是否有效可能很诱人，但这会使官方语法部分不正确（因为不包括操作），并且会使其他 Python 实现更难根据自己的需要调整语法。

作为一般规则，如果操作生成多行或需要比单个 C 代码表达式更复杂的内容，通常最好在Parser/action_helpers.c中创建一个自定义帮助器，并在Parser/pegen.h头文件中公开它，以便可以从语法中使用它。

如果解析成功，解析器必须返回一个有效的 AST 对象。

测试

有三个文件包含语法和解析器的测试

• Lib/test/test_grammar.py

• Lib/test/test_syntax.py

• Lib/test/test_exceptions.py

检查这些文件的内容以了解根据您要添加的新功能的性质将新测试放在哪个位置最合适。

可以在Lib/test/test_peg_generator目录中找到解析器生成器本身的测试。

调试生成的解析器

进行实验

由于生成的 C 解析器是 Python 使用的解析器，这意味着如果在向语法添加一些新规则时出现问题，您将无法再正确编译和执行 Python。当出现问题时，这会让调试变得有点困难，尤其是在进行实验时。

出于这个原因，最好先通过生成 Python 解析器来进行实验。为此，您可以转到 CPython 存储库中的Tools/peg_generator/目录，并通过执行以下操作手动调用解析器生成器

$ python -m pegen python <PATH TO YOUR GRAMMAR FILE>

这将在同一目录中生成一个名为parse.py的文件，您可以使用该文件解析一些输入

$ python parse.py file_with_source_code_to_test.py

由于生成的parse.py文件只是 Python 代码，因此您可以对其进行修改并添加断点以调试或更好地理解一些复杂的情况。

详细模式

当 Python 在调试模式下编译时（在 Linux 中运行配置步骤时添加--with-pydebug，或在 Windows 中调用PCbuild/build.bat脚本时添加-d），可以在生成的解析器中激活非常详细的模式。这对于调试生成的解析器和了解其工作原理非常有用，但一开始可能有点难以理解。

注意

在 Python 解析器中激活详细模式时，最好不要使用交互模式，因为它可能更难理解，因为交互模式涉及一些与常规解析相比的特殊步骤。

要激活详细模式，您可以在执行 Python 时添加-d标志

$ python -d file_to_test.py

这会将大量输出打印到stderr，因此最好将其转储到文件中以进行进一步分析。输出由具有以下结构的跟踪行组成

<indentation> ('>'|'-'|'+'|'!') <rule_name>[<token_location>]: <alternative> ...

每一行缩进量不同 (<indentation>)，具体取决于调用堆栈的深度。下一个字符标记跟踪的类型

• > 表示将尝试解析规则。

• - 表示解析规则失败。

• + 表示规则已正确解析。

• ! 表示检测到异常或错误，解析器正在展开。

<token_location> 部分表示标记数组中的当前索引，<rule_name> 部分表示正在解析哪个规则，<alternative> 部分表示正在尝试该规则中的哪个备选方案。

参考资料

[1]

福特，布莱恩 https://pdos.csail.mit.edu/~baford/packrat/thesis/

[2]

梅德罗斯等人 https://arxiv.org/pdf/1207.0443.pdf

[3]

沃思等人 http://web.cs.ucla.edu/~todd/research/pepm08.pdf

文档历史

帕勃罗·加林多·萨尔加多 - 原作者