Earley 解析算法 | Codeboy's Blog

形式陈述

Earley算法直接处理有限上下文无关文法，不要求先转成Chomsky范式，也不要求分析表无冲突。给输入 $w_0\cdots w_{n-1}$ ，用半开区间 $[i,j)$ 表示从位置 $i$ 到 $j$ 之前的token。

加增广规则 $S'\to S$ ，建立chart列 $C_0,\ldots,C_n$ 。 $C_j$ 中的项目

[A\to\alpha\cdot\beta,i]

表示：从输入位置 $i$ 开始的一次 $A$ 识别，已用 $[i,j)$ 匹配了 $\alpha$ ，剩余还要识别 $\beta$ 。起点 $i$ 是项目的一部分；同一产生式和点位置可以同时有不同起点。

初始只放 $[S'\to\cdot S,0]\in C_0$ ，反复使用三条规则：

预测：若 $[A\to\alpha\cdot B\beta,i]\in C_j$ ，为每条 $B\to\gamma$ 加入 $[B\to\cdot\gamma,j]\in C_j$
扫描：若 $[A\to\alpha\cdot a\beta,i]\in C_j$ 且 $w_j=a$ ，把 $[A\to\alpha a\cdot\beta,i]$ 加入 $C_{j+1}$
完成：若 $[B\to\gamma\cdot,k]\in C_j$ ，对 $C_k$ 内每个等待 $B$ 的项目 $[A\to\alpha\cdot B\beta,i]$ ，把 $[A\to\alpha B\cdot\beta,i]$ 加入 $C_j$

每列先对预测和完成取闭包，再扫描到下一列；最终 $[S'\to S\cdot,0]\in C_n$ 当且仅当接受。项目按集合去重，不能因同一项目被再次推出就无限重复插入。

直觉

LR在读入之前把许多可能解析编译成状态；Earley在读入过程中把尚有机会完成的项目直接保留下来。不同推导若抵达相同产生式位置、相同起点与终点，就共享一个事实，这是动态规划消除重复工作的地方。

完成规则必须返回“这个 $B$ 当初从哪里开始”的列 $C_k$ ，而不是只看当前列。那里的等待项目才是真正调用它的上下文。把起点丢掉会把不相邻的输入片段拼起来，制造根本不存在的解析。

例子与边界

左递归与歧义都保留在 chart 中

取 $S\to S+S\mid\mathrm{id}$ ，输入 id+id+id，共五个token。记 $[A\to\alpha\cdot\beta,i]$ 为 $A\to\alpha\cdot\beta@i$ 。各列闭包为：

列	全部项目
$C_0$	$S'\to\cdot S@0$ ； $S\to\cdot S+S@0$ ； $S\to\cdot\mathrm{id}@0$
$C_1$	$S\to\mathrm{id}\cdot@0$ ； $S\to S\cdot+S@0$ ； $S'\to S\cdot@0$
$C_2$	$S\to S+\cdot S@0$ ； $S\to\cdot S+S@2$ ； $S\to\cdot\mathrm{id}@2$
$C_3$	$S\to\mathrm{id}\cdot@2$ ； $S\to S\cdot+S@2$ ； $S\to S+S\cdot@0$ ； $S\to S\cdot+S@0$ ； $S'\to S\cdot@0$
$C_4$	$S\to S+\cdot S@0$ ； $S\to S+\cdot S@2$ ； $S\to\cdot S+S@4$ ； $S\to\cdot\mathrm{id}@4$
$C_5$	$S\to\mathrm{id}\cdot@4$ ； $S\to S\cdot+S@4$ ； $S\to S+S\cdot@2$ ； $S\to S\cdot+S@2$ ； $S\to S+S\cdot@0$ ； $S\to S\cdot+S@0$ ； $S'\to S\cdot@0$

在 $C_0$ 预测 $S\to\cdot S+S@0$ 时会再次要求预测 $S$ ，但所得项目已经在集合中，因此左递归不会造成无限递归调用。

$C_3$ 同时保留“已经把前两个id组成一个 $S$ ”与“从位置2开始的 $S$ 还可以继续加”的信息。它们在后面形成 (id+id)+id 和 id+(id+id) 两棵语法树。最终项目去重不表示只剩一棵树：若要输出全部结构，必须在项目上保留所有完成来源，或建立共享打包森林；只保存一个布尔成员标记只能回答接受与否。

空规则需要同一列内的双向触发

令 $S\to AB,A\to\varepsilon,B\to\varepsilon$ ，输入为空。全部工作发生在 $C_0$ ：先预测 $S\to\cdot AB$ ，完成空 $A$ 后产生 $S\to A\cdot B$ ，再预测并完成空 $B$ ，最后得到 $S'\to S\cdot$ 。

更隐蔽的情形是：某个可空 $B$ 的完成项目已经处理过，后来同列才新增一个等待 $B$ 的项目。若实现只在“完成项目首次入队”时遍历当时的等待者，就会漏掉这对新搭配。安全的简单实现反复扫描到整列不再变化；高效实现分别索引等待者与完成者，任一侧新增时都匹配另一侧。

接受前缀不是接受完整输入

$C_1$ 已含 $S'\to S\cdot@0$ ，表示首个id本身是合法句子，但输入还没结束。只能在 $C_n$ 检查完整接受。对 id+，最后一列只有等待后一个 $S$ 的项目，没有完整增广项目，必须拒绝。

推论与应用

三条规则的可靠性都可按新事实归纳：扫描匹配一个真实token，预测只启动真实产生式，完成把相邻区间的推导拼接起来。完整性则按一棵给定解析树自底向上的区间结构归纳：各子树的完成事实会推进等待它们的父项目，最终生成根的完整项目。预测保证这些父子上下文在需要时存在。

令 $N=n+1$ ，并用 $g$ 表示增广文法的全部点位置数。项目最多 $O(gN^2)$ 个，因为每个点位置还带起点 $i$ 、终点 $j$ 。使用索引并保证每个等待/完成组合只处理常数次的实现，可给出 $O(g^2N^3)$ 的直接上界；固定文法时为 $O(N^3)$ 时间、 $O(N^2)$ 识别空间。这样也计入空输入在第零列完成预测与空规则闭包的成本。反复全列扫描便于手算小例子，但要得到上述界，仍需前述索引与组合去重。

CYK依靠CNF二分区间，Earley依靠带起点的部分右部；二者都能处理歧义，但都不能在多项式时间内显式打印可能指数多的全部解析树。压缩森林与逐棵输出的成本必须分开。

单元支线任务及解答

要求用上述chart证明 id+id+id 有两种分组，又用空文法说明空输入接受。解答中，最终 $S$ 的根分割点可在第一个或第二个加号：前者使用区间 $[0,1)$ 和 $[2,5)$ ，后者使用 $[0,3)$ 和 $[4,5)$ ，各子区间已有完成事实；两种根划分生成不同树。空文法的完成链为 $A[0,0)$ 、 $B[0,0)$ 、 $S[0,0)$ 、 $S'[0,0)$ 。

验收要写出起止位置和父项目来源，不能只凭字符串看起来有歧义；空输入例中所有位置都为0，也不能伪造一次扫描来推进。

参考资料

Jay Earley, “An Efficient Context-Free Parsing Algorithm,” CACM 13(2), 1970, 94–102；CMU原始学位论文
Stanford CS143, Advanced Parsing, 2012，Earley in Action部分：预测、扫描、完成和起点列
Elizabeth Scott, “SPPF-Style Parsing from Earley Recognisers,” Electronic Notes in Theoretical Computer Science 203(2), 2008, 53–67：从识别事实构造共享森林；本页的识别脚本不声称实现这篇森林算法

形式陈述 ​

左递归与歧义都保留在 chart 中 ​

空规则需要同一列内的双向触发 ​

接受前缀不是接受完整输入 ​

单元支线任务及解答 ​

反向链接

形式陈述

左递归与歧义都保留在 chart 中

空规则需要同一列内的双向触发

接受前缀不是接受完整输入

单元支线任务及解答