4.2.7 CYK的简短回顾

到现在我们已经在这条路上走了很远。首先我们通过原始语法构建了识别表。接下来，我们找到了单元规则和ε规则，虽然比较复杂但用它们也能达到我们的目的。接着我们改进了一下，将语法转换为CNF。而CNF并不包含单元规则和ε规则。由此我们发现构建识别表的算法会变得更简单。发现右侧的最大长度限制为2，也让我们的效率提高很多，同时也让事情简单了一点。然而Sheil [20]已经证明，效率只取决于语法右侧出现的非终结符的最大个数，而不是每一个sé的右侧的长度。这个很容易理解，只要意识到效率取决于（相对于其他事）子句中“很难”找到的小切片（当检查一个右侧是否能生成这个子句时）。而这些“很难”找的小切片的数量取决于右侧的非终结符的数量。因此为了提升效率，Chomsky Normal Form就比较严格一些了。

转换为CNF的一个缺点是生成的识别表丢失了一些信息，以至于我们需要从原始语法中构建一些派生。在转换过程中，有些非终结符被丢弃了，因为它们变成了非生成性的。好在这些失去的信息倒是很容易恢复。最终，这个过程将带给我们一个与我们首次尝试使用原始语法时得到的，几乎一模一样的识别表。它只多了一些在我们将语法转换为CNF时添加在非终结符上的额外的信息。更重要的是，它是以一个更简单高效的方式得到的。

作为CYK算法的一个更详细版本，详见15.4.2节Tree Adjoining Grammars。