本章内容对应教材 3.5节。先讨论“自下而上”语法分析（Bottom-Up Parsing）的一般方法、短语/直接短语/句柄三个重要的概念，接着介绍一般的移进归约分析，重点讨论基于移进归约分析的一般 LR 分析、SLR（1）分析器的构造。
【本节重点】基本方法；短语/直接短语/句柄；最左归约；剪句柄；移进-归约分析。
【本节难点】如何找句柄；移进-归约分析原理。
一、什么是自下而上分析
1.1 基本思路：
对任何输入序列 ω 的语法分析，都是从 ω 开始，反复进行最左归约，谋求对 ω 的匹配,最终得到文法的开始符号，或者发现一个错误。
1.2 基本特点：
（1）从左到右扫描输入序列，边扫描边分析；
（2）采用自下而上的方式为输入 ω 构造分析树。
1.3 自上而下 vs. 自下而上
自上而下的语法分析是根据文法产生语言的过程，其本质是在扫描输入序列过程中，从文法开始符号 S 开始，尝试采用“最左推导”来产生一颗与输入序列匹配的分析树；
自下而上的语法分析是根据文法对输入进行类似于归纳总结的过程，其本质是在扫描输入序列过程中，采用“最左归约”，看看能否将其归约为文法开始符号 S。
它们的名字已经体现了二者对分析树的构造过程。
类比： 自上而下 --> 写文章； 自下而上 --> 读（理解）文章。
二、重要概念与剪句柄
2.1 短语、直接短语、句柄
教材中的【定义3.13】给出了这三个术语的定义（此处省略定义之文本）。
理解概念的要点：
（1）短语与句型是什么关系？ 若干文法符号构成短语的两个要素是？
（2）三个概念都是针对“句型”而言的，而不是针对任意的文法符号序列。
（3）句柄是特殊的直接短语，直接短语是特殊的短语。特殊在哪些方面？
（4）一个句型中，至少有几个 短语/直接短语/句柄？
2.2 短语、直接短语、句柄在分析树上的表现
根据概念之定义，要找出某个句型的短语/直接短语/句柄，比较困难。但如果我们根据它们在句型的分析树上的表现形式来寻找的话，则比较直观、比较容易：
| 要找的结构 | 在分析树上的表现 |
| 短语 | 以某个非终结符为根子树中，所有从左到右的叶子 |
| 直接短语 | 位于树的末端，且只有父子关系的子树中所有从左到右排列的叶子（树高为2） |
| 句柄 | 最左边父子关系树中所有从左到右排列的叶子（若文法不是二义的，则每个句型的句柄是唯一的） |
在分析树上寻找短语/直接短语/句柄，应注意：
（1）它们一定位于树的叶子；
（2）对于这些叶子，你应将标记它们的文法符号按照 从左到右 的顺序写出来；
（3）对于直接短语，如何确定它是否为最左边的那个？只能是采用深度优先地遍历，先遇到的直接短语，就是最左边的，它就是句型的句柄。
（4）不同的句型具有不同的分析树，反之亦然（若文法不是二义的话）。
2.3 最左归约 &剪句柄
教材中的【定义3.14】给出了最左归约的定义（此处省略定义之文本）。
提示1：最左归约，就是逆序的最右推导。前者称为“规范归约”，后者称为“规范推导”。
提示2：无论是推导，还是归约，都是对文法符号序列进行变换的策略，但推导是将文法符号序列中的非终结符用用其产生式右部替换（即展开），而归约则是将文法符号序列中的“句柄”用它所属产生式左部来替换。
提示3：在本课程学习中，将最左推导应用于自上而下的语法分析，将最右归约应用于自下而上的移进归约分析（含 LR 分析）。
术语“剪句柄”： 是一步最左归约的别名。指对于待分析的输入序列，假设一开始就有了分析树，那么我们就在树上很容易地找到句柄，接着剪掉句柄（即丢弃句柄对应的叶子结点），再找句柄、剪句柄...。这个过程持续到仅剩树根为止。【这个过程实际上就是语法分析过程】
三、移进归约分析（器）
虽然在分析树上反复“剪句柄”很直观，但实际上，分析树不可能一开始就有了，因为还没有进行语法分析呢！
那么在真正的自下而上分析中，如何实现找句柄、剪句柄？即如何确定句柄已经形成，以及选择哪个产生式进行归约。目前较常用的解决办法就是采用“移进归约分析”（Shift-Reduct Parsing）方法，并据之构造移进归约分析器。
移进归约分析器的结构模型与棕色图，与预测分析器类似（其结构模型如蓝色图），都是对下推自动机的实现，但落地的具体措施不同。
【注意：移进归约分析器也存在多种不同的实现，如 LR 分析就是实现方式之一】
不同之处：
（1）驱动器算法不同，这也决定了下面的不同；
（2）改变格局的动作不同；
（3）分析表的结构、使用时机不同；
（4）“栈”中存放的信息不同。
相同之处：
（1）都是“表驱动型”的语法分析器；
（2）都采用“格局”、“格局变化”的方式完成分析，但改变格局的动作不同；
（3）只要分析能够到达“接受”格局，则表明输入序列可被接受（是正确的）；
（4）只要分析到达了某个“出错”格局，则表明输入序列不可被接受（存在语法错误）。