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 \le i \le j \le 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 \rarr YZ$ 是 $~G$ 中的一個規則且 $Y \in V_{i,k}, Z \in V_{k+1,j}$

### 偽代碼

```
''FOR'' i:= 1 ''TO'' n ''DO'' <math>V_{i,i}:= \{ X \in V ~| ~X \rarr \sigma_i ~in ~P \}</math>
''FOR'' l:= 1 ''TO'' n-1
    ''FOR'' i:= 1 ''TO'' n-l ''DO''
        <math>~V_{i,i+l} := \varnothing</math>
        ''FOR'' k:= i ''TO'' i+l-1 ''DO''
            <math>~V_{i,i+l} := V_{i,i+l} \cup \{X ~| ~X \rarr YZ, Y \in V_{i,k}, Z \in V_{k+1,i+l} \}</math>
''IF'' <math>S \in V_{1,n}</math> ''THEN'' accept ''ELSE'' reject
```

## 擴展CYK演算法

### 簡介

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

### 偽代碼

```
''FOR'' i:= 1 ''TO'' n ''DO'' <math>V_{i,i}:= \{ X \in V ~| ~X \rarr \sigma_i ~in ~P \}</math>
''FOR'' l:= 1 ''TO'' n-1
    ''FOR'' i:= 1 ''TO'' n-l ''DO''
        <math>~V_{i,i+l} := \varnothing</math>
        ''FOR'' k:= i ''TO'' i+l-1 ''DO''
            <math>~V_{i,i+l} := V_{i,i+l} \cup \{ (X,k) ~| ~X \rarr YZ, Y \in V_{i,k}, Z \in V_{k+1,i+l} \}</math>
''IF'' <math>\exists k : (S,k) \in V_{1,n}</math> ''THEN'' accept ''ELSE'' reject
```

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

```
Tree(X,i,j):
   ''IF'' i=j ''THEN'' RETURN <math>~\sigma_i</math>
   选择一个 k 使 <math>(X,k) \in V_{i,j}</math>
    选择 Y 和 Z 使 <math>X \rarr YZ, Y \in V_{i,k}, Z \in V_{k+1,j}</math>
    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$。

例如：$Table[1,3] = {A}$，表示從非終結符 A 開始能夠產生子串 bba。有如下推導：$A \rightarrow BA \rightarrow bA \rightarrow bBA \rightarrow bbA \rightarrow bba$

i｜1｜2｜3｜4｜5｜6

ai｜b｜b｜a｜b｜a｜a

{A}｜{S,A}｜{A,C}

{S,C}｜{S,C}｜{S,C}｜{B}

{B}｜{B}｜{B}｜{A,S}｜{A,C}

{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