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

05 | 语法分析(三):实现一门简单的脚本语言

宫文学 2019-08-23
前两节课结束后,我们已经掌握了表达式的解析,并通过一个简单的解释器实现了公式的计算。但这个解释器还是比较简单的,看上去还不大像一门语言。那么如何让它支持更多的功能,更像一门脚本语言呢?本节课,我会带你寻找答案。
我将继续带你实现一些功能,比如:
支持变量声明和初始化语句,就像“int age” “int age = 45”和“int age = 17+8+20”;
支持赋值语句“age = 45”;
在表达式中可以使用变量,例如“age + 10 *2”;
实现一个命令行终端,能够读取输入的语句并输出结果。
实现这些功能之后,我们的成果会更像一个脚本解释器。而且在这个过程中,我还会带你巩固语法分析中的递归下降算法,和你一起讨论“回溯”这个特征,让你对递归下降算法的特征理解得更加全面。
不过,为了实现这些新的语法,我们首先要把它们用语法规则描述出来。

增加所需要的语法规则

首先,一门脚本语言是要支持语句的,比如变量声明语句、赋值语句等等。单独一个表达式,也可以视为语句,叫做“表达式语句”。你在终端里输入 2+3;,就能回显出 5 来,这就是表达式作为一个语句在执行。按照我们的语法,无非是在表达式后面多了个分号而已。C 语言和 Java 都会采用分号作为语句结尾的标识,我们也可以这样写。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《编译原理之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(21)

  • janey
    像这里用java实现了一种脚本语言,但是这些java语句又是怎么被计算机识别的呢?

    作者回复: java语句当然是由java的编译器来识别了。
    不过你提了一个重要的事情。
    在编译领域,有一个事情,叫做自举(bootstraping),也就是这门语言的编译器可以用自己这门语言编写。这是语言迈向成熟的标志。一般前面的版本,是要借助别的语言编写编译器,但后面就应该用自己的语言来编译了。
    著名的语言都实现了自举。比如,go语言的编译器是用go编写的(早期版本不是。能实现自举,还是go发展历程上的一个历程碑),jdk里面自带了java语言的编译器,本身也是用java写的。

    2019-08-27
    1
    9
  • LDxy
    正则表达式匹配文本的时候也会导致回溯吧?好像还有可能因此导致严重的性能问题

    作者回复: 对。如果正则表达式的内部实现是基于NFA的,就会有这个问题。
    NFA和DFA这个知识点不适合在前期讲,会把初学者搞晕。我准备在后面找个机会放入这个知识点。

    2019-08-24
    4
  • C语言实现:
    https://github.com/KiLuYa/simpleScript

    C语言,没有现成的数据结构,没有 try catch throw 处理错误的机制,没有虚拟机的垃圾回收机制,感觉实现起来比Java要麻烦很多,尤其是繁琐的错误码判断,以及程序流程在多分支下的内存的手动申请和释放。
    遇到过一个国外公司的产品,它提供了脚本语言,但用户写程序,如果某一行有个语法bug,编译报错时,它会报连续十几行的错。学完这节内容就知道,应该是它的parser没有在检测到语法错误时停下来,还傻傻地带着错误继续parse,直到所有token都被处理掉。

    作者回复: 看你用C语言做了很多实践,非常好!
    针对你的问题,也跟你探讨一下:
    1.每门语言都有它的优势。很多编译器都是用C/C++编写的,比如可以更灵活的对内存管理,就是优势呀。JVM的实现,也没法用Java,还是要用比较底层的语言。
    2.错误处理这个问题比较复杂。最好的情况,是我们知道哪一个小范围是有错的,对这个部分报错,但其他部分继续处理。比如,你调用一个函数时,监测出参数的数量错了,但其他部分仍然可以继续去解析和处理。如果碰到一个错误,就完全停下,那也不行。这样做IDE的时候,就不够友好和智能。

    2019-09-29
    2
  • 安排
    有点感觉了,哈哈😄

    作者回复: 加油!

    2019-08-24
    2
  • Sudouble
    跟着课程做,一下就明白了。打卡第五节课
    https://github.com/potterhere/TheBeautyOfCompiling/tree/master/w5_ReadEvalPrintLoop

    作者回复: 看到你的github空间里有好几个项目,学习力很强!

    另外,能否把你的项目整个cmake文件,便于我编译运行?:)

    2019-10-18
    1
    1
  • windpiaoxue
    参考03-05实现的c语言版本
    https://github.com/windpiaoxue/simple_script.git

    作者回复: 看了,非常不错!点赞!
    连README.md都写得很清晰。
    你学习的效率很高呀!
    而且看来你有C语言的基础,所以到时学后端技术你也会毫不费力呀!

    2019-08-27
    1
  • wj
    老师, 还有个问题, 借此文问一下, 词法分析\语法分析等和机器学习有什么交集吗? 我有个场景想比较两个java文件的匹配度, 或者两段代码的匹配度, 不知道机器学习在这个场景是否可以应用, 以及如何应用呢?谢谢~

    作者回复: 你提了一个好问题。
    其实,人工智能的发展史经历了两个不同的路径。 早期,更多的是演绎逻辑。就是人为制定规则,比如自然语言翻译的规则,并不断执行这些规则。
    第二条路径,是最近复兴的机器学习的方法。它更多的是归纳逻辑。机器学习是通过数据的训练,把规则归纳出来。这些归纳出来的规则目前还是比较黑盒的,人比较难以解读,但却很有用,更加准确。
    你的需求场景用这两种方法应该都能解决,只不过落地时还要考虑很多细节和限制因素。

    2019-08-24
    1
  • 仵浩
    表达式负数怎么处理呢?

    作者回复: 负数有两种处理办法:
    1.在词法分析阶段,就把它作为一个字面量提取出来。这有一定的难度。比如,a - 3和 a - -3要能准确地把减号和负号区分开。但也不是不能做到。
    2.把减号作为一元运算符处理。
    示例用的语法规则,是按照第二种方式处理的。

    2019-11-21
  • 缺个豆饼吗
    https://github.com/yuguomin/my-compiler
    老师,作业来啦~

    作者回复: 棒!TypeScript版本的!

    2019-10-08
  • 阿尔伯特
    https://github.com/albertabc/compiler
    继续攒代码。我在老师前面几节的基础上写的本讲的一个sample。老师在本讲重点讲解了回溯。但是我在实现中仔细想了想。
    exp -> or | or = exp
    上次课的第一条语法规则其实是针对表达式的,但是这条规则,事实上是合并了表达式语句和赋值语句。所以本节的新的语法规则是不是可以就优化掉。
    这里一旦不区分普通表达式,和赋值语句,也就避免了一次回溯。
    从中,是不是可以有这样的推论,就好像用EBNF,可以通过语法规则的变换来避免左递归,也同样用规则来减少回溯?
    谢谢老师。

    作者回复: 首先,赋值在C和Java里都是表达式,跟加法表达式没啥区别,它也是有值的。
    第二,确实可以通过语法规则的设计来避免冲突,包括避免回溯。

    2019-09-29
  • 曾经瘦过
    学完了这部分之后 感觉 其实编译没有想的那么复杂,通过递归下降,对所有的可能做了处理.不符合的可能回溯 去匹配其他的. 有点感觉了,希望可以一步一步啃下编译原理

    作者回复: 这个“感觉”很重要。保持好。遇到挫折也不要在意!

    2019-09-17
  • nil
    老师你好,看到回溯这个关键字,让我想起学生时代解八皇后问题,用的就是试探&回溯。也是通过八皇后体会到了递归的美妙。递归思维比较符合人的思维,而循环更符合计算机。看了老师的一系列文章,现在对编译原理没有这么惧怕了,一旦揭开技术神秘的面纱后,展现在眼前的只剩下一片美妙!加油!

    作者回复: 感谢分享!
    一起加油!

    2019-09-11
  • 宇智波芭芭干
    描述算法逻辑时建议采用流程图的形式,一个清晰的流程图一目了然,远不是一大段啰嗦的文字可比的

    作者回复: 谢谢你的建议!
    好的,我会在迭代版本中改进!

    2019-09-10
  • Smallfly
    本讲 Swift 版本实现:

    https://github.com/iostalks/PlayWithCompiler/tree/lecture-5

    欢迎参考。

    作者回复: 点赞!

    2019-09-04
  • 中年男子
    有了前几讲的基础,这一讲很轻松搞定,根据宫老师的java代码我实现了C++版本,其中一些不太清晰的概念通过代码也理解了,老师真的很棒!

    作者回复: 谢谢肯定!
    编译原理这门课,是学原理可能学不懂。但真正动手,其实都能写出来。早期写编译器的先驱并没有编译原理课。
    并且,很多具体实现过程,是可以偏离死搬教条的原理的。比如,理想情况下要设计无二义性文法。实际应用中,只要针对某个具体算法是无二义的就行了。能实际有用才是硬道理。

    2019-08-25
  • catplanet
    根据老师讲解,实现了一个 golang 的版本 https://repl.it/@catplanet007/simple-interpreter

    作者回复: 你用的这个在线工具很酷。可以提供一个运行环境直接跑!很棒!
    我玩了好一会 :-D

    2019-08-24
  • wj
    老师, 我发现对一些基本术语, 比如 Statement, expression, binaryExpression, 等不太会分辨, 请问有什么书或资料可以推荐系统看一下吗? 谢谢

    作者回复: 可以参考成熟的语法规则文件,去琢磨。
    大致来说,你从字面意思来理解它就好了。比如语句、表达式、二元表达式。
    本课程都是倾向于采用这种有意义的单词,而不是像教科书那样只写一个字母,太抽象。
    而在实际工程中,我们总是让自己的语法单元更具可读性,这样更实用。

    2019-08-24
  • 沉淀的梦想
    Java中的范型语法应该是需要回溯的。感觉计算时间的浪费和代码长度应该是指数关系。

    作者回复: 为你的动脑思考点赞!
    泛型语法,嗯嗯有可能。
    深度优先算法的回溯,时间复杂性(大O)不是指数的。广度优先的才是指数的。这个在15讲会再总结一遍。
    深度优先算法,实际浪费不多,所以是有实用价值的一个算法。再加上预测功能就完美了。讲LL算法的时候会再回过来说这个事情。

    2019-08-23
  • 许童童
    老师讲得好啊,不要给自己设天花板,不断努力,成功最终会属于你。

    作者回复: 是的。
    很多时候,做某件事情真正的阻力是畏惧,是根本不去做...

    2019-08-23
  • 雲至
    老师 那个verbase是什么意思呀

    作者回复: 是verbose吧?也就是启动“话痨”模式,打印输出等多信息。
    有一些linux命令习惯上会用-v参数来表达这个意思 :-D

    2019-08-23
    1
收起评论
21
返回
顶部