4.2.5 Chomsky普通形式的CYK解析

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

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

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

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

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

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

图1

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

results matching ""

    No results matching ""