CYK算法

CYK算法（，縮寫為CYK algorithm）是由約翰·科克，Younger和共同研究出来大约发表于1965年的一个算法，它是一个用来判定任意给定的字符串 是否属于一个上下文无关文法的算法。普通的回溯法（backtracking）在最坏的情况下需要指数时间才能解决这样的问题，而CYK算法只需要多项式时间就够了（ ， n 为字符串 w 的长度）。CYK算法采用了动态规划的思想。

对于一个任意给定的上下文无关文法，都可以使用CYK算法来计算上述问题，但首先要将该文法转换成乔姆斯基范式。

 相关参数定义 
  是一个上下文无关文法
 对于任意字符串  ，定义 
 对于任意选择的  ，定义 

 算法描述 
 简介 
通过由下而上的方法计算  这个集合，如果  ，那么就说明  是被上下文无关文法  接受的字符串。

因为  是一个乔姆斯基范式，当且仅当有下面描述的情况时  ：
  是  中的一个规则且 

 伪代码 
 FOR i:= 1 TO n DO 
 FOR l:= 1 TO n-1
     FOR i:= 1 TO n-l DO

         FOR k:= i TO i+l-1 DO

 IF  THEN accept ELSE reject

 扩展CYK算法 
 简介 
对于上述CYK算法作一个小改动，也就是说记住每次的k，就可以自动产生一个由该上下文无关语言的推导树。

 伪代码 
 FOR i:= 1 TO n DO 
 FOR l:= 1 TO n-1
     FOR i:= 1 TO n-l DO

         FOR k:= i TO i+l-1 DO

 IF  THEN accept ELSE reject

通过对下面的方法递归运行就可以生成推导树。
 -{}-
 Tree(X,i,j):
    IF i=j THEN RETURN 
    选择一个 k 使 
     选择 Y 和 Z 使 
     RETURN Tree(X,Tree(Y,i,k),Tree(Z,k+1,j))

 例子 
给定一个乔姆斯基范式的上下文无关文法  ，其中规则 P 如下：

问：字符串 bbabaa 能不能通过该文法产生？

CYK算法可以通过一个表格来运算，表中 i 列 j 行表示由哪几个非终结符可以产生字字符串  。

例如：，表示从非终结符 A 开始能够产生子串 bba。有如下推导：
 i 1 2 3 4 5 6 ai b b a b a a j=1 {B} j=2  - {B} j=3 {A} {S,A} {A,C} j=4 {S,C} {S,C} {S,C} {B} j=5 {B} {B} {B} {A,S} {A,C} j=6 {A,S} {A,S} {A,S} - {B} {A,C}

如果在表格的最左下角一格中有文法的开始非终结符 S ，那么字符串 bbabaa 就能由上面给出文法 G 产生。

 参考文献 

 John Cocke and Jacob T. Schwartz (1970). Programming languages and their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University.
 T. Kasami (1965). An efficient recognition and syntax-analysis algorithm for context-free languages. Scientific report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA.
 Daniel H. Younger (1967). Recognition and parsing of context-free languages in time n3. Information and Control 10(2): 189–208.

 外部链接 
 Interaktives Java-Applet zur Demonstration

Category:算法
Category:形式语言
Category:分析演算法