1. 项目概述一份“答案”的价值与边界最近在整理旧书又翻出了那本经典的《编译原理第三版》陈火旺院士主编的书页都泛黄了。每次看到第七章“中间代码生成”后面的那些习题还是会心头一紧。我猜很多计算机专业的学生或者正在自学编译原理的朋友都有过类似的体验对着那些关于四元式、三元式、DAG有向无环图和布尔表达式翻译的题目苦思冥想却总觉得差那么一点火候。网上流传着各种版本的“课后题答案”质量参差不齐有的甚至错误百出不仅没帮上忙反而把人带进了沟里。所以今天我想做的不是简单地给你一份“标准答案”——那样的东西网上或许能找到但价值有限。我更想和你一起像同行讨论问题一样把第七章的核心习题掰开揉碎讲清楚每道题背后的编译原理思想、解题的关键步骤以及我当年踩过的坑和总结出的技巧。编译原理不是一门靠死记硬背就能掌握的学科它需要理解代码从高级语言到低级语言乃至机器指令的“变形记”。课后题正是这个理解过程最好的试金石。无论是为了应对考试还是为了夯实基础、面试备战吃透这些题目远比抄对一个答案重要得多。2. 核心习题思路拆解与方法论第七章“中间代码生成”是整个编译过程的枢纽。词法分析和语法分析告诉我们程序在结构上是否正确而中间代码生成则开始关心“做什么”和“怎么做”。这一章的习题主要围绕几种主流的中间表示形式和它们的生成算法展开。2.1 四元式与三元式本质与转换四元式(op, arg1, arg2, result)和三元式(op, arg1, arg2)是最经典的中间代码形式。很多题目要求将一段简单的赋值或算术表达式翻译成这两种形式。解题核心思路建立临时变量序列这是最关键的一步。对于复杂的表达式编译器需要引入临时变量如 t1, t2, ...来存储中间计算结果。在翻译时心里要默默维护这个临时变量计数器。遵循运算优先级和结合性和手工计算表达式一样必须严格按照优先级先乘除后加减和结合性从左到右来分解表达式。可以先将表达式转换成对应的语法树或DAG然后以后序遍历的方式生成代码这样顺序自然就对了。注意三元式的“位置引用”四元式的结果字段显式指明了存放结果的变量或临时变量。而三元式的结果是隐式的它本身所在的位置即三元式编号就代表了它的结果。因此在三元式中引用之前计算的结果使用的是该三元式的编号。这是初学者最容易混淆的地方。实操心得遇到复杂的表达式我习惯先用铅笔在草稿纸上画出简化的语法树。树的所有内部节点都是运算符叶子节点是运算对象。然后从最底层的运算开始为每个内部节点的计算结果赋予一个临时变量并写下对应的四元式或三元式。这个过程能让你直观地看到临时变量是如何被创建和引用的极大减少错误。2.2 DAG有向无环图的优化应用DAG不是一种中间代码而是一种用于优化中间代码的数据结构。题目常给出一段基本块代码要求构造其DAG表示并利用DAG进行优化如删除公共子表达式、删除无用赋值。解题核心思路节点创建规则DAG的每个节点代表一个变量、常量或运算结果。核心原则是相同的值只用一个节点表示。例如如果两个地方都用到了变量a的值它们应该指向同一个节点。公共子表达式识别这是DAG的核心优化。当处理到像t2 a b这样的语句时首先检查DAG中是否已经存在一个“”节点其左子节点是a的节点右子节点是b的节点。如果存在就不创建新节点而是让t2的标记附加到这个已有节点上。这直接对应了优化中的“删除公共子表达式”。无用代码消除在DAG构造完成后只有那些有活跃变量标记或者说是最终输出结果依赖的节点才需要生成目标代码。如果一个节点的值没有被任何活跃变量引用那么为它生成的指令就是无用代码可以删除。示例步骤针对基本块(1) t1 a b (2) t2 a b (3) t3 t1 * t2 (4) t4 t3 (5) b t4构造DAG时语句(1)创建“”节点N1结果标记为t1。语句(2)发现相同的“”节点N1已存在因此将t2也标记在N1上而不是创建新节点。这就优化掉了一次ab的计算。注意事项DAG优化是在基本块内进行的。它无法优化跨基本块的公共子表达式。同时要特别注意像数组赋值A[i] x和A[j] y这样的语句除非能证明i和j绝对相等否则它们不能视为公共子表达式因为可能指向同一内存位置。在构造DAG时这类具有副作用的操作通常作为单独节点处理并可能打断优化。2.3 布尔表达式的短路计算与控制流翻译这是第七章的难点。题目通常给出一个布尔表达式如ab or cd and ef要求将其翻译成四元式序列并体现短路计算特性。解题核心思路理解短路语义对于A or B若A为真则整个表达式为真B无需计算。对于A and B若A为假则整个表达式为假B无需计算。翻译成的代码必须是能实现这种控制跳转的。使用“拉链-回填”技术这是解决此问题的标准且高效的方法。核心是维护两个“回填列表”truelist指向那些待填充“真出口”的四元式编号。falselist指向那些待填充“假出口”的四元式编号。翻译过程以ab or cd为例先翻译ab生成一个条件跳转四元式例如(j, a, b, _)。这个四元式的目标地址第四区段还不知道先填为“_”。此时这个四元式既需要真出口如果ab为真整个or表达式为真也需要假出口如果ab为假需要继续计算cd。因此它的编号同时加入truelist和falselist。翻译or运算符时首先回填falselist。将falselist中所有四元式的假出口即跳转地址设置为当前四元式序列的末尾即接下来要翻译cd的起始位置。然后or运算自身的truelist继承自ab的truelistfalselist则新建留给cd。接着翻译cd生成条件跳转四元式其编号加入新的truelist和falselist。最终整个表达式的truelist指向所有能跳转到“真”结果的四元式falselist指向所有能跳转到“假”结果的四元式。在后续翻译if或while语句时再用具体的目标地址回填这些列表。踩坑记录最容易出错的地方是and和or运算符对truelist和falselist的合并与传递逻辑。记住一个口诀E1 or E2的“假”出口需要穿过E1落到E2的起点而E1 and E2的“真”出口需要穿过E1落到E2的起点。画一个简单的控制流图来辅助理解会清晰很多。3. 典型课后题精讲与分步实现下面我们选取几个最具代表性的课后题模拟一遍完整的解题过程。请注意我的目的是展示方法和过程答案可能因对题目细节理解的微小差异而略有不同但思路是相通的。3.1 习题 7.1表达式到四元式/三元式序列题目简述将表达式-(ab)*(cd)-(abc)翻译成四元式序列和三元式序列。分步解析拆解表达式与引入临时变量这个表达式包含一元负号、加法和乘法。优先级最高的是括号和一元负号然后是乘法最后是减法。我们先处理最内层的(ab)和(cd)。生成四元式序列假设临时变量序列为T1, T2, T3...。(1) (, a, b, T1)// 计算 ab结果存T1(2) (, c, d, T2)// 计算 cd结果存T2(3) (*, T1, T2, T3)// 计算 T1 * T2即 (ab)*(cd)结果存T3(4) (, T3, _, T4)// 一元负操作计算 -T3结果存T4。这里用代表一元负。(5) (, a, b, T5)//注意再次计算 ab。虽然值与T1相同但在没有进行优化如公共子表达式删除的基本翻译中编译器会重新计算。优化是后续步骤。(6) (, T5, c, T6)// 计算 T5 c即 abc结果存T6(7) (-, T4, T6, T7)// 计算 T4 - T6即最终结果存T7生成三元式序列三元式没有result字段结果用该三元式的位置表示。(1) (, a, b)// 结果引用为 (1)(2) (, c, d)// 结果引用为 (2)(3) (*, (1), (2))// 乘法的参数是前两个三元式的结果(4) (, (3), _)// 对三元式(3)的结果取负(5) (, a, b)// 再次计算 ab结果引用为 (5)(6) (, (5), c)// 计算 (5) c(7) (-, (4), (6))// 最终计算关键点提示四元式序列中的步骤(5)在优化后的代码中是可以消除的通过重用T1。但在基础的、未经优化的中间代码生成阶段按照语法制导定义SDD或翻译方案Translation Scheme机械地翻译就会产生这样的代码。这恰恰体现了后续优化阶段如DAG优化的必要性。三元式中对之前结果的引用方式(编号)是必须掌握的要点。3.2 习题 7.4DAG构造与优化题目简述对基本块P构造DAG并假设只有L在基本块后是活跃的给出优化后的四元式序列。(0) P 0 (1) I 1 (2) T1 4 * I (3) T2 addr(A) - 4 (4) T3 T2[T1] // 假设为 A[I] 的取值操作 (5) T4 4 * I (6) T5 addr(B) - 4 (7) T6 T5[T4] // 假设为 B[I] 的取值操作 (8) T7 T3 * T6 (9) P P T7 (10) I I 1 (11) if I 20 goto (2)分步解析逐步构造DAG初始节点为常量0、1、4、20变量P、I、addr(A)、addr(B)创建叶节点。语句(2)T1 4 * I创建*节点左子节点是4右子节点是I的节点。标记该节点为T1。语句(4)T3 T2[T1]这是数组取值。创建一个[]或类似操作节点左子节点是T2即addr(A)-4的节点右子节点是T1的节点。标记为T3。注意数组访问通常视为具有副作用的操作且A和B是不同的数组因此A[I]和B[I]不是公共子表达式。语句(5)T4 4 * I发现已存在4 * I的节点即T1的节点。因此不创建新节点将T4也标记到该节点上。这就删除了公共子表达式4*I。语句(8)T7 T3 * T6创建*节点左子节点是T3的节点右子节点是T6的节点。标记为T7。语句(9)P P T7创建节点左子节点是P的当前节点初始为0右子节点是T7的节点。将P的标记移动到新节点意味着P获得了新值。语句(10)I I 1创建节点左子节点是I的当前节点右子节点是常量1。将I的标记移动到新节点。语句(11) 是控制流不直接影响DAG数据部分。根据DAG生成优化代码只有L在块后活跃但题目中未定义L。我们假设活跃变量是P和I因为循环要继续。DAG中只有那些根节点即没有父节点的节点或者标记了活跃变量的节点对应的计算需要生成代码。从DAG中我们可以提取出必须的计算步骤并消除无用赋值如对T1、T4的重复赋值对T2、T5的中间存储等。优化后的四元式序列可能如下(1) I 1 (2) T1 4 * I // 计算数组下标偏移被多次使用 (3) T2 addr(A) - 4 (4) T3 T2[T1] // 取 A[I] (5) T5 addr(B) - 4 // 原T5这里直接用了 (6) T6 T5[T1] // 取 B[I]注意使用了T1而不是重新计算4*I (7) T7 T3 * T6 (8) P P T7 (9) I I 1 (10) if I 20 goto (2)可以看到原语句(0)P0如果是在循环前初始化则不应在循环体内。原语句(5)T44*I被消除。代码得到了简化。深度思考DAG优化极大地依赖于“活跃变量分析”。如果某个临时变量如T2,T5在基本块后不再被使用且其值不影响活跃变量那么为它生成计算代码的语句甚至可以被删除如果该计算无副作用。在实际编译器中这需要更精细的数据流分析。3.3 习题 7.8布尔表达式短路计算翻译题目简述将布尔表达式ab or cd and ef翻译成四元式序列。其中and的优先级高于or。分步解析确定语法结构由于and优先级高表达式等价于ab or (cd and ef)。使用拉链-回填法我们用E表示表达式E.truelist和E.falselist分别表示其真假出口链。翻译E1 ab:生成四元式(1) (j, a, b, _)// 真出口未定假出口未定E1.truelist [1];E1.falselist [1]。翻译E2 cd and ef:先翻译E21 cd:生成四元式(2) (j, c, d, _)E21.truelist [2];E21.falselist [2]。处理and运算符回填将E21.truelist即[2]中的四元式的真出口全部设置为下一个四元式的地址。下一个要生成的是ef的代码假设其起始位置是3。所以回填后四元式(2)变为(2) (j, c, d, 3)。意思是如果cd为真就继续检查ef为假则整个and为假假出口待定。E2.falselist E21.falselist [2]这个2的假出口指向整个and表达式为假的位置待定。接着翻译E22 ef:生成四元式(3) (j, e, f, _)E22.truelist [3];E22.falselist [3]。合并为E2E2.truelist E22.truelist [3];E2.falselist merge(E21.falselist, E22.falselist) merge([2], [3]) [2, 3]。翻译E E1 or E2:处理or运算符回填将E1.falselist即[1]中的四元式的假出口全部设置为E2翻译代码的起始地址即地址2。回填后四元式(1)变为(1) (j, a, b, _)真出口仍为_和(1) (j, a, b, 2)假出口为2。实际上一个四元式只能有一个跳转目标。这里需要理解四元式(1)的语义是“如果ab为真则跳转到真出口否则顺序执行即假出口”。我们回填的是它的“顺序执行”路径即假出口。所以(1)保持不变但我们已经知道如果ab为假程序会顺序执行到(2)。E.truelist merge(E1.truelist, E2.truelist) merge([1], [3]) [1, 3]。E.falselist E2.falselist [2, 3]。最终四元式序列(1) (j, a, b, _)// 真出口待回填至整个表达式为真的目标地址T假出口隐式为(2)(2) (j, c, d, 4)// 如果cd为假跳转到整个表达式为假的地址F为真则执行(3)(3) (j, e, f, _)// 真出口待回填至T假出口待回填至F这里(1)的真出口和(3)的真出口都需要在后续翻译if或while时回填到同一个“真”目标T比如if语句的then部分入口。(2)和(3)的假出口需要回填到同一个“假”目标F比如if语句的else部分入口或下一条语句。技巧总结处理布尔表达式翻译一定要画出控制流图。把每个关系运算如ab看作一个条件判断的两路分支。and意味着“必须连续为真”所以前一个为真时流向后一个为假时直接流向假出口。or意味着“有一个为真即可”所以前一个为真时直接流向真出口为假时才流向后一个。用拉链-回填技术就是自动化地管理这些分支点的目标地址列表。4. 常见困惑、易错点与排查指南即使理解了原理在动手做题时也常会出错。下面是一些高频问题和我总结的排查技巧。4.1 四元式/三元式生成中的顺序错误问题表达式的计算顺序与优先级不符导致结果错误。排查画语法树这是最可靠的方法。画出表达式对应的语法树然后后序遍历这棵树。遍历顺序就是计算顺序也是生成四元式/三元式的顺序。检查临时变量确保每个中间结果都分配了唯一的临时变量并且在引用时使用的是正确的变量名或三元式编号。代入验证用一组简单的值如a1, b2, c3...代入你生成的四元式序列模拟执行一遍看最终结果是否与直接计算表达式的结果一致。4.2 DAG优化中公共子表达式识别遗漏问题未能识别出所有公共子表达式优化不彻底。排查严格遵循节点创建规则在DAG中值相同的表达式必须对应同一个节点。检查每个运算节点如,*的左、右子节点是否与已有节点完全相同。不仅要看运算符还要看子节点是否指向同一个DAG节点。区分“值”与“存储位置”这是关键。x y z和a y z如果y和z的值未改变那么yz是公共子表达式。但A[i] x和A[j] y即使i和j值相同由于无法确定A[i]和A[j]是否指向同一内存可能i和j是变量通常不作为公共子表达式消除除非有非常严格的别名分析。检查活跃变量只有最终被活跃变量引用的节点才需要生成代码。如果一个节点没有任何活跃变量标记那么以它为根的整个子树如果该子树没有其他活跃变量引用的计算都可以消除。4.3 布尔表达式翻译中拉链回填逻辑混乱问题truelist和falselist合并错误回填地址搞错。排查为每个E维护两个列表在翻译每个子表达式时清晰地列出它当前的E.truelist和E.falselist包含哪些四元式编号。掌握合并规则E E1 or E2:E.truelist merge(E1.truelist, E2.truelist);E.falselist E2.falselist。需要回填将E1.falselist中的四元式其“假出口”即顺序执行分支设置为E2代码的起始地址。E E1 and E2:E.truelist E2.truelist;E.falselist merge(E1.falselist, E2.falselist)。需要回填将E1.truelist中的四元式其“真出口”设置为E2代码的起始地址。画流图辅助在纸上画出简单的控制流标出E1为真/假时该去哪E2为真/假时该去哪。然后看or和and如何连接这两个流图回填点就一目了然。4.4 综合型题目中上下文信息缺失问题一些题目描述简略例如未说明哪些变量在基本块后是活跃的或者数组访问的细节。应对策略做出合理假设如果题目未说明活跃变量通常假设所有非临时变量即源程序中的变量都是活跃的而编译器生成的临时变量如T1, T2在块后不活跃。这符合最一般的场景。明确标注在你的答案中首先声明你的假设。例如“假设只有P和I在基本块出口活跃”或“假设数组访问T2[T1]表示A[I]”。这展示了你的思考过程即使最终答案与标准答案因假设不同而有差异思路正确也能获得大部分分数。关注核心考点课后题的目的往往是考察你对某个特定知识点的掌握比如DAG的构造过程、拉链-回填的算法步骤。确保你的解答清晰地展示了这个过程细节假设可以围绕核心考点自洽即可。编译原理的习题往往没有唯一的“标准答案”尤其是在涉及优化和假设时。重要的是展现出清晰的逻辑、正确的算法应用和对原理的深刻理解。希望这份超详细的“解题思路说明书”能帮你打通第七章的任督二脉。记住比起答案本身通往答案的这条路才是编译原理带给我们的真正财富。