4.2 程序的启动
相信各位同学已经编写了不少高级语言的程序，我们可以理解自己编写代码的含义，但是计算机是如何理解并准确无误地执行我们的代码的。这一过程并不是一个启动按钮，或是一行指令。
实际上，程序的启动是一个相当复杂的过程，对于C语言而言，涉及了四个相对独立的功能模块，分别是：编译器（Compiler），汇编器（Assembler），链接器（Linker），加载器（Loader）。他们按照一定的次序工作，上一层的输出产物成为下一层的输入，逐步将程序转换成与实际计算机系统硬件相关的，计算机可以理解执行的程序（C.A.L.L.过程）。如下图所示：
- 为了确定文件类型UNIX使用文件的后缀，
x.c表示C源文件，x.s表示汇编文件，x.o表示目标文件，x.a表示静态链接库，x.so表示动态链接库。默认情况下，a.out表示可执行文件。 - MS-DOS使用
.C, .ASM, .OBJ, .LIB, .DLL, .EXE来完成相同功能。
4.2.1 代码编译
编译器将C程序转换成一种机器可以理解的符号形式的汇编语言程序，它能够被进一步翻译成二进制机器语言。
4.2.2 代码汇编
由编译器生成的汇编程序中，存在着简化程序转换和编程的一些实际硬件不支持的指令，这类指令称为伪指令(pseudoinsruction)。
例如，MIPS硬件确保寄存器$zero保持0。即一旦使用该寄存器，它都能提供0，而且程序员不能修改寄存器$zero的值。寄存器$zero用于生成汇编语言指令move。move的功能是将一个寄存器中的内容复制到另一个中。因此即使MIPS体系结构不存在这条指令，MIPS汇编器依然可以识别它。
move $t0, $t1 # 寄存器$t0得到寄存器$t1的值
汇编器将这条汇编语言指令转换成等价的机器语言指令：
add $t0, $zero, $t1
总的来说，伪指令使得MIPS拥有比硬件所实现的更为丰富的汇编语言指令集。唯一的代价是保留了$at寄存器。本次实验中也存在着将伪指令扩展成通用指令的任务。
汇编器的主要任务是汇编成机器代码。汇编器将汇编语言程序转换成目标文件(object file)，它包括机器语言指令，数据和指令正确放入内存所需要的信息。
为了产生汇编语言程序每条指令对应的二进制表示，汇编器必须处理所有标号对应的地址，汇编器将分支和数据传输指令中用到的标号都放入一个**符号表(Symbol Table)**中。这个表由标号和地址组成。
UNIX系统中的目标文件通常包括以下6个不同部分：
- 目标文件头，描述目标文件其他部分的大小和位置
- 代码段，包含机器语言代码
- 静态数据段，包含在程序生命周期内分配的数据
- 重定位信息，标记了一些在程序加载进内存时依赖于绝对地址的指令和数据
- 符号表，包含未定义的剩余标记，如外部引用
- 调试信息，包括了一份说明目标模块如何编译的简明描述
4.2.3 代码链接
到目前为止我们描述的所有内容表明，对源程序的任意一行代码的修改都需要重新编译和汇编整个程序，全部的编译和汇编效率是低下的，尤其对于标准库而言。因而出现了另一种方法，即单独编译和汇编每个过程，使得某一行代码的修改只需要编译和汇编一个过程，这种方法需要一个新的系统程序，称为链接器(Linker)。它把所有独立汇编的机器语言程序拼接在一起。
链接器的工作分为三个步骤：
- 将代码和数据模块象征性地放入内存
- 决定数据和指令标签的地址
- 修补内部和外部引用
链接器使用每个目标模块中的重定位信息和符号表，来解析所有未定义标签，这种引用发生在分支指令，跳转指令和数据寻址处。它的工作非常像一个编辑器，寻找所有旧地址并用新地址加以代替。 如果所有外部引用都解析完成，链接器接着要确定每个模块将要占用的内存位置。因为文件是单独汇编的，所以汇编器不可能知道该模块指令和数据相对于其他模块而言的位置，因此也就无从确定他们的内存位置。当链接器将一个模块放到内存中的时候，所有的绝对引用（与寄存器无关的内存地址），必须重定位来反映它们的真实地址。 链接器将产生一个可执行文件(Executable file)，它可以在一台计算机上运行，通常，这个文件与目标文件具有相同的格式，但是它不包含未解决的引用。
4.2.4 代码加载
现在可执行文件已经存在于磁盘中，操作系统就可以将其读入内存并启动执行该程序，在UNIX系统中，**加载器(Loader)**按照以下步骤工作：
- 读取可执行文件头来确定代码段和数据段的大小
- 为正文和数据创建一个足够大的地址空间
- 将可执行文件中的指令和数据复制到内存中
- 把主程序的参数复制到栈顶
- 初始化机器寄存器，将栈指针指向第一个空位置
- 跳转到启动例程，它将参数复制到参数寄存器并且调用程序的main函数，当main函数返回时，启动例程通过系统调用exit终止程序
接下来，就让我们一起构造我们自己的汇编器和链接器！
4.3 汇编器
4.3.1 汇编器原理详解
正如上文所述，汇编器将汇编语言文件翻译成二进制机器指令和二进制数据组成的文件，我们将在下文阐述MIPS汇编器的实现细节。 首先我们先来看看汇编器在处理过程中可能面临的一些情况：
- 简单情况：
- 计算和逻辑指令，例如
等；addu rd, rs, rt mult rs, rt lw rt, offset(rs)- 为将其汇编成二进制指令所需要的所有信息都已经包含在了指令中。
- 分支指令(Branch)：
- 分支指令中的
imm字段代表的是相对当前指令地址的偏移量，即需要的是相对地址； - 一旦将所有的伪指令解析成实际的机器代码以后，由于MIPS是定长指令，因此通过简单的计算我们便可以得到实际的地址偏移量。
- 分支指令中的
- 前向引用：汇编语言允许标签在定义之前就被使用，如下图所示：
beq $zero, $zero, Label
Label:
汇编器在看到指令beq时，它不知道标签Label在哪里，因此也就无从得知相对地址偏移量了。
为解决这个问题，我们首先引入一个概念——遍(Pass)。它指的是对源程序（包括源程序的中间形式）从头到尾扫描一次，并做有关的加工处理，生成新的源程序中间形式或目标程序，通常称为遍。
汇编器通常采用两遍的方式来处理可能出现的前向引用：
第一遍，汇编器将汇编文件的每一行读入，如果一行以标签作为开始，汇编器在他的符号表中记录标签的名字以及在文件中的位置。
第二遍，汇编器使用整个文件的符号表中的信息，在这一遍产生机器代码，若依然有未决的引用，将由链接器来进行解析：
跳转指令：例如
j, jal指令，这类跳转指令需要跳转的绝对地址，汇编器对于单一文件的操作，不可能得到最终的绝对地址。数据引用：例如
la指令，la指令将由汇编器处理为lui和ori指令，同样需要32位的绝对地址。外部引用：
jal指令可能跳转到外部文件的函数（就如C语言引用库函数），汇编器处理单一文件无法获取外部引用。
可以看到，我们对于需要绝对地址的指令以及外部引用都是无法解析的，因此汇编器将创建两张表。
符号定义表(Symbol Table)：每个文件都有一个符号定义表，用来记录该文件中定义的标签，这些标签可能被其他文件引用：
- 文本段标签： 1. 跳转标签，如循环时定义的 For/Loop/End 等标签； 2. 函数定义，如 main/add 等自行定义的函数；
- 数据段标签：出现在文件
.data段的数据标签。
重定位表(Relocation Table)：该文件中暂时无法确定的，需要在之后的过程中得到地址的标签：
j, jal等指令的跳转标签，一般都是在文本段中定义的，无论是文件内定义的还是文件以外定义的；- 任何可能的数据标签，例如所有被
la指令引用的数据标签。
4.3.2 汇编器具体实现
汇编器实现概述
本次实验，我们的汇编器将实现一个MIPS指令的子集。同时我们的汇编器是一个如上文描述的**“两遍”**汇编器，实现汇编.data和.text段。它将按照以下流程工作：
第一遍：读取输入的.s文件
举例如下：
.data
num: .space 8
num2: .space 16
.text
add:
lw $s5, -4($sp)
lw $s6, -8($sp)
addu $t0, $s5, $s6
move $v0, $t0
jr $ra
main:
la $v1, num
li $s1, 10
li $s2, 20
sw $ra, 0($a3)
sw $s1, -4($a3)
sw $s2, -8($a3)
move $sp, $a3
jal add
lw $ra, 0($sp)
move $t0, $v0
beq $t0, $0, end
j end
end:
- 剔除文件注释（在.s文件中，注释为#开头的单行注释）；
- 扩展伪指令，如
li,la等； - 记录文件符号，构建相应的符号定义表；
- 注意：在我们的处理中，为了区分符号是来自
.data段还是来自.text段，我们为来自.data段中的符号，在符号名最开始追加一个%用于在符号定义表中区分。
- 注意：在我们的处理中，为了区分符号是来自
- 标签（是否重复定义）和伪指令（是否合法）将被检查确认；
- 输出：中间文件（.int），对于
.data段，只需要输出.data段所占据的字节数即可，按照如下格式：
.data
24
.text
lw $s5 -4 $sp
lw $s6 -8 $sp
addu $t0 $s5 $s6
addu $v0 $0 $t0
jr $ra
lui $at num@Hi
ori $v1 $at num@Lo
addiu $s1 $0 10
addiu $s2 $0 20
sw $ra 0 $a3
sw $s1 -4 $a3
sw $s2 -8 $a3
addu $sp $0 $a3
jal add
lw $ra 0 $sp
addu $t0 $0 $v0
beq $t0 $0 end
j end
第二遍：读取.int中间文件