CYK算法

CYK算法（英語：Cocke–Younger–Kasami algorithm，縮寫為CYK algorithm）是由約翰·科克，Younger和嵩忠雄共同研究出來大約發表於1965年的一個算法，它是一個用來判定任意給定的字符串$~w\in \Sigma ^{*}$ 是否屬於一個上下文無關文法的算法。普通的回溯法（backtracking）在最壞的情況下需要指數時間才能解決這樣的問題，而CYK算法只需要多項式時間就夠了（$~O(n^{3})$ ， n 為字符串 w 的長度）。CYK算法採用了動態規劃的思想。

對於一個任意給定的上下文無關文法，都可以使用CYK算法來計算上述問題，但首先要將該文法轉換成喬姆斯基範式。

相關參數定義

• $~G=(V,\Sigma ,S,P)$ 是一個上下文無關文法
• 對於任意字符串 $w=\sigma _{1}...\sigma _{n}\in \Sigma ^{*}$ ，定義 $w[i,j]=\sigma _{i}...\sigma _{j},~1\leq i\leq j\leq n$
• 對於任意選擇的 $~i,j$ ，定義 $V_{i,j}=\{X\in V~|~X\Rightarrow ^{*}w[i,j]\}$

算法描述

簡介

通過由下而上的方法計算 $~V_{i,j}$ 這個集合，如果 $S\in V_{1,n}$ ，那麼就說明 $~w$ 是被上下文無關文法 $~G$ 接受的字符串。

因為 $~G$ 是一個喬姆斯基範式，當且僅當有下面描述的情況時 $X\in V_{i,j}$ ：

• $i<j,~\exists Y,Z,k:X\rightarrow YZ$ 是 $~G$ 中的一個規則且 $Y\in V_{i,k},Z\in V_{k+1,j}$

偽代碼

FOR i:= 1 TO n DO $V_{i,i}:=\{X\in V~|~X\rightarrow \sigma _{i}~in~P\}$
FOR l:= 1 TO n-1
    FOR i:= 1 TO n-l DO
        $~V_{i,i+l}:=\varnothing$
        FOR k:= i TO i+l-1 DO
            $~V_{i,i+l}:=V_{i,i+l}\cup \{X~|~X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,i+l}\}$
IF $S\in V_{1,n}$ THEN accept ELSE reject

擴展CYK算法

簡介

對於上述CYK算法作一個小改動，也就是說記住每次的k，就可以自動產生一個由該上下文無關語言的推導樹。

偽代碼

FOR i:= 1 TO n DO $V_{i,i}:=\{X\in V~|~X\rightarrow \sigma _{i}~in~P\}$
FOR l:= 1 TO n-1
    FOR i:= 1 TO n-l DO
        $~V_{i,i+l}:=\varnothing$
        FOR k:= i TO i+l-1 DO
            $~V_{i,i+l}:=V_{i,i+l}\cup \{(X,k)~|~X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,i+l}\}$
IF $\exists k:(S,k)\in V_{1,n}$ THEN accept ELSE reject

通過對下面的方法遞歸運行就可以生成推導樹。

Tree(X,i,j):
   IF i=j THEN RETURN $~\sigma _{i}$
   選擇一個 k 使 $(X,k)\in V_{i,j}$
    選擇 Y 和 Z 使 $X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,j}$
    RETURN Tree(X,Tree(Y,i,k),Tree(Z,k+1,j))

例子

給定一個喬姆斯基範式的上下文無關文法 $~G=(\lbrace S,A,B,C\rbrace ,\lbrace a,b\rbrace ,S,P)$ ，其中規則 P 如下：

$S\rightarrow AB\mid BC$

$A\rightarrow BA\mid a$

$B\rightarrow CC\mid b$

$C\rightarrow AB\mid a$

問：字符串 bbabaa 能不能通過該文法產生？

CYK算法可以通過一個表格來運算，表中 i 列 j 行表示由哪幾個非終結符可以產生字字符串 $\sigma _{i}\dots \sigma _{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 n³. Information and Control 10(2): 189–208.

外部連結

• Interaktives Java-Applet zur Demonstration（頁面存檔備份，存於網際網路檔案館）