基于动态规划的CYK（Cocke-Younger-Kasami）句法分析算法 题目描述 CYK算法是一种用于判断给定字符串是否可以由某个上下文无关文法（Context-Free Grammar, CFG）生成，并构建对应句法树的动态规划算法。该算法要求文法必须为乔姆斯基范式（Chomsky Normal Form, CNF），即产生式规则只能是两种形式：A→BC（两个非终结符）或A→w（一个终结符）。CYK算法广泛应用于自然语言处理中的句法分析任务，例如判断句子是否合乎语法、构建句法树等。 解题过程循序渐进讲解 1. 问题输入与输出 输入 ： 一个上下文无关文法G，已转换为CNF形式，包含非终结符集合、终结符集合、产生式规则集、起始符号S。 一个长度为n的单词序列（句子）w = w1 w2 ... wn。 输出 ： 布尔值：句子是否能由文法G生成（即是否符合语法）。 （可选）对应的句法树或所有可能的句法分析结果。 2. 算法核心思想 CYK算法的核心是动态规划表（通常称为parse table）。我们构建一个二维表dp，其中dp[ i][ j]（1 ≤ i ≤ j ≤ n）表示句子中从第i个单词到第j个单词的子串（即wi ... wj）可以由哪些非终结符推导出来。算法自底向上（从短子串到长子串）填充这个表，最终检查起始符号S是否在dp[ 1][ n ]中，若在则句子合法。 3. 算法步骤详解 步骤1：初始化（长度为1的子串） 对每个位置i（1 ≤ i ≤ n），考虑子串wi（长度为1）。 查找文法中所有形如A→wi的产生式（即终结符产生式）。 将所有这样的非终结符A加入dp[ i][ i ]。 例如，如果文法有规则“NP → '苹果'”，且wi='苹果'，则将NP加入dp[ i][ i ]。 步骤2：递推（长度从2到n的子串） 对子串长度len从2到n遍历： 对子串起始位置i从1到n-len+1遍历： 令j = i + len - 1（子串结束位置）。 对分割点k从i到j-1遍历（将子串分为两段：wi...wk和wk+1...wj）： 从dp[ i][ k]中取出所有非终结符B，从dp[ k+1][ j ]中取出所有非终结符C。 查找文法中所有形如A→BC的产生式（即两个非终结符产生式），其中B∈dp[ i][ k]且C∈dp[ k+1][ j ]。 将所有这样的非终结符A加入dp[ i][ j ]。 这一步骤的本质是：要得到子串wi...wj，我们尝试所有可能的方式将其分割为两段，分别由非终结符B和C生成，然后通过规则A→BC组合成A生成整个子串。 步骤3：判断与回溯 检查起始符号S是否在dp[ 1][ n ]中。如果在，则句子合法，否则不合法。 如果需要构建句法树，可以从dp[ 1][ n ]中的S开始，递归回溯： 对于dp[ i][ j]中的每个非终结符A，找到某个分割点k和非终结符B、C，使得B∈dp[ i][ k]、C∈dp[ k+1][ j ]且A→BC是文法规则。 对B和C递归执行相同操作，直到叶子节点（终结符）。 注意：可能存在多个句法树（歧义），回溯可找到所有可能。 4. 复杂度与特点 时间复杂度O(n³ * |G|)，其中|G|是文法规则数，n是句子长度。 空间复杂度O(n²)。 必须先将文法转为CNF，否则算法不适用。转换过程可能增加文法规模，但保证了一般CFG都可等价转换。 算法是确定性的，能处理所有CNF文法描述的语言，但无法处理非上下文无关的语法现象。 5. 简单示例演示 假设文法规则为： S → NP VP NP → 'I' | 'apple' VP → V NP V → 'eat' 句子为“I eat apple”，已转为CNF（此例无需转）。 初始化： dp[ 1][ 1 ] = {NP}（因为NP→'I'） dp[ 2][ 2 ] = {V}（因为V→'eat'） dp[ 3][ 3 ] = {NP}（因为NP→'apple'） 递推： 长度2：子串“I eat”即dp[ 1][ 2]，k=1分割：B∈dp[ 1][ 1]={NP}, C∈dp[ 2][ 2]={V}，查找规则A→NP V，无对应，所以dp[ 1][ 2]为空。子串“eat apple”同理dp[ 2][ 3 ]为空。 长度3：子串“I eat apple”即dp[ 1][ 3]，尝试k=1：B∈{NP}, C∈dp[ 2][ 3]={}，无；k=2：B∈dp[ 1][ 2 ]={}，C∈{NP}，无；但需注意规则S→NP VP，而VP→V NP，因此实际上应通过组合得到。更仔细地： 先计算长度2的子串“eat apple”dp[ 2][ 3]，k=2分割：B∈{V}, C∈{NP}，查找A→V NP，得到VP，所以dp[ 2][ 3 ]={VP}。 再计算长度3的子串“I eat apple”dp[ 1][ 3]，k=1分割：B∈{NP}, C∈dp[ 2][ 3]={VP}，查找A→NP VP，得到S，所以dp[ 1][ 3 ]={S}。 最终dp[ 1][ 3 ]包含S，句子合法。回溯可得树：S(NP('I'), VP(V('eat'), NP('apple')))。 总结 CYK算法是句法分析的基础动态规划算法，其核心在于利用CNF的二叉特性，通过自底向上组合子串推导结果来判断全局合法性。尽管实际应用中常使用更高效的算法（如Earley算法），但CYK因其简洁性和普遍性，仍是理解句法分析原理的重要范例。