自底向上语法分析

规约

我们可以将自底向上语法分析过程看成将一个串w“归约”为文法开始富豪的过程。在每个规约(reduction)步骤中，一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号。

根据定义，一次规约是一个推导步骤的反向操作。因此自底向上语法分析的目标是反向构造一个推导过程。

句柄剪枝

通俗地讲，句柄(handle)是和某个产生式体匹配的子串。

句柄剪枝是指分析过程可以看成对分析树的不断剪枝直到最后只剩下起始符号。

移入-规约语法分析技术

移入-规约语法分析是自底向上语法分析的一种形式。它使用一个栈来保存文法符号，并使用一个输入缓冲区来存放要进行语法分析的其余符号。

在对输入串的一次从左到右扫描过程中，语法分析器讲零个或多个输入符号移到栈的顶端，直到它可以对栈顶的一个文法符号串β进行规约为止。它将β规约为某个产生式的头。

不断重复这个循环，知道它检测到语法错误或者栈中包含了开始符号且输入缓冲区为空。

• 一个移入-规约分析器可以采取4种动作：

1. 移入(shift)：将下一个输入符号移到栈顶。
2. 规约(reduce)：被规约的符号串右端必然是栈顶。语法分析器确定串的左端并决定用哪个非终结符来替换这个串。
3. 接受(accept)：宣布语法分析过程完成。
4. 报错(error)：语法错误，调用一个错误恢复子例程。

栈          输入       动作
$       id1*id2$       移入
$id1       *id2$       按F->id规约  
$F         *id2$       按T->F规约  
$T         *id2$       移入  
$T*         id2$       移入  
$T*id2         $       按F->id规约  
$T*F           $       按T->T*F规约  
$T             $       按E->T规约  
$E             $       接受  

移入-规约语法分析中的冲突

有些上下文无关文法不能使用移入-规约语法分析技术。会出现如下情形：知道了栈和接下来的k个输入符号依然无法判断该进行移入还是规约（移入/规约冲突），或者无法在多个可能的规约方法中选择正确的规约动作（规约/规约冲突）。

（END）