02 | 词法分析：用两种方式构造有限自动机
该思维导图由 AI 生成，仅供参考
词法分析的原理
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
词法分析是编译过程中的关键步骤，通过有限自动机将字符串识别为Token串。有限自动机是一种计算模型，其状态数量有限，当接收到新字符时会导致状态迁移。词法分析的过程实质上是对字符串进行模式匹配，而正则表达式工具可以用来描述词法规则。文章通过图示和示例生动地展示了有限自动机如何识别标识符和数字字面量，以及如何设计区分关键字和标识符的有限自动机。此外，文章还介绍了词法规则的优先级问题，以及如何使用正则文法描述词法规则。通过本文，读者可以快速了解词法分析的原理和实现方式，为进一步深入学习编译原理领域奠定了基础。文章还介绍了正则表达式工具如何生成有限自动机，以及NFA和DFA的概念和转换方法。此外，还提到了回溯和子集构造法等算法，以及如何利用NFA进行正则表达式的匹配。整体而言，本文深入浅出地介绍了词法分析的原理和实现方式，对于编译原理领域的学习者具有很高的参考价值。文章还提到了编译器中词法分析器的手写构造和一些优化技巧，以及NFA转DFA的算法，为读者提供了更深入的学习方向。
《编译原理实战课》，新⼈⾸单¥59
全部留言(12)
- 最新
- 精选
吃鱼老师我是否可以这么理解NFA细分的两种情况： 第一种直接将针对不同输入选择不同路径的表现画了出来，每个状态可能有多个选择路线；第二种 ε 转换其实就是将前一种情况使用 ε 转换拆分开来，通过这种“可能”通过 ε 转换成另外一个状态的形式，使得图中每一个状态只有一条路线到下一个状态，多个选择的可能性由 ε 转换来表达。 好像如果把所有被 ε 转换连接起来的状态重合成一个状态，第二种情况的图就会变成第一种状态。作者回复: 你理解得没错。 状态1 + 输入a ->状态2 状态1 + 输入a ->状态3 等价于： 状态1 + 输入a -> 中间状态 中间状态 + ε -> 状态2 中间状态 + ε -> 状态3 就像你说的，多个选择的可能性由ε做了表达。
2020-06-17212
王成感觉词法分析和语法分析几乎在做相同的工作，只不过词法分析处理的是字符，而语法分析处理的是token，而且同样上上下文无关 我记得老师说过语法分析是可以一次预读多个token，那么词法分析应该也是可以预读多个字符吧 还有，既然词法语法分析都与上下文无关，那么是不是这两个也可以同步进行呢作者回复: 对于某些特殊的词法规则，有时也需要预读多个字符，在实际的编译器里就有这种情况。 在实践中，通常是把这词法分析和语法分析两个处理过程串起来，用语法分析程序来驱动。当需要token的时候，才调用词法分析器来获得一个Token，而不是一次把Token全部生成完毕。
2020-06-0528
奕对于 ε 转换 不是很理解作者回复: 你看看“吃鱼”同学的理解和我的回复，看看有没有帮助？
2020-06-077- 王成老师，您好 我想问下，词法分析真的只是正则文法就能满足么 今天在用java写一个简单计算器的时候发现一个问题 问题描述 在java中，支持1++--+-+-2这样的方式计算，但是这在词法分析阶段判定'++'和'--'的时候就出现了问题，之前都是碰到连续的两个加号或减号都当成'++'或'--'了，但是在知道还支持这种计算方式时，就有点懵了，显然在词法分析阶段需要依赖前后的token进行判断。 老师，是我的思考方式有问题么，还是有其他的方式可以在词法分析阶段解决上面的问题 谢谢老师啦
作者回复: 这个事情要这么理解：如果词法分析都要基于比较复杂的规则，那实际上是不便于人类阅读的。所以，词法规则应该尽量简单。比如，两个+号连载一起的话，那就识别成一个Token。 补充一下： 你的问题让我想起了一种情况，对于有的语言来说，仅仅用上下文无关文法解决不了一些有二义性的语法。 举个例子。c语言有一种奇怪的声明变量的方式，比如： “int(a);” 跟 “int a;” 的含义是一样的，都是声明一个整型变量a。但如果有一个句子是“bar(a)”，那你不知道bar是个类型还是一个函数。类似奇怪的语法还有别的一些。 在这种情况下，即使是做语法分析，也要依赖上下文信息，要搞清楚bar到底是个函数，还是一个自定义的类型。所以，C和C++语言在语法分析阶段就需要用到符号表。
2020-06-124 - nate_luo在实际的编译器中，词法分析器一般都是手写的，依据的基本原理就是构造有限自动机。不过有一些地方也会用手工编码的方式做一些优化（如 javac 编译器），有些编译器会做用一些特别的技巧来提升解析速度（如 JavaScript 的 V8 编译器），你在后面的课程中会看到。 这里是不是应该写成”一般都是自动写的”？
作者回复: 还真不是。 词法分析器因为比较简单，所以手写的可以又快又好。因而，成熟语言的编译器里，词法分析器大多是手写的。 当然，如果你是为了快速完成一个用到编译技术的项目，那么我鼓励你用词法分析器生成工具，这样容易更快见到成果。
2020-06-192 - thomas1994不容易啊，全看懂了，还是涉及到很多基础概念，需要额外查资料的
作者回复: 点赞！
2020-06-08 - ヾ(◍°∇°◍)ﾉﾞ有个疑问，为什么正则表达式或nfa直接有优化实现，或者提供更多直接搞笑的语法
作者回复: 很多正则表达式引擎都是基于NFA实现的，减少了生成DFA的步骤，从而减少了相应的损耗（时间和内存）。 但NFA有回溯的问题，所以就存在优化空间。这件事情可以这么理解：正则表达式或NFA其实就代表了一个比较简单的程序，而程序是可以被优化的。 编译器的中后端都是运行各种优化算法。对NFA的优化算法，基本上就是这些优化算法的低配版。 你学完编译器的各种优化算法以后，再看看讲正则表达式引擎的书，看看是不是这样。 甚至运行正则表达式，跟运行一个全功能的程序也有类似的地方，都可以基于虚拟机，都有自己的指令。你其实也可以把正则表达式编译成机器指令。 本课程没有专门在正则表达式引擎的实现上做深入。但是，如果掌握了完整的编译器的实现，再去实现一个针对正则表达式的小型的编译器和虚拟机，其实是比较容易的。
2020-06-04 
A君从字符串到token，需要用到正则表达式，而依据正则表达式来遍历字符串生成token的工具是词法分析器。词法分析器可以手工编写，也可以编写生成器来生成，它首先会将正则表达式转换成NFA或DFA，有限自动机，再根据自动机生成自动词法分析器。NFA，不确定有限自动机，一个状态可以转换到多个状态，因此当一个路径走不下去时会回溯到上一个分叉来走其他的路径。ε表示没有输入时也能做状态转换，这里的没有输入可以是输入为空格。2022-04-281
风之前看了《编译原理之美》讲RE引擎实现原理的课程，试着参考老师的代码，自己实现了一个简单的RE引擎，要先将RE转为一个grammar tree（这里要自己写个parser，但比较简单，甚至不用递归，用循环+手动操作栈就行，最后得到grammar tree，里面有or结点、and结点、和CharSet结点，Or结点和CharSet结点上面可以标记上量词，然后按照课程里介绍的规则，将grammar tree转换成一个NFA，最后根据子集构造法转换成DFA。 最后的感想是，如果想对标那些成熟的RE引擎，还有很多麻烦的细节要实现，比如要支持捕获和引用、模式修饰符号、断言等，还要处理好字符编码和转义字符的细节，工作量不小。2020-11-141
Leesin发现这个课程太晚了，学习也晚了，就是不知道还能看到学习的小伙伴的互动啊2023-07-26归属地：山东
