多栈并行 · GSS · SPPF

GLR 与 GLL：把冲突变成分岔口

Earley 与 CYK 是从零设计的通用算法。另一条路更省事：拿现成的确定性引擎，把它「遇冲突就拒绝」的那一步改成「遇冲突就分叉」。

沿这条路走，LR 通用化成 GLR（Masaru Tomita，1985），LL 通用化成 GLL（Elizabeth Scott 与 Adrian Johnstone，2010）。两者互为镜像。

1 · 冲突格作为分岔口

GLR 的解析表按 LR(0) 或 SLR(1) 照常构造，但不要求无冲突：一个格子里有 $k$ 个动作就在此分出 $k$ 条路径，各自带一个栈并行推进。走不通的路径自然死掉，走通的路径各自产出一棵树。

图 1-1 · 同一份文法的四路对照：LR 与 GLR、LL 与 GLL。全部结论与计数来自各模块的真实 buildTable / parse。读数条给出 GLR 的冲突格数与活动栈峰值，并核对 GLR 与 GLL 的棵数是否一致。切到悬垂 else 可见两种 else 归属被同时产出。

LR 一页里 $E \to E + E$ 在四个等级下都有一处冲突，确定性 LR 因此拒绝了整份文法。图 1-1 里 GLR 在同一份文法上给出两棵树（n+n+n），冲突格数为 1、活动栈峰值为 7：那个唯一的冲突格就是分叉发生的地方，而峰值远大于 2 是因为本实现不做栈合并，每条路径独占一个栈（见 §2 的注）。

2 · 栈变成图：GSS

朴素的「每条路径一个栈」在分叉多时会爆炸： $k$ 个连续的冲突点产生 ${2}^k$ 个栈，而这些栈的大部分内容是相同的。

定义 2.1（图结构栈） graph-structured stack（GSS）把多个栈合并成一张有向图：共同的栈底只存一份，分叉处产生分支节点，重新汇合时分支合并。栈顶集合是图的一组前沿节点。

GSS 让 GLR 的时间与空间从指数降到多项式（最坏 $O(n^{k+1})$ ， $k$ 为最长产生式右部长度）。它是 Tomita 算法的核心贡献，也是 GLR 相对「回溯式 LR」的本质区别：后者重试时丢弃已完成的工作，GSS 让分支共享它。

对应地，输出侧也需要共享： $n$ 棵树里的公共子树不该被复制 $n$ 份。

定义 2.2（共享紧凑森林） shared packed parse forest（SPPF）是一张 DAG：相同区间上相同符号的节点只存一份；一个节点若有多种展开方式，则挂多个「打包节点」，每个代表一种。 $k$ 棵树的森林由此只占 $O(\text{poly}(n))$ 而非 $O(k)$ 空间。

注 · 本仓库的 GLR 与 GLL 实现是教学近似：用「多栈 + 去重」代替完整的 GSS，用枚举树代替 SPPF，并以 maxStacks / maxTrees 兜底。这足以呈现「冲突处分叉」这一主线与棵数的正确性（图 1-1 的棵数与 Earley、CYK 逐项一致），但不具备工业实现的复杂度保证。看到活动栈峰值这个计数时，它量的是近似实现的分叉宽度，而非 GSS 的节点数。

3 · GLL：镜像的一侧

GLL 对 LL 做同样的手术：预测表某格有多条候选时，不报冲突，而是同时展开全部候选。它同样需要两样共享结构：GSS 用来共享调用栈（自顶向下的栈是「还需要匹配什么」），SPPF 用来共享输出。

GLL 相对 GLR 的优势在可读性与可插手性：它保留了递归下降的形状，每个非终结符仍对应一段代码，错误消息与语义动作的写法由此与手写 parser 接近。这使它在需要「通用能力但要能改」的场合有位置，是 ANTLR 之外的另一条路线。

图 1-1 里可以看到镜像关系：左递归算术让 LL(1) 构表冲突，而 GLL 照样解析；歧义算术让 SLR(1) 构表冲突，而 GLR 照样解析。四个格子恰好构成一个方阵。

4 · 与 Earley 殊途同归

GLR 与 Earley 的产物完全一致（图 1-1 与歧义一页的棵数交叉验证），但路径不同：

	Earley	GLR
记账单位	位置 × item（含起点）	状态栈 + 前沿
文法预处理	无	构造 LR 表
无歧义文法上的行为	item 数为常数，退化线性	无分叉，退化为普通 LR
对文法形态的要求	无	无（表允许有冲突）

实践中的选择依据通常是「文法有多接近确定」。绝大部分构造合法、只在少数几处歧义的文法上，GLR 几乎全程走单栈，只在那几处分叉，常数因此比 Earley 小得多；而高度歧义的文法上两者都会退化到多项式高次，此时 Earley 的实现更简单。

5 · 落地位置

bison 的 %glr-parser、Elkhound（Scott McPeak 用于 C++ 解析）、以及 SDF/SGLR（Stratego 语言工作台）是 GLR 的主要工业实现。它们的共同动机是：C++ 与实际编程语言的文法难以整理成 LALR(1)，而把「解析时不确定、之后靠语义消解」这条路走通比反复改文法更实际。

Tree-sitter 的做法值得单独一提：它用 LR 表加有界的错误恢复与冲突处理，而非完整 GLR，因为编辑器场景更需要增量与容错，而不是接受任意歧义文法。这条取舍与本系列末段的增量解析与容错解析两页直接相关。

6 · 参考文献

Tomita, M. (1985). Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. Kluwer Academic Publishers.
Scott, E., & Johnstone, A. (2010). GLL parsing. Electronic Notes in Theoretical Computer Science, 253(7), 177–189.
Scott, E., & Johnstone, A. (2013). GLL parse-tree generation. Science of Computer Programming, 78(10), 1828–1844.
McPeak, S., & Necula, G. C. (2004). Elkhound: A fast, practical GLR parser generator. In Compiler Construction (LNCS 2985, pp. 73–88).