j=1  j=2  j=3
i=1 {Det}  -    -
i=2  -   {N}   -
i=3  -    -   {V}

    j=1  j=2    j=3
i=1 {Det} {NP}   -
i=2  -   {N}    {}
i=3  -    -    {V}

基于动态规划的CYK（Cocke-Younger-Kasami）句法分析算法详解 1. 算法题目描述 CYK算法是一种基于动态规划的、用于上下文无关文法（Context-Free Grammar, CFG）的句法分析算法。它的核心任务是：给定一个输入句子（一个单词序列）和一组已知的上下文无关文法规则，判断这个句子是否能够被该文法生成（即句子是否符合文法），并找出所有可能的句法分析树（即句子的语法结构）。 CYK算法要求文法必须是乔姆斯基范式（Chomsky Normal Form, CNF）。CNF是一种规范形式，其中每条产生式规则只能是以下两种形式之一： 非终结符 → 非终结符 非终结符 （例如： NP -> Det N ，表示一个名词短语可以由一个限定词和一个名词组成） 非终结符 → 终结符 （例如： N -> 'cat' ，表示一个名词可以生成具体的单词“cat”） 任何上下文无关文法都可以转化为等价的CNF形式，这使得CYK算法具有通用性。该算法因其发现者Cocke、Younger和Kasami而得名。 2. 解题过程循序渐进讲解 步骤1：问题定义与输入准备 假设我们有： 输入句子 S ：长度为 n 的单词序列，例如 "the cat sat" ，这里 n=3 。 单词列表 ： [w1, w2, ..., wn] = ["the", "cat", "sat"] 。 文法规则集 G（CNF格式） ： S -> NP VP NP -> Det N VP -> V NP Det -> 'the' N -> 'cat' V -> 'sat' （注： S 表示句子， NP 名词短语， VP 动词短语， Det 限定词， N 名词， V 动词） 我们的目标是：构建一个表格（或称图表），来记录句子中每一个 子串 （从第i个词到第j个词）可以由哪些 非终结符 推导出来。 步骤2：构建动态规划表格 我们构建一个二维表格 P ，其维度为 (n+1) x (n+1) 。更常见的是构建一个上三角矩阵 P[i][j] ，其中： i 表示子串的起始位置（从1开始计数）。 j 表示子串的结束位置（从1开始计数）。 单元格 P[i][j] 中存储一个 集合 ，包含了所有能够推导出子串 words[i...j] 的非终结符。 对于句子 "the cat sat" (n=3)，我们构建一个4x4的表格，但只关注 i <= j 的部分。 初始时，表格是空的。 步骤3：初始化（处理长度为1的子串） 这是动态规划的“基础情况”。我们处理所有单个单词的子串（即 i == j 的情况）。 对于每个位置 i ，我们看单词 w_i 。 查找文法 G 中所有形如 X -> w_i 的规则（即非终结符直接生成这个终结符/单词的规则）。 将满足条件的非终结符 X 放入单元格 P[i][i] 。 以我们的例子为例： P[1][1] ：单词是 "the" 。查找规则， Det -> 'the' 匹配。所以 P[1][1] = {Det} 。 P[2][2] ：单词是 "cat" 。规则 N -> 'cat' 匹配。所以 P[2][2] = {N} 。 P[3][3] ：单词是 "sat" 。规则 V -> 'sat' 匹配。所以 P[3][3] = {V} 。 此时表格如下（ - 表示空或未计算）： （注： i 是行， j 是列，我们只填对角线） 步骤4：递推计算（处理更长的子串） 这是算法的核心。我们从长度为2的子串开始，一直计算到长度为n的整个句子（ l 表示当前子串长度）。 外层循环 ：遍历子串长度 l = 2 to n 。 中层循环 ：遍历子串的起始位置 i = 1 to n-l+1 。确定了 i 和 l ，子串的结束位置 j = i + l - 1 也就确定了。我们现在要计算 P[i][j] 。 内层循环 ：遍历一个“分割点” k = i to j-1 。这个分割点 k 将子串 words[i...j] 切分成两个更短的子串： words[i...k] 和 words[k+1...j] 。 关键递推逻辑 ： 对于每一对 (i, j, k) ，我们已经（在之前的步骤中）计算出了： left_candidates = P[i][k] （能生成左半部分的非终结符集合） right_candidates = P[k+1][j] （能生成右半部分的非终结符集合） 然后，我们 遍历文法G中所有形如 X -> Y Z 的规则 （即两个非终结符生成一个非终结符的规则）： 如果存在一条规则 X -> Y Z ，使得 Y ∈ left_candidates 且 Z ∈ right_candidates 同时成立，那么就意味着： Y 可以生成左子串， Z 可以生成右子串，而 X -> Y Z 这条规则允许 X 生成这两个部分的连接。因此， X 可以生成整个子串 words[i...j] 。 将这样的非终结符 X 加入到集合 P[i][j] 中。 以我们的例子计算 l=2 ： l=2 ： i=1, j=2 （子串 "the cat" ）： k 只能取 1 。 left = P[1][1] = {Det} , right = P[2][2] = {N} 。 查找规则：是否存在 X -> Det N ？是的， NP -> Det N 匹配。 因此， P[1][2] = {NP} 。 i=2, j=3 （子串 "cat sat" ）： k 只能取 2 。 left = P[2][2] = {N} , right = P[3][3] = {V} 。 查找规则：是否存在 X -> N V ？我们的文法中没有这样的规则。 因此， P[2][3] = {} （空集）。 表格更新为： 步骤5：计算整个句子（ l=3 ） l=3 , i=1, j=3 （整个句子 "the cat sat" ）： 我们需要遍历所有分割点 k = 1, 2 。 当 k=1 ： left = P[1][1] = {Det} , right = P[2][3] = {} 。 由于 right 为空，无法找到匹配 X -> Y Z 的规则。无结果。 当 k=2 ： left = P[1][2] = {NP} , right = P[3][3] = {V} 。 查找规则：是否存在 X -> NP V ？我们的规则是 VP -> V NP ，顺序是反的，不匹配！CNF规则是严格的 A -> B C ，顺序很重要。所以不匹配。 等一下 ，我们漏了一条规则！仔细看文法： VP -> V NP 。这意味着左部分是 V ，右部分是 NP 。而我们这里的 left 是 NP ， right 是 V 。顺序对不上，所以没有规则能直接组合 NP 和 V 。 但是，句子 "the cat sat" 应该是 (NP (Det the) (N cat)) (VP (V sat)) ？这看起来不对，因为 sat 是不及物动词吗？我们的示例文法 VP -> V NP 暗示 sat 是及物动词，需要一个宾语NP。让我们修正一下文法，让例子更完整。 让我们修正例子，让句子是 "the cat saw a dog" ，并增加规则。但为了简化，我们回到原句并修正文法，假设 sat 是不及物动词： 增加规则： VP -> V （这也是CNF，因为 V 是终结符？不， VP -> V 不是标准CNF。标准CNF要求右侧要么是两个非终结符，要么是一个终结符。 V 是非终结符，所以 VP -> V 不是CNF。我们需要引入一个中间规则。为了让例子简单，我们假设有一个新的终结符规则，但这会破坏结构。为了教学清晰，我们采用一个更简单的可解析例子。 让我们用一个真正能运行的简单例子 ： 句子： "the cat runs" 文法（CNF）: S -> NP VP NP -> Det N VP -> V // 注意 ：这不是标准CNF！ V 是非终结符。为了符合CNF，我们需要写成 VP -> V 吗？不行。或者写成 VP -> V 和 V -> 'runs' 。 VP -> V 是 A -> B 形式，不是 A -> B C 也不是 A -> a 。所以需要转换。一个真正的CNF文法应该是： S -> NP VP NP -> Det N VP -> Verb // 引入新非终结符 Det -> 'the' N -> 'cat' Verb -> 'runs' 现在重新用CYK分析 "the cat runs" ： 初始化： P[ 1][ 1] = {Det} ( the ) P[ 2][ 2] = {N} ( cat ) P[ 3][ 3] = {Verb} ( runs ) l=2 : i=1,j=2 : k=1 , left={Det}, right={N} -> 规则 NP -> Det N 匹配 -> P[ 1][ 2 ]={NP} i=2,j=3 : k=2 , left={N}, right={Verb} -> 查找规则 X -> N Verb ？没有匹配。P[ 2][ 3 ]={} l=3 (整个句子): i=1,j=3 : k=1 : left={Det}, right=P[ 2][ 3 ]={} -> 无 k=2 : left=P[ 1][ 2]={NP}, right=P[ 3][ 3 ]={Verb} 查找规则： X -> NP Verb ？没有。 等等，我们的规则是 VP -> Verb 和 S -> NP VP 。我们需要组合。 实际上，在 k=2 时，左部分 NP 生成了 "the cat" ，右部分 Verb 生成了 "runs" 。但 Verb 本身不是 VP 。根据规则 VP -> Verb ， Verb 能推出 VP 吗？在CYK表格中，P[ 3][ 3]只包含了能直接生成单词 "runs" 的非终结符，也就是 Verb 。 VP 并不在P[ 3][ 3]里，因为 VP 不是直接生成 "runs" ，而是通过 Verb 间接生成。 CYK算法在递推时，只查 A -> B C 规则 。 VP -> Verb 不是这种形式，所以不会在递推中直接用。我们需要把文法完全转换为CNF。 真正的CNF转换 ：规则 VP -> Verb 是单位产生式（unit production），不是CNF。我们需要消除它。因为 Verb -> 'runs' ，我们可以直接将 VP 和 'runs' 用规则 VP -> 'runs' 连接？但 VP 是一个非终结符， 'runs' 是终结符， VP -> 'runs' 是合法的CNF（ A -> a 形式）。是的！所以修正文法为： S -> NP VP NP -> Det N Det -> 'the' N -> 'cat' VP -> 'runs' // 现在是 A -> a 形式 现在重新分析 "the cat runs" ： 初始化： P[ 1][ 1 ] = {Det} P[ 2][ 2 ] = {N} P[ 3][ 3] = {VP} // 因为 VP -> 'runs' l=2 : i=1,j=2 : k=1 , left={Det}, right={N} -> NP -> Det N -> P[ 1][ 2 ]={NP} i=2,j=3 : k=2 , left={N}, right={VP} -> 查找 X -> N VP ？没有规则。P[ 2][ 3 ]={} l=3 : i=1,j=3 : k=1 : left={Det}, right=P[ 2][ 3 ]={} -> 无 k=2 : left=P[ 1][ 2]={NP}, right=P[ 3][ 3 ]={VP} 查找规则： X -> NP VP ？有！ S -> NP VP 匹配！ 因此，将 S 加入 P[ 1][ 3 ]。 最终表格 P[ 1][ 3] = {S}。 因为起始符号 S 在最终表示整个句子的单元格 P[ 1][ n] 中，所以句子 "the cat runs" 符合该文法。 步骤6：输出结果 算法结束时，检查单元格 P[1][n] （即表示整个句子的单元格）： 如果 P[1][n] 包含文法的起始符号（通常为 S ），则句子合乎文法，并且可以从表格中通过回溯（backtracking）构造出具体的句法分析树。 如果不包含，则句子不符合该文法。 在我们的修正例子中， P[1][3] 包含 S ，所以句子是合法的。 3. 总结 CYK算法的核心思想是动态规划：将大问题（整个句子的语法性）分解为小问题（子串的语法性），并利用表格存储子问题的解以避免重复计算。其步骤清晰：1) 定义CNF文法；2) 构建表格；3) 初始化（单个词）；4) 递推（组合子串）；5) 判断结果（起始符号是否在顶格）。虽然实际应用中的文法规模庞大，句子更长，计算更复杂，并且需要处理歧义（单元格中可能有多个非终结符），但其基本原理是自然语言处理中基于规则句法分析的一个经典范例。