企业官网建设流程全解析

这个实验看起来简单，实际上一旦把“从正则表达式到自动机”这条完整链路走通，你对编译器的理解会直接上升一个档次。词法分析（Lexical Analysis）是整个编译过程的第一步，它负责把源代码字符串拆成有意义的记号（Token），而这门实验里最经典、最值得手写一遍的做法，就是基于 Thompson 构造法：把正则表达式转换成 NFA，再把 NFA 转成 DFA，最后用 DFA 做串匹配。适合正在上编译原理课、或者想自己写一个脚本语言前端的同学参考。

我用的是 C++ 实现，整体代码量在 1000 行左右；如果你用 Python，代码量会更少，但处理性能模型会略有差异。下面我把整个项目的设计思路、核心原理、实现细节、踩坑记录全部拆开讲清楚，希望能帮你把这个实验做成黑盒测试和脑力测试都能扛住的版本。

1. 项目整体设计与思路拆解

1.1 这个实验到底在做什么

大多数编译原理教材会把实验分成三块：词法分析、语法分析、语义分析。词法分析实验一般有两种做法：一种是使用现成工具（比如 Flex、lex），直接写 .l 文件让工具生成分析器；另一种是纯手写，要求你实现正则表达式解析、NFA 构造、DFA 转换，再用 DFA 去扫描源码。

这个标题里点名“（Thompson）”，意味着课程期望你采用 Thompson 构造法来完成 NFA 的构造。Thompson 构造法的本质是：把正则表达式视作一组基本结构（单字符匹配、连接、选择、闭包），每种结构都有一套固定的“拼装”规则，最终构建出一台带空转移的 NFA 状态机。

我一开始也犹豫过，要不要直接用现成工具，但后来想明白一件事：如果用工具，你学到的只是配置语法；而手写 Thompson 构造法，你能看到正则表达式的每个算子是如何变成状态边和状态的。这种“看到机器长什么样”的体验，比任何 PPT 都直观。

1.2 为什么选择 Thompson 构造法而不是直接手写状态机

很多同学觉得词法分析很简单，直接在扫描源码时写一堆 if 判断不就行了吗？比如判断是不是数字、是不是标识符。这种思路对付几十行 demo 是没问题的，但它有两个明显弊端：

第一，逻辑复杂后失控。当你需要同时识别关键字、运算符、注释、字符串、浮点数时，每个分支里又嵌套分支，代码会很快滑向不可维护的深渊。第二，规则变化成本高。如果今天要加一个->箭头操作符，你得在所有判断链里找到对应位置手动补充，很容易漏掉边界情况。

Thompson 构造法恰好解决这两个痛点。你把所有词法规则统一写成“正则表达式清单”，比如if、[a-zA-Z_][a-zA-Z0-9_]*、[0-9]+(\.[0-9]+)?，然后让代码自动把这批正则编译成一台统一的 DFA。后续要加语法，只需修改正则清单，不需要改动扫描主逻辑。这个思路，和编译器设计中“语法驱动”的思想一脉相承。

1.3 词法分析器的整体架构

我的项目最终长成这样：

• 正则表达式预处理模块：把用户写的正则字符串做一些规范化处理，比如去掉多余空格、补全省略的显式连接符·。
• 中缀到后缀的转换模块：把正则表达式当作普通表达式处理，使用一个调度场算法（Shunting-yard）把中缀形式转为后缀形式，方便后续自底向上的构造。
• Thompson NFA 构造模块：读到后缀表达式，遇字符压栈、遇操作符弹出对应子表达式片段，按规则拼装成新的 NFA。
• NFA 转 DFA 模块：用子集构造法（Subset Construction）消除空转移，得到一台确定有限自动机。
• DFA 最小化模块：用划分法（分割法）合并等价状态，去掉冗余状态，让状态机更精简。
• Token 识别驱动模块：读入源代码字符串，按照 DFA 状态转移表，配合最长匹配原则切分成 Token 序列。
• 错误报告模块：记录出错的行号、列号、错误字符和期望说明。

整个链路是单向依赖的：正则文本 -> NFA 图结构 -> DFA 转移表 -> 驱动识别。我在实验报告里画了一张大的调用关系图，如果你也需要画图，建议用类似“模块-职责”的框图，会比纯文字清楚很多。

1.4 Token 体系与正则规则设计

在设计词法分析器之前，必须先确定支持哪些 Token 类型。我基于一个类 C 语言的简化子集，定义了这几类：

这里有一个非常重要的细节：关键字和标识符的正则其实会同冲突。因为关键字本身也是字母序列，用[a-zA-Z_][a-zA-Z0-9_]*这个表达式也能匹配到if。一般有两种解决方案：

方案一：把关键字单独变成大正则里的“选择分支”，并且放在标识符分支之前。但因为做的是最长匹配，最后返回的 token 类型取决于命中哪个分支的接受状态。方案二：统一当作标识符识别，然后在识别结束之后查一张关键字表。我最终采用了方案二，理由很直接：当正则规则从几十条增加到几百条时，维护一张哈希关键字表远比在正则清单里维护几十个kw_if分支简单，而且关键字的识别本来就是 O(1) 查表。

2. 核心原理解析：正则、NFA 与 DFA 的三角关系

2.1 正则表达式如何描述词法模式

正则表达式的本质是一种描述字符串集合的记号法。比如[0-9]+表示“至少一位数字构成的所有字符串”，(ab|cd)*表示“由任意个 ab 或 cd 首尾拼接形成的字符串”。

词法分析器需要的，就是把这些字符串集合变成一台状态机。原因是：正则表达式适合被人阅读和修改，但计算机执行匹配时，逐字回溯的效率很不稳定，而且容易写出灾难性回溯。而状态机不存在回溯，它每读入一个字符，只做一次查表转移，匹配时间是 O(n) 的。

从正则表达式到状态机，最经典的路径就是：正则 -> NFA -> DFA。NFA（非确定有限自动机）和 DFA（确定有限自动机）的区别在于：NFA 在某个状态读入某个字符时，可能有多条可走路径，也可能存在不需要读字符就能走的空转移；DFA 每个状态读入每个字符后只有一个确定目标。计算机模拟 NFA 需要同时跟踪多个候选状态，而模拟 DFA 只需要一个“当前状态”变量。

2.2 NFA 的形式化定义与表示方法

一台 NFA 在理论上用五元组表示：状态集合、字母表、转移函数、初态集合、接受状态集合。但在代码里，我建议直接用一个有向图来表示它。

每个状态我分配一个整数编号。状态的出边我需要记录两类：普通字符边和空转移边。所以我的 NFA 结构大概是：

struct NFAState { int id; map<char, vector<int>> transitions; // 普通字符转移 vector<int> epsilonTransitions; // 空转移 bool isAccept = false; // 是否是接受状态 };

这里有一个非常巧妙的设计习惯：一段 NFA 片段我会额外记录两个编号，start 和 accept。这样在拼接不同正则片段时，不需要遍历整个状态族去找入口和出口，直接拿这两个编号就能完成图的缝合。Thompson 构造法的所有规则本质上都是：给定两个片段的 start 和 accept，新建一个片段并记录新的 start 和 accept。

2.3 Thompson 构造法的五个基本规则

Thompson 构造法可以归纳成五种基本模式，我逐一拆开说明：

单字符匹配：新建一个起始状态 S 和一个接受状态 A，在 S 和 A 之间连一条标有该字符的边。这是最小的结构单元。比如正则a就会得到两个状态和一条边。

连接运算：假设你已经有了一个子正则表达式对应的片段 E1（start=s1, accept=a1）和另一个片段 E2（start=s2, accept=a2）。连接E1 E2的做法是：新建一个空转移边，从 a1 指向 s2，然后整个新片段保留 s1 作为 start，a2 作为 accept。注意这里有个优化点——如果 E1 的 accept 没有其他入边，你可以直接把 E1 的 accept 和 E2 的 start 合并成一个状态，省去一条空转移边。但为了代码清晰，我先保留标准做法，优化可以留到 DFA 最小化阶段再做。

选择运算（|）：对于E1 | E2，新建一个新的起始状态 NS，从 NS 分别引两条空转移边到 s1 和 s2。同时新建一个新的接受状态 NA，从 a1 和 a2 分别引空转移边到 NA。这样整台 NFA 匹配时，要么完全走 E1 的路径，要么完全走 E2 的路径，两条路径互不干扰。

闭包运算（星号 *）：对于E*，新建 NS 和 NA。在 NS 和 NA 之间加一条空转移边，代表“直接跳过整个 E”；再从 NS 引一条空转移边到 s1；从 a1 引一条空转移边到 NA；最后从 a1 引一条空转移边回 s1，代表“可以重复”。这条回边是整个闭包构造的精髓，它让状态机具备了循环能力。

加号和问号：E+可以等价于E E*，E?可以等价于E | ε。如果你实现时想简单，可以先用等价关系把表达式改写；如果你想要更高效的状态数，也可以单独实现规则。我当时图省事，直接在语法树展开时用等价关系替换，实验状态下状态数量略多，但逻辑不容易出错。

2.4 子集构造法：怎么把 NFA 变成 DFA

NFA 虽然已经能表达正则语言，但模拟执行时需要维护一个“活动状态集合”，每次读入字符都要重新计算闭包，效率太低。所以我们需要把 NFA 转成 DFA。

核心方法是子集构造法（Subset Construction）。它做的事，可以理解成“把所有可能同时处于的状态打包成一个整体，并将其视为 DFA 中的一个状态”。

具体流程是这样的：

1. 从 NFA 的起始状态出发，求它的 epsilon 闭包。所谓 epsilon 闭包，就是一个状态集合，包含当前状态本身，以及从集合中任一状态沿着空转移边能到达的所有状态。这个集合就是 DFA 的初态。
2. 对当前 DFA 状态（也就是一个 NFA 状态集合），逐个考虑字母表里的每个字符 c，求出集合中所有状态通过 c 边能到达的目标状态，对这些目标状态再求一次 epsilon 闭包，得到一个候选子集。
3. 如果这个候选子集之前没出现过，就把它登记为一个新的 DFA 状态，并把这条(当前状态, c) -> 新状态的转移记录下来。
4. 重复执行，直到所有 DFA 状态的所有字符转移都被计算完毕。

这里有一个经常让新手崩溃的 bug：epsilon 闭包的计算必须使用迭代或队列，不能只递归一层。因为你从状态 A 通过空转移到了 B，B 后面可能还有空转移到 C，因此闭包是一个持续扩散的过程，直到集合不再增大。

2.5 DFA 最小化：去掉冗余状态

子集构造法生成的 DFA 往往包含大量冗余状态，因为不同的“NFA 状态集合”可能从匹配角度上完全等价。最小化的标准做法是填表法或划分法。

我的实现采用划分法，思路是先把所有状态分成两类：接受状态和非接受状态。然后反复细化：对于当前划分中的每个等价类，分别用每个字符冲激，看目标状态的归类情况。如果一个状态在字符 a 下跳到了类别 X，另一个状态在字符 a 下跳到了类别 Y，而 X 和 Y 不是同一个类别，那么这两个状态必须分开。

最小化能显著减少识别阶段的状态数。我记得自己第一次跑最小化后，识别一个包含十个 token 类的词法分析器，状态数从 40 多个降到了 20 个左右。状态少，转移表就小，查表速度自然更快。

3. 实操环节：从零实现一个基于 Thompson 的词法分析器

3.1 技术选型与数据结构设计

语言我推荐用 C++ 或 Python。Python 的好处是写起来快，适合快速验证算法；C++ 的好处是性能好，状态对象和转移表更接近课程对“数据结构”的要求。我最终用 C++，并全程以指针和索引号操作状态。

我的数据结构分三层：

• 第一层是 NFA 图，用vector<NFAState>存所有状态。
• 第二层是 DFA，用int表示状态编号，用二维转移表vector<vector<int>>表示状态间转移，用vector<string>记录每个 DFA 状态对应的 token 类型。
• 第三层是源码扫描缓冲，直接把源码读入一个string，用一个下标指针从头扫到尾。

在动手写核心算法之前，我强烈建议你先把“中缀转后缀”这个步骤做扎实。因为所有的 Thompson 规则本质是按后缀表达式的顺序触发的。后缀表达式的求值就是典型的栈式求值：遇到字符就压一个单字符 NFA 片段进栈；遇到操作符就弹出两个片段，拼装后再压栈。这几乎就是“表达式求值”的经典场景。

3.2 正则表达式预处理：补全省略的连接符

人写正则时通常会省略连接运算符。比如写abc，实际含义是a·b·c；写ab*，实际含义是a·(b*)。为了让调度场算法能正确处理优先级，我需要对原始文本做一个扫描，在适当位置插入显式的连接符·。

具体规则是：从第二个字符开始，如果当前字符可以出现在整个字符集合中，而且前一个字符是可以结束一个原子的字符，那么认为这里存在省略的连接。要分类讨论：

• 如果前一个字符是字母、数字、右括号、闭包符号*、加号+、问号?，而当前字符是字母、数字、左括号，则插入·。
• 这里最容易漏掉的情况是)*后面接字母，比如(ab)*c，在*和c之间必须插入·。

3.3 调度场算法处理优先级

处理完连接符之后，就可以用调度场算法把中缀正则表达式转成后缀表达式。

优先级从高到低我定义为：括号 > 闭包*/+/?> 连接·> 选择|。

算法过程很简单：遍历字符；遇到原子字符直接输出；遇到|或·这类二元操作符时，如果栈顶操作符优先级不低于当前操作符，就把栈顶弹出并输出，最后把当前操作符入栈；遇到左括号直接入栈；遇到右括号则弹出栈内操作符直到遇见左括号，括号本身不输出。

我最初没有给“连接符”定义优先级，结果ab|c被解析成了a·(b|c)的语义，明显不对。后来把连接符优先级设置到“低于*、高于|”之后，一切才恢复正常。建议你也专门为连接符写一个precedence判断函数，并附上几个测试用例验证。

3.4 NFA 构造类的实现要点

以下是我实现的关键函数原型，逻辑不难但细节很多：

class NFAFragment { public: int start; int accept; }; NFAFragment constructChar(char c); NFAFragment constructConcat(NFAFragment& left, NFAFragment& right); NFAFragment constructUnion(NFAFragment& left, NFAFragment& right); NFAFragment constructStar(NFAFragment& inner); NFAFragment constructPlus(NFAFragment& inner); NFAFragment constructOptional(NFAFragment& inner);

以constructUnion为例，你要做四件事：

1. 新建两个状态ns和na。
2. 从ns引出两条空转移边，分别指向left.start和right.start。
3. 从left.accept和right.accept分别引出空转移边到na。
4. 返回{ns, na}。

代码很容易，但要注意：如果left.accept或right.accept已经在构造过程中被当作普通状态并被复用（比如是两个单字符片段产生的接受状态），你直接对它加出边会不会导致其他连接出问题？答案是不会，因为在 Thompson 构造法里，每个片段的 accept 都只有一个语义上的“出口”，你在它上面加空转移边只会增加新的跳转路径，不会破坏原有路径。不过为了保险，我在设计片段结构时，约定一个片段的 accept 不再作为其他片段内部的普通状态复用，所有拼接只经由 start 和 accept 两个接口完成。

3.5 NFA 转 DFA 的驱动代码逻辑

NFA 转 DFA 的代码我用了一个队列作为工作列表：

queue<int> worklist; map<vector<int>, int> subsetToDfaId; vector<vector<int>> dfaTransitions; vector<string> dfaAcceptTokens; int getOrCreateDfaState(const vector<int>& nfaStates) { // 查表，如果已存在则直接返回 // 否则创建新的DFA状态，并加入工作队列 }

关键步骤是epsilonClosure函数。我每次求闭包都会新建一个栈，初始把当前状态集合全部压栈，然后不断弹栈，检查当前状态的所有空转移边并加入集合，直到栈空。这里如果用递归函数来求闭包，状态一多很容易栈溢出；用显式栈可以完全避免。

之后，对于每个新生成的 DFA 状态（NFA 状态集合），我遍历字母表里的每个字符，计算moveClosure。这里要特别注意：字母表如果包含全部 ASCII 可打印字符，那么每个 DFA 状态都要循环 128 甚至 256 次；如果你直接用 map 存字符而不是用固定数组，遍历时只要遍历实际出现过的字符集合即可。我的实现里维护了一个set<char> alphabet，专门收集所有正则中真正出现的字符，这样能大幅减少无效计算。

获取一个 DFA 状态对应的 token 类型也很关键。当一个 DFA 状态（NFA 状态集合）里包含多个 NFA 接受状态时，它可能同时对应“关键字 if”和“标识符”，我在设计正则清单时就让每个 token 模式的接受状态带有一个编号，并约定：如果出现冲突，取第一个被标记的接受状态。但这个约定并不总是最优，后面的最长匹配机制会弥补一部分冲突。

3.6 词法扫描驱动：最长匹配与回溯

DFA 构造完成后，词法识别本身反而简单：

• 从初始状态出发，用一个指针逐字符读入源字符串。
• 每次读入一个字符，查转移表。如果转移存在，就更新当前状态，并记住“最后一个被标记为接受状态的位置和状态编号”。
• 如果转移不存在，说明已经不可能继续匹配，这时回退到最近一次记录的“接受位置”，从这个位置切出一个 token，把扫描指针回退到接受位置，再重置 DFA 状态，开始下一个 token。

这个“记住最近接受位置”其实就是最长匹配原则的实现。我见过不少同学在这里犯错：他们一遇到死状态就直接报错，而不是先考虑“即使整个字符串目前死了，但更早的某个前缀可能已经构成合法 token”。正确做法是始终维护lastAcceptPos和lastAcceptState两个变量。

我贴一个识别核心循环的伪代码：

int i = 0; string source; while (i < source.size()) { int state = startState; int lastAcceptPos = -1; int lastAcceptState = -1; int j = i; while (j < source.size()) { int next = dfaNext(state, source[j]); if (next == -1) break; state = next; ++j; if (isAcceptState[state]) { lastAcceptPos = j; lastAcceptState = state; } } if (lastAcceptState == -1) { reportError(i, source[i]); ++i; // 跳过非法字符，继续扫描 } else { string lexeme = source.substr(i, lastAcceptPos - i); TokenKind kind = dfaAcceptTypes[lastAcceptState]; tokens.push_back({kind, lexeme, line, column}); i = lastAcceptPos; } }

最长匹配里最经典的坑是无符号常量和浮点数的边界。比如源码里出现123abc，按最长匹配，应该先识别出整数123，再把abc作为下一个标识符开头，而不是报错。上面的循环可以正确处理，因为它在读到a时发现状态死了，但123结束时已经记录过一次接受位置。

还有一类坑是关键字冲突。比如iff是一个合法的标识符，而不是关键字if加标识符f。如果你把if和标识符分开成两个正则分支，并且做了最长匹配，由于iff整体匹配标识符得到的长度更长，它会正确识别为标识符。这正好验证了“最长匹配优先于正则优先序”的策略。

3.7 表格驱动与状态压缩

DFA 状态的存储我用了一个vector<vector<int>>二维表。不过直接开状态数 × 128的表有点浪费，尤其字符集很大时。我改用了vector<map<char, int>>作为稀疏表。这样每个状态只存储实际转移的字符，内存显著下降。代价是查表多了一次map::find，但对词法分析来说依然很快。

如果你追求极致性能，可以对字符类别做一步压缩：把所有 ASCII 字符按“类型”分类（例如数字类、字母类、操作符类），同一类型在转移表中指向同一列。这本质上做了一个 DFA 输入的等价类划分，状态和表大小都会大幅缩小。实验中不做这项优化也能过，但实现它是一个很好的加分点。

4. 常见问题与排查技巧实录

4.1 空转移闭包算不对，导致 DFA 状态爆炸

这是整个实验里我花时间最多的地方。症状是：生成的 DFA 状态数远超预期，或者转移表里有大量状态从起始状态根本不可达。

根源多半是闭包没有采用迭代算法。假设 NFA 里存在两条连续空转移边A -> B -> C，如果求闭包时只处理一层，闭包集合会错误地缺少 C，导致后续子集构造的根基就错了。

建议你在求闭包时写一个独立函数，并单独测试几个已知图：

状态 0 有 epsilon 边到 1，状态 1 有 epsilon 边到 2。 epsilonClosure({0}) 必须得到 {0,1,2}。

这类单元测试强烈建议先写，否则后面报错很难定位是子集构造的问题还是闭包的问题。

4.2 运算符和双字符符号的优先级冲突

在词法规则中，==、->、<=、>=这类两个字符的运算符必须被识别成一个 token。如果你的 DFA 只按单字符切分，源码a <= b会被错误地切分成<和=两个 token。

我的解决方式是：在正则清单里把双字符运算符作为单独模式放进去，并且在识别循环里依赖最长匹配原则。比如<和<=两条正则分支同时存在时，输入<=，扫描器先吃进<，状态可能是接受态；再吃进=，又到了一个接受态（对应<=），最终记录的是最后一个接受位置，所以会输出<=而不是<。

但有一下需要注意的地方：a<-b这种源码，如果语言语义里没有定义<-运算符，DFA 在扫描时会在读完<-之后发现没有后续合法转移，最终接受位置停留在<，于是输出<和-。这是正确行为，不需要特殊处理。

4.3 关键字与标识符的冲突处理

我前面提过，标准做法是先把所有字母串都识别成标识符，再查关键字哈希表。但这里还要处理一个细节：关键字表查询必须发生在识别结束之后，而不是在识别过程中。比如intx是一个合法标识符，它扫描完是intx，查表没有命中，因此识别为标识符，而不是int加x。

在代码实现上，我会在拿到 DFA 识别结果后做一次unordered_map<string, TokenKind>查表。这种查表法比用 DFA 直接做关键字分支更灵活。我实测过识别效率几乎没有差别，因为哈希表查询是 O(1)，而词法分析的整体瓶颈在读源码和转移表的查表上。

4.4 报错位置又准又好看

报错信息一定要带行号、列号和字符上下文。我的实现里，扫描指针推进时同时维护行号与列号：遇到换行符就把行号加一、列号重置；其他字符列号加一。源码扫描中如果遇到未知字符，我会输出以下格式：

[词法错误] 第 3 行，第 7 列：无法识别的字符 '@'

行号列号的追踪听起来简单，但有一个细节：记录 token 起始位置时要用 token 开始时的行列，而报错时要用出错时的行列；如果你只记录一个全局行列，token 之间会串位。我建议在每个 token 结构体里同时保存行列信息：

struct Token { TokenKind kind; string text; int line; int col; };

4.5 常见问题速查表

我把自己在调试过程中遇到的高频问题整理成了下表，相信你在实现过程中也会撞上其中几个：

4.6 使用可视化与日志快速定位

状态机的 bug 最难查，因为问题范围大且不直观。我建议你在开发期加上一个“打印 NFA/DFA”的功能，输出类似于：

NFA states: 0 --epsilon--> 1 1 --a--> 2 2 --epsilon--> 3

打印这些边比单步调试更高效。另外，每次构造完 DFA 后，可以写一个“自检”函数：模拟一段已知 token 集，逐字输出接受状态命中情况。自检函数跑通了，再进入整体扫描流程，思路会清晰很多。

5. 编写测试用例与验收自查

5.1 从最小用例到综合用例

我的测试用例分三层：

第一层是正则表达式单元测试，主要测解析器本身。比如输入a输出一个 NFA 片段；输入a|b输出两个分支；输入(a|b)*c检查后缀表达式是否a b | c · *。这一类测试不涉及源码输入，纯看构造结果。

第二层是自动机识别测试，喂给 DFA 一组字符串，检查是否接受。我常用这些样例：

• a应接受
• aa应接受（对a*）
• ab应接受（对ab或a|b的语义需结合表达式）
• ac应拒绝

第三层是整源码的 token 流测试。我准备了一个小型 C 风格测试文件，里面写满各种边界情况：

int main() { int a = 123; float b = 3.14; if (a >= 100 && b <= 4.0) { return a + b; } // 这是一行注释 /* 多行注释 */ return 0; }

运行后我会人工检查每一行 token 的 kind 和 text，确认没有切错。

5.2 一个典型 token 输出示例

在正确实现下，第三层测试输出大致长这样（我用简化格式）：

(KEYWORD, int), (IDENT, main), (DELIM, (), (DELIM, )) ... (KEYWORD, if), (DELIM, (), (IDENT, a), (OP, >=), (INT, 100)

如果你自己和预期对不上，从打印信息反查生产这个 token 的 DFA 路径，通常会发现问题出在某个正则的括号匹配或操作符优先级上。

5.3 验收自查清单

我在最终提交实验报告之前，都会逐项核对以下检查点：

• 正则表达式是否支持括号嵌套。
• 是否支持*、+、?三种闭包。
• 是否支持|优先级低于连接。
• NFA 构造过程中是否出现状态丢失（打印验证）。
• DFA 初态是否包含 NFA 初态的完整闭包。
• 每个 DFA 状态对每个字符是否有超出一路的转移（即确定性）。
• 最小化后接受状态集合是否保持一致。
• 扫描时是否实现了最长匹配，且遇到死状态时不崩。
• 错误信息是否包含行列号。
• 程序是否能处理空源文件。

5.4 性能调优与状态规模控制

如果你做到 DFA 状态数仍然偏大，可以优先检查 NFA 构造时的“连接”操作。标准 Thompson 构造法中，连接操作会留下一条空转移边；如果把前一个片段的接收状态和后一个片段的起始状态直接合并，能省掉不少状态。实验性质的非目标不是极致性能，但如果能减少 30% 状态，不管是转移表尺寸还是构建速度都会有明显改善。

另一个优化点是字符类别。给字符集分成字母、数字、运算符号、空白符等几类，每个 DFA 状态转移表按类索引。这样在实际代码扫描时，每次查表不是查原始字符，而是先查字符类别，再根据类别查转移。有两种思路，根据自己的算法水平选一种做即可。

6. 个人踩坑笔记与最后分享

我自己完成这个实验时踩过最深的一个坑，是正则表达式的“连接符”隐藏的优先级问题。当时我调试了一个钟头，发现正则ab|cd总是被识别成a(b|c)d的语义，后来打印后缀表达式才发现，自己忘了在a和b之间显式插入连接符，导致调度场算法把|的优先级误解了。从那以后，我每次解析正则前都会先打印一遍“规范化后的表达式”，确保连接符插入位置正确。

另外一个值得分享的经验是，在动手写完整算法前，先用小例子把这套流程手工推一遍。当时我在纸上手工把(a|b)*abb这个经典三层结构走了一遍：先转后缀，再逐步构建 NFA，再做子集构造，得到 DFA。等你把手工流程走通了，再去看代码里的状态编号变化，整个思路就通畅很多。

最后再说一点后续扩展方向。如果学有余力，你可以在完成 DFA 驱动识别后，给词法分析器加一个简单的语法分析器，比如递归下降解析器，尝试解析赋值语句和表达式。词法分析只是编译器前端的入口，当你把这份 DFA 转移表拿出去做语法分析时，你会真正体会到自动机理论不是纸上谈兵。