06. Assembler
术语
机器语言一般分为两类：二进制型（binary）和符号型（symbolic）。
符号化的语言称为汇编（assembly），翻译程序称为汇编编译器（assembler）。
变量（Variable）程序员可以使用符号的变量名称，翻译器会自动为其分配内存地址。
标签（Labels）在程序中用符号来标注不同的位置。
二进制代码（.hack）文件：每一行由 16 个 0/1 组成的 ASCII 码构成一个序列。文件的所有行在整体上代表一个机器语言程序。 当机器语言程序被加载到计算机的指令内存时，文件的第 n 行会被存储到地址为 n 的指令内存单元中。
汇编语言（.asm）文件：由文本行组成，每一行代表一个指令（instruction）或者一个符号声明（symbol declaration）。
第四章其实也涉及了这部分内容，包括 A 指令和 C 指令的具体格式，语法规约以及预定义符号。
Hack 汇编编译器
一个基于 4 个模块的实现：
- 语法分析器（Parser）模块用来对输入文件进行语法解析
- 编码（Code）模块用来提供所有汇编命令对应的二进制代码
- 符号表（Symbol Table）模块用来处理符号
- 最后一个主程序来驱动整个编译过程
Parser Module
| 程序 | 参数 | 返回值 | 功能 |
|---|---|---|---|
| Constructor/initializer | Input file/stream | — | 打开输入文件/输入流，为语法解析做准备 |
| hasMoreCommands | — | Boolean | 输入中还有更多命令吗？ |
| advance | — | — | 从输入中读取下一条命令，将其当做当前命令。仅当 hasMoreCommands() 返回 True 时才能调用。最开始的时候没有当前命令 |
| commandType | — | A_COMMAND，C_COMMAND，L_COMMAND | 返回当前命令的类型：A_COMMAND @Xxx 中的 Xxx 是符号或者数字时；C_COMMAND 用于 dest=comp;jump；L_COMMAND 实际上是伪命令，当 (Xxx) 中的 Xxx 是符号时 |
| symbol | — | string | 返回形如 @Xxx 或 (Xxx) 的当前命令的符号或十进制。仅当 commandType() 是 A_COMMAND 或 L_COMMAND 时才能调用 |
| dest | — | string | 返回当前 C 指令的 dest 助记符（具有 8 种可能的形式）。仅当 commandType() 是 C_COMMAND 时才能调用 |
| comp | — | string | 返回当前 C 指令的 comp 助记符（具有 28 种可能的形式）。仅当 commandType() 是 C_COMMAND 时才能调用 |
| jump | — | string | 返回当前 C 指令的 jump 助记符（具有 8 种可能的形式）。仅当 commandType() 是 C_COMMAND 时才能调用 |
Code Module
| 程序 | 参数 | 返回值 | 功能 |
|---|---|---|---|
| dest | mnemonic (string) | 3 bits | 返回 dest 助记符的二进制代码 |
| comp | mnemonic (string) | 7 bits | 返回 comp 助记符的二进制代码 |
| jump | mnemonic (string) | 3 bits | 返回 jump 助记符的二进制代码 |
Symbol Table Module
| 程序 | 参数 | 返回值 | 功能 |
|---|---|---|---|
| Constructor | - | - | 创建空的符号表 |
| addEntry | symbol (string), address (int) | - | 将 (symbol, address) 配对加入符号表 |
| contains | symbol (string) | Boolean | 符号表中是否包含该符号？ |
| getAddress | symbol (string) | int | 返回与符号相关联的地址 |
Main Program
符号定义前即可使用符号标签，需要编写 two-pass 汇编编译器，从头至尾地读取两次代码。
第一次读取（First Pass）：要在符号表中建立每条命令及其对应的地址。ROM 地址从 0 开始，逐行读取代码，遇到 C 或 A 指令都自动加一，遇到 L 指令则将符号和当前 ROM 地址的值加入符号表中。
第二次读取（Second Pass）：遇到 A 指令的 @Xxx 中的 Xxx 是一个符号时，就在符号表中查找该符号。如果符号表中没有该符号，那么它必定代表变量。为了处理这个变量，就在符号表中添加 (Xxx, n)，这里 n 是下一个可用的 RAM 地址（从 16 开始）。
Project 06
项目已经把 API 定义好了，剩下的就是填充内容了。
py
import sys
from pathlib import Path
A_COMMAND = "A_COMMAND"
C_COMMAND = "C_COMMAND"
L_COMMAND = "L_COMMAND"
# =========================
# Parser Module
# =========================
class Parser:
"""Parses Hack assembly commands and exposes their fields."""
def __init__(self, input_file):
with input_file.open() as file:
self.commands = self._clean_lines(file.readlines())
self.current_index = -1
self.current_command = None
def _clean_lines(self, lines):
cleaned = []
for line in lines:
line = line.split("//")[0].strip()
if line != "":
cleaned.append(line)
return cleaned
def has_more_commands(self):
return self.current_index + 1 < len(self.commands)
def advance(self):
self.current_index += 1
self.current_command = self.commands[self.current_index]
def command_type(self):
if self.current_command.startswith("@"):
return A_COMMAND
if self.current_command.startswith("(") and self.current_command.endswith(")"):
return L_COMMAND
return C_COMMAND
def symbol(self):
if self.command_type() == A_COMMAND:
return self.current_command[1:]
if self.command_type() == L_COMMAND:
return self.current_command[1:-1]
return None
def dest(self):
if "=" not in self.current_command:
return None
return self.current_command.split("=")[0]
def comp(self):
command = self.current_command
if "=" in command:
command = command.split("=")[1]
if ";" in command:
command = command.split(";")[0]
return command
def jump(self):
if ";" not in self.current_command:
return None
return self.current_command.split(";")[1]
# =========================
# Code Module
# =========================
class Code:
"""Translates Hack assembly mnemonics into binary codes."""
DEST_TABLE = {
None: "000",
"M": "001",
"D": "010",
"MD": "011",
"DM": "011",
"A": "100",
"AM": "101",
"MA": "101",
"AD": "110",
"DA": "110",
"AMD": "111",
"ADM": "111",
"MAD": "111",
"MDA": "111",
"DAM": "111",
"DMA": "111",
}
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",
"A+D": "0000010",
"D-A": "0010011",
"A-D": "0000111",
"D&A": "0000000",
"A&D": "0000000",
"D|A": "0010101",
"A|D": "0010101",
"M": "1110000",
"!M": "1110001",
"-M": "1110011",
"M+1": "1110111",
"M-1": "1110010",
"D+M": "1000010",
"M+D": "1000010",
"D-M": "1010011",
"M-D": "1000111",
"D&M": "1000000",
"M&D": "1000000",
"D|M": "1010101",
"M|D": "1010101",
}
JUMP_TABLE = {
None: "000",
"JGT": "001",
"JEQ": "010",
"JGE": "011",
"JLT": "100",
"JNE": "101",
"JLE": "110",
"JMP": "111",
}
@classmethod
def dest(cls, mnemonic):
return cls.DEST_TABLE[mnemonic]
@classmethod
def comp(cls, mnemonic):
return cls.COMP_TABLE[mnemonic]
@classmethod
def jump(cls, mnemonic):
return cls.JUMP_TABLE[mnemonic]
# =========================
# Symbol Table Module
# =========================
class SymbolTable:
"""Keeps a correspondence between symbols and numeric addresses."""
def __init__(self):
self.table = {
"SP": 0,
"LCL": 1,
"ARG": 2,
"THIS": 3,
"THAT": 4,
"SCREEN": 16384,
"KBD": 24576,
}
for i in range(16):
self.table[f"R{i}"] = i
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]
# =========================
# Main Program
# =========================
def first_pass(input_file, symbol_table):
"""Add labels to the symbol table. Generates no code."""
parser = Parser(input_file)
rom_address = 0
while parser.has_more_commands():
parser.advance()
command_type = parser.command_type()
if command_type == L_COMMAND:
symbol = parser.symbol()
symbol_table.add_entry(symbol, rom_address)
else:
rom_address += 1
def second_pass(input_file, output_file, symbol_table):
"""Translate A- and C-commands. Allocate new variables from RAM address 16."""
parser = Parser(input_file)
next_variable_address = 16
with output_file.open("w") as file:
while parser.has_more_commands():
parser.advance()
command_type = parser.command_type()
if command_type == L_COMMAND:
continue
if command_type == A_COMMAND:
symbol = parser.symbol()
if symbol.isdigit():
address = int(symbol)
else:
if not symbol_table.contains(symbol):
symbol_table.add_entry(symbol, next_variable_address)
next_variable_address += 1
address = symbol_table.get_address(symbol)
file.write(format(address, "016b") + "\n")
elif command_type == C_COMMAND:
comp_bits = Code.comp(parser.comp())
dest_bits = Code.dest(parser.dest())
jump_bits = Code.jump(parser.jump())
file.write("111" + comp_bits + dest_bits + jump_bits + "\n")
def assemble(input_file):
symbol_table = SymbolTable()
output_file = input_file.with_suffix(".hack")
first_pass(input_file, symbol_table)
second_pass(input_file, output_file, symbol_table)
def main():
if len(sys.argv) != 2:
print("Usage: python assembler.py Xxx.asm")
sys.exit(1)
input_file = Path(sys.argv[1])
if input_file.suffix != ".asm":
print("Error: input file must end with .asm")
sys.exit(1)
assemble(input_file)
if __name__ == "__main__":
main()