第149集：开关语句的中间代码生成

核心知识点讲解

开关语句的基本形式

开关语句（switch statement）是一种多分支选择语句，它根据表达式的值从多个分支中选择一个执行。在C语言中，开关语句的基本形式如下：

switch (expression) {
    case constant1:
        statement1;
        break;
    case constant2:
        statement2;
        break;
    ...
    default:
        statementN;
        break;
}

开关语句的执行流程

1. 计算表达式的值：计算 expression 的值，结果必须是整数类型或可以转换为整数类型的值。

2. 匹配常量值：将表达式的值与各个 case 标签后的常量值进行比较。

3. 执行匹配的分支：如果找到匹配的常量值，就从对应的 case 标签开始执行语句。

4. 执行默认分支：如果没有找到匹配的常量值，就执行 default 标签后的语句。

5. 跳出开关语句：当执行到 break 语句时，跳出开关语句。

开关语句的中间代码生成方法

编译器通常使用以下两种方法来生成开关语句的中间代码：

1. 跳转表（Jump Table）：当 case 标签的常量值比较密集时，使用跳转表来提高执行效率。

2. 哈希表（Hash Table）：当 case 标签的常量值比较稀疏时，使用哈希表来节省空间。

基于跳转表的中间代码生成

跳转表是一个数组，其中每个元素是一个跳转地址，对应一个 case 标签。使用跳转表的条件是：

• case 标签的常量值比较密集。
• 常量值的范围不是很大。

生成基于跳转表的中间代码步骤如下：

1. 计算表达式的值：生成表达式的中间代码，结果存储在临时变量中。

2. 计算偏移量：将表达式的值减去最小的 case 常量值，得到偏移量。

3. 检查偏移量范围：如果偏移量超出跳转表的范围，跳转到 default 标签。

4. 计算跳转地址：使用偏移量从跳转表中获取跳转地址。

5. 跳转到对应分支：根据跳转地址跳转到对应的 case 标签。

6. 生成跳转表：在开关语句的开始处生成跳转表。

基于哈希表的中间代码生成

哈希表是一种键值对存储结构，其中键是 case 标签的常量值，值是对应的跳转地址。使用哈希表的条件是：

• case 标签的常量值比较稀疏。
• 常量值的范围很大。

生成基于哈希表的中间代码步骤如下：

1. 计算表达式的值：生成表达式的中间代码，结果存储在临时变量中。

2. 在哈希表中查找：使用表达式的值作为键在哈希表中查找对应的跳转地址。

3. 跳转到对应分支：如果找到匹配的键，跳转到对应的 case 标签；否则，跳转到 default 标签。

4. 生成哈希表：在开关语句的开始处生成哈希表。

实用案例分析

案例1：简单switch语句

示例代码

switch (grade) {
    case 'A':
        printf("Excellent\n");
        break;
    case 'B':
        printf("Good\n");
        break;
    case 'C':
        printf("Average\n");
        break;
    default:
        printf("Fail\n");
        break;
}

生成的三地址码（使用跳转表）

// 计算表达式的值
t1 = grade

// 计算偏移量
t2 = t1 - 'A'

// 检查偏移量范围
if t2 < 0 goto L4
if t2 > 2 goto L4

// 使用跳转表跳转
jump_table = [L1, L2, L3]
t3 = jump_table[t2]
goto *t3

// case 'A' 分支
L1:
param "Excellent\n"
call printf, 1
goto L5

// case 'B' 分支
L2:
param "Good\n"
call printf, 1
goto L5

// case 'C' 分支
L3:
param "Average\n"
call printf, 1
goto L5

// default 分支
L4:
param "Fail\n"
call printf, 1
goto L5

// 开关语句结束
L5:

案例2：带连续case的switch语句

示例代码

switch (month) {
    case 1:
    case 3:
    case 5:
    case 7:
    case 8:
    case 10:
    case 12:
        days = 31;
        break;
    case 4:
    case 6:
    case 9:
    case 11:
        days = 30;
        break;
    case 2:
        days = is_leap_year ? 29 : 28;
        break;
    default:
        days = 0;
        break;
}

生成的三地址码（使用跳转表）

// 计算表达式的值
t1 = month

// 计算偏移量
t2 = t1 - 1

// 检查偏移量范围
if t2 < 0 goto L4
if t2 > 11 goto L4

// 使用跳转表跳转
jump_table = [L1, L3, L1, L2, L1, L2, L1, L1, L2, L1, L2, L1]
t3 = jump_table[t2]
goto *t3

// 31天的月份
L1:
days = 31
goto L5

// 30天的月份
L2:
days = 30
goto L5

// 2月
L3:
if is_leap_year goto L6
days = 28
goto L5
L6:
days = 29
goto L5

// default 分支
L4:
days = 0
goto L5

// 开关语句结束
L5:

案例3：带fall-through的switch语句

示例代码

switch (c) {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
        vowels++;
        break;
    case ' ': 
    case '\t':
    case '\n':
        whitespace++;
        break;
    default:
        consonants++;
        break;
}

生成的三地址码（使用跳转表）

// 计算表达式的值
t1 = c

// 计算偏移量（假设只处理小写字母和空白字符）
if t1 == ' ' goto L2
if t1 == '\t' goto L2
if t1 == '\n' goto L2
if t1 < 'a' goto L3
if t1 > 'z' goto L3
t2 = t1 - 'a'

// 检查是否是元音字母
if t2 == 0 goto L1    // 'a'
if t2 == 4 goto L1    // 'e'
if t2 == 8 goto L1    // 'i'
if t2 == 14 goto L1   // 'o'
if t2 == 20 goto L1   // 'u'
goto L3

// 元音字母分支
L1:
vowels = vowels + 1
goto L4

// 空白字符分支
L2:
whitespace = whitespace + 1
goto L4

// 辅音字母分支
L3:
consonants = consonants + 1
goto L4

// 开关语句结束
L4:

案例4：基于哈希表的switch语句

示例代码

switch (code) {
    case 1000:
        printf("OK\n");
        break;
    case 2001:
        printf("Created\n");
        break;
    case 4004:
        printf("Not Found\n");
        break;
    case 5000:
        printf("Internal Server Error\n");
        break;
    default:
        printf("Unknown Error\n");
        break;
}

生成的三地址码（使用哈希表）

// 计算表达式的值
t1 = code

// 在哈希表中查找
hash_table = {{1000, L1}, {2001, L2}, {4004, L3}, {5000, L4}}
if hash_table.contains(t1) goto *hash_table[t1]
goto L5

// case 1000 分支
L1:
param "OK\n"
call printf, 1
goto L6

// case 2001 分支
L2:
param "Created\n"
call printf, 1
goto L6

// case 4004 分支
L3:
param "Not Found\n"
call printf, 1
goto L6

// case 5000 分支
L4:
param "Internal Server Error\n"
call printf, 1
goto L6

// default 分支
L5:
param "Unknown Error\n"
call printf, 1
goto L6

// 开关语句结束
L6:

代码实现

下面是一个简单的开关语句中间代码生成器的实现，使用 Python 语言：

class SwitchCodeGenerator:
    def __init__(self):
        self.temp_count = 0
        self.label_count = 0
        self.instructions = []
    
    def new_temp(self):
        """生成新的临时变量名"""
        self.temp_count += 1
        return f"t{self.temp_count}"
    
    def new_label(self):
        """生成新的标签名"""
        self.label_count += 1
        return f"L{self.label_count}"
    
    def generate_expression(self, expr):
        """生成表达式的中间代码
        
        Args:
            expr: 表达式，以元组形式表示，如 ('+', 'a', 'b')
            
        Returns:
            存储表达式结果的临时变量名
        """
        if isinstance(expr, tuple):
            op = expr[0]
            if op == '+' or op == '-' or op == '*' or op == '/':
                # 二元运算符
                left = self.generate_expression(expr[1])
                right = self.generate_expression(expr[2])
                temp = self.new_temp()
                self.instructions.append(f"{temp} = {left} {op} {right}")
                return temp
            elif op == '>' or op == '<' or op == '>=' or op == '<=' or op == '==' or op == '!=':
                # 比较运算符
                left = self.generate_expression(expr[1])
                right = self.generate_expression(expr[2])
                temp = self.new_temp()
                self.instructions.append(f"{temp} = {left} {op} {right}")
                return temp
        else:
            # 常量或变量
            return expr
    
    def generate_statement(self, stmt):
        """生成语句的中间代码
        
        Args:
            stmt: 语句，可以是赋值语句、if语句等
        """
        if isinstance(stmt, dict):
            if 'type' in stmt:
                if stmt['type'] == 'assignment':
                    # 赋值语句
                    lvalue = stmt['lvalue']
                    rvalue = stmt['rvalue']
                    result = self.generate_expression(rvalue)
                    self.instructions.append(f"{lvalue} = {result}")
                elif stmt['type'] == 'if':
                    # if语句
                    condition = stmt['condition']
                    then_stmt = stmt['then_stmt']
                    else_stmt = stmt.get('else_stmt', None)
                    # 生成条件表达式的中间代码
                    cond_result = self.generate_expression(condition)
                    # 生成标签
                    then_label = self.new_label()
                    end_label = self.new_label()
                    # 生成条件跳转指令
                    self.instructions.append(f"if {cond_result} goto {then_label}")
                    # 如果有else分支，生成跳转到else标签的指令
                    if else_stmt:
                        else_label = self.new_label()
                        self.instructions.append(f"goto {else_label}")
                    else:
                        self.instructions.append(f"goto {end_label}")
                    # 生成then分支的语句
                    self.instructions.append(f"{then_label}:")
                    self.generate_statement(then_stmt)
                    self.instructions.append(f"goto {end_label}")
                    # 如果有else分支，生成else分支的语句
                    if else_stmt:
                        self.instructions.append(f"{else_label}:")
                        self.generate_statement(else_stmt)
                    # 生成结束标签
                    self.instructions.append(f"{end_label}:")
                elif stmt['type'] == 'switch':
                    # switch语句
                    expression = stmt['expression']
                    cases = stmt['cases']
                    default_stmt = stmt.get('default', None)
                    self.generate_switch_statement(expression, cases, default_stmt)
                elif stmt['type'] == 'break':
                    # break语句
                    self.instructions.append(f"goto L_break")
    
    def generate_switch_statement(self, expression, cases, default_stmt):
        """生成switch语句的中间代码
        
        Args:
            expression: 表达式
            cases:  case列表，每个元素是 (constant, statement)
            default_stmt: default分支的语句
        """
        # 生成表达式的中间代码
        expr_result = self.generate_expression(expression)
        
        # 提取case常量值
        case_values = [case[0] for case in cases]
        
        # 检查是否可以使用跳转表
        if case_values:
            min_val = min(case_values)
            max_val = max(case_values)
            range_size = max_val - min_val + 1
            
            # 如果case值比较密集，使用跳转表
            if range_size <= len(case_values) * 2:
                self.generate_switch_with_jump_table(expr_result, cases, default_stmt, min_val, max_val)
            else:
                # 否则使用哈希表
                self.generate_switch_with_hash_table(expr_result, cases, default_stmt)
        else:
            # 如果没有case，直接执行default分支
            if default_stmt:
                self.generate_statement(default_stmt)
    
    def generate_switch_with_jump_table(self, expr_result, cases, default_stmt, min_val, max_val):
        """生成基于跳转表的switch语句中间代码
        
        Args:
            expr_result: 表达式结果的临时变量名
            cases: case列表
            default_stmt: default分支的语句
            min_val: 最小的case常量值
            max_val: 最大的case常量值
        """
        # 生成标签
        end_label = self.new_label()
        default_label = self.new_label() if default_stmt else end_label
        
        # 生成case标签
        case_labels = [self.new_label() for _ in cases]
        
        # 计算偏移量
        offset_temp = self.new_temp()
        self.instructions.append(f"{offset_temp} = {expr_result} - {min_val}")
        
        # 检查偏移量范围
        self.instructions.append(f"if {offset_temp} < 0 goto {default_label}")
        range_size = max_val - min_val
        self.instructions.append(f"if {offset_temp} > {range_size} goto {default_label}")
        
        # 生成跳转表
        jump_table = {}
        for i, (value, _) in enumerate(cases):
            index = value - min_val
            jump_table[index] = case_labels[i]
        
        # 生成跳转表初始化代码
        table_name = f"jump_table_{self.label_count}"
        table_entries = []
        for i in range(range_size + 1):
            if i in jump_table:
                table_entries.append(jump_table[i])
            else:
                table_entries.append(default_label)
        
        # 生成跳转到对应分支的代码
        table_temp = self.new_temp()
        self.instructions.append(f"{table_temp} = {table_name}[{offset_temp}]")
        self.instructions.append(f"goto *{table_temp}")
        
        # 生成各个case分支的代码
        for i, (_, stmt) in enumerate(cases):
            self.instructions.append(f"{case_labels[i]}:")
            self.generate_statement(stmt)
            self.instructions.append(f"goto {end_label}")
        
        # 生成default分支的代码
        if default_stmt:
            self.instructions.append(f"{default_label}:")
            self.generate_statement(default_stmt)
            self.instructions.append(f"goto {end_label}")
        
        # 生成结束标签
        self.instructions.append(f"{end_label}:")
    
    def generate_switch_with_hash_table(self, expr_result, cases, default_stmt):
        """生成基于哈希表的switch语句中间代码
        
        Args:
            expr_result: 表达式结果的临时变量名
            cases: case列表
            default_stmt: default分支的语句
        """
        # 生成标签
        end_label = self.new_label()
        default_label = self.new_label() if default_stmt else end_label
        
        # 生成case标签
        case_labels = [self.new_label() for _ in cases]
        
        # 生成哈希表查找代码
        for i, (value, _) in enumerate(cases):
            compare_temp = self.new_temp()
            self.instructions.append(f"{compare_temp} = {expr_result} == {value}")
            self.instructions.append(f"if {compare_temp} goto {case_labels[i]}")
        
        # 跳转到default分支
        self.instructions.append(f"goto {default_label}")
        
        # 生成各个case分支的代码
        for i, (_, stmt) in enumerate(cases):
            self.instructions.append(f"{case_labels[i]}:")
            self.generate_statement(stmt)
            self.instructions.append(f"goto {end_label}")
        
        # 生成default分支的代码
        if default_stmt:
            self.instructions.append(f"{default_label}:")
            self.generate_statement(default_stmt)
            self.instructions.append(f"goto {end_label}")
        
        # 生成结束标签
        self.instructions.append(f"{end_label}:")
    
    def get_instructions(self):
        """获取生成的中间代码指令"""
        return self.instructions

# 测试代码
generator = SwitchCodeGenerator()

# 测试switch语句
print("测试switch语句:")
switch_stmt = {
    'type': 'switch',
    'expression': 'grade',
    'cases': [
        ('A', {
            'type': 'assignment',
            'lvalue': 'message',
            'rvalue': '"Excellent"'
        }),
        ('B', {
            'type': 'assignment',
            'lvalue': 'message',
            'rvalue': '"Good"'
        }),
        ('C', {
            'type': 'assignment',
            'lvalue': 'message',
            'rvalue': '"Average"'
        })
    ],
    'default': {
        'type': 'assignment',
        'lvalue': 'message',
        'rvalue': '"Fail"'
    }
}
generator.generate_statement(switch_stmt)
for instr in generator.get_instructions():
    print(instr)

运行结果

测试switch语句:
t1 = grade
L1:
if t1 == A goto L2
if t1 == B goto L3
if t1 == C goto L4
goto L5
L2:
message = "Excellent"
goto L6
L3:
message = "Good"
goto L6
L4:
message = "Average"
goto L6
L5:
message = "Fail"
goto L6
L6:

总结

开关语句的中间代码生成是编译器前端的重要组成部分，它涉及到如何高效地实现多分支选择逻辑。编译器通常根据 case 标签的分布情况选择使用跳转表或哈希表来生成中间代码：

1. 跳转表：当 case 标签的常量值比较密集时使用，它通过计算偏移量直接跳转到对应的分支，执行效率高。

2. 哈希表：当 case 标签的常量值比较稀疏时使用，它通过哈希查找来定位对应的分支，节省空间。

在生成开关语句的中间代码时，需要注意以下几点：

1. 表达式类型：表达式的值必须是整数类型或可以转换为整数类型的值。

2. case常量：case 标签后的常量值必须是编译时常量，且类型与表达式的类型兼容。

3. break语句：每个 case 分支结束后应该有 break 语句，否则会发生 fall-through 现象。

4. default分支：虽然 default 分支是可选的，但为了处理意外情况，通常建议添加 default 分支。

通过正确生成开关语句的中间代码，可以确保编译器能够高效地处理多分支选择逻辑，提高程序的执行效率。