第156集：中间代码表示——三元式

三元式的基本概念

三元式（Triple）是一种简洁的中间代码表示形式，它由三个部分组成：操作码、第一操作数和第二操作数。与四元式不同，三元式不使用显式的结果字段，而是通过三元式的编号来引用中间结果。三元式的结构紧凑，节省存储空间，是另一种常用的中间代码表示形式。

三元式的结构

三元式的一般形式为：

(OP, ARG1, ARG2)

其中：

OP：操作码，表示要执行的操作
ARG1：第一操作数
ARG2：第二操作数

三元式的特点

结构紧凑：每个三元式只包含三个部分，节省存储空间
通过编号引用：使用三元式的编号来引用中间结果
易于生成：生成过程简单直接
不利于优化：由于使用编号引用，优化时需要调整编号，较为复杂

三元式的编号

三元式在生成过程中会被顺序编号，从1开始。当一个三元式的结果需要被其他三元式使用时，使用该三元式的编号作为操作数。

三元式编号的示例

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

1. (MUL, c, d)    // 计算 c * d，编号为 1
2. (ADD, b, 1)    // 计算 b + 三元式 1 的结果，编号为 2
3. (ASSIGN, 2, a) // 将三元式 2 的结果赋值给 a，编号为 3

这里，三元式 2 使用三元式 1 的编号 1 作为第二操作数，表示使用三元式 1 的计算结果。三元式 3 使用三元式 2 的编号 2 作为第一操作数，表示使用三元式 2 的计算结果。

间接三元式

间接三元式（Indirect Triple）是三元式的一种变体，它使用一个指针数组来引用三元式，而不是直接使用三元式的编号。间接三元式的优点是在优化过程中可以更方便地重排和共享三元式。

间接三元式的结构

间接三元式由两部分组成：

三元式表：存储所有唯一的三元式
执行序列：存储指向三元式表中三元式的指针（索引）

间接三元式的示例

对于表达式 a = b + c * d 和 e = c * d + f，生成的间接三元式：

三元式表：

1. (MUL, c, d)
2. (ADD, b, 1)
3. (ASSIGN, 2, a)
4. (ADD, 1, f)
5. (ASSIGN, 4, e)

执行序列：

1, 2, 3, 1, 4, 5

这里，执行序列中的数字是指向三元式表的索引。注意，三元式 1（c * d）被复用了两次，避免了重复存储。

三元式的操作码

三元式的操作码与四元式类似，包括算术操作、关系操作、逻辑操作、赋值操作、控制流操作等。

常见的三元式操作码

操作码	含义	示例
ADD	加法	(ADD, a, b)
SUB	减法	(SUB, a, b)
MUL	乘法	(MUL, a, b)
DIV	除法	(DIV, a, b)
LT	小于	(LT, a, b)
LE	小于等于	(LE, a, b)
GT	大于	(GT, a, b)
GE	大于等于	(GE, a, b)
EQ	等于	(EQ, a, b)
NE	不等于	(NE, a, b)
AND	逻辑与	(AND, a, b)
OR	逻辑或	(OR, a, b)
NOT	逻辑非	(NOT, a)
ASSIGN	赋值	(ASSIGN, a, b)
GOTO	无条件跳转	(GOTO, L1)
IF	条件跳转	(IF, a, L2)
LABEL	标签定义	(LABEL, L3)
CALL	函数调用	(CALL, func)
PARAM	参数传递	(PARAM, a)
RETURN	返回值	(RETURN, a)

三元式的生成示例

表达式的三元式生成

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

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

条件语句的三元式生成

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

1. (GT, x, y)     // 计算 x > y
2. (IF, 1, 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)     // 计算 i < n
3. (IF, 2, L2)    // 如果条件为假，跳转到 L2
4. (ADD, i, 1)    // 计算 i + 1
5. (ASSIGN, 4, 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)   // 调用函数 func
4. (ASSIGN, 3, z) // 将结果赋值给 z

间接三元式的生成示例

表达式的间接三元式生成

对于表达式 a = b + c * d 和 e = c * d + f，生成的间接三元式：

三元式表：

1. (MUL, c, d)
2. (ADD, b, 1)
3. (ASSIGN, 2, a)
4. (ADD, 1, f)
5. (ASSIGN, 4, e)

执行序列：

1, 2, 3, 1, 4, 5

循环语句的间接三元式生成

对于循环语句 for (i = 0; i < 10; i++) { sum = sum + i; }，生成的间接三元式：

三元式表：

1. (ASSIGN, 0, i)
2. (LABEL, L1)
3. (LT, i, 10)
4. (IF, 3, L2)
5. (ADD, sum, i)
6. (ASSIGN, 5, sum)
7. (ADD, i, 1)
8. (ASSIGN, 7, i)
9. (GOTO, L1)
10. (LABEL, L2)

执行序列：

1, 2, 3, 4, 5, 6, 7, 8, 9, 2, 3, 4, 10

三元式的实现

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

代码结构

class TripleGenerator:
    def __init__(self):
        self.triples = []
        self.temp_count = 0
    
    def add_triple(self, op, arg1=None, arg2=None):
        """添加一个三元式"""
        self.triples.append((op, arg1, arg2))
        return len(self.triples)
    
    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)
                    op_code = 'ADD' if op == '+' else 'SUB'
                    return self.add_triple(op_code, left_result, right_result)
        
        # 处理乘法和除法
        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)
                    op_code = 'MUL' if op == '*' else 'DIV'
                    return self.add_triple(op_code, left_result, right_result)
        
        # 处理变量或常量
        return expr
    
    def generate_assignment(self, var, expr):
        """生成赋值语句的三元式"""
        expr_result = self.generate_expression(expr)
        return self.add_triple('ASSIGN', expr_result, var)
    
    def print_triples(self):
        """打印生成的三元式"""
        print("生成的三元式：")
        print("序号 | 操作码 | 第一操作数 | 第二操作数")
        print("-----|-------|------------|------------")
        for i, triple in enumerate(self.triples, 1):
            op, arg1, arg2 = triple
            arg1_str = str(arg1) if arg1 is not None else ""
            arg2_str = str(arg2) if arg2 is not None else ""
            print(f"{i:3d}  | {op:5} | {arg1_str:10} | {arg2_str:10}")

class IndirectTripleGenerator:
    def __init__(self):
        self.triple_table = []
        self.execution_sequence = []
        self.triple_map = {}  # 用于检测重复的三元式
    
    def add_triple(self, op, arg1=None, arg2=None):
        """添加一个三元式到三元式表，并返回其索引"""
        # 创建三元式的键，用于检测重复
        triple_key = (op, arg1, arg2)
        
        # 检查三元式是否已经存在
        if triple_key in self.triple_map:
            return self.triple_map[triple_key]
        
        # 添加新的三元式
        self.triple_table.append((op, arg1, arg2))
        index = len(self.triple_table)
        self.triple_map[triple_key] = index
        return index
    
    def add_to_sequence(self, index):
        """将三元式的索引添加到执行序列"""
        self.execution_sequence.append(index)
    
    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)
                    op_code = 'ADD' if op == '+' else 'SUB'
                    triple_index = self.add_triple(op_code, left_result, right_result)
                    self.add_to_sequence(triple_index)
                    return triple_index
        
        # 处理乘法和除法
        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)
                    op_code = 'MUL' if op == '*' else 'DIV'
                    triple_index = self.add_triple(op_code, left_result, right_result)
                    self.add_to_sequence(triple_index)
                    return triple_index
        
        # 处理变量或常量
        return expr
    
    def generate_assignment(self, var, expr):
        """生成赋值语句的间接三元式"""
        expr_result = self.generate_expression(expr)
        triple_index = self.add_triple('ASSIGN', expr_result, var)
        self.add_to_sequence(triple_index)
        return triple_index
    
    def print_indirect_triples(self):
        """打印生成的间接三元式"""
        print("三元式表：")
        print("序号 | 操作码 | 第一操作数 | 第二操作数")
        print("-----|-------|------------|------------")
        for i, triple in enumerate(self.triple_table, 1):
            op, arg1, arg2 = triple
            arg1_str = str(arg1) if arg1 is not None else ""
            arg2_str = str(arg2) if arg2 is not None else ""
            print(f"{i:3d}  | {op:5} | {arg1_str:10} | {arg2_str:10}")
        
        print("\n执行序列：")
        print(' '.join(map(str, self.execution_sequence)))

# 测试三元式生成器
generator = TripleGenerator()
generator.generate_assignment('a', 'b + c * d')
generator.print_triples()

# 测试间接三元式生成器
indirect_generator = IndirectTripleGenerator()
indirect_generator.generate_assignment('a', 'b + c * d')
indirect_generator.generate_assignment('e', 'c * d + f')
indirect_generator.print_indirect_triples()

三元式的优缺点

优点

结构紧凑：每个三元式只包含三个部分，节省存储空间
生成简单：生成过程直接，不需要管理临时变量
引用方便：通过编号引用中间结果，直观简洁
适合简单优化：对于局部优化，如常量折叠，较为方便

缺点

不利于优化：当进行优化需要删除或重排三元式时，需要调整所有引用该三元式的编号，较为复杂
难以共享子表达式：相同的子表达式会生成不同的三元式，除非使用间接三元式
可读性较差：对于复杂表达式，通过编号引用中间结果可能降低可读性
不适合全局优化：全局优化需要频繁修改三元式，编号调整的开销较大

间接三元式的优缺点

优点

便于优化：可以通过修改执行序列来重排三元式，而不需要调整编号
共享子表达式：相同的子表达式只需要存储一次，节省存储空间
适合全局优化：全局优化时可以更方便地添加、删除或重排三元式
保持编号稳定：三元式的编号一旦确定就不再改变，便于引用

缺点

生成复杂：生成过程比直接三元式复杂，需要维护三元式表和执行序列
需要额外的映射：需要维护三元式到索引的映射，以检测重复的三元式
执行开销：执行时需要通过执行序列间接访问三元式，可能增加开销
实现复杂：实现间接三元式生成器比直接三元式生成器复杂

三元式与四元式的比较

特性	三元式	四元式
结构	(OP, ARG1, ARG2)	(OP, ARG1, ARG2, RESULT)
结果引用	通过编号	通过显式的结果字段
存储空间	紧凑，节省空间	较为宽松，需要更多空间
生成难度	简单	中等
优化难度	困难（直接三元式）/ 中等（间接三元式）	容易
可读性	中等	较好
适合场景	简单编译器，空间受限的环境	复杂编译器，需要大量优化的场景

三元式的优化

常量折叠

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

示例：

// 原始三元式
1. (ADD, 10, 20)

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

公共子表达式消除

对于重复出现的子表达式，使用间接三元式可以共享相同的三元式，减少冗余计算。

示例：

// 原始三元式表
1. (MUL, a, b)
2. (ADD, 1, c)
3. (MUL, a, b)  // 重复的子表达式
4. (ADD, 3, d)

// 优化后的三元式表
1. (MUL, a, b)
2. (ADD, 1, c)
3. (ADD, 1, d)  // 复用三元式 1

死代码消除

对于没有被使用的三元式，可以从执行序列中删除，减少代码体积。

示例：

// 原始执行序列
1. (ADD, a, b)
2. (MUL, c, d)  // 未被使用
3. (ASSIGN, 1, x)

// 优化后的执行序列
1. (ADD, a, b)
3. (ASSIGN, 1, x)

强度削弱

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

示例：

// 原始三元式
1. (MUL, x, 2)

// 优化后
1. (ADD, x, x)

实用案例分析

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

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

生成的三元式：

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

生成的间接三元式：

三元式表：

1. (ADD, a, b)
2. (SUB, c, d)
3. (MUL, 1, 2)
4. (ASSIGN, 3, z)

执行序列：

1, 2, 3, 4

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

代码：

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

生成的三元式：

1. (GT, x, 0)       // 计算 x > 0
2. (IF, 1, L1)      // 如果条件为假，跳转到 L1
3. (ASSIGN, x, y)   // 条件为真，执行 y = x
4. (GOTO, L2)       // 跳转到 L2
5. (LABEL, L1)      // 标签 L1
6. (SUB, 0, x)      // 计算 0 - x
7. (ASSIGN, 6, 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)      // 计算 i < 10
4. (IF, 3, L2)      // 如果条件为假，跳转到 L2
5. (ADD, sum, i)    // 计算 sum + i
6. (ASSIGN, 5, sum) // 执行 sum = sum + i
7. (ADD, i, 1)      // 计算 i + 1
8. (ASSIGN, 7, i)   // 执行 i = i + 1
9. (GOTO, L1)       // 跳转到循环开始
10. (LABEL, L2)     // 循环结束标签

三元式在编译器中的应用

简单编译器

对于简单的编译器，特别是空间受限的环境，三元式是一种不错的选择，因为它结构紧凑，节省存储空间。

教学编译器

在教学编译器中，三元式的生成过程简单直观，适合作为中间代码表示的教学示例。

快速原型

在编译器的快速原型开发中，三元式可以快速实现，验证编译器的基本功能。

与其他中间表示的配合

在复杂的编译器中，三元式可以与其他中间表示配合使用，例如：

前端生成三元式
中端将三元式转换为四元式进行优化
后端将优化后的四元式转换为目标代码

小结

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

三元式的基本概念：结构、特点和组成部分
三元式的编号：通过编号引用中间结果
间接三元式：三元式表和执行序列的组合
三元式的操作码：与四元式类似的操作码
三元式的生成示例：表达式、条件语句、循环语句、函数调用等
三元式的实现：简单的三元式生成器和间接三元式生成器
三元式的优缺点：结构紧凑但不利于优化
间接三元式的优缺点：便于优化但实现复杂
三元式与四元式的比较：结构、存储空间、生成难度、优化难度等
三元式的优化：常量折叠、公共子表达式消除、死代码消除、强度削弱等
实用案例分析：算术表达式、条件语句、循环语句的三元式生成
三元式在编译器中的应用：简单编译器、教学编译器、快速原型等

通过本集的学习，你应该能够理解三元式的结构和使用方法，以及它在编译器中的应用场景。三元式作为一种紧凑的中间代码表示形式，在某些场景下具有独特的优势，特别是在空间受限的环境中。而间接三元式则通过引入执行序列，解决了三元式优化困难的问题，使得三元式在更复杂的编译器中也能得到应用。

思考与练习

编写一个三元式生成器，支持更复杂的表达式和语句。
分析以下代码的三元式生成：

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

比较三元式和四元式的优缺点，并分析在什么情况下应该使用哪种中间代码表示。
实现一个间接三元式到四元式的转换器，将间接三元式转换为等价的四元式。
讨论如何使用间接三元式进行公共子表达式消除优化。