斑的家

這是我從PARSING TECHNIQUES a practical guide 得到的心得。

Unger's parsing 主要是利用permutation 的概念去做input  和CFG

(context free grammar) 的配對。

例如：

A->BCD

B->C is

C->Allen|Bill|Chris

D-> a dog

有一個input ：Chris is a dog。

A為start symbol

則我們會去做Chris is a dog 和BCD去配對

為了簡單說明，這邊並沒有epilson這個空的符號。

現在的問題變成如何把4 個words 放到BCD三個

盒子裡。

每一個盒子至少放一個，且words的順序不能改變。

因此會有

B = Chris is , C = a , D = dog   (1)

B = Chris , C = is a , D = dog   (2)

B = Chris , C = is , D = a dog   (3)

然後B,C,D又會遇到同樣分配的問題，一直到完全配對為止。

(2),(3) 都不會match 成功，而(1) 會，所以

得(1) 的match 結果。

這樣的方法，明顯地最大的問題在於“組合數“很多。

不過至少也是一個辦法，總比沒頭緒的好。