1. 项目概述一份“硬核”课后答案的诞生记如果你正在啃陈火旺院士那本经典的《编译原理》第三版并且卡在了第六章那么你找对地方了。第六章“中间代码生成”绝对是整本书的一个分水岭它不像前面的词法、语法分析那样有相对固定的套路也不像后面的代码优化和目标代码生成那样目标明确。这一章是真正考验你是否把前面学的“形式化”知识转化为解决“工程化”问题的能力。我自己当年学的时候对着课后那些看似简短、实则千变万化的题目也没少挠头。网上流传的答案要么语焉不详要么步骤跳跃对于自学者来说看懂了答案却不知道答案是怎么“想”出来的等于没学。所以我决定做这件事不是简单地罗列第六章课后题的最终答案而是完整呈现每一道典型题目的解题思路、决策过程和背后的编译原理思想。我的目标是让你拿到这份资料后不仅能核对结果更能理解面对一个语法结构应该如何设计合适的中间表示形式在生成三地址码或四元式时遇到嵌套、跳转、数组访问具体的翻译方案Translation Scheme该如何一步步展开那些“临时变量”和“标号”究竟从何而来这份“答案”的核心价值在于过程而非仅仅一个结果。它适合所有被第六章“卡住”的同学无论你是为了备考还是为了真正掌握编译器的核心构造环节。2. 解题核心思想与中间代码形式选择在动手解答具体题目前我们必须统一思想明确我们手中的“武器”是什么。第六章主要引入了两种主流的中间表示形式三地址码和四元式。它们本质是等价的只是表现形式不同。三地址码的格式通常是x y op z非常直观像一种简单的抽象汇编。它的优势是易于人工阅读和书写我们在推导和思考时用三地址码会更顺畅。例如对于一个赋值语句a b c * d我们很自然地会想先计算t1 c * d再计算t2 b t1最后a t2。四元式则更结构化格式为(op, arg1, arg2, result)。它明确区分了操作符和操作数更适合作为编译器内部的数据结构。比如上面的例子对应的四元式序列是(*, c, d, t1),(, b, t1, t2),(, t2, _, a)。注意赋值操作在四元式中通常也用表示并且是二目操作arg2为空。关键选择在本答案中我将主要使用三地址码作为推导和展示的媒介因为它更符合人类的思维步骤。但在最终答案呈现时对于部分题目我会同时给出四元式序列以便你对照理解。你需要明白从三地址码到四元式的转换是机械的、一一对应的。另一个核心思想是语法制导翻译。我们不再是孤立地看表达式或语句而是将它们嵌入到产生式中并为每个产生式关联一系列的语义动作生成代码的动作。第六章的课后题绝大部分都是在训练你根据给定的语法设计或应用这些语义动作。例如对于控制流语句if (E) S1 else S2其核心翻译方案是为E生成代码结果保存在某个临时变量中并设置条件跳转。为S1和S2分别生成代码。需要解决的关键问题是标号Label的管理E.true条件为真时跳往的标号E.false条件为假时跳往的标号以及S.next整个if语句执行完毕后的出口标号。这些标号需要在生成代码的过程中被正确地回填Backpatch。3. 典型题型深度解析与手把手推导第六章的题目大致可以分为几类表达式翻译、数组元素引用翻译、控制流语句翻译以及布尔表达式翻译。我们挑出最具代表性的题目进行“慢动作”回放式推导。3.1 表达式与赋值语句的翻译这是最基础的一类题目标是熟练应用简单的语法制导定义SDD或翻译方案Translation Scheme。例题基于习题6.1风格为赋值语句S - id E;设计翻译方案并生成a b * -c b * -c的三地址码。推导过程定义翻译方案我们采用教材中常见的方案。假设非终结符E有综合属性E.addr表示存放表达式值的临时变量名或名字。S - id E; { gen(id.lexeme E.addr); } E - E1 T { E.addr newtemp(); gen(E.addr E1.addr T.addr); } E - T { E.addr T.addr; } T - T1 * F { T.addr newtemp(); gen(T.addr T1.addr * F.addr); } T - F { T.addr F.addr; } F - ( E ) { F.addr E.addr; } F - - F1 { F.addr newtemp(); gen(F.addr uminus F1.addr); } // 注意单目减 F - id { F.addr id.lexeme; }这里gen()是生成三地址码的函数newtemp()生成一个新的临时变量名如 t1, t2。为a b * -c b * -c手动推导解析树自底向上看。首先处理右边的表达式b * -c b * -c。-c是一个因子F。根据F - - F1F1是c生成代码t1 uminus c。F.addr t1。b * -c是一个项T。T1是bF是t1生成代码t2 b * t1。T.addr t2。同理另一个b * -c生成t3 b * t1。注意这里优化器会发现-c是公共子表达式但中间代码生成阶段通常不处理所以会重复计算生成t4 uminus c; t3 b * t4。我们按标准翻译来。表达式E是t2 t3生成代码t5 t2 t3。E.addr t5。最后赋值语句S生成a t5。生成的三地址码序列t1 uminus c t2 b * t1 t3 uminus c // 注意这是另一个相同的计算 t4 b * t3 t5 t2 t4 a t5对应的四元式序列(uminus, c, _, t1) (*, b, t1, t2) (uminus, c, _, t3) (*, b, t3, t4) (, t2, t4, t5) (, t5, _, a)实操心得在推导表达式时一定要“画”出语法分析树哪怕在脑海里然后严格地自底向上、从左到右地应用语义动作。每应用一个产生式就立即写下生成的代码和属性值。临时变量t1, t2...的编号顺序就是它们被创建的顺序这能有效避免混乱。3.2 数组元素引用的翻译这是第六章的重点和难点核心在于计算数组元素的地址。需要掌握“数组元素地址计算”的公式以及如何将其分解为一系列三地址码。例题基于习题6.3风格设数组声明为int A[10][20]每个元素占4个字节按行存放。翻译赋值语句x A[i][j]。推导过程理解地址计算公式对于二维数组A[l1][l2]l110, l220元素A[i][j]的地址相对于数组基址base为addr base ( i * l2 j ) * w其中w4是元素宽度。 我们可以将其分解为t1 i * 20,t2 t1 j,t3 t2 * 4,t4 base t3。最后x *t4加载操作。假设的翻译方案我们简化处理假设语法是S - id Elist ]Elist产生下标列表。其语义动作需要计算Elist.place存放最终偏移量的临时变量和Elist.ndim维数计数。这里我们直接进行语义计算。生成三地址码首先计算行偏移t1 i * 20然后加上列索引t2 t1 j接着转换为字节偏移t3 t2 * 4假设A的基址在某个符号表条目中我们仍用A表示。计算元素地址t4 A t3这里A被当作常量基址处理最后加载值并赋值x *t4在有些三地址码表示中可能用t5 A[t3]的形式意指以A为基址t3为偏移取内容所以完整的三地址码为t1 i * 20 t2 t1 j t3 t2 * 4 t4 A t3 x *t4对应的四元式(*, i, 20, t1) (, t1, j, t2) (*, t2, 4, t3) (, A, t3, t4) (, *t4, _, x) // 这里用‘’表示加载可能不够精确更常见的是用专门的 load 操作更精确的三地址码可能会区分操作例如使用x A[t3]这种形式隐含了加载。注意事项数组翻译极易出错的地方有两个一是维度计算顺序必须严格按照声明和公式来二是元素宽度乘法的位置必须在所有下标计算完成后乘而不是每维都乘。在题目中一定要先看清数组的声明方式行优先还是列优先、下标起始值通常是0和元素大小。3.3 控制流语句的翻译if-then-else这是另一个核心涉及标号生成、回填等关键技术。例题基于习题6.4风格为if (E) S1 else S2设计翻译方案并翻译if (a b) x 1; else x 2;。推导过程定义翻译方案关键属性S.next 语句S执行后应跳往的标号。E.true,E.false 表达式E为真/假时应跳往的标号。newlabel(): 生成一个新标号的函数。gen(): 生成代码。backpatch(list, label): 回填函数将list中所有待填标号的位置都填上label。一个经典的翻译方案如下S - if ( E ) M1 S1 N else M2 S2 { backpatch(E.true, M1.instr); backpatch(E.false, M2.instr); S.next merge(S1.next, merge(N.next, S2.next)); } M - ε { M.instr nextinstr; } // 记录下一条指令的地址标号 N - ε { gen(‘goto _’); N.next makelist(nextinstr-1); } // 生成无条件跳转其目标待填翻译if (a b) x 1; else x 2;步骤1:处理E: a b。生成条件跳转代码。假设我们生成100: if a b goto _(E.true 列表指向这条指令的地址 100)101: goto _(E.false 列表指向地址 101)步骤2:遇到M1记录下一条指令地址M1.instr 102。步骤3:处理S1: x 1;。生成代码102: x 1。S1.next是一个空列表表示没有未决跳转。步骤4:遇到N生成无条件跳转103: goto _。N.next是一个包含地址103的列表。步骤5:遇到M2记录下一条指令地址M2.instr 104。步骤6:处理S2: x 2;。生成代码104: x 2。S2.next为空列表。步骤7:执行语义动作中的回填和合并backpatch(E.true, 102): 将地址100的goto _填为goto 102。backpatch(E.false, 104): 将地址101的goto _填为goto 104。S.next merge(空, merge([103], 空)) [103]。这个S.next列表包含了S执行完后需要跳过的else部分后面的指令地址即103: goto _的目标待填。通常这个S.next会在外层语句比如一个顺序语句块中被回填到S之后的下一条指令地址。最终生成的三地址码标号已回填100: if a b goto 102 101: goto 104 102: x 1 103: goto ? // 这个标号‘?’等待外层语句回填假设外层下一条指令是105 104: x 2假设外层将103回填为105则最终代码为100: if a b goto 102 101: goto 104 102: x 1 103: goto 105 104: x 2 105: ... // 后续语句避坑技巧控制流翻译最容易晕的地方是标号列表的维护。一个有效的方法是画流程图。把if-else结构画成基本块E.true指向S1的入口E.false指向S2的入口。S1和S2的出口都指向同一个合并点即S.next指向的位置。这样N生成的那个goto就是为了让执行完S1后能跳过S2直接到达合并点。在纸上画出这个流程标号该回填到哪里就一目了然。3.4 布尔表达式的短路计算翻译布尔表达式的翻译与控制流紧密相关同样涉及大量回填。例题基于习题6.5风格翻译布尔表达式a b or c d and e f采用短路计算方式。推导过程理解短路计算对于or如果左边为真则整个表达式为真无需计算右边。对于and如果左边为假则整个表达式为假无需计算右边。因此我们需要为E.true和E.false设置跳转。翻译方案简化版思想对于E - E1 or M E2backpatch(E1.false, M.instr); E.true merge(E1.true, E2.true); E.false E2.false;对于E - E1 and M E2backpatch(E1.true, M.instr); E.false merge(E1.false, E2.false); E.true E2.true;对于E - id1 relop id2生成代码if id1 relop id2 goto _(加入E.true列表) 和goto _(加入E.false列表)。翻译a b or c d and e f我们按优先级and高于or所以结构是(ab) or ((cd) and (ef))。处理E1: a b:生成代码100: if a b goto _(E1.true [100])101: goto _(E1.false [101])处理E2: c d and e f:先处理E21: c d。生成代码102: if c d goto _(E21.true [102])103: goto _(E21.false [103])遇到M记录位置M.instr 104。处理E22: e f。 生成代码104: if e f goto _(E22.true [104])105: goto _(E22.false [105])应用and规则backpatch(E21.true, 104)将102处的目标填为104。E2.false merge([103], [105]) [103,105]。E2.true [104]。应用or规则遇到另一个M记录位置M.instr 106。backpatch(E1.false, 106)将101处的目标填为106。E.true merge([100], [104]) [100, 104]。E.false [103, 105]。生成的三地址码部分回填后100: if a b goto _ // 目标待填属于E.true列表 101: goto 106 // E1.false已回填 102: if c d goto 104 // E21.true已回填 103: goto _ // 属于E.false列表 104: if e f goto _ // 属于E.true列表 105: goto _ // 属于E.false列表 106: ... // E2的起始点这里E.true列表[100, 104]和E.false列表[103, 105]将在该布尔表达式被用于if或while语句时被回填到相应的目标标号。常见问题短路计算翻译中最容易混淆的是E.true和E.false列表的合并merge与回填backpatch对象。记住一个原则or操作关心的是“真”出口的合并和“假”出口的回填and操作关心的是“假”出口的合并和“真”出口的回填。画出示意图明确每个列表里存放的是哪些指令地址需要被填充能极大降低出错率。4. 综合应用题与代码优化初探有些题目会将多种结构结合在一起并可能涉及简单的优化思想。例题综合题翻译以下代码片段为三地址码while (i 10) { if (A[i] 0) { sum sum A[i]; } i i 1; }假设A是一维整型数组下标从0开始每个元素占4字节。推导过程整体结构分析这是一个while循环循环体包含一个if语句和一条赋值语句。我们需要为while和if生成标号。L_begin: 循环条件判断开始处。L_true: 循环条件为真进入循环体。L_false: 循环条件为假退出循环。L_if_true:if条件为真时执行的代码块。L_if_out:if语句执行完毕后的出口即i i 1之前。逐步翻译生成循环开始标号L_begin:翻译循环条件i 10:生成条件跳转。t1 i 10(假设这是三地址码的比较操作结果在t1)if t1 0 goto L_false(如果假跳往循环出口)goto L_true循环体入口L_true:翻译if (A[i] 0):先计算A[i]的地址和值。计算数组偏移t2 i * 4(元素宽度为4)计算元素地址t3 A t2(A是基址)加载元素值t4 *t3(或t4 A[t2])判断条件t5 t4 0if t5 0 goto L_if_out(条件为假跳过 then 部分)goto L_if_trueif的 then 部分L_if_true:sum sum t4(使用之前加载的t4)if语句出口L_if_out:翻译i i 1:i i 1生成跳回循环开始的指令goto L_begin循环出口L_false:完整的三地址码序列L_begin: t1 i 10 if t1 0 goto L_false goto L_true L_true: t2 i * 4 t3 A t2 t4 *t3 t5 t4 0 if t5 0 goto L_if_out goto L_if_true L_if_true: sum sum t4 L_if_out: i i 1 goto L_begin L_false: ... // 后续代码优化点提示在基础的中间代码生成阶段我们通常不进行复杂优化但一些显而易见的优化可以提一下。例如在这个循环中t2 i * 4的计算每次循环都依赖i而i在循环中递增。更优化的代码可能会将数组访问的基址计算提到循环外或者在循环内使用强度削弱Strength Reduction将乘法转化为加法。但作为第六章的课后题答案生成上述清晰、正确的代码已经达到了考核要求。理解这个生成过程是后续学习代码优化的基础。5. 常见错误排查与学习建议在完成第六章习题时以下几个错误非常普遍数组地址计算错误这是最高频的错误。务必确认维数、各维长度、下标起始值通常是0、元素大小。公式base ( (i1 * l2 i2) * l3 i3 ... ) * w必须烂熟于心。建议对每一道数组题都先把这个公式写出来再分解为三地址码。控制流标号管理混乱特别是嵌套的if-else和while。强烈建议画控制流图。把每个基本块一段顺序执行的代码画成一个方框用箭头连接跳转关系。在图上标出E.true,E.false,S.next等属性应该指向哪里回填动作就变得非常直观。布尔表达式短路计算中列表合并错误记住merge函数只是将两个标号列表合并成一个新列表而backpatch是将一个列表中的所有指令地址都填上同一个目标标号。混淆这两个操作会导致跳转目标完全错误。做题时可以在每条生成的跳转指令后面用注释标明它当前属于哪个列表如// E.true。临时变量重复使用或生命周期混淆在复杂的表达式中临时变量t1, t2...是顺序生成的。但在控制流分支中要小心同一个临时变量名在不同分支中被定义和使用的情况。在简单的语法制导定义中通常假设每次调用newtemp()都返回一个新名字所以问题不大。但在理解数据流时需要意识到不同路径可能定义同名变量这属于后续优化分析的范畴。给学习者的建议亲自动手编译原理是“做”出来的学问。只看答案不动手永远无法真正掌握。找一张白纸从最简单的表达式开始一步步推导写下每一步生成的代码和属性值。聚焦“翻译方案”第六章的精髓是那几个经典的翻译方案赋值、数组、控制流、布尔表达式。不要死记硬背要理解每个语义动作的意图。比如为什么if-else语句里需要那个N产生式因为它要生成一个跳过else部分的goto指令。利用工具辅助理解如果有条件可以尝试使用像ANTLR或Flex/Bison这样的工具实际实现一个小型的语法制导翻译器。亲眼看到输入字符串变成一串三地址码会对整个过程有颠覆性的认识。关联前后章节把第六章看作一个承上启下的枢纽。前面章节的词法、语法分析为你提供了分析树这一章的中间代码生成是结果后续的代码优化和目标代码生成则以此结果为输入。思考一下你生成的三地址码如何方便后续的优化如何容易地映射到目标机器的指令这样能建立起知识网络。这份“答案”的撰写过程也是我对自己编译原理知识的一次重新梳理和巩固。其中涉及的每一个步骤、每一个临时变量、每一个标号都蕴含着编译器将高级语言抽象映射到低级表示的核心逻辑。希望这份注重过程的解析能帮你穿透习题的表面真正触摸到编译技术中那部分充满设计美感的工程实践。如果在推导某个具体题目时遇到了卡点不妨回到最基础的翻译方案画一画语法树标一标属性流一步步来编译原理的世界会逐渐在你眼前清晰起来。