移进归约分析（进阶）
复习
- 预测分析：自顶向下，靠查表决定展开哪条产生式
- 上下文无关文法：产生式与推导
- 栈：后进先出
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 移进归约从输入出发，逐步归约成起始符号
- 它用栈保存已经读入的部分
- “移进”是把词压栈，“归约”是把栈顶符号替换成非终结符
- LR 分析是这类方法的代表
正文
预测分析是“自顶向下”：从起始符号出发，一路往下展开。移进归约分析反了过来，是“自底向上”：从输入串出发，一步步归约，最终归约到起始符号。
两个动作，一个栈
它靠一个栈来工作，只有两个基本动作：
- 移进（shift）：把当前输入词压入栈
- 归约（reduce）：如果栈顶的一段符号，恰好是某条产生式右边的形式，就把这段“替换”成该产生式左边的非终结符
就这样，一边把词压进栈，一边在合适的时候把栈顶的片段归约成更大的语法成分，直到整个输入被归约成起始符号，分析成功。
一个例子
拿 1 + 2 * 3 举例（假设已有“项”“表达式”等非终结符）：
- 移进
1，它是数字，归约为“因子” - 再归约为“项”
- 移进
+…… - 读到
2 * 3时，先把乘法所在的2 * 3归约成一个“项”，再和前面的1 + ...归约
注意最后一步：乘法的归约先于加法。这正好把优先级“体现”了出来——不需要文法分层，归约的时机本身就带来了优先级。
好处与麻烦
移进归约的优点，是能处理的文法范围更广，包括很多左递归的、自然写法的程序语言文法，不必像 LL 那样先大改。以 LR 分析为代表的方法，是很多工业级编译器的选择。
但它也有自己的麻烦：在每一步，究竟该“移进”还是“归约”、该归约哪条产生式，有时并不唯一，会产生冲突（移进／归约冲突、归约／归约冲突）。处理这些冲突，是构造分析表时的核心工作。
把两种方法放一起看：
- 自顶向下（递归下降、预测分析）：直观、易手写，但受文法限制
- 自底向上（移进归约、LR）：文法适应性广，但自动构造分析表较复杂
又是不出所料的取舍：写起来舒服，还是用起来通用，往往只能偏向一头。
思考题 1
移进归约分析和预测分析，在“方向”上有什么不同？
思考题 2
“移进”和“归约”分别是什么动作？
小结
知识点
- 移进归约是自底向上的分析方式
- 移进把词压栈，归约把栈顶片段替换成非终结符
- 归约时机可体现运算优先级
- LR 分析适用文法更广，但分析表构造较复杂
参考资料
- Wikipedia(zh)：LR解析器：自底向上的移进归约分析
- Wikipedia(zh)：语法分析：自顶向下与自底向上的对比
思考题答案（仅供参考）
思考题 1
预测分析是自顶向下：从起始符号出发，逐步展开成具体的词。移进归约是自底向上：从输入的词出发，逐步归约、合并，最终回到起始符号。方向正好相反。
思考题 2
“移进”是把当前输入的词压入分析栈；“归约”是在栈顶出现某条产生式右边的符号序列时，把它替换成该产生式左边的非终结符，相当于识别出一个更大的语法成分。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪