PCFG的剖析問題是對于一個(gè)給定的句子產(chǎn)生最佳剖析樹的問題，也就是計(jì)算：

幸運(yùn)的是，計(jì)算最佳剖析的算法只是標(biāo)準(zhǔn)剖析算法的簡單擴(kuò)充。使用Earley算法來對于給定的輸入句子和給定的上下文無關(guān)語法找出所有剖析，但我們完全可能提升Earley算法，使它能夠計(jì)算每個(gè)剖析的概率，從而找出最佳的剖析。但是，這里不介紹概率Earley算法，而是介紹概率CYK算法（Cocke-Younger-Kasami algorithm）。之所以這樣做，一是因?yàn)楦怕蔈arley算法介紹起來比較復(fù)雜，二是因?yàn)镃YK算法很值得我們理解和學(xué)習(xí)，而我們現(xiàn)在還沒有學(xué)習(xí)過這種算法。

Earley算法主要是一種自頂向下的剖析算法，使用動(dòng)態(tài)規(guī)劃表來有效地存儲(chǔ)中間結(jié)果；CYK算法主要是一種自底向上的剖析算法，也使用同樣的動(dòng)態(tài)規(guī)劃表。CYK算法的這種自底向上的性質(zhì)，使得它在處理詞匯化的語法時(shí)非常有效。

概率CYK算法首先是由Ney(1991)描述的，但是現(xiàn)在采用的概率CYK算法的版本來自Collins（1999）和Aho and UIIman(1972）。首先，我們要假定PCFG是具有Chomsky范式的。如果一個(gè)語法是ε-free的，并且如果每個(gè)產(chǎn)生式的形式或者為A→BC，或者為A→a，那么這個(gè)語法就是具有Chomsky范式（CNF）的語法。CYK算法假定如下的輸入、輸出和數(shù)據(jù)結(jié)構(gòu)：

輸入

- Chomsky范式的PCFG G=（N,E,P,S,D)。假定非終極符號(hào)INI的索引號(hào)為1,2,…,INI，初始符號(hào)的索引號(hào)為1。

- n個(gè)單詞為W1…Wn。

* 數(shù)據(jù)結(jié)構(gòu) 動(dòng)態(tài)規(guī)劃數(shù)組π[i,j,a]表示跨在單詞i…j上的非終極索引號(hào)為a的成分的最大概率。在這個(gè)區(qū)域上的反向指針用于存儲(chǔ)剖析樹中成分之間的鏈接。

* 輸出 最大概率剖析將是π[1,n,1]：剖析樹的根是S，剖析樹跨在單詞W1…Wn構(gòu)成的整個(gè)符號(hào)串上。