predict / scan / complete · 任意 CFG

Earley：chart 上的三类动作

确定性方法的共同前提是「文法得先过关」。Earley 取消了这个前提：任何上下文无关文法都能直接解析，左递归、歧义、空产生式都不需要预处理。它由 Jay Earley 在 1970 年提出，是通用解析的第一个实用算法。

1 · chart 与 item

数据结构是一列集合，每个输入位置一个，合称 chart。

定义 1.1（Earley item） 一个 item 是三元组 $\langle A \to \alpha \cdot \beta,\; j \rangle$ ，含义是「产生式 $A \to \alpha\beta$ 的前半部分 $\alpha$ 已经匹配了输入的 $[j, i)$ 段，其中 $i$ 是本 item 所在的位置」。点表示识别进度， $j$ 称为该 item 的起点（origin）。

item 与 LR 的项很像，多出来的就是那个起点 $j$ 。有了起点，「这条产生式从哪里开始」被显式记住，Earley 因此不需要状态栈：一个 item 自带足够信息定位它覆盖的输入区间。

图 1-1 · chart 的逐位置视图。柱状图给出每个 state set 的 item 数，可拖动滑块查看任一集合的全部 item（• 是进度，@k 是起点）；末表量出 item 总数对输入长度的增长。chart 与计数均由 @vega/parsing/earley 的 recognize 直接给出。

2 · chart 的推进动作

从 $\langle S \to \cdot\,\gamma,\; 0 \rangle$ 出发，反复施加三条规则直到不动点：

predict：item 的点在非终结符 $B$ 之前时，把 $B$ 的每条产生式以点在最左、起点为当前位置的形式加入本集合。这一步相当于「预期接下来要识别一个 $B$ 」。

scan：item 的点在终结符 $a$ 之前且输入当前字符是 $a$ 时，把点右移一格的副本加入下一个集合。这是唯一推进输入位置的动作。

complete：item 的点已到末尾（ $A$ 识别完成，覆盖 $[j, i)$ ）时，回到集合 $j$ 找所有点在 $A$ 之前的 item，把它们的点右移一格加入本集合。这一步把「子结构完成」的消息回传给等待它的父结构。

输入读完后，若最后一个集合含起点为 0、点在末尾的起始符号 item，则接受。

左递归在此毫无障碍。 $E \to \cdot\,E + T$ 的 predict 会再产生 $E \to \cdot\,E + T$ 自身，但集合是集合：重复的 item 不会被加入第二次，predict 自然停在不动点。这就是 Earley 吃得下左递归的全部机制，与「集合去重」这一句话等价。

3 · 复杂度

定理 3.1 Earley 算法的时间复杂度：任意上下文无关文法 $O(n^3)$ ；无歧义文法 $O(n^2)$ ；LR(k) 一族的文法 $O(n)$ 。

三档的来源是 complete 动作的代价。位置 $i$ 的集合里至多 $O(n)$ 个 item（起点有 $n$ 种取法，产生式与点位是常数），每个 complete 要回扫集合 $j$ ，故单个位置 $O(n^2)$ ，总计 $O(n^3)$ 。文法无歧义时同一区间不会有多种覆盖方式，一档降为 $O(n^2)$ ；文法确定时每个位置的 item 数为常数，再降为 $O(n)$ 。

图 1-1 末表实测的正是最后一档：分层算术文法下每字符的 item 数几乎不随长度变化（长度 3 到 31 之间，item 总数 21、41、81、161，恰好线性）。这条性质使 Earley 在实践中远比 $O(n^3)$ 的名声好用：只有真正歧义的文法才会付出高次代价。

注 · Earley 原论文的 complete 步骤在处理可空非终结符时有一处缺陷（nullable 的 predict 可能漏掉已在同一位置完成的 item），由 Aycock 与 Horspool 在 2002 年指出并给出修正。这是通用算法里典型的边界情形： $\varepsilon$ 产生式让「起点等于当前位置」的 item 出现，破坏了「complete 只回看更早集合」这一隐含假设。

4 · 从 chart 到树

chart 只回答「接受与否」。要得到树需要第二遍：从终态 item 出发，沿 complete 关系反向追溯每个 item 是由哪些子 item 合成的。歧义文法在这一步会遇到「同一个 item 有多种合成方式」，逐一展开即得多棵树。

棵数可以指数增长（见歧义一页的卡塔兰数），实用实现给出的上限参数因此不是可选项而是必需品。

上限之外还有一类情形连上限都拦不住。 $S \to S\,S \mid \varepsilon$ 在空串上有无限多棵派生树（每棵 $S$ 都可以再裂成两个空的 $S$ ），实测 parse 返回 1 棵树且 stats.truncated 为假。这不是算错：chart 里 item 去重后本就只有有限多个 item，反向追溯时循环被自然切断，返回的是那个有限表示的一次展开。要留意的是 truncated 这个标记的含义仅为「树数没到 maxTrees 上限」，它不承诺「已穷尽」。判断棵数可信与否，得先确认文法在该串上的派生树是有限的。更好的做法是不枚举，而产出一个共享子结构的紧凑表示，即 SPPF，在 GLR 与 GLL 一页展开。

5 · 落地位置

Earley 的典型用户是「文法不受我控制」的场合。自然语言处理是原始动机，nearley（JavaScript）与 NLTK 的 chart parser 都在此列。另一类是需要接受用户提供的文法的工具：语法高亮器的通用后端、协议逆向、以及 Markdown 一类「没有非法输入」的格式的实验性实现。

它也常被当作参照实现。本仓库的 transform 模块用它验证文法变换保语言不变，cyk 用它当 CNF 转换的 oracle：因为它接受任意文法，可作为语言层面的判据而不受形态限制。这个用法在测试策略上很值得借鉴：手上有一台「慢但什么都吃」的引擎，就能给所有「快但挑食」的引擎当裁判。

6 · 参考文献

Earley, J. (1970). An efficient context-free parsing algorithm. Communications of the ACM, 13(2), 94–102.
Aycock, J., & Horspool, R. N. (2002). Practical Earley parsing. The Computer Journal, 45(6), 620–630.
Grune, D., & Jacobs, C. J. H. (2008). Parsing Techniques: A Practical Guide (2nd ed.). Springer. §7.2。