编译原理与实践：移进-归约方法

自下而上语法分析需要通过分析栈展开分析动作。通常，还要求在输入符号串左端增加一个标志符号‘#’。分析开始前需要将左端标志符移入分析栈，分析栈和输入串的初始情形为

分析栈 输入串

# w#

自下而上语法分析技术的基本思想是将输入串w的符号自左至右逐一移进分析栈。移进过程中，一旦发现栈顶形成某个产生式的右部时，就将这部分符号串替换为相应产生式的左部。上述替换过程称为归约，被归约的栈顶符号串称为可归约串。因此，自下而上分析法也称为移进-归约法。移进-归约动作将不断重复，直至栈顶呈现如下格局分析过程实例

可归约串

分析栈 输入串

#S #

表示分析成功。输入串w的各个符号最终归约为文法的开始符号S。

例5.1 判别输入串w=abbcde是否为下述文法的句子。

利用自下而上分析方法，为输入串构建语法分析树的过程如图5-1所示。分析栈中的移进-归约步骤如表5-1所示，首先初始化分析栈，然后将下一个输入符号‘a’移进分析栈。由于并未形成任何可归约的符号串，于是将下一个输入符号‘b’移进分析栈。此时，利用第（2）条产生式将栈顶的b归约为A。分析过程中先后在第2、第4、第7和第9四步中使用（2）、（3）、（4）和（1）号产生式进行了四次归约，最终分析成功结束。

(www.xing528.com)

图5-1　自下而上构建输入串abbcde的语法分析树

表5-1　输入串abbcde的自下而上分析过程

动画：自下而上语法

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d

注意，第4步如果没有使用产生式（3），而是用产生式（2）将栈顶的b归约为A，后续分析将无法归约至S。为了能够进行正确的自下而上的语法分析，分析器需要能够根据当前分析栈的情况，以及输入串的后续符号，确定在第4步必须使用产生式（3）进行归约。也就是说，找到方法确定此时栈顶的Ab是可归约串，而b不是可归约串。因此，精确定义可归约串是自下而上分析的关键问题。