bittern.cn
11

编译器（下）

代码生成

阅读量：6 · 预计 6 分钟读完

中间代码目标代码
关联层级：L5 虚拟机代码L6 高级语言
阅读进度4%

第十一章 编译器（下）

导读

在第十章中，我们构建了Jack编译器的基本框架，实现了词法分析、语法分析和基本的代码生成。本章将完善编译器，处理更复杂的语言特性和边界情况。

一个完整的编译器需要处理许多细节：类型检查、作用域规则、内存管理、错误恢复等。通过本章的学习，你将掌握这些高级技术，构建一个健壮的、能够处理真实程序的编译器。

编译器的完善过程展示了软件工程的许多重要实践：模块化设计、错误处理、测试驱动开发等。这些经验对于构建任何复杂的软件系统都很有价值。

核心概念详解

11.1 类型检查

类型检查确保程序中的操作对操作数类型是合法的。

静态类型检查

Jack是静态类型语言，在编译时进行类型检查：

赋值类型检查：

jack
var int x;
var boolean b;
let x = 5;        // OK: int = int
let b = true;     // OK: boolean = boolean
let x = true;     // Error: int != boolean

参数类型检查：

jack
function int add(int a, int b) { ... }
let x = add(5, 3);      // OK
let y = add(true, 3);   // Error

返回值类型检查：

jack
method int getValue() {
    return 5;           // OK
    // return true;     // Error
}

类型检查实现

python
class TypeChecker:
    def __init__(self, symbol_table):
        self.symbol_table = symbol_table
    
    def check_assignment(self, var_name, expression_type):
        var_type = self.symbol_table.type_of(var_name)
        if var_type != expression_type:
            raise TypeError(f"Type mismatch: cannot assign {expression_type} to {var_type}")
    
    def check_binary_op(self, op, left_type, right_type):
        if op in ['+', '-', '*', '/']:
            if left_type != 'int' or right_type != 'int':
                raise TypeError(f"Arithmetic operator {op} requires int operands")
            return 'int'
        elif op in ['&', '|']:
            if left_type != 'boolean' or right_type != 'boolean':
                raise TypeError(f"Logical operator {op} requires boolean operands")
            return 'boolean'
        elif op in ['<', '>', '=', '!=']:
            if left_type != right_type:
                raise TypeError(f"Comparison operator {op} requires same type operands")
            return 'boolean'
    
    def check_unary_op(self, op, operand_type):
        if op == '-' and operand_type != 'int':
            raise TypeError(f"Unary minus requires int operand")
        if op == '~' and operand_type != 'boolean':
            raise TypeError(f"Logical not requires boolean operand")

11.2 作用域规则

Jack有两级作用域：类作用域和子程序作用域。

名称解析

名称解析确定标识符引用哪个声明：

python
def resolve_name(self, name):
    # 首先查找子程序作用域
    if name in self.subroutine_scope:
        return self.subroutine_scope[name]
    # 然后查找类作用域
    elif name in self.class_scope:
        return self.class_scope[name]
    else:
        raise NameError(f"Undefined name: {name}")

名称遮蔽

子程序作用域中的声明会遮蔽类作用域中的同名声明：

jack
class Example {
    field int x;
    
    method void doSomething(int x) {
        // 这里的x是参数，遮蔽了字段x
        let x = 5;  // 修改的是参数x
    }
}

11.3 数组处理

数组是Jack中最复杂的特性之一。

数组声明

jack
var Array arr;
let arr = Array.new(10);

数组访问

数组访问需要计算元素地址：

jack
let arr[i] = value;

编译为：

push local arr_index    // 数组基地址
push local i            // 索引
add                     // 元素地址
pop pointer 1           // that = 元素地址
push value              // 值
pop that 0              // that[0] = value

数组读取

jack
let x = arr[i];

编译为：

push local arr_index    // 数组基地址
push local i            // 索引
add                     // 元素地址
pop pointer 1           // that = 元素地址
push that 0             // 读取值

数组编译实现

python
def compile_array_access(self, array_name, is_assignment):
    # 获取数组基地址
    self.emit_push_var(array_name)
    
    # 编译索引表达式
    self.tokenizer.advance()  # '['
    self.compile_expression()
    
    # 计算元素地址
    self.vm_writer.write_arithmetic('add')
    
    if is_assignment:
        # 赋值：将地址存入that
        self.vm_writer.write_pop('pointer', 1)
    else:
        # 读取：从that读取值
        self.vm_writer.write_pop('pointer', 1)
        self.vm_writer.write_push('that', 0)

11.4 对象方法调用

对象方法调用需要传递this指针。

方法调用语法

jack
do obj.method(args);

方法调用编译

python
def compile_method_call(self, obj_name, method_name, n_args):
    # 推入this指针(对象引用)
    self.emit_push_var(obj_name)
    
    # 推入参数
    self.compile_expression_list()
    
    # 调用方法，参数数+1(包括this)
    obj_type = self.symbol_table.type_of(obj_name)
    self.vm_writer.write_call(f'{obj_type}.{method_name}', n_args + 1)

11.5 构造函数调用

构造函数调用创建新对象。

构造函数语法

jack
let obj = ClassName.new(args);

构造函数编译

构造函数调用编译为普通函数调用：

python
def compile_constructor_call(self, class_name, method_name, n_args):
    # 推入参数
    self.compile_expression_list()
    
    # 调用构造函数
    self.vm_writer.write_call(f'{class_name}.{method_name}', n_args)

11.6 字符串处理

字符串常量需要特殊处理。

字符串常量编译

jack
let s = "Hello";

编译为：

push constant 5         // 字符串长度
call String.new 1       // 创建新字符串
push constant 72        // 'H'
call String.appendChar 2
push constant 101       // 'e'
call String.appendChar 2
// ... 对每个字符

字符串编译实现

python
def compile_string_constant(self, string):
    # 创建字符串对象
    self.vm_writer.write_push('constant', len(string))
    self.vm_writer.write_call('String.new', 1)
    
    # 逐个添加字符
    for char in string:
        self.vm_writer.write_push('constant', ord(char))
        self.vm_writer.write_call('String.appendChar', 2)

11.7 错误处理

编译器需要能够处理源代码中的错误。

错误类型

词法错误：

jack
let x = @;  // 非法字符

语法错误：

jack
let x = ;   // 缺少表达式

语义错误：

jack
let x = undefinedVar;  // 未定义变量

错误恢复策略

恐慌模式：

python
def panic_mode_recovery(self):
    # 跳过token直到找到同步点
    while self.tokenizer.has_more_tokens():
        self.tokenizer.advance()
        if self.tokenizer.current_token in [';', '}']:
            break

错误产生式：

python
def compile_expression_safe(self):
    try:
        return self.compile_expression()
    except SyntaxError as e:
        self.report_error(e)
        self.panic_mode_recovery()
        return 'int'  # 返回默认类型

11.8 代码优化

虽然Jack编译器很简单，但可以进行一些基本优化。

常量折叠

jack
let x = 5 + 3;

优化为：

push constant 8

死代码消除

jack
if (false) {
    do something();
}

可以完全删除。

优化实现

python
def optimize_constant_expression(self, op, left, right):
    if isinstance(left, int) and isinstance(right, int):
        if op == '+':
            return left + right
        elif op == '-':
            return left - right
        elif op == '*':
            return left * right
        elif op == '/':
            return left // right
    return None  # 无法优化

11.9 编译器架构完善

完整的Jack编译器架构：

JackCompiler
├── JackTokenizer
│   ├── 词法分析
│   └── 错误报告
├── CompilationEngine
│   ├── 语法分析
│   ├── 语义分析
│   └── 代码生成
├── SymbolTable
│   ├── 类作用域
│   └── 子程序作用域
├── TypeChecker
│   ├── 类型推断
│   └── 类型检查
└── VMWriter
    ├── VM代码生成
    └── 标签管理

11.10 多文件编译

Jack程序通常由多个类文件组成。

编译流程

扫描所有.jack文件

为每个文件创建符号表

编译每个文件

生成对应的.vm文件

多文件编译实现

python
def compile_project(self, project_dir):
    jack_files = glob.glob(os.path.join(project_dir, '*.jack'))
    
    # 第一遍：收集所有类信息
    for jack_file in jack_files:
        self.collect_class_info(jack_file)
    
    # 第二遍：编译每个文件
    for jack_file in jack_files:
        vm_file = jack_file.replace('.jack', '.vm')
        self.compile_file(jack_file, vm_file)

重要知识点

知识点1：属性文法

属性文法扩展了上下文无关文法，用于语义分析：

  • 综合属性：从子节点计算
  • 继承属性：从父节点传递
  • 语义规则：定义属性计算方式

知识点2：符号表优化

高效的符号表实现：

  • 哈希表：O(1)平均查找时间
  • 作用域栈：支持嵌套作用域
  • 类型信息：存储完整的类型信息

知识点3：错误报告

良好的错误报告机制：

  • 位置信息：文件名、行号、列号
  • 错误描述：清晰的错误消息
  • 恢复建议：可能的修复方法

知识点4：代码生成策略

代码生成的不同策略：

  • 朴素生成：直接映射，简单但低效
  • 优化生成：应用优化，复杂但高效
  • 延迟生成：收集信息后统一生成

知识点5：测试策略

编译器测试的重要性：

  • 单元测试：测试各个组件
  • 集成测试：测试完整编译流程
  • 回归测试：确保修改不破坏现有功能

常见误区

误区1：忽视类型检查

类型检查是编译器的重要职责。忽视类型检查会导致运行时错误。

误区2：不理解数组的复杂性

数组访问涉及地址计算，是编译器中最容易出错的部分之一。

误区3：忽视错误恢复

编译器必须能够处理错误输入。良好的错误恢复机制对于用户体验至关重要。

误区4：过度优化

虽然优化很重要，但过度优化会增加编译器复杂度。在教学编译器中，简单性比性能更重要。

误区5：不理解多文件编译

真实程序通常由多个文件组成。理解多文件编译的流程对于构建实用编译器很重要。

实践应用

实践1：完善类型检查

python
class TypeChecker:
    def check_subroutine_call(self, name, arg_types):
        # 获取子程序签名
        sig = self.get_subroutine_signature(name)
        
        # 检查参数数量
        if len(arg_types) != len(sig.param_types):
            raise TypeError(f"Wrong number of arguments for {name}")
        
        # 检查参数类型
        for i, (expected, actual) in enumerate(zip(sig.param_types, arg_types)):
            if expected != actual:
                raise TypeError(f"Argument {i} type mismatch: expected {expected}, got {actual}")
        
        return sig.return_type

实践2：完善数组处理

python
def compile_array_assignment(self):
    # let arr[i] = value;
    var_name = self.tokenizer.current_token
    self.tokenizer.advance()
    
    # 获取数组基地址
    self.emit_push_var(var_name)
    
    # 编译索引
    self.tokenizer.advance()  # '['
    self.compile_expression()
    self.tokenizer.advance()  # ']'
    
    # 计算地址
    self.vm_writer.write_arithmetic('add')
    self.vm_writer.write_pop('pointer', 1)
    
    # 编译值
    self.tokenizer.advance()  # '='
    self.compile_expression()
    
    # 存储
    self.vm_writer.write_pop('that', 0)
    self.tokenizer.advance()  # ';'

实践3：完善错误处理

python
class CompilerError(Exception):
    def __init__(self, message, filename, line, column):
        self.message = message
        self.filename = filename
        self.line = line
        self.column = column
        super().__init__(f"{filename}:{line}:{column}: {message}")

class ErrorReporter:
    def __init__(self):
        self.errors = []
        self.warnings = []
    
    def error(self, message, line, column):
        error = CompilerError(message, self.current_file, line, column)
        self.errors.append(error)
    
    def warning(self, message, line, column):
        self.warnings.append(f"{self.current_file}:{line}:{column}: warning: {message}")
    
    def has_errors(self):
        return len(self.errors) > 0
    
    def report(self):
        for error in self.errors:
            print(f"Error: {error}")
        for warning in self.warnings:
            print(f"Warning: {warning}")

实践4：实现代码优化

python
class Optimizer:
    def __init__(self, vm_writer):
        self.vm_writer = vm_writer
        self.pending_instructions = []
    
    def emit(self, instruction):
        self.pending_instructions.append(instruction)
        
        # 尝试优化
        if len(self.pending_instructions) >= 2:
            optimized = self.try_optimize()
            if optimized:
                self.pending_instructions = optimized
    
    def flush(self):
        for instruction in self.pending_instructions:
            self.vm_writer.write(instruction)
        self.pending_instructions = []
    
    def try_optimize(self):
        # 常量折叠
        if (self.pending_instructions[-2].startswith('push constant') and
            self.pending_instructions[-1].startswith('push constant')):
            # 提取常量值
            c1 = int(self.pending_instructions[-2].split()[2])
            c2 = int(self.pending_instructions[-1].split()[2])
            # 等待下一个操作符
            return self.pending_instructions
        
        return None

实践5：完善编译器主程序

python
class JackCompiler:
    def __init__(self):
        self.error_reporter = ErrorReporter()
    
    def compile_file(self, input_file, output_file):
        try:
            tokenizer = JackTokenizer(input_file)
            vm_writer = VMWriter(output_file)
            symbol_table = SymbolTable()
            type_checker = TypeChecker(symbol_table)
            engine = CompilationEngine(tokenizer, vm_writer, symbol_table, type_checker)
            
            engine.compile_class()
            
            vm_writer.close()
            
            if self.error_reporter.has_errors():
                self.error_reporter.report()
                return False
            
            return True
        
        except CompilerError as e:
            print(f"Compilation error: {e}")
            return False
        except Exception as e:
            print(f"Internal compiler error: {e}")
            return False
    
    def compile_directory(self, directory):
        jack_files = glob.glob(os.path.join(directory, '*.jack'))
        
        success = True
        for jack_file in jack_files:
            vm_file = jack_file.replace('.jack', '.vm')
            if not self.compile_file(jack_file, vm_file):
                success = False
        
        return success

实践6：测试完整的编译器

使用复杂的测试程序：

jack
class Complex {
    field int real, imag;
    
    constructor Complex new(int r, int i) {
        let real = r;
        let imag = i;
        return this;
    }
    
    method Complex add(Complex other) {
        var Complex result;
        let result = Complex.new(real + other.getReal(), imag + other.getImag());
        return result;
    }
    
    method int getReal() {
        return real;
    }
    
    method int getImag() {
        return imag;
    }
    
    method void dispose() {
        do Memory.deAlloc(this);
    }
}

class Main {
    function void main() {
        var Complex c1, c2, c3;
        
        let c1 = Complex.new(3, 4);
        let c2 = Complex.new(1, 2);
        let c3 = c1.add(c2);
        
        do Output.printString("Result: ");
        do Output.printInt(c3.getReal());
        do Output.printString(" + ");
        do Output.printInt(c3.getImag());
        do Output.printString("i");
        do Output.println();
        
        do c1.dispose();
        do c2.dispose();
        do c3.dispose();
        
        return;
    }
}

本章小结

本章我们完善了Jack编译器，处理了更复杂的语言特性和边界情况。

核心要点回顾

类型检查：确保程序中的操作对操作数类型是合法的。

作用域规则：Jack有两级作用域，名称解析遵循作用域规则。

数组处理：数组访问涉及地址计算，是编译器中最复杂的部分之一。

对象方法调用：需要传递this指针作为隐含的第一个参数。

字符串处理：字符串常量需要特殊处理，逐个字符构建。

错误处理：编译器需要能够处理各种错误，并提供有用的错误信息。

代码优化：可以进行基本的优化，如常量折叠和死代码消除。

多文件编译：真实程序通常由多个文件组成，需要协调编译。

关键技能掌握

  • 理解类型检查的原理和实现
  • 掌握作用域规则和名称解析
  • 能够处理数组访问
  • 理解对象方法调用的编译
  • 掌握错误处理和恢复技术
  • 能够进行基本的代码优化

与后续章节的联系

本章完成的编译器是后续章节的基础：

  • 第十二章将实现Jack标准库，为编译后的程序提供运行时支持
  • 标准库包括Math、String、Array、Output、Keyboard、Screen、Memory、Sys等类

学习建议

重视细节：编译器是一个复杂的系统，细节决定成败

充分测试：使用各种测试程序验证编译器的正确性

模块化设计：将编译器分解为独立的模块，便于开发和维护

错误处理：良好的错误处理机制对于用户体验至关重要

通过本章的学习，你已经掌握了完整编译器的构建技术。从词法分析到代码生成，编译器展示了软件工程的许多重要概念。理解编译器的工作原理，对于理解编程语言和计算本质至关重要。现在，我们有了完整的编译器，下一步是实现标准库，为Jack程序提供运行时支持。