3、词法分析器实现：从NFA到DFA的完整旅程
说实话，词法分析器这块内容，我当年学的时候也觉得挺抽象的。什么NFA、DFA、子集构造法，听着就头大。但后来真正做编译器项目时才发现，这些理论其实特别实在——你写一个词法分析器，本质上就是在做这些转换工作。
今天咱们就把这块内容掰开揉碎了讲。我会结合我实际做过的项目经验，带你一步步走通从NFA到DFA的完整流程。
3.1 为什么需要NFA到DFA的转换？
先问个问题：我们直接用NFA做词法分析不行吗？
理论上可以，但实际不行。为什么呢？因为NFA是非确定性的——同一个状态、同一个输入字符，可能跳到多个不同的状态。你想想看，这怎么用程序实现？程序是确定性的，它没法同时走多条路。
核心区别：
- NFA：非确定性有限自动机。一个输入可能对应多条路径，适合人类理解
- DFA：确定性有限自动机。一个输入唯一确定一条路径，适合计算机执行
我在项目中遇到过这样的情况：用NFA做词法分析，结果遇到复杂正则表达式时，回溯次数爆炸，性能惨不忍睹。后来换成DFA，速度直接提升了一个数量级。
3.2 子集构造法：NFA → DFA
子集构造法，说白了就是把NFA的状态集合看作DFA的一个状态。你想想看，NFA的每个状态可能对应多个后续状态，那我把这些后续状态打包成一个"状态子集"，不就变成确定性的了吗？
具体步骤是这样的：
- 计算ε-闭包：从某个状态出发，通过ε边能到达的所有状态
- 计算转移：对每个输入字符，计算当前状态子集经过该字符能到达的状态集合
- 重复直到没有新状态：把新生成的状态子集加入DFA的状态集合
我画了个流程图，帮你理解这个过程：
3.3 一个具体的例子
光说理论太枯燥，咱们看个具体的例子。假设我们要识别正则表达式 a(b|c)*，它的NFA是这样的：
状态0 --a--> 状态1
状态1 --ε--> 状态2
状态2 --b--> 状态3
状态2 --c--> 状态4
状态3 --ε--> 状态2
状态4 --ε--> 状态2
状态1是接受状态现在用子集构造法转成DFA：
| DFA状态 | NFA状态子集 | 输入a | 输入b | 输入c |
|---|---|---|---|---|
| A | {0} | B = {1,2} | - | - |
| B | {1,2} | - | C = {2,3} | D = {2,4} |
| C | {2,3} | - | C | D |
| D | {2,4} | - | C | D |
你看，原来NFA有5个状态，转成DFA后变成了4个状态。而且每个状态对每个输入字符的转移都是确定的——这就是我们想要的。
我的经验：实际写代码时，可以用一个队列来管理待处理的状态子集。每次从队列中取出一个状态子集，计算它的转移，把新生成的状态子集加入队列。这样代码结构特别清晰。
3.4 DFA的最小化
DFA虽然能用，但往往不是最简的。你想想看，有些状态其实是等价的——它们对后续所有输入的反应都一样。那这些状态就可以合并。
最小化的核心思想是：划分等价类。
具体步骤：
- 初始划分：把状态分成两组——接受状态和非接受状态
- 细化划分：对每个分组，检查组内状态对每个输入字符的转移是否落在同一个分组中
- 重复直到稳定：直到所有分组都无法再细化
嗯，这里要注意：最小化后的DFA是唯一的（同构意义下）。也就是说，不管你用什么方法，最终得到的最小DFA都是一样的。
避坑指南：我曾经在最小化时犯过一个低级错误——忘了处理死状态。死状态就是那些无法到达接受状态的状态。这些状态其实可以全部合并成一个。如果不处理，最小化后的DFA会多出很多冗余状态。
3.5 Lex/Flex：词法分析器生成工具
讲完了理论，咱们来看看实际工具。Lex和Flex是啥？说白了就是词法分析器的"代码生成器"。你给它一个词法规则文件，它自动帮你生成C代码。
Flex是Lex的GNU版本，功能更强，也更常用。一个典型的Flex文件长这样：
%{
#include <stdio.h>
%}
%%
"if" { printf("IF keyword\n"); }
"then" { printf("THEN keyword\n"); }
[a-z]+ { printf("IDENTIFIER: %s\n", yytext); }
[0-9]+ { printf("NUMBER: %s\n", yytext); }
[ \t\n] { /* 忽略空白 */ }
. { printf("Unknown: %s\n", yytext); }
%%
int main() {
yylex();
return 0;
}这个文件分成三部分：
- 定义部分：C代码声明、正则表达式别名等
- 规则部分：模式-动作对，匹配到模式就执行对应的动作
- 用户代码部分：main函数等
我个人习惯把常用的正则表达式先定义成别名，比如：
DIGIT [0-9]
LETTER [a-zA-Z]
IDENT {LETTER}({LETTER}|{DIGIT})*这样写出来的规则更清晰，也更容易维护。
3.6 手写一个简单的词法分析器
有时候你不想依赖Lex/Flex，或者你的目标语言不是C。这时候就需要手写词法分析器了。
手写词法分析器，我建议用状态机驱动的方式。核心就是一个大循环，不断读取字符，根据当前状态决定下一步动作。
下面是一个简单的例子，识别整数和标识符：
#include <stdio.h>
#include <ctype.h>
typedef enum {
START,
IN_NUM,
IN_ID,
DONE
} State;
int main() {
char input[] = "123 abc 456xyz";
char *p = input;
State state = START;
char buffer[100];
int buf_idx = 0;
while (*p != '\0') {
switch (state) {
case START:
if (isspace(*p)) {
p++;
} else if (isdigit(*p)) {
state = IN_NUM;
buffer[buf_idx++] = *p++;
} else if (isalpha(*p)) {
state = IN_ID;
buffer[buf_idx++] = *p++;
} else {
printf("Unknown char: %c\n", *p);
p++;
}
break;
case IN_NUM:
if (isdigit(*p)) {
buffer[buf_idx++] = *p++;
} else {
buffer[buf_idx] = '\0';
printf("NUMBER: %s\n", buffer);
buf_idx = 0;
state = START;
}
break;
case IN_ID:
if (isalnum(*p)) {
buffer[buf_idx++] = *p++;
} else {
buffer[buf_idx] = '\0';
printf("IDENTIFIER: %s\n", buffer);
buf_idx = 0;
state = START;
}
break;
}
}
// 处理最后一个token
if (buf_idx > 0) {
buffer[buf_idx] = '\0';
if (state == IN_NUM)
printf("NUMBER: %s\n", buffer);
else if (state == IN_ID)
printf("IDENTIFIER: %s\n", buffer);
}
return 0;
}这个代码虽然简单，但体现了手写词法分析器的核心思想。实际项目中，我会用状态转移表来替代switch-case，这样更容易扩展。
我的建议：如果你要手写词法分析器，先画状态转移图。把每个状态、每个输入字符的转移都画清楚，再写代码。这样不容易漏掉边界情况。
3.7 总结
这一章我们走完了从NFA到DFA的完整路径。你想想看，其实核心就三件事：
- 子集构造法：把NFA的非确定性变成DFA的确定性
- DFA最小化：去掉冗余状态，让自动机更高效
- 工具与手写：Lex/Flex帮你自动生成，手写让你更理解原理
我个人觉得，理解这些原理比会用工具更重要。因为工具会变，但原理不会。你掌握了NFA到DFA的转换，以后遇到任何词法分析的问题，都能从根上理解它。