|
2.自底向上的并行算法
对于上下文无关语法的另一个通用算法是自底向上的并行算法。这个算法以自底向上的方式建立一些局部分析，其中每个局部分析代表了输入句子的一个子串。形式地说，标号为i的局部分析包含四个成分：root(i)，first(i)，last(i)和constituents(i)。它的意思是：句子中号码从fist(i)到last(i)的词可以从root(i)推导出来，而且如果constituents(i)是一个n元组：<c1,…,cn>，那么这个推导由。以下产生式组成：
root(i)→root(c1)…root(cn)，
后面跟着的是伴随局部分析c1…cn的推导。
具体算法如下：
(1) 如果句子的词是S1,…,Sn
则对于i＝1,…,k：
分别建立一个局部分析，
它的root＝Si，
first＝last＝i，
constituents＝空的n元组，
并且对于Si的每个词类C
分别建立一个局部分析，
它的root＝C，
first＝last＝i，
constituents＝空的n元组。
(2) 无限地重复：
如果存在一个产生式A→r1r2…rn
以及局部分析i1,…,in
使得对于j=1,…,n，root(ij)＝rj，
并且对于j＝2,…,n，last(ij-1)＝first(ij)一1。
则建立一个新的局部分析，
它的root＝A，
first＝first(i1)，
last：＝last(in)，
Constituents＝<i1,…,in>；
否则(如果不存在这样的产生式)退出。
当你实现这个过程时，一个复杂的问题就是要保证不得重复应用同一个归约。这一点通常是用一组嵌套的循环来取代上述算法中的非结构化的"重复"(repeat)来实现的，即让最外层的循环总是越过正在建立的那个局部分析的最后一个词。
如果产生式的右侧总是只有一个或两个符号，我们便可以按如下方式来建立这种自底向上的算法：
(1)对于i＝1,…,k重复步骤(2)到(7)；
(2)建立一个局部分析，它的root＝Si，
first=1ast＝i。
constituents＝空的n元组，
并且对于Si的每个词类C
建立一个局部分析，其root＝C，
first＝last＝i，
constituents＝空的n元组，
把这些局部分析的标号装入"todo"集。
(3)重复步骤(4)到(7)直到todo为空。
(4)从todo中选择一个元素(即一个局部分析的标号)，命它为r。从todo中删除r。
(5)设P是这样一个产生式集，这些产生式右侧的最后一个符号(也许只有这样一个符号)是root(r)。
(6)对于P中的每个成员p重复步骤(7)。
(7)如果p的形式为A→y，其中y＝root(r)
则建立一个局部分析，它的root＝A，
first＝first(r)，
1ast=last(r)，
Constituents=<r>;
否则p的形式为A→xy，其中y＝root(r)
对每个局部分析m，使得root(m)＝x，
last(m)＝first(r)-1，
建立一个局部分析，它的root＝A，
first＝first(m)，
1ast：＝1ast(r)，
Constituents＝<m，r>。
把刚才建立的所有局部分析的标号添加到todo中去。
这个算法利用todo集来保存那样一些局部分析，它们已经生成但未曾作为其他局部分衍的最后成分被结合。如果对算法中的第(7)步加以适当的一般化，这个算法便可以用来处理产生式右侧具有任意多个符号的语法。
一旦所有的局部分析都已建立，那么那些root＝起始符,first＝1，last＝句长的局部分析便是输入句子的句法分析。沿着constituents的指针便可以找到句子的句法树。请注意，对于一个有句法歧义的句子来说。两棵或多棵句法树可以共享一个局部分析，这意味着那些局部分祈和constituents指针所构成的是一个无环图，而不是一棵树。
用这个算法来处理那部只有三条规则的语法和句子"I like cheese"(PRO TV N)，将产生顺序如表9.2所示的局部分析。
 |
表9.2 句子"I1
like2 cheese3"的局部分析
|