4.2 CYK解析法

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

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

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