4.2.4 重访问示例

现在,让我们来看看CYK语法如何与我们刚刚转换为CNF的示例语法一起工作。同样,我们的输入句子是32.5e+1。识别表如图Fig4.16所示。底部的一行可以直接从语法中读取到。例如,唯一有生成规则的右侧为3的非终结符是NumberIntegerDigit。请注意,对句子中的每一个标记a必须至少有一个具有A → a规则的非终结符A,否则该句子就不能从语法中生成。

图1

图2

其他行按前所述计算。实际上有两种方法可以计算某一个Ri,l。第一种方法是检查语法中的每一个右侧。例如,要知道右侧N1 Scale’,是否生成子字符串2.5e(= s2,4)。到目前为止识别表显示:

  • N1不是R2,1R2,2的一个成员

  • N1R2,3的一个成员,但Scale’不是R5,1的一个成员

因此答案是否定的。使用此方法,我们必须用这种方法来检查每一个右侧,将左侧添加到R2,4,当我们发现其右侧可以生成s2,4

第二种方法是计算到目前为止,识别表中可能出现的右侧。例如,R2,4是具有右侧AB的非终结符的集合,同时右侧也不是以下情况:

  • AR2,1的一个成员,BR3,3的一个成员,或者

  • AR2,2的一个成员,BR4,2的一个成员,或者

  • AR2,3的一个成员,BR5,1的一个成员。

这位AB提供了可能的组合:N1 T2Number T2。现在我们检查语法中的所有规则,以确定是否有测试是这个集合的成员。如果是这样的,那就把左侧添加到R2,4

results matching ""

    No results matching ""