企业官网建设流程全解析

简介：《编译原理（紫龙书）中文第2版习题答案》是一份面向编译原理学习者和备考者的配套参考资料，适合正在啃“紫龙书”的学生、考研党或自学人群对照教材巩固理论、检验解题思路。资源覆盖词法分析、语法分析、语义分析、中间代码生成、代码优化与目标代码生成等章节习题解答，涉及递归下降解析、LR 解析表构造、语法制导翻译、符号表管理等核心算法，能帮助读者验证答案并加深对编译器设计流程的整体理解。压缩包共 208 个文件，以 49 个 md 解题笔记、73 个 gif 过程示意图、67 个 graphml 状态图/语法图为主，另含少量 C/Lex 程序、PNG 截图、PDF 汇总与 HTML 说明；md 便于检索题解，gif 展示关键推导，graphml 可查看状态机/语法结构，C/Lex 代码可直接用于验证词法与语法分析。整个资源约 1.08MB，轻量易用。目前已有 3990 人学习使用，适合期末复习、考研冲刺或编译器课程设计时逐题对照、查漏补缺。 编译原理这门课，挂科率常年居高不下。原因很简单：教材理论读得懂，课后习题一做就露馅。紫龙书，也就是那本封面上画着紫色龙的《Compilers: Principles, Techniques, and Tools》，中译本第2版由机械工业出版社出版，几乎成了国内计算机专业编译原理课程的标配教材。我当年啃这本书时最头疼的，不是正文难懂，而是课后题做了没人批改，心里完全没底。今天这篇东西，是我自己整理中文第2版习题答案过程中的完整复盘，包括每章的核心解法、典型的推导步骤、网上找不到答案时我自己硬推的经验，以及哪些地方最容易掉坑。不管你是期末突击、考研复习，还是工作后想补一补编译基础，建议先把这份思路收好。

1. 先摸清紫龙书的结构，再谈刷题

1.1 中译本第2版的章节布局与命题风格

紫龙书第2版正文一共12章，从第1章的引论开始，第2章用一个简单的语法制导翻译器带出全貌，后面依次是词法分析、语法分析、语法制导翻译、中间代码生成、运行时刻环境、代码生成、代码优化、指令级优化，最后两章涉及并行性与过程间分析。国内高校的编译原理课程，一般会把第3章到第9章作为教学和考试的核心区间，其中第3、4、5、6章更是重中之重，期末试卷的大题基本都从这几章出。

这本书的中译本第2版由机械工业出版社于2009年前后引进，译者是赵建华、郑滔、戴新宇。术语翻译和国内大多数高校课件比较一致，比如“语法导向翻译”统一译作“语法制导翻译”，“推导”和“归约”等表述也规范，适合拿来对答案时对照教材术语。需要注意的是，中译本第2版对应的是英文原版第2版，和后来清华大学出版社引进的第3版（王生原等翻译）在章节编排上有差异，习题编号并不完全一致，整理答案时如果混着两个版本看，很容易对不上号。

1.2 习题答案解决的不是“抄”，而是“验证闭环”

很多同学拿到参考答案的第一反应是复印、背诵、考前突击。这个思路在编译原理这门课上基本行不通，因为考试题目几乎不会原题重现，而是换一个文法、换一个正则表达式让你现场推。刷紫龙书习题的真正价值，是建立“做题-对照-复盘”的验证闭环。

我的用法是：先自己动手推一遍，哪怕推得磕磕绊绊，也要把每一步写在纸上；然后翻开答案，逐行对照，重点看卡住的地方。如果我的构造方法和答案给的不一样，只要结果等价、推导过程合法，也算对。编译原理的不少题型都有多种解法，比如 NFA 转 DFA 选哪个状态作初态、DFA 最小化时按什么顺序划分子集，只要最终自动机接受的语言相同，就不能说谁错了。这一点，光抄答案的人是体会不到的。

2. 整理一套靠谱习题答案的完整方法

2.1 以中译本第2版习题编号为基准建立索引

中文第2版的习题编号规则比较有规律，大都是按节编号，比如第3章第3节的小题会标成 3.3.x 的样子。我整理时做了一张索引表，把每一章的习题号、对应知识点、答案来源、我的推导状态都记下来，后面复习时按表检索，不用每次从头翻。

这里有个比较坑的地方：网上流传的中文版答案，很多其实是英文原版第2版作业答案的翻译，题号和中译本能对上七八成，但个别题目会因为翻译调整而错位。所以我默认不以网传答案的题号为准，而是以中译本教材里印的题号为准，发现对不上就在索引表里标注“疑似第X章第Y题”，避免复习到一半跑去查原版书浪费时间。

2.2 官方答案、民间答案和自推三路交叉验证

紫龙书习题答案的权威来源比较稀缺。原作者在早期版本提供过部分章节课后题的官方解答，但国内能稳定找到的多是流传多年的扫描版，覆盖范围通常只有前几章，而且像素和清晰度一言难尽。后来很多高校的编译原理课程把部分原题当作作业或考试题，讲义后面附带参考答案，这些民间答案质量参差不齐，有些明显是学生作业扫描件，错误率不低。

我的办法是同一个题至少找两份不同来源的答案对照，如果两份答案不一致，就自己重新推导，再用工具验证。一份答案如果既没推导过程，又没写清楚最终结论，那基本可以直接跳过。整理到第6章之后，网上能找到的参考答案锐减，绝大部分题是我自己推完再用工具核对，过程确实慢，但收获也最大。

2.3 用工具验证你的推导结果

人工推导容易在小细节上翻车，尤其是指标集、词法自动机这类状态繁多的题。我在整理时用了几类工具，实测下来能省很多事。

词法分析相关的题，可以用 flex 构造一个最小验证程序，把正则表达式写进去，再拿几组测试串跑一遍，看接受/拒绝结果是否符合预期。语法分析相关的题，可以借助 ANTLR 或 bison 验证文法是否有冲突，比如 LR 分析表里出现移进-归约冲突时，工具会直接报出来。还有一些国产的教学工具，比如“编译原理词法语法分析实验系统”，会把 NFA 转 DFA、LL(1) 分析表、LR 自动机这些过程可视化，步骤展示得比手算清楚，用来对照自己的推导过程很合适。

如果你熟悉 Java，也可以直接用 JavaCC 或手写一个简单的递归下降分析器来做验证。这样不仅验证了答案，还把 “java+编译原理” 的实践能力一起练了。我的经验是，工具验证只能告诉你“最终结果对不对”，不能告诉你“推导过程中哪一步错了”，所以该手推的步骤一步都不能省。

3. 核心章节的解题套路与高频考点

3.1 词法分析：从正则式到DFA的三板斧

第3章词法分析是整本书第一个硬骨头，课后题最常考的就是给一个正则表达式，要求构造 NFA、再转 DFA、最后最小化。这串流程可以总结成“三板斧”。

第一板斧是 Thompson 构造法。按并、连接、闭包三种基本结构递归拆解，每引入一个算符就新增一组状态和 ε 边。很多同学在这一步漏掉 ε 边，导致后面的子集构造出问题。我的建议是画 NFA 时用虚线专门标 ε 转移，实线标字符转移，区分度一高，检查起来就容易多了。

第二板斧是子集构造法。核心是把 NFA 的状态集合映射成 DFA 的状态，关键操作是计算 ε-closure。这里最常见的错误是只算了当前状态本身的 ε 闭包，没有再对新到达的状态继续求闭包，导致初态集合漏状态。我反复踩坑后养成了一个习惯：每到一个新状态都先停下来，沿着 ε 边把所有可达状态全部加进去，再去看字符边。

第三板斧是 DFA 最小化。初始划分一定是终态组和非终态组两拨，然后反复考察每个组在不同输入符号下的转移目标，发现目标不在同一个组就继续拆分。网上很多人直接跳过初始划分，上来就按直觉合并状态，结果把终态和非终态并到一起，整个自动机就废了。记住一个原则：任何时候都不能把终态和非终态合并。

3.2 语法分析：FIRST/FOLLOW 别只背定义

第4章语法分析的课后题量最大，题型也最杂，包括消除左递归、提取左因子、计算 FIRST 和 FOLLOW 集合、构造 LL(1) 分析表、构造 LR(0)/SLR(1)/LR(1) 自动机并判断文法类型、处理移进-归约冲突等等。

计算 FIRST 集合时，同学们最容易漏掉两种情形：一是产生式右部第一个符号是终结符，直接加入 FIRST 就完事，这个还好；二是遇到形如 A → BC 这样的产生式，B 可以推导出 ε 时，还要把 C 的 FIRST 集合也加进来。这属于递归定义，很多人漏掉第二层就提前收手。FOLLOW 集合就更隐蔽了，经常忘记在开始符号的 FOLLOW 里加入结束标记 $，尤其是教材里默认用这个符号表示输入结束，考试时忘了就是白丢分。

LR 系列的题目对耐心要求很高。手工构造 LR(0) 自动机，项目集可能会画到十几甚至二十几个状态，每个状态的闭包都要重新计算。我的体感是，这类题大部分不是不会做，而是画着画着把自己绕晕了。后来我改用表格记录每个项目集的内容、每个符号转移到的项目集编号，状态之间的关系一目了然，出错的概率大大降低。SLR(1) 分析表的构造还要额外用 FOLLOW 集合解决归约动作的填入问题，这一步最容易把 FOLLOW 集合算错，进而导致整个分析表错掉，所以每次填分析表之前我都会把相关非终结符的 FOLLOW 集合重新验算一遍。

3.3 语法制导翻译与中间代码：别漏属性和临时变量

第5章和第6章的题目从“自动机构造”转向了“语义处理”，风格差别很大。语法制导定义的题，核心是把综合属性和继承属性分清楚。综合属性在产生式右部计算、往上传；继承属性从父节点或兄弟节点传下来。很多题要求你给出一个语法制导定义，但如果只写规则不标注属性类型，阅卷老师一眼就能看出你没吃透概念。

中间代码生成的题目以三地址码居多，主要考察声明语句、赋值语句、布尔表达式、控制流语句的翻译。一个特别容易失分的点是临时变量的使用：每产生一个中间结果就分配一个新的临时变量，这不仅是代码风格问题，更是为了确保后续引用不会串值。还有些题会要求你为数组引用a[i]生成带下标计算的中间代码，这里需要先计算偏移量，再计算基地址，最后才是取数，步骤一个都不能省。遇到这类题，我的建议是把“地址计算-取数/赋值”写成两步，先算地址再操作数据，逻辑就顺了。

4. 实操记录：一道经典词法题的完整推导

4.1 题目与考察点

从紫龙书第3章课后题里挑一道最有代表性的：给正则表达式(a|b)*abb，构造与之等价的最小 DFA。这题几乎每年都会出现在各高校的编译原理期末试题里，考研复试也常拿它当口试题，非常适合用来演示完整思路。

这道题表面上只考“正则式转DFA”，实际把 Thompson 构造法、子集构造法、DFA 最小化全串起来了，正好是一次完整的词法分析流程演练。下面我按步骤写一遍，每步都标出我当时踩过的坑。

4.2 NFA构造与子集构造法

用 Thompson 构造法构造 NFA，大致流程是：先为a和b分别构造两个独立的小自动机，再用闭包运算把(a|b)变成带 ε 回边的结构，最后依次连接a、b、b三段。画出来的 NFA 大约有 11 个状态，其中初态通过 ε 边连到整个自动机的入口，两个接受状态分别对应最后的b和第一个b（中间状态的处理方式不完全一样，要看参考书写的是哪一套状态编号）。

这里吐槽一下：不同教材的 Thompson 构造法在细节上略有差别，有的把闭包的回边画在子自动机外层，有的画在内部，导致状态编号完全不同。我第一次对照答案时，发现状态编号对不上就以为自己做错了，后来才明白只要转移关系等价就行。所以看答案时重点关注边的走向，而不是状态编号。

进入子集构造法。假设计算后得到初始状态集合A = ε-closure(初态) = {0,1,2,4,7}，之后按输入符号a和b不断求转移闭包。最后会得到一组 DFA 状态，逐一标出哪些集合包含原 NFA 的接受状态，这些就是 DFA 的终态。整理成表格大约是：

这个表格本身就是完整答案的一部分。考试时把这步写清楚，阅卷老师能看到你的推导链条，分数就稳了。

4.3 DFA最小化与最终结果

最小化从初始划分开始：终态组{E}和非终态组{A,B,C,D}。检查{A,B,C,D}，对输入a，A、B、C、D 都转移到非终态组；但对输入b，A 到 C，B 到 D，C 到 C，D 到 E，其中 D 的转移目标是终态组，所以要单独拆出来。分组变成{A,B,C}、{D}、{E}。

再看{A,B,C}。输入a时三者都到 B，没问题；输入b时 A 到 C，B 到 D，C 到 C，B 又不一样，于是再把 B 拆出来，得到{A,C}、{B}、{D}、{E}。此时 A 和 C 在输入a、b下的表现完全一致，可以合并。最终最小 DFA 只有 4 个状态：

这个 4 状态 DFA 就是教科书里最常见的结果。我当初自己推导时，卡在最后一步：A 和 C 能合并其实并不直观，因为它们的“名字”不同，状态含义也分别对应“尚未匹配”和“已经匹配了一个单独的 b”，但转移行为一致，按最小化算法就该合并。所以这类题做完后，尽量用工具跑一遍，能第一时间发现你少合并或误合并的情况。

5. 常见问题、资源推荐与避坑指南

5.1 网上答案版本太乱，怎么找到对得上的那个

现在网上能搜到的紫龙书答案，按来源大致分三类：一是英文原版第2版的课后解答扫描件，覆盖面广但清晰度差；二是国内高校编译原理课程的作业答案，覆盖章节不一，还经常夹带私货；三是第3版（王生原翻译）的配套答案，章节顺序和第2版对不太上，但前三章的核心题型几乎一脉相承。

我的建议是不要想着找到一份全而准的答案，那基本不存在。正确做法是：以中译本第2版教材的题号为基准，哪题不会就针对性地去搜该题对应知识点的讲解，搜题号比搜书名管用得多。比如直接搜“LR(0) 自动机 构造 例题”“FIRST 集合 计算 习题”，往往比搜“编译原理答案”更精准，因为很多老师在博客里讲过详细步骤，比干巴巴的答案更好懂。

5.2 怎么判断你自己的解法对不对

没有标准答案，就全凭自觉？绝对不是。编译原理有很强的结构性，很多题可以用工具或反例验证。比如你推了一个 LL(1) 分析表，可以用 ANTLR 把对应文法写进去，看能不能直接生成语法分析器；你手算了一个 SLR(1) 分析表，可以找一个长一点的输入串，按照分析表走一遍移进-归约，看最后能不能规约到开始符号。能走到最后，至少说明这个表自洽；走到一半卡住，大概率是表里的某个 Action 或 Goto 写错了。

还有一个小技巧：换一种解法看能不能得到同样的结果。比如同一道题用递归下降分析思路想一遍，如果你能手工写出等价的分析过程，那说明对文法的理解是通的。如果两种思路下的结果对不上，多数情况下是最初的推导里面有隐藏假设没发现。

5.3 配套视频课和期末备考的实战打法

如果只看书刷题觉得吃力，强烈建议配合视频课一起学。我推荐哈尔滨工业大学陈鄞老师主讲的编译原理课程，讲得非常细，重点和紫龙书很契合，尤其是词法分析、语法分析这两个硬块的讲解，能把教材里比较干燥的推导过程拆成一步一步的演示，配合课后习题效果很好。这门课在MOOC平台上也能找得到，适合在刷题卡壳时定向回看。

期末备考的节奏，我的心得是：别指望把全书课后题都刷完，这不现实也没必要。按题型练，每种题型吃透 2 到 3 道代表性的题就够。优先级从高到低大概是：正则式转DFA并最小化、计算FIRST/FOLLOW并构造LL(1)分析表、构造SLR(1)或LR(1)分析表、语法制导定义与属性计算、中间代码三地址码生成。这几类题在期末试卷里占掉六七十分，先把它们练熟，再去碰代码优化等较冷门的章节。刷题时严格按考试标准来，只写关键推导步骤和最终表格，不写废话，这样既练了解题速度，也顺带训练了答题格式。

我在整理这套答案的过程中，最大的收获不是手头多了一份能对照的文件，而是被逼着把每一道题从“看得懂”做到了“写得出来”。编译原理这门课最忌眼高手低，你觉得自己理解了，合上书推导一遍就知道哪里还有漏洞。建议你也用这个方法：先自己推，推到卡住再看答案，然后把答案合上，隔天再推一遍。真正留下的不是答案本身，而是你脑子里那套推导的肌肉记忆。

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