自底向上语法分析

为一个输入串构造语法分析树的过程，从叶子（输入串中的终结符号，将位于分析树的底端）开始，向上到达根节点。

在实际的语法分析过程中并不一定会构造出相应的分析树，但是用分析树的概念可以方便理解。

重要的自底向上语法分析的通用框架：

• 移入-归约（shift-reduce）

多种LR技术

• 简单LR技术（SimpleLR）

• 向前看LR技术（Look-Ahead LR）

归约

归约过程等于一个反向最右推导。

句柄

最右句型中和某个产生式体（右部）相匹配的子串，对它的归约代表了该最右句型的最右推导的最后一步。

• 在一个最右句型中，句柄右边只有终结符号

• 如果文法是无二义性的，那么每个句型有且只有一个句柄

自底向上分析的过程就是识别和归约句柄的过程。