概率上下文无关文法在提高句法分析器效率方面还没有起到什么作用。我们可以研究一些算法来尝试优先找出高概率的成分，这称为最佳优先句法分析算法。我们希望能迅速找到最好的句法分析，而且不用遍历大部分包含较低概率的搜索空间。
实际上，chart句法分析算法都可以相当容易地进行改造，使之能够优先生成最可能的语法成分。其核心思想是将待处理表组织成为优先队列一一在这个结构里，得分排名最高的语法成分总在队列的首位。然后，句法分析器总是将排名最高的语法成分从待处理表中移除，并将其添加到chart图中。
从表面上看，该算法需要进行的全部改进好像就是搜索策略的变化，但是，还有一个复杂的问题。以前的chart句法分析算法都依赖于一个事实，即句法分析器会系统地从左向右进行处理。在考虑句子的后一个成分之前，必须处理完前面出现的成分。而在改进算法中，情况并非如此。如果句子的最后一个词语得分最高，那么，它将第一个加到chart图中。由此导致的问题是不能简单地在chart图中添加活动边（并且，要依靠算法后面的步骤对它们进行扩展）。实际上，chant图可能已经包含了需要用来扩展特定活动边的语法成分。因此，对于现有的chart图，无论什么时候向其中添加活动边，都必须检查，确定它是否可以立刻进行扩展。除了需要修改步骤2使之检查chart图中已有的成分之外，该算法和前面给出的算法相同。图1给出了完整的算法。
图1新的边扩展算法
采用最佳优先策略能极大地提高句法分析器的效率。例如，使用语法1以及从语料库中训练出的词典，最佳优先句法分析器生成65个成分之后，就可以正确地分析出句子“The man put a bird in the house”。对于同一个句子，自底向上的标准算法却要产生158个成分，才能得到相同的结果。如果标准算法修改成发现第一个完整的S解析后立即中止，仍然要为这个句子生成106个成分。因此，最佳优先策略的效率显著提高。
上一篇：简单的上下文相关最佳优先句法分析器
下一篇：浅层句法分析
微信公众号搜索“译员”关注我们，每天为您推送翻译理论和技巧，外语学习及翻译招聘信息。