形式陈述

对 Chomsky 范式文法和长度 $n\ge1$$n\ge 1$ 的词 $w$$w$，CYK 建立集合 $T[i,\ell]$$T[i,\ell ]$：所有能推出子串 $w_i\cdots w_{i+\ell-1}$$w_i\cdots w_{i+\ell -1}$ 的非终结符。长度 1 由规则 $A\to w_i$$A\to w_i$ 初始化；对 $\ell>1$$\ell >1$，枚举切分 $k$$k$ 与规则 $A\to BC$$A\to BC$，若 $B\in T[i,k]$$B\in T[i,k]$ 且 $C\in T[i+k,\ell-k]$$C\in T[i+k,\ell -k]$，则加入 $A$$A$。最终 $w\in L(G)$$w\in L(G)$ 当且仅当 $S\in T[1,n]$$S\in T[1,n]$。朴素复杂度为 $O(n^3|G|)$$O(n^3|G|)$。

直觉

CNF 的每棵解析树根部都把区间分成左右两块。动态规划从短子串到长子串，缓存“哪种非终结符能生成这段”，避免重复枚举相同子问题。

例子与边界

对于输入 abba，表格先标出每个字符可由哪些变量产生，再逐层组合长度 2、3、4 的区间。若要恢复解析树，应记录产生式和切分点，而非只存布尔值。空串必须依据开始规则单独判断；未先转为 CNF 时，单位规则、长右部和 $\varepsilon$$\epsilon$ 规则会破坏上述递推。复杂度中的 $|G|$$|G|$ 取决于产生式组织方式，固定文法时常简写为 $O(n^3)$$O(n^3)$。

推论与应用

CYK 给出 CFG 成员资格的标准多项式算法，也可扩展为计数解析、概率文法的 Viterbi/inside 算法以及基于半环的通用解析框架。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 1–9。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。