18 | 移进和规约：用LR算法推演一个实例

宫文学



该思维导图由 AI 生成，仅供参考

到目前为止，我们所讨论的语法分析算法，都是自顶向下的。与之相对应的，是自底向上的算法，比如本节课要探讨的 LR 算法家族。
LR 算法是一种自底向上的算法，它能够支持更多的语法，而且没有左递归的问题。第一个字母 L，与 LL 算法的第一个 L 一样，代表从左向右读入程序。第二个字母 R，指的是 RightMost（最右推导），也就是在使用产生式的时候，是从右往左依次展开非终结符。例如，对于“add->add+mul”这样一个产生式，是优先把 mul 展开，然后再是 add。在接下来的讲解过程中，你会看到这个过程。
自顶向下的算法，是递归地做模式匹配，从而逐步地构造出 AST。那么自底向上的算法是如何构造出 AST 的呢？答案是用移进 - 规约的算法。
本节课，我就带你通过移进 - 规约方法，自底向上地构造 AST，完成语法的解析。接下来，我们先通过一个例子看看自底向上语法分析的过程。
通过实例了解自底向上语法分析的过程我们选择熟悉的语法规则：
add -> mul
add -> add + mul
mul -> pri
mul -> mul * pri  
pri -> Int | (add)
然后来解析“2+3*5”这个表达式，AST 如下：
我们分步骤看一下解析的具体过程。
第 1 步，看到第一个 Token，是 Int，2。我们把它作为 AST 的第一个节点，同时把它放到一个栈里（就是图中红线左边的部分）。这个栈代表着正在处理的一些 AST 节点，把 Token 移到栈里的动作叫做移进（Shift）。

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

LR算法是一种自底向上的语法分析算法，通过移进-规约方法逐步构造AST完成语法解析。本文详细介绍了LR算法的原理和类型，包括LR(0)、SLR(k)、LALR(k)和LR(k)等级别的算法特点和实现细节。文章强调了句柄的重要性，即产生式的右边部分及其在句型中的位置，以及如何通过句柄做出正确的选择。LR算法要解决的核心问题是如何找到正确的句柄。通过实例生动地展示了LR算法的实际运用，为读者提供了深入理解自底向上语法分析的方法和原理的实用指南。此外，文章还介绍了LR算法的类型和实现细节，建议读者多做推导练习，以建立直觉认知。LR算法的特点和实际应用使得本文成为一份有价值的技术指南。文章还提到LR算法的缺点和改进，以及对于LR算法的思考和应用。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《编译原理之美》，新⼈⾸单¥59

立即购买

登录后留言

全部留言(12)

最新
精选

沉淀的梦想
既然LALR(1)有性能低的缺点，那为什么yacc和bison还使用它呢？用yacc和bison生成的语法分析器性能差的话，为什么还有这么多人用？
作者回复: LALR(1)比LR(1)的性能要高。实际上，它是LR家族中比较优秀的一个算法了，所以实用度已经比较高，这也是yacc和bison用它的原因。我再看看文稿，是不是我有什么地方表达得不清楚，引起了你的误解。另外，我补充几点： 1.就算是LR(1)算法，在处理现代语言的一些语法特征时（泛型、Lamda等），也会产生很多冲突（移进-规约冲突，规约-规约冲突）。所以，用yacc和bison，可以支持实现比较简单的语法，但到了更加复杂的语法，就不够了。 2.GLR是很多人关注的一个LR家族的算法，具有处理冲突的能力。 3.我们课程中讲的单一的算法，无论是LL的还是LR的，在处理复杂的语法时都不够。有语法处理能力的原因，也有处理错误信息方面的考虑。所以，生产环境中支持比较复杂语法的编译器，都不会这么的单线条。GCC之前用过LALR，现在改为纯手写的基于递归下降的（如果我没记错的话...）了。
2019-09-25

4
minghu6
用Rust写了一个完整demo: https://bitbucket.org/minghu6code/alg-parser/src/master/
作者回复: 我的bitbucket账号不允许看你的页面。 “We can't let you see this page”... 奇怪！
2021-05-26
3
2
余晓飞
start -> exp exp -> lvalue = rvalue exp -> rvalue lvalue -> Id lvalue -> *rvalue rvalue -> lvalue 对这里最后两行的产生式不太理解，请问有对应哪种具体语言的语法吗？
作者回复: C语言。左值，代表可以放在赋值符号左边的值，在编译器内部，要把它解析成一个地址，这样才能修改值。右值，就是一般意义上的值，比如一个整形字面量。 "a = 10 * 2;" 这个表达式中，a是左值，编译器会把它编译成一个内存地址（或寄存器），而10、2、10*2都是右值。 lvalue -> *rvalue : 是取某个右值的地址，也就是一个指针。通过这个指针，可以改变其值。 rvalue -> lvalue：意思是左值是可以用在需要右值的地方（但反过来是不行的）。
2019-11-03

2
ZYS
宫老师这个课件做的真棒👍，GCC语法分析用的是LR分析器么？Clang用的是什么语法分析器
作者回复: GCC用过LR，后来用手写的递归下降算法取代了。Clang也是用的手写的递归下降算法。这说明，递归下降算法真的还是很有实用价值的:-) 用手写代码的好处，是随时可以Hack。就像我们在解决手写实现左结合的时候，就是在做hack。
2019-09-23
2
1
Amy
一个小typo： LR 算法中的 R，带有反向（Reverse）和最右（Reightmost）这两层含义。 s/Reightmost/Rightmost
作者回复: 收到！感谢！我让小编同学改一下！
2021-08-04


lion_fly
mark一下，算法篇趟过去了
作者回复: 算法部分会有点抽象。多用图形化的方法做实例的推演，有助于你深入理解编译器的运行机制。
2020-11-03
2

飞翔
老师，不理解第 13 步，根据“add->add+mul”规约到 add 为什么会回到状态 2 状态2中“add->add.+mul”点号不是在中间吗，状态1的点号在开始
作者回复: 用状态2中的第一个产生式：start->add.
2019-10-17


xiaobang
这一章看的有点困难，不理解那个NFA怎么来的
作者回复: 那个NFA表达了在做正向推导的时候，可能采取的所有可能的推导路径。用了Item这种方式表达出来了而已。你按照我这种说法看看，是不是那个NFA就代表了示例的语法的推导路径。把这一关过了，转DFA的过程你肯定是理解的。
2019-09-25
3

locke.wei
在状态 2，如果下一个输入是“=”，那么做移进和规约都是可以的。因为“=”在 rvalue 的 Follow 集合中。这里我理解"="应该是lvalue的follow集合？
2020-05-09

6
温雅小公子
把follow集合拆解是怎么做的？
2022-10-10归属地：河北

1

收起评论