构造三地址代码——基于SDD的翻译

三地址代码（Three-Address Code, TAC）是编译器中的一种常用中间表示形式，用于表示源程序的基本运算和控制流。它的每条指令通常由三个操作数组成，其中包括操作数、操作符以及目标地址。构造三地址代码是编译器的一个关键步骤，而基于语义描述（SDD，Syntax-Directed Definition）进行翻译是一种常用的技术。

1. 语义描述（SDD）

语义描述（SDD）是一种用于描述语言语法和语义之间关系的工具。它结合了文法规则和语义规则，通过语法规则来描述语言的结构，使用语义规则来描述每个语法单元的语义。

在编译器中，语义描述用来指定如何在解析时生成中间代码。具体而言，SDD 通过在语法规则的右侧添加语义动作来定义如何为每个非终结符生成相应的三地址代码。

2. 三地址代码的构造

三地址代码的构造通常基于语法树的节点进行生成。每当语法分析器遍历到一个符合特定文法规则的节点时，会根据该节点的语义规则生成相应的三地址代码。

2.1 SDD的基本形式

在SDD中，每个文法规则的右侧都可以有一个语义动作，它定义了该规则对应的中间代码生成过程。假设我们有一个简单的加法表达式 E → E1 + E2，我们可以为其定义一个语义动作来生成三地址代码。

文法规则：

E → E1 + E2

语义动作：

E.code = E1.code + E2.code + t = E1.t1 + E2.t1

在这个语义动作中，t 是一个临时变量（用于存储中间结果），E1.t1 和 E2.t1 是分别由 E1 和 E2 表达式产生的临时变量。最终，生成的三地址代码就是 t = E1.t1 + E2.t1。

2.2 文法规则及其语义动作

以下是一个更完整的例子，展示了如何使用SDD来构造三地址代码。

文法规则：

E → E1 + E2       // 加法表达式
E → E1 - E2       // 减法表达式
E → NUM           // 数字常量

对于每个文法规则，我们可以为其定义语义动作：

1. 对于加法表达式 E → E1 + E2，语义动作如下：

   E.t1 = newTemp()  // 生成一个新的临时变量
   E.code = E1.code + E2.code + E.t1 = E1.t1 + E2.t1
   

2. 对于减法表达式 E → E1 - E2，语义动作如下：

   E.t1 = newTemp()  // 生成一个新的临时变量
   E.code = E1.code + E2.code + E.t1 = E1.t1 - E2.t1
   

3. 对于数字常量 E → NUM，语义动作如下：

   E.t1 = NUM
   E.code = ""
   

在这些语义动作中，newTemp() 是一个函数，用来生成新的临时变量名；E.code 是生成的三地址代码。

2.3 生成三地址代码

假设输入是一个简单的算术表达式：a = b + c * d，我们希望基于SDD来生成其三地址代码。

步骤 1：分析表达式 b + c * d，首先解析 c * d：

T1 = c * d      // 生成临时变量 t1 存储 c * d

步骤 2：然后解析 b + T1：

T2 = b + T1     // 生成临时变量 t2 存储 b + t1

步骤 3：最后，将结果赋给变量 a：

a = T2          // 将结果存储在变量 a 中

最终，生成的三地址代码如下：

T1 = c * d
T2 = b + T1
a = T2

2.4 复杂表达式解析与生成三地址代码

假设我们有一个更复杂的表达式：a = b + (c - d * e) / f。

步骤 1：首先解析 d * e：

T1 = d * e      // 计算 d * e，并保存结果

步骤 2：然后解析 c - T1：

T2 = c - T1     // 计算 c - t1，并保存结果

步骤 3：接着解析 T2 / f：

T3 = T2 / f     // 计算 t2 / f，并保存结果

步骤 4：最后解析 b + T3：

T4 = b + T3     // 计算 b + t3，并保存结果

步骤 5：最终将结果赋给 a：

a = T4          // 赋值给 a

最终，生成的三地址代码如下：

T1 = d * e
T2 = c - T1
T3 = T2 / f
T4 = b + T3
a = T4

2.5 三地址代码优化

生成的三地址代码可以进行各种优化。常见的优化包括：

• 常量折叠：在编译时计算常量表达式的值，避免运行时的计算。
• 公共子表达式消除：将重复的子表达式提取出来，避免重复计算。
• 死代码删除：删除那些不会被执行或影响最终结果的代码。

例如，在上述代码中，如果 f 是常量，则可以计算出 T3 = (T2 / f) 的结果，避免后续的重复除法操作。

3. 总结

• 三地址代码（TAC） 是一种编译器中常见的中间表示形式，通过表示程序中的基本运算、控制流和表达式，方便编译器进行优化和代码生成。
• 语义描述（SDD） 用来结合语法规则和语义规则，指导语法分析器生成三地址代码。
• 三地址代码生成过程包括基于语法树节点的遍历，在遍历过程中结合语义规则生成三地址代码。
• 通过不断优化三地址代码，编译器能够生成更高效的目标代码。