CYK算法解析

Cocke-Younger-Kasami算法——上下文无关文法的句法分析利器

一种基于动态规划的算法，用于判定给定字符串是否可由某个上下文无关文法生成

算法复杂度

时间复杂度: O(n³ · |G|)

空间复杂度: O(n²)

CYK算法简介

CYK算法是一种用于判断字符串是否属于某个上下文无关文法的动态规划算法。

历史背景

CYK算法由三位独立研究者分别提出：John Cocke、Daniel Younger和Tadao Kasami。

核心功能

判断一个给定字符串是否可以被特定的上下文无关文法生成。

算法要求

要求上下文无关文法必须是乔姆斯基范式(CNF)。

算法原理

动态规划思想

CYK算法使用动态规划表来存储子问题的解，避免重复计算。

对于长度为n的字符串，构建一个n×n的三角矩阵，其中：

  • P[i][j] 表示从位置i开始长度为j的子串可以由哪些非终结符推导得出
  • 通过组合较小子串的解来构建更大子串的解

乔姆斯基范式(CNF)

CYK算法要求文法必须是CNF形式，其产生式只有两种形式：

  1. A → BC （两个非终结符）
  2. A → a （一个终结符）

任何上下文无关文法都可以转换为等价的CNF形式。

CYK表示例

i\j 1 2 3 4 5
1 S,A - B - S,A
2 B A - S,A,C -
3 A,C - B - -
4 B S,A,C - - -
5 A,C - - - -

算法执行流程

  • 1. 初始化阶段

    对每个位置i和长度为1的子串，找出可以直接生成该终结符的非终结符。

    for i = 1 to n:
      P[i,1] = {A | A → word[i] ∈ G}
  • 2. 递推计算

    对于长度从2到n的所有子串，分解为两部分，检查是否存在产生式A→BC。

    for length = 2 to n:
      for i = 1 to n-length+1:
        for k = 1 to length-1:
          P[i,length] ∪= {A | A→BC ∈ G, B∈P[i,k], C∈P[i+k,length-k]}
  • 3. 结果判定

    检查起始符号S是否在P[1,n]中，如果在则字符串可由文法生成。

    if S ∈ P[1,n] then
      return "字符串属于文法"
    else
      return "字符串不属于文法"

交互式演示

演示控制

算法结果

运行算法后将在此显示结果矩阵和解析结果

应用场景

自然语言处理

用于句法分析，判断句子是否符合语法规则。

编译器设计

在语法分析阶段检查程序代码结构是否正确。

形式语言研究

研究上下文无关文法的性质和能力。

人工智能

在对话系统和知识表示中应用形式文法。