第六章汇编器

导读

在前一章中，我们构建了完整的Hack计算机，并学习了机器语言编程。然而，直接使用二进制代码编程极其繁琐且容易出错。本章将构建汇编器——一个将符号化的汇编语言转换为机器语言的工具。

汇编器是软件工具链中最基础的组件之一。它架起了人类可读的符号语言和机器可执行的二进制代码之间的桥梁。通过本章的学习，你将理解汇编器的工作原理，掌握符号解析和代码生成的技术，并为后续章节中构建更复杂的编译器奠定基础。

汇编器的构建展示了软件工程的一个重要原则：通过抽象和自动化，将复杂任务简化。汇编器让我们可以使用符号名称而不是数字地址，大大提高了编程的效率和可读性。

核心概念详解

6.1 汇编语言概述

汇编语言是机器语言的符号表示，使用助记符代替二进制代码。

汇编语言的特点

符号化：使用符号名称代替数字地址

可读性：比机器语言更易读易写

一一对应：每条汇编指令对应一条机器指令

硬件相关：与特定计算机架构紧密相关

Hack汇编语言

Hack汇编语言是Hack机器语言的符号表示，包括：

A指令：

@symbol

其中symbol可以是数字或符号名称。

C指令：

dest=comp;jump

其中dest、comp、jump使用符号表示。

6.2 汇编过程

汇编是将汇编语言转换为机器语言的过程。

汇编的两个阶段

汇编过程通常分为两个阶段：

第一遍(First Pass)：

扫描整个程序
收集所有符号标签及其地址
构建符号表

第二遍(Second Pass)：

再次扫描程序
将每条汇编指令转换为机器指令
使用符号表解析符号引用

为什么需要两遍

两遍汇编的必要性源于前向引用(forward reference)问题：

@loop    // 引用尚未定义的标签
...
(loop)   // 标签定义在后面

在第一遍中，我们记录所有标签的地址。在第二遍中，我们可以解析所有符号引用。

6.3 符号表

符号表是汇编器的核心数据结构，存储符号名称到地址的映射。

符号类型

Hack汇编语言中有三种类型的符号：

预定义符号：

预定义寄存器：SP=0, LCL=1, ARG=2, THIS=3, THAT=4
预定义屏幕/键盘：SCREEN=16384, KBD=24576
寄存器R0-R15：R0=0, R1=1, ..., R15=15

标签符号：

在代码中定义的标签
地址是下一条指令的地址
例如：(loop)定义标签loop

变量符号：

在@指令中引用的未定义符号
自动分配到第一个可用的RAM地址
从地址16开始分配

符号表实现

符号表通常使用哈希表实现，提供O(1)的平均查找时间：

python

class SymbolTable:
    def __init__(self):
        self.table = {}
        # 初始化预定义符号
        self.add_predefined()
    
    def add_entry(self, symbol, address):
        self.table[symbol] = address
    
    def contains(self, symbol):
        return symbol in self.table
    
    def get_address(self, symbol):
        return self.table[symbol]

6.4 指令解析

解析汇编指令是汇编器的核心功能。

A指令解析

A指令格式：@symbol

解析步骤：

提取符号(数字或名称)

如果是数字，直接转换为15位二进制

如果是符号，查表获取地址

生成16位指令：0 + 15位地址

示例：

@5       -> 0000000000000101
@loop    -> 0 + loop的地址
@SCREEN  -> 0100000000000000

C指令解析

C指令格式：dest=comp;jump

解析步骤：

解析comp字段，生成6位c字段和1位a字段

解析dest字段，生成3位d字段

解析jump字段，生成3位j字段

组合成16位指令：111 + a + c + d + j

示例：

D=A      -> 111 0 110000 010 000
M=D+1    -> 111 0 011111 001 000
D;JGT    -> 111 0 001100 000 001

6.5 代码生成

代码生成是将解析后的指令转换为二进制机器码。

A指令生成

python

def generate_a_instruction(address):
    # 16位：0 + 15位地址
    return format(0x8000 | address, '016b')

C指令生成

python

def generate_c_instruction(a, c, d, j):
    # 16位：111 + a(1位) + c(6位) + d(3位) + j(3位)
    instruction = 0xE000  # 1110000000000000
    instruction |= (a << 12)
    instruction |= (c << 6)
    instruction |= (d << 3)
    instruction |= j
    return format(instruction, '016b')

6.6 标签处理

标签是汇编语言中最重要的符号之一。

标签定义

标签定义格式：(label)

标签的地址是下一条指令的地址。在汇编过程中：

维护指令计数器，初始为0

遇到标签时，将标签和当前指令计数器关联

遇到A或C指令时，指令计数器递增

示例：

(loop)     // loop = 0
@5
D=A
(next)     // next = 2

标签引用

标签可以在@指令中引用：

@loop      // 引用标签loop

在第二遍汇编时，使用符号表解析标签地址。

6.7 变量分配

当@指令引用未定义的符号时，汇编器将其视为变量。

变量分配策略

维护变量计数器，初始为16

遇到未定义符号时：

- 分配当前变量计数器的值作为地址

- 将符号添加到符号表

- 变量计数器递增

示例：

@x         // x = 16
@y         // y = 17
@x         // 使用已分配的地址16

6.8 汇编器实现

完整的汇编器实现包括以下组件：

主程序流程

python

def assemble(input_file, output_file):
    # 第一遍：构建符号表
    symbol_table = first_pass(input_file)
    
    # 第二遍：生成机器码
    second_pass(input_file, output_file, symbol_table)

第一遍实现

python

def first_pass(input_file):
    symbol_table = SymbolTable()
    rom_address = 0
    
    for line in input_file:
        line = remove_comments(line)
        if is_label(line):
            label = extract_label(line)
            symbol_table.add_entry(label, rom_address)
        elif is_instruction(line):
            rom_address += 1
    
    return symbol_table

第二遍实现

python

def second_pass(input_file, output_file, symbol_table):
    ram_address = 16
    
    for line in input_file:
        line = remove_comments(line)
        if is_a_instruction(line):
            symbol = extract_symbol(line)
            if symbol.isdigit():
                address = int(symbol)
            elif symbol_table.contains(symbol):
                address = symbol_table.get_address(symbol)
            else:
                symbol_table.add_entry(symbol, ram_address)
                address = ram_address
                ram_address += 1
            output_file.write(generate_a_instruction(address))
        elif is_c_instruction(line):
            output_file.write(generate_c_instruction(line))

重要知识点

知识点1：单遍vs多遍汇编

单遍汇编：

只扫描源程序一次
需要限制前向引用
速度快，内存需求小

多遍汇编：

扫描源程序多次
支持任意前向引用
功能更强大，但速度较慢

现代汇编器通常使用多遍汇编以获得更好的功能。

知识点2：宏汇编

宏是汇编语言的扩展功能：

定义可重用的代码片段
支持参数替换
在汇编时展开

宏汇编器需要额外的处理来展开宏定义。

知识点3：目标代码格式

汇编器输出的目标代码有多种格式：

绝对二进制：包含地址信息的二进制文件
可重定位二进制：可以加载到任意地址
目标文件：包含符号信息和重定位信息

Hack汇编器输出简单的二进制文件，每行一条16位指令。

知识点4：错误处理

汇编器需要检测并报告各种错误：

语法错误：指令格式不正确
符号错误：未定义的符号引用
地址错误：地址超出范围
重复定义：标签重复定义

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

知识点5：优化技术

虽然Hack汇编器很简单，但实际汇编器可能包含优化：

指令选择优化：选择更高效的指令序列
地址分配优化：优化变量地址分配
代码压缩：减少代码大小

常见误区

误区1：认为汇编器很复杂

实际上，基本的汇编器相对简单。它主要做两件事：构建符号表和转换指令。复杂的汇编器通常包含更多高级功能。

误区2：忽视符号表的重要性

符号表是汇编器的核心数据结构。正确实现符号表对于汇编器的正确性至关重要。

误区3：不理解两遍汇编的必要性

两遍汇编解决了前向引用问题。如果不理解这一点，可能会尝试用单遍汇编处理所有情况，导致错误。

误区4：混淆标签和变量

标签和变量虽然都使用符号表示，但处理方式不同：

标签在定义时确定地址
变量在首次引用时分配地址

误区5：忽视错误处理

错误处理是汇编器的重要组成部分。忽视错误处理会导致汇编器在遇到错误时崩溃或产生错误的输出。

实践应用

实践1：实现符号表

python

class SymbolTable:
    def __init__(self):
        self.table = {
            'SP': 0, 'LCL': 1, 'ARG': 2, 'THIS': 3, 'THAT': 4,
            'R0': 0, 'R1': 1, 'R2': 2, 'R3': 3, 'R4': 4,
            'R5': 5, 'R6': 6, 'R7': 7, 'R8': 8, 'R9': 9,
            'R10': 10, 'R11': 11, 'R12': 12, 'R13': 13, 'R14': 14,
            'R15': 15, 'SCREEN': 16384, 'KBD': 24576
        }
    
    def add_entry(self, symbol, address):
        self.table[symbol] = address
    
    def contains(self, symbol):
        return symbol in self.table
    
    def get_address(self, symbol):
        return self.table[symbol]

实践2：实现指令解析器

python

class Parser:
    def __init__(self, input_file):
        self.lines = input_file.readlines()
        self.current_line = 0
    
    def has_more_lines(self):
        return self.current_line < len(self.lines)
    
    def advance(self):
        self.current_line += 1
    
    def instruction_type(self):
        line = self.current_instruction()
        if line.startswith('@'):
            return 'A_INSTRUCTION'
        elif line.startswith('('):
            return 'L_INSTRUCTION'
        else:
            return 'C_INSTRUCTION'
    
    def symbol(self):
        line = self.current_instruction()
        if self.instruction_type() == 'A_INSTRUCTION':
            return line[1:].strip()
        elif self.instruction_type() == 'L_INSTRUCTION':
            return line[1:-1].strip()
    
    def comp(self):
        line = self.current_instruction()
        if '=' in line:
            return line.split('=')[1].split(';')[0]
        else:
            return line.split(';')[0]
    
    def dest(self):
        line = self.current_instruction()
        if '=' in line:
            return line.split('=')[0]
        else:
            return 'null'
    
    def jump(self):
        line = self.current_instruction()
        if ';' in line:
            return line.split(';')[1]
        else:
            return 'null'

实践3：实现代码生成器

python

class Code:
    def __init__(self):
        self.comp_table = {
            '0': '0101010', '1': '0111111', '-1': '0111010',
            'D': '0001100', 'A': '0110000', '!D': '0001101',
            '!A': '0110001', '-D': '0001111', '-A': '0110011',
            'D+1': '0011111', 'A+1': '0110111', 'D-1': '0001110',
            'A-1': '0110010', 'D+A': '0000010', 'D-A': '0010011',
            'A-D': '0000111', 'D&A': '0000000', 'D|A': '0010101',
            'M': '1110000', '!M': '1110001', '-M': '1110011',
            'M+1': '1110111', 'M-1': '1110010', 'D+M': '1000010',
            'D-M': '1010011', 'M-D': '1000111', 'D&M': '1000000',
            'D|M': '1010101'
        }
        
        self.dest_table = {
            'null': '000', 'M': '001', 'A': '010', 'D': '100',
            'AM': '011', 'AD': '110', 'MD': '101', 'AMD': '111'
        }
        
        self.jump_table = {
            'null': '000', 'JGT': '001', 'JEQ': '010', 'JGE': '011',
            'JLT': '100', 'JNE': '101', 'JLE': '110', 'JMP': '111'
        }
    
    def comp(self, comp_symbol):
        return self.comp_table[comp_symbol]
    
    def dest(self, dest_symbol):
        return self.dest_table[dest_symbol]
    
    def jump(self, jump_symbol):
        return self.jump_table[jump_symbol]

实践4：实现完整的汇编器

python

class Assembler:
    def __init__(self, input_file, output_file):
        self.parser = Parser(input_file)
        self.code = Code()
        self.symbol_table = SymbolTable()
        self.output_file = output_file
    
    def assemble(self):
        self.first_pass()
        self.second_pass()
    
    def first_pass(self):
        rom_address = 0
        while self.parser.has_more_lines():
            self.parser.advance()
            if self.parser.instruction_type() == 'L_INSTRUCTION':
                symbol = self.parser.symbol()
                self.symbol_table.add_entry(symbol, rom_address)
            elif self.parser.instruction_type() in ['A_INSTRUCTION', 'C_INSTRUCTION']:
                rom_address += 1
    
    def second_pass(self):
        ram_address = 16
        self.parser.reset()
        
        while self.parser.has_more_lines():
            self.parser.advance()
            if self.parser.instruction_type() == 'A_INSTRUCTION':
                symbol = self.parser.symbol()
                if symbol.isdigit():
                    address = int(symbol)
                elif self.symbol_table.contains(symbol):
                    address = self.symbol_table.get_address(symbol)
                else:
                    self.symbol_table.add_entry(symbol, ram_address)
                    address = ram_address
                    ram_address += 1
                self.write_a_instruction(address)
            elif self.parser.instruction_type() == 'C_INSTRUCTION':
                self.write_c_instruction()
    
    def write_a_instruction(self, address):
        binary = format(0x8000 | address, '016b')
        self.output_file.write(binary + '\n')
    
    def write_c_instruction(self):
        comp = self.code.comp(self.parser.comp())
        dest = self.code.dest(self.parser.dest())
        jump = self.code.jump(self.parser.jump())
        a = '1' if 'M' in self.parser.comp() else '0'
        binary = '111' + a + comp + dest + jump
        self.output_file.write(binary + '\n')

实践5：测试汇编器

使用提供的测试程序测试汇编器：

// 测试程序：Add.asm
// 计算R0 + R1，结果存入R2

@R0
D=M
@R1
D=D+M
@R2
M=D

预期输出：

0000000000000000
1111110000010000
0000000000000001
1110000010010000
0000000000000010
1110001100001000

实践6：处理复杂程序

测试包含标签和变量的程序：

// 计算1+2+...+n
@n
D=M
@sum
M=0
@i
M=0
(LOOP)
@i
D=M
@n
D=D-M
@END
D;JGT
@i
D=M
@sum
M=M+D
@i
M=M+1
@LOOP
0;JMP
(END)
@END
0;JMP

本章小结

本章我们构建了完整的Hack汇编器，将符号化的汇编语言转换为机器语言。

核心要点回顾

汇编语言：机器语言的符号表示，使用助记符代替二进制代码。

汇编过程：分为两遍，第一遍构建符号表，第二遍生成机器码。

符号表：存储符号名称到地址的映射，是汇编器的核心数据结构。

指令解析：解析A指令和C指令的各个字段。

代码生成：将解析后的指令转换为16位二进制机器码。

标签和变量：标签在定义时确定地址，变量在首次引用时分配地址。

关键技能掌握

理解汇编器的工作原理
掌握两遍汇编的方法
能够实现符号表
能够解析和生成机器指令
能够处理标签和变量

与后续章节的联系

本章构建的汇编器是后续章节的基础：

第七章和第八章将介绍虚拟机，提供更高级的抽象
第九章将介绍高级语言Jack
第十章和第十一章将构建Jack编译器
编译器最终会生成汇编代码，由汇编器转换为机器码

学习建议

理解原理：深入理解汇编器的工作原理，而不仅仅是实现

动手实践：亲手实现汇编器的各个组件

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

思考扩展：思考如何扩展汇编器以支持更多功能

通过本章的学习，你已经掌握了汇编器的核心知识。汇编器是软件工具链的基础组件，理解其工作原理对于理解整个软件栈至关重要。从机器语言到汇编语言，再到高级语言，每一层抽象都让编程变得更加容易和高效。

第六章 汇编器

导读

核心概念详解

6.1 汇编语言概述

汇编语言的特点

Hack汇编语言

6.2 汇编过程

汇编的两个阶段

为什么需要两遍

6.3 符号表

符号类型

符号表实现

6.4 指令解析

A指令解析

C指令解析

6.5 代码生成

A指令生成

C指令生成

6.6 标签处理

标签定义

标签引用

6.7 变量分配

变量分配策略

6.8 汇编器实现

主程序流程

第一遍实现

第二遍实现

重要知识点

知识点1：单遍vs多遍汇编

知识点2：宏汇编

知识点3：目标代码格式

知识点4：错误处理

知识点5：优化技术

常见误区

误区1：认为汇编器很复杂

误区2：忽视符号表的重要性

误区3：不理解两遍汇编的必要性

误区4：混淆标签和变量

误区5：忽视错误处理

实践应用

实践1：实现符号表

实践2：实现指令解析器

实践3：实现代码生成器

实践4：实现完整的汇编器

实践5：测试汇编器

实践6：处理复杂程序

本章小结

核心要点回顾

关键技能掌握

与后续章节的联系

学习建议

第六章汇编器