CKY解析（也称为CYK，即Cocke-Younger-Kasami）是一种用于上下文无关文法的解析算法，采用自底向上解析和动态规划。它最早由酒井伊知郎于1961年发表，后来由约翰·科克、丹尼尔·扬格、笠井忠雄和雅各布·T·施瓦茨独立重新发现，并以他们的名字命名。该算法确定给定字符串是否可由文法生成，如果可以，则能构造该字符串的所有可能解析树。
CKY的标准版本仅适用于乔姆斯基范式（CNF）的上下文无关文法，其中每条产生式规则要么形式为A → BC（两个非终结符），要么为A → a（一个终结符）。任何不生成空字符串的上下文无关文法都可以通过算法转换为等价的CNF文法，因此这一限制原则上不影响算法的适用性。对于生成空字符串的文法，可以显式允许规则S → ε，其中S是起始符号。
CKY解析的重要性源于其最坏情况时间复杂度为O(n^3 · |G|)，其中n是输入字符串的长度，|G|是CNF文法的大小。这使其在渐近最坏情况行为方面成为最高效的解析算法之一，尽管其他算法在实际场景中可能具有更好的平均运行时间。
算法概述
该算法通过填充一个三维表P[l, s, v]来工作，其中每个条目是一个布尔值，表示从位置s开始、长度为l的子字符串是否可由非终结符R_v生成。表按子字符串长度递增的顺序填充，从长度为1的子字符串开始。
对于输入中的每个终结符，算法检查所有形式为R_v → a_s的单位产生式，并将相应的表条目标记为真。对于较长的子字符串，它考虑该子字符串的每一种可能划分，并检查是否存在产生式A → BC，使得B生成第一部分，C生成第二部分。如果存在这样的产生式，则将A的条目设为真。
伪代码
设输入为包含n个字符的字符串I：a1 ... an。
设文法包含r个非终结符R1 ... Rr，起始符号为R1。
设P[n,n,r]为布尔数组。将P的所有元素初始化为false。
设back[n,n,r]为回溯三元组列表的数组。将back的所有元素初始化为空列表。
对于每个s = 1到n
对于每个单位产生式Rv → as
将P[1,s,v]设为true
对于每个l = 2到n -- 跨度长度
对于每个s = 1到n-l+1 -- 跨度起始位置
对于每个p = 1到l-1 -- 跨度划分
对于每个产生式Ra → Rb Rc
如果P[p,s,b]且P[l-p,s+p,c]为真，则
将P[l,s,a]设为true，
将<p,b,c>追加到back[l,s,a]
如果P[n,1,1]为真，则
I是语言的成员
返回back -- 通过回溯back中的步骤，可以轻松构造字符串的所有可能解析树。
否则
返回“不是语言的成员”
示例
考虑以下CNF文法：
S → NP VP
VP → VP PP
VP → V NP
VP → eats
PP → P NP
NP → Det N
NP → she
V → eats
P → with
Det → the
N → fish
要解析字符串“she eats the fish with the fish”，算法首先标记所有长度为1的子字符串。例如，P[1,1,NP]设为真，因为NP → she，P[1,2,VP]设为真，因为VP → eats。然后处理长度为2的子字符串，如“she eats”，可通过S → NP VP推导，因此P[2,1,S]变为真。该过程继续处理更长的子字符串，考虑所有划分。最后，如果P[n,1,S]为真，则字符串被识别为语言的一部分，回溯指针允许重建解析树。
应用与变体
CKY解析广泛用于自然语言处理和计算语言学，特别是用于概率上下文无关文法的解析。该算法的变体已被开发出来以处理加权文法并改善平均情况性能。算法的动态规划方法也将其与其他解析方法联系起来，如Earley解析器，后者无需CNF转换即可处理任意上下文无关文法，但具有相似的复杂度。
在现代Artificial intelligence系统中，CKY解析已在很大程度上被基于Neural network的方法所取代，特别是用于Large language model的Transformer (architecture)模型。然而，该算法在形式语言理论中仍然是重要的基础技术，并在计算机科学课程中仍被教授。其动态规划和自底向上分析的原理也出现在其他领域，如Sequence-to-Sequence (Seq2Seq)模型和Beam Search解码。
算法的效率和清晰性使其成为解析和Machine learning教科书中的标准示例。MIT CSAIL和Stanford AI Lab等研究机构对其研究和应用做出了贡献，并且它在需要精确解析结构化数据的领域（如生物信息学和编译器设计）中仍然具有相关性。
局限性
CKY解析要求文法为乔姆斯基范式，这可能会增加产生式规则的数量和文法的大小。O(n^3)的最坏情况时间复杂度对于非常长的输入字符串可能过于昂贵，尤其是在实时应用中。此外，算法的空间复杂度为O(n^2 · r)，对于具有许多非终结符的文法可能很大。尽管存在这些局限性，CKY解析仍然是精确解析算法的基准，并且是研究上下文无关语言的关键概念。