4.2.5 Chomsky普通形式的CYK解析

我们现在有一个算法，来确定一个句子是否属于一个语言，并且它比深度搜索要快得多。但是我们不只是想知道一个句子是否属于一个语法，在可能的情况下我们更想知道语法是如何生成这个句子的。并且如果一个句子可以以多种方式生成，那我们还想要知道所有生成的路径。由于识别表包含了我们可能会有的输入句子子句的所有生成信息，因此也就包含了所有我们需要的信息。正因此，这个表所包含的信息太过庞大，以至于我们想要的东西都被隐藏在内，需要我们自己挖掘。这个表包含了非终结符生成子句的信息，这些生成过程又不能被用在起始符号S生成子句的生成过程中。例如在上面的例子中，*R_2,3*包含了N1，但N1生成2.5的过程不能被用在Number生成32.5e+1的过程中。

解决这个问题的关键稍加注意就能发现，生成过程必须从起始符号S开始。生成输入句子t（长度n）的第一步，可以从语法和识别表中读取。如果n=1，则必须存在规则S → t；如果n ≥ 2，则我们必须要检查所有S → AB的规则，其中A生成t的第一个k符号，B生成第二个，也就是说，A是R_1,k的值，B是R_k+1,n-k的值（k值一定的情况）。必须至少存在这样一个规则，否则S就无法生成t。T

对于每一个AB组合我们都会遇到同样的问题：A如何生成s_1,k，以及B如何生成s_k+1,n−k？实际上这些问题都可以以同样的方式解决。从哪个非终结符开始并不重要。始终保持对于最左侧的生成结果中采用最左侧的值，以及最右侧的生成结果中采用最右侧的值。

请注意，在这里我们可以使用Unger类解析器。但是不需要在生成所有的部分，因为我们已经知道的需要的部分是哪些。

我们来试一下从图4.16的识别表中，为示例中的句子和语法找到一个最左侧的生成结果。从起始符号Number开始。句子包含七个符号，因为有多个，因此我们必须使用带有一个右侧的AB形式的规则。这里Integer Digit规则不适用，因为Digit的唯一实例可能生成的句子是*R_7,1中的，但Integer却并不属于R_1,6的子集。Integer Fraction规则也不适用，因为没有生成句子最后一部分的Fraction。因此就只剩一个规则Number ---> N1 Scale’，并且确实适用，因为N1是R_1,4的值，并且**Scale’**是R_5,3*的值，因此N1生成32.5，Scale’生成e+1。

接下来，我们要找出N1如何生成32.5。只有一个可用的规则：N1 -> Integer Fraction，确定可用是因为Integer是R_1,2的值，而Fraction是R_3,2的值，因此Integer可以生成32，Fraction生成**.5**。最后，我们就有了以下的生成结果：

但很可惜这并不是我们真正想要的，因为这是适用图4.15中的语法规则生成的，而不是图4.16中的语法规则（我们原本的语法）。