CYK 算法

CYK 把“某个非终结符能否生成这一整段子串”拆成所有更短区间的组合。Chomsky 标准形把产生式统一为 $A\to BC$ 或 $A\to a$，所以每棵解析树的根部都把长区间在某个位置切成左右两段；动态规划恰好从短子串到长子串枚举这些切点与中间非终结符，并缓存“哪种非终结符能生成这段”，避免重复求解相同子问题。表格中的每个集合不是一棵具体语法树，而是对所有可能解析的压缩表示。

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

设文法含 $S\to AB$、$A\to a$、$B\to b$，输入为 ab。长度为 $1$ 的表项分别有 $A\in T[1,1]$、$B\in T[2,2]$；长度为 $2$ 时在切点 $1$ 看到 $A,B$，故把 $S$ 放入 $T[1,2]$，字符串被接受。若同一表项能由多个产生式或切点得到，CYK 仍只需记录非终结符；要恢复所有解析树，则必须同时保存回溯指针。

算法依赖标准形。直接拿含 $A\to BCD$ 或 $A\to \epsilon$ 的一般文法套入二分递推会漏解；通常先做等价变换，并单独处理空串。最坏 $O(n^3|G|)$ 是朴素实现的界，不意味着每个文法和输入都达到该成本。

CYK 是 动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。 在形式语言中的典型实例，也是 CFG 成员资格的标准多项式算法，证明了固定 上下文无关文法公理库上下文无关文法Context-free grammar · CFG每条产生式左侧是单个非终结符的生成系统。 的成员问题可在多项式时间解决。它以 Chomsky 标准形公理库Chomsky 范式Chomsky normal form · CNF for grammars除空字特殊规则外，每条产生式只形如 A→BC 或 A→a 的上下文无关文法标准形。 为接口，可扩展为计数解析、概率文法的 Viterbi/inside 算法、求最高概率解析、构造共享解析森林，以及基于半环的通用解析框架。