有序选择 · memo 表 · 左递归死穴

PEG 与 packrat：把回溯压成线性

上一页的 combinator 有两处代价：回溯不带缓存，最坏情形指数级；文法是代码而非数据，无法被分析。Parsing expression grammar（PEG）由 Bryan Ford 在 2004 年提出，两处都动了。

它保留有序选择的语义，但把文法表示成数据，即一棵表达式树加一组命名规则，交由解释器驱动。数据形式使记忆化成为可能：解释器可以在求值任何规则之前先查一张表。

1 · 文法作为数据

PEG 的表达式只有九种：字面串、任意字符、字符类、顺序、有序选择、零或多、一或多、可选，以及两个前瞻断言。规则引用把它们串起来：

Expr   <- Term '+' Expr / Term
Term   <- Factor '*' Term / Factor
Factor <- '(' Expr ')' / Number
Number <- [0-9]+

/ 是有序选择，与上下文无关文法的 | 语义不同：它按顺序试，第一个成功者胜出，且一旦成功就不再回头。这条性质使 PEG 无歧义：任何输入至多一棵解析树，因为每个选择点的结果都由顺序唯一确定。

2 · packrat：每格至多算一次

定义 2.1（packrat parsing） 在解释器与文法之间插入一张以 $(\text{规则}, \text{位置})$ 为键的记忆表。求值一条规则前先查表：命中则直接返回缓存结果（含「此处失败」这一结果），未命中则求值并写入。于是每个 $(\text{规则}, \text{位置})$ 至多求值一次。

规则数是常数、位置数是 $n$ ，故总求值次数是 $O(n)$ ，这就是 packrat 把回溯压成线性的全部原理。代价是 $O(n)$ 的空间（表的大小与输入长度成正比），这是 Ford 论文标题里那句「backtracking without the cost」所指的交换。

图 2-1 · 同一份 PEG 文法、同一份输入，开关记忆化对照求值次数。观测口由引擎自带：memo 选项置假即退化为朴素回溯，stats.ruleEvals 给出每个「规则 @ 位置」的规则体求值次数。可调规模

n

观察嵌套括号形态下朴素回溯约每层乘四、packrat 只增常数；末项验证 packrat 不变量。

嵌套括号是暴露差距最快的形态。Factor <- '(' Expr ')' / Number 的两条候选在遇到左括号时都要往下走，失败后整段回退再试下一条；嵌套 $k$ 层则这种重叠自乘 $k$ 次。图 2-1 实测的朴素回溯步数为 224、928、3744、15008、60064、240288，每层约乘四；同一列 packrat 的步数是 34、49、64、79、94、109，每层固定加十五。

3 · packrat 不变量

「每个 $(\text{规则}, \text{位置})$ 至多求值一次」是一条可以直接断言的性质，它比性能数字更适合当验收条件：引擎的 stats.ruleEvals 记录每格的规则体求值次数，开启记忆化时其中每个值必须恰为 1。

这类不变量在性能优化里格外有用。「更快了」需要基准与统计显著性，而「每格恰一次」是一个布尔判断，任何一次回归都会立刻违反它。

不变量守住的范围值得看清：ruleEvals 的键是命名规则加位置，匿名节点（seq / alt / lit 这些内联表达式）不进记忆表，也不计入这个计数。在嵌套括号上实测，开启记忆化后 ruleEvals 里每一项确实都是 1，而 steps 仍随嵌套层数每层增加十五，那十五次就是每层那些匿名节点的重新求值。所以 packrat 给出的是线性，不是常数，而线性的斜率取决于文法怎么切分：把一段逻辑内联进一条大规则，它就落在记忆表之外；把它提成一条命名规则，才换来跨位置的缓存。规则边界在 PEG 里不只是可读性问题，它同时是记忆化的粒度。

4 · 左递归是硬边界

记忆表的键是「规则 @ 位置」，而左递归要求在同一位置递归引用自身：求值 Expr@0 需要先求值 Expr@0。查表时该格尚在计算中，既非命中也非未命中。

警示 · 朴素实现在此栈溢出，这是 packrat 最常见的事故形态。本模块的对策是显式检测：维护一个「正在求值」的集合，命中即报「检测到左递归」并给出规则名与位置，而非让调用栈崩掉。工程上的三条出路与递归下降一页相同：改写文法消左递归、把重复写成 *（PEG 里最常用）、或换用能吃左递归的方法。学术上另有 Warth 等人 2008 年的「左递归 packrat」扩展，用逐步增长种子值的办法支持左递归，但它牺牲了 PEG 语义的简明性，多数实现未采纳。

5 · 有序选择的语义陷阱

有序选择消灭了歧义，但也带来一类只在 PEG 里出现的缺陷：候选顺序写错时，parser 不报错，只是静默地少认一些输入。

经典例子是 'if' / 'ifelse'：输入 ifelse 会被第一条候选匹掉 if，剩下的 else 让外层失败，而作者本以为写了两个关键字。上下文无关文法里 | 无序，不会有这个问题；glob 与 regex 一族的贪婪匹配也有类似形态的坑。

注 · 一条工程规则：有序选择的候选之间若存在前缀关系，长者必须在前。这条约束无法由引擎检查（它无从知道作者的意图），只能靠约定与测试。peg.js 一类工具会对「不可达候选」给出警告，覆盖的是这个问题最明显的子集。

6 · 落地

Python 从 3.9 起把官方 parser 换成了 PEG（PEP 617），替掉原先的 LL(1)。动机不是性能，而是表达力：LL(1) 的一个 lookahead 限制迫使 CPython 的文法长期做各种改写，而 PEG 的无限前瞻与有序选择让文法可以照着语言规范写。这次替换也顺带解释了 PEG 的定位：它适合「文法由我掌握、且我想照直写」的场合。

其余落地包括 Rust 的 pest、Go 的 pigeon、以及 JavaScript 的 peggy（原 PEG.js）。与 parser combinator 一页的对照可以一句话总结：同源的有序选择回溯，combinator 留着指数风险不缓存，PEG 用记忆表把它压平，并因文法回到数据形式而重新获得可分析性。

7 · 参考文献

Ford, B. (2002). Packrat parsing: A practical linear-time algorithm with backtracking (Master's thesis). Massachusetts Institute of Technology.
Ford, B. (2004). Parsing expression grammars: A recognition-based syntactic foundation. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (pp. 111–122).
Warth, A., Douglass, J. R., & Millstein, T. (2008). Packrat parsers can support left recursion. In Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (pp. 103–110).
Bucher, G. (2019). PEP 617 – New PEG parser for CPython. Python Software Foundation.