斑的家

CYK 的parsing 方法有個限制就是

必需先把CFG 轉成CNF (Chomsky Normal Form)

而CNF 主要的規則就是：

A->BC    (1)

D->a      (2)

只能有(1)，一個non-termial symbol 變成2個non-terminal symbol，或者

1個non-terminal 轉成一個terminal 。

這樣的架構從轉換從圖形就變成一個Binary tree 。

那麼CYK parsing 是怎麼match 的呢？

主要的精神是dynamic programming。時間複雜度：O(tn³),

t 為rule 個數，n 為input letter 數

我們會從leaf node 開始往上建樹。

因為(2)的關係，所以我們一開始可以設定每一個input letter

match 像D->a 的rule。

那麼我們可以建一個2維的table[i][j]，i,j 表示position i

到position j 的input letters match 那一條rule。

而table[i][i] 為初始狀態。

那麼我們可以用

for(i = 2 ; i < n ; i++) // 長度為i

   for(j = 1 ; j <= n - i ; j++) // 起始點

         for(k = j ; k <=j+i ; k++) // cutting point

              for(s = 1 ; s <= t ; s++) // t 為rule 數, s 表示第s 條rule

                     if(rule(s) is OK to obtain

                            table[i][j] = combine( table[i][k], table[k][j] )

                      )

                       table[i][j] = true; // 設定table[i][j] match 哪條rule。

最後只要判斷

table[1][n] 是否成功match 就可以了。

接下來，問題回答如何將CFG 轉成CNF。

這邊提出5項要做的事：

1) 刪除D-> epilson

2) A->B, B->c 要換成A->c

3) A->B1B2B3 換成 U ->B1B2 ，而A->UB3

4) A->Ba 換成U->a , A->BU

5) start symbol 的rule 加上S'->S //這條我覺得蠻多餘的

// 但是還沒有特別想出哪種情況需要。