编译原理之美
宫文学
北京物演科技CEO
立即订阅
8171 人已学习
课程目录
已完结 43 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 为什么你要学习编译原理?
免费
实现一门脚本语言 · 原理篇 (13讲)
01 | 理解代码:编译器的前端技术
02 | 正则文法和有限自动机:纯手工打造词法分析器
03 | 语法分析(一):纯手工打造公式计算器
04 | 语法分析(二):解决二元表达式中的难点
05 | 语法分析(三):实现一门简单的脚本语言
06 | 编译器前端工具(一):用Antlr生成词法、语法分析器
07 | 编译器前端工具(二):用Antlr重构脚本语言
08 | 作用域和生存期:实现块作用域和函数
09 | 面向对象:实现数据和方法的封装
10 | 闭包: 理解了原理,它就不反直觉了
11 | 语义分析(上):如何建立一个完善的类型系统?
12 | 语义分析(下):如何做上下文相关情况的处理?
13 | 继承和多态:面向对象运行期的动态特性
实现一门脚本语言 · 应用篇 (2讲)
14 | 前端技术应用(一):如何透明地支持数据库分库分表?
15 | 前端技术应用(二):如何设计一个报表工具?
实现一门脚本语言 · 算法篇 (3讲)
16 | NFA和DFA:如何自己实现一个正则表达式工具?
17 | First和Follow集合:用LL算法推演一个实例
18 | 移进和规约:用LR算法推演一个实例
实现一门脚本语言 · 热点答疑与用户故事 (2讲)
19 | 案例总结与热点问题答疑:对于左递归的语法,为什么我的推导不是左递归的?
用户故事 | 因为热爱,所以坚持
编译原理 · 期中考试周 (1讲)
期中考试 | 来赴一场100分的约定吧!
免费
实现一门编译型语言 · 原理篇 (12讲)
20 | 高效运行:编译器的后端技术
21 | 运行时机制:突破现象看本质,透过语法看运行时
22 | 生成汇编代码(一):汇编语言其实不难学
加餐 | 汇编代码编程与栈帧管理
23 | 生成汇编代码(二):把脚本编译成可执行文件
24 | 中间代码:兼容不同的语言和硬件
25 | 后端技术的重用:LLVM不仅仅让你高效
26 | 生成IR:实现静态编译的语言
27 | 代码优化:为什么你的代码比他的更高效?
28 | 数据流分析:你写的程序,它更懂
29 | 目标代码的生成和优化(一):如何适应各种硬件架构?
30 | 目标代码的生成和优化(二):如何适应各种硬件架构?
实现一门编译型语言 · 应用篇 (2讲)
31 | 内存计算:对海量数据做计算,到底可以有多快?
32 | 字节码生成:为什么Spring技术很强大?
实现一门编译型语言 · 扩展篇 (3讲)
33 | 垃圾收集:能否不停下整个世界?
34 | 运行时优化:即时编译的原理和作用
35 | 案例总结与热点问题答疑:后端部分真的比前端部分难吗?
面向未来的编程语言 (3讲)
36 | 当前技术的发展趋势以及其对编译技术的影响
37 | 云编程:云计算会如何改变编程模式?
38 | 元编程:一边写程序,一边写语言
结束语 (1讲)
结束语 | 用程序语言,推动这个世界的演化
编译原理之美
登录|注册

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

宫文学 2019-09-23
到目前为止,我们所讨论的语法分析算法,都是自顶向下的。与之相对应的,是自底向上的算法,比如本节课要探讨的 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/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《编译原理之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(5)

  • Lamont

    start -> exp
    exp -> lvalue = rvalue
    exp -> rvalue
    lvalue -> Id
    lvalue -> *rvalue
    rvalue -> lvalue

    对这里最后两行的产生式不太理解,请问有对应哪种具体语言的语法吗?
    2019-11-03
  • 飞翔
    老师,不理解第 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
    2
  • 沉淀的梦想
    既然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
  • ZYS
    宫老师这个课件做的真棒👍,GCC语法分析用的是LR分析器么?Clang用的是什么语法分析器

    作者回复: GCC用过LR,后来用手写的递归下降算法取代了。Clang也是用的手写的递归下降算法。
    这说明,递归下降算法真的还是很有实用价值的:-)
    用手写代码的好处,是随时可以Hack。就像我们在解决手写实现左结合的时候,就是在做hack。

    2019-09-23
    1
收起评论
5
返回
顶部