从0到1构建计算机(6/10)--汇编语言与汇编器

前一篇我们完成了Hack平台的硬件部分，本篇开始我们进入到软件的部分。相比较而言，软件部分更加复杂，需要花更多时间来实现和调试。软件部分的第一层就是汇编语言和汇编器，本篇我们将定义Hack的汇编语言，并编写对应的汇编器

汇编语言和汇编器

汇编语言是机器语言的符号表示，相比于机器语言，汇编语言更接近于自然语言，便于我们阅读和记忆。汇编语言和机器语言在表述上的一致性是非常高的，绝大多数情况下两种指令是一一对应的，例如：1000100111011000对应mov ax,bx，把机器指令拆成3段，其中前8位代表mov，中间4位代表寄存器ax，最后四位代表寄存器bx。此外，我们还可以在汇编语言中用引用一些符号，用于代表某些数值（例如内存地址，指令地址等），这可以把我们从处理这些繁琐的数值的工作中解放出来（例如我们用符号i来代表一块内存地址，然后不用去记忆地址具体的值是多少，分配在什么位置，是否和其他地址冲突等），提高代码的编写效率。

汇编器负责把汇编语言翻译成机器语言。因为汇编语言和机器语言的高度一致性，所以实现汇编器是比较简单的。唯一的难点可能就在于上面所提到的如何把一些符号和它们所对应的数值联系起来，即符号解析(symbol resolution)的过程。

Hack的汇编语言设计

想要设计一门汇编语言，那么必须要参考它的机器语言。Hack的机器指令集过于简单，只有A、C两种命令，所以相应的它的汇编语言也很简单????。

A指令

我们copy一些上一篇文章的内容：A指令，即Address指令。它的功能很简单，就是把一个数值传送到CPU中的A寄存器即可，多数情况下这个数字后续会当做地址使用，用于定位内存中的存储单元。

我们定义A指令的汇编指令格式是：@value。

**1.**value可以是一个立即数。这种格式是两种语言的天然映射。

@3  //把数字3传送到A寄存器
@5  //把数字5传送到A寄存器

**2.**value也可以是一个符号（变量名）

我们支持把符号当做数值代入，这更像我们在高级语言中编码的方式。例如@number，它的含义是：把变量number的首地址传送到A寄存器，number的首地址可能是1000或者2000，我们并不去关心它。如果不支持@+符号这种命令，我们该怎么编写Hack的A汇编指令呢？我们可能需要先梳理出该程序需要几个变量，例如i，j，k，然后画一个表格，安排一下i，j，k的地址，并保证他们不互相冲突，然后用@+立即数的方式编写，每次遇到需要传入变量地址的时候，去检查下表格，填入变量对应的数值。在复杂的程序中，这可能是相当繁琐且容器出错的，所以把他交给汇编器去做是一个明智的选择。

@number  //把变量number对应的数值（变量地址）传送到A寄存器
@END     //把标签END对应的数值（指令地址）传送到A寄存器

到目前为止，这好像是我们第一次使用某种技巧（借助一些数据结构和算法），来把一个问题解决地更快更好，这可能就是编程中最有意思也最有挑战的地方吧。

C指令

C指令较为复杂，分成4部分。

• 第一位是标志位：为1时就代表该指令是C指令
• 3-10位是comp位：：这几位的排列用于表示执行不同的元素&逻辑运算
• 11——13位是dest位：指示需要把计算出的数据传送到哪里（寄存器或内存）
• 14-16位是jump位：指示CPU执行跳转指令的条件
  

我们定义C指令的汇编指令格式是：dest=comp ; jump。其中"dest="，或"; jump"可以被省略，所以还可以演化出另外两种更常用的指令：“dest=comp"和"comp ; jump”。

**1.**计算后赋值指令：dest=comp

下图我们可以看到dest，comp，jump各自的操作和code的对应方式。例如comp中0000010对代表算D+A的和，然后从out输出；dest中010代表把comp计算的赋给寄存器D；那么D=D+A，这句汇编指令就代表：进行D+A的计算操作，然后把结果传送到寄存器D。D=D+A对应的机器指令是：111(0000010)(010)(000)（后三位000代表跳转指令为null，即不跳转）

**2.**计算后跳转指令：comp ; jump

jump中001代表判断comp输出的值，如果>0，则进行指令跳转操作。那么D ; JGT，这句汇编指令就代表：进行D的计算操作（即简单的把D输出），然后判断如果值>0，则进行指令跳转操作。D ; JGT对应的机器指令是：111(0001100)(000)(001)。（倒数后三位000代表赋值指令为null，即不需赋值）

需要注意的是：无论是要进行指令跳转操作，还是对内存的数据进行读或写，都需要先调用A指令，把目标地址写入A寄存器

符号与符号表

Hack汇编语言中涉及3中符号：预定义符号、标签符号、变量符号

**1.**预定义符号：预定义符号绑定了内存中的一些地址值，在编写汇编语言时起到辅助作用。例如SP, lCL, ARG等用于辅助函数调用栈的实现；R0-R15可以被当做扩展的寄存器使用；SCREEN, KBD代表屏幕和键盘的内存区域首地址。

**2.**标签符号：标签符号绑定了指令的地址值，用于跳转指令。用（大写字母符号）声明，独占一行。

**3.**变量符号：变量符号绑定了变量的地址值。每遇到新的变量，则连续地在内存空间为其分配地址（变量地址从内存中16地址开始）。

符号表是一个字典结构，key是符号本身，value可以是和该符号相关的若干信息，在这里符号表的value就是符号代表的内存地址的值。在使用符号表的时候，往往需要先构建符号表（符号表可能会被动态地修改），然后在处理程序数据的时候，通过查找符号表来获取符号相关的信息。符号表是一个重要的数据结构，在汇编器、编译器、链接器中都扮演了重要的角色。

举例

这里我们举一个例子，把一个C语言风格的代码，转化为Hack上的汇编语言实现。

实现

实现Hack的汇编器相对比较简单，主要方法是逐行的分析汇编指令，判断指令类型和组成成分，然后生成对应的机器指令。唯一的难点在于对符号的处理，而实现的技巧在于对符号表的运用。

汇编器实现：（完整实现放在:github）

class SymbolTable
    # void add_entry(entry)      新增一个符号
    # bool contains(symbol)      是否包含符号
    # string get_address(symbol) 获取符号的值
    # ......
end

class Parser
    # bool hasMoreCommand        是否还有下一条指令
    # void advance               指令游标前进
    # string commandType         当前指令的类型
    # string symbol              当前指令的符号
    # string dest                当前指令dest部分的符号
    # string comp                当前指令comp部分的符号
    # string jump                当前指令jump部分的符号
    # ......
end

class Code
    # string dest(mnemonic)      根据符号获取dest的机器码
    # string comp(mnemonic)      根据符号获取comp的机器码
    # string jump(mnemonic)      根据符号获取jump的机器码
    # ......
end

# main
file_name = ARGV[0]
hack_name = file_name.split(".")[0] + ".hack"

parser=Parser.new(File.read(file_name))
code = Code.new()
symbol_table = SymbolTable.new();
$command_line = 0

#第一次遍历源文件，构建符号表（初始化所有标签符号的值，因为标签符号可以先使用后声明，所以需要先遍历一遍；变量符号可以边生成机器代码时边初始化，因为变量符号是先声明后使用）
puts "generate symbol table:" 
while parser.hasMoreCommand()
    parser.advance()
    command_type = parser.commandType()
    command_symbol = parser.symbol()
    if command_type == "L_COMMAND"
        if !symbol_table.contains(command_symbol)
            symbol_table.add_entry({command_symbol=>completeBinary(($command_line).to_s(2))})
        end
    else
        $command_line += 1
    end
end

puts "generate code:"
#第二次遍历源文件，把汇编代码汇编成机器代码
parser.reset()
$variabel_address = 16 #变量从地址16开始连续分配
hack_file = File.new(hack_name, "w")

while parser.hasMoreCommand()
    new_command = ""
    parser.advance()
    command_type = parser.commandType()
    command_symbol = parser.symbol()

    if command_type == "A_COMMAND"
        new_command << "0"
        address_value = ""
        if is_number(command_symbol)
            address_value = completeBinary(command_symbol.to_i.to_s(2))
        elsif symbol_table.contains(command_symbol) #如果符号表已经包含符号，则直接取出符号的值
            address_value = symbol_table.get_address(command_symbol)
        else
            address_value = completeBinary($variabel_address.to_s(2)) #如果符号表不包含符号，则把符号加入到符号表，并把下一个变量地址+1
            symbol_table.add_entry({command_symbol=>address_value})
            $variabel_address += 1
        end
        new_command << address_value
    elsif command_type == "C_COMMAND"
        new_command << "111"
        dest_value = code.dest(parser.dest())
        comp_value = code.comp(parser.comp())
        jump_value = code.jump(parser.jump())
        new_command << comp_value
        new_command << dest_value
        new_command << jump_value
    elsif command_type == "L_COMMAND"
        next
    else
        new_command << "unknow command type"
    end

    new_command << "\n"
    hack_file.write(new_command)
end

def completeBinary(binary_string)
    while binary_string.length < 15
        binary_string.insert(0,"0")
    end
    return binary_string
end

def is_number(string)
  return string !~ /\D/ 
end

我们用不到200行的代码就实现了一个汇编器，是不是很简单？

总结

汇编语言是人操作计算机工作最直接的方式，它描述了计算机最终执行的指令序列。学习汇编语言能让我们充分获得底层编程的体验，理解计算机运行的机理，这能让我在学习理解上层知识的时候更加准确。Hack的汇编指令只具备了最必要的功能，和我们常用的动辄几百条的汇编指令集有很大差距，但这并不妨碍Hack成为一个完整的计算机。下一篇我们会基于Hack的汇编指令扩展出一个虚拟机，这个虚拟机的指令集更接近我们常用的CPU的指令集。

推荐王爽的《汇编语言》，这本书不仅能高效地指导大家学习汇编语言，同时也是一本用于指导如何学习的书，字里行间蕴含了王爽老师自己对如何学习，如何教学的理解。相比较于很多苍白的翻译书籍，这本本土书籍更加优秀。