编译原理课后习题答案.doc：从校验器到逆推验证的完整使用指南

简介：《编译原理第三版》课后习题答案文档，面向计算机专业本科生、考研备考者以及需要系统梳理编译原理核心知识点的自学者，针对各类课后练习中的重点和难点提供逐题解答。压缩包为1个doc文件，约984KB，目录结构清晰，按章节从词法分析（P36）、语法分析、中间代码生成（P64）、目标代码生成（P81）延伸到优化技术（P133），便于按需检索。文档按章节顺序排列习题，编号与页码标识明确，脉络清晰。内容涵盖Token识别与词法分析器、语法规则与语法分析树、中间代码形式和生成规则、目标代码生成及优化方法等编译全过程要点。目前已有1729人学习下载。文档不仅给出答案，还注意展示关键推导和实现思路，适合对照教材逐章查漏补缺，也能帮助备考者快速建立从源程序到可执行代码的整体编译脉络。

1. 编译原理第三版课后习题答案.doc：一份答案文档能把编译原理学到什么程度

手头只有一份《编译原理第三版课后习题答案.doc》的时候，多数人的第一反应是考前突击：把词法分析、语法分析的大题抄一遍，求个心理安慰。但这份文档真正值钱的地方不是让你背，而是当"校验器"——你手算的 FIRST/FOLLOW 集、NFA 转 DFA 的状态转换表、LR 分析表，跟它一对照，就能精确知道卡在哪一步。适合正在修编译原理课程、准备考研复试，或者做编译原理实验写到一半被文法分析卡住的人。一个反直觉的结论：这类答案文档里的错误比想象中多，尤其是 LR(1) 展望符和 FOLLOW 集这两块，直接抄反而会让你在考试和实验里翻车。它是一份需要带着怀疑去读的资料，而不是标准答案书。

2. 先看这份答案文档覆盖了什么：从词法分析到代码生成的六类典型题

编译原理第三版的课后题，按教材章节大致可以分成六类：正则式与有穷自动机、词法分析器设计、文法与语言、LL(1) 分析、LR 分析族、语法制导翻译与中间代码生成。答案文档里出现频率最高的是前三类，因为它们有唯一结果，适合手算对答案；后三类步骤长、结果判定依赖过程正确，答案只给结论的话用处有限。先搞清文档里有哪些题型，再决定每道题投入多少时间，这是用这份文档之前最值得做的一件事。

2.1 词法分析：正则式、NFA 转 DFA 与最小化，答案怎么用

这类题在答案文档里通常以状态转换图或状态转换表的形式出现。常见出题方式有三种：给正则式让构造等价的 NFA 或 DFA；给一个 DFA 求最小化；反过来给一段词法规则让写出正则式。对答案时重点看三个参数：状态编号是否一致、弧上的标记是否齐全（尤其是 ε 弧），以及初态终态集合是否标对。

用答案文档的正确姿势是先遮住结果自己画一遍。以典型例题(a|b)*abb为例，第一步把 a、b 各自拆成小的子 NFA，用 ε 弧并联进初态；第二步加两个并联的 ε 转移表示闭包；第三步依次串联 a、b、b 的识别路径。子集构造法得到 DFA 状态时，答案的编号一般是 I0、I1 这样按生成顺序编的，自己算的编号和答案对不上不一定是错，要看状态转移是否同构。

最小化部分的坑比较隐蔽：有些答案文档把最小化直接写成"合并 2、3 状态"，但不说明用的是可区分性划分。手算时第一轮按终态/非终态划分，第二轮看每个状态对每个输入符号的转移落在哪个集合，转移不在同一集合的两个状态必须拆开。答案若跳过了中间的划分迭代，你用最终结果倒推一遍划分过程，反而比对着抄更稳。

2.2 语法分析：LL(1) 与 FIRST、FOLLOW 集的计算，别只抄结果

语法分析是课后题的重头，答案文档里量最大的是 FIRST 集、FOLLOW 集和预测分析表。计算规则可以压成三句话：FIRST 集里终结符直接进，非终结符顺着产生式传播，能推空串的产生式把 ε 传进去；FOLLOW 集从开始符号加 $ 起步，跟在 A 后面的 B，把 FIRST(β) 减掉 ε 并进 FOLLOW(B)，能推空的后面再接 FOLLOW(A)。以最经典的算术表达式文法为例：

E → TE' E' → +TE' | ε T → FT' T' → *FT' | ε F → (E) | id

这个文法的 FIRST 和 FOLLOW 结论如下：

对答案时发现 FOLLOW(T') 多了 $ 或少了 +，几乎可以肯定是 ε 产生式处理错了：FOLLOW 集传播时，遇到能推空的非终结符，要把它后面的东西"透支"给前面的符号，很多人漏掉这一步。LL(1) 判定题也是如此，同一非终结符的候选式 FIRST 集两两不相交，且任何一个候选可推 ε 时，它的 FIRST 不能和该非终结符的 FOLLOW 相交。答案直接写"是 LL(1)"或"不是 LL(1)"时，不如自己构造预测分析表来得踏实，表中同一格出现两个产生式的那一格，就是你判断冲突时该圈出来的证据。

2.3 LR 分析表与中间代码生成：答案文档里最容易出错的两块

LR 族分析表和中间代码生成，是这份答案文档里"事故率"最高的两处。原因很直接：这两类题的答案是否正确取决于过程，而 .doc 里常常只给最终分析表或最终四元式序列，中间项目集规范族被压缩成一句"略"。你要是只对着最终结论背，遇到考试里换一个文法的变体题，基本就只能靠玄学了。

LR(0) 项目集规范族要验证，只有一条路：从 I0 = closure({S' → ·S}) 开始，对每个项目集里的每个非终结符 X 做 goto，循环到没有新状态为止。SLR(1) 在归约时用 FOLLOW 集做展望，LR(1) 则要在项目里带展望符。答案文档给你最终表，你可以倒推：表中某一格标注 r1 却和 FOLLOW 集冲突，说明要么 FOLLOW 算错，要么展望符没算对。遇到这类题，我一般会把答案表当"参考"而不是"标准"，先用 15 分钟重建项目集规范族，再回来对照，能发现不少抄错。

中间代码生成题以四元式和回填为主。四元式 (op, arg1, arg2, result) 的顺序要跟你自己推导的语义动作一致；回填题则要把真值/假值链的编号对齐。答案文档给的四元式行号和教材里的编号对应关系经常差一位，对答案时先数行数，再对每行操作符，行数对不上就先别纠结内容。

3. 用答案文档反推知识点：一份课后题答案的正确打开方式

答案文档最大的误用是拿来当教材从头读。读答案学不会编译原理，因为课后题答案只覆盖"每道题的结论"，不覆盖"为什么这么做"。正确的打开方式，是把文档当一面镜子，用来照自己思考过程里的裂缝，而不是当标准答案书来背。

3.1 先做题后对答案：把 .doc 当校验器而不是教材

我建议的流程是五步，每一步都有明确产出：

1. 读题后先圈考点。圈不出来就翻教材目录，把题号对应到章节，再回来看题。
2. 白纸手算到能写出结论为止，卡住 10 分钟看教材对应规则，而不是看答案。
3. 对答案时只标记"结论一致/不一致"，不直接改自己的草稿。
4. 对不一致的题，把答案的中间步骤和教材规则逐条比对，找出第一个分叉点。
5. 在题号旁边批注这个分叉点，作为复习时的重点。

这套流程的核心逻辑：答案文档给出的是"考试里会得分的形态"，你的草稿是"思考过程的形态"，两者不一致时，多半是过程中哪个规则没落地，而不是答案错了。先改自己的过程，再怀疑答案，这个顺序不能反。一上来就翻答案，等于把思考过程外包给一份来路不明的文档，后面实验课写代码时迟早要还债。

3.2 用答案里的构造步骤做交叉验证：以 LR(0) 项目集为例

答案文档里如果给了项目集规范族，是运气好；只给分析表，就需要自己重建。以文法S → A A、A → aA | b为例，这是很经典的 LR(0) 练习，重建步骤如下：

1. 增广文法，加 S' → S。
2. I0 = closure({S' → ·S})，最终包含 S' → ·S、S → ·A A、A → ·aA、A → ·b。
3. 对 I0 分别按 S、A、a、b 做 goto，得到 I1（S' → S·）、I2（S → A·A，A → ·aA，A → ·b）、I3（A → a·A，A → ·aA，A → ·b）、I4（A → b·）。
4. 对 I2 里的 A 做 goto 得到 I5（S → A A·）；对 I3 里的 A 做 goto 得到 I6（A → aA·）。
5. 检查 I3 里 A → a·A 对 a 的 goto 仍是 I3，对 A 的 goto 是 I6，闭环即结束。

和答案对照时，状态编号可能不同（有的答案按生成顺序编），但只要每个项目集的"项目内容"和"goto 目标"一一对应，就是同一份东西。编号对不上不用慌，项目内容对不上才需要回炉。

3.3 答案不全时的补全路径：结合实验课与编译器调试

常见的答案 .doc 只有前面几章，后半部分（语法制导、中间代码、代码优化）往往只有题号没有答案。与其到处找残缺文档，不如把编译原理实验的路径走一遍。多数学校实验分三个阶段：词法分析器（flex 或手写）、语法分析器（bison/yacc 或递归下降）、语义分析与中间代码生成。做完这三步，课后题里"设计题"的答案你自己就写出来了。

如果用的是 Java 技术栈，常见做法是用 JavaCup 生成语法分析器，配合 JFlex 做词法分析，正好覆盖 java+编译原理 这个方向的实验需求。写完之后拿课后题里的文法喂进去，看有没有冲突报告，比对着 .doc 猜答案可靠得多。答案文档缺的部分，就用工具的输出补上，补完再做 3.1 里的五步对答案流程，这样补出来的结论至少有工具背书。

4. 编译原理第三版课后题答案的避坑记录：这些坑我基本都踩过

下面五条是我用这类答案文档时真实踩过的坑，每一条都按"现象 → 原因 → 解决"说清楚，照着排查能省下大量对答案的时间。

4.1 FIRST/FOLLOW 集算错导致 LL(1) 分析表对不上

现象：自己算的 FOLLOW(T') 里有 $，答案文档里没有，预测分析表怎么都对不上；或者同一格出现两个产生式，程序跑起来直接报文法冲突。

原因：FOLLOW 集的传播规则里，产生式右部形式是 A → αBβ 且 β 能推 ε 时，要把 FOLLOW(A) 整个并入 FOLLOW(B)。漏掉这一步的人会把 FOLLOW 少算一大块；反过来，有人把 FIRST 里的 ε 不加处理直接并入 FOLLOW，又会多算。答案文档很多只写最终集合、不写过程，抄的时候很容易把两个方向搞混。

解决：把 FOLLOW 的迭代过程按轮拆开。第一轮只处理 A → αB 和 A → αBβ（β 可推 ε）这种直接传播；第二轮再补 β 中非终结符的 FIRST 传播；迭代到集合不再变化为止。每轮结束和答案对照一次，第一轮对不上就只查直接传播规则，别全盘重算。

4.2 NFA 转 DFA 后的子集编号和答案不一致

现象：自己算的 DFA 有 6 个状态，答案文档只有 5 个；或者状态数一样，但编号顺序完全不同，怀疑自己哪步错了。

原因：子集构造法的状态编号取决于闭包的计算顺序，答案文档的整理者通常是按自己手算的顺序编号，不是你按教材步骤得到的编号。状态数不一致才是真问题，编号不一致不是。

解决：别用编号对答案，用"状态包含的 NFA 状态集"对答案。把每个 DFA 状态还原成 NFA 状态集合，看看两个状态集是否一一对应；能对应上，编号不同无所谓；对应不上，才需要回到 epsilon 闭包这一步，检查闭包是否漏掉了经 ε 弧可达的状态。最小化之后再做一次同样的集合比对。

4.3 LR(1) 项目集规范族少一项，移进-归约冲突判断相反

现象：答案说某文法不是 SLR(1)，但你重建的 LR(0) 项目集规范族里看不到冲突；或者答案给的 LR(1) 项目比你自己算的少了带某个展望符的项目，导致你判断"可归约"，答案却写着"应移进"。

原因：LR(1) 项目的展望符来自归约项目所在项目集的"前进路径"。闭包计算时，遇到 A → α·Bβ 这种项目，要把 FIRST(β) 的每个终结符作为新项目的展望符；很多人直接沿用 LR(0) 的闭包习惯，把展望符默认成 $，于是少生成一整个项目分支。

解决：LR(1) 闭包动手前先列两个集合：当前位置需要的展望符集合，和 β 的 FIRST 集合。每生成一个新项目，先写 [产生式, 点位置, 展望符] 三元组，再检查闭包。对答案时不要比项目数量，要比"每个归约项目 A → α· 带哪些展望符"，这个对上，项目数量少一个也大概率只是合并写法不同。

4.4 公式排版错位，把推导箭头看成减号

现象：答案里一个产生式写的是 A → b | ε，但 .doc 打开后箭头显示成"-"，或者 ε 显示成空字符，整道题看起来是错的。

原因：.doc 是老格式，很多课后题答案是早年用公式编辑器录入后转存的，符号编码在 WPS、Office、LibreOffice 里渲染不一致。遇到字体缺失，推导箭头会退化成连字符，下标数字会变成普通数字。

解决：先换打开方式。.doc 用 WPS 或 LibreOffice 打开通常对老公式兼容更好；还乱码就另存为 PDF，在打印预览里看公式。对关键题，从答案反推题面：如果题号对应的内容和你教材对不上，优先怀疑题面错位而不是答案错，再决定这道题要不要跳过。

4.5 题号与教材版本对不上，答案张冠李戴

现象：答案文档前几章和教材章节顺序一致，到了 LR 分析那章，题号连续但内容跳跃，甚至混入了另一本教材的题目。

原因：第三版教材有过多次印次修订，部分印次调整了课后题编号；整理答案的人往往只按自己手上的印次录入，文档流传过程中又被拼接裁切。

解决：对答案前先做一次题号抽样，随机抽三道你知道结论的题，看文档里的题干和你的教材是否一致。抽样有两道对不上，这份文档只能当部分参考，优先用自己手算和工具验证，别把时间花在调和大版本差异上。

5. 把课后题答案变成可复现实验：三张表加一个校验流程

答案文档读三遍不如整理一遍。把散乱的 .doc 内容结构化之后，复习效率和对答案的准确度都会上一个台阶。下面是我常用的三张表和一个固定点校验流程。

5.1 用表格整理答案：题号、知识点、结论、验证状态

我一般建一张"题目—答案—验证状态"表，把文档内容结构化，既方便复习，也方便发现文档内部矛盾。表的结构建议如下：

填表时注意：验证状态这一列不要只写"对"或"错"，要写验证手段，比如"JFLAP 一致"或"bison 报告冲突"。这样三个月后回来看，还能知道当时为什么信这个结论。

5.2 手工构造与工具对照：用脚本验证 FIRST/FOLLOW 集

手算之后，用脚本验证是性价比最高的方式。常见做法是写一个固定点迭代的 Python 脚本，把产生式按字典维护，反复计算 FIRST 集直到不再变化。下面是一个能直接跑的简化版：

# first_sets.py: 用固定点迭代计算 FIRST 集，验证课后题答案 rules = { 'E': [['T', "E'"]], "E'": [['+', 'T', "E'"], []], # 空列表代表 ε 'T': [['F', "T'"]], "T'": [['*', 'F', "T'"], []], 'F': [['(', 'E', ')'], ['id']], } terminals = {'+', '*', '(', ')', 'id'} first = {nt: set() for nt in rules} changed = True while changed: # 外层固定点：集合变大就继续 changed = False for nt, prods in rules.items(): for prod in prods: if not prod: # 空产生式，能推 ε if 'ε' not in first[nt]: first[nt].add('ε') changed = True continue for sym in prod: if sym in terminals: # 终结符直接进 FIRST if sym not in first[nt]: first[nt].add(sym) changed = True break # 非终结符：并入它的 FIRST（去掉 ε）， # 只有它能推 ε 才继续扫描下一个符号 before = set(first[nt]) first[nt] |= (first[sym] - {'ε'}) if first[nt] != before: changed = True if 'ε' not in first[sym]: break else: # 整个产生式右部都能推 ε if 'ε' not in first[nt]: first[nt].add('ε') changed = True for nt in sorted(first): print(nt, sorted(first[nt]))

代码逻辑说明：dict 的 key 是非终结符，value 是产生式列表，每个产生式是符号列表，空列表代表 ε。外层 while 是做固定点迭代，每次遍历所有产生式：产生式空则给 FIRST 加 ε；否则逐个符号扫，终结符直接加入并中断，非终结符把它的 FIRST 减掉 ε 并进来，只有该非终结符能推 ε 才继续扫下一个符号。跑完把结果和你手算及答案文档三方对照，差异能定位到具体符号。FOLLOW 集也可以用同样的固定点思路实现，只是传播规则多一条"A → αBβ 且 β 能推 ε 时并入 FOLLOW(A)"，建议单独写一个脚本，别和 FIRST 混在一起。

5.3 参数与边界：哪些题必须手算，哪些可以上工具

不是所有题都适合上工具。把课后题按"验证手段"和"考试要求"两个维度分四类，边界很清楚：

边界经验：凡是要进考场的题，一律手算为主，工具只做最后校验；凡是编译原理实验要交付的模块，一律工具为主，手算只用来理解工具的报错。把这两条分清，答案文档的作用就定位清楚了——它只属于"手算校验"那一侧。

6. 逆推答案：从结论倒推过程，一张表找出答案里的错

拿到任何一份课后题答案，先别急着对，抽一道"有唯一结论"的题做逆推。答案说这个 DFA 最小化后是 3 个状态，我就从终态集合出发，反做一轮可区分性划分，看能不能推到 3 个；答案说文法是 LL(1)，我就从预测分析表反推它隐含的 FIRST/FOLLOW 假设。逆推能走通，这份文档的信任等级提高一档；走不通，把它标成"存疑"，只留结论清晰的题做参考。

逆推的核心价值在于它同时训练两遍：正着做一遍是"从规则到结果"，倒着做一遍是"从结果反推规则"。两遍交叉验证出来的结论，比单纯对着答案抄要扎实得多。我在 5.1 那张表里专门加了一列"逆推结论"，凡是不一致的地方，回到教材规则本身上找原因——十次里有八次，问题是规则没兜住，而不是笔误。

说一个我的血泪经验：刚学编译原理那会儿，手头有一份答案文档，我对着抄了两章，直到一次模拟考才发现题号完全不同，整个第三章白抄。从那以后，我再也不信任何一份未经验证的 .doc，每份答案拿来先做抽样题号校验，再做逆推验证。答案文档是工具，不是教材；是校验器，不是标准答案。希望帮到你。

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