4.3.2 自底向上表解析

自底向上表解析可以正确填充所有输入内容,但要比自顶向下算法更仔细一些。就像CYK一样,对于CNF类型的语法它的效率最高,因此我们将尽可能保证我们的语法属于这类。而且与CYK一样,在计算时关于输入内容的顺序我们要小心处理。此外,我们将填充图Fig4.21的三维“楔形(背面)”(其输入为布尔(位(Bits))),而不是正面的二维部分(其输入内容是整数列表)。楔形的输入内容描述了一个终结符的生成是否是来自于位置i长度KA(写作Ti,A,K)。

自底向上表解析对整个识别表的填充过程开始于右端的起始列。为了填充输入Ti,A,K,我们从语法中找到了一个A → BC形式的规则,然后我们就可以访问到Ti,B,1。如果这个输入已经设置好了吗,那么在位置i就有B生成的一个长度位1的段。如果都设置好了,那我们接下来就访问Ti+1,C,k−1,同理在位置i+1C生成的长度位k-1的一个段。由此我们得出结论,在位置i的长度为K的输入段会有一个A的终结符生成,我们将此输入称为Ti,A,K。如果不对,依次检查Ti,B,2Ti+2,C,K-2等等,直到Ti,B,K-1Ti+k-1,C,1,就像CYK算法一样。

我们可以在Ti+K-1,C,1停止,因为CNF语法中没有ε规则,因此Ti+k,C,0并不存在。这意味着Ti,A,K在计算过程中会涉及到Ti,B,j(仅只当j < K时)。因此当我们在Ti,Q,K(j < KPQ为任意值)之前计算Ti,P,j,那么就需要确保计算Ti,A,K输入内容和值都已经准备好了。就会对算法施加特定的计算顺序:

图1

计算Ti,A,K的成本是O(n|Pav|),其中n是输入的长度而|Pav|是一个非终结符产生规则数的平均值。正如我们看到的,这个计算重复了O(n|G|n)次,其中|G|与语法的大小成正比。因此这个解析算法的时间成本为O(n3|G||Pav|)O(n3)×O(|G||Pav|)

自底向上表解析应用于12章和15.7节的许多算法中。

Nederhof 和 Satta [40]写了一个关于表解析的教程,并将其广泛应用于非确定性解析算法中。

results matching ""

    No results matching ""