CYK 算法

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

先看最小合并：对 $S\to AB$、$A\to a$、$B\to b$ 和输入 ab，有 $T[1,1]=\{A\}$、$T[2,1]=\{B\}$，因此唯一切点把 $S$ 放入 $T[1,2]$。

再用一个能生成非空偶数长度回文的 CNF 文法，完整分析字理路字Word · String从某个有限位置集到字母表的函数，即有限符号序列。 abba：

所有有效表项如下，列按起点 $i$ 排列，“—”表示区间超出输入，而 $\varnothing$ 表示合法区间没有可用非终结符。

长度二只有 bb 能由 $S\to BB$ 生成。长度三的 bba 在切分 bb|a 处用 $C\to SA$，得到 $C\in T[2,3]$。最后把 abba 切成 a|bba，用 $S\to AC$ 得 $S\in T[1,4]$，故接受。其余切点与规则不匹配，正是表中空集的来源。若要恢复这棵解析树，应同时记录所用规则和切点；恢复所有解析则要保存全部有效选择。

空串按开始规则单独判断。直接拿含单位规则、$A\to BCD$ 或 $A\to \epsilon$ 的一般文法套二分递推会漏解，因此先做保持语言的 CNF 转换。最坏 $O(n^3|G|)$ 是逐切点、逐规则检查的朴素界；固定文法时写为 $O(n^3)$，不意味着每个输入都达到该成本。

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

Earley解析理路Earley 解析算法Earley parsing · Earley algorithm用带起点的部分产生式及预测、扫描、完成三种规则进行通用CFG识别。不先转CNF，而以产生式点位置、起点和当前列保存部分推导；该页的左递归加法例与同列空规则闭包，可用来比较两种动态规划怎样避免重复工作。若需要按LR表保留冲突分支，GLR理路广义 LR 与图结构栈Generalized LR parsing · GLR parsing以图结构栈共享冲突分支，并以打包森林保存多种语法树的LR泛化方法。还要区分共享状态栈与保存语法树的打包森林。