广义 LR 与图结构栈

两条解析分支可能只在最近几个符号的分组上有区别，栈底却完全相同。分叉时共享栈底，随后若又到达同一状态和输入位置，就共享栈顶，把差别保留成多条前驱路径。这形成一个有向无环图公理库有向无环图Directed acyclic graph · DAG不含有向环的有向图。：在本页无空串的模型中，每条边都指向更早的输入位置。

控制状态的共享与解析结果的共享是两回事。GSS回答“有哪些状态栈仍可继续”；共享打包解析森林回答“同一个区间有哪些语法树公理库语法树Parse tree · Derivation tree用有序树记录产生式层次，以完整例子区分推导顺序、文法歧义、优先级及抽象语法树。”。只保存GSS而丢掉归约来源，可以正确识别输入，却无法恢复全部结构。

森林用 $(A,i,j)$ 表示非终结符 $A$ 覆盖区间 $[i,j)$。不同产生式或分割点放在它下面的不同“打包分支”中；重复的子区间节点则复用。父节点保存所有分支，不会在第一次归约成功后覆盖旧分支。

保留两种分组，而不是替文法猜优先级 ​

取 $E\to E+E\mid E\ast E\mid \mathrm{id}$，输入 id+id*id。此文法没有声明乘法优先；GLR的正确结果必须保留两种分组。

消费前三个token id+id 后，下一token是 *。此时既可按 $E\to E+E$ 归约已经完成的加法，也可移进乘号继续扩展右侧 $E$。两条路径分别形成

第一条在位置3就把 $[0,3)$ 归约为 $E$；第二条把起于位置2的右侧表达式继续延伸到位置5。最终森林根 $(E,0,5)$ 有两个分支：

其中 $E[0,3)$ 是加法，$E[2,5)$ 是乘法。三片 id 叶各只需保存一次。这张表已足以恢复两棵树；若强制只保留第一分支，就额外加入了文法没有声明的消歧策略。

基础校验实现使用SLR多动作表和上述GSS闭包，在长度不超过7的全部3280个 id,+,* token串上，与独立Earley识别器公理库Earley 解析算法Earley parsing · Earley algorithm用带起点的部分产生式及预测、扫描、完成三种规则进行通用CFG识别。得到相同接受结果。这个有限核对验证了例子和实现，不替代任意长度输入上的正确性证明。

新边不能被“这个状态处理过了”吞掉 ​

假设顶点 $(q,i)$ 已存在并处理过一次归约。随后另一分支给它增加一条前驱边，便可能新增一条长度为 $k$ 的可弹出路径，落到不同的 $(p,j)$，进而产生新GOTO状态。仅把“顶点处理过”作为永不再处理的标志，会漏掉这条解析。

正确调度以待处理的归约路径或新边所触发的组合为单位；最简单的教学实现反复重扫直到边集稳定。森林中新加的分组若不改变GSS边，也仍要保存在已有森林节点下，不能因为控制图未改变就丢弃。

空规则为何另需处理 ​

$A\to \epsilon$ 会在同一输入位置加入边，可能让简单的“边总向更早位置”性质失效；可空后缀还使归约触发与新边到达顺序相互影响。RNGLR利用right-nulled项目并配套严密的调度处理这些情形，二叉化的BRNGLR进一步控制复杂度。

因此“GLR可以处理一般CFG”是关于完整算法家族的能力，不等于任意十几行分叉栈代码都覆盖所有空产生式、单位循环和歧义森林。使用库时应检查它具体实现的是哪一种变体。

正确性可由栈路径不变量说明：初始GSS只有初始栈；每条移进边对应一条合法LR移进；每条归约边对应一条真实可弹出的右部路径，所以不会凭空造出栈。反过来，每条非确定LR执行都能逐步在GSS中找到对应路径，因为算法没有丢弃冲突动作，并对新增路径完成闭包。accept因此对应至少一棵完整解析树。

只保存一份显式栈列表时，歧义可能让分支数指数增长。GSS把控制节点数限制为至多 $(n+1)q$，其中 $q$ 是LR状态数；边数粗界为其平方。不过枚举归约路径仍有成本，不能从节点少直接推出总时间为二次。

对本页的朴素闭包实现，令最大产生式长度为 $r$、产生式数为 $p$，取 $N=(n+1)q$。每个位置至多有 $q$ 个顶点及 $qN$ 条向后边；一次全扫描每条规则的长度至多 $r$ 的路径，粗计 $O(pqr{N}^r)$。每轮非终止扫描至少增一节点或边，至多 $O(qN)$ 轮；遍历 $n+1$ 个位置得到保守界 $O((n+1)p{q}^{2}r{N}^{r+1})$。固定文法时这是多项式，但远非最优。

经过二叉化、去重的专门GLR变体可获得固定文法下 $O(n^3)$ 的最坏时间；这不是上述朴素路径枚举自动拥有的界。输出所有独立树仍可能指数多，压缩森林和展开输出必须分别计费。