1. 词法分析基础：正则表达式与有限自动机理论，Token定义与分类
好，咱们正式开始编译器前端的第一站——词法分析。
说实话，很多初学者觉得词法分析很简单，不就是把代码切成一个个单词嘛。嗯，表面上看确实是这样。但我在实际项目中踩过不少坑，比如一个正则写错了，导致整个语法树构建失败，排查了半天才发现是词法分析阶段漏掉了一个边界情况。所以，这一章咱们把基础打扎实。
1.1 什么是词法分析？
词法分析，说白了就是让计算机理解源代码里的「最小有意义单元」。你写的一行代码，比如 int a = 10;，在编译器眼里并不是一串字符，而是 int、a、=、10、; 这五个 Token。
我习惯把词法分析比作「拆积木」——把一整段代码拆成一块块标准大小的积木块，后面语法分析才能把这些积木搭成完整的结构树。
核心任务：将源代码字符串序列，转换为 Token 序列。
1.2 正则表达式：描述词法的语言
正则表达式是描述字符串模式的利器。在词法分析中，我们用正则来定义每种 Token 的「长相」。
举个例子，标识符（变量名、函数名）通常要求：以字母或下划线开头，后面跟字母、数字或下划线。用正则写就是：
[a-zA-Z_][a-zA-Z0-9_]*数字字面量呢？整数、浮点数都要考虑：
[0-9]+(\.[0-9]+)?我个人习惯把常用的 Token 正则先列个表，方便后面直接复用：
| Token 类型 | 正则表达式 | 示例 |
|---|---|---|
| 标识符 | [a-zA-Z_][a-zA-Z0-9_]* |
foo, _bar, x1 |
| 整数 | [0-9]+ |
42, 0 |
| 浮点数 | [0-9]+\.[0-9]+ |
3.14, 0.5 |
| 运算符 | \+|-|\*|/ |
+, -, * |
| 分隔符 | \(|\)|\{|\}|;|, |
(, ;, , |
| 关键字 | int|float|if|else|return |
int, if |
小技巧：关键字和标识符的正则可能会有冲突。比如 int 既匹配关键字正则，也匹配标识符正则。我的做法是：先匹配关键字，再匹配标识符。这样关键字会被优先识别。
1.3 有限自动机：正则的「执行引擎」
正则表达式写好了，计算机怎么用它来匹配字符串呢？这就轮到有限自动机登场了。
有限自动机有两种：
- NFA（非确定有限自动机）：一个输入可能对应多个状态转移，需要回溯。
- DFA（确定有限自动机）：每个输入唯一确定下一个状态，效率高。
实际工程中，我们通常把正则表达式先转成 NFA，再转成 DFA。为什么多此一举？因为从正则直接构造 DFA 比较麻烦，而 NFA 的构造有标准算法（Thompson 构造法），然后再用子集构造法转成 DFA。
我曾经在优化一个词法分析器时，发现 NFA 直接匹配太慢了，尤其是长代码文件。后来改成 DFA，速度提升了将近 10 倍。嗯，这里要注意：DFA 虽然快，但状态数可能爆炸，需要做状态最小化。
避坑指南：我曾经在写正则时，不小心写了个 a* 这样的模式，结果匹配空字符串时无限循环。记住：* 表示零次或多次，一定要考虑边界情况。
1.4 Token 的定义与分类
Token 是词法分析的输出。每个 Token 通常包含两部分信息：
- 类型：比如
INTEGER、IDENTIFIER、PLUS - 值：比如
42、foo、+
我习惯用枚举来定义 Token 类型：
enum TokenType {
// 关键字
INT, FLOAT, IF, ELSE, RETURN,
// 标识符
IDENTIFIER,
// 字面量
INTEGER_LITERAL, FLOAT_LITERAL,
// 运算符
PLUS, MINUS, STAR, SLASH,
// 分隔符
LPAREN, RPAREN, LBRACE, RBRACE, SEMICOLON, COMMA,
// 特殊
EOF, ERROR
}Token 的结构体可以这样设计：
struct Token {
TokenType type;
string lexeme; // 原始字符串
int line; // 行号
int column; // 列号
};你想想看，为什么需要记录行号和列号？因为报错的时候，你得告诉用户「第几行第几列出错了」。没有这个信息，调试起来简直要命。
1.5 知识体系总览
下面这张图是我自己画的，把本章的核心逻辑串起来了：
1.6 实战中的几个要点
理论说完了，聊聊实际干活时要注意什么。
第一，Token 的优先级问题。 比如 >= 和 >，如果先匹配 >，那 >= 就被拆成两个 Token 了。我建议采用「最长匹配」原则——能匹配多长就匹配多长。
第二，空白和注释的处理。 空格、换行、注释在大多数语言中是没有意义的，直接跳过就行。但要注意记录行号，不然报错信息没法定位。
第三，错误恢复。 遇到非法字符怎么办？比如用户写了个 @。我的做法是：报错，但继续扫描，尽量多发现几个错误，而不是一错就停。
个人经验：我在写词法分析器时，习惯先写一个「字符流」类，封装读取、回退、记录位置等操作。这样后面的逻辑会清爽很多。
1.7 小结
这一章我们聊了词法分析的核心：用正则表达式描述 Token，用有限自动机实现匹配，最后输出结构化的 Token 序列。
说白了，词法分析就是给源代码做「分词」。虽然看起来简单，但正则的边界情况、自动机的效率优化，都是实打实的坑。我当年第一次写词法分析器时，就因为没处理好 /* */ 注释的嵌套，导致一个开源项目编译不过去……嗯，从那以后我再也不敢轻视这一步了。