1. 传统图算法分析器的不足之处
图算法分析的目标是得到跨过整个输入串的完成弧。为了达到这个目标，不断创建活动弧，并且希望用完成弧来满足活动弧的要求。不管是从时间方面，还是从空间方面来考虑，在图中的活动弧都是越少越好。
在传统图算法分析器中，活动弧的要求都是严格从左到右满足的，即活动弧是没有方向的，一条类为C的完成弧对于规则库中的每条右部以类C为开始的规则，触发产生一条新的活动弧，但是，如果分析过程中，C的后面其他类没有按照规则规定的顺序出现，则这条活动弧的创建是无效的，所以传统图算法分析器的效率不高。下面将要提到，没有方向的分析（严格从左到右或从右到左）是引起这种缺陷的原因。
2. 规则的触发类
I. 触发类的含义
考虑如下的简化规则库：
(1)NP =＞ N
(2)NP =＞ADJ NP
(3)NP =＞XPDE NP
(4)XPDE =＞S DE
(5)XPDE =＞ NP DE
(6)S =＞NP VP
(7)VP =＞ VN
(8)VP =＞ VT NP
请看规则(8)，虽然NP前面未必是VT，但是，如果VT出现，它的后面一定接NP。如果对规则(8）从左到右分析，看到VT之后，对于NP的预见总是正确的。反之，如果对它从右到左分析，则从NP预见VT有时是错误的。所以对规则（8）从左到右分析更有效。再看规则（6），则是从右到左分析更有效。因为，如果从左到右分析，当找到一个NP，一条标志为S=NP。VP的新活动弧创建了，如果后面没有找到VP（可以设想，如同规则5描述的，NP后面是一个DE），则这条弧就白创建了。如果对规则(6）从右到左分析，则这个问题就不存在了，因为从规则库中可以看到，在VP前面只能是NP，否则就是一个错误句子。如果找到一个VP，一条标志为S=NP。VP的新活动弧被创建，如果这是一个正确句子，在VP前面将会找到一个NP。
由以上例子看出，为了使分析的效率更高，有的规则应该从左到右分析，而有的规则应该从右到左分析。
本文介绍的双向图分析器允许规则从左到右，从右到左，或者更一般地，从规则右部的某个特定类开始分析。我们把这个特定类称为规则的触发类。因为双向图的活动弧可对左边和右边同时都有要求，所以需要决定一个顺序。我们总是先填左边，再填右边。如果规则的触发类是它右部的最左边的类，则规则从左到右分析；如果规则的触发类是它右部的最右边的类，则规则从右到左分析。
上一篇：向量空间模型
下一篇：传统LR语法分析器
微信公众号搜索“译员”关注我们，每天为您推送翻译理论和技巧，外语学习及翻译招聘信息。