移进归约句法分析器
2023-04-24 09:26:30 etogether.net 网络 次
这些状态可以用来控制句法分析器。在句法分析过程中，我们需要维护两个栈结构。其中一个是分析栈，包含句法分析的状态（即图1中的节点）和语法符号；另一个是输入栈，包含输入的句子和一些语法符号。在任何时候，句法分析器均根据分析栈顶端状态的信息进行处理。
状态可以按照如下方式进行解释。有些状态只包含一条点号在最右边的简单规则，比如S2'：
S → NP VP°
它表示的是，句法分析器应当依据该规则改写分析栈顶端的符号，这就叫归约（reduce)操作。新派生出来的符号(本例中的S）压到输入栈顶端。
对于其他不包含完结规则的状态，我们通过状态转移图对其进行解释。如果输入栈顶端的符号与某条边匹配，那么，它和新状态(在边的末尾)会压到分析栈的顶端，我们称之为移进(shift)操作。根据对这些状态的解释，可以构建一张表，我们通常称之为预测表(oracle)。在各种不同的情况下，预测表都会告诉句法分析器应该如何去做。语法1的预测表如图1所示。对于每一个状态和可能的输入，它都指出了操作类型和下一个状态。不管下一个输入是什么，都可以直接使用归约操作，而接受操作只有在输入栈为空的时候（即，下一个符号为空符号ε)才有可能执行。根据预测表进行句法分析的算法如图2所示。
图1语法1的预测表
图2移进归约句法分析器的分析算法
上一篇：高效的歧义表示技术
下一篇：句法分析中人的优选策略
微信公众号搜索“译员”关注我们，每天为您推送翻译理论和技巧，外语学习及翻译招聘信息。