编译原理中间代码生成：三地址码与四元式实战解析

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，其核心翻译方案是：

1. 为E生成代码，结果保存在某个临时变量中，并设置条件跳转。
2. 为S1和S2分别生成代码。
3. 需要解决的关键问题是标号（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的三地址码。

推导过程：

1. 定义翻译方案：我们采用教材中常见的方案。假设非终结符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。

2. 为a = b * -c + b * -c手动推导：

   • 解析树自底向上看。首先处理右边的表达式b * -c + b * -c。
   • -c是一个因子F。根据F -> - F1，F1是c，生成代码t1 = uminus c。F.addr = t1。
   • b * -c是一个项T。T1是b，F是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。

3. 生成的三地址码序列：

   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]。

推导过程：

1. 理解地址计算公式：对于二维数组A[l1][l2]（l1=10, l2=20），元素A[i][j]的地址（相对于数组基址base）为：addr = base + ( i * l2 + j ) * w，其中w=4是元素宽度。 我们可以将其分解为：t1 = i * 20,t2 = t1 + j,t3 = t2 * 4,t4 = base + t3。最后x = *t4（加载操作）。

2. 假设的翻译方案：我们简化处理，假设语法是S -> id = Elist ]，Elist产生下标列表。其语义动作需要计算Elist.place（存放最终偏移量的临时变量）和Elist.ndim（维数计数）。这里我们直接进行语义计算。

3. 生成三地址码：

   • 首先，计算行偏移：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;。

推导过程：

1. 定义翻译方案（关键属性）：

   • 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); } // 生成无条件跳转，其目标待填

2. 翻译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之后的下一条指令地址。

3. 最终生成的三地址码（标号已回填）：

   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，采用短路计算方式。

推导过程：

1. 理解短路计算：对于or，如果左边为真，则整个表达式为真，无需计算右边。对于and，如果左边为假，则整个表达式为假，无需计算右边。因此，我们需要为E.true和E.false设置跳转。

2. 翻译方案（简化版思想）：

   • 对于E -> E1 or M E2：backpatch(E1.false, M.instr); E.true = merge(E1.true, E2.true); E.false = E2.false;
   • 对于E -> E1 and M E2：backpatch(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列表)。

3. 翻译a < b or c > d and e == f：我们按优先级，and高于or，所以结构是(a<b) or ((c>d) and (e==f))。

   • 处理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]。

4. 生成的三地址码（部分回填后）：

   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字节。

推导过程：

1. 整体结构分析：这是一个while循环，循环体包含一个if语句和一条赋值语句。我们需要为while和if生成标号。

   • L_begin: 循环条件判断开始处。
   • L_true: 循环条件为真，进入循环体。
   • L_false: 循环条件为假，退出循环。
   • L_if_true:if条件为真时执行的代码块。
   • L_if_out:if语句执行完毕后的出口（即i = i + 1之前）。

2. 逐步翻译：

   • 生成循环开始标号：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 > 0
     • if t5 == 0 goto L_if_out(条件为假，跳过 then 部分)
     • goto L_if_true
   • if的 then 部分：L_if_true:
     • sum = sum + t4(使用之前加载的t4)
   • if语句出口：L_if_out:
   • 翻译i = i + 1:i = i + 1
   • 生成跳回循环开始的指令：goto L_begin
   • 循环出口：L_false:

3. 完整的三地址码序列：

   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. 常见错误排查与学习建议

在完成第六章习题时，以下几个错误非常普遍：

1. 数组地址计算错误：这是最高频的错误。务必确认：维数、各维长度、下标起始值（通常是0）、元素大小。公式base + ( (i1 * l2 + i2) * l3 + i3 ... ) * w必须烂熟于心。建议对每一道数组题，都先把这个公式写出来，再分解为三地址码。

2. 控制流标号管理混乱：特别是嵌套的if-else和while。强烈建议画控制流图。把每个基本块（一段顺序执行的代码）画成一个方框，用箭头连接跳转关系。在图上标出E.true,E.false,S.next等属性应该指向哪里，回填动作就变得非常直观。

3. 布尔表达式短路计算中列表合并错误：记住merge函数只是将两个标号列表合并成一个新列表，而backpatch是将一个列表中的所有指令地址都填上同一个目标标号。混淆这两个操作会导致跳转目标完全错误。做题时，可以在每条生成的跳转指令后面用注释标明它当前属于哪个列表（如// E.true）。

4. 临时变量重复使用或生命周期混淆：在复杂的表达式中，临时变量（t1, t2...）是顺序生成的。但在控制流分支中，要小心同一个临时变量名在不同分支中被定义和使用的情况。在简单的语法制导定义中，通常假设每次调用newtemp()都返回一个新名字，所以问题不大。但在理解数据流时，需要意识到不同路径可能定义同名变量，这属于后续优化分析的范畴。

给学习者的建议：

• 亲自动手：编译原理是“做”出来的学问。只看答案不动手，永远无法真正掌握。找一张白纸，从最简单的表达式开始，一步步推导，写下每一步生成的代码和属性值。
• 聚焦“翻译方案”：第六章的精髓是那几个经典的翻译方案（赋值、数组、控制流、布尔表达式）。不要死记硬背，要理解每个语义动作的意图。比如，为什么if-else语句里需要那个N产生式？因为它要生成一个跳过else部分的goto指令。
• 利用工具辅助理解：如果有条件，可以尝试使用像ANTLR或Flex/Bison这样的工具，实际实现一个小型的语法制导翻译器。亲眼看到输入字符串变成一串三地址码，会对整个过程有颠覆性的认识。
• 关联前后章节：把第六章看作一个承上启下的枢纽。前面章节的词法、语法分析为你提供了分析树；这一章的中间代码生成是结果；后续的代码优化和目标代码生成则以此结果为输入。思考一下，你生成的三地址码，如何方便后续的优化？如何容易地映射到目标机器的指令？这样能建立起知识网络。

这份“答案”的撰写过程，也是我对自己编译原理知识的一次重新梳理和巩固。其中涉及的每一个步骤、每一个临时变量、每一个标号，都蕴含着编译器将高级语言抽象映射到低级表示的核心逻辑。希望这份注重过程的解析，能帮你穿透习题的表面，真正触摸到编译技术中那部分充满设计美感的工程实践。如果在推导某个具体题目时遇到了卡点，不妨回到最基础的翻译方案，画一画语法树，标一标属性流，一步步来，编译原理的世界会逐渐在你眼前清晰起来。