手写词法分析器
复习
- 字符怎样组成词：词法单元及其类别
- 字符串：逐字符处理
- 状态机：根据当前状态和输入决定下一步
TL;DR
- 手写词法分析器逐字符读取，边走边判断
- 它维护“当前状态”，遇到字符就做相应处理
- 读满一个词，就产出一个词法单元
- 它本质上是一个简单的状态机
正文
上一章讲了词法分析要产出什么。这一章看看，怎样亲手写一个词法分析器。
一个循环，扫过所有字符
词法分析器的主干非常朴素：用一个大循环，从头到尾扫描字符。
每一轮大致做几件事：
- 跳过空白和注释
- 看当前字符属于哪一类（字母？数字？符号？）
- 按这一类的规则，继续往后吃字符，直到这个词结束
- 产出一个词法单元，然后从下一个字符继续
比如看到字母或下划线，就一路吃到“不再是字母数字下划线”为止，得到标识符；看到数字，就一路吃到“不再是数字”为止，得到数字字面量。
用“状态”来想
把上面的过程换个角度描述：分析器始终处于某个状态，读到一个字符就决定“接下来怎么处理、状态变成什么”。
- 一开始是“空闲”状态 - 读到字母，进入“正在读标识符”状态，继续吃字符 - 读到不等于字母数字下划线的字符，说明一个词结束，产出词法单元，回到“空闲”
这正是我们前面讲过的状态机：当前状态 + 输入 → 下一状态 + 动作。词法分析器本质上就是一个为分词而生的状态机。
别忘了出错的情况
现实输入不一定规范，比如出现一个语言里根本没有的字符。这时词法分析器不能默默忽略，而应报告一个词法错误，指出位置，方便使用者改正。
“正常路径 + 错误处理”，是任何合格分析器都要考虑的两面。手写词法分析器虽然简单，也逃不掉这一条。
手写的好处是直观、可控；但如果词法规则很多、很复杂，手写既枯燥又容易出错。有没有更省力的办法？下一章先引入一种描述词法规则的工具——正则表达式。
思考题 1
手写词法分析器的循环里，每一轮大致做哪几件事？
思考题 2
为什么说词法分析器本质上是一个状态机？
小结
知识点
- 词法分析器用循环逐字符扫描
- 每轮跳过空白、判断类别、读取完整词、产出词法单元
- 它的行为可用“状态 + 输入”描述
- 需要报告非法的词法错误
参考资料
- Wikipedia(zh)：词法分析：词法分析器的构造
- Wikipedia(zh)：有限状态机：词法分析器背后的模型
思考题答案（仅供参考）
思考题 1
大致是：跳过空白与注释，查看当前字符的类别，按该类别的规则继续读取字符直到词结束，产出一个词法单元，然后再从下一个字符继续下一轮。
思考题 2
因为它始终处于某个状态，读入一个字符后据此决定如何处理、状态如何改变，并可能产出词法单元。这种“当前状态 + 输入决定动作与下一状态”的模式，正是状态机的定义。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪