02｜词法分析：识别Token也可以很简单吗？
宫文学
你好，我是宫文学。
上一节课，我们用了很简单的方法就实现了语法分析。但当时，我们省略了词法分析的任务，使用了一个 Token 的列表作为语法分析阶段的输入，而这个 Token 列表呢，就是词法分析的结果。
其实，编译器的第一项工作就是词法分析，也是你实现一门计算机语言的头一项基本功。今天，我们就来补补课，学习一下怎么实现词法分析功能，词法分析也就是把程序从字符串转换成 Token 串的过程。
词法分析难不难呢？我们来对比一下，语法分析的结果是一棵 AST 树，而词法分析的结果是一个列表。直观上看，列表就要比树结构简单一些，所以你大概会猜想到，词法分析应该会更简单一些。
那么，具体来说，词法分析要用什么算法呢？词法是不是也像语法一样有规则？词法规则又是如何表达的？这一节课，我会带着你实现一个词法分析器，来帮你掌握这些技能。
在这里，我有个好消息告诉你。你在上一节课学到的语法分析的技能，很多可以用在词法分析中，这会大大降低你的学习难度。好了，我们开始了。
词法分析的任务
你已经知道，词法分析的任务就是把程序从字符串转变成 Token 串，那它该怎么实现呢？我们这里先不讲具体的算法，先来看看下面这张示意图，分析一下，我们人类的大脑是如何把这个字符串断成一个个 Token 的？
图1：词法分析是把字符串转变为Token串
你可能首先会想到，借助字符串中的空白字符（包括空格、回车、换行），把这个字符串截成一段段的，每一段作为一个 Token，行不行？
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
编译器中的词法分析是一项重要工作，本文介绍了词法分析的任务和实现方法。通过对比语法分析和词法分析的结果，强调了词法分析的结果是一个列表，相对简单。作者提出了借助正则表达式来描述词法规则的方法，并给出了标识符和浮点数字面量的词法规则示例。文章还讨论了词法分析的性能优化，介绍了有限自动机的概念，并给出了相关的算法实现。通过预读字符和状态迁移图，词法分析的性能得到了提升。文章深入浅出地介绍了词法分析的基本概念和实现方法，适合初学者快速了解。此外，文章还介绍了语法分析中的思路迁移，提升了语法分析效率。通过预读字符，可以减少尝试的次数，提高性能。文章还介绍了LL(1)算法，避免了回溯导致的性能开销。总结起来，本文内容涵盖了词法分析和语法分析的基本概念及实现方法，以及性能优化的相关技术，对编程语言感兴趣的读者具有很高的参考价值。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《手把手带你写一门编程语言》，新⼈⾸单¥59
《手把手带你写一门编程语言》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(13)
- 最新
- 精选
yjhmelody首先考虑是否有一元运算符-，没有则为整体解析。然后考虑支不支持该运算符的重载，如果有则可能分开解析更好。其他情况均可以，取决于实现者如何看待这个-号作者回复: 答案在第六节的正文里，在这里我就不说了。
2021-08-113
船为什么在用cmd运行这节代码时会出现？ Usage: node D:\craft-a-language\02\play.js FILENAME作者回复: 02的代码，需要在命令行里，比01的play.js 在执行时 多输入一个命令行参数：node play.js xxx.js 。其中 xxx.js 是你要parse的js文件。
2021-09-14- 有学识的兔子-3作为一个负数字面量，会减少一个减法表达式，从这章的内容看，语法分析过程中会因为回溯会影响效率，减少不必要的规则表达式也是提升效率一种方式。从词法分析上把-3当作一个token识别出来，性能消耗可能并不多。
作者回复: 答案在第六节的正文里，在这里我就不说了。
2021-08-12 
蓝士钦如果要自己实现一个JSON parse、或者PDF parse，只需要识别Token即可，整个过程和写一个有限自动机一样，这些parse比写一门语言要来的简单吧作者回复: 你说的这两项任务，可能仅仅做词法分析是不够的，也会有语法分析和语义分析。 以JSON为例，每种JSON文件都会有自己的Schema，这些Schema往往也可以用EBNF描述，它就表达了某一类JSON的语法规则。
2021-08-112
王老师，我觉得应该把-3整体当做一个字面量解析。如果解析成一个-和一个3的话，就是减法运算了，减法是需要两个数的。如果非要解析为减法运算，是不是被减数还得默认设置为0作者回复: 答案在第六节的正文里，在这里我就不说了。
2021-08-113
springXu把-3作为整体，计算机中负数是用补码来表示负数的。这样把字符转换成数字方便了。作者回复: 答案在第六节的正文里。
2021-08-11
星小哥建议代码少一点else{} 嵌套，比如 以下的else没有必要 if (this.stream.eof()) { return { kind: TokenKind.EOF, text: "" }; } else {}2023-06-14归属地：上海
ifelse
学习打卡2022-09-09归属地：浙江
神经旷野舞者老师能不能把每节课的要求列一下，因为不懂得太多，不知道理解到什么程度可以进入下一节2022-07-03- Jack_1024这样实现是自举对吗？2022-04-27
收起评论
