4.2 CYK解析法

本节中讲述的解析方法来自于J. Cocke、D.H. Younger以及T. Kasami，他们发现了该方法的变体；它被称为Cocke-Younger-Kasami法，或者CYK法。最容易理解的初稿是Younger [10]。更早一版是Sakai [5]。

与Unger解析法一样，CYK法的输入包含一个CF语法和一个输入语句。算法的第一阶段构造了一个表，为我们将非终结符和派生出的句子的子句对应起来。这是识别阶段；它最终也告诉我们输入句子是否可以从语法中推导出来。第二阶段用这个对照表以及语法来生成所有可能的的句子。

我们先关注识别阶段，这是这个算法很特别的地方。