3.两种算法的比较 为了比较这两种算法，必须在存储空间和运算时间两方面来衡量它们的要求。 对于并行算法来说，由于它必须保存所有的局部分析，所以它对于存储空间的要求显然会大得多。反之，回溯算法只要求比存储一棵单独的句法树略多一点的空间。如果用一部规模较大的语法来分析一个长句子，有可能产生数以千计的局部分析，这对于并行算法的句法分析器来说是一个沉重的负担。 一个分析器对运算时间的耗费通常可以粗略地用产生式的数量和分析一个句子所需进行的归约次数来度量。在这方面两种算法互有长短。自顶向下分析器的优点在于当它处理到一个句子的第n+1个词的时候，如果句法树的前n个终结符名已同该句子的前n个词匹配，那么就不需要再考虑那些不能在这棵树上出现的非终结符；自底向上分析器则不具备这样一种上下文约束，因此在许多情况下对于那些本来可以避免应用的产生式，它仍要用它们来进行归约(即建立局部分析)。另一方面，自顶向下分析器会去扩展某些非终结符，即使扩展结果所包含的某个特定词或词类并没有出现在被分析的那个句子中；而自底向上分析器却可以避免这一类的归约。由于这些因素对运算时间的影响取决于所用语法的特性，所以很难作出定量的判断。 自底向上算法的一个明显优点在于每个局部分析只需建立一次，即使它后来会成为许多种局部分析的一个成分。与此相反，自顶向下算法会对从同一个词开始的某个给定符号进行多次重复的扩展，只要这个符号可能出现在多种不同的上下文中。对于某些附加串来说这是一个严重的问题。 把这两种算法各自的优点结合起来是可能的，办法是采用其中的一种算法，同时吸收另一种算法的某些特性。例如，我们可以采用自底向上的句法分析器，但增加一个"过滤器"，后者仅仅允许那些能够被一个自顶向下分析器建立的局部句法树通过。这个过程利用了"选择性关系"S，如果存在这样一个推导，它从A开始生成一个以符号B为首的串，那么就有选择性关系S(A,B)。根据语法建立的这样一个选择性关系矩阵，也可以用来把自顶向下分析器转变成为一个选择性的自顶向下分析器，如果句子中下一个要匹配的词是W，则仅当矩阵中存有S(A，W)才对符号A进行扩展。 还可以在自顶向下算法中引入某种机制来保存它所建立的任何子树，由于这些子树能同输入句子的某些部分匹配，所以它们事实上就是局部分析。如果下一次分析器试图扩展在同一个词开始的同一个符号，它只需要检索这个局部分析，而无需去重复扩展这个符号。这样一来，我们就把自顶向下算法基于上文有选择地建立局部分析的优点，同自底向上算法每个局部分析只建立一次的优点结合起来了。这种局部分析表又时常被称"合式的子串表"。在线图分析器(chart parsers)中，这种合式的子串表和由一个自顶向下分析器所建立的树被统一于线图(chart)这样一种单独的数据结构中了。 |