CYK算法

CYK算法（英语：Cocke–Younger–Kasami algorithm，缩写为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算法作一个小改动，也就是说记住每次的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))