编译原理之美
宫文学
北京物演科技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讲)
结束语 | 用程序语言,推动这个世界的演化
编译原理之美
登录|注册

04 | 语法分析(二):解决二元表达式中的难点

宫文学 2019-08-21
在“03 | 语法分析(一):纯手工打造公式计算器”中,我们已经初步实现了一个公式计算器。而且你还在这个过程中,直观地获得了写语法分析程序的体验,在一定程度上破除了对语法分析算法的神秘感。
当然了,你也遇到了一些问题,比如怎么消除左递归,怎么确保正确的优先级和结合性。所以本节课的主要目的就是解决这几个问题,让你掌握像算术运算这样的二元表达式(Binary Expression)。
不过在课程开始之前,我想先带你简单地温习一下什么是左递归(Left Recursive)、优先级(Priority)和结合性(Associativity)。
在二元表达式的语法规则中,如果产生式的第一个元素是它自身,那么程序就会无限地递归下去,这种情况就叫做左递归。比如加法表达式的产生式“加法表达式 + 乘法表达式”,就是左递归的。而优先级和结合性则是计算机语言中与表达式有关的核心概念。它们都涉及了语法规则的设计问题。
我们要想深入探讨语法规则设计,需要像在词法分析环节一样,先了解如何用形式化的方法表达语法规则。“工欲善其事必先利其器”。熟练地阅读和书写语法规则,是我们在语法分析环节需要掌握的一项基本功。
所以本节课我会先带你了解如何写语法规则,然后在此基础上,带你解决上面提到的三个问题。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《编译原理之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(34)

  • 谱写未来
    只有第一步用add,接下来都用add',后面不是都是add'了,还是左边那张图不是吗?

    作者回复: 是的。

    我们通过改写规则的方法,能够避免左递归,但无法同时照顾结合性。这是很多教科书都没有提到的一件事情。

    好在,这个事情比较简单,因为改写后的规则,是多了一个标准的“尾巴”。对,很多人都称呼它为尾巴。这个尾巴可以特别处理。

    也就是说,结合性的信息已经不是单纯通过上下文无关文法提供了,要辅助额外的信息。

    无独有偶,还有的作者用别的方法来解决算法优先级问题,比如LLVM的一个初学者教程,用的也是标注算符优先级的方法,也要在文法的基础上提供额外的信息给算法。

    http://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index.html

    本课程讲究实践。在实践中才会看到这些教科书上讲不到的点,但在面对实际问题时必须要解决。

    2019-08-21
    7
  • Enzo
    老师 看不懂以下的公式
    add -> mul | add + mul
    mul -> pri | mul * pri
    pri -> Id | Num | (add)
    是需要找本书看看吗?

    作者回复: 我给你解释一下吧:
    以 add -> mul | add + mul 为例,
    -> 意思是推导出;
    | 意思是“或者”
    这个加号,我回头修改一下吧,可以用引号引起来,'+'只是匹配一个+号字符的意思,没有别的意思。
    所以,这个产生式的意思是:
    加法表达式,要么是一个乘法表达式,要么是一个加法表达式,后面跟个+号,然后再跟一个乘法表达式。

    参考书的话,看看这个链接:https://time.geekbang.org/column/article/125948

    2019-09-06
    5
  • 贾献华
    https://github.com/iOSDevLog/Logo
    Swift 版《编译原理之美》代码,可以在 iOS 上运行。

    作者回复: 厉害!点赞!

    2019-08-20
    1
    4
  • knull
    老师,我简单研究了下bnf,我觉得你写法最好修正下,不然不好看。比如:
    原来的写法:add -> mul (+ mul)*
    现在的写法:add -> mul ('+' mul)*
    '+'表示关键字;
    + 直接用,表示1个活多个;
    加单引号以示区分,看起来方便一点

    作者回复: 有道理!用EBNF的话,+号有特殊含义。
    我们修改一下文稿。
    谢谢你的建议,你很细心,并且自己去做研究了!

    2019-08-28
    3
  • pwlazy
    2+3+4+5生产的AST 是否是这样的?

    Programm Calculator
        
          AdditiveExp +
            AdditiveExp +
                AdditiveExp +
                    IntLiteral 2
                    IntLiteral 3
                IntLiteral 4
            IntLiteral 5

    作者回复: 是,没错。

    2019-08-21
    1
    3
  • 春去春又来
    老师 上一讲看懂了 这一讲在推导公式的时候迷糊了。可以加点推导过程的详细讲解嘛 而不是直接给一个推导的结果图

    作者回复: 好的,我对于公式推导过程再加个图。加完了在回复中告诉你。

    你指的是用:
    add -> mul add'
    add' -> + mul add' | ε

    来推导2+3+4的过程不清楚吗?

    2019-08-21
    3
  • 许童童
    老师可以说一下生成出来的AST怎么使用吗?
    https://github.com/jamiebuilds/the-super-tiny-compiler
    这个编译器写得怎么样,老师可以说一下吗?

    作者回复: AST是对计算机语言的结构化表示,它是一切后续工作的基础,比如做语义分析,翻译成目标代码。

    看了一下你发的那个链接。是从类似lisp语言的函数调用翻译到C语言的格式。这属于语言翻译的范畴。

    我有两点点评:
    1.lisp语言很容易翻译,一个递归下降算法肯定搞定。因为它的语法结构很简单,所有的语法结构都是一层层括号的嵌套。
    2.翻译后得到AST,再生成C的格式,这就很简单了。基本上就是把括号位置改一下而已。

    感谢你经常参与讨论!

    2019-08-21
    2
  • nil
    老师你好,问个问题。最终通过循环来消除递归带来的二元预算符的结合性问题?能否直接在递归中消除结合性问题?

    作者回复: 理论上是可以的,但需要给算法提供额外的信息。
    采用递归下降算法的时候,我们在函数中标准的处理放肆,都是创建一个AST节点,并返回给调用者。调用者都是把返回的AST作为自己的子节点。
    如果要改变结合性,相当于要知道什么时候把返回的节点作为自己的父节点。
    Antlr里用属性标注的方法,来提供这个额外的信息。这种信息在标准的上下文无关文法中是无法提供的。

    2019-09-11
    1
  • 阿尔伯特
    https://github.com/albertabc/compiler
    继续攒代码。
    有了上节课的基础,这节相对比较容易理解。用文法的形式推导,最终消除了左递归的思路我觉得很有意思,用左右递归代表结合性,用文法上下级实现了优先级,这些可以作为解决问题的一个思路和方法,用比较平常的普通方法解决了这些问题。感觉比中缀后缀表达式容易掌握。

    作者回复: 嗯。编译且运行了一下。

    2019-09-11
    1
  • Enzo

    exp -> or | or = exp
    or -> and | or || and
    and -> equal | and && equal
    equal -> rel | equal == rel | equal != rel
    rel -> add | rel > add | rel < add | rel >= add | rel <= add
    add -> mul | add + mul | add - mul
    mul -> pri | mul * pri | mul / pri
     老师不懂这里的 + - >= 等符号的意思 能推荐本书 吗

    作者回复: 所有的操作符,你可以加上引号,也就是去匹配这样一个字符而已。没有太复杂的意思。
    add -> mul | add '+' mul | add '-' mul

    参考书籍的话,参见这篇攻略:https://time.geekbang.org/column/article/125948

    2019-09-06
    1
  • 半桶水
    是否可以给一些扩展资料的链接,有些概念,推导还是需要更多资料和练习才能掌握

    作者回复: 如果想练习语法规则的推导,那么随便买哪本教材都可以。一般也都会带些练习。

    其他的扩展资料,我后面有想到的,会提供链接。

    2019-08-21
    1
  • 北冥Master
    四则运算中的负号和减号怎么处理?-1+2,-(1+4)
    2019-12-07
  • ldd
    老师,我想问下,我之前的理解是把中缀表达式用栈改写成后缀表达式也可以生成AST树,老师推荐这种做法吗?
    2019-12-04
  • 慧强
    左递归可以通过改写语法规则来避免,而改写后的语法又可以表达成简洁的 EBNF 格式,从而启发我们用循环代替右递归。 是不是错了,,应该为 从而启发我们用循环代替左递归?
    2019-12-01
  • Geek_e986e3
    老师想问问

    add -> mul add'
    add' -> + mul add' | ε
    这个表达式是啥意思 为何和之前的语法不一样。
    还有 没看明白咋就变成了这个:add -> mul (+ mul)*
    能解释下吗?
    2019-11-15
  • knull
    add -> mul | add + mul 改成add-> pri |add + mul,是否可以

    作者回复: 这两个产生式应该是不等价的。
    你修改后的产生式,不能解析3*5这样的纯乘法表达式。

    2019-10-28
  • eviltion
    add -> mul add'
    add' -> + mul add' | ε
    这个是顺序匹配吗?就是先匹配mul然后返回的是2再匹配add'

    作者回复: 对的,递归下降算法都是先匹配完第一个元素,再匹配第二个,从左向右。

    2019-10-19
  • 郑家庄赶大车的老郑
    作为一个外行,最开始影响我理解的竟然是"推导"这样的术语,硬头皮看了,似乎是“可以展开为”的意思,不知道理解对了没有。

    作者回复: 非常对!
    1.就是要把这些看上去很难的概念,变成自己的直观理解。
    2.基础概念,比如啥叫推导,就是要重视。不要觉得不好意思。还是那个话,在别人提不出问题的地方提问,才叫厉害。基础概念,我们容易一模糊就过去了。但推敲一下呢,很有意思。

    2019-10-07
    1
  • 缺个豆饼吗
    继续交作业
    https://github.com/yuguomin/my-compiler

    作者回复: 棒!

    2019-09-26
    1
  • 曾经瘦过
    上一节 看懂了之后再看这一节 感觉简单了好多

    作者回复: Great!

    2019-09-16
收起评论
34
返回
顶部