1. 从“能跑就行”到“状态清晰”：为什么词法分析的第一步是DFA
很多人第一次接触编译原理实验，看到“词法生成器”四个字，第一反应是打开搜索引擎找一段现成的正则表达式引擎代码，或者干脆用std::regex把token切出来交差。我当年也动过这个念头，但真正动手写完之后才明白，实验一让你先实现一个确定有穷状态机（DFA），不是为了折腾你，而是因为词法分析器的本质就是一个被高度优化过的DFA。你后面要写的词法生成器，无论是手写状态转移还是用自动机工具生成，底层跑的都是同一个东西。
DFA这个东西，说穿了特别朴素：它有一组有限的状态，一个输入字符集，一个转移函数，一个初始状态，以及若干个接受状态。每读入一个字符，就根据当前状态和这个字符决定跳到哪个状态；如果跳到一个接受状态，就说明刚才读入的那段字符构成了一个合法的词素。就这么简单。但简单不等于好写，尤其是当你需要处理标识符、关键字、数字常量、运算符、界符这些混杂在一起的情况时，状态的数量和转移关系会迅速膨胀，手写if-else或者switch-case很快就会变成一坨难以维护的代码。
所以这篇内容的核心目标很明确：带你从零实现一个结构清晰、可扩展、可调试的DFA，并用它完成一个简化版词法分析器的字符识别任务。适合正在做编译原理实验的同学，也适合任何想理解“正则表达式引擎底层到底在干什么”的开发者。我不会只给你一段代码就完事，而是会把设计决策、状态编码、转移表的组织方式、调试技巧、以及我踩过的坑全部摊开讲。你跟着走一遍，后面写完整的词法生成器时，会发现自己对状态的理解完全不一样了。
提示：本文假设你至少写过C++或Java，知道结构体和数组的基本用法。如果你用的是Python，思路完全一样，只是转移表的表达方式更灵活。
2. 状态机建模：先把“词”拆成状态，再谈代码
2.1 词法单元的状态抽象：从正则到状态图
在写任何代码之前，必须先把你要识别的词法单元用状态图描述出来。假设我们的实验要求识别以下几类token：
- 标识符：以字母或下划线开头，后跟字母、数字或下划线。
- 无符号整数：以数字开头，后跟数字。
- 关键字：
if、else、while、return等，本质上和标识符共享同一套字符规则，但需要在识别后查表区分。 - 运算符：
+、-、*、/、=、==、!=、<、<=、>、>=。 - 界符：
(、)、{、}、;、,。 - 空白字符：空格、制表符、换行，通常跳过。
把这些规则画成状态图，你会发现标识符和关键字可以共用一条路径：从初始状态出发，遇到字母或下划线进入“标识符主体”状态，继续读字母数字下划线就留在该状态，读到其他字符就接受并回退。数字同理。运算符稍微麻烦一点，因为=和==、<和<=、>和>=、!和!=存在前缀关系，需要多一个状态来区分“只读到一个字符”和“读到两个字符”的情况。
这里有一个关键设计决策：是否把所有token的识别塞进同一个DFA。我的建议是，实验一阶段先分开做，每个token类型一个独立的DFA函数，比如scanIdentifier()、scanNumber()、scanOperator()。这样做的好处是调试极其方便，你可以单独测试每个函数，确认状态转移正确后再考虑合并。合并成一个大DFA虽然理论上是等价的，但调试成本会指数级上升，尤其是当某个状态转移写错时，你很难定位到底是哪条规则出了问题。
2.2 状态编码：用枚举还是整数常量
状态怎么表示？最直观的方式是用枚举：
enum class State { START, IN_ID, IN_NUM, IN_OP, IN_OP_EQ, DONE, ERROR };枚举的好处是代码可读性高，调试时打印状态名一目了然。但如果你后面要写一个通用的词法生成器，状态数量是动态的，枚举就不适用了，得用整数索引加转移表。实验一阶段我建议先用枚举把逻辑跑通，等理解透了再改成表驱动。
转移函数怎么写？最朴素的方式是switch-case：
State transition(State current, char ch) { switch (current) { case State::START: if (isalpha(ch) || ch == '_') return State::IN_ID; if (isdigit(ch)) return State::IN_NUM; if (isOperatorChar(ch)) return State::IN_OP; return State::ERROR; case State::IN_ID: if (isalnum(ch) || ch == '_') return State::IN_ID; return State::DONE; // ... 其他状态 } }这种写法在状态少的时候没问题，但状态一多，switch会变得非常长，而且每个状态的处理逻辑散落在不同的case里，修改起来容易漏。更好的方式是用二维数组做转移表，行是状态，列是字符类别，值是下一个状态。字符类别需要预先归类，比如把所有字母归为一类，所有数字归为一类，把=单独归为一类，等等。
// 字符类别索引 enum CharClass { CC_LETTER, // 字母或下划线 CC_DIGIT, // 数字 CC_EQ, // '=' CC_LT, // '<' CC_GT, // '>' CC_BANG, // '!' CC_OTHER, // 其他字符 CC_COUNT }; // 转移表：trans[当前状态][字符类别] = 下一个状态 State trans[STATE_COUNT][CC_COUNT] = { // START行 { State::IN_ID, State::IN_NUM, State::IN_OP, State::IN_OP, State::IN_OP, State::IN_OP, State::ERROR }, // IN_ID行 { State::IN_ID, State::IN_ID, State::DONE, State::DONE, State::DONE, State::DONE, State::DONE }, // ... 其他行 };表驱动的好处是状态转移关系一目了然，你可以直接对着状态图填表，填完之后检查每一行是否覆盖了所有字符类别。而且后面如果要增加新的token类型，只需要增加状态和对应的行，不需要改动转移逻辑的代码结构。这是从“手写状态机”到“词法生成器”的关键一步。
2.3 接受状态与回退：为什么需要“多看一个字符”
DFA的一个核心特性是：它不知道什么时候该停下来。比如识别标识符abc，你读到a进入IN_ID，读到b还在IN_ID，读到c还在IN_ID，读到空格时发现空格不属于标识符字符集，此时你才知道标识符结束了。但问题是，空格已经被你读进来了，它不属于标识符，你需要把它“退回去”，让下一个token的扫描从空格开始。
这就是所谓的**回退（retract）**机制。实现方式很简单：维护一个输入指针pos，每次读取字符时pos++，如果需要回退就pos--。但要注意，回退只能回退一个字符，因为DFA每次只多看一个字符就能确定当前token是否结束。这也是DFA相对于NFA的优势之一：不需要回溯多个字符，效率高。
char getChar() { if (pos < input.size()) return input[pos++]; return '\0'; // EOF } void retract() { if (pos > 0) pos--; }在实际写代码时，我习惯把“读取-判断-回退”封装成一个循环：
State state = State::START; std::string lexeme; while (true) { char ch = getChar(); State next = trans[state][charClass(ch)]; if (next == State::ERROR || next == State::DONE) { retract(); break; } lexeme += ch; state = next; }这里有一个容易踩的坑：EOF的处理。当getChar()返回\0时，charClass应该把它归为CC_OTHER，这样从IN_ID状态会转移到DONE，然后回退。但回退之后pos指向的是\0的位置，下一次循环又会读到\0，如果不做特殊处理，可能会陷入死循环。我的做法是在主循环里判断pos是否已经到达输入末尾，如果是且当前状态是START，就直接结束。
注意：回退操作在表驱动DFA里是必须的，但如果你用的是“最长匹配”策略，回退逻辑需要更小心。实验一阶段建议先用最简单的“读到一个不属于当前token的字符就回退”策略，等跑通了再考虑优化。
3. 从状态表到可运行代码：一个极简DFA的完整落地
3.1 字符分类函数的实现细节
字符分类是DFA的入口，分类错了后面全错。我见过不少同学直接写if (ch >= 'a' && ch <= 'z')，这样写本身没错，但可移植性差，而且容易漏掉大写字母和下划线。更稳妥的方式是用标准库函数isalpha、isdigit、isalnum，但要注意这些函数对char参数有符号性问题，最好先转成unsigned char。
int charClass(char ch) { if (isalpha(static_cast<unsigned char>(ch)) || ch == '_') return CC_LETTER; if (isdigit(static_cast<unsigned char>(ch))) return CC_DIGIT; switch (ch) { case '=': return CC_EQ; case '<': return CC_LT; case '>': return CC_GT; case '!': return CC_BANG; default: return CC_OTHER; } }这里有一个设计上的取舍：是否把=、<、>、!单独分类。如果你把它们都归为CC_OTHER，那么从START状态遇到这些字符时，你无法区分到底是哪个运算符，需要额外读取字符来判断。单独分类的好处是转移表可以直接根据字符类别决定下一个状态，不需要在转移函数里再做判断。代价是字符类别数量增加，转移表的列数变多。实验一阶段，我倾向于单独分类，因为这样转移表的逻辑更清晰，调试时也更容易看出问题。
3.2 转移表的填充与验证
转移表填完之后，必须做验证。验证的方法很简单：手动模拟几个典型输入，看状态转移是否符合预期。比如输入abc123，从START开始，遇到a（CC_LETTER）转到IN_ID，遇到b还在IN_ID，遇到c还在IN_ID，遇到1（CC_DIGIT）还在IN_ID，遇到2还在IN_ID，遇到3还在IN_ID，遇到EOF（CC_OTHER）转到DONE，回退，接受。整个过程状态序列是START -> IN_ID -> IN_ID -> IN_ID -> IN_ID -> IN_ID -> IN_ID -> DONE，词素是abc123。
再比如输入==，从START遇到=（CC_EQ）转到IN_OP，再遇到=（CC_EQ）转到IN_OP_EQ，遇到EOF转到DONE，接受，词素是==。如果输入是=后面跟一个字母，比如=a，从START遇到=转到IN_OP，遇到a（CC_LETTER）时，IN_OP行对应的CC_LETTER列应该是什么？应该是DONE，因为=本身就是一个合法的运算符，遇到字母说明运算符结束了，需要回退。所以IN_OP行的CC_LETTER列填DONE，CC_EQ列填IN_OP_EQ，其他列填DONE。
这种手动模拟虽然笨，但非常有效。我建议你在纸上画一个表格，行是状态，列是字符类别，把每个格子填上目标状态，然后逐个检查。填完之后，用几个边界情况测试：空输入、只有空白字符、只有单个运算符、标识符后直接跟运算符（如a+b）、数字后直接跟字母（如123abc，这应该报错还是识别为两个token？取决于你的实验要求）。
3.3 主循环与Token输出
主循环的逻辑是：跳过空白字符，然后根据当前字符决定调用哪个扫描函数，扫描完成后输出token类型和词素，继续下一轮。
std::vector<Token> tokenize(const std::string& input) { std::vector<Token> tokens; size_t pos = 0; while (pos < input.size()) { // 跳过空白 while (pos < input.size() && isspace(static_cast<unsigned char>(input[pos]))) pos++; if (pos >= input.size()) break; char ch = input[pos]; if (isalpha(static_cast<unsigned char>(ch)) || ch == '_') { tokens.push_back(scanIdentifier(input, pos)); } else if (isdigit(static_cast<unsigned char>(ch))) { tokens.push_back(scanNumber(input, pos)); } else { tokens.push_back(scanOperator(input, pos)); } } return tokens; }每个scan函数的内部逻辑就是前面说的DFA循环。以scanIdentifier为例：
Token scanIdentifier(const std::string& input, size_t& pos) { State state = State::START; std::string lexeme; while (pos < input.size()) { char ch = input[pos]; State next = trans[state][charClass(ch)]; if (next == State::DONE || next == State::ERROR) break; lexeme += ch; pos++; state = next; } // 查关键字表 TokenType type = isKeyword(lexeme) ? TokenType::KEYWORD : TokenType::IDENTIFIER; return Token(type, lexeme); }注意这里没有显式的回退操作，因为我们在循环里先判断next，如果是DONE或ERROR就不消费当前字符，pos保持不变，相当于自动回退了。这种写法比先消费再回退更简洁，也不容易出错。
提示：关键字识别不要用一堆
if-else，用一个std::unordered_set<std::string>或者std::map查表，代码更干净，扩展也方便。
4. 调试DFA时最容易翻车的几个地方
4.1 状态转移表的行列错位
这是最隐蔽的bug。你填表的时候可能把某一行的列顺序记错了，比如把CC_EQ和CC_LT的顺序搞反了，结果=被识别成<。这种错误在代码里不会报错，只会导致token类型错误，而且往往要到测试阶段才发现。我的建议是：在转移表旁边写注释，标明每一列对应的字符类别，并且在初始化时用static_assert检查列数是否匹配。
// trans[state][charClass] // 列顺序：CC_LETTER, CC_DIGIT, CC_EQ, CC_LT, CC_GT, CC_BANG, CC_OTHER State trans[STATE_COUNT][CC_COUNT] = { ... }; static_assert(sizeof(trans[0]) / sizeof(trans[0][0]) == CC_COUNT, "列数不匹配");另外，每次修改转移表后，重新跑一遍所有测试用例，不要只跑你正在调试的那个。我吃过这个亏：改了一个状态转移，结果另一个不相关的token识别挂了，排查了半天才发现是表填错了。
4.2 回退逻辑与EOF的边界情况
回退逻辑在输入末尾特别容易出问题。假设输入是abc，没有换行符。扫描标识符时，读到c之后pos已经等于input.size()，下一次循环pos < input.size()为假，直接退出，词素是abc，正确。但如果输入是abc（末尾有空格），扫描到空格时next是DONE，不消费空格，pos指向空格，返回标识符。主循环下一轮跳过空格，pos到达末尾，结束。看起来没问题。
但如果你在scanIdentifier里用了getChar()和retract()的写法，就要小心EOF的处理。getChar()在pos >= input.size()时返回\0，retract()会把pos减一，如果pos已经是0，减一就变成负数了。所以retract()里必须加if (pos > 0)的判断。这个bug在输入为空或者只有一个字符时特别容易触发。
4.3 关键字与标识符的优先级
关键字和标识符共享同一套字符规则，区别只在于识别完成后查表。这里有一个常见的错误：在DFA内部就把关键字识别出来。比如在IN_ID状态里判断当前词素是否是关键字，如果是就转到KEYWORD状态。这样做的问题是，关键字表是动态的，而且DFA的状态应该只负责字符层面的识别，不应该掺杂语义判断。正确的做法是：DFA只负责识别出“这是一个标识符形状的词素”，然后在外层查关键字表，决定是IDENTIFIER还是KEYWORD。
这个设计原则在后面写词法生成器时非常重要：DFA只做字符识别，语义分析交给外层。这样DFA的转移表可以保持稳定，增加关键字不需要修改状态机。
4.4 运算符的前缀匹配问题
=和==、<和<=、>和>=、!和!=这几组运算符存在前缀关系。处理方式有两种：一种是最长匹配，即尽可能读入更多字符，直到无法构成更长的运算符为止；另一种是优先匹配短运算符，即读到=就立即返回，不检查下一个字符是否是=。显然，最长匹配才是正确的，因为==是一个独立的运算符，不能被拆成两个=。
实现最长匹配的关键是：在IN_OP状态遇到=时，不要立即接受，而是转到IN_OP_EQ状态，继续读下一个字符。如果下一个字符不是=，则回退，接受IN_OP状态的词素（即单个=）。如果下一个字符是=，则接受IN_OP_EQ状态的词素（即==）。这个逻辑在转移表里体现为：IN_OP行的CC_EQ列填IN_OP_EQ，IN_OP_EQ行的所有列填DONE（因为==已经是最长的了，后面跟任何字符都说明运算符结束）。
但这里有一个细节：!单独出现时通常不是合法运算符（除非你的语言支持逻辑非），所以!后面必须跟=才是合法的!=。如果输入是!a，应该报错。这个逻辑需要在转移表里体现：IN_OP状态遇到!转到IN_OP_BANG状态，IN_OP_BANG状态遇到=转到IN_OP_NEQ状态，遇到其他字符转到ERROR。这样!a就会在IN_OP_BANG状态遇到a时转到ERROR，报错。
注意：实验一阶段，如果你的实验要求不涉及
!=，可以简化处理，把!单独作为一个运算符或者直接报错。但理解这个前缀匹配的逻辑，对后面写完整的词法分析器非常重要。
5. 从实验一延伸到词法生成器：DFA只是起点
5.1 表驱动DFA的通用化改造
实验一你写的是一个针对特定token集合的DFA。但词法生成器的目标是：给定一组正则表达式，自动生成DFA。这意味着你不能把状态和转移关系硬编码在代码里，而应该把它们作为数据结构的输入。
改造的思路是：把状态定义、字符类别定义、转移表、接受状态集合、每个接受状态对应的token类型，全部用数据结构表示。然后写一个通用的runDFA函数，接收这些数据结构和输入字符串，输出token序列。
struct DFADefinition { int stateCount; int startState; std::vector<int> acceptStates; std::vector<std::vector<int>> transitionTable; // [state][charClass] std::vector<TokenType> acceptTypes; // 每个接受状态对应的token类型 };这样，当你后面用正则表达式构造NFA、再转换成DFA时，只需要生成这个DFADefinition结构，然后交给通用的runDFA执行即可。实验一的手写DFA，本质上是在手动填充这个结构，理解了这个映射关系，后面的自动化生成就顺理成章了。
5.2 从DFA到NFA再到正则：反向理解词法生成器
如果你已经理解了DFA的工作方式，下一步可以反过来想：给定一个正则表达式，怎么构造出对应的DFA？标准的路径是：正则表达式 -> NFA（Thompson构造法） -> DFA（子集构造法） -> DFA最小化 -> 生成转移表。实验一你写的是最后一步的“执行”部分，而词法生成器的核心是前面的“构造”部分。
我建议你在完成实验一之后，尝试手动把一个简单的正则表达式（比如[a-z][a-z0-9]*）转换成NFA，再用子集构造法转换成DFA，最后和实验一里手写的标识符DFA对比。你会发现，子集构造法生成的DFA状态可能比你手写的多，但经过最小化之后，状态数量会减少到和你手写的差不多。这个过程能让你真正理解“为什么DFA是最优的”。
5.3 性能考量：DFA为什么比正则表达式引擎快
很多人会问：既然std::regex已经能匹配正则表达式了，为什么还要自己写DFA？答案很简单：性能。std::regex通常是基于回溯的NFA实现，最坏情况下时间复杂度是指数级的。而DFA的时间复杂度是线性的，每个字符只需要一次状态转移，没有回溯。对于编译器这种需要处理大量源代码的场景，DFA的效率优势非常明显。
当然，DFA也有缺点：状态爆炸。当正则表达式的数量很多时，DFA的状态数量可能急剧增加。这就是为什么实际的词法生成器（如Flex）会提供DFA最小化和表压缩的选项。实验一阶段你不需要考虑这些，但理解这个权衡，对你后面选择工具和优化代码很有帮助。
提示：如果你对DFA最小化感兴趣，可以看看Hopcroft算法。它的核心思想是把状态划分成等价类，然后合并等价状态。实验一阶段可以先跳过，等词法生成器跑通了再回头优化。
6. 一些让我少走弯路的实操习惯
写DFA代码的时候，我养成了几个习惯，后来发现非常省时间。第一个习惯是先画状态图再写代码。状态图不用很漂亮，用纸笔或者画图工具都行，关键是每个状态的含义、每条转移的条件、哪些是接受状态，必须清清楚楚。我见过太多同学直接上手写switch-case，写到一半发现状态不够用，又回头改，改着改着就乱了。
第二个习惯是为每个状态写一个测试用例。比如START状态，测试空输入、测试单个字母、测试单个数字、测试单个运算符；IN_ID状态，测试字母后跟字母、字母后跟数字、字母后跟运算符、字母后跟EOF。每个测试用例不需要很复杂，但必须覆盖该状态的所有出边。这样一旦某个转移写错，测试会立刻告诉你。
第三个习惯是打印状态转移日志。在DFA循环里加一行调试输出，打印当前状态、读入字符、下一个状态。跑测试的时候打开日志，一眼就能看出状态转移是否符合预期。这个习惯在调试复杂的DFA时特别有用，因为你可以看到完整的转移路径，而不是只看到最终结果。
#ifdef DEBUG std::cerr << "State: " << stateName(state) << ", Char: " << ch << ", Next: " << stateName(next) << std::endl; #endif最后一个习惯是保持转移表的单一数据源。状态定义、字符类别定义、转移表，这三者必须保持一致。我通常会把它们放在同一个头文件里，用枚举定义状态和字符类别，用二维数组定义转移表，然后在代码里只通过枚举名访问，不直接写数字。这样即使后面增加状态或字符类别，编译器也会帮你检查数组维度是否匹配。
这些习惯看起来琐碎，但在我后来写词法生成器的时候，它们帮我节省了大量调试时间。DFA本身不复杂，复杂的是状态之间的交互和边界情况。把状态图、测试用例、日志、单一数据源这四件事做好，你就能把DFA写得又快又稳。
实操)
