企业官网建设流程全解析

做编译原理相关的项目或者正在啃词法分析这块的朋友，应该都绕不开“正规式转化自动机”这个坎。这期内容是我在整理编译原理系列笔记时的第六篇，也是我自己当时花了最多时间去“悟”的一篇。别看教材上就那么几页纸，真正动手去画NFA、去理解那个递归构造过程的时候，才会意识到这里面有多少细节值得抠。

这篇博文不打算泛泛地讲理论，而是直接把正规式转自动机的核心思路、手工实操步骤和那些教材里不会明说的坑，一次性给你捋清楚。无论你是正在准备考试的学生，还是在做词法分析器、正则表达式引擎相关工作的开发者，这篇文章都能帮你把这块硬骨头啃下来。

1. 核心思路拆解：正规式为什么非得变成自动机

1.1 从“描述语言”到“识别语言”的鸿沟

正规式（也叫正则表达式）本质上是一种声明式的描述，它告诉你“什么样的字符串序列是合法的”。比如(a|b)*abb这个正规式，它描述的是“由a和b组成、且以abb结尾的字符串集合”。但问题在于，计算机要“识别”一个字符串是否匹配这个模式，不能光靠人类去读这个式子，它需要一套机械化的执行步骤。

自动机（有限自动机）恰恰就是这套机械化步骤的载体。它是一个带有有限状态和转移边的图，从起始状态出发，沿着输入字符的指引一步步走下去，如果最终停在接受状态，就说明这个字符串被接受了。所以，正规式转自动机的本质，是把“描述语言”的静态规则，翻译成“识别语言”的动态过程。

这个过程在编译原理里至关重要，因为词法分析器（Lexer）干的就是这件事。你在写代码时用的那些关键字识别、标识符匹配、数字常量判断，背后都是一堆自动机在跑。

1.2 NFA与DFA：两条路线怎么选

自动机分两种：不确定有限自动机（NFA）和确定有限自动机（DFA）。

NFA的特点是，同一个状态下、同一个输入字符可能转移到多个状态，而且存在空串转移（ε转移），也就是不读入任何字符也能跳转。DFA则严格得多，每个状态下、每个输入字符有且只有一个确定的转移方向。

既然最终执行的时候DFA更高效（不需要回溯，不需要维护多个可能状态的集合），为什么不直接正规式转DFA？原因是：直接从正规式构造DFA，没有一套简单、机械、可递归的规则，而NFA的构造有一整套非常漂亮的归纳构造法（Thompson构造法）。所以路线变成了：正规式 → NFA → （子集构造法）→ DFA → （最小化）→ 最简DFA。

这个“先绕一步”的路线，表面上多了一步，实际上每一步都有严格算法保证，工程上完全可自动化。很多编译器教材和lex/flex这类工具都是这么干的。

1.3 理解Thompson构造法的核心价值

Thompson构造法（也叫McNaughton-Yamada-Thompson算法）是1968年提出的，是正规式转NFA最经典的方法。它的核心思想是分治+递归：把复杂的正规式拆成原子操作，每种操作都有对应的图构造模板，然后像搭积木一样拼接起来。

我当时学的时候觉得它像乐高：每种积木（空串、字符、连接、选择、闭包）都有固定的拼法，整个正规式就是这些积木按照树形语法结构组合起来的。只要你会递归分解，就能机械地画出NFA，而且每个步骤都有唯一的标准做法，不存在“自由发挥”的空间。

这套方法的工程价值在于它能被代码化。你可以写一个递归函数，输入是正规式的语法树节点，输出是对应的NFA片段，完全遵循固定的局部构造规则，全局拼装自动完成。这就是为什么几乎所有词法分析器生成器内部都采用这个方案的底层原因。

2. 构造规则拆解：五类基本操作的转换

2.1 空串与单字符：最小的积木单元

Thompson构造法的基础积木有两块：空串ε对应的NFA和单字符对应的NFA。

空串ε对应的NFA非常简单：一个起始状态、一个接受状态，一条从起始指向接受的ε转移边。用图表示就是：

start --ε--> accept

单字符a对应的NFA稍微多一点：同样是一个起始状态和一个接受状态，但转移边上的标签是字符a本身：

start --a--> accept

这两块积木虽然简单，但它们是整个构造过程的基石。任何复杂的正规式，最终都会被分解到原子级别，所以这两块积木会反复出现。画图的时候我建议把起始状态用一个箭头（无来源的箭头）标识出来，接受状态用双圆圈标识，熟练了以后一眼就能看出整个自动机的关键节点。

理论上也可以让空串的NFA和单字符的NFA在局部细节上做一些合并，但不要这么做。保持每个操作对应的子图边界清晰，后续拼接和验证时才不会乱。

2.2 连接操作：像拼管道一样拼接

两个正规式r和s的连接（rs），表示先匹配r再匹配s。构造方式很直观：把r的NFA和s的NFA串联起来，让r的接受状态作为s的起始状态的前驱，用一条ε转移边把两者连起来。

具体规则是：r的NFA的接受状态不再作为最终接受状态，而是通过ε边连到s的NFA的起始状态；整个组合的起始状态是r的起始状态，接受状态是s的接受状态。

为什么用ε边而不是直接合并状态？因为这两个子NFA内部可能会有自己独立的空转移内部结构，直接合并会破坏子图封闭性。用ε边连接，从形式上保持了“组合”的清晰边界，而且后续做子集构造时，ε-closure（ε闭包）的计算可以统一处理这些空转移。

实际操作中我第一次画连接操作的时候，老想着把r的接受状态和s的起始状态合并成一个状态，省一条边。后来发现这样容易出错，尤其在处理长连接链的时候，中间某个状态的身份（既是前一个的接受，又是后一个的起始）会混淆。还是老老实实加ε边，结构最清晰。

2.3 选择操作：分支的引入

正规式r|s表示匹配r或匹配s任意一个。构造方式是并联：新设一个起始状态和一个接受状态，把r和s的NFA分别挂在起始状态和接受状态之间。

具体规则：新的起始状态通过ε边分别指向r的起始状态和s的起始状态；r的接受状态和s的接受状态分别通过ε边指向新的接受状态。整个组合的起始状态是新建的起始状态，接受状态是新建的接受状态。

这里有个容易忽略的细节：r和s原来的接受状态在这个组合里不再是整个组合的接受状态了，它们只是中间节点。所以当你递归构造的时候，必须清楚当前这一层组合的接受状态是谁，不能拿子表达式的接受状态当整层的接受状态用。

我在手工画选择结构的时候，习惯把两个分支画得上下对齐，这样视觉上很对称，检查有没有漏边也很方便。并且两个分支的ε边都必须存在，缺一条就会漏掉一种匹配可能。

2.4 闭包操作：循环的引入

闭包（r*）表示r重复零次或多次。构造方式是围绕r的NFA加一个“回环”结构。

具体规则：新设一个起始状态和一个接受状态；新的起始状态通过ε边指向r的起始状态，同时直接通过ε边指向新的接受状态（这对应“零次”的情况）；r的接受状态通过ε边指向新的接受状态（对应“一次”的情况），同时通过ε边指回r的起始状态（对应“多次”的情况，形成循环）。

等待，这里有一个容易混淆的边界问题。r和r+的区别在于：r允许“零次”，所以必须有从起始状态直接到接受状态的ε路径；r+要求至少一次，所以这个“零次路径”不需要存在。很多书上的闭包模板看起来差不多，但“新起始状态到新接受状态的直接ε边”这个细节，恰恰是决定“零次是否允许”的关键。

每次画闭包我都习惯数一遍：新起始状态有几条出边？r的接受状态有几条出边？正确答案是各两条（新起始到r起始、新起始到新接受；r接受回r起始、r接受到新接受）。这不只是一个方便检查的技巧，它更是一种工程思维的体现：为每个关键状态列出“状态转移表”，比盯着图看更不容易漏。

2.5 组合示例：从一个完整式子看整体构造

光看规则可能觉得抽象，我们用一个经典例子完整走一遍。目标是构造正规式(a|b)*abb的NFA。

第一步：分解结构。这是连接操作，由三部分组成：(a|b)*、a、b、b（准确说是四段：(a|b)*拼接a拼接b拼接b）。

第二步：构造基础单元。分别为a和b构造单字符NFA，每个有两个状态。

第三步：构造(a|b)。这是选择操作，把a的NFA和b的NFA并联到新的起始状态和接受状态之间。

第四步：对(a|b)整体应用闭包操作。在(a|b)的NFA外面加新的起始、接受状态，加上四条ε边。

第五步：把这个闭包NFA和三个单字符NFA依次用ε边串联。

这样整个NFA的最终结构是：起始状态→ε→(闭包子图)→ε→a子图→ε→b子图→ε→b子图→接受状态。

画完之后我习惯标注每一个状态，比如S0、S1、S2……这样后续检查转移边和算ε闭包的时候会很高效。一个常见的错误是，闭包子图中(a|b)的接受状态被后续连接操作改成了中间节点，如果你还在把旧接受状态当整体接受状态来画，后面必乱。

3. 实操过程详解：从正规式到NFA的手工转换全流程

3.1 手工转换前的准备：优先级分析

拿到一个正规式，第一步不是急着画图，而是先做语法分析，把整个式子的结构层次理清楚。正规式的运算优先级从高到低依次是：闭包（*）> 连接（隐式，比如ab表示a连接b）> 选择（|）。

优先级分析决定了一棵语法树。比如a|b*的实际结构是a|(b*)，而不是(a|b)*，因为闭包的优先级高于选择。同理ab*是a(b*)而不是(ab)*。

我建议在草稿纸上先把语法树画出来，树根是优先级最低的运算（通常是连接或选择），叶子是字符。这一步是后续所有构造的地基，语法树画错了，后面全白做。

以(a|b)*abb为例，语法树是：

(连接) / | | \ 闭包 a b b | (选择) / \ a b

注意连接是“左结合”还是“右结合”实际上并不影响NFA的最终语言识别能力，因为连接操作满足结合律。但为了递归程序实现的统一性，建议统一按左结合处理。

3.2 按语法树自底向上构造

语法树画好之后，构造过程就是自底向上的。每个叶子节点对应一个基础NFA，然后按照语法树的结构，将子NFA逐步合成父NFA。

操作细节：

• 叶子节点：为每个字符a构造两状态一转移边的NFA，为ε构造两状态一条ε边的NFA。
• 选择节点：拿到两个子NFA，新建两个状态，按选择模板连接。
• 连接节点：将两个子NFA串联，用ε边把前者的接受状态连到后者的起始状态。
• 闭包节点：拿到子NFA，新建两个状态，按闭包模板添加四条ε边。

这里有一个非常重要的实操经验：每合成一个节点，都把当前得到的NFA的“起始状态编号”和“接受状态编号”记下来。因为父节点拼接时需要用到子节点的这两个端口，如果不记录，回头翻图找状态很浪费时间，而且在递归代码实现中，函数的返回值就是这两个信息。

还有一个细节是状态的编号问题。手工画图时，每新建一个状态就按顺序编号，编号越乱后面越难看，建议统一从左到右、从上到下地分配编号，这样图面上状态的位置也大致有序。

3.3 编写递归构造代码的过程

如果你不是手工画，而是想用代码来实现正规式转NFA，我建议按照递归下降的思路来写。首先定义状态结构：

class State: def __init__(self, is_accept=False): self.is_accept = is_accept self.transitions = [] # 列表，元素为 (字符或None, 目标状态) def char_nfa(ch): start = State() accept = State(is_accept=True) start.transitions.append((ch, accept)) return start, accept def concat_nfa(nfa1, nfa2): start1, accept1 = nfa1 start2, accept2 = nfa2 accept1.is_accept = False accept1.transitions.append((None, start2)) # None 代表 ε return start1, accept2 def union_nfa(nfa1, nfa2): start1, accept1 = nfa1 start2, accept2 = nfa2 start = State() accept = State(is_accept=True) start.transitions.append((None, start1)) start.transitions.append((None, start2)) accept1.is_accept = False accept2.is_accept = False accept1.transitions.append((None, accept)) accept2.transitions.append((None, accept)) return start, accept def star_nfa(nfa): start1, accept1 = nfa start = State() accept = State(is_accept=True) start.transitions.append((None, start1)) start.transitions.append((None, accept)) # 零次 accept1.is_accept = False accept1.transitions.append((None, accept)) # 一次 accept1.transitions.append((None, start1)) # 多次 return start, accept

这个代码里的关键点在于每个操作都返回“起始状态”和“接受状态”两个句柄，并且把子NFA的接受状态修正为普通状态（is_accept = False）。

有一个非常值得注意的Bug：在union_nfa里，如果两个子NFA是同一个对象引用（比如a|a这种表达式），直接修改accept1.is_accept = False会影响第二次使用时的判断。实际操作中需要做深拷贝，或者构造时保证每个叶子节点都是全新的State对象。这也是我在写代码时踩过的一个坑，你以为传入的是两个独立的NFA，实际上它们共享了子图。

3.4 构造完成后的验证与自检

构造完成后最重要的一步是验证。我常用一个简单有效的方法：对几个典型字符串做路径模拟。

比如对(a|b)*abb构造出的NFA，我至少要检查三类字符串：

• 应该被接受的：abb、aabb、bababb、bbabb
• 不应该被接受的：ab、abba、aab

检查方法是从起始状态开始，沿着输入字符的ε闭包一直走到输入结束，看是否存在一条路径到达接受状态。

手工检查时可以先算ε闭包，把所有能通过空转移到达的状态算出来，然后模拟读入第一个字符，看哪些转移是可行的。这是一个相对耗时的过程，但它能立刻暴露出构造中的错误。

我还教一个更快的自检法：检查NFA的“骨架”。(a|b)*abb的NFA应该可以看出明显的三段式结构，先是一个循环选择区，再是一条直线区。如果整个NFA画出来没有这种局部特征，那多半在哪里拼错了。

更正规的验证方式是写一个NFA模拟器，输入一个字符串，输出是否接受。这个模拟器本身也不复杂，核心就是不断计算ε闭包和字符转移。如果你在写编译器相关的项目，这个模拟器后续做DFA模拟时还能复用，不亏。

4. 常见问题与避坑经验

4.1 优先级处理出错导致结构不对

初学阶段最容易犯的错误就是忽略优先级。ab|c和a(b|c)是两个截然不同的正规式，前者是(ab)|c，结构上是一个选择节点，两个分支分别是连接节点和字符节点；后者是一个连接节点，左子树是字符a，右子树是选择节点。

如何避免？强制自己在草稿纸上写出带括号的完全展开形式，哪怕原式省略了括号。比如ab|c先改写成(ab)|c，a|b*改写成a|(b*)，ab*改写成a(b*)。这个过程看起来很机械，但特别能避免结构判断错误。

还有一个经验：如果你在用lex或flex这类工具，正规式的优先级规则可能和编译原理教材不完全一样，工具通常有自己的一套扩展语法（如贪婪匹配、锚点等），写之前查一下工具的优先级说明，别把教材规则硬套到工具上。

4.2 ε边过多导致后续子集构造效率低

Thompson构造法产生的NFA有个显著特点：ε边特别多，状态也特别多。虽然NFA正确性没有问题，但后续子集构造时ε闭包的计算会变得很重，浪费计算资源。

业界常见的优化方案是对NFA做化简：合并一些等价状态、删除多余ε转移。不过这个化简本身也需要额外算法，常见的是先做ε闭包计算，再进行状态合并。如果你只是验证算法正确性，直接做子集构造也行；如果做性能敏感的词法分析器，建议还是加一步化简。

我的个人建议是：先保证正确实现，再考虑优化。一开始就用各种花哨优化，容易把自己绕晕。

4.3 单独正规式转NFA不等于词法分析器

有人做完正规式到NFA的转换后，觉得词法分析器就快完成了，其实还差得远。完整的词法分析器需要处理多个正规式的合并匹配（比如关键字和标识符的正规式有重叠部分），确定最终接受的“最长匹配”“优先匹配”规则，还需要从NFA转DFA、DFA最小化，最终输出一个状态转移表驱动的主循环。

所以如果你在做一个词法分析器生成器，正规式转NFA只是中段步骤，后面还有子集构造、Hopcroft最小化（或Moore最小化）、表驱动模拟器等环节。但所有这些环节都依赖于一个正确的NFA，所以这一步的细节值得认真打磨。

4.4 正则引擎的实现路径差异

学习正规式转自动机，最直接的应用就是自己写一个正则引擎。但要明白工程领域有另一条路线：回溯式引擎（如多数脚本语言内置的正则实现），它不需要转DFA，而是对NFA做带回溯的深度优先搜索。回溯式实现起来简单得多，但存在灾难性回溯的潜在风险。而Thompson式构造+DFA模拟的路线是线性时间复杂度，不存在这种问题。

我个人的学习路线是：先用Thompson构造法实现一版NFA模拟器，理解经典的自动机理论；然后有时间再研究回溯式引擎的优化手段，比如缓存、字符类加速、锚点优化等。理论路线能帮你建立清晰的自动机观，回溯路线能帮你理解日常工程工具的行为特征。

5. 我个人的实操体会

做了这么多遍正规式到自动机的转换，我最大的体会是：这些规则一定要动手画，光看不练等于白学。看教材上Thompson构造法的图觉得很简单，等你真的拿一个复杂的正规式自己画，才会发现优先级分析、端口记录、接受状态修正这些细节，哪一个都不能偷懒。

还有一个很实用的习惯：画完以后，用不同的彩色笔标注“哪些状态是中间状态、哪些是接受状态、哪些是起始状态”，然后再用ε闭包的思路跑一遍例子字符串。这个方法虽然原始，但对于建立自动机的直觉非常有帮助。

我最想提醒的还是编码实现时的那几个坑：共享子图引用问题、子NFA被父操作“污染”的情况（修改了is_accept后不可逆）、闭包里零次路径遗漏等。如果你正在写一个NFA构造库，建议先写单元测试，把每个构造函数的输入输出都测到位，比最后再统统调试省心得多。

正规式转化自动机这个主题，在编译原理里算一个分水岭。跨过这道坎，词法分析、语法分析甚至更后面的代码生成，很多概念都能串起来了。希望这篇笔记能帮你少走一些弯路，要是卡住了，拿着自己的NFA图对着教程模板挨个检查，总能找到问题的源头。