跳至內容

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

[編輯]

簡介

[編輯]

對於上述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.

外部連結

[編輯]