企业官网建设流程全解析

做编译原理课设那会儿，我最头疼的不是语法分析，而是词法分析里那个看似不起眼的环节：正规式怎么变成自动机。刚接触正规式（Regular Expression，也就是常说的正则表达式）这个概念时，我总觉得它已经很“程序化”了——不就是一套字符匹配规则吗？可当老师让我把一个正规式手工转换成NFA，再变成DFA，最后写出对应的词法识别程序时，我才发现这条路远比我以为的长，而且坑一个接一个。

这篇文章就围绕这条主线展开：正规式为什么要变成自动机、Thompson构造法怎么把正规式“翻译”成NFA、子集构造法怎么把NFA“确定化”成DFA、DFA最小化怎么做，以及把这些理论落到代码时会遇到的真实问题。我会全程用一个经典正规式 (a|b)*abb 做例子，每一步都手算给你看。不管你是正在准备编译原理考试，还是想搞清楚正则表达式引擎内部原理，或者纯粹想做词法分析器但不想用现成生成器，这篇应该都能帮上忙。

1. 正规式为什么要变成自动机——先搞清楚转换到底解决什么问题

1.1 正规式是给人写的，机器没法直接“运行”它

词法分析的任务很简单：把源代码这个长字符串切成一个个Token，比如关键字、标识符、数字、运算符、括号。而Token的模式天然适合用正规式描述。比如“C语言风格标识符”可以写成[A-Za-z_][A-Za-z0-9_]*，“无符号整数”可以写成[0-9]+。这些正则写出来简洁、直观，人看一眼就明白匹配规则是什么。

问题在于，你把[A-Za-z_][A-Za-z0-9_]*这段字符串交给程序，程序并不知道该怎么执行它。它不像一段C语言代码那样有明确的指令序列。正规式本质上是一个“描述性”的声明，而不是一个“过程式”的算法。要想让计算机自动、高效地识别一个字符串是否符合某个正规式，必须先把正规式编译成另一种东西——一种可以让状态机一步步走起来的数据结构。

1.2 自动机才是能“跑起来”的词法识别模型

有限自动机就是那个“能跑起来”的东西。它由一组状态和带标签的转移边组成。给你一个输入字符串，从初始状态出发，每读一个字符就沿着对应标签的边跳一次，等字符串读完了，如果停在接受状态，就说明这个字符串被接受了。

这个模型最大的好处是简单、机械、可执行。计算机模拟状态转移只需要一张“当前状态 + 当前输入 → 下一个状态”的查找表，循环一遍输入串就能完成匹配。正规式适合人写，自动机适合机器跑，这俩是天然互补的。所以整个转换过程，本质上就是在人和机器之间做一次“翻译”。

编译原理里通常会把这个翻译拆成两步：先把正规式转成NFA（非确定有限自动机），再把NFA转成DFA（确定有限自动机）。中间为什么要插一个NFA？直接一步到位行不行？答案是可以，但很难。NFA允许同一个状态在同一个输入符号下有多个可能的转移，还允许在不消耗输入的情况下跳转（ε边），这让它构造起来非常自由，可以按正规式的递归结构机械地“拼”出来。但正因为它非确定，模拟起来要考虑所有分支，不够高效。DFA则相反，每个状态每个输入最多一个转移，模拟起来是线性的，但直接构造很麻烦。所以标准做法是：先用简单的递归规则生成NFA，再用算法自动转成DFA。

1.3 整条转换链路全貌

我下面这张流程图不画图了，直接用文字描述这条链：

正规式 (a|b)*abb ↓ Thompson构造法 NFA（带ε边，状态多，非确定） ↓ 子集构造法 DFA（确定性，每个输入只有一条路） ↓ DFA最小化 最小化DFA（合并等价状态，状态数更少） ↓ Table-driven 词法分析驱动代码 / 转移表

每一步都有明确的算法，而且都是“机械劳动”为主，不需要拍脑袋。所以学会了流程之后，哪怕给你一个很复杂的正规式，你也只需要按照固定套路一步步来。这也是为什么这个知识点值得认真手算一遍而不是只记结论。

2. Thompson构造法——把正规式“翻译”成NFA图的机械步骤

2.1 四个基础构造模式

Thompson构造法的核心思想是：正规式是由原子和运算符递归组成的，那么我就对每个原子和每种运算符定义一种“拼图”方式，最后按照正规式的语法树自底向上拼接即可。

先约定一下记号：每个NFA片段有一个初始状态和一个接受状态，内部细节我们暂时不关心。任何复杂正规式对应一个NFA片段时，都保持这种“一个入口、一个出口”的接口，这样才能拼装。

第一个模式是单个字符 a。这就是最原始的小图：

初始状态 --a--> 接受状态

没有比这更基础的了。

第二个模式是连接 AB。假设A的NFA片段初始状态为 iA、接受状态为 fA，B的片段是 iB、fB。连接就是把 fA 和 iB 用一条ε边串起来，新初始状态是 iA，新接受状态是 fB。

第三个模式是选择 A|B。从新的初始状态分别发一条ε边到 iA 和 iB，再从 fA 和 fB 分别发一条ε边汇聚到新的接受状态。这样读入一个字符，就可以在A、B两条路径中任选一条走。

第四个模式是闭包 A*。为A的片段添加一个新的初始状态和一个新的接受状态，然后加三条ε边：新初始 ε→ iA（允许进入循环体）、新初始 ε→ 新接受（重点：这表示可以匹配零次，直接退出）、fA ε→ iA（让循环可以重复）、fA ε→ 新接受（循环结束退出）。

这里容易漏掉的是“新初始 ε→ 新接受”这条边。如果漏了，闭包就必须至少匹配一次，不能匹配空串，那和A+就没区别了。我当年手算时在这个地方错过很多次，后来每次构造闭包都会先检查这条边在不在。

2.2 完整示例：构造 (a|b)*abb 的NFA

下面用上面的四条规则手把手把 (a|b)*abb 拆出来。

第一步：构造 a 的子图，设状态为1和2：

1 --a--> 2

第二步：构造 b 的子图，设状态为3和4：

3 --b--> 4

第三步：构造 a|b。新初始状态0，新接受状态5：

0 --ε--> 1 0 --ε--> 3 2 --ε--> 5 4 --ε--> 5

第四步：构造 (a|b)*。新初始状态6，新接受状态7：

6 --ε--> 0 6 --ε--> 7 5 --ε--> 0 5 --ε--> 7

注意这里我特意把“6 ε→7”写上了，它保证闭包可以匹配空串并直接退出。

第五步：为后面的 abb 分别构造 a、b、b 三个小片段。为了避免和前面的状态冲突，我用状态8到13：

8 --a--> 9 10 --b--> 11 12 --b--> 13

把 (a|b)* 的接受状态7和8用ε边连起来，9接10，11接12：

7 --ε--> 8 9 --ε--> 10 11 --ε--> 12

完整拼装后的NFA状态转移如下表。初始状态是6，唯一接受状态是13。

你现在不用急着看懂这张表每一个细节，后面算ε-closure的时候会反复用到它。重要的是体会一件事：Thompson构造法是纯“拼积木”，没有任何智能决策。给定正规式的语法结构，任何人都能按规则机械地拼出等价的NFA。这就是它适合写成程序的原因。

2.3 为什么非用ε不可

你可能会问，这些ε边能不能省掉？比如选择 a|b，直接用“初始状态发a到接受状态；a那条路和b那条路分开”行不行？可以，但那样会让构造规则变得复杂，而且遇到嵌套表达式时很难保持“一个入口、一个出口”的统一接口。

ε边的作用类似汇编语言里的跳转指令。它不消耗输入字符，只负责把控制流从一个片段导到另一个片段。有了它，每一块拼图都能保持接口一致，连接、选择、闭包都能用固定模式完成。代价是NFA里会出现很多空跳转，状态数膨胀，执行时还要不断查看ε闭包。不过这个代价是值得的，因为后面的子集构造法会自动把这些空跳转消化掉。

实际动手的时候，ε边也是最容易出错的地方。我的建议是：每拼装完一个子表达式，就在纸上把这一小块的初始状态、接受状态标出来，画好后再看下一个运算符，不要等到整体画完再检查。画完整体NFA之后，再沿着几条典型输入串（比如空串、abb、aabb、ababb）从初始状态到接受状态走一遍，能走通就基本没问题。

3. 子集构造法——NFA的“确定性化”到底怎么算

3.1 ε-closure与move：两个必须吃透的操作

NFA变成DFA的算法叫子集构造法，它的思想很深刻：把NFA的“多个可能状态”打包成DFA的一个状态。一个DFA状态不是一个点，而是一组NFA状态；只要这组里有任何一个NFA状态可能被下一步到达，DFA都把这个能力记下来。

实现子集构造法只需要两个基本操作：

ε-closure(S)：从NFA状态集合S出发，沿着ε边反复走，能到达的所有状态的集合。简单说就是把“不消耗输入就能一口气跳过去”的状态全收进来。

move(S, c)：从S集合中的某个状态出发，读入字符c能一步到达的所有状态的集合。注意这里只走一步，不看ε边。

ε-closure的实现本质上是图上的可达性问题，用BFS或者DFS都能做。递归写起来最直观，但状态多的时候容易踩重复加入和递归深度的问题。我更推荐用栈写迭代版本：

def epsilon_closure(state_set, eps_table): result = set(state_set) stack = list(state_set) while stack: s = stack.pop() for nxt in eps_table.get(s, []): if nxt not in result: result.add(nxt) stack.append(nxt) return result

这里eps_table是状态到其所有ε转移目标状态的映射。迭代版本的好处是天然避免重复处理，只要一个状态被加入过result，就不会再次被推进栈里，不会死循环。

3.2 逐步子集构造：从A到E

现在对 (a|b)*abb 的NFA做子集构造。

第一步，计算初始状态的ε-closure。初始状态是6：

ε-closure({6})

从6出发，ε能到0和7；从0又能ε到1和3；从7又能ε到8。所以：

A = {6, 0, 1, 3, 7, 8}

这就是DFA的初始状态。注意它里面包含了7和8，这说明它真的可以一步都不消耗就直接进入后面的abb子图。

第二步，对A分别看输入a和b。

先看a。A里哪个状态有a转移？1有1 --a--> 2，8有8 --a--> 9。所以 move(A, a) = {2, 9}。再对这个集合求ε-closure：

2 ε→ 5，5 ε→ 0和7，0 ε→ 1和3，7 ε→ 8 9 ε→ 10

收集起来得到：

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

再看b。A里哪个状态有b转移？3有3 --b--> 4。所以 move(A, b) = {4}，紧接着求ε-closure：

4 ε→ 5，5 ε→ 0和7，0 ε→ 1和3，7 ε→ 8

得到：

C = {0, 1, 3, 4, 5, 7, 8}

我用同样的方法把剩下的状态全部算出来。这里为了节省篇幅，直接把每次的move集合和最终结果列成一张表：

判断一个DFA状态是不是接受状态，就看它对应的NFA状态集合里有没有包含NFA的接受状态13。上表里只有E包含13，所以E是DFA的唯一接受状态。表格填满、所有状态的两个输入转移都有归属之后，子集构造就结束了。

提醒一句：实际算的时候，每产生一个新集合，一定要立刻检查它是否已经和之前某个DFA状态相同。集合相等和元素顺序无关，检查的时候要把集合排序或者用哈希集合表示，否则很容易把同一个状态算两次，让DFA白白多出冗余状态。

3.3 得到的DFA与一个直观理解

把上面这张表当DFA转移图来读：

• A读到a去B，读到b去C；
• B遇到a原地自转，遇到b去D；
• C遇到a去B，遇到b原地不动；
• D遇到a回B，遇到b去E（接受）；
• E遇到a回B，遇到b回C。

为什么B遇到a会自转？因为B集合里同时包含1、8这些能产生a的NFA状态和它们经过ε闭包所能到达的所有后续状态。算出来是什么就是什么，不用硬找直观意义。但如果你非要找个说法，可以这么理解：每走一个字符，DFA就把“所有NFA可能处在的位置”整体挪动一次。B这个位置表示“NFA此时有可能正在闭包内部循环，也有可能已经走到abb的途中”，所以a一进来它会继续保持这种可能。

这个例子还有个小特点：任意输入串都不会让DFA彻底没路可走，因为前缀(a|b)*本身就能消化任意字符序列。所以这里没有出现“死状态”。但换一个正规式，比如ab*，如果输入串里突然出现c，DFA就会面临“没有对应转移”的处境。实际写词法分析器时，这种情况一定要显式处理——要么在转移表里预留一个错误状态，要么在查表时判断键不存在直接报错。

4. DFA最小化——把重复劳动的等价状态砍掉

4.1 等价状态是怎么定义的

子集构造法生成的DFA往往不是最精简的，里面可能有一批行为完全相同的状态。比如上一步的结果里C和E就有相似之处：C读a去B、读b回C；E读a去B、读b回C。看上去就差“E是接受状态，C不是”这一点，但正是这一点让它们不能合并。

两个状态等价的意思是：以后无论喂什么输入串，它们要么同时接受，要么同时拒绝，行为一模一样。反过来说，只要存在一个输入串能让一个状态走到接受状态、另一个状态走到非接受状态，这两个状态就是可区分的，绝对不能合并。

这个等价关系可以一层层划分出来。最粗糙的划分是“接受状态组”和“非接受状态组”，然后不断细化：如果组内两个状态在某个输入符号上跳去了不同的组，那它们必须被拆开。重复这个过程直到任何组的内部都不再分裂。

4.2 划分法手算全过程

我对上面5状态的DFA（A、B、C、D、E，E为接受状态）做一遍划分。

初始划分：

P0 = { {A, B, C, D}, {E} }

第一轮检查非接受组 {A,B,C,D} 里的每个状态在a、b上分别跳去哪一组：

• A读a去B（本组内），读b去C（本组内）；
• B读a去B（本组内），读b去D（本组内）；
• C读a去B（本组内），读b去C（本组内）；
• D读a去B（本组内），读b去E（接受组）。

D的b转移去了接受组，其他人没有，所以D必须从 {A,B,C,D} 里拆出来。得到：

P1 = { {A, B, C}, {D}, {E} }

第二轮检查 {A,B,C}：

• A读a去B（本组内），读b去C（本组内）；
• B读a去B（本组内），读b去D（{D}组）；
• C读a去B（本组内），读b去C（本组内）。

B的b转移去了 {D} 组，A和C的b转移还在组内，所以B拆出去。得到：

P2 = { {A, C}, {B}, {D}, {E} }

第三轮检查 {A,C}：

• A读a去B（{B}组），读b去C（本组内）；
• C读a去B（{B}组），读b去C（本组内）。

两者的行为完全一致，不再拆分。划分稳定：

P3 = { {A, C}, {B}, {D}, {E} }

A和C可以合并成同一个DFA状态。合并后的最小化DFA转移表如下：

从5个状态压到了4个状态。你可能会觉得只是少了一个状态，意义不大。但如果处理的是几十个状态的手写词法分析器，最小化能显著缩小查表空间，也能让最终状态图清晰得多。对考试来说，划分数轮直到稳定这个流程必须写得完整。

4.3 用测试串验证最小化DFA

最小化之后至少要拿几个典型串验证一遍，确认合并行为真的没改变语言。

先测abb。这是闭包部分匹配空串、直接进入abb尾串的最简单情况：

AC --a--> B --b--> D --b--> E（接受）

再测babb。闭包部分先吃掉一个b，再匹配尾串abb：

AC --b--> AC --a--> B --b--> D --b--> E（接受）

再测一个反例abab。它不以abb结尾，应该被拒绝：

AC --a--> B --b--> D --a--> B --b--> D

D不是接受状态，拒绝。

三个测试串结果都符合预期，说明最小化没有破坏DFA的识别能力。这里特别建议你也拿一个本来会被拒绝、但容易误判成接受的串（比如aabb你验证一下，它是能被接受的，因为aabb整体以abb结尾；要找反例就找不以abb结尾的）好好走一遍，比只测正向用例更能发现合并错误。

5. 实战落地：从DFA到词法分析器和踩坑记录

5.1 三种把DFA变成代码的方式

有了最小化DFA，就可以写词法分析了。实现方式有三种常见选择。

第一种是写if-else嵌套。对于状态很少的DFA，直接在代码里层层嵌套判断也可以。优点是没有额外的表结构，缺点是一旦token模型复杂，代码会膨胀得一塌糊涂，而且很难维护。我不建议用这种，除非你的DFA不超过五六个状态且不会变动。

第二种是二维转移表。用state和input_char两个维度查表，状态转移写成一张表结构。这是最通用也最好维护的做法。上面最小化DFA可以写成这样：

transition = { "AC": {"a": "B", "b": "AC"}, "B": {"a": "B", "b": "D"}, "D": {"a": "B", "b": "E"}, "E": {"a": "B", "b": "AC"}, } accepting = {"E"} start = "AC" def recognize(word): state = start for ch in word: if ch not in transition[state]: return False state = transition[state][ch] return state in accepting

第三种是循环驱动+状态编号，用整数编号代替字符串状态名，配上switch或查表。这个方案在编译原理的词法分析实验里很常见，因为最终要从一个C语言程序里读源代码，而不是把单个单词喂进函数。

我个人的习惯是：先写一份Python脚本把正规式到最小化DFA的整条链路跑通，再根据需要把转移表翻译成目标语言的查表结构。转移表本身是纯粹的数据，翻译过去不涉及算法改动，非常稳。

5.2 最长匹配与token优先级

真正做词法分析器时，光会识别一个正规式还不够，因为一个词法分析器要同时识别几十种token。常见做法是给每个token模式一个编号，让DFA的接受状态记录它对应哪个token。但这时候会出现两个经典问题。

第一个是“最长匹配”。比如你要同时识别关键字if和标识符，输入串是ifx。DFA走到if两个字符后已经到达接受状态，如果这时候立刻返回“识别到关键字if”，那就错了，因为后面还接着字母x，应该继续读下去，最后按标识符处理。解决方法是每到一个接受状态就记录“当前位置 + token编号”，一旦后续字符让DFA无路可走，就回退到最近一次记录的位置返回结果。

第二个是“优先级”。如果输入串同时匹配多个token模式（比如=可能同时是单独等号和==的前缀），不同的模式可能在不同的接受位置结束。编译原理的处理办法是多个DFA并行跑，取最早到达、且匹配长度最长的那个结果。如果你的实现里把所有正规式合并成一个大NFA再转DFA，那么每个DFA接受状态要保存对应的token编号列表，并从中按优先级挑一个。这些细节不到写代码时会踩到，但踩过就记住了。

5.3 手算与调试的经验

最后分享几条实操经验，都是我自己在写和调试过程中真正吃过亏的地方。

第一，计算ε-closure时，一定要用“已访问集合”而不是只靠递归栈。我当时有个版本只靠栈去重，结果同一个状态出现在另一条分支时被重复推入，导致计算结果死循环。改成if nxt not in result判断之后再入栈就稳定了。

第二，手算子集构造时，每产生一个新DFA状态，立刻用“有序元素列表”的方式记录下来，比如[0,1,3,5,7,8]这样的顺序，方便和后续新集合做比较。我见过不少同学把所有集合写在一张纸上，最后因为集合A和集合E长得太像而抄错转移。把“ABCDE”编好号，每个状态占一行，填完一行就检查一行，能省掉大量返工。

第三，从DFA转代码时，不要忘了处理“无路可走”的分支。表中看起来所有状态都有a、b转移，是因为(a|b)*abb这个表达式的前缀部分能吸收任意字符。如果换一个正规式，比如ab*，遇到c就会查表失败。词法分析器遇到这种情况要能报“非法字符/无法匹配”，不能直接抛一个裸异常。

第四，调试DFA的时候，只测几个典型正向串是不够的。我常用的做法是写一个小脚本枚举所有长度不超过N的0-1串（在本例字母表是a、b，那就枚举a和b组成的串）分别喂给原始NFA模拟器和最小化DFA模拟器做输出比对。两边结果完全一致，才能说明合并没有出问题。这一步虽然土，但极其有效。一个用原始NFA模拟器做“标准答案”的想法非常实用，因为NFA和DFA理论上等价，如果两边结果不一致，要么子集构造错了，要么最小化错了，立刻就能定位到是哪一步的问题。

整条链路走完之后回头看，正规式转自动机并没有哪一步依赖灵感，全部是确定性的算法操作。Thompson构造法负责搭骨架，子集构造法负责把不确定性压缩成确定性，最小化负责消除重复劳动。真正容易翻车的不是理论，而是手算的细心程度和代码里对边界的处理。把这些养成本能，后面学语法分析会更轻松。