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

16 | NFA和DFA:如何自己实现一个正则表达式工具?

宫文学 2019-09-18
回顾之前讲的内容,原理篇重在建立直观理解,帮你建立信心,这是第一轮的认知迭代。应用篇帮你涉足应用领域,在解决领域问题时发挥编译技术的威力,积累运用编译技术的一手经验,也启发你用编译技术去解决更多的领域问题,这是第二轮的认知迭代。而为时三节课的算法篇将你是第三轮的认知迭代。
在第三轮的认知迭代中,我会带你掌握前端技术中的核心算法。而本节课,我就借“怎样实现正则表达式工具?”这个问题,探讨第一组算法:与正则表达式处理有关的算法。
在词法分析阶段,我们可以手工构造有限自动机(FSA,或 FSM)实现词法解析,过程比较简单。现在我们不再手工构造词法分析器,而是直接用正则表达式解析词法。
你会发现,我们只要写一些规则,就能基于这些规则分析和处理文本。这种能够理解正则表达式的功能,除了能生成词法分析器,还有很多用途。比如 Linux 的三个超级命令,又称三剑客(grep、awk 和 sed),都是因为能够直接支持正则表达式,功能才变得强大的。
接下来,我就带你完成编写正则表达式工具的任务,与此同时,你就能用正则文法生成词法分析器了:
首先,把正则表达式翻译成非确定的有限自动机(Nondeterministic Finite Automaton,NFA)。
其次,基于 NFA 处理字符串,看看它有什么特点。
然后,把非确定的有限自动机转换成确定的有限自动机(Deterministic Finite Automaton,DFA)
最后,运行 DFA,看看它有什么特点。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《编译原理之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(8)

  • tengen
    如果在dfa中加上通配符点号有什么好方法吗,我是在move里进行修改的,但是这样的话如果有大量正则表达式的时候,nfa转dfa很慢.
    2019-09-23
    1
  • 老师:为什么NFA要加空转换这样的操作呢,感觉对表达能力并没有扩展。

    作者回复: 加空转换不是为了扩展表达能力,而是为了能够通过一个简单标准的方法,把正则文法转换成NFA。

    2019-09-22
    1
  • 飞翔
    老师NFA2DFA这个函数的这一行dfaState = findDFAState(dfaStates, nextStateSet);中的nextStateSet是不是应该是calculatedClosures这个?还有,这一节的代码怎么运行啊,一直编不过

    作者回复: 我明天抽空检查一下代码库是否存在编译问题,再给你回复。最近有点忙,回复大家迟了点。

    2019-09-29
  • Lamont
    文中代码块
    int | [a-zA-Z][a-zA-Z0-9]* | [0-9]*
    最后一个字符*应该是+

    作者回复: get!是小编的问题,谢谢提醒,已更新。

    2019-09-28
  • 飞翔
    老师,这一节的代码怎么运行,GrammarNodeType没有找到定义的地方
    2019-09-27
    1
  • 醉雪飘痕
    请问老师,您的图是用什么工具做得呀?

    编辑回复: 是用Mac自带的Keynote呐~😜

    2019-09-22
  • 沉淀的梦想
    感觉NFA的匹配很适合并行啊,如果对于每个转换条件,开个线程并行匹配,这样就不需要回溯了,是不是能提升不少效率,虽然浪费了一些算力

    作者回复: 嗯,如果计算机有多余的算力的情况下。

    2019-09-22
  • Geek_dba6ea
    第一次从这个层面理解了贪心正则匹配

    作者回复: 你是指,“知其所以然”了吗? :-)

    2019-09-21
收起评论
8
返回
顶部