PCFG的剖析问题是对于一个给定的句子产生最佳剖析树的问题，也就是计算：

幸运的是，计算最佳剖析的算法只是标准剖析算法的简单扩充。使用Earley算法来对于给定的输入句子和给定的上下文无关语法找出所有剖析，但我们完全可能提升Earley算法，使它能够计算每个剖析的概率，从而找出最佳的剖析。但是，这里不介绍概率Earley算法，而是介绍概率CYK算法（Cocke-Younger-Kasami algorithm）。之所以这样做，一是因为概率Earley算法介绍起来比较复杂，二是因为CYK算法很值得我们理解和学习，而我们现在还没有学习过这种算法。

Earley算法主要是一种自顶向下的剖析算法，使用动态规划表来有效地存储中间结果；CYK算法主要是一种自底向上的剖析算法，也使用同样的动态规划表。CYK算法的这种自底向上的性质，使得它在处理词汇化的语法时非常有效。

概率CYK算法首先是由Ney(1991)描述的，但是现在采用的概率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。

* 数据结构 动态规划数组π[i,j,a]表示跨在单词i…j上的非终极索引号为a的成分的最大概率。在这个区域上的反向指针用于存储剖析树中成分之间的链接。

* 输出 最大概率剖析将是π[1,n,1]：剖析树的根是S，剖析树跨在单词W1…Wn构成的整个符号串上。