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

01 | 理解代码:编译器的前端技术

宫文学 2019-08-14
在开篇词里,我分享了一些使用编译技术的场景。其中有的场景,你只要掌握编译器的前端技术就能解决。比如文本分析场景,软件需要用户自定义功能的场景以及前端编程语言的翻译场景等。而且咱们大学讲的编译原理,也是侧重讲解前端技术,可见编译器的前端技术有多么重要。
当然了,这里的“前端(Front End)”指的是编译器对程序代码的分析和理解过程。它通常只跟语言的语法有关,跟目标机器无关。而与之对应的“后端(Back End)”则是生成目标代码的过程,跟目标机器有关。为了方便你理解,我用一张图直观地展现了编译器的整个编译过程。
你可以看到,编译器的“前端”技术分为词法分析、语法分析语义分析三个部分。而它主要涉及自动机和形式语言方面的基础的计算理论。
这些抽象的理论也许会让你“撞墙”,不过不用担心,我今天会把难懂的理论放到一边,用你听得懂的大白话,联系实际使用的场景,带你直观地理解它们,让你学完本节课之后,实现以下目标:
对编译过程以及其中的技术点有个宏观、概要的了解。
能够在大脑里绘制一张清晰的知识地图,以应对工作需要。比如分析一个日志文件时,你能知道所对应的技术点,从而针对性地解决问题。
好了,接下来让我们正式进入今天的课程吧!
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《编译原理之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(98)

  • coder
    我做过一款已经投入商用的编译器,从编译器的前端到中端的优化,再到后端针对某个特定architecture的代码生成以及优化,完整地趟过一遍,编译器的实现是基于clang和llvm的,目前的感觉是,工程经验确实积累了不少。antlr,flex,bison等这些工具也都用过。所以在看到课程目录时,感觉比较熟悉,目录中提到的东西都是知道的。

    但是我目前的感觉是,自己在理论方面的积累还是有些欠缺的,那些PL相关的理论也同样重要,包括图灵机,状态机,计算模型,lambda演算,类型和类型系统等,所以希望老师也能够也讲一下这部分理论🌝🌝🌝

    作者回复: 看来我要跟你学习才对:)

    这门课是实战和原理并重。但在设计上,会先让同学们建立对编译的直观感受,然后再引导到对算法的兴趣上。所以,在前端部分,我把算法的总结和提升放到了最后部分。因为这个时候,大家都已经没有陌生感、恐惧感了,学算法也就顺理成章了。

    你的经验已经比大部分同学多。我也争取把理论这部分也在课程里搞好!

    2019-08-14
    2
    54
  • 梓航(﹏)
    程序的某个地方写错了,比如某个关键词拼错,少逗号,分号等,是在哪一个阶段发现的呢?

    作者回复: 在各个阶段都会发现一些错误。
    在词法分析阶段,可能会发现某些输入不符合我们的任何一条词法规则。
    关键词拼错,在词法分析阶段是发现不出来的,它会被识别成一个标识符。比如inta, 假设是笔误,少了空格,也是一个合法的标识符。
    在语法分析阶段,你说的少逗号,分号什么的,这些错误在语法分析阶段就可以识别出。因为不满足语法规则。
    还有一些必须要等到语义分析阶段才能发现错误。比如
    inta=10;
    语法是没错的。
    但我们真正想写的是:
    int a = 10;
    在语义检查的时候,对第一句就会检查出,之前并没有声明inta这个变量。所以可能是错误。

    不知道是否解答了你的疑问。在后面的课程例子中,我们会做出错处理。

    2019-08-16
    39
  • Simon
    之前基于ANTLR给游戏策划做了一套dsl 战斗技能解析器,策划只要在文件中配置技能的效果就行,战斗的时候根据配置的表达式去解析并计算伤害啥的。感觉策划们用的很爽,新增加技能或者修改技能效果再也不用找开发了。开发感觉更爽。😀️😀️

    作者回复: 对的,做DSL能够给具体的领域带来很大的帮助!感谢你分享游戏领域的经验!
    我知道游戏领域有人在做DSL,我对这个领域不太了解。马云也曾经参观国外的一个游戏公司,发现他们把平台做的很好,能够支持很多游戏的快速研发。他回来以后,在阿里提了中台的概念,目前在企业应用领域很流行。中台呀,游戏平台呀,编译原理都能发挥作用。

    2019-08-14
    4
    30
  • 公众号:业余草
    BAT为什么没有造出一门语言的轮子?

    作者回复: 首先呢,编译原理不仅仅是造大家通用的语言。有很多是用来解决领域问题的。比如,好像阿里内部就有一个语言,叫cava,是跟它的搜索引擎配合的。

    其次,我们做这些底层平台的时候,都要涉及编译。还是拿阿里的druid开源项目说事,它就手写了一个高速的sql parser。其他几家大的互联网公司肯定也有不少这种应用。

    华为的方舟编译器,不是也很争气吗?有人说它没有多少创新,但它就是效果显著呀。

    我跟大家一样,都期盼带有中国血统的、全球人都用的语言诞生出来。我相信时间不远了。这种事情需要技术底蕴,更重要的是需要产业发言权。这方面,我们是越来越强了!大家一起期盼!

    2019-08-15
    29
  • halweg
    很棒!
    之前看了一本从逻辑门构建一台带操作系统的计算机的书,卡在了那本书里jack的语言的编译上,
    这次希望可以搞懂

    作者回复: 如果我的哪一讲让你卡壳了,你要告诉我!我单独给你讲:)

    2019-08-14
    2
    24
  • Fan
    希望后面有具体的一些demo

    作者回复: 有的,有很多demo。这门课不是纯讲理论,而是拿实操带动我们学理论。
    第一节课是前端技术的概述。第二节就开始做例子了!示例代码到时候也释放出来。

    2019-08-14
    10
  • X中倪
    盘他

    作者回复: 对头!

    2019-08-14
    2
    8
  • Mr.J
    老师好,词法分析好理解一些,即程序识别出每个词汇,语法分析这个,拆分AST,打个比方,一个java代码:
    class A {
        int a = 2;
        boolean = false;
    }
    语法分析时,把这个拆分AST,比如,遇到class,定义为根节点,两个关键字int 和boolean为两个子节点,每个子节点下面继续拆分,可以这样理解不,一条完整的java代码,就是从最后一个自己点一直向上到某个节点?
    语义分析这个是在整个上下文中去进行的,定了全局变量a,在方法中使用a时,能够知道这个是在全居中定义过的那个a?

    作者回复: 你大的概念理解完全正确。
    这个类语法分析后会变成一棵树。像这样的语法,解析起来是很简单的。反倒是像表达式这样看似很简单的语法,解析起来反倒有难度。在后面的课程里会深入到细节。
    语义分析的关键点你也抓住了,就是上下文。语法阶段是上下文无关的,语义阶段则专门处理上下文。
    加油!

    2019-08-15
    1
    7
  • 旺旺
    讲的还是很易懂的,👍!

    作者回复: 谢谢鼓励。讲的易懂,是我准备这门课程最大的挑战。我会继续努力!

    2019-08-14
    1
    7
  • Rockbean
    请教老师,AST可不可以转成可视化UML

    作者回复: 我刚好研究过UML和MDA。

    UML是对世界的建模。我们普通的程序也是对世界的建模。所以,这两者之间应该是可以互相翻译的。就像一门高级语言可以翻译成另一门高级语言。

    我记得之前有一个方向,就是建好UML模型之后,程序自动生成。在这个意义上,UML就是一门计算机语言。

    2019-08-15
    1
    6
  • Rockbean
    想起标识符的命名为什么不能用数字开头,扫描到了数字,立马认为这个token是数字,不作标识符处理了

    作者回复: 对的。
    如果允许数字开头的标识符,处理起来要麻烦一点。但也不是不可以。改一改本文的有限自动机应该也能实现。

    2019-08-15
    6
  • William
    请问老师,JavaScript解释器 V8引擎或者Node.js解释器里内置了Antlr这些语法分析器吗,还是自己实现了一套?

    作者回复: 这些级别的项目,还是自己写的。因为会最契合项目的需求。比如速度、资源消耗、解析过程等方面的需求。因为对V8的编写者来说,语法分析这个层面的事情真的不是事情。你如果把前端技术学透,也不会觉得这是个事。
    另一方面,对于大多数项目来说,借助工具就足够了。比如,Hibernate,比如mysql workbench。后者就是用的antlr。

    2019-08-14
    6
  • William
    分析一下自己做得一些摘录。
    trick:
    mac 下的 clang命令可以编译C语言代码。
    术语:
    正则文法 最普通、最常见的规则
    有限自动机 有限个状态的自动机器
    词法分析 lexical analysis -> 分词
    * 实现原理:有限自动机
    * 现成的词法分析工具:Lex、GNU Flex
    语法分析 parser -> 根据语法规则识别出程序的语法结构 (抽象语法树AST)
    * 需要考虑优先级等等
    * 递归下降方法
    * 现成的语法分析工具:Yacc、GNU Bison、Antlr、JavaCC
    语义分析 semantic analysis -> 上下文分析、消除歧义
    * 变量引用消解、作用域
    * 合法性检查
    * 数据类型标识
    * 语义分析的某些结果,会作为属性标注在AST上

    作者回复: 记得这么认真!
    Great!

    2019-08-14
    5
  • babel的编译器大概看过看不太懂,我是做前端的,学了老师的课程能不能做一个页面设计器呢

    作者回复: 我自己做过表单设计器、报表设计器,跟你说的页面设计器应该有相似之处。
    界面模板引擎啦、前端的DSL啦,也都与你的兴趣有关联吧?这些都与编译技术有关。
    我后面在课程里还提供了一个报表系统的原型系统。估计也会对你有启发。也就是说,做前端方面的工具,真的经常用到编译技术。

    2019-08-14
    1
    5
  • frazer
    老师,不涉及 逻辑 分析么?

    作者回复: 当然要涉及。
    但我重视帮大家建立直觉的理解。一旦你直觉上理解那件事了,对它有感觉了,去做逻辑推理就很顺利了。
    我觉得,这种直接认知,是学好一门课的关键。

    2019-08-15
    4
  • x
    想问下老师,我是前端程序员,这门课适合我吗。。

    作者回复: 前端程序员当然有用。
    第一,react这样的框架好不好?当然好。但作者一定是有编译的功底才能做这件事情。实际上,它就是要把一个DSL转换成Javascript的基础功能。
    第二,typescript,也是前端的语言翻译工具。这是近几年的一个趋势,你用任何一种语言写前端,然后会被工具翻译成其他语言。flutter也在做这样的事情。把dart翻译成js。学好编译,有助于你深度切入这些技术。
    第三,webassembly就要开始迈入实用了。很多后端语言甚至都能编译生成web assembly。到时候,前端和后端的界限,可能也就会再次模糊吧!

    2019-08-14
    3
    4
  • X中倪
    这篇文章看了一遍又一遍。这篇文章主要在说明前端技术。它给我的最直观的知识点还是最开始的那句话。这里的“前端(Front End)”指的是编译器对程序代码的分析和理解过程。它通常只跟语言的语法有关,跟目标机器无关。而重中之重 是 “跟语言的语法有关”。
    文章中在语义分析有句话
    计算机语言的语义一般可以表达为一些规则,你只要检查是否符合这些规则就行了。这句话中的这些规则。我理解的还是 “语言的语法”。(可能我这个说有点狭义)
    跟随这句话的第一个问题。我用java和Go语言简单的阐述一下 ,举一个最low的例子
    java :
          int a = 30;
          float b = 60;
          System.out.print(a * b); // 输出 1800.0
    Go:
    var a int32 = 30;
    var b float32 = 60;
    t.Log(a * b) // 编译报错
    在java中支持低精度转双精度,
    在Go中不支持低精度转双精度。
    在龙书章节一当中。有个案例 我简写为 a = b + c * 60 。在语义分析中,60 的这个节点 有inttofloat的转换。这个转换存在的编译器有 java 、C 、C++ 、Scala等。不存在类似Go的语言。
    inttofloat。这个疑问解决了。
    学习学习,一边学、一边练习。主要的还是在练习。

    作者回复: 点赞!
    动手,还是动手!
    一旦动手,马上就明白了!

    2019-08-23
    3
  • Hurt
    老师 es 的文本分词 是不是基于这么处理的啊

    作者回复: 据我了解,不完全是。详细的可以看看吴军的书,他搞过全文检索。

    根本原因,是程序语言有严格的词法规则,能够知道如何把词准确的分开。而像中文这样的自然语言就不行。同一个句子有多个可能的切法。所以就要用进去统计的方法。现在自然语言处理,更加要用AI的方法。

    2019-08-16
    3
  • 傲娇的小宝
    感觉就是类似XML的实现,节点类似xml的节点,语义分析的成果就像xml上的属性。似乎很多东西其实都是树形结构,通过属性记录一些东西,节点保存东西,运行的时候两相结合。这些操作的根本目的就是保存住有效信息并且有效读取。

    作者回复: 你理解得非常准确!非常好!
    或者说,因为普通的文本解析似乎有点难度,所以发明XML这种格式,让解析更容易一些。代价就是很多尖括号标签,文件也膨胀得更厉害。
    所以,计算机记日志的时候,不会采用xml,因为太浪费空间了。

    2019-08-15
    3
  • 雲至
    老师能讲一个具体树最好了

    作者回复: 后面的课程中,有好多棵具体的树,慢慢来!

    2019-08-14
    2
    3
收起评论
98
返回
顶部