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算法

簡介

對於上述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 行表示由哪幾個非終結符可以產生字字符串  

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.

外部連結