第155集：中间代码表示——四元式

四元式的基本概念

四元式（Quadruple）是一种常用的中间代码表示形式，它由四个部分组成：操作码、第一操作数、第二操作数和结果。四元式的结构清晰，易于生成和优化，是许多编译器采用的中间代码形式之一。

四元式的结构

四元式的一般形式为：

(OP, ARG1, ARG2, RESULT)

其中：

• OP：操作码，表示要执行的操作
• ARG1：第一操作数
• ARG2：第二操作数
• RESULT：结果存储位置

四元式的特点

1. 结构清晰：每个四元式对应一条基本操作，易于理解和处理
2. 易于优化：四元式的结构便于进行各种代码优化
3. 便于代码生成：四元式可以直接映射到目标代码
4. 支持复杂表达式：通过多个四元式的组合，可以表示复杂的表达式和语句

四元式的操作码

四元式的操作码（OP）表示要执行的操作，常见的操作码包括：

算术操作

关系操作

逻辑操作

赋值操作

控制流操作

函数操作

内存操作

四元式的操作数

四元式的操作数（ARG1, ARG2）可以是：

1. 变量名：如 x, y, z 等
2. 常量：如 10, 3.14, "hello" 等
3. 临时变量：由编译器生成的临时存储位置，如 t1, t2 等
4. 标签：用于控制流操作，如 L1, L2 等
5. 函数名：用于函数调用操作，如 func 等

四元式的生成示例

表达式的四元式生成

对于表达式 a = b + c * d，生成的四元式序列：

1. (MUL, c, d, t1)    // 计算 c * d
2. (ADD, b, t1, t2)    // 计算 b + t1
3. (ASSIGN, t2, , a)   // 将结果赋值给 a

条件语句的四元式生成

对于条件语句 if (x > y) then z = x else z = y，生成的四元式序列：

1. (GT, x, y, t1)      // 计算 x > y
2. (IF_FALSE, t1, , L1) // 如果条件为假，跳转到 L1
3. (ASSIGN, x, , z)     // 条件为真，执行 z = x
4. (GOTO, , , L2)       // 跳转到 L2
5. (LABEL, , , L1)      // 标签 L1
6. (ASSIGN, y, , z)     // 条件为假，执行 z = y
7. (LABEL, , , L2)      // 标签 L2

循环语句的四元式生成

对于循环语句 while (i < n) { i = i + 1; }，生成的四元式序列：

1. (LABEL, , , L1)      // 循环开始标签
2. (LT, i, n, t1)       // 计算 i < n
3. (IF_FALSE, t1, , L2) // 如果条件为假，跳转到 L2
4. (ADD, i, 1, t2)      // 计算 i + 1
5. (ASSIGN, t2, , i)    // 执行 i = i + 1
6. (GOTO, , , L1)       // 跳转到循环开始
7. (LABEL, , , L2)      // 循环结束标签

函数调用的四元式生成

对于函数调用 z = func(x, y)，生成的四元式序列：

1. (PARAM, x, , )       // 传递第一个参数 x
2. (PARAM, y, , )       // 传递第二个参数 y
3. (CALL, func, , t1)   // 调用函数 func，结果存储在 t1
4. (ASSIGN, t1, , z)    // 将结果赋值给 z

四元式的实现

现在，让我们实现一个简单的四元式生成器，用于生成表达式的四元式。

代码结构

class QuadrupleGenerator:
    def __init__(self):
        self.temp_count = 0
        self.quadruples = []
    
    def new_temp(self):
        """生成新的临时变量"""
        self.temp_count += 1
        return f"t{self.temp_count}"
    
    def add_quadruple(self, op, arg1=None, arg2=None, result=None):
        """添加一个四元式"""
        self.quadruples.append((op, arg1, arg2, result))
    
    def generate_expression(self, expr):
        """
        生成表达式的四元式
        支持简单的算术表达式，如 a + b * c
        """
        # 简单的表达式解析和四元式生成
        # 这里使用递归下降解析器的思想
        return self._parse_expression(expr)
    
    def _parse_expression(self, expr):
        """解析表达式并生成四元式"""
        expr = expr.strip()
        
        # 处理括号
        if expr.startswith('(') and expr.endswith(')'):
            return self._parse_expression(expr[1:-1])
        
        # 处理加法和减法
        for op in ['+', '-']:
            if op in expr:
                parts = expr.rsplit(op, 1)
                if len(parts) == 2:
                    left = parts[0].strip()
                    right = parts[1].strip()
                    left_result = self._parse_expression(left)
                    right_result = self._parse_expression(right)
                    temp = self.new_temp()
                    op_code = 'ADD' if op == '+' else 'SUB'
                    self.add_quadruple(op_code, left_result, right_result, temp)
                    return temp
        
        # 处理乘法和除法
        for op in ['*', '/']:
            if op in expr:
                parts = expr.rsplit(op, 1)
                if len(parts) == 2:
                    left = parts[0].strip()
                    right = parts[1].strip()
                    left_result = self._parse_expression(left)
                    right_result = self._parse_expression(right)
                    temp = self.new_temp()
                    op_code = 'MUL' if op == '*' else 'DIV'
                    self.add_quadruple(op_code, left_result, right_result, temp)
                    return temp
        
        # 处理变量或常量
        return expr
    
    def generate_assignment(self, var, expr):
        """生成赋值语句的四元式"""
        expr_result = self.generate_expression(expr)
        self.add_quadruple('ASSIGN', expr_result, None, var)
    
    def print_quadruples(self):
        """打印生成的四元式"""
        print("生成的四元式：")
        print("序号 | 操作码 | 第一操作数 | 第二操作数 | 结果")
        print("-----|-------|------------|------------|------")
        for i, quad in enumerate(self.quadruples, 1):
            op, arg1, arg2, result = quad
            arg1_str = arg1 if arg1 is not None else ""
            arg2_str = arg2 if arg2 is not None else ""
            result_str = result if result is not None else ""
            print(f"{i:3d}  | {op:5} | {arg1_str:10} | {arg2_str:10} | {result_str:6}")

# 测试四元式生成器
generator = QuadrupleGenerator()

# 生成赋值语句的四元式
generator.generate_assignment('a', 'b + c * d')

# 打印生成的四元式
generator.print_quadruples()

# 生成复杂表达式的四元式
generator2 = QuadrupleGenerator()
generator2.generate_assignment('x', 'a + b * c - d / e')
generator2.print_quadruples()

四元式的优缺点

优点

1. 结构清晰：每个四元式对应一条基本操作，易于理解和处理
2. 易于优化：四元式的结构便于进行各种代码优化，如常量折叠、公共子表达式消除等
3. 便于代码生成：四元式可以直接映射到目标代码，简化了代码生成器的设计
4. 支持复杂表达式：通过多个四元式的组合，可以表示复杂的表达式和语句
5. 灵活性高：可以根据需要扩展操作码，支持新的语言特性

缺点

1. 空间开销：四元式的表示需要更多的存储空间，因为每个操作都需要单独的四元式
2. 生成开销：生成四元式序列需要更多的计算时间
3. 间接引用：四元式之间通过临时变量进行连接，可能导致间接引用的开销

四元式与其他中间代码表示的比较

四元式 vs 三元式

• 四元式：使用显式的结果字段，便于优化，但需要更多的存储空间
• 三元式：使用编号引用中间结果，节省存储空间，但优化较为复杂

四元式 vs 三地址码

• 四元式：使用表格形式表示，结构清晰，便于处理
• 三地址码：使用类汇编语言形式表示，更接近目标代码，便于代码生成

四元式 vs 抽象语法树

• 四元式：线性表示，便于顺序处理和优化
• 抽象语法树：层次结构，表示更直观，但处理和优化较为复杂

四元式的优化

常量折叠

对于常量表达式，可以在生成四元式时进行常量折叠，减少运行时计算。

示例：

// 原始四元式
(ADD, 10, 20, t1)

// 优化后
(ASSIGN, 30, , t1)

公共子表达式消除

对于重复出现的子表达式，可以复用之前的计算结果，减少冗余计算。

示例：

// 原始四元式
(MUL, a, b, t1)
(ADD, t1, c, t2)
(MUL, a, b, t3)
(ADD, t3, d, t4)

// 优化后
(MUL, a, b, t1)
(ADD, t1, c, t2)
(ADD, t1, d, t4)

死代码消除

对于没有被使用的四元式，可以进行消除，减少代码体积。

示例：

// 原始四元式
(ADD, a, b, t1)
(MUL, c, d, t2)  // t2 未被使用
(ASSIGN, t1, , x)

// 优化后
(ADD, a, b, t1)
(ASSIGN, t1, , x)

强度削弱

对于某些运算，可以用更高效的运算替代，如用加法替代乘法。

示例：

// 原始四元式
(MUL, x, 2, t1)

// 优化后
(ADD, x, x, t1)

实用案例分析

案例：算术表达式的四元式生成

表达式：z = (a + b) * (c - d)

生成的四元式：

1. (ADD, a, b, t1)      // 计算 a + b
2. (SUB, c, d, t2)      // 计算 c - d
3. (MUL, t1, t2, t3)    // 计算 t1 * t2
4. (ASSIGN, t3, , z)     // 将结果赋值给 z

案例：条件语句的四元式生成

代码：

if (x > 0) {
    y = x;
} else {
    y = -x;
}

生成的四元式：

1. (GT, x, 0, t1)        // 计算 x > 0
2. (IF_FALSE, t1, , L1)  // 如果条件为假，跳转到 L1
3. (ASSIGN, x, , y)      // 条件为真，执行 y = x
4. (GOTO, , , L2)        // 跳转到 L2
5. (LABEL, , , L1)       // 标签 L1
6. (SUB, 0, x, t2)       // 计算 0 - x
7. (ASSIGN, t2, , y)     // 条件为假，执行 y = -x
8. (LABEL, , , L2)       // 标签 L2

案例：循环语句的四元式生成

代码：

for (i = 0; i < 10; i++) {
    sum = sum + i;
}

生成的四元式：

1. (ASSIGN, 0, , i)      // 初始化 i = 0
2. (LABEL, , , L1)       // 循环开始标签
3. (LT, i, 10, t1)       // 计算 i < 10
4. (IF_FALSE, t1, , L2)  // 如果条件为假，跳转到 L2
5. (ADD, sum, i, t2)     // 计算 sum + i
6. (ASSIGN, t2, , sum)   // 执行 sum = sum + i
7. (ADD, i, 1, t3)       // 计算 i + 1
8. (ASSIGN, t3, , i)     // 执行 i = i + 1
9. (GOTO, , , L1)        // 跳转到循环开始
10. (LABEL, , , L2)      // 循环结束标签

四元式在编译器中的应用

前端到中端的桥梁

四元式作为前端和中端之间的桥梁，将语法分析的结果转换为易于优化的中间表示。

代码优化的基础

四元式的结构便于进行各种代码优化，如常量折叠、公共子表达式消除、死代码消除等。

后端代码生成的依据

四元式可以直接映射到目标代码，为后端代码生成提供了清晰的指导。

跨平台编译的支持

四元式作为与平台无关的中间表示，支持跨平台编译，同一套四元式可以生成不同平台的目标代码。

小结

本集我们学习了四元式作为中间代码表示的相关知识，包括：

1. 四元式的基本概念：结构、特点和组成部分
2. 四元式的操作码：算术操作、关系操作、逻辑操作、赋值操作、控制流操作等
3. 四元式的操作数：变量名、常量、临时变量、标签、函数名等
4. 四元式的生成示例：表达式、条件语句、循环语句、函数调用等
5. 四元式的实现：简单的四元式生成器
6. 四元式的优缺点：结构清晰、易于优化，但空间开销较大
7. 四元式与其他中间代码表示的比较：与三元式、三地址码、抽象语法树的对比
8. 四元式的优化：常量折叠、公共子表达式消除、死代码消除、强度削弱等
9. 实用案例分析：算术表达式、条件语句、循环语句的四元式生成
10. 四元式在编译器中的应用：前端到中端的桥梁、代码优化的基础、后端代码生成的依据、跨平台编译的支持

通过本集的学习，你应该能够理解四元式的结构和使用方法，以及它在编译器中的重要作用。四元式作为一种常用的中间代码表示形式，为编译器的设计和实现提供了很大的便利，是编译原理中的重要概念之一。

思考与练习

1. 编写一个四元式生成器，支持更复杂的表达式和语句。

2. 分析以下代码的四元式生成：

int factorial(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

3. 比较四元式和三元式的优缺点，并分析在什么情况下应该使用哪种中间代码表示。

4. 讨论四元式在代码优化中的应用，举例说明如何通过四元式进行常量折叠和公共子表达式消除。

5. 设计一个四元式到三地址码的转换器，将四元式序列转换为等价的三地址码。