词法分析基础：从字符流到Token序列
说实话，每次带新人做编译器项目，我第一个让他们啃的就是词法分析。为什么？因为这是整个编译过程的「入口关」。你想想看，源代码就是一串字符流，计算机哪懂什么关键字、标识符？词法分析器就是那个「翻译官」——把字符流切成有意义的词素，再贴上Token标签。
我记得刚入行那会儿，自己手写过一个词法分析器，处理C语言的预处理指令。当时没考虑好注释和字符串字面量的边界情况，结果一个多行注释直接让整个解析器崩了。嗯，从那以后我对词法分析的边界处理就格外小心。
词法分析器的功能
说白了，词法分析器就干三件事：
- 扫描：从左到右读入源程序字符
- 识别：根据词法规则识别出词素（Lexeme）
- 输出：生成Token序列，每个Token包含
(类型, 属性值)对
举个例子，对于代码：
int sum = 42;词法分析器会输出：
| Token类型 | 词素 | 属性值 |
|---|---|---|
| KEYWORD | int | — |
| IDENTIFIER | sum | 指向符号表的指针 |
| OPERATOR | = | — |
| NUMBER | 42 | 42 |
| SEMICOLON | ; | — |
这里有个坑，我必须要提醒你：词法分析器不负责语法正确性。比如 int 123abc 这种写法，词法分析器只会忠实地识别出 int（关键字）和 123abc（可能是个非法标识符），至于它合不合语法，那是语法分析器的事。
42. 这种写法（小数点结尾）。在C语言里这是合法的，但在某些语言里不是。一定要仔细看语言规范！
正则表达式基础
正则表达式是描述词法模式的利器。我个人习惯用正则来定义Token的模式，因为它直观又好维护。
基本的正则运算有三种：
- 连接：
ab表示a后面跟着b - 选择：
a|b表示a或b - 闭包：
a*表示零个或多个a
举个例子，标识符的模式可以写成：
letter (letter | digit)*其中 letter 是 [a-zA-Z_]，digit 是 [0-9]。这个模式的意思是：一个字母开头，后面跟零个或多个字母或数字。
数字字面量呢？整数和浮点数一起考虑：
digit+ ( "." digit+ )? ( "e" digit+ )?这里 ? 表示零次或一次，相当于 ε | ...。你看，用正则描述词法模式，清晰又精确。
if 和标识符 ifx，要确保关键字优先匹配。
有限自动机：DFA与NFA
正则表达式虽然好写，但计算机不能直接执行它。我们需要把正则转换成有限自动机——一种状态转移图。
两种自动机：
- NFA（非确定有限自动机）：一个状态可以有多条相同输入的转移，也可以有ε转移（不消耗字符就跳转）
- DFA（确定有限自动机）：每个状态对每个输入字符只有一条转移，没有ε转移
你可能会问：「NFA看起来更复杂，为什么还要用它？」
原因很简单：NFA更容易从正则表达式构造出来。Thompson构造法就是干这个的。而DFA虽然构造起来麻烦，但执行效率高——每个字符只查一次状态表，时间复杂度O(n)。
实际项目中，我们通常的做法是：
- 用正则表达式描述词法模式
- 用Thompson构造法转成NFA
- 用子集构造法将NFA转成DFA
- 用DFA驱动词法分析器
嗯，这个流程我做过不下十次了，每次都觉得「子集构造法」那步最烧脑，但也是最核心的。
从正则到NFA：Thompson构造法
Thompson构造法的核心思想是：每个正则表达式都能对应一个NFA，而且这个NFA可以递归地构造出来。
基本构造规则：
- 空串ε：一个起始状态，一个接受状态，中间有ε转移
- 单个字符a：起始状态→a→接受状态
- 连接st：把s的接受状态和t的起始状态用ε连接
- 选择s|t：新起始状态用ε分别连到s和t的起始，s和t的接受状态用ε连到新接受状态
- 闭包s*：新起始状态用ε连到s的起始和新的接受状态，s的接受状态用ε连回s的起始和新的接受状态
下面我用一个具体的例子来说明。假设我们要构造 a|b 的NFA：
ε
┌─────────►[a]──►((1))
│ │
▼ │ ε
((0)) │
│ │
│ ▼
└─────────►[b]──►((2))
ε状态0是起始，状态1和2是接受状态。从0出发，走ε可以到a或b的起始，然后读入a或b后到达接受状态。你看，这个NFA是非确定的——从0出发，不读任何字符就能选择走哪条路。
再复杂一点的例子，a* 的NFA：
ε
┌──────────────┐
│ │
▼ │
((0))──ε──►[a]──►((1))
│ │
└──────ε───────┘状态0既是起始也是接受（因为可以匹配零次a），从0走ε到a的起始，读入a后回到0（通过ε），这样就实现了循环。
我记得有一次，我需要为一个领域特定语言写词法分析器，它的模式里有大量的嵌套闭包和选择。用Thompson构造法手工画NFA，画了整整两页纸。后来我写了个脚本自动生成，省了不少力气。
知识体系总览
下面这张图总结了本章的核心逻辑：
这张图把本章的知识点串起来了。你从左上角开始看：源程序字符流进入词法分析器，分析器内部依赖正则表达式和自动机理论，最终输出Token序列。右侧是理论基础，左侧是实践工具，底部是核心流程。
我个人觉得，理解这张图比死记硬背Thompson构造法的细节更重要。因为当你真正动手写词法分析器时，脑子里要有这张「地图」，才知道每一步在干什么。
好了，词法分析的基础就讲到这里。下一节我们会深入NFA到DFA的转换，以及如何用状态转移表驱动词法分析器。到时候我会分享一个我实际项目中用过的优化技巧，保证让你眼前一亮。