第148集：循环语句的中间代码生成

核心知识点讲解

循环语句的分类

在编程语言中，循环语句通常可以分为以下几类：

1. while循环：先判断条件，再执行循环体，如 while (condition) { statement }。

2. do-while循环：先执行循环体，再判断条件，如 do { statement } while (condition);。

3. for循环：初始化、条件判断、循环后操作一体化的循环，如 for (init; condition; update) { statement }。

4. foreach循环：遍历集合元素的循环，如 for (element : collection) { statement }（在Java等语言中）。

循环语句的中间代码生成原理

循环语句的中间代码生成主要涉及到跳转指令和标签的生成，以实现循环的控制流程。编译器会为循环语句生成以下类型的中间代码：

1. 条件跳转指令：根据条件表达式的值决定是否继续循环。

2. 无条件跳转指令：用于跳转到循环开始或循环结束的位置。

3. 标签：用于标记循环的开始、循环体的开始和循环的结束位置。

while循环的中间代码生成

while循环的形式为：

while (condition) {
    statement
}

生成while循环的中间代码步骤如下：

1. 生成循环开始标签L1：标记循环的开始位置。

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

3. 生成条件跳转指令：如果条件为假，跳转到 L2（循环结束后的位置）。

4. 生成循环体的中间代码：生成 statement 的中间代码。

5. 生成无条件跳转指令：跳转到 L1（循环的开始位置）。

6. 生成循环结束标签L2：标记循环的结束位置。

例如，对于while循环：

while (i < n) {
    sum = sum + i;
    i = i + 1;
}

生成的中间代码如下：

L1: if i < n goto L2
goto L3
L2: sum = sum + i
i = i + 1
goto L1
L3:

do-while循环的中间代码生成

do-while循环的形式为：

do {
    statement
} while (condition);

生成do-while循环的中间代码步骤如下：

1. 生成循环体开始标签L1：标记循环体的开始位置。

2. 生成循环体的中间代码：生成 statement 的中间代码。

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

4. 生成条件跳转指令：如果条件为真，跳转到 L1（循环体的开始位置）。

5. 生成循环结束标签L2：标记循环的结束位置。

例如，对于do-while循环：

do {
    sum = sum + i;
    i = i + 1;
} while (i < n);

生成的中间代码如下：

L1: sum = sum + i
i = i + 1
if i < n goto L1
L2:

for循环的中间代码生成

for循环的形式为：

for (init; condition; update) {
    statement
}

for循环可以转换为等价的while循环：

init;
while (condition) {
    statement;
    update;
}

生成for循环的中间代码步骤如下：

1. 生成初始化语句的中间代码：生成 init 的中间代码。

2. 生成循环开始标签L1：标记循环的开始位置。

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

4. 生成条件跳转指令：如果条件为假，跳转到 L2（循环结束后的位置）。

5. 生成循环体的中间代码：生成 statement 的中间代码。

6. 生成更新语句的中间代码：生成 update 的中间代码。

7. 生成无条件跳转指令：跳转到 L1（循环的开始位置）。

8. 生成循环结束标签L2：标记循环的结束位置。

例如，对于for循环：

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

生成的中间代码如下：

i = 0
L1: if i < n goto L2
goto L3
L2: sum = sum + i
i = i + 1
goto L1
L3:

循环嵌套的中间代码生成

循环嵌套是指在一个循环内部包含另一个循环。生成嵌套循环的中间代码时，需要为每个循环生成独立的标签，以避免标签冲突。

实用案例分析

案例1：简单while循环

示例代码

while (i > 0) {
    i = i - 1;
}

生成的三地址码

L1: if i > 0 goto L2
goto L3
L2: i = i - 1
goto L1
L3:

案例2：do-while循环

示例代码

do {
    x = x * 2;
    count = count + 1;
} while (x < 100);

生成的三地址码

L1: x = x * 2
count = count + 1
if x < 100 goto L1
L2:

案例3：for循环

示例代码

for (int i = 1; i <= 10; i++) {
    printf("%d\n", i);
}

生成的三地址码

i = 1
L1: if i <= 10 goto L2
goto L3
L2: param i
call printf, 1
i = i + 1
goto L1
L3:

案例4：嵌套循环

示例代码

for (i = 0; i < n; i++) {
    for (j = 0; j < m; j++) {
        matrix[i][j] = 0;
    }
}

生成的三地址码

i = 0
L1: if i < n goto L2
goto L6
L2: j = 0
L3: if j < m goto L4
goto L5
L4: t1 = i * m
    t2 = t1 + j
    t3 = t2 * 4
    t4 = matrix + t3
    *t4 = 0
    j = j + 1
goto L3
L5: i = i + 1
goto L1
L6:

案例5：带break语句的循环

示例代码

while (i < n) {
    if (a[i] == key) {
        break;
    }
    i = i + 1;
}

生成的三地址码

L1: if i < n goto L2
goto L5
L2: t1 = i * 4
    t2 = a + t1
    t3 = *t2
    if t3 == key goto L5
    i = i + 1
goto L1
L5:

案例6：带continue语句的循环

示例代码

while (i < n) {
    i = i + 1;
    if (i % 2 == 0) {
        continue;
    }
    sum = sum + i;
}

生成的三地址码

L1: if i < n goto L2
goto L6
L2: i = i + 1
    t1 = i % 2
    if t1 == 0 goto L1
    sum = sum + i
goto L1
L6:

代码实现

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

class LoopCodeGenerator:
    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 == '!=' 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']
                    # 生成条件表达式的中间代码
                    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}")
                    self.instructions.append(f"goto {end_label}")
                    # 生成then分支的语句
                    self.instructions.append(f"{then_label}:")
                    self.generate_statement(then_stmt)
                    # 生成结束标签
                    self.instructions.append(f"{end_label}:")
                elif stmt['type'] == 'while':
                    # while循环
                    condition = stmt['condition']
                    body_stmt = stmt['body']
                    self.generate_while_loop(condition, body_stmt)
                elif stmt['type'] == 'do-while':
                    # do-while循环
                    condition = stmt['condition']
                    body_stmt = stmt['body']
                    self.generate_do_while_loop(condition, body_stmt)
                elif stmt['type'] == 'for':
                    # for循环
                    init_stmt = stmt['init']
                    condition = stmt['condition']
                    update_stmt = stmt['update']
                    body_stmt = stmt['body']
                    self.generate_for_loop(init_stmt, condition, update_stmt, body_stmt)
                elif stmt['type'] == 'break':
                    # break语句
                    # 在实际编译器中，需要知道跳出到哪个标签
                    # 这里简化处理，假设break标签为L_break
                    self.instructions.append(f"goto L_break")
                elif stmt['type'] == 'continue':
                    # continue语句
                    # 在实际编译器中，需要知道跳转到哪个标签
                    # 这里简化处理，假设continue标签为L_continue
                    self.instructions.append(f"goto L_continue")
    
    def generate_while_loop(self, condition, body_stmt):
        """生成while循环的中间代码
        
        Args:
            condition: 条件表达式
            body_stmt: 循环体语句
        """
        # 生成标签
        loop_start_label = self.new_label()
        body_start_label = self.new_label()
        loop_end_label = self.new_label()
        
        # 生成循环开始标签
        self.instructions.append(f"{loop_start_label}:")
        
        # 生成条件表达式的中间代码
        cond_result = self.generate_expression(condition)
        
        # 生成条件跳转指令
        self.instructions.append(f"if !{cond_result} goto {loop_end_label}")
        
        # 生成循环体开始标签
        self.instructions.append(f"{body_start_label}:")
        
        # 生成循环体的语句
        self.generate_statement(body_stmt)
        
        # 生成无条件跳转指令，跳转到循环开始
        self.instructions.append(f"goto {loop_start_label}")
        
        # 生成循环结束标签
        self.instructions.append(f"{loop_end_label}:")
    
    def generate_do_while_loop(self, condition, body_stmt):
        """生成do-while循环的中间代码
        
        Args:
            condition: 条件表达式
            body_stmt: 循环体语句
        """
        # 生成标签
        body_start_label = self.new_label()
        loop_end_label = self.new_label()
        
        # 生成循环体开始标签
        self.instructions.append(f"{body_start_label}:")
        
        # 生成循环体的语句
        self.generate_statement(body_stmt)
        
        # 生成条件表达式的中间代码
        cond_result = self.generate_expression(condition)
        
        # 生成条件跳转指令，如果条件为真，跳转到循环体开始
        self.instructions.append(f"if {cond_result} goto {body_start_label}")
        
        # 生成循环结束标签
        self.instructions.append(f"{loop_end_label}:")
    
    def generate_for_loop(self, init_stmt, condition, update_stmt, body_stmt):
        """生成for循环的中间代码
        
        Args:
            init_stmt: 初始化语句
            condition: 条件表达式
            update_stmt: 更新语句
            body_stmt: 循环体语句
        """
        # 生成初始化语句的中间代码
        self.generate_statement(init_stmt)
        
        # 生成标签
        loop_start_label = self.new_label()
        body_start_label = self.new_label()
        loop_end_label = self.new_label()
        
        # 生成循环开始标签
        self.instructions.append(f"{loop_start_label}:")
        
        # 生成条件表达式的中间代码
        cond_result = self.generate_expression(condition)
        
        # 生成条件跳转指令
        self.instructions.append(f"if !{cond_result} goto {loop_end_label}")
        
        # 生成循环体开始标签
        self.instructions.append(f"{body_start_label}:")
        
        # 生成循环体的语句
        self.generate_statement(body_stmt)
        
        # 生成更新语句的中间代码
        self.generate_statement(update_stmt)
        
        # 生成无条件跳转指令，跳转到循环开始
        self.instructions.append(f"goto {loop_start_label}")
        
        # 生成循环结束标签
        self.instructions.append(f"{loop_end_label}:")
    
    def get_instructions(self):
        """获取生成的中间代码指令"""
        return self.instructions

# 测试代码
generator = LoopCodeGenerator()

# 测试while循环
print("测试while循环:")
while_loop = {
    'type': 'while',
    'condition': ('<', 'i', 'n'),
    'body': {
        'type': 'assignment',
        'lvalue': 'sum',
        'rvalue': ('+', 'sum', 'i')
    }
}
generator.generate_statement(while_loop)
for instr in generator.get_instructions():
    print(instr)
print()

# 测试do-while循环
generator2 = LoopCodeGenerator()
print("测试do-while循环:")
do_while_loop = {
    'type': 'do-while',
    'condition': ('<', 'x', '100'),
    'body': {
        'type': 'assignment',
        'lvalue': 'x',
        'rvalue': ('*', 'x', '2')
    }
}
generator2.generate_statement(do_while_loop)
for instr in generator2.get_instructions():
    print(instr)
print()

# 测试for循环
generator3 = LoopCodeGenerator()
print("测试for循环:")
for_loop = {
    'type': 'for',
    'init': {
        'type': 'assignment',
        'lvalue': 'i',
        'rvalue': '0'
    },
    'condition': ('<', 'i', '10'),
    'update': {
        'type': 'assignment',
        'lvalue': 'i',
        'rvalue': ('+', 'i', '1')
    },
    'body': {
        'type': 'assignment',
        'lvalue': 'sum',
        'rvalue': ('+', 'sum', 'i')
    }
}
generator3.generate_statement(for_loop)
for instr in generator3.get_instructions():
    print(instr)

运行结果

测试while循环:
L1:
t1 = i < n
if !t1 goto L3
L2:
t2 = sum + i
sum = t2
goto L1
L3:

测试do-while循环:
L1:
t1 = x * 2
x = t1
t2 = x < 100
if t2 goto L1
L2:

测试for循环:
i = 0
L1:
t1 = i < 10
if !t1 goto L3
L2:
t2 = sum + i
sum = t2
t3 = i + 1
i = t3
goto L1
L3:

总结

循环语句的中间代码生成是编译器前端的重要组成部分，它涉及到跳转指令和标签的生成，以实现循环的控制流程。对于不同类型的循环语句，如while循环、do-while循环和for循环，它们的中间代码生成方式有所不同，但核心都是通过条件跳转和无条件跳转指令来控制程序的执行流程。

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

1. 标签的管理：合理生成和使用标签，确保跳转的目标位置正确，特别是在嵌套循环中，要避免标签冲突。

2. 循环控制语句：正确处理break和continue语句的中间代码生成，它们分别需要跳转到循环结束和循环开始的位置。

3. 循环优化：在生成中间代码时，可以考虑一些简单的循环优化，如循环不变量外提、强度削弱等。

4. 循环嵌套：处理好嵌套循环的中间代码生成，确保每个循环都有独立的标签和正确的跳转逻辑。

通过正确生成循环语句的中间代码，可以确保编译器能够正确处理各种循环逻辑，为后续的代码优化和目标代码生成做准备。