PCFG的剖析問題是對于一個給定的句子產生最佳剖析樹的問題，也就是計算：

幸運的是，計算最佳剖析的算法只是標準剖析算法的簡單擴充。使用Earley算法來對于給定的輸入句子和給定的上下文無關語法找出所有剖析，但我們完全可能提升Earley算法，使它能夠計算每個剖析的概率，從而找出最佳的剖析。但是，這里不介紹概率Earley算法，而是介紹概率CYK算法（Cocke-Younger-Kasami algorithm）。之所以這樣做，一是因為概率Earley算法介紹起來比較復雜，二是因為CYK算法很值得我們理解和學習，而我們現(xiàn)在還沒有學習過這種算法。

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

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

輸入

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

- n個單詞為W1…Wn。

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

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