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

02 | 正则文法和有限自动机:纯手工打造词法分析器

宫文学 2019-08-16
上一讲,我提到词法分析的工作是将一个长长的字符串识别出一个个的单词,这一个个单词就是 Token。而且词法分析的工作是一边读取一边识别字符串的,不是把字符串都读到内存再识别。你在听一位朋友讲话的时候,其实也是同样的过程,一边听,一边提取信息。
那么问题来了,字符串是一连串的字符形成的,怎么把它断开成一个个的 Token 呢?分割的依据是什么呢?本节课,我会通过讲解正则表达式(Regular Expression)和有限自动机的知识带你解决这个问题。
其实,我们手工打造词法分析器的过程,就是写出正则表达式,画出有限自动机的图形,然后根据图形直观地写出解析代码的过程。而我今天带你写的词法分析器,能够分析以下 3 个程序语句:
age >= 45
int age = 40
2+3*5
它们分别是关系表达式、变量声明和初始化语句,以及算术表达式。
接下来,我们先来解析一下“age >= 45”这个关系表达式,这样你就能理解有限自动机的概念,知道它是做词法解析的核心机制了。

解析 age >= 45

在“01 | 理解代码:编译器的前端技术”里,我举了一个词法分析的例子,并且提出词法分析要用到有限自动机。当时,我画了这样一个示意图:
我们来描述一下标识符、比较操作符和数字字面量这三种 Token 的词法规则。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《编译原理之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(64)

  • KnowNothing
    老师,在关键字和保留字的识别上,我认为有不需要加入中间状态的更简单的方式:
    完成词法分析后,遍历所有ID token,如果其text在关键字和保留字集合内,将该token类型改成对应的关键字/保留字类型。
    或者,
    每当识别出一个ID token,都检查其text,如果是在关键字和保留字集合内,纠正type。

    作者回复: 没错,可以的。
    但是构造成有限自动机的话,程序就可以标准化处理。不需要再手写其他代码。比如正则表达式工具。

    当然,如果纯手写词法分析器,不受任何标准算法的限制的话,那发挥空间就会大很多。

    爱动脑的好同学!

    2019-08-16
    3
    22
  • kirogiyi
    宫老师,例子里面的词法分析大多是靠条件判断来实现,如果对一门完整的语言来进行分析的话,工作量会不会很大。我在想,是否有其他方式可以实现?

    作者回复: 课程的示例代码的主要目的是把意思讲明白,我甚至把状态都用枚举表示,就是为了易读。性能不是第一考虑。
    从性能的角度,词法分析可以用查表的方法实现状态迁移。在每个状态,接收什么字符,切换到另外的状态。那样更快,这是常用的方法。
    不光词法分析可以这么做,语法分析也可以。基于表驱动。这时候,最重要的是构造那张表。代码的话,就不大看明白是啥意思。

    2019-08-17
    20
  • Fan
    宫老师,有没有一些词法分析的demo可以推荐看看呢?

    作者回复: 最好的demo,就是现有语言的词法分析器,比如Java的、GNU c的,都能拿到源代码。比如Java的编译器在JDK的源代码里就有。

    此外,我们在后端时会讲到LLVM工具。LLVM的文档里有一个小的教程,做了一个完整的前端。你也可以参考一下。http://llvm.org/docs/tutorial/MyFirstLanguageFrontend/LangImpl01.html

    回头我整理一份清单放到github上,告诉大家去哪里下载。你的需求估计其他同学也有。

    谢谢你!

    2019-08-16
    1
    17
  • 傲娇的小宝
    感觉有限状态机有点类似图灵机的工作方式。我一般只用正则匹配一下文件名或者某个字符串是否符合我的预期。

    作者回复: 有限自动机是比较简单的一种自动机,对应于正则文法,也叫做3型文法。
    比它强大的是下推自动机,对应于上下文无关文法,也叫做2型文法。
    比它更强大的是线性有界自动机,对应于上下文相关文法,也叫1型文法。
    图灵机的范围比它们都大,它对应0型文法。你任何能用产生式写出来的文法规则,都属于0型文法。

    希望对你有帮助,了解有限自动机和图灵机的关系:)

    2019-08-18
    1
    12
  • 逗逼师父
    老师您好,我的疑问是,age>=45的有限状态机图中,为什么比较操作符不像标识符那样停留在同一个状态?我觉得>和>=都是属于比较操作符呀

    作者回复: 很好的问题。
    是这样的。从Token分类的角度,我们确实可以把这两个归为一类。
    但如果把它们看做同一个状态,就会有一些问题。比如,接收到=号应该怎么处理呢?接收第一个=号,仍然处于比较操作符状态。那么接收第二个呢?问题是,有限状态机接收字符的时候,是没法数个数的。如果你要记个数,也就相当于在内部新增加了一个状态,还是等价于两个状态。我这么说你理解吗?

    2019-08-17
    3
    8
  • devna
    之前做的一个项目中有大量的历史遗留脚本是用Perl写的,于是主动去学了下Perl,不得不说,Perl是我见过所有语言里对正则表达式支持最强的,效率也是最高的(我想可能是因为Perl在语言核心内置了正则表达式引擎,不像其他语言,是通过各种模块支持的)。
    后来从Perl了解到《精通正则表达式》这本书,买来看了下,确实是很好的一本书。虽然读完很久很多东西都忘了,但是对正则表达式的理解深刻了很多。

    作者回复: great!
    基于你已有的积累,是否可以进一步想想,能否自己写一个支持正则的工具?比如像grep、sed这些超级命令一样。那几个命令被认为是神级的命令,就是因为支持正则表达式,让它们能适应各种情况。

    2019-08-16
    1
    8
  • 梓航(﹏)
    我是来提意见的,麻烦老师在讲示例的时候,把对应的github链接贴上,而不是在最后贴一个总的地址,我点进去一脸懵,哪个文件对应哪个例子啊?

    作者回复: 好的,谢谢您提意见!已通知后台调整一下。
    02课的文件是目录中的SimpleLexer.java文件。

    另,如果到github的https://github.com/RichardGong/PlayWithCompiler项目主页,里面有每堂课的课件的介绍,供您参考。

    2019-08-17
    7
  • 诺亚
    isAlpha 的 alpha 好像没有字母的意思吧?用 alphabet 会不会比较合适点?

    作者回复: 你很细心,所以我也仔细给你解答下:-)
    isAlpha是 is alphabetic 的缩写。isalpha()函数是好几个语言的标准库里都提供的,比如C、python等。
    alphabet指的是整个字母表,不是字母表里的单个字母。

    2019-08-25
    5
  • xindoo
    正则表达式匹配3的任意倍数 https://www.zhihu.com/question/24824487

    作者回复: 哇,真好玩!
    点赞!

    2019-08-16
    5
  • (╯‵□′)╯︵┻━┻
    有回随手发现Google搜索可以使用正则表达式……然后感觉星星都亮了

    作者回复: 嗯。等你学了算法篇第16讲,了解了正则表达式的机制后,可以设计点正则表达式测试一下谷歌的性能,看看能否把谷歌的服务器累趴下...

    2019-10-03
    3
  • 冬瓜
    int 后面的 id 的正则是不是 [a-zA-Z_][0-9a-zA-Z_]*这样就行,为啥要将数字通过|连接呢?是不是有什么用意😳

    作者回复: 就是个习惯而已,把数字和字符分两组。

    我们在写正式的词法文件时,有时会这么写:
    Id: Charactor (Charactor | Digit)*
    Number: Digit+
    Charactor: [a-zA-Z_]
    Digit: [0-9]

    这时候,Digit在几个不同的规则中是复用的。

    2019-08-16
    2
    3
  • 恩佐
    https://github.com/shaojintian/learn_compiler
    老师能看看我的lexer么?用golang写的
    请老师和同学们指正,感谢

    作者回复: 看了你的代码,挺不错的。如果再补充一下README,让人可以迅速build和测试你的项目就更好了。

    2019-11-01
    1
    2
  • 乐毅
    老师,是否可以将关键字和保留字预先存储起来? 如果可以,那和文中描述的方式有什么区别吗?

    作者回复: 可以呀。
    算法可以是灵活的,可以有多种实现。课程里讲的理论往往更通用,比如可以根据正则表达式自动生成有限自动机。
    在具体领域中,比如如果只是给计算机语言做词法分析,当然可以针对关键字这种特殊情况做特殊处理。
    所以,在实际工程中,往往比纯原理更简单。因为允许变通。

    2019-08-24
    2
  • 好吃的呆梨
    ts的实现,请老师和同学指正。https://github.com/sheeeeep/fundamentals-of-compiling/blob/Ch02/src/lexical-analyser.ts

    作者回复: 非常好!要号召大家跟你学习!
    太棒了!

    你有精力的话,还可以再精进一下,参考一下成熟编译器的词法分析工具,从课程示例的代码的基础上再提升一个等级:)

    比如说,另一个同学提到过,如何提升词法分析的性能什么的。

    2019-08-16
    2
    2
  • (口-口)🌟
    一般都是用来批量的处理数据的,比如把csv格式转换为json格式,方便程序操作,或者从日志冲筛选出指定的字段。

    作者回复: 谢谢分享!
    没错,这是词法分析的应用之一。
    再进一步,在处理一些复杂格式的日志时,仅仅用词法分析还不够,还要加上语法分析功能才行。

    2019-08-16
    2
  • 鱼_XueTr
    正则表达式在做爬虫和文本处理中用过比较多。

    作者回复: 是滴。
    程序编译的第一阶段工作,本质也是文本处理。

    2019-08-16
    2
  • 姜大牙
    老师,是否有计划讲一下方舟编译器?

    作者回复: 这个题目比较大:-D
    这需要我去仔细看看方舟的代码才敢评价。我也很想抽出时间来研究一下。如果安排这个内容,应该是在答疑模块中。

    2019-09-02
    1
  • 阿尔伯特
    Mark.
    https://github.com/albertabc/compiler/blob/master/main.cpp

    作者回复: 下载,编译,并运行了。
    你提供的cmake配置很赞,让编译很顺畅!
    也看出你C++功底很扎实呀!
    再次点赞!

    2019-08-31
    1
    1
  • 请叫我赓哥
    您好,老师,初步接触编译原理,您讲的手工打造词法分析,是用已知的java或c或其他语言实现,我想问一下,c语言的编译器是用什么实现的呢,或者其他语言的编译器?另外其他的词法分析器又是用什么语言编写的呢,谢谢

    作者回复: 在编译领域,有一个事情,叫做自举(bootstraping),也就是这门语言的编译器可以用自己这门语言编写。这是语言迈向成熟的标志。一般前面的版本,是要借助别的语言编写编译器,但后面就应该用自己的语言来编译了。
    著名的语言都实现了自举。比如,go语言的编译器是用go编写的(早期版本应该是用C语言写的编译器。能实现自举,还是go发展历程上的一个历程碑),jdk里面自带了java语言的编译器,本身也是用java写的。
    更早的语言,那当然是用汇编写编译器。比尔盖茨当年就是用汇编写。
    掌握编译原理之后,其实用什么语言都可以写。
    这门课程的示例语言是playscript。我有计划后面把playscript实现自举。

    2019-08-28
    1
  • Rockbean
    用Swift Playground写了一个小DEMO
    [Swift Playground词法分析器DEMO](https://juejin.im/post/5d640edde51d453b5d4d8d94)

    作者回复: 为动手实操点赞!
    谢谢你还在页面上加了课程链接:-D

    2019-08-27
    1
收起评论
64
返回
顶部