汇编语言诞生于机器语言之后,高级语言之前,作为一个过渡性产品它的存在是如此尴尬,以至于今天有的编译器在从源代码生成机器代码的过程中不需要生成它。

和机器语言相比,汇编语言最大的好处是程序员可以写一些符号来代替存储器地址,从而避免了手工计算偏移地址的麻烦。其次是程序员再也用不着记某条指令的操作码,除此之外汇编语言和机器代码并无本质的区别。换句话说,汇编语言仅仅是一种“更可读的”机器语言,但它的某些“设计”使得汇编器实现起来并不简单(至少没有看上去那么简单)。

实现一个汇编器

最直接的想法是把汇编看成某种语言,然后为它写个编译器。我们可以用 lex 和 yacc 这样的自动化工具,但还是不得不写冗长的 lexer 和 BNF 文件。况且 BNF 适合描述 Algol 系的编程语言:Pascal、C/C++、Java、Perl 或 Python,这些语言的特点是嵌套结构,而汇编语言的结构简单得多。

第二种方法是用正则表达式。/\s*(\w{2,3})\s+((\w+)(,\w+)?)?/这个正则表达式就能匹配 2 个操作数(Op A, B)和 3 个操作数(Op A, B, C)的情况,然后根据匹配出来的模式提取操作数和操作码以便生成二进制代码,或进行错误处理。

regex

这种模式的语法分析器方法叫 “ad hoc”(专设)parser,比用 BNF 简单,但是还是要进行一系列判断(比如匹配出操作数后我们需要继续判断操作数是寄存器,还是立即数,或是一个 label,然后进行相应的动作)。

但是既然二进制代码之间是一对一的关系,汇编语言不过是指令的一些助记符而已,实现一个汇编器有必要那么复杂吗?更准确的问题是:为汇编器编写 parser 是必须的吗?

在回答这个问题之前我们先来看一块别人山上的石头。

RTL

GCC 在设计中间语言时使用了一种非常接近汇编但是比汇编更优雅的语言作为中间形式,这种语言就是 RTL(Register Tranfer Language)。

RTL 的语法十分像 Lisp,据说作者在发明 RTL 的时候受到了 Lisp 的启发。例如下面这段稍作简化的代码的作用是把 1 号寄存器的内容加上 2 号寄存器的内容,然后保存到 3 号寄存器中。

 (set (reg 3)
   (plus (reg 1)
     (reg 2)))

首先,这种中间语言是与目标机器无关。GCC 的前端从源代码生成 RTL,后端根据目标机器信息(如字节序、字长等)可以用 RTL 直接生成目标代码。当然 RTL 是中间语言,这一点上它和机器相关的汇编语言没有可比性。

但是和汇编语言相比,它有一个很大的好处,那就是为这种语言实现 parser 是一件轻而易举的事情,因为实现一个 Lisp 语言解释器本身就很简单。前提是程序员需要这样写汇编:

(label hello
  (add $s1, $2, $3)
  (lw, $s0, $sp, 4)
)

add 函数调用的语义变成了“生成 add 语句的二进制代码”。我们甚至可以借助其他高级语言写一个 AsmFile.exe:

function addi(rd, rs, rt) {
    // 生成 addi 的目标代码
}

addi(s0, s1, s2);    
...

“汇编”不再是一种文本文件,而是一个可执行文件,运行它我们可以得到目标文件。我们还可以用脚本语言来实现,结果也是一样的。

符号表

下面简单讨论一下 AsmFile.exe 是怎么生成符号表的,这里要用到一个叫 inst_loc 的全局变量,它表示当前指令在存储器中的位置:

inst_loc = 0;

add(...);       // inst_loc = 1
sub(...);       // inst_loc = 2
label("hello");  // inst_loc = 2, symbal_table["hello"] = 2 
add(...);       // inst_loc = 3
jump("hello");

AsmFile.exe 每次调用 add、sub、jump 这样的函数时都会将inst_loc 的值加 1,表示有一条新指令将载入存储器。而调用 label("hello") 的结果是在符号表中加入 hello,它对应的地址是 2,即第二条 add 的位置。当程序执行到 jump 时,程序就会去符号表中找 hello 的地址。

另一种情况是标号在跳转语句以后出现,这时执行 jump 语句就发现符号表中没有 hello ,于是就生成含有占位地址的指令,以后让连接器或加载器来负责定位。

jump("hello");   
add(...);       
label("hello");
sub(...);       
add(...);       

数据定义

由于我们采用了一种易于识别的语法,因此不需要再在汇编文件中区分代码段和数据段,完全可以这样写:

add(...);
data("foo", word, 3);
load(r1, "foo");
data("bar", word, 4);
load(r2, "bar" );

伪指令

汇编语言中有一种叫伪指令(pseudo instruction)的东西,它用来扩展现有机器的指令集。比如某些机器(如 MIPS)本身并不提供 move (寄存器移动)指令,当程序员需要实现寄存器拷贝的功能时往往需要用一条 add 指令来代替:

add $t0, $zero, $t1 

这样带来的坏处显而易见,原来的“赋值”语义现在变成了“加”,程序员不但在编程时需要多绕一个弯,写出的代码也存在二义性。于是,为了让程序员在写汇编程序时更加直观,同时又不增加指令集的复杂度(因为指令集复杂度会直接影响到电路设计的复杂度),这些机器的汇编器就会提供“伪指令”,与其说是伪指令,不如说是给汇编器加了一道后门。

现在我们可以用函数调用来实现伪指令,如 move:

function move(rdest, rsrc) {
    add(rdest, zero, rsrc);
}

是不是很简单?当我们调用 move() 时,“编译器”就会在背后调用 add() 生成有效的二进制代码。

我们可以用下面这个函数来实现”压栈“:

function push(r3) {
    addi(sp, sp, -4); // 栈顶增长
    sw(r3, sp, 0);    // 寄存器的内容入栈
}


Published

21 March 2013