企业官网建设流程全解析

最近重新整理了编译原理中词法分析这部分，把“正则式 → NFA → DFA → 最小化DFA”这条经典链路完整手算了一遍。如果你正在准备编译原理实验、笔试面试，或者被课程设计里的词法分析器折磨，这篇内容应该能帮上忙。教材里的定理往往很干净，但实际拿笔推导时，从正则式构造NFA那一步就很容易乱；至于子集构造法构造出DFA之后，为什么还要再最小化，很多朋友也是一知半解。这篇文章用同一个例子把全过程拆开揉碎，顺便把我在手算和代码实现时踩过的坑一并说清楚。

1. 为什么非要从正则式一路折腾到DFA

1.1 三种等价描述，但工程执行能力不同

正则式、NFA、DFA在描述能力上是等价的，它们能识别的语言集合完全一致。也就是说，任给一个正则式，都能构造出等价的NFA和DFA；反过来也一样。但它们在“执行”层面的行为差别很大。

正则式是一种描述工具，它适合表达规则，比如“一串a和b组成的字符串，最后三个字符必须是abb”，用(a|b)*abb写出来非常直观。可它不能直接用来做匹配器，因为正则式本身不是一个自动机，没有一个明确的“读字符、换状态”的执行模型。

NFA引入了非确定性和ε转移，执行时一个字符可能同时激活多个状态路径，所以直接用NFA做匹配也不是不行，但需要维护一个活跃状态集合，复杂度不稳定。DFA则是最直观的执行模型：每个状态在每个输入符号上至多只有一个后继，读一个字符，状态转移是唯一的，扫描器只需要一路跟着转换表走，识别一个长度为n的字符串复杂度是O(n)。

这就是为什么编译器前端要做“正则式 → NFA → DFA”的原因：用正则式写规则，用DFA做执行。这中间NFA是你手推或者工具自动生成的中间产物。

1.2 转换路线的大局观

很多人背得住“Thompson构造法”“子集构造法”这些名词，但不知道为什么要分两步。

第一步从正则式到NFA，是用结构化的方式把正则式拆成小自动机，再拼接起来。Thompson构造法很机械，每个字符、每个并运算、每个闭包都有固定的拼接模板，几乎不需要动脑。第二步从NFA到DFA，本质是模拟NFA的“所有可能状态集合”，把NFA在读字符时可能到达的所有状态打包成一个DFA状态。这两步一组合，就从“描述规则”走到了“可执行机器”。

至于最小化，很多人误以为只有优化需要，其实它是DFA从“构造产物”变成“干净产物”的关键一步。子集构造法很容易生成重复等价的状态，状态越多，词法分析器的转换表越占空间，匹配时的缓存命中率也越差。在后面做词法分析器生成器、手写扫描器的时候，最小化直接关系到生成的代码质量。

2. 经典例子走一遍：从正则式构造NFA

2.1 选一个合适的正则式当靶子

我先选一个编译原理教材里的经典例子：

(a|b)*abb

这个正则式描述的是：所有由a和b组成的、且以abb结尾的字符串。比如abb、aabb、bababb都匹配，ab、bba、abba不匹配。

选它的原因很实际：它同时用到了字符、并运算、闭包、连接，几乎覆盖了所有正则运算符，能串起完整的转换流程。很多课程设计里的标识符、数字字面量规则，本质上比它更复杂，但核心步骤是一样的。

2.2 Thompson构造法手工步骤

Thompson构造法的核心思路是：每个子表达式都生成一个带一个开始状态和一个接受状态的小NFA，然后用ε转移把小机器拼接成大机器。原子表达式a就是两个状态、一条a转移；原子表达式b同理。

先构造a|b。取两个原子机器，引入一个新的开始状态，分别用ε转移到两个原子机器的开始；再引入一个新的接受状态，让两个原子机器的接受状态通过ε转移汇入它。我习惯用编号把状态列清楚：

• 状态1：原子a的开始，1 -a→ 2
• 状态3：原子b的开始，3 -b→ 4
• 状态0：a|b的开始，0 -ε→ 1，0 -ε→ 3
• 状态5：a|b的接受状态，2 -ε→ 5，4 -ε→ 5

接下来对这个整体应用闭包运算，也就是(a|b)*。闭包的模板稍微绕一点：引入新的开始状态6和新的接受状态7，并添加以下ε转移：

• 6 -ε→ 0，进入原来的a|b机器内部
• 6 -ε→ 7，表示可以不重复任何字符，直接接受空串
• 5 -ε→ 0，完成一次a|b后可以回到开头继续重复
• 5 -ε→ 7，也允许重复结束后从旧接受状态直接走向新接受状态

这里最容易被搞混的就是“旧接受状态回到旧开始状态”。没有这一步，闭包就只能执行一次，不能循环，整个正则式的语义就错了。

最后把(a|b)*和后面的三个字符a、b、b连接起来。连接就是让前面机器的接受状态通过ε转移到后一个原子机器的开始状态。我引入原子a的状态8、9，原子b的状态10、11，第二个b的状态12、13，并添加：

• 7 -ε→ 8
• 9 -ε→ 10
• 11 -ε→ 12

最终整台NFA的开始状态是6，唯一接受状态是13。状态较多，但每一步都有对应的小机器模板，比凭感觉乱画稳得多。

3. 子集构造法：把NFA变成DFA

3.1 ε-闭包与move操作

有了NFA，下一步就是用子集构造法得到等价DFA。两个核心概念必须吃透：

第一个是ε-闭包。一个状态集合的ε-闭包，是从集合中的任意状态出发，只沿着ε转移能到达的所有状态集合，包含这些状态本身。做闭包的时候要一层一层向外扩张，直到不能再加入新状态为止。

第二个是move操作。对于某个输入符号x，move(T, x)表示从集合T中任意状态出发，沿着一条标记为x的转移能到达的所有普通状态。注意，这里还没有算ε转移，所以通常先move，再对move结果求ε-闭包，得到完整的目标状态集合。

我记得初学的时候经常漏掉“先move再闭包”这步，直接拿当前状态集合去算闭包，导致读入一个字符后自动机停在原地，怎么调都不对。后来养成了一个固定习惯：每个输入符号都走两条命令，先move，再closure，缺一不可。

3.2 构造状态转换表的全过程

从NFA的开始状态6出发，计算：

A = ε-closure({6}) = {6, 0, 7, 1, 3, 8}

这里必须特别注意，状态8也被卷进初始闭包了。原因是7可以通过ε到8，而8是后续abb中第一个a的开始状态。很多手算不正确的人，就是在这里漏掉状态8，后面DFA识别abb后缀时会出错。

接着对A分别读入a和b。A中能沿着a转移的状态是1和8，分别到了2和9，所以：

move(A, a) = {2, 9}

计算ε-closure({2, 9})，得到DFA状态B：

B = {2, 5, 0, 1, 3, 7, 8, 9, 10}

读入b时，A中能沿着b转移的状态是3，到4，所以：

C = ε-closure({4}) = {4, 5, 0, 1, 3, 7, 8}

有了A、B、C三个状态后，用BFS的思路继续对每个新状态计算a、b转移。我直接列出完整转换表：

其中：

• D = ε-closure(move(B, b)) = ε-closure({4, 11}) = {4, 5, 0, 1, 3, 7, 8, 11, 12}
• E = ε-closure(move(D, b)) = ε-closure({4, 13}) = {4, 5, 0, 1, 3, 7, 8, 13}

A是开始状态，E包含NFA接受状态13，所以E是DFA的接受状态。

这张表不是猜出来的，每一步都在做“集合搬家”。我强烈建议第一次手算的人把每个集合的详细元素写出来，而不是直接跳到最后结果，否则会漏状态。

3.3 这个DFA还能怎么验证

子集构造法得到的DFA有时候会给人“状态也不少”的错觉。但可以拿几个典型字符串验证一下：

识别abb：

A --a--> B --b--> D --b--> E，接受。

识别aabb：

A --a--> B --a--> B --b--> D --b--> E，接受。

识别bb：

A --b--> C --b--> C，C不是接受状态，拒绝。这完全符合(a|b)*abb的语义，因为bb不以abb结尾。

有时候我还会故意构造一个形如ababaabb的长串，走完整条DFA路径，看最后是否会落到E。这个验证方式简单又有效，比自己盯着状态表空想靠谱得多。

4. DFA等价类最小化：划分算法实操

4.1 为什么刚构造出来的DFA不一定最简

子集构造法生成的DFA状态，本质上是NFA状态集合。NFA里的某些状态虽然在结构上不同，但在DFA中可能表现出完全一致的“未来行为”。比如状态A和状态C，它们各自读入任意长度的字符串后，是否到达接受状态的情况完全相同，那么它们就可以合并。

最小化不是改变DFA的语言，而是去掉冗余状态，让同一个语言用一个更紧凑的自动机表示。从工程角度说，状态越少，转换表越小；放到词法分析器里，就对应着更少的存储和更快的查表。

4.2 基于可区分性的迭代划分

标准的划分算法思路很直白：先把状态分成两个大组——接受状态组和非接受状态组。然后反复检查每个组内部的状态，如果两个状态在读入同一个符号后落到了不同的组，那它们就是“可区分的”，需要拆开。一直拆到每个组内部状态在任意符号下的后继都属于同一个组为止。

我这里的初始划分：

P1 = {非接受组{A, B, C, D}, 接受组{E}}

然后逐组检查。先看非接受组内部，A、B、C、D在输入b后的走向：

• A → C，属于原非接受组
• B → D，属于原非接受组
• C → C，属于原非接受组
• D → E，进入了接受组

所以D和另外三个状态可区分，拆出来：

P2 = {组1{A, C}, 组2{B}, 组3{D}, 组4{E}}

这里的 {A, C} 是经过第二轮检查后，再次从 {A,B,C} 中拆出来的。实际上第二轮我会这样操作：状态A在b上到C，状态B在b上到D，它们的行为不一致，于是把 {A, C} 和 {B} 分开。

继续检查 {A, C} 这个组。A读入a到B，C读入a也到B；A读入b到C，C读入b也到C。两个状态在所有字母下的后继都落在同一个等价类里，无法再区分，于是合并。

最终等价类：

• 组0 = {A, C}
• 组1 = {B}
• 组2 = {D}
• 组3 = {E}

4.3 从划分结果重建最小DFA

用新编号替代原来的DFA状态，我得到最小DFA转换表：

开始状态是0，因为原开始状态A在组0中；接受状态是3，因为原接受状态E在组3中。

用最小化后的DFA再跑一遍abb：

0 --a--> 1 --b--> 2 --b--> 3，接受。

跑一个反例abba：

0 --a--> 1 --b--> 2 --b--> 3 --a--> 1，最终不在接受状态，拒绝。因为字符串以bba结尾，确实不匹配。

最小化前后状态数从5个降到4个，看起来不算夸张，但在实际词法规则里，多个正则式合并后，子集构造法经常产生几十到几百个冗余状态，最小化能压缩到一个非常小的规模。

5. 实操建议与常见问题排查

5.1 手算时最容易栽的几个坑

第一个坑是ε-闭包漏状态。特别是闭包运算的箭头很多，很容易只走一层ε就走人了。破解办法是老老实实用一个队列或栈，每加入一个新状态，就继续检查这个新状态有没有新的ε后继，直到没有为止。

第二个坑是move之后忘记求闭包。NFA上的状态转移经常连着ε路径，直接拿move结果当目标集合，会导致DFA状态缺少原来的等价状态，后续转移就会断裂。

第三个坑是接受状态判断错。一个DFA集合只要包含NFA的接受状态，它就是接受状态；不是要求集合里的所有状态都接受。这个判断我见过不少同学写反。

第四个坑是闭包运算的ε回路。比如(a|b)*中旧接受状态回到旧开始状态，容易在ε-闭包中造成无限循环。写程序时，如果不用visited集合记录，死循环就出现了。

5.2 用代码实现时的数据结构选择

如果只是课程实验，不需要写一个工业级生成器，重点在于思路清晰。我在实现子集构造法时，常用以下几个结构：

• 用dict表示NFA状态转移，键是状态编号，值是一个dict[字符] -> 状态集合，ε转移单独用一个set[int]集合存放。
• 使用frozenset表示DFA状态，因为它可哈希，能直接作为dict的键。每次计算完一个新的状态集合，就去查字典看是否已经存在，不存在就分配新的DFA状态编号。
• 转换表可以用list[dict]保存：下标是DFA状态编号，值是该状态下每个输入字符对应的目标状态编号。

最小化实现时，最稳妥的是先做一次“可区分性”迭代：维护当前划分的等价类列表，对每个等价类，把组内每个状态映射成(该状态在a上的目标组号, 该状态在b上的目标组号)的元组，再按这个元组分组。重复直到不再变化。这个朴素的实现效率不一定最高，但正确性容易保证，做实验应付几万状态也够用。

5.3 在词法分析器里落地时的一些经验

真正写词法分析器时，一般会把多个正则式合并成一个大的正则式，然后统一构造NFA、DFA，再最小化。为什么要合并？因为如果每个关键字、运算符都单独做一台DFA，同时运行多台机器，匹配时的维护成本会很高。合并成一个自动机后，词法分析器每读一个字符只需要做一次状态转移，最后在某个状态上判断当前命中了哪条规则。

这时候有一个容易被忽略的点：处理“最长匹配”和“优先级”。DFA只告诉你当前状态是不是某个token的接受状态，但要实现最长匹配，需要在扫描过程中不断记录最近一个接受的字符位置和对应的token类型。如果多个正则式在同一个接受状态上重叠，通常按定义先后顺序决定优先级。

另外，实际输入字符集远不止a和b，字母表可能有上百个字符。构造转换表时不建议给每个字符都开一列，而应先做字符分类，把行为相同的字符归成一个等价类。这也是为什么真正的生成器里会有“字符区间压缩”这一步。我在做自己的词法分析器时，通常先对字符做离散化，把0到255的字符值映射到更少的类别编号，再构造DFA，这样转换表一下子瘦身很多。

最小化之后，我还建议把DFA导出来，用一些边界用例去测。比如空串、只含一个终止符的串、超长串、正好以目标后缀结尾的串、多一个字符使结果反转的串。这些用例能快速暴露出状态构错、接受状态判断错、最小化分组错等问题。不要等到整个词法分析器跑起来再排查，那样定位问题会非常痛苦。

还有一个经验：手推和写代码时，最好把中间每一步都打出来，尤其是NFA的转移表、子集构造出来的每个DFA集合、最小化时每次划分结果。中间结果一旦输出，哪里出错一目了然。我最早实现时图省事，只打印最终转换表，结果一个状态跳错，前面对后面对不上，最后不得不重新加上调试输出。从那之后我养成了“过程可视化”的习惯，凡是做状态机相关的东西，一定保留中间态打印开关，这比事后猜测高效得多。