4.3.2 自底向上表解析

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

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

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

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

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

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