蒋立源编译原理第三章习题与答案：从正规式到DFA的高效复习法

简介：这是蒋立源《编译原理（第三版）》第三章习题与答案的PDF文档，适合正在学习词法分析、文法与自动机理论的高校学生、考研复习者及自学者使用。资源共1个PDF文件，压缩包约2.97MB，内容按习题序号编排，既包含原题，也给出逐步推导答案与关键结论。重点覆盖右线性文法的构造、状态转换图与状态转换矩阵、NFA的确定化与最小化、带ε动作的NFA处理、正规式描述语言以及正规式对应DFA的构造等核心练习。通过对照解题过程，读者可以掌握由文法到自动机、再由自动机到正规式的基本分析方法，理解不同形式化描述之间的等价转换，并用于检验自己的推导。目前已有1919人学习下载，适合作为编译原理第三章复习、作业自查与考研备考的配套资料。

1. 蒋立源编译原理第三版第三章习题与答案：先搞懂这份PDF能帮你省多少时间

期末复习到编译原理的人，大概率都下载过一份名为“蒋立源编译原理第三版第三章习题与答案(修改后).pdf”的资料。第一次打开它，很多人会误以为这是“背答案就能及格”的捷径，直到真正做题时发现，第三章习题考的并不是记忆，而是能不能手写出一张合理的DFA状态转换表，能不能把一个正规式拆成NFA再合并成最小DFA。这份答案的真正价值，是让你在闭卷状态下拿自己的推导过程和“标准答案”逐行对照，找出你在构造自动机时的思维盲区。它适合三类人：正在准备期末考试的学生、被词法分析实验卡住的本科生，以及想快速复习“正规式到自动机”这条主线的考研党。接下来我按自己的复习经验，把它拆成能直接照着做的路线。

2. 第三章考点拆解：词法分析的理论骨架与习题答案的主线

蒋立源版教材第三章讲的是词法分析，几乎所有课后题都围绕“正规式、NFA、DFA、最小化、符号表”这几件事打转。这份习题答案的每个大题里，其实都藏着一条固定主线：先能用正规式描述单词，再把正规式变成NFA，接着用子集构造法转DFA，最后做最小化。这条主线在考试里占七八成分值，在编译原理实验里也是词法器设计的核心。

2.1 正规式与正规集：所有习题答案的第一层过滤器

第三章前几个题通常会让写出某类单词的正规式，比如标识符、无符号整数、注释、空白串。答案的得分点往往不在“唯一正确”，而在“等价变形”是否严谨。比如描述“以字母开头后跟字母数字”的标识符，常见写法是letter(letter|digit)*，但有人会写成letter|letter(letter|digit)*，后者其实求的集合和前者不同——前者包含了单独一个letter，后者也包含，但前者的*作用范围是(letter|digit)，所以等价。答案里如果出现这种变形，说明出题人想考察正规式运算的优先级和闭包。

我一般建议拿到答案后，不要先看推导，而是自己先列出这个正规式对应的三个正例和三个反例。比如a9、_a、9a分别应该被接受还是拒绝，如果你判断错，说明你对“字母”的定义没有和题干对齐——有些题里letter只包括英文大小写，有些题把下划线也算进去。这是答案里最容易“看懂但做错”的第一层。

此外，第三章还会考正规式和上下文无关文法的边界。习题答案里会明确说“词法规则用正规式，语法规则用文法”。如果你在答案里看到某道题用文法描述单词，那大概率是陷阱题。正确做法是用柯莱尼闭包和选择运算，而不是递归定义。这个区分在后面的符号表题里也会涉及。

2.2 从NFA到DFA与最小化：答案里的表格式推导是拿分关键

第三章有一半题目会让“为下面的正规式构造NFA”“用子集构造法转DFA”“最小化DFA”。许多同学会在这一步翻车，不是因为不会，而是因为答案里的表格太简洁，只看结果不看过程，到自己写时不知道状态集合是怎么编号的。

习题答案里NFA的画法通常遵循Thompson构造法：每个正规式子表达式对应一个小NFA片段，然后用ε连接起来。子集构造法的答案是ε-闭包的表格，第一列是新状态名，第二列是对a的转移，第三列是对b的转移，以此类推。我在批改时发现，得分高的人不会只写A={1,2,3}，而是会把“从状态1出发经a到达哪些状态、这些状态再经ε到达哪些状态”的理由写在旁边。这样做的原因是DFA状态名的编号如果和答案不一致，只要有中间过程，老师还能按步骤给分。

最小化的答案则是一张划分表：先把所有状态分成终态集和非终态集，然后反复按转移函数细分。答案里通常会看到类似“{0,1}|{2} -> {0,1},{2}”的写法。这里有一个容易忽略的点：划分时不要看状态编号是否相邻，而是看它们对每个输入符号的“去向集合”是否属于同一个现有集合。很多习题答案会把最终划分直接给出，但你最好在纸上补一遍每次划分前后的表，否则遇到“不可达状态”时你会一头雾水——有些答案会先把从开始状态不可达的状态删掉，你没删就直接最小化，结果会多出状态。

2.3 符号表与词法错误处理：考试和编译原理实验的共同交集

蒋立源第三章的最后几题会涉及符号表，这部分在热词里也经常和“编译原理符号表”一起出现。习题答案里符号表题通常考三类：符号表的组织方式（线性表/有序表/散列）、作用域管理（是否允许嵌套）、重复声明的处理策略。有些同学只背了“符号表是一张表”就去做题，遇到“局部变量和全局变量同名怎么办”就懵了。

答案里常见的做法是给每个作用域维护一个独立的符号表，或者用栈式符号表。我在做这类题时的自查方法是：画一张“变量名-作用域”的嵌套图，然后看答案里的查找过程是否按外层顺序回退。比如内层找不到x，应该去外层表里找，如果答案直接跳过了外层，说明它默认了“不允许跨作用域访问”，这时候你要回头看看题干的描述。这道题还经常和“编译原理实验”挂钩，因为词法分析识别出的单词类别最后都要登记到符号表里，属性包括类型、地址、行号等。

很多学校的编译原理实验（比如广州大学编译原理实验里就有词法分析一关）要求你用Java+编译原理课程学的知识实现一个简易词法器，符号表就是实验里跑不掉的一环。习题答案里的“符号表题”虽然偏理论，但实验里的表项设计、关键字和标识符的区分，都回归到这一章的概念。看答案时别只看结构，要看它怎么处理“重复定义”“未定义”这两类错误，这些在实验报告里也是加分项。

3. 用这份习题答案做自测的完整流程：从闭卷到改错的五个步骤

如果你已经拿到“蒋立源编译原理第三版第三章习题与答案(修改后).pdf”，建议别一页页翻着背。我自己的做法是把它当成“有参考答案的练习册”，按下面五个步骤走完一遍，比我同学直接刷三遍效果要好得多。

3.1 第一步：闭卷手写，把每个题当成一次“微型实验”

打开PDF后，先只看题干部分，把答案部分遮住。拿一张A4纸，严格按考试格式写：每题先写正规式，再画NFA，再写子集构造法的状态转换表，最后画最小化DFA。不要在心里想“这题我会”，一定要落笔。

写完以后，在纸的右上角给自己打一个“盲写自信分”，比如10分制。这个分数不用于和别人比，而是为了观察自己哪些题是真正会写，哪些是“看一眼答案才会”。我当年给标识符题打了7分，结果批改后发现自己把letter(letter|digit)*的NFA画成了letter后直接接回起点，没有给digit单独立分支——这就是只看书没下笔的典型症状。

这一步还有一个好处：你会发现习题答案里的题干其实隐含了很多边界条件。比如“以/开头，以*/结尾的注释”，是否允许嵌套？是否允许出现在字符串里？如果你不闭卷写，就不会意识到自己漏考虑了。

3.2 第二步：批改时只标差异，不直接看答案推导过程

把自己的答案和PDF里的答案并排摆开，用红笔只标记“不一致的点”，比如状态数量不同、转移条件不同、终态集不同。不要急着看对方为什么那样写，先把差异列成清单。清单样式如下：

这个表做出来以后，你会发现多数差异分为两类：一类是等价的常规变形，另一类是实质构造错误。前者不用慌，后者才需要进入第三步。

不要在批改阶段就翻答案讲解，因为很多人会陷入“哦原来是这样”的虚假理解，关上PDF又不会了。批改的目标是找出盲区，而不是获得正确答案。

3.3 第三步：对照答案的表格重新推一遍NFA/DFA

找出实质差异后，再回头看答案里的表格。这时不要只读表，要拿一张新纸，从答案的NFA开始，自己重新画一次子集构造法。比如答案里写ε-closure({0}) = {0,1,2}，你就要自己从状态0出发，模拟每条ε边，看到底能不能到状态2。

很多习题答案的“修改后”版本里，会修正掉早期版本的一些笔误。你重新推一遍时，最好用铅笔在答案表格的旁边补上自己的计算过程，比如“这里A状态对a的转移是1、2，原因是从状态1能走一条a边到状态4，状态4又能经ε到状态5”。这样推完，你才算真的“看懂”了这份答案。

如果发现答案和自己的不一致，但答案又是等价且更简洁的，可以把答案的写法记在错题本上。比如“最小化后状态数相同但状态编号不同”这种不算错，考试时老师会接受等价答案。

3.4 第四步：把错题按“构造类/化简类/表驱动类”归档

大多数习题答案的题目都能归到三类。我在笔记本上做了三个标签：

• 构造类：从正规式构造NFA/DFA，错在漏边、多边、终态设错。
• 化简类：DFA最小化、删除不可达状态，错在划分不细、合并了不等价状态。
• 表驱动类：根据转换表识别单词、输出token类型，错在最长匹配和回退逻辑。

归档以后，你会发现自己的错误集中在某一类。比如我的构造类错得少，但化简类总喜欢把终态和非终态放同一组，这就是典型的“划分第一步就没做对”。针对这一类，可以专门回到第二章的等价关系定义，再看答案里最小化的前两行。

这一步还能帮助你预测考试重点。如果你所在的本科院校在“编译原理实验”里要求用Java写词法器，那么表驱动类的错题价值更高，因为它直接对应实验里的自动机模拟循环；如果期末考试更偏理论，构造类和化简类就是主要得分区。

3.5 第五步：用归档清单回头检查第2章知识点

最后一步是把错题清单映射回第二章的知识点，形成一张“薄弱知识点-对应题号-答案页码”的对照表。比如“不可达状态删除不彻底”对应知识点“DFA中每个状态必须从初态可达”，你就在PDF里找到那道题，用荧光笔标出答案里删除该状态的那一步，并在旁边注明“我错在没删”。

这一步做多了，你会明显感觉到“蒋立源编译原理第三版第三章习题与答案”不再是一份静态的PDF，而是变成了一张带索引的错题地图。复习时不需要重新做所有题，只需要看自己的对照表，哪一项标红就重做哪一题。我考前的复习时间能缩短一半，靠的就是这张表。

4. 避坑：蒋立源第三章习题答案里常见的四个翻车点

看这份PDF时，大家踩的坑高度相似。我结合自己和同学的教训，总结了四个最容易出问题的地方，每条都按“现象-原因-解决”来写。

4.1 现象：答案里的ε转移被“省略”，推导时漏边

很多习题答案为了画图简洁，NFA中的ε边用虚线或根本不标。比如从状态1到状态2有一条ε边，但答案只写了“状态2等价于状态1”，没有画箭头。你照着子集构造法求ε-closure时，很可能漏掉本来能到达的状态，导致后面DFA状态表少了行。

原因：PDF里的图是静态图片或简化文本，作者默认读者已经掌握Thompson构造法，能自己脑补出ε边。解决：每道NFA题先独立画出完整的ε边，再和答案的简化图比对。我一般用不同颜色的笔补画ε箭头，画完以后再对照答案的ε-closure集合，如果集合里的状态数多于你画的，说明你漏边了。

4.2 现象：DFA最小化时把终态和非终态合并到一起

这是最常见也最致命的错误。比如一个DFA有状态A、B、C，其中C是终态，A和B在输入0时都到C，输入1时都到非终态。有些同学看到A和B转移完全一致，就合并成一组，但忘了A是非终态、B是终态——即使转移一样，终态属性不同也不能合并。

原因：我们从第二章学到的“等价状态”条件有两个，一是行为一致，二是同为终态或同非终态。很多人只记住了前者，后者下意识忽略。解决：做最小化时，第一步永远先画一条竖线把状态分为终态集合和非终态集合，然后在这两个集合内部再做细分。习题答案里如果合并后的状态里既有终态又有非终态，那基本可以认定是答案印刷错误，或者它用的是另一套定义——这时候你要以教材正文的定义为准。

4.3 现象：符号表题只答了表结构，没答作用域与生命周期

PDF里符号表习题答案经常会画一张“符号表”，但有些版本只给出表头和几行记录。如果你照抄这种答案，遇到考试里“变量在块内声明，块外是否可见”的扩展题，就会丢分。

原因：答案只覆盖题目基本问法，没有覆盖变体。解决：看符号表题时，先把“作用域栈”画在旁边，把每个表项标注它所属的层号，然后模拟一次声明和查找。如果答案里的层次关系和你画的不一致，说明题目可能要求“不允许访问外层同名变量”。另外，注意符号表的生命周期是“编译期”还是“运行期”，习题答案里有时会混用，这两个概念在编译原理实验的符号表打印任务里尤其重要。

4.4 现象：答案版本是“修改后”，页码与题目编号和原书对不上

这份PDF的文件名里有“(修改后)”，意味着它修正过某个早期版本。但修正后的内容不一定和原书页码一一对应。我曾看到有人说“第3.7题答案不对，因为我的书里3.7题是另一个题”，其实是他看的是旧书或者答案PDF里的题目编号错位了。

原因：不同印刷批次的书，题号可能会有微调；PDF在改版时保留了原题号，但页码重排了。解决：不要依赖页码和题号来定位，建议用“题干关键词”来匹配，比如“为正规式(a|b)*abb构造NFA”。如果PDF里只有答案没有题干，你可以先把书上的题干抄到PDF对应答案旁边，形成自己的“题干-答案对照版”，之后复习就不怕错位了。

5. 从习题答案到编译原理实验：用Java或Python实现一个词法器

如果你正在做编译原理实验（很多学校的实验课都叫“编译原理实验”，常用Java实现），这份习题答案里的DFA完全可以变成可运行代码。下面是我常用的最小实现路线，用Python写更直观，但思路用Java也能照搬。

5.1 最小可用词法器：先用手写状态机跑通识别流程

一个最简单的词法器只要识别标识符和整数就行。DFA状态可以定义成常量，状态转移用二维数组或字典。先看这个最小可运行的骨架：

# 极简词法器：识别标识符(letter开头)和无符号整数(digit开头) import sys # 状态定义 START = 0 ID = 1 # 标识符状态 NUM = 2 # 整数状态 DONE = 3 # 接受状态，这里用DONE表示成功识别一个词 def classify_char(ch): if ch.isalpha() or ch == '_': return 'letter' if ch.isdigit(): return 'digit' return 'other' def next_state(state, ch): kind = classify_char(ch) if state == START: if kind == 'letter': return ID if kind == 'digit': return NUM return -1 # 非法起点 if state == ID: if kind == 'letter' or kind == 'digit': return ID return DONE # 遇到非字母数字，结束标识符 if state == NUM: if kind == 'digit': return NUM return DONE return -1 def tokenize(code): tokens = [] i = 0 while i < len(code): ch = code[i] if ch.isspace(): i += 1 continue state = START start = i while i < len(code): state = next_state(state, code[i]) if state == -1: break if state == DONE: break i += 1 # 注意：遇到DONE时，i指向当前字符，需要回退一个 if state == DONE: tok = code[start:i] tokens.append((tok, 'IDENT' if tok[0].isalpha() else 'INT')) else: # 如果循环耗尽仍然处于ID或NUM，把剩余字符也识别为token if state == ID or state == NUM: tok = code[start:i] tokens.append((tok, 'IDENT' if tok[0].isalpha() else 'INT')) else: raise SyntaxError(f"无法识别字符: {code[start]} at index {start}") return tokens # 测试 sample = "abc 123 def456" for tok in tokenize(sample): print(tok)

这段代码的逻辑是“最长匹配”：从初始状态开始，不断读入字符并更新状态，直到状态变成接受态(DONE)或读入非法字符。注意DONE状态是在读入下一个字符后才触发，所以在返回token时要回退一个字符。这是词法分析里最容易写错的地方。

参数说明：这里的classify_char相当于DFA的输入符号分类，你可以把它替换成正则表达式判断；next_state就是状态转换表的一行一列。如果你想把“关键字”也加进来，可以在识别出IDENT后查一个关键字集合：keywords = {'if', 'else', 'int', 'return'}，如果token在集合里，就把类型从IDENT改成对应关键字名。这个处理方式和习题答案里的“标识符与关键字识别”是完全对应的。

5.2 把正规式转NFA的代码框架：习题答案之外的工程延伸

如果你不满足于手写DFA，可以尝试做一个正规式到NFA的转换器。这是第三章习题答案里那些手工作业题的“机械化版本”。核心思路是用Thompson构造法，把正规式的每个部分递归地拼成NFA片段。这里给出一个极简框架，只支持连接、选择和闭包三种运算：

# 极简正规式 -> NFA 框架（只支持 a|b, ab, a*） # 状态用整数表示，NFA用字典存边：{(起点, 终点): 输入字符或'ε'} class NFA: def __init__(self, start, accept, edges): self.start = start self.accept = accept self.edges = edges # { (from, to): symbol } def char_nfa(ch): s = 0; t = 1 return NFA(s, t, {(s, t): ch}) def concat(n1, n2): # 把n1的接受状态和n2的开始状态用ε连接 edges = dict(n1.edges) edges.update(n2.edges) edges[(n1.accept, n2.start)] = 'ε' # 调整n2的状态编号，避免冲突（这里省略偏移逻辑） return NFA(n1.start, n2.accept, edges) def union(n1, n2): # 新建初态0和终态F，两边用ε连接 edges = dict(n1.edges) edges.update(n2.edges) new_start = 0; new_accept = 1 edges[(new_start, n1.start)] = 'ε' edges[(new_start, n2.start)] = 'ε' edges[(n1.accept, new_accept)] = 'ε' edges[(n2.accept, new_accept)] = 'ε' return NFA(new_start, new_accept, edges) def star(n): # 闭包：加一条从接受状态回到开始状态、以及跨越整个NFA的ε边 edges = dict(n.edges) new_start = 0; new_accept = 1 edges[(new_start, n.start)] = 'ε' edges[(n.accept, new_accept)] = 'ε' edges[(n.accept, n.start)] = 'ε' edges[(new_start, new_accept)] = 'ε' return NFA(new_start, new_accept, edges)

这段代码没有处理状态编号冲突，实际工程里需要用计数器重新编号。它存在的意义是帮你理解习题答案里的NFA图是怎么一步步拼出来的——答案中那些弯弯曲曲的ε边，本质上就是上面这些操作的产物。

参数说明：edges字典里的键是(起点, 终点)，值是该边上的输入字符或ε。在做子集构造法时，你要先实现ε-closure函数：从一个状态出发，把所有能通过ε边到达的状态收集起来。这个函数就是回答“为什么答案里ε-closure({0})包含那么多状态”的最直接工具。我建议你用Python写完这个函数后，把习题答案里的NFA输进去，对比你的闭包结果和答案是否一致，这就是最可靠的验证方法。

5.3 用习题答案原题做测试集：构造覆盖三类情况的验证用例

习题答案里的正规式最优当测试用例，因为它们既有正确答案，又能覆盖边界。我经常把第三章课后题里的词例如(a|b)*abb、a(b|c)*、c*a*等拿来做词法器的测试输入。具体做法如下：

• 对每个正规式，先用自己实现的转换器生成NFA/DFA。
• 准备三组输入样例：一组应该接受（正例），一组应该拒绝（反例），一组和自动机“沾边”但会因为最长匹配规则而回退（边界例）。
• 把运行结果和习题答案的状态转换表对照。

比如识别(a|b)*abb，正例是ababb、bbbabb，反例是abab（末尾找不到abb完整串）、ababba（多余字符）。边界例可以是abbab，按最长匹配应该先识别出abb，再识别ab。用代码跑一遍，你会发现如果状态机在a后面遇到b时没有正确回退，输出就会是错的。

这个测试集不仅能验证你的代码，还能帮你反向理解习题答案里的DFA为什么某些状态被标记为“接受状态”。我把答案题号和我自己的测试用例对应起来，建立了下面这种小表，复习时一眼就能看出哪个知识点还没覆盖：

做完这一步，你会发现习题答案PDF已经变成了你实验报告的“参考答案”和“测试标准”。很多同学做编译原理实验只写代码不写测试，导致验收时被老师几个反例问懵；拿这些原题做测试，至少能让你在理论上站得住脚。

6. 进阶检验方法：用“自动机等价性”验证你的答案与教材答案一致

当你做习题答案里的DFA最小化题时，可能会遇到“我的最小DFA和答案的状态数一样，但状态转移表看起来不一样”的情况。这并不一定是你错了，也可能只是状态编号不同。我自己的习惯是用一种“行为黑匣子对比法”来验证：对于每个可接受的输入串，两台DFA要么都接受，要么都拒绝，那就认为等价。不需要把两台DFA的状态名映射起来，只需要穷举一个足够短的输入串集合。

具体做法是写一个穷举小脚本，生成所有长度不超过5的由a、b组成的串，分别喂给两个DFA的模拟函数，比较接受结果。如果全部一致，基本可以确认答案等价。这个办法在应对“答案修改后状态编号变了”的场景特别有用，比如你从PDF里抄的DFA状态A对应别人的状态S0，但转移函数本质上一样。避免因为编号顺序不同而误判自己写错。

如果发现不一致，先检查两边是否有未删除的不可达状态。我上次做一个(a|b)*abb的题时，答案里删除了初始状态无法到达的某个状态，而我没删，导致最小化后多了一个状态。用等价性验证脚本一秒就能定位，比一页页翻答案快多了。

这份PDF我前后用过两轮：第一轮是期末复习，照着答案背，结果考试遇到“把注释识别成token”的题还是不会；第二轮按上面说的方法闭卷手写、归档错题、再用脚本验证等价性，才真正把第三章啃下来。我的教训是：习题答案不是用来背的，是用来“对照错误”的。你花在批改和重推上的时间，会比反复刷整套题更有价值。希望这个流程能帮你在编译原理这门课上少走点弯路。

本文还有配套的精品资源，点击获取