← 解析器 · 各路引擎、一门文法与编辑器要的那半边 / 同题横评：同一份文法喂给全部引擎 待审核 18 / 25
四象限 · 能力边界 · 交叉验证

同题横评：同一份文法喂给全部引擎

前面各页各自介绍了一台或两台引擎。这一页把它们摆在同一张表里，用同一份文法与同一个输入同时驱动，作为这条线的收口。

1 · 方向与确定性

各台引擎按两个维度分类。第一个维度是方向：自顶向下从起始符号出发猜产生式，自底向上从输入出发凑齐右部就归约。第二个维度是确定性：确定性方法要求文法无冲突、换来一遍扫描与线性时间，通用方法接受任意上下文无关文法、换来对歧义的支持。

自顶向下 自底向上 混合
确定性 LL(1) LR(0)/SLR(1)/LALR(1)/LR(1)、算符优先 left-corner（经典形态）
通用 GLL、Unger、PEG（有序选择） GLR、CYK Earley（chart 不分方向）

表达式专用的两台不在这个分类里：Pratt 与算符优先都只处理「运算符为操作数竞争」这一子问题，前者自顶向下、后者自底向上，但都不接受一般的上下文无关文法。

图 1-1 · 同一份文法与输入下的同题横评，每一格都是对应模块的真实 parse 或 buildTable 结果。可切换各份预设文法观察哪些引擎在哪一份上被拒绝；末行核对产树引擎的棵数是否一致。工作量列的计数口径各引擎不同，仅在同列内部可比。

2 · 读表规则

第一条：通用引擎的棵数必须逐项相同。 歧义是文法的性质，与解析方法无关。Earley、CYK、GLR、GLL、Unger、left-corner 的原理各异，若在同一份文法与输入上给出不同棵数，必有一台实现有缺陷。这条规则是本系列各引擎最有力的验收条件，它不需要人工写出期望树。

第二条：确定性引擎的「失败」有两种含义。 一种是构表阶段就拒绝整份文法（预测表或解析表有冲突），这与输入无关，是关于文法的结论。另一种是构表通过但该输入不被接受，这才是真正的语法错误。图 1-1 的结果列把两者分开显示，因为它们在工程上的含义完全不同：前者说明「换个方法或改文法」，后者说明「输入有问题」。

第三条：工作量列不能跨引擎比。 Earley 数 chart item、CYK 数 DP 基本操作、GLR 数活动栈峰值、其余数步：这些量纲不同，横条只在同一列内部有意义。跨引擎的性能比较需要统一的基准与真实输入，而各引擎的常数因子差异往往比复杂度阶差更能决定实际表现。

第四条：先看有没有触顶，再读任何数字。 上面三条都以「各引擎都算完了」为前提，而各引擎都带兜底上限，触顶的方式还不一样。歧义算术上给六台引擎统一传 maxTrees = 200 时实测：3 到 6 个操作数六台一致（2、5、14、42），7 个操作数时五台报 132 而 Unger 报 90，它先撞上的是步数上限而非树数上限；8 个操作数时 Unger 直接拒绝。工作量列同理，CYK 与 Unger 一页量出的 110 倍差距建立在一个已触顶的 Unger 步数上，只是下界。截断标记本身也不齐备：CYK 的 stats 没有 truncated 字段，它报的 200 与 Earley 报的 200 看着一样，前者却无从判断是否算完。

3 · 各份预设文法上的分野

图 1-1 的预设各自暴露一处边界：

  • 分层算术（左递归）：LL(1) 构表冲突，SLR(1) 起全部通过。左递归是自顶向下的边界。
  • 消左递归后的算术：全部通过。代价是树形右倾且多了辅助非终结符。
  • 歧义算术：确定性方法全部拒绝，通用引擎一致给出 2 棵树。歧义是确定性方法的绝对边界。
  • 非 SLR(1) 但 LALR(1)：SLR(1) 冲突而 LALR(1) 通过。lookahead 精度的边界。
  • 悬垂 else：与歧义算术同类，但它出现在真实语言里。
  • 配对括号：含 ε 产生式，考验各引擎对空产生式的处理。
  • 共享前缀：LL(1) 冲突（FIRST 相交），其余通过。这是「需要更多 lookahead」而非歧义。

4 · 怎么选

真实项目里的选择顺序通常是这样。

语言由自己设计：先手写递归下降，表达式层用 Pratt。这是 rustc、Clang、TypeScript、Go 的共同选择，理由在 递归下降 一页第 6 节：可插手性压倒一切。同时用 LL(1) 或 LALR(1) 给文法做一次体检，冲突落在哪里往往指出语法设计上真正含糊的地方。

语言已经存在且文法难整理：LALR(1) 生成器仍是最省事的（bison、LALRPOP）；整不出 LALR(1) 就上 GLR 或 PEG。CPython 从 LL(1) 换到 PEG 走的就是这条路径。

文法由第三方给定或需要接受歧义：Earley 或 GLR。前者实现简单、对文法零要求，后者在接近确定的文法上常数更小。

目标是编辑器而非编译器：优先级完全不同，增量、容错、无损语法树比「接受多大的文法类」重要得多。tree-sitter 用 LR 表加有界容错而非完整 GLR，就是这个取舍的结果。本系列末段那一组讲的就是这一半。

注 · 有一类需求会推翻上面全部结论：吞吐。当解析成为热点（日志管道、JSON API 网关、列式存储读取）时，方法的选择让位于数据布局与指令级并行。@vega/parsing 的 simd-json 模块复刻了 simdjson 的两阶段位并行架构：它连「逐字符状态机」都不做，用的是 64 位掩码一次处理 64 字节。那条路线不在本系列的四象限里，因为它优化的不是「能解析什么」，是「每秒能过多少字节」。

5 · 参考文献

  1. Grune, D., & Jacobs, C. J. H. (2008). Parsing Techniques: A Practical Guide (2nd ed.). Springer. 全书的方法分类图谱即本页表格的来源。
  2. Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley. 第 4 章。