Cocke-Younger-Kasami算法（CYK，或CKY）是计算机科学中用于上下文无关文法的解析算法。它由Itiroo Sakai于1961年首次发表，后来由John Cocke、Daniel Younger、Tadao Kasami和Jacob T. Schwartz独立重新发现，并以他们的名字命名。该算法采用自底向上解析和动态规划来确定给定字符串是否可由给定文法生成，并且还可以构建解析树。其最坏情况运行时间为O(n^3 · |G|)，其中n是输入字符串的长度，|G|是乔姆斯基范式文法的大小，使其在渐近最坏情况复杂度方面成为最高效的解析算法之一，尽管其他算法在实践中可能具有更好的平均性能。
CYK算法广泛用于自然语言处理和编译器设计中，其中解析是基本步骤。它尤其因其简单性和保证的多项式时间而受到重视，即使对于歧义文法也是如此。该算法对动态规划的依赖使其能够系统地处理所有可能的解析，这在编程语言的语法分析和人工智能系统中的句法解析等应用中非常有用。
历史背景
该算法由Itiroo Sakai于1961年首次描述，但通过John Cocke、Daniel Younger和Tadao Kasami在1960年代后期的独立重新发现而获得 prominence。Jacob T. Schwartz也对其发展做出了贡献。算法的名称反映了这些重新发现，缩写CYK源自Cocke、Younger和Kasami。该算法成为计算机科学教育中的标准主题，特别是在形式语言和自动机理论课程中。它的发展早于现代机器学习和神经网络解析方法，但作为基础技术仍然具有相关性。
标准形式：乔姆斯基范式
CYK算法的标准版本要求上下文无关文法采用乔姆斯基范式（CNF）。在CNF中，所有产生式规则的形式为A → BC（其中B和C是非终结符）或A → α（其中α是终结符）。此外，起始符号S可以有产生式S → ε以允许空字符串。任何不生成空字符串的上下文无关文法都可以转换为等价的CNF文法，如Sipser在1997年所示。这种转换是算法性的，并保留文法生成的语言。CNF要求简化了解析过程，因为它限制了子字符串可以被分割成两部分的方式，从而实现高效的动态规划。
算法描述
CYK算法通过填充一个三维表P[l, s, v]来操作，其中l是子字符串的长度，s是该子字符串的起始位置，v是非终结符。如果从非终结符R_v可以推导出从位置s开始的长度为l的子字符串，则条目P[l, s, v]设置为真。算法按子字符串长度递增的顺序进行，从长度1开始。
对于每个长度为1的子字符串，算法检查形式为R_v → a_s的单位产生式，其中a_s是位置s处的终结符。对于长度大于或等于2的子字符串，它考虑子字符串的每个可能分割成两部分，并且对于每个产生式A → BC，检查第一部分是否可从B推导出，第二部分是否可从C推导出。如果是这样，它将子字符串标记为可从A推导出。算法还维护一个回溯指针表以允许重建解析树。
最后，如果P[n, 1, 1]为真，则输入字符串被识别为语言成员，这意味着起始符号R_1可以推导出整个字符串。然后可以使用回溯指针构建所有可能的解析树。
示例
考虑以下CNF文法：
- S → NP VP
- VP → VP PP
- VP → V NP
- VP → eats
- PP → P NP
- NP → Det N
- NP → she
- V → eats
- P → with
- N → fish
- Det → the
该文法可以解析像“she eats the fish with the fork”这样的句子。CYK算法将首先标记单字子字符串：“she”作为NP，“eats”作为VP或V，“the”作为Det，“fish”作为N，“with”作为P，以及“fork”作为N。然后它组合子字符串：“the fish”作为NP（Det N），“eats the fish”作为VP（V NP），依此类推。最终，它确定整个句子可从S推导出，并且回溯指针揭示了解析树结构。
应用与意义
CYK算法在解析理论和实践中具有重要意义。它用于自然语言处理中的句法分析、编译器设计中的编程语言解析，以及生物信息学中的RNA二级结构预测。其最坏情况时间复杂度O(n^3)对于一般上下文无关文法解析在最坏情况下是最优的，尽管像Earley解析器这样的专门算法对于某些文法可能更高效。该算法的动态规划方法也使其适用于歧义文法，因为它可以枚举所有可能的解析。在现代人工智能中，CYK算法已被改编用于概率上下文无关文法和统计解析，其中它根据产生式的概率分布计算最可能的解析树。
局限性与扩展
标准CYK算法的一个局限性是它对CNF的要求，这可能会增加文法的大小并影响效率。对于非CNF文法存在扩展，例如Earley算法，它直接处理任意上下文无关文法。此外，CYK算法已扩展以处理加权文法和概率文法，其中每个产生式具有权重或概率，目标是找到具有最大权重或概率的解析。这些扩展用于语音识别和机器翻译。该算法还构成了深度学习模型中更高级解析技术的基础，尽管这些技术通常使用神经网络方法而不是显式文法规则。