企业官网建设流程全解析

如果你也曾经在搜索引擎里输入过“龙书第三章作业答案”这几个字，别不好意思，我当年也是这么过来的。编译原理这门课，龙书（Aho 那本《编译原理》）是绕不过去的经典，而第三章词法分析又是全书的第一道硬坎。作业里那些正则表达式、NFA、DFA、最小化，看着每个字都认识，组合在一起就变成“我是谁、我在哪、这个状态为什么非要这么画”。这篇文章不是单纯把答案甩给你，而是把答案背后的推导过程、作业里常见的坑、考试爱考的题型一起讲清楚。不管你是正在赶作业、准备期中期末，还是考研复试要复习编译原理，这一篇都能帮你少走不少弯路。

1. 先把第三章的“考点地图”摊开

1.1 第三章到底在讲什么

词法分析器要做的事情一句话就能说清楚：把源代码字符串拆成一个一个有意义的“词”，也就是 token。比如int a = 10;会被拆成关键字int、标识符a、运算符=、数字10和分号;。问题是，计算机怎么知道“a”是个标识符，“10”是个数字？答案就是这一章的主角：正则表达式和有穷自动机。

整章的推导链条非常清晰，几乎是环环相扣的：

• 先用正则表达式描述每个 token 的模式，比如标识符可以写成[a-zA-Z_][a-zA-Z0-9_]*；
• 正则表达式是一种给人看的描述方式，计算机要识别它，得把它转换成有穷自动机；
• 转换过程是“正则表达式 → NFA（不确定有穷自动机）→ DFA（确定有穷自动机）→ 最小化 DFA”；
• 最后把 DFA 变成一张转移表，交给词法分析器去查表执行。

作业题基本就是围绕这条链来的：给你一个自然语言描述的语言，让你写正则；给你正则，让你构造 NFA；给你 NFA，让你用子集构造法转 DFA；给你 DFA，让你最小化。看起来题型多，其实练熟了就是一套固定流程。

1.2 作业最常见的三类题型

我批改过不少次作业，也翻过好几届学生的常见错误，第三章的作业题翻来覆去就三类。

第一类是正则表达式构造题。题目给你一段自然语言描述，比如“所有以 0 开头、以 1 结尾的二进制串”，让你写出对应的正则表达式。这种题考察的不是语法，而是你能不能把自然语言里的边界条件想清楚：空串算不算？单个字符算不算？开头和结尾的约束怎么表示？

第二类是自动机构造题。包括用 Thompson 构造法从正则表达式构造 NFA，再用子集构造法把 NFA 转成 DFA。这种题步骤性强，只要掌握套路就能拿分，但很多人栽在 ε 闭包没求全、状态集合算错这类细节上。

第三类是 DFA 最小化题。题目会给你一个看起来挺规整的 DFA，让你合并等价状态。这种题表面上考算法，实际上考的是对“可区分状态”这个概念的理解。如果只背步骤不理解原理，稍微变一变状态命名就懵了。

把这三类题吃透，第三章作业基本就稳了。下面我一个一个拆开讲。

2. 典型作业题解法拆解：从正则到自动机

2.1 正则表达式构造题：先给语言“画边界”

很多同学看到正则表达式题就急着动笔写符号，结果写出来的表达式要么多匹配了、要么漏匹配了。我的经验是，动笔之前先用大白话把语言描述清楚，尤其是把边界条件列出来。比如“以 1 开头、以 0 结尾的 0/1 串”，先想清楚：这个语言里最短的串是10，长度为 2；空串不算；单个字符也不能算。那么表达式就很好写了：

1(0|1)*0

意思是首字符必须 1，末尾必须 0，中间可以是任意 0/1 串。注意千万不要写成1(0|1)0，那就把长度固定成 3 了。

再看一个经典的“不含连续两个 1 的 0/1 串”。这个题的难点在于，怎么表达“两个 1 不能挨着”。一个巧妙的做法是把串拆成若干个以 0 结尾的块：每个块要么是0，要么是10，这样每出现一个 1，后面必定跟一个 0 来和下一个 1 隔开。最后如果串尾还多了一个孤立的 1，那就用可选的1?来接住。所以答案是：

(0|10)*1?

我来验证几个串：01101包含连续的11，表达式匹配不了；01010可以拆成0 10 10，能匹配；1010可以拆成10 10，能匹配；01能匹配吗？取(0|10)*的一个0，再用末尾的1，刚好组成01，能匹配。这个表达式看起来简单，但包含了“块”的划分思想，理解它对后面学自动机很有帮助。

还有一个龙书课后题里非常著名的类型：写 C 语言注释/* ... */的正则表达式。这里的关键是中间的内容不能包含*/这个结束标记。常见的错误答案是/\*.*\*/，它会在贪婪匹配下把第一个/*和最后一个*/之间的所有内容都吞掉，一旦注释里有多个*/就会出现匹配错误。严谨写法是这样的：

\/\*([^*]|\*+[^*/])*\*+\/

拆开看：\/\*匹配开头的/*；([^*]|\*+[^*/])*表示中间要么是普通非*字符，要么是一串*后面跟着一个既不是*也不是/的字符；最后\*+\/匹配结尾的若干个*加一个/。这个表达式虽然繁琐，但能把“注释内容不能提前碰到*/”这个语义精确表达出来。作业里如果能写出这种级别，老师一眼就知道你是真懂了。

2.2 Thompson构造法：正则到NFA的标准手艺

从正则表达式构造 NFA，作业里要求的标准方法是 Thompson 构造法。它的核心思想是：每个正则表达式子结构都对应一个“单开始状态、单接受状态”的小 NFA，再用 ε 边把小 NFA 拼起来。这样做出来的 NFA 状态多、ε 边多，但结构非常规整，机器也好处理。

最基本的规则有四个。单个字符 a，直接构造一个从状态 p 到状态 q、边标记为 a 的 NFA。并运算R1|R2，新建一个开始状态，用 ε 边分别连到 R1 和 R2 的开始状态，再让 R1 和 R2 的接受状态分别用 ε 边连到一个新的接受状态。连接运算R1R2，把 R1 的接受状态和 R2 的开始状态用 ε 边接起来，合并成一个状态。闭包运算R*，新建开始和接受状态，开始状态用 ε 边连到 R 的开始状态，也直接连到新接受状态表示零次重复；同时 R 的接受状态用 ε 边连回 R 的开始状态形成循环，再连到新接受状态表示一次以上的重复。

拿经典正则式(a|b)*abb来说，用 Thompson 构造法会得到一长串带 ε 边的 NFA。很多同学看到状态表就发怵，其实不需要背具体状态编号，只要理解它是怎么拼出来的：先把 a 和 b 两个单字符 NFA 用并运算拼成a|b，再把这个整体套上*闭包，得到(a|b)*，最后依次用 ε 边串上 a、b、b 三个单字符 NFA。整个构造过程层次分明，和正则表达式的括号层级严格对应。作业里如果让你写 Thompson 构造的 NFA，你只要体现出“并”“闭包”“连接”这几个拼接点，老师通常就会给分，不要求状态编号千篇一律。

2.3 子集构造法：从NFA到DFA的完整演算

NFA 转 DFA 的标准算法是子集构造法。核心思路一句话：把 NFA 状态集合变成 DFA 的单个状态。每个 DFA 状态都是一个 NFA 状态的集合，代表“当前可能在哪些 NFA 状态里”。

为了让你看清计算过程，我用一个比 Thompson 版本紧凑一些的等价 NFA 来演示。这个 NFA 有状态 0、1、2、3，初始状态 0，接受状态 3，转移规则是：状态 0 读 a 可以到 0 或 1，读 b 仍在 0；状态 1 读 b 到 2；状态 2 读 b 到 3。这个 NFA 和(a|b)*abb等价，只是省掉了大量 ε 边。

子集构造第一步，求初始状态的 ε 闭包。这个 NFA 没有 ε 边，所以初始集合就是{0}，记为 DFA 状态 A。第二步，对集合 A 分别看输入 a 和 b。读 a 时，从状态 0 可以到{0, 1}，记作 DFA 状态 B；读 b 时，从状态 0 只到{0}，仍回到 A。第三步，对 B 集合看输入：读 a，从{0,1}中的状态看，0 到 0/1，1 没有 a 边，所以还是{0,1}，也就是 B；读 b，0 仍在 0，1 到 2，于是得到{0,2}，记为 C。第四步，对 C 看输入：读 a 得到{0,1}即 B；读 b，0 仍在 0，2 到 3，得到{0,3}，记为 D。最后看 D：读 a 回到{0,1}，即 B；读 b，0 回到 0，3 没有 b 边，所以回到{0}，即 A。

把整个过程整理成一张表：

这里最关键的一步是判断哪些 DFA 状态是接受态：只要对应集合里包含原 NFA 的接受状态 3，它就是接受态。所以只有 D 是接受态。很多同学在这里出错，是因为他们用“集合是否恰好等于”来判断，而不是用“是否包含”。这两个说法差别很大，尤其是像 B 这种集合里包含 0 也包含 1 的状态，如果原 NFA 接受状态是 1，那 B 就是接受态；如果你只看集合元素多不多就会判断错。

做完之后，A、B、C、D 四个 DFA 状态就是一张完整的转移表，词法分析器可以直接拿它去查表识别串。

3. DFA最小化：作业里的“压轴题”

3.1 最小化的核心：可区分与不可区分

DFA 最小化的正式名字叫“等价状态合并”，它的理论基础是：两个状态如果从它们出发，对于所有可能的输入串，接受行为完全一致，那它们就是等价的，可以合并成一个状态。用术语说，如果存在某个输入串，使得一个状态能走到接受态、另一个不能，那么这两个状态就是可区分的，不能合并。

这里我特别想多说一句，很多同学容易把“状态转移表看起来一样”错当成“等价”。判断等价必须把接受性考虑进去。两个状态就算 a 边、b 边都指向同一个地方，如果一个是接受态、一个不是，空串立刻就能把两者区分开——因为在接受态读 ε 能接受，在非接受态读 ε 不能接受。所以最小化算法的第一步永远是：划分成接受态组和非接受态组。

标准算法叫划分细化法。初始把所有接受态放一组、所有非接受态放一组；然后反复检查每个组内的状态，看它们在每个输入符号下落入的组是否一致；如果不一致，就把这个组拆成更小的组。一直重复到没有任何组能被继续拆分，剩下的每个组就对应最小化 DFA 的一个状态。这个过程有点像筛面粉：先粗筛一次分成“能接受/不能接受”两堆，再拿不同目数的筛子一层层细分。

实际操作时有一个很容易踩的坑：DFA 的转移表必须是完整的。如果某个状态在某个输入符号下没有定义，最好补一个“死状态”，所有未定义转移都指向它，死状态不是接受态，而且所有符号下都走回自己。不补死状态，两个状态可能因为“恰好都没定义那条边”被错误地判定为等价，一补就露馅了。

3.2 用划分法拆一个完整例子

下面直接上一个作业风格的题。给定一个五状态 DFA，初始状态 T0，接受状态 T4，转移表如下：

第一步，初始划分：接受态{T4}，非接受态{T0, T1, T2, T3}。

第二步，检查非接受态组。我们要看组内每个状态在 a 和 b 两个输入下分别落到哪个组。T0 读 a 到 T1（本组内），读 b 到 T2（本组内）；T1 读 a 到 T1（本组内），读 b 到 T3（本组内）；T2 读 a 到 T1（本组内），读 b 到 T2（本组内）；T3 读 a 到 T1（本组内），读 b 到 T4（接受态组）。T3 读 b 时明显和其他三个不一样，它跑到了接受态组，而其他三个都还在非接受态组，所以 T3 要被拆出来。现在划分变成：{T4}、{T3}、{T0, T1, T2}。

第三步，检查{T0, T1, T2}。T0 读 a 到 T1（同组），读 b 到 T2（同组）；T2 读 a 到 T1（同组），读 b 到 T2（同组）；T1 读 a 到 T1（同组），但读 b 到 T3，T3 已经是另一个组了。于是 T1 也要拆出来。现在划分变成：{T4}、{T3}、{T1}、{T0, T2}。

第四步，检查{T0, T2}。T0 读 a 到 T1（另一组），读 b 到 T2（本组）；T2 读 a 到 T1（另一组），读 b 到 T2（本组）。两者行为完全一致，无可区分之处，所以保留合并。

最终得到四个状态组：{T0, T2}、{T1}、{T3}、{T4}。把{T0, T2}命名为 S0，{T1}命名为 S1，{T3}命名为 S2，{T4}命名为 S3，新 DFA 转移表如下：

从这个例子可以清楚看到，T2 和 T4 的转移行看起来几乎一样，很多同学一眼就以为它们能合并，但在第一步划分里，T2 是非接受态、T4 是接受态，它们早就被分到不同组里了。这个“看着像、实际不能合”的细节，就是最小化题里最容易丢分的地方。

4. 那些年我们踩过的坑

4.1 正则表达式里最容易翻车的几个点

第一个坑是运算符优先级。正则表达式里，闭包运算优先级最高，接着是连接，最后是并。所以ab|c的语义是(ab)|c，不是a(b|c)。很多同学写“匹配 ab 或 ac”的时候直接写ab|ac，其实这个写法也没错，但更规范的写法是a(b|c)。如果优先级搞混，在构造 NFA 时也会跟着错。

第二个坑是把a|b*和(a|b)*混为一谈。a|b*匹配的是“一个 a 或者任意个 b”，而(a|b)*匹配的是“由 a 和 b 组成的任意串”。这两个语言差别巨大，一个是有限语言加 b 的闭包，一个是完全不同的无限语言。作业里如果题目要求“由 a 和 b 组成的任意串”，你写成a|b*，那就是典型错误。

第三个坑是空串 ε 和空语言 ∅ 分不清。ε 是长度为 0 的串，它是一个具体的串；∅ 是“一个串都没有”。所以能匹配空串的正则可以是a*，而空语言的正则通常是 ∅。有的同学在描述“可选的前缀”时直接写 ∅，等于否认了这个前缀的存在，逻辑上完全变了。

第四个坑是漏写边界约束。比如要求“不以 0 开头的 0/1 串”，答案是1(0|1)*，很多同学写(0|1)*1(0|1)*，这就变成了“包含 1 的串”，语义完全跑偏。写正则前先把“开头”“结尾”“至少一个”“不能出现”这些边界词翻译成表达式里的结构，再动笔。

第五个坑是贪婪匹配问题，主要出现在注释这类带定界符的模式上。正如 2.1 节里写 C 注释正则时提到的，/\*.*\*/不是安全写法，必须用字符集把结束符屏蔽在中间内容之外。这种题考察的不只是正则语法，更是对“最长匹配”语义的理解。

4.2 状态图和状态表最容易错的三处

画状态转移图时，第一个高频错误是忘了标接受态双圈。很多同学 NFA 逻辑全对，图也画得挺整齐，唯独接受状态没画双圈，或者接受了状态却标了双圈。初态箭头、接受态双圈是自动机的基本约定，批改时第一个就看这两个符号。

第二个错误是转移边上的字符标反。比如读 b 从状态 1 跳到 2，结果在图上标成了 a；或者状态表里行和列搞反，把“状态”写到了列、“输入字符”写到了行。这种错误很可惜，建议做完后倒着检查一遍：从初始状态出发，拿题目要求的串走一遍状态表，看最终能不能落到接受态。

第三个错误是 NFA 的 ε 边画得乱七八糟。Thompson 构造法里的 ε 边有明确用途：进入子表达式、跳出子表达式、以及闭包的循环。很多同学凭感觉加 ε 边，导致自动机多了很多不该有的路径，识别出的语言比题目要求的范围大得多。画 ε 边之前问自己一句：这一条边表示的是“可选跳转”还是“并行分支”？想清楚再落笔。

4.3 最小化题目里的隐性失分点

最小化题目的失分点不在算法步骤，而在细节处理。第一个细节是初始划分不能只把接受态挑出来，而是把所有接受态放一组、所有非接受态放一组。如果接受态也有多个，它们之后还可能因为转移行为不同被继续拆分。

第二个细节是检查组内状态时，必须同时看所有输入符号，不能只挑一个看。像 3.2 节的例子，T3 和其他三个状态在 b 输入下行为不同，才被拆出来；如果只检查 a 输入，会发现大家都去 T1，全一样，那就会错误地不拆分。

第三个细节是补死状态。转移表不完整时，两个状态可能因为“在某个输入下都没有定义”而看起来等价。补上死状态之后，它们的转移目标都变成了同一个非接受死状态，这没问题；但如果一个状态对某输入有定义、另一个没有定义，补全后立刻就能看出区别。这个坑在书面作业里尤其常见，因为同学们图省事省略了未定义转移。

第四个细节是合并后要重新画转移表，不要套用旧状态名。合并状态后，旧状态名可能对应多个旧状态，直接用旧名画表很容易写混。我习惯的做法是给每个最终状态组重新命名，然后逐一填入转移目标，最后再检查一遍从新初始状态出发是否还接受原来的语言。

5. 作业不是终点：第三章到词法分析器只差一步

5.1 表驱动的词法分析器：30行代码就能跑

做完第三章的作业，如果只是会做题，其实有点浪费。词法分析器的运行方式就是一张 DFA 转移表加一个循环，把题目里的状态表变成代码，你会对“自动机到底是什么”有完全不一样的理解。伪代码大致是这样：

state = 开始状态 last_accept = -1 last_accept_pos = 0 for i in 0..len-1: ch = 输入串[i] next = 转移表[state][ch] if next == 非法状态: 如果 last_accept 有效，则返回从 last_accept_pos+1 开始的 token 否则报告词法错误 state = next 如果 接受态[state] 为真: last_accept = state last_accept_pos = i 处理完所有字符后，再检查是否有有效的 last_accept

这个逻辑里有个非常关键的点：不能一进入接受态就立刻返回 token，而要记录“最近一次进入接受态的位置”，继续往后读，直到无路可走再回退。这就是最长匹配。C 语言里if和标识符ifx并存，正则if和[a-zA-Z_][a-zA-Z0-9_]*都能匹配if的前缀，词法分析器必须选择更长的ifx，而不是一看到i后面是f就返回关键字。这个“记录最近接受位置”的技巧，是词法分析器实现的灵魂。

5.2 Flex/Lex 其实就在做“正则转自动机”

如果你用过 Flex 或 Lex 写词法规则，你会发现它的输入文件其实就是“正则表达式 + 动作代码”：

if { return IF_TOKEN; } [a-zA-Z_][a-zA-Z0-9_]* { return IDENTIFIER; } [0-9]+ { return NUMBER; }

Flex 内部做的事情，就是把每条正则表达式转换成 NFA，再用子集构造法合成一个 DFA，最后做最小化，最后生成一张表驱动的词法分析器。换句话说，龙书第三章教的每一步，都是这些工具引擎里真实运行的算法。理解了第三章，再看 Flex 生成的代码，你就知道那堆大状态表和 switch-case 是从哪来的了。

这也能回答一个很多人问过的问题：“我才学编译原理，以后用不到吧？”实际上，你在写脚本时用到的正则表达式，在代码编辑器里的语法高亮，在爬虫里的信息抽取，底层都离不开这一章的自动机理论。只是大多数时候工具帮你把它封装好了。

5.3 期末复习指南与三道自测题

如果你学第三章不只是为了交作业，还想应付期末，那复习重点很明确：概念题里常考“正则表达式与有穷自动机的关系”，简答题里常考“词法分析器的输入输出是什么”，大题则固定围绕“正则表达式→NFA→DFA→最小化”这条生产线出。建议你把每一类题型的手算流程练熟，尤其是子集构造时求 ε 闭包的步骤，不要跳步。

给你留三道自测题，都是龙书和期末卷子里非常典型的方向：

1. 写出“由 0 和 1 组成、不以 0 开头”的正则表达式。提示：先考虑首字符的限制。
2. 写出“由 0 和 1 组成、不含连续两个 0”的正则表达式。提示：参考 2.1 节那个“块”的思路，把串拆成以 1 结尾的小块。
3. 构造识别语言“最后一个字符是 b”的最小 DFA。提示：这个语言可以描述为(a|b)*b，想想最少需要几个状态。

这三道题能独立做出来，第三章的核心考点基本就拿下了。做的时候拿一张草稿纸，老老实实画状态转移图、填状态表，别眼高手低。

最后说点题外话。我当年看龙书第三章的时候，也觉得 Thompson 构造法又长又臭，宁可背答案也不想一步步推。后来做编译器相关的实际项目，需要对一门口香糖大小的脚本语言写词法分析器，才回头把这一章重新啃了一遍。那时候才明白，第三章教的不是“背出 NFA 状态表”，而是一种能力：把一段文本的模式用形式化语言精确描述，再把它转换成可执行的判定程序。这个能力在写解释器、写配置文件解析器、甚至写复杂的数据校验逻辑时，都会反复用到。所以别嫌麻烦，也别急着抄答案，草稿纸上多画几遍状态转移图，画着画着你就会发现，这些状态和边不再是一堆符号，而是你自己搭建的一台小机器。那才是真正学会的感觉。