词法分析基础：从字符流到Token的旅程
各位同学，今天我们来聊聊编译器的第一道关卡——词法分析。说实话，我刚开始学编译原理时，觉得这玩意儿不就是个字符串处理吗？后来真正动手写了一个简单的词法分析器，才发现这里面的门道还真不少。
词法分析的任务：它到底在干什么？
词法分析的任务，说白了就一句话：把源代码的字符流，转换成有意义的词法单元（Token）流。
你想想看，编译器拿到的是一个长长的字符串，比如：
int a = 10 + 20;这个词法分析器要做的，就是把它拆成一个个有意义的“单词”：
int—— 关键字a—— 标识符=—— 赋值运算符10—— 数字字面量+—— 加法运算符20—— 数字字面量;—— 分号
嗯，这里要注意：词法分析器不关心这些Token组合起来有没有意义，它只负责“切词”。至于语法对不对，那是语法分析器的事。
核心任务总结：
- 扫描字符流
- 识别出有意义的单词
- 过滤掉空白、注释等无用信息
- 生成Token流供后续阶段使用
词法单元（Token）、模式与词素
这三个概念经常被混淆，我当年也踩过这个坑。咱们一个一个说清楚。
词素（Lexeme）：源代码中实际出现的字符序列。比如上面例子中的 int、a、10 都是词素。
词法单元（Token）：对词素进行分类后的抽象单元。它通常是一个二元组：<Token类型, 属性值>。
模式（Pattern）：描述词素应该长什么样的规则。比如“标识符”的模式是“以字母或下划线开头，后跟零个或多个字母、数字或下划线”。
举个例子你就明白了：
// 源代码中的词素
"while"
// 对应的Token
<WHILE, "while">
// 匹配的模式
while 关键字模式：精确匹配 "while"我的经验：在实际项目中，我习惯把Token定义成一个枚举类型，每个枚举值对应一种Token类型。这样后续处理起来特别清晰，代码也容易维护。
正则表达式基础：描述模式的利器
正则表达式，说白了就是一套描述字符串模式的“小语言”。词法分析中，我们用正则表达式来定义每个Token的模式。
常用的正则表达式符号：
| 符号 | 含义 | 示例 |
|---|---|---|
a |
匹配字符 a | a 匹配 "a" |
. |
匹配任意单个字符 | a.b 匹配 "acb" |
* |
零次或多次重复 | a* 匹配 "", "a", "aa" |
+ |
一次或多次重复 | a+ 匹配 "a", "aa" |
? |
零次或一次 | a? 匹配 "", "a" |
| |
选择 | a|b 匹配 "a" 或 "b" |
[abc] |
字符集 | [0-9] 匹配任意数字 |
举个实际例子，标识符的正则表达式可以写成：
[a-zA-Z_][a-zA-Z0-9_]*数字字面量：
[0-9]+我曾经踩过的坑：写正则表达式时，一定要注意优先级。比如 a|bc 匹配的是 "a" 或 "bc"，而不是 "ab" 或 "ac"。如果你想要后者，得写成 a(b|c)。这个细节让我调试了整整一个下午。
有限自动机（DFA/NFA）概念
正则表达式虽然好写，但计算机没法直接执行它。我们需要把正则表达式转换成一种计算机能理解的“机器”——有限自动机。
NFA（非确定有限自动机）：
- 从一个状态出发，读入一个字符，可能到达多个状态
- 允许 ε 转移（不读字符就能跳转）
- 实现简单，但效率低
DFA（确定有限自动机）：
- 从一个状态出发，读入一个字符，只能到达一个确定的状态
- 没有 ε 转移
- 实现复杂，但效率高
我画了一张图，帮你理解从正则表达式到DFA的转换过程：
你看，状态0是起始状态，读入字母或下划线后进入状态1。状态1读入字母、数字或下划线后进入状态2（接受状态），状态2还可以继续读入这些字符形成自环。这就是一个典型的标识符DFA。
我的建议：刚开始学的时候，别急着去理解NFA到DFA的转换算法。先画几个简单的DFA，比如匹配数字、匹配标识符，把状态转移图画熟练了，后面自然就理解了。
词法分析器的实现思路
有了DFA，实现词法分析器就水到渠成了。基本思路是：
- 为每种Token类型构建一个DFA
- 从输入字符流的起始位置开始，模拟DFA的运行
- 记录每次到达接受状态的位置
- 当DFA无法继续转移时，回退到最近一次接受状态
- 输出该Token，然后从下一个字符重新开始
这里有个关键点——最长匹配原则。比如输入是 while1，如果只匹配到 while 就停下来，那后面的 1 就丢了。正确的做法是尽可能多地读入字符，直到无法匹配为止。
我曾经犯过的错：写词法分析器时，没有处理好回退逻辑。结果遇到 ifx 这种输入，直接匹配成了关键字 if，把后面的 x 当成了另一个Token。嗯，这种bug特别隐蔽，调试起来很痛苦。
好了，词法分析的基础知识就讲到这里。记住，词法分析是编译器的“门卫”，它把杂乱的字符流整理成有序的Token流，为后续的语法分析铺平道路。下一节我们会深入讨论如何用代码实现一个完整的词法分析器。
本章要点回顾：
- 词法分析的任务：字符流 → Token流
- Token、模式、词素三者的关系
- 正则表达式是描述Token模式的工具
- DFA/NFA是正则表达式的执行模型
- 词法分析器实现的核心：DFA模拟 + 最长匹配