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

07 | 编译器前端工具(二):用Antlr重构脚本语言

宫文学 2019-08-28
上一讲,我带你用 Antlr 生成了词法分析器和语法分析器,也带你分析了,跟一门成熟的语言相比,在词法规则和语法规则方面要做的一些工作。
在词法方面,我们参考 Java 的词法规则文件,形成了一个 CommonLexer.g4 词法文件。在这个过程中,我们研究了更完善的字符串字面量的词法规则,还讲到要通过规则声明的前后顺序来解决优先级问题,比如关键字的规则一定要在标识符的前面。
目前来讲,我们已经完善了词法规则,所以今天我们来补充和完善一下语法规则,看一看怎样用最高效的速度,完善语法功能。比如一天之内,我们是否能为某个需要编译技术的项目实现一个可行性原型?
而且,我还会带你熟悉一下常见语法设计的最佳实践。这样当后面的项目需要编译技术做支撑时,你就会很快上手,做出成绩了!
接下来,我们先把表达式的语法规则梳理一遍,让它达到成熟语言的级别,然后再把语句梳理一遍,包括前面几乎没有讲过的流程控制语句。最后再升级解释器,用 Visitor 模式实现对 AST 的访问,这样我们的代码会更清晰,更容易维护了。
好了,让我们正式进入课程,先将表达式的语法完善一下吧!

完善表达式(Expression)的语法

在“06 | 编译器前端工具(一):用 Antlr 生成词法、语法分析器”中,我提到 Antlr 能自动处理左递归的问题,所以在写表达式时,我们可以大胆地写成左递归的形式,节省时间。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《编译原理之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(19)

  • Void_seT
    老师,目前的学习过程中,比如表达式语法规则、语句语法规则等,虽然能知道它们表示了什么,但是并不知道它是怎么凭空产生的;请问:这种规则是相对比较固定的,我们要使用时,可以参照“标准”的规则文法进行修改呢?还是要自己掌握各种类型语法规则的各个组成细节,以便于在写语法规则时可以信手拈来呢?如果需要熟练掌握语法规则的各个组成细节,目前的工作如果还用不到生成“小编译器”这种技能,也就是没有练习或高强度的训练时间的话,是否需要现在就硬啃下这块硬骨头(因为怕长时间不使用,将来真正要使用时,还是要重新再训练一遍)?

    作者回复: 各种文法规则的设计经验的积累,属于"最佳实践"的范畴。我建议大家不仅仅是要懂原理,还能掌握一些最佳实践,说起某个语法现象的时候,随后就能写出几个文法来。
    能有这种实操能力,才算是把理论落到实际了。这些“最佳实践”,属于你自己积累的领域经验,这也是你为什么会更有竞争力的原因。
    这些经验,只有动手,多看别人的,才能积累。一般没有书籍专门讲这个,顶多是以示例的方式呈现。

    2019-08-28
    5
  • 李懂
    现在都是用一门语言去实现这些功能,我想知道最开始的语言是怎么实现分析的呢!有一点鸡生蛋蛋生鸡!

    作者回复: 在编译领域,有一个事情,叫做自举(bootstraping),也就是这门语言的编译器可以用自己这门语言编写。这是语言迈向成熟的标志。一般前面的版本,是要借助别的语言编写编译器,但后面就应该用自己的语言来编译了。
    著名的语言都实现了自举。比如,go语言的编译器是用go编写的(早期版本应该是用C语言写的编译器。能实现自举,还是go发展历程上的一个历程碑)。
    最早的语言的编译器,那肯定是用汇编写。到一定程度后再自举。

    2019-08-29
    1
    4
  • Spring
    老师,你好。请教一下,词法,语法解析后生成 AST 后,计算机怎么指导我的AST 中的“+” 就是执行 add 的计算呢?这其中是不是还有还存在一个中间层?

    作者回复: 对。你提的问题很好。
    说明你思考的很深入了。
    “+”执行加法运算,是由计算机语言的语义规定的。比如,你可以再让“+”去做字符串连接,这也是语义上的规定。
    所以,计算机语言之间真正的差别,其实在语义上。
    词法分析、语法分析完毕以后,只是搭起一个数据结构。至于基于这个结构可以干什么,还必须附加语义。你可以在这个AST上附加一些“动作指令”,比如对AST遍历的时候,遍历到“+”,就把两边加起来。这就是属性计算做的事情。我们把value作为一个属性,用一些规则来计算属性。说起来,属性计算还是大师高德纳提出来的。
    你再沿着自己的思路深入下去,你可能自己把高德纳大师想到的也都想出来了。
    看来你对编译原理的直觉很好:-D

    2019-08-28
    4
  • 宇智波芭芭干
    学习时总感觉节奏在老师那边,自己的思路并不连贯,对于初学者容易出现断片。在极客时间其它老师那里也同步购买了linux以及网络协议,另外一边通过故事的形式通熟易懂的讲解了一些底层知识原理,学习也是相当顺畅有兴趣,而这里不知道为啥就是顺畅不起来,差距不是一般的大。

    作者回复: 谢谢提意见。我们会收集大家的意见,在课件版本迭代时提升表述水平!

    2019-09-10
    2
  • windpiaoxue
    老师您好
    例如下面这个规则:
    stmt -> if expr stmt
          | if expr stmt else stmt
          | other
    我测试了一下,antlr使用上面这个规则可以正确的处理悬挂else的问题,
    antlr在处理这种二义性问题的时候,是依据什么来处理的。

    作者回复: 为你的动手实践点赞!
    其实原因我在文稿里已经说了。
    我们实现一个算法的时候,是有确定的顺序来匹配的。所以,即使是二义性文法,在某种算法下也可以正常解析。

    严格的非二义性文法要求得比较高。它要求是算法无关的。也就是不管你用最左还是最右推导,得出的结果是一样的。

    关键点,在于把“文法”和“算法”这两件事区分开。文法是二义的,用某个具体算法却不一定是二义的。

    其余的部分,你可以再看看文稿,是否能理解。Antlr是LL算法,最左推导、深度优先。如果你一时看不明白,也没关系,因为到后面我还会专门讲LL算法。

    2019-08-31
    2
  • cry soul
    建议老师用用git搭好tag来表示每个课程到到哪部分源码,不然需要读好几篇才能自己尝试。

    作者回复: 谢谢你的建议。有的代码文件确实很长,查找不太容易。我后面优化一下代码链接!

    2019-10-05
    1
  • 李懂
    JavaScript中的this是咋实现的,这个一直处于迷糊当中,好想弄清楚,不同语言之间语意的差别,学完语意能理解么😇 😇 😇 ,看了很多课程,都很失望,都是再讲几种场景,怎么指向,没实质的改变!

    作者回复: 我记着你这个需求。
    我看看能否把这个点插到某一讲中。

    2019-08-29
    1
    1
  • 中年男子
    编译 git 里 PlayScript-cpp, 我这里报错, PlayScriptJit.h 这个文件, 搞了半天没搞懂
    In file included from /Users/shiny/learn/PlayWithCompiler/playscript-cpp/src/PlayScript.cpp:5:
    [build] In file included from /Users/shiny/learn/PlayWithCompiler/playscript-cpp/src/grammar/IRGen.h:28:
    [build] /Users/shiny/learn/PlayWithCompiler/playscript-cpp/src/grammar/PlayScriptJIT.h:33:31: error: unknown type name 'LegacyRTDyldObjectLinkingLayer'; did you mean 'RTDyldObjectLinkingLayer'?
    [build] using ObjLayerT = LegacyRTDyldObjectLinkingLayer;
    [build] ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    [build] RTDyldObjectLinkingLayer

    作者回复: 你的进度有点快!
    playscript-cpp我还没有整理好。
    如果你着急看后端的东西,建议你先做两件事情:
    1.用Antlr将.g4文件生成c++代码,测试一下在C++中运行是否OK。
    2.下载和安装LLVM,做做教程里的例子,有一个是c++的例子。
    好消息是,这两个项目都是用cmake管理的。

    2019-08-28
    1
  • ( ̄_ ̄ )
    写了一晚上终于用c语言模仿着实现了第二节课的内容
    https://github.com/hongningexpro/Play_with_Compiler/tree/master/01-Simple_Lexer

    作者回复: 点赞!
    动手出真知!

    2019-08-28
    1
  • fung
    老师,这一段看不懂咋办,有的救吗?看不懂这些语法啊,能解析下吗?或有其他资料介绍吗?谢谢
    expression : primary | expression bop='.' ( IDENTIFIER | functionCall | THIS ) | expression '[' expression ']' | functionCall | expression postfix=('++' | '--') | prefix=('+'|'-'|'++'|'--') expression | prefix=('~'|'!') expression | expression bop=('*'|'/'|'%') expression | expression bop=('+'|'-') expression | expression ('<' '<' | '>' '>' '>' | '>' '>') expression | expression bop=('<=' | '>=' | '>' | '<') expression .......

    作者回复: 首先,关于Antlr的详细语法,你可以看一下它的作者的一本书:《the definitive antlr 4 reference》,应该也有中文版的。

    另外,你可以搜一下EBNF的语法,因为antlr的语法基本上就是EBNF的语法,跟正则表达式的语法也很像,然后又加了一些元素,比如给某些部分做了命名。
    bop=('+'|'-')是给('+'|'-')起了个名称,便于引用。

    最后,当你动手实践的时候,这些困难就都不存在了。你就是对它们陌生。用多了就不陌生了!

    2019-11-05
  • shantelle
    宫老师你好,请问这个匹配的是什么内容呢
    '\\' [btnfr"'\\]

    作者回复: 转义字符,比如:\t是tab。

    2019-10-25
  • zhj
    现在拿到的ASTEvaluator,都裹扎了编译器相关的代码,这里才看到Ast树,这边没有很好的 版本迭代吗,上来直接就是讲课同步的代码,看的云里雾里,没法循序渐进

    作者回复: 回头把代码分拆整理一下。

    2019-10-16
  • 长方体混凝土移动工程师
    blockLabel 这个怎么没看到在哪里定义的呢?

    作者回复: 在PlayScript.g4中:

    statement
        : blockLabel=block

    blockLabel就是给block起个别名而已。可以在StatementContext中访问blockLabel属性,来获得一个block子节点。

    2019-09-07
  • 长方体混凝土移动工程师
    bop只是一个别名吗?

    作者回复: 是的,只是个别名。
    它会变成ExpressionStatement的一个属性。通过这个属性,可以获得一个子节点。

    2019-09-07
  • Lafite
    宫老师,本章的代码应该如何去学习呢,想学习一下 本章的解释器及其他代码, 结果发现代码量比较大,我阅读起来比较困难,麻烦老师指导一下,谢谢

    作者回复: playscript的java版我没有维护多个版本。所以里面有很多特性是后面几讲里的。
    但是,你可以先关注本讲的内容。比如,(1)比较完整的语法规则文件;(2)ASTEvaluator.java如何完成计算的整体流程。
    一些其他的细节,听完后面几讲以后,应该就能明白了。

    2019-09-05
  • 沉淀的梦想
    有个疑问,为什么expression的规则是写作

    expression bop=('+'|'-') expression

    而不是写作:

    expression bop=(ADD|SUB) expression

    作者回复: 这两个生成的结果一样。Antlr会知道其实'+'是你已经在词法规则中声明了的,知道这里等价于ADD。
    如果词法规则里没有把'+'定义成ADD,也没关系,Antlr会自动添加词法规则,但名称就是它自己起的了。

    2019-08-30
    1
  • 许童童
    难度越来越大了,要好好消化才行。

    作者回复: 我相信你的消化能力:-D

    2019-08-28
  • 石维康
    statement
        : blockLabel=block
        | IF parExpression statement (ELSE statement)?
        | FOR '(' forControl ')' statement
        | WHILE parExpression statement
        | DO statement WHILE parExpression ';'
        | SWITCH parExpression '{' switchBlockStatementGroup* switchLabel* '}'
        | RETURN expression? ';'
        | BREAK IDENTIFIER? ';'
        | SEMI
        | statementExpression=expression ';'
        ;
    请问" : blockLabel=block"这个规则如何解释?谢谢!

    作者回复: 这是给block起了个别名,这样在生成的AST节点StatementContext中,就会有blockLabel这个属性,来访问这个下级节点。
    就是为了编程方便的。

    2019-08-28
  • 雲至
    老师能讲一下antlr的语法吗?

    作者回复: antlr是个工具。它的完整语法和介绍什么的,看官方网站和我提供的参考书就行了。我们课程不可能在这方面笔墨太多。
    工具这个事情,你只要了解了原理,去试着用一下就行了。
    动手是最重要的。课程里的示例代码,可以给你怎么具体使用antlr提供很多线索。

    2019-08-28
收起评论
19
返回
顶部