Assembler Roadmap

Week 6 notes

• Assembler（汇编器） 通过 Cross-compiling 的方式实现，即使用已存在的计算机生成新计算机的 Assembler。
• Assemblers 是软件层的第一层

汇编器重复以下的功能：

1. 读取下一条汇编命令
2. 将命令分解为几个部分
3. 查找每部分对应的二进制代码
4. 将这些代码组合为一整条机器语言命令
5. 输出该机器语言命令

以下面的汇编代码为例：

// Start processing the table
Load R1, 18

1. 读取时，会按行读取。读取时会忽略掉 whitespace 内容，得到的内容会存到一个数组中
2. 将读取的指令分为几个部分（字符串），比如：Load, R1, 18
3. 通过command-opcode 的对照表来进行翻译（主要是命令），某些数字可以直接进行翻译
4. 将所有的内容组合在一起，形成机器语言指令，并进行输出

汇编语言中存在着 symbols，以便提高程序的可读性，比如：

• Labels：JMP loop
• Variables：Load R1, weight

而在汇编器翻译的过程中，这些 symbols 都会被替代为其对应的地址，比如 loop 对应的是跳转后的指令地址，weight 对应的是在 RAM 里面的寄存器所属地址。这种翻译也是依赖对应的 map 来实现的：

第一次进入 symbol table 的变量需要汇编器为其安排 table 中的位置。通常，汇编器会在 RAM 中找到第一个可用的内存单元（Unallocated memory cell）来存放该变量。

Label 需要处理额外的两件事：

• 保证 Label 下的所有命令都是基于 Label 的地址
• 如果引用 Label 的位置发生在第一次看到 Label 定义之前（也就是表内还没有 记录Label 地址的时候），有两种处理方式：
  • 将未定义的标签放入一个待解决的 table 中，将其标记为尚未解析的状态，之后看到该 label 的定义时，再回填正确地址到引用该 label 的位置
  • 或是做两遍全扫描（C++ 类就是这么干的）: 第一遍只看标签的定义，将其与地址关联起来，第二遍才是真正的将指令翻译为机器码的过程

• A-instruction
• C-instruciton
• Symbols：
  • 预定义的(Pre-defined) 的 symbol
  • label 声明
  • 变量声明

需要汇编器处理的元素有：

• White space：会被处理中被忽略
  • Empty lines / indentation
  • In-line & line comments
• Instructions
• Symbols
  • References
  • Label

对于 ROM 所有的指令：

• 首先对其进行解析，并将其拆分为指定的部分
• 其次根据指令的类型，来进行对应的转换
• 将所有转化的结果组合起来，并输出到对应的文件中

A 指令的结构表现为： @ + value ，因此将 A 指令转化为二进制取决于：

• 如果 value 是十进制常量（比如 @21），那么直接转成对应的 15 位的二进制常量
• 如果 value 是 symbol，交给之后的 symbol 区域处理。

首先回顾一下，C 指令的机器语言组成如下图所示：


因此，如果希望翻译 C 指令，那么首先需要做的就是将汇编语言按照机器语言的组成来进行划分。通常这部分会由 Parser（解析器）来完成。以下面的汇编语句为例：

// 将 D + 1 的值存储到 M 和 D 寄存器中
MD = D + 1

1. C 指令中 15-13 这三位永远都是 111，可以将其先填入
2. 对 comp 这部分 12..6（a 和 comp）进行翻译。这部分通过对照 C 指令的 table 来获取二进制代码。比如例子中的计算部分 D+1，对应的 a 是 0，对应的六位 comp 是 011111，那么这一部分对应的代码就是 0011111
3. 对 dest 这部分 5..3 进行翻译。这部分的翻译也是通过查表：比如例子中的 MD，对应的是 011
4. 对 jump 这部分 2..0 进行翻译，同样也是通过查表：本例中没有跳转部分（null），对应的 bits 是 000
5. 最后得到的翻译结果是 111 0011111 011 000

之前介绍过，根据 symbol 的内容，可以将 symbol 划分为三种类型：

• varible symbol：代表着用于数据操作的内存位置，该地址映射由汇编器管理
• label symbol：代表着 goto 跳转的指令位置
• pre-defined symbols：代表着系统占用的特殊内存位置

由于这些 symbol 只会在 A 指令中出现，因此只需要根据对照表，将 symbol 转化为对应的地址值即可：比如

// R1 corresponds address 1
@R1->@1

label 类型的 symbol 主要用于：

• 标记 goto 命令的终点，比如 @loop。这类 symbol 会被直接替换成其值（与 pre-defined symbol 类似），比如下面例子中的 LOOP 会被替换为 16
• 对应的伪代码声明，比如 (loop)：这类 label 通常不会进行翻译，但汇编器遇到这类 label 时，会将其对应的 symbol 与其起始行关联起来。比如：

@i // line 0
M=1
@sum
M=0

(LOOP) // not a instruction line
    @i // line 4
    ...
    @LOOP //line 16

变量类型的 symbol 指非提前定义的，且没有使用 driective 在别处进行定义的（比如 LOOP）的 symbol。上面例子中的 @i，@sum 都是变量类型的 symbol。之前提到过，这类 symbol 都会被存储在一个独特地址的内存单元中（地址从 16 开始）。因此这类 symbol 对应的值，是他们所在内存单元的地址：

由于变量可能会被多次用到，当第一次用到时，该变量 symbol 和其对应地址会被加入到映射表中；之后再使用时，汇编器会从映射表中查找到该对应关系，并把 symbol 翻译为对应的地址。

可以看到的是，上述的所有翻译都依赖于一种数据结构：Symbol table，用于建立翻译的映射关系。Hack 计算机的 Symbol table 通过几个阶段进行构造：

• 初始化：这个阶段会建立一张空表，并将 pre-defined symbol 的映射关系写入表中
• 寻找 label 声明：这个阶段（first pass）会扫描整个指令序列，将所有的 label 声明找出来
  • 当遇到 ( 的时候，就识别为 label 的声明
  • 同时维护一个计数器，对行数计数。记录的是已经扫描过的行数：比如之前的 (LOOP)，其对应的数据是之前已经扫描过的行数 4
  • 然后接着扫描，直到遇到下一个 ( 开头的 label 声明，重复上面的过程，直到构建出整个 Symbol table 中的 label 声明数据
• 变量处理（second pass）：这个阶段会再次扫描指令序列，寻找变量，再将其与 RAM地址关联，并写入关系到 Symbol table 中：
  • 新变量会直接加入 symbol table
  • 已存在的变量会直接读取 symbol table 中的对应映射关系

// init
- construct an empty symbol table
- add the pre-defined symbols to the symbol table

// first pass
// adding label declaration to the symbol table
- scan the program
- For each instruction of the form(xxx):
    - add the pair(xxx, address) to the symbol table, where address is the number of the instruction following (xxx)

// second pass
// adding variable symbol to the symbol table
- scan the program
- For each instruction:
    - if the insturction is @symbol, look up the symbol in the table
        - if (symbol, value) is found, use value to complete the instruction's translation
        - if not found
            - add(symbol, n) to the symbol table
            - use n to complete the instruction translation
            - ++n
    - if the instruction is a C-instruction, complate the instruction translation
- write the translated instruction to the output file