编译原理之美
宫文学
北京物演科技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
收起评论