======Assembler Roadmap======
//Week 6 notes//
----
====Assembly Languages and Assemblers====
  * //Assembler//（汇编器） 通过 //Cross-compiling// 的方式实现，即使用已存在的计算机生成新计算机的 Assembler。
  * Assemblers 是软件层的第一层
===Basic Assmbler Logic===
汇编器重复以下的功能：
  - 读取下一条汇编命令
  - 将命令分解为几个部分
  - 查找每部分对应的二进制代码
  - 将这些代码组合为一整条机器语言命令
  - 输出该机器语言命令
==读取逻辑==
以下面的汇编代码为例：
<code bash>
// Start processing the table
Load R1, 18
</code>
  - 读取时，会按行读取。读取时会忽略掉 whitespace 内容，得到的内容会存到一个数组中
  - 将读取的指令分为几个部分（字符串），比如：''Load'', ''R1'', ''18''
  - 通过command-opcode 的对照表来进行翻译（主要是命令），某些数字可以直接进行翻译
  - 将所有的内容组合在一起，形成机器语言指令，并进行输出
\\ 
{{ :cs:comp_n_arch:courses:fnti_i:ass_logic.svg?450 |}}
===Symbols===
汇编语言中存在着 //symbols//，以便提高程序的可读性，比如：
  * Labels：''JMP loop''
  * Variables：''Load R1, weight''
==symbol table==
而在汇编器翻译的过程中，这些 symbols 都会被替代为其对应的**地址**，比如 ''loop'' 对应的是跳转后的指令地址，''weight'' 对应的是在 RAM 里面的寄存器所属地址。这种翻译也是依赖对应的 map 来实现的：
\\ \\ {{ :cs:comp_n_arch:courses:fnti_i:symbol_table.svg?150 |}}
==allocation of variables==
第一次进入 symbol table 的变量需要汇编器为其安排 table 中的位置。通常，汇编器会在 RAM 中找到第一个可用的内存单元（//Unallocated memory cell//）来存放该变量。
==Labels==
Label 需要处理额外的两件事：
  * 保证 Label 下的所有命令都是基于 Label 的地址
  * 如果引用 Label 的位置发生在第一次看到 Label 定义之前（也就是表内还没有 记录Label 地址的时候），有两种处理方式：
    * 将未定义的标签放入一个待解决的 table 中，将其标记为尚未解析的状态，之后看到该 label 的定义时，再回填正确地址到引用该 label 的位置
    * 或是做两遍全扫描（C++ 类就是这么干的）: 第一遍只看标签的定义，将其与地址关联起来，第二遍才是真正的将指令翻译为机器码的过程
====Hack Assembly Language====
  * A-instruction
  * C-instruciton
  * Symbols：
    * 预定义的(//Pre-defined//) 的 symbol
    * label 声明
    * 变量声明
===Assembly program 中的元素===
需要汇编器处理的元素有：
  * White space：会被处理中被忽略
    * Empty lines / indentation
    * In-line & line comments
  * Instructions
  * Symbols
    * References
    * Label
====Instruction Handling====
===外部总逻辑===
对于 ROM 所有的指令：
  * 首先对其进行解析，并将其拆分为指定的部分
  * 其次根据指令的类型，来进行对应的转换
  * 将所有转化的结果组合起来，并输出到对应的文件中
===Translating A-instructions===
A 指令的结构表现为： ''@ + value'' ，因此将 A 指令转化为二进制取决于：
  * 如果 value 是十进制常量（比如 ''@21''），那么直接转成对应的 ''15'' 位的二进制常量
  * 如果 value 是 symbol，交给之后的 symbol 区域处理。
===Translating C-instructions===
首先回顾一下，C 指令的机器语言组成如下图所示：
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:c-ins.svg?400 |}}
\\ 
因此，如果希望翻译 C 指令，那么首先需要做的就是将汇编语言按照机器语言的组成来进行划分。通常这部分会由 //Parser//（解析器）来完成。以下面的汇编语句为例：
<code cpp>
// 将 D + 1 的值存储到 M 和 D 寄存器中
MD = D + 1
</code>
接下来按如下的顺序进行翻译：
  - C 指令中 ''15-13'' 这三位永远都是 ''111''，可以将其先填入
  - 对 ''comp'' 这部分 ''12..6''（''a'' 和 ''comp''）进行翻译。这部分通过对照 C 指令的 table 来获取二进制代码。比如例子中的计算部分 ''D+1''，对应的 ''a'' 是 ''0''，对应的六位 ''comp'' 是 ''011111''，那么这一部分对应的代码就是 ''0011111''
  - 对 ''dest'' 这部分 ''5..3'' 进行翻译。这部分的翻译也是通过查表：比如例子中的 ''MD''，对应的是 ''011''
  - 对 ''jump'' 这部分 ''2..0'' 进行翻译，同样也是通过查表：本例中没有跳转部分（null），对应的 bits 是 ''000''
  - 最后得到的翻译结果是 ''111 0011111 011 000''

====Symbols Handling====
之前介绍过，根据 symbol 的内容，可以将 symbol 划分为三种类型：
  * //varible symbol//：代表着用于数据操作的**内存位置**，该地址映射由汇编器管理
  * //label symbol//：代表着 ''goto'' 跳转的**指令位置**
  * //pre-defined symbols//：代表着系统占用的特殊内存位置
===pre-defined symbols===
由于这些 symbol 只会在 A 指令中出现，因此只需要根据对照表，将 symbol 转化为对应的地址值即可：比如 
<code nand2tetris-hdl>
// R1 corresponds address 1
@R1->@1
</code>
===Label symbols===
label 类型的 symbol 主要用于：
  * 标记 goto 命令的终点，比如 ''@loop''。这类 symbol 会被直接替换成其值（与 pre-defined symbol 类似），比如下面例子中的 ''LOOP'' 会被替换为 ''16''
  * 对应的伪代码声明，比如 ''(loop)''：这类 label 通常不会进行翻译，但汇编器遇到这类 label 时，会将其对应的 symbol 与其起始行关联起来。比如：
<code nand2tetris-hdl>
@i // line 0
M=1
@sum
M=0

(LOOP) // not a instruction line
    @i // line 4
    ...
    @LOOP //line 16
</code>
这里的 ''(LOOP)'' 标签，对应的 block 起始行为 ''4''；这个关系将会使用一张表来维护：
^Symbol^value^
|LOOP|4|
===Variable symbols===
变量类型的 symbol 指非提前定义的，且没有使用 driective 在别处进行定义的（比如 ''LOOP''）的 symbol。上面例子中的 ''@i''，''@sum'' 都是变量类型的 symbol。之前提到过，这类 symbol 都会被存储在一个独特地址的内存单元中（地址从 ''16'' 开始）。因此这类 symbol 对应的值，是他们所在内存单元的地址：
^Symbol^value^
|i|16|
|sum|17|
由于变量可能会被多次用到，当第一次用到时，该变量 symbol 和其对应地址会被加入到映射表中；之后再使用时，汇编器会从映射表中查找到该对应关系，并把 symbol 翻译为对应的地址。
===Symbol table===
可以看到的是，上述的所有翻译都依赖于一种数据结构：//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 中的对应映射关系

===Assembly process===
<code cpp>
// 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
</code>