Python 3.9 中的 PEG 语法分析算法

0 题外话

若文章有后续更新，可以在我的博客上看到。
pre 视频在这里。

1 PEG: Parsing Expression Grammar

1.1 定义

1.1.1 语法

形式上，一个解析表达文法由以下部分组成：

• 一个有限的非终结符的集合 \(N\)
• 一个有限的终结符的集合 \(\Sigma\)，和 \(N\) 没有交集
• 一个有限的解析规则的集合 \(P\)
• 一个被称作开始表达式的解析表达式 \(e_s\)

1.1.2 语义

PEG 与 CFG 最关键的不同是，PEG 的选择操作符是有序的。如果第一个选项匹配成功，则忽略第二个（以及之后的）选项。因此 PEG 的有序选择是不可交换的。

1.2 解释

解析表达文法里每一个非终结符本质上表示递归下降解析器里面的一个解析函数，其对应的解析表达式展示了这个函数包含的代码内容。
从原理上来说，每一个解析函数接受一个输入字符串作为参数，返回其中一个结果：

• 成功，函数可能向前移动或者消耗一个或多个输入字符串的字符
• 失败，不消耗字符

序列操作符 \(e_1e_2\) 首先调用 \(e_1\)，如果 \(e_1\) 成功，接着对 \(e_1\) 消耗盛夏得输入字符串调用 \(e_2\)，最后返回结果。如果 \(e_1\) 或者 \(e_2\) 失败，那么序列表达式 \(e_1e_2\) 失败。
选择操作符 \(e_1/e_2\) 首先调用 \(e_1\)，如果 \(e_1\) 成功，立刻返回结果。否则如果 \(e_1\) 失败，选择操作符回溯到输入字符串匹配 \(e_1\) 的原始位置，调用 \(e_2\)，最后返回 \(e_2\) 结果。
与上下文无关文法和正则表达式不同的是，在 PEG 里这些操作符总是执行贪婪的行为，那就是消耗尽可能多的输入，而且绝对不回溯。正则表达式一开始执行贪婪匹配，但是如果整个正则表达式失败后，会回退并尝试短一些的匹配。

1.3 解析器

1.3.1 实现

所有的解析表达文法都能够被转化为递归下降解析器。由于 PEG 提供了理论上不受限制的向前检查能力，所以最终得到的解析器是可以避免最坏情况下指数级时间复杂度的。通过保存增量解析步骤的结果和确保每一个解析函数在同一个输入位置只被调用一次，就可以把任意解析表达文法转化成一个 Packrat Parser，可以实现线性时间复杂度解析，代价是占用大量的空间。

1.3.2 细谈 Packrat Parser

Packrat Parser 是一种结构上类似递归下降解析器的语法解析器，区别是解析过程中，它记下所有互相递归调用的函数的中间结果。因为保存了这些信息，Packrat Parser 拥有以线性时间复杂度解析多数上下文无关文法和所有解析表达文法的能力。类似的东西让我想起蒋炎岩老师在 ICS 实验课上讲到过的汉诺塔问题，当时他展示了如何不用递归解决汉诺塔，用的就是直接对栈的操作。当然可能真实原理差了很多，但是同样是处理递归问题的一些小小的震撼，因此在这提一嘴。

2 PEG 与 LL (1)

2.1 预测 vs. 回溯

我们知道，Cpython 3.8 以前采用的都是一个叫 pgen 的分析器，它基于的是 LL (1) 分析算法。而 LL (1) 分析器是一种预测型分析器，即每次可以"预见"往后数 1 个的 token，来确定使用哪条规则展开。这个过程是在实际递归调用之前的，因此可以保证解析函数不会被重复调用，并且任意输入都能在线性时间内完成。那么既然有这么大的时间优势，LL (1) 算法必然也会存在一定的局限性。那就是它对文法的要求很高，即很多上下文无关文法是没有办法用 LL (1) 等预测型算法解析的。比如有不能含有左递归、必须"left-factoring"等限制条件。

2.2 pgen 的问题

这里列举了一些 Rossum 要更改 parser 的原因，其中可能并非完全与 LL (1) 自身的性质相关，只是想对 CPython 性能的进一步提升有所帮助。

2.2.1 复杂的 AST 解析

当下的解析器（pgen）中，AST 生成过程和生成树的特定形状有着巨大的耦合性。这使得生成 AST 的代码特别复杂，因为很多的行为和选择是隐式的。例如，AST 生成代码根据给定的解析节点中存在的子节点的数量，来知道产生规则的哪些选择。这使得代码难以遵循，因为这个属性与语法文件没有直接关系，而是受到实现细节的影响。因此，相当数量的 AST 生成代码需要处理检查和推理它所收到的解析树的特定形状。

2.2.2 中间生成树

这个问题在于创建一个解析树或具体语法树的中间过程，然后将其转换为抽象语法树。虽然 CST 的构建在解析器和编译器管道中非常常见，但在 CPython 中，这个中间的 CST 并没有被其他东西使用（它只是被解析器模块间接地暴露出来，而且 CST 生产中的一小部分代码在模块中被重复使用，这令人惊讶）。更糟糕的是：整个树被保存在内存中，保留了许多由具有单个子节点的链组成的分支。这已被证明会消耗相当多的内存。不得不在语法和 AST 之间产生一个中间结果，这件事情是我们不希望看到的，并且它还使得 AST 生成步骤更加复杂，无疑给维护增加了相当大的负担。

3 PEG parser 给 Python 带来了什么

3.1 支持左递归

我们知道，PEG 文法本身是不支持左递归的。但是当使用的是 Packrat Parser 的时候，就能通过一些改进做到这一点。那么这是如何做到的呢？这篇论文里给出了详细证明，我在这里稍作解释。下面展示的这个方法展示了如何做到中间结果的存储，即将 (R, P) 这对 map 存入 memo table，只要 memo table 中存在这个记录，就直接返回结果，一定不会再进行语法分析，从而保证了时间复杂度是线性的。

首先需要搞清楚的是本身不能支持左递归的原因。假设 Apply-Rule(expr, 0) 是对 expr 这条输入字符串的分析，其中 0 是当前处理字符的位置。考虑将“1-2-3”输入下面这个规则：

expr : expr '-' num          # 1
		 | num                   # 2   

这里比较灾难的一点是，当执行 Apply-Rule(expr, 0) 时，先会去查找 Memo(expr, 0)，即用来保存中间结果的 memo table。当然此时表还是空的，因此结果会是 null。这时接着使用 1 进行匹配，进入了一个无限递归的过程，因为只有当匹配 1 的结果是失败时才会进行 2 的匹配，这是由 peg 分析器的特性所决定的。

要能够支持左递归，一个简单点的办法是在进入 rule 之前先预存一个 fail 的结果，如上图所示。当首次执行 Apply-Rule(expr, 0) 时，向 memo table 中加入 FAIL，接着进入 Eval(R.body)。此时由于先前存入的 FAIL，使得能够知道规则 1 匹配不成功，于是进入规则 2，故能消耗掉“1”，剩下“-2-3”。
考虑一下刚刚对 expr 在位置 0 进行的操作：

• parser 的当前位置更新到了 1
• parser 的 memo table 中将 (expr, 0) 更新为 (expr->num->1, 1)
  上述行为我们称为 seed parse 。实际上当我们有了这个 seed，parser 就能接着往下进行，这个过程就变为了迭代。论文中把这个迭代过程称为 growing the seed，十分生动形象。而剩下需要做的就是分辨出什么时候是左递归，来让 memo 记录下来即可。文章中抽象了一个 Grow-LR 方法，只要遇到的是递归，就调用这个方法得到最终结果。
  上述这些是直接递归问题，非直接的递归就不在这里赘述了，感兴趣可以阅读一下原文。

回到 python 上，python 使用的 peg parser 不仅能够实现简单的左递归规则，还有如下非直接左递归：

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

以及“隐藏左递归”：

rule: 'optional'? rule '@' some_other_rule

3.2 Grammar Actions

为了避免掩盖语法和 AST 生成之间的关系的中间步骤，提议的 PEG 解析器允许通过语法动作直接为规则生成 AST 节点。语法动作是特定于语言的表达式，当语法规则被成功解析时就会被评估。这些表达式可以用 Python 或 C 语言编写，这取决于解析器生成器的预期输出。这意味着如果想用 Python 和 C 语言生成一个解析器，应该写两个语法文件，每个文件都有一组不同的动作，除了上述动作外，两个文件中的其他内容保持一致。作为一个带有 Python 动作的语法的例子，解析器生成器中解析语法文件的部分是从带有 Python 动作的元语法文件中引导出来的，这些动作在解析后生成语法树。

在为 Python 提出的新的 PEG 语法的具体情况下，有了动作就可以直接描述 AST 是如何在语法本身中组成的，使其更加清晰和可维护。这个 AST 的生成过程是通过使用一些辅助函数来支持的，这些函数将常见的 AST 对象操作和其他一些与语法没有直接关系的必要操作分解出来。

4 Reference

Construction of LL(1) Parsing Table - GeeksforGeeks

Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (mit.edu)

thesis.pdf (mit.edu)

pepm08.pdf (ucla.edu)