简介第二版《编译原理》即龙书习题答案合集主要面向计算机专业本科生、考研复习者及自修编译原理的读者也适合作为以经典教材授课时的辅助参考。资料对应 Alfred V. Aho 等编著的经典版本整理了各章课后作业答案可用于作业核对、考前复习与难点梳理尤其适合需要对照教材逐章掌握词法分析、语法分析、中间代码生成等核心知识点的学习者。压缩包共 30 个文件以 13 个 doc 答案文档和 2 个 ppt 讲稿为主体另有 8 个 html 页面和 7 个 gif 图示整体仅 3.34MB便于离线阅读和按章节检索。内容覆盖第二章、第四章、第六章、第八章等课后作业答案还提供以龙书为教材的编译原理课件及第二、三章习题讲 PPT能够帮助读者在缺少参考答案时快速定位解题步骤、借助图示理解抽象流程教材虽出版较早部分技术已过时但核心习题仍是巩固编译原理基础的经典训练。目前已有 2034 人学习下载对课程复习和考研备考具有实用价值。1. 先说结论第二版龙书习题答案拿来当标准答案用会翻车聊第二版龙书习题答案之前先说个反直觉的结论网上流传的大多数答案并不能当作判断对错的基准。龙书是编译原理方向的经典教材那句封面上的龙几乎是几代人的共同记忆但它最大的特点是习题基本都是构造型作业——算 FIRST/FOLLOW 集、画 LR 状态机、写属性规则、生成三地址代码每一道题都在逼你亲手搭一个微缩编译器。找答案的人有的是赶作业有的是自学对答案但最终都会撞上同一个问题答案质量参差有的跳步有的改自第一版有的干脆是错的。这篇文章不是再给你一份答案清单而是把拿到一份答案之后怎么办这件事讲透。我会按题型拆开讲每类答案该怎么验、参数和步骤怎么查、哪些地方最容易踩坑。适合正在学编译原理、准备考试、或者带学生改作业的从业者。读完你至少能判断一件事手上这份答案值不值得信。2. 对答案前的第一步分清龙书四类习题的答案形态龙书第二版的习题横跨简单语法制导翻译到机器独立优化几乎每一章都在考构造而不是选择。这带来一个很实际的问题不同类型的题正确答案的形态完全不同对答案时看的东西也完全不同。拿最终结果表去对一道构造过程题永远对不出结果反过来拿过程去比结果表也会把自己绕晕。2.1 四类题型与完成标准一份参考答案该有什么、不该缺什么按产出物把习题分成四类比较实用。这里的判断直接决定你对答案时盯住哪个位置题型典型章节答案的产出物对答案时的检查重点词法分析第 3 章正则式、NFA/DFA、模拟器代码状态转移图是否完整输入串是否被一致接受/拒绝语法分析第 4、5 章消除左递归、FIRST/FOLLOW、LL/LR 分析表集合计算是否有遗漏冲突是否被合理处理语法制导翻译与类型检查第 5、6 章SDD/SDT、属性规则、注释分析树属性的依赖方向标注顺序能否走通中间代码与优化第 69 章三地址代码、基本块、数据流方程地址码与原表达式是否语义等价迭代是否收敛网上流传的第二版龙书习题答案来源通常有三类早年学生的手写扫描版、课程助教整理的讲义版、以及拿第一版作业直接改题号的改编版。判断一份答案值不值得信先看三件事一看是否带题号二看是否给出了中间构造过程三看有没有明确标注对应第二版还是第一版。三者都没有的建议直接换一份别浪费时间猜。再强调一下完成标准。以二义性证明题为例一道证明某表达式文法具有二义性的题合格答案必须给出同一个终结符串的两棵不同语法树而且两棵树的叶子从左到右完全一致。很多人对答案时只看画没画出两棵树忘了检查叶子序列于是把等价树错判成两棵不同树或者反过来把真正二义的文法判成了无二义。这是最常见的误判之一。还有一种情况是半个答案。第三章经常让给出正则式并构造对应的 NFA有些答案只给正则式NFA 直接不画。题目要求的是构造答案里却没有构造物这种就属于缺了一半。你需要的不是替它脑补而是明确题目考察点是什么、缺了哪一半然后自己补。2.2 过程比结果值钱用构造过程而不是最终表验对错我做习题时的习惯是不看最终答案先看答案里的构造过程。龙书的题几乎都是构造型的比如让你为一个文法构造 SLR 分析表。这种题的结果就是一张几十行的大表如果你只核对终表任何一个状态出错都会被淹没在表项里。反过来如果答案给出了项集族的构造过程你就能顺着状态编号从 I0 一路比对到 In把错误精确定位到某个闭包计算或移进/规约动作上。龙书的答案还有一个特性不唯一。比如 NFA 转 DFA子集构造法的状态命名顺序不同会得到两组名字完全不同的 DFA但接受的语言完全一样。消除左递归也一样常见版本把 E → E T | T 改成 E → T E、E → T E | ε这个版本接受的语言和原文法一致但语法树的形状变了。如果题目只要求消除左递归两个版本都算对如果题目带了语义动作语义动作必须跟着树形调整否则结合性会变。所以对答案时语言等价和语义等价要分开判断。我一般会用抽样对拍选三五个有代表性的输入串比如单个 id、两个 id 相加、乘加混合、带括号的嵌套表达式分别拿自己的构造和答案的构造跑一遍接受/拒绝结论全部一致再下结论。这个习惯成本很低但能过滤掉绝大多数低级错误。如果答案只有结果没有过程别直接信把它当成已给结论自己把过程补出来再验证。3. 验证语法分析题答案FIRST/FOLLOW 自查与 LR 状态机比对语法分析题是翻车重灾区因为它的结果往往是一张表错一格都不容易看出来。我的经验是先验集合再验状态机两层都过了才敢说这份答案能信。3.1 FIRST/FOLLOW 手算的四个检查点从 ε 传播到集合闭包先拿一份网上答案多半会在 FIRST/FOLLOW 计算上出问题。我验证时用下面这个文法做基准它是表达式文法消除左递归后的标准形态E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | id手算这套集合我给自己定了四个检查点按顺序走一遍基本能覆盖所有常见错误第一ε 只进 FIRST绝不进 FOLLOW。先圈出所有能推导出 ε 的非终结符这里是 E 和 T。如果答案的 FOLLOW 集里出现了 ε直接判错没有商量余地。第二FIRST 的闭包传播至少要跑两轮。E → T ET → F TF → ( E ) | id所以 FIRST(E)、FIRST(T)、FIRST(F) 三者相同都等于 {(, id}。如果你算出的 FIRST(E) 缺了 ( 或 id八成是没从 F 一级一级往上冒。第三FOLLOW 里右部末尾非终结符这条规则最容易漏。比如 E → T E 中 E 在右部末尾FOLLOW(E) 就必须继承 FOLLOW(E)同理 T → F T 中 T 继承 FOLLOW(T)。第四逐条扫产生式右部确认每个终结符都进去了。比如 E → T E说明 FOLLOW(T) 里必须有 。按照这套检查点算出来的正确答案如下可以直接当基准表用非终结符FIRSTFOLLOWE{ ( , id }{ ) , $ }E{ , ε }{ ) , $ }T{ ( , id }{ , ) , $ }T{ * , ε }{ , ) , $ }F{ ( , id }{ * , , ) , $ }提示算完 FOLLOW 之后把每个非终结符的 FIRST 和 FOLLOW 并排摆在一起扫一眼。如果某个终结符同时出现在 FIRST(T) 和 FOLLOW(T) 里放在 LL(1) 预测分析表里就会制造冲突这往往是答案错误的信号。3.2 用 bison 状态表照妖SLR/LALR 状态比对的三处细节FIRST/FOLLOW 过了之后下一步验 LR 状态机。构造 LR 自动机是纯机械过程人算容易出错但不该靠感觉判断谁对谁错。常见做法是拿 bison 生成的状态报告当参照跟你手算的项集族逐状态比对。# 把答案给出的文法写进 parser.y用 bison 生成状态报告 bison -v -o parser.c parser.y # 状态报告会输出到 parser.output一个可用的文法文件长这样%token ID %left %left * %% E : E T | T ; T : T * F | F ; F : ( E ) | ID ;这里加了两行 %left 声明原因是这个表达式文法在输入 ididid 时会出现移进-规约冲突解析器看到一个已经规约好的 E后面又跟着 既可以继续移进 去扩展更长的表达式也可以立即规约。%left 表示遇到 时优先规约也就是让加法左结合。这一步恰好呼应教材里结合性由文法和语义动作共同决定的结论。生成了 parser.output 之后里面是完整的规范状态表。每个状态里都有一个.表示解析器当前扫描到的位置比如 E → E · T 表示已经看到 E、下一个期待 。和你手算的项集族比对时注意三处细节第一状态编号没有意义比的是状态内容和转移关系。两组自动机状态编号不同很正常别因为编号对不上就认定错了。第二起点状态里必须有增广产生式 S → ·E终点状态必须能对 $ 执行接受动作这两条是硬指标。第三bison 默认做 LALR会合法合并同核状态你手算 SLR 不合并所以你的状态数比它多反而可能是正常的。反过来如果你的状态数比答案少那才要警惕答案是不是漏了状态。没有工具环境的时候还有一个纯手工的走表验证法选一个 6 到 10 个符号的终结符串比如 id id * id按查动作 → 移进或规约 → 看新状态的流程在答案给的分析表上走一遍。走到某一步发现查不到动作或者同时查到两个动作问题就定位到了。这张表加一支笔就能做能过滤掉绝大多数错误答案。4. 验证语义分析与中间代码答案属性重演与反向还原语法分析题验的是结构语义题和中间代码题验的是行为。结构错了肉眼能看出来行为错了往往要跑一遍才知道。对这类答案我的方法是把答案倒过来执行。4.1 属性计算重演先查 SDD 的依赖方向再动手标注语法制导定义题的答案是一组属性规则。对答案之前先问三个问题综合属性是否只依赖子节点和自己的其他属性继承属性是否来自父节点或左兄弟所有属性能否按自底向上或自顶向下的顺序排出一个合法的计算序列。三个问题有一个答不上来这份答案就不可信。具体到验证方式我管它叫属性计算重演拿题目的输入串画出具体语法树再按答案的属性规则一层层往上标属性。标到哪里算不下去答案就断在哪里。举一个最简单的例子产生式语义规则E → E1 TE.val E1.val T.valE → TE.val T.valT → T1 * FT.val T1.val * F.valT → FT.val F.valF → ( E )F.val E.valF → numF.val num.lexval对输入 2 3 * 4 走一遍先标叶子 2、3、4再往上标 F.val、T.val然后 T.val 3 * 4 12最后 E.val 2 12 14。如果答案的规则把加法排在乘法前面最终值会变成 20当场就能判定语义规则与文法结构冲突。继承属性的验证更麻烦一点常见场景是声明语句把类型从左往右传给标识符列表。检查点只有一个继承属性必须从产生式右部靠前的符号流向右部靠后的符号也就是从左到右。如果答案把继承属性写成从子节点往父节点传或者依赖右侧兄弟那这个 SDD 就不是 L-属性定义很多自顶向下翻译方案根本没法执行。4.2 三地址代码反向还原用 DAG 判断答案的语义等价性三地址代码题对答案我推荐反向翻译法把答案给的三地址代码逐条反推还原成表达式树或 DAG再和题目原表达式比对。比如原式 a b * -c b * -c一份朴素答案可能长这样t1 -c t2 b * t1 t3 -c t4 b * t3 t5 t2 t4 a t5还原的时候把它读成一棵树a 由 t2 和 t4 相加得到t2 是 b * -ct4 也是 b * -c。此时你会看到左右两棵子树完全相同这就是公共子表达式。优化后的版本只需要三行核心代码t1 -c t2 b * t1 a t2 t2两个版本语义等价但行数差了一倍。对答案时看到这种差异别急着判错先判断题目有没有要求指出公共子表达式或优化。如果题目只要求翻译两个版本都算对如果要求优化朴素版本就是没做完。反向还原时重点检查三个位置。一是临时变量使用前必须已经赋值把代码按顺序连成依赖图有环说明答案引用了未定义的值。二是布尔表达式短路求值的翻译龙书在中间代码这一章特别喜欢考短路答案里的跳转标号应当成对出现真出口和假出口各有一个明确位置漏了 goto 或把标号写反是高频错误。三是数组下标计算a[i] 的翻译必须先算 i再按元素宽度算偏移最后加基址如果答案里下标计算顺序颠倒还原出的树就跟原式对不上。if a b goto Ltrue t 0 goto Lend Ltrue: t 1 Lend:上面这个布尔赋值片段里Ltrue 和 Lend 各被引用一次结构干净。错误答案常见把 Ltrue 和 Lend 写反或者漏掉第二行的 goto导致真假两条路径汇合不到同一个出口。4.3 数据流方程答案迭代结果与初始化的两个检查点数据流分析题到了第 9 章答案往往是一组集合方程和迭代结果。对答案时先确认分析方向到达定值分析是前向活跃变量分析是后向。方向反了迭代必然不收敛或者收敛到一个明显离谱的结果。第二个检查点是初值前向分析里到达定值常用空集初始化可用表达式则要用全集初始化因为一个表达式只有对所有路径都可用才算可用从空集开始迭代会得出什么都可用的错误结论。分析方向常用初值典型的错误写法到达定值前向空集把 IN/OUT 方程写反可用表达式前向全集初值写成空集活跃变量后向空集方向搞反迭代不收敛验证时还有个笨办法手动迭代两轮看集合是否还在变。如果一轮之内集合就完全不动要么是初始集合给得太大要么是方程根本没起到传播作用。把答案的方程拿去照样迭代一遍收敛结果和答案不一致那答案的迭代过程大概率有跳步。5. 避坑指南第二版龙书习题答案最常见的四个翻车点这一章写我这些年对答案时踩过的坑每条都是现象 → 原因 → 解决的结构。如果你对答案对到怀疑人生先按这个清单排查比重新算一遍更快。5.1 版本与题号错位答案对不上的第一嫌疑现象答案分析的文法和教材某道题长得完全不像题号倒是能对上。原因这份答案可能基于第一版作业改写第二版调整了部分题目的数字和文法甚至换了章节位置。解决先别碰内容把题号对应的题干原文抄下来和书上逐字核对数字对不上就当另一道题处理内容再像也不能直接采纳。5.2 FIRST/FOLLOW 里的 ε 处理不当现象自己的 FIRST 集和答案差一个 ε或者答案的 FOLLOW 集里躺着 ε。原因ε 的可达性没有跑透比如 E → T E | ε 这种产生式ε 会通过 E 影响到包含它的所有产生式的 FIRST 集而 FOLLOW 集定义里明确不含 ε把 FIRST 的结果直接搬过来就错了。解决用第 3.1 节的四个检查点重跑一遍重点检查ε 是否只进 FIRST和闭包是否跑了两轮。5.3 把 LALR 的状态合并当成漏状态现象答案的状态数明显少于自己手算的数量认为自己找到了一处致命错误。原因答案是 LALR 构造合法合并了同核状态你手算的是 SLR不合并所以数量多。解决先判断两个状态是否同核也就是状态里的项目集合不含向前看符号是否完全相同。同核合并是标准做法不是漏状态。真正的错误是合并了不同核的状态那会改变语言可以直接判错。5.4 用行顺序判断三地址代码对错现象自己翻译的三地址代码和答案顺序不同但看着都挺对。原因临时变量命名不同、公共子表达式有没有提取、基本块划分粒度不同都会造成行级差异。解决把两边代码都还原成 DAG按 4.2 节的方法比对树形结构。叶子顺序一致、运算符优先级一致就算语义等价还原后结构不同再去逐行核对是哪一步翻译出了问题。6. 把答案做成自己的回归集两周后还能验错的习惯工具和方法都是别人的最后还得落到自己的习惯上。我现在对习题的标准动作是每道题留一份可复现过程记下日期、跳过的步骤和当时卡住的位置。两周之后不看答案重做一遍能独立走通才算真正会了走不通的地方就是下一轮要补的课。我还会维护一份私人勘误表网上答案错在哪一格、我修正成了什么、依据是哪条定义。这份勘误表比任何下载来的答案集都可靠因为它记录了完整的决策链。高频复用的验证命令我也会整理成一个小脚本比如把常练的十几条文法存成 .y 文件一条 bison -v 命令就能生成状态报告验证一道题从手算到工具对照不超过三分钟。最后说一个我自己的教训早些时候对一份 SLR 分析表答案直接采信没做走表验证结果整个翻译流程在某个状态上反复出错排了一晚上才发现答案的状态转移少了一条边。从那以后我只把习题答案当参考实现不当标准输出。参考实现的意义是帮你定位分歧而不是替你做决定。希望帮到你。本文还有配套的精品资源点击获取