DP 三角表 · CNF · 切分枚举

CYK 与 Unger：记住与不记住

Earley 的 chart 是「按位置记账」。另一条通用路线按区间记账：对输入的每一段子串，记下哪些非终结符能覆盖它。这条路线上有两台引擎，它们的算法几乎相同，差别只在一个字——记不记。

1 · Unger：直接枚举切分

Unger 的方法是最朴素的通用解析：要判断非终结符 $A$ 能否覆盖某段输入，就枚举 $A$ 的每条产生式，把该段按产生式右部的符号个数切成若干块，递归判断每块。

A 覆盖 s ?
  对 A 的每条产生式 A → X1 X2 … Xk:
    枚举把 s 切成 k 块的所有方式:
      若每个 Xi 都能覆盖第 i 块 → 成功

它的正确性与代价都一目了然：切分方式数是组合量级，且同一个「 $X$ 覆盖某段」的子问题会在不同的切分下被反复求解。图 1-1 末表量的就是这一点。

图 1-1 · Chomsky 范式、DP 三角表与两台引擎的步数对照。CNF 与计数来自 @vega/parsing/cyk 的 toCNF / recognize，Unger 步数来自 @vega/parsing/unger；三角表的格子内容按定义在页面侧填出（引擎只报计数、不暴露表），并与引擎的接受判定交叉核对。

2 · CYK：把结果记进三角表

CYK 做同样的枚举，但把每个 $(\text{起点},\text{长度})$ 的结果存进一张表，只算一次。

定义 2.1（CYK 表） 设输入长度为 $n$ ，表 $P[i][\ell]$ 存放「能覆盖 $\text{tokens}[i, i+\ell)$ 的非终结符集合」。基础格 $P[i][1]$ 由产生式 $A \to a$ 填入；归纳格 $P[i][\ell]$ 枚举切分点 $k$ （$1 \le k < \ell $），对每条产生式 $A \to B\,C$ ，若 $B \in P[i][k]$ 且 $C \in P[i+k][\ell-k]$ 则把 $A$ 加入。输入被接受当且仅当起始符号属于 $P[0][n]$ 。

表的形状是三角形：长度为 $\ell$ 的段有 $n-\ell+1$ 个起点，故行越往上越短。填表次序必须自底向上，因为归纳格依赖更短的段。

复杂度直接从三重循环读出： $O(n^2)$ 个格子，每格枚举 $O(n)$ 个切分点，每次遍历 $O(|G|)$ 条产生式，合计 $O(n^3\,|G|)$ 。这是通用解析的经典上界，与 Earley 的最坏情形同阶。

3 · CNF 是入场券

定义 2.1 里那句「对每条产生式 $A \to B\,C$ 」暗含一个前提：产生式右部恰好两个非终结符。这就是 Chomsky 范式的要求（另一形态是 $A \to a$ ）。

任意上下文无关文法都能转成 CNF 且语言不变（见文法变换一页），代价是规模膨胀。图 1-1 里分层算术的 6 条产生式转出 20 条，非终结符从 3 个增至 11 个，这个膨胀就落在复杂度的 $|G|$ 那一项上。

膨胀出来的中间非终结符会留在树上。@vega/parsing/cyk 的 parse 返回的是 CNF 文法的树，没有还原回原文法：n+n 得到的根是 S0，内部出现 E_bin、T_+ 这类转换期生成的符号，而 Earley 对同一份文法同一个串给出的是 E(E(T(F(n))) + T(F(n)))。两者的棵数仍然可以逐项对照（歧义一页正是这么用的），树形则不能直接比。要拿 CYK 的树与其他引擎对照，中间符号得先按转换记录折回去。

注 · 「二元」这个要求不是任意的。CYK 的归纳格靠一个切分点把区间分成两段，故右部必须恰好两项才能与之对应。右部三项就要枚举两个切分点，复杂度升到 $O(n^4)$ ；把长产生式拆成一串二元产生式，等于把这个额外的枚举代价转移成了更多的中间非终结符，总量反而更省，因为拆出的中间结果同样被表记住了。

4 · 记与不记的对照

把两台引擎并列，能看清动态规划到底做了什么：

	Unger	CYK
枚举内容	产生式 × 切分方式	产生式 × 切分点
子问题结果	不保存，每次重算	存进 $P[i][\ell]$ ，只算一次
方向	自顶向下递归	自底向上填表
文法形态	任意	须为 CNF
复杂度	指数	$O(n^3\,\vert G \vert)$

图 1-1 实测的步数（分层算术，n+n+… 形态）：长度 3 时 CYK 用 72 步、Unger 用 382 步，差 5.3 倍；长度 7 时 728 对 13878，差 19 倍。倍数本身在稳定放大。

第三档要单独说明，它的口径与前两档不同。长度 11 时 CYK 用 2728 步、Unger 报 300022 步，但这一档 Unger 的 stats.truncated 为真：三十万是引擎设的步数上限，不是它跑完所需的步数。所以 110 倍只是一个下界，真实倍数无从由这次运行得出。长度 15 时 Unger 报 300025，同样触顶，与 CYK 的 6840 步相除只会得到 43.9 倍这个更小的数字，倍数曲线由此在触顶后转头向下。读这张表要认准 truncated 标记出现的位置：它之后的每一档都不再是两台引擎的对比，而是「CYK 的真实步数」对「上限常数」的对比。

这组数字是「记住子问题的解」这一件事的完整价值证明。Unger 与 CYK 的关系，与斐波那契数的朴素递归和带记忆版本的关系完全同构，也与 PEG 与 packrat 一页 packrat 相对朴素回溯的关系同构。三处都是同一个模式：重叠子问题 + 记账。

5 · 它们各自的位置

CYK 在工程上的直接使用不多，原因是常数大、且必须先转 CNF（转换会打乱树形，还原成原文法的树需要额外记账）。它的位置主要在两处。一是作为通用解析复杂度上界的标准证明载体，二是在概率文法（PCFG）里：加权版 CYK 能在同一张表上做 Viterbi 式的最优树搜索，这是统计句法分析的主力算法。

Unger 的位置纯粹是教学的：它给出通用解析的最简正确算法，然后由它引出「为什么需要 DP」。本仓库把两者放在同一页，就是为了让这个对照可以被一眼量出来。

6 · 参考文献

Kasami, T. (1965). An efficient recognition and syntax-analysis algorithm for context-free languages (Technical Report AFCRL-65-758). Air Force Cambridge Research Laboratory.
Younger, D. H. (1967). Recognition and parsing of context-free languages in time $n^3$ . Information and Control, 10(2), 189–208.
Unger, S. H. (1968). A global parser for context-free phrase structure grammars. Communications of the ACM, 11(4), 240–247.
Grune, D., & Jacobs, C. J. H. (2008). Parsing Techniques: A Practical Guide (2nd ed.). Springer. §4.1（Unger）、§4.2（CYK）。