我们将尝试构建一个C语言的解释器，这个项目也是我C语言的大作业。现在回顾看来，当时对整个项目都是知其然不知其所以然，从现在的眼光来看，当时很多做法都是很稚嫩的。尤其是对于这个项目结构的理解也远远不足，所以打算重构一遍。
构建流程
首先是整个编译器的构建流程，一般来讲，编译器的编写有三个步骤：
- 词法分析器，用于将文本文件转换为内部的表示结构
- 语法分析器，在词法分析得到的标记的基础之上，构建一棵语法树
- 目标代码的生成，将语法树转换成目标代码
但是由于这里我们编写的是一个解释器，所以我们自定义自己的虚拟机框架和指令。我们通过语法分析词法分析之后得到的语法树，来生成使用自定义虚拟机框架的指令的目标代码。
编译器的框架
仿照c4编译器的写法：
这里我们的解释器主要包括4个函数：
next()用于词法分析，获取下一个标记program()用于语法分析，分析整个C语言的程序expression(level)用于解析一个表达式eval()虚拟机的入口，用于执行目标代码
可能在此基础之上我会做出一点自己的改动，但是总体框架还是确定的，首先是实现对要解释的文件的处理：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 源文件全局变量
int line; // 当前行数
char *src; // 源文件内容
char *old_src; // 源文件备份
int main(int argc, char *argv[]) {
int i, fd;
argc--;
argv++;
int poolsize = 256*1024; // 内存池大小
line = 1;
// 读取源文件
{
if((fd = open(*argv,0)) < 0){
printf("Could not open %s\n", *argv);
exit(1);
}
if(!(src = old_src = malloc(poolsize))){
printf("Could not malloc %d bytes\n", poolsize);
exit(1);
}
if((i=read(fd, src, poolsize-1)) <= 0){
printf("Could not read %s\n", *argv);
exit(1);
}
src[i] = 0; // 文件结束符
close(fd);
}
program();
return eval();
}
我们将读取到的文件内容复制到src内存空间中。
现在我们就需要开始模拟一台计算机应有的功能了，我们的指令需要运行在我们的虚拟机上。那么首先，我们就需要定义一个自己的虚拟机，一台机器必须要有以下几个部分：
- 内存： 这是用来存放数据的主要空间，我们的代码段数据 还有函数调用时的栈段都存放在这里
- 寄存器：我们需要寄存器帮助我们实现各种命令，同时也需要程序计数器指向我们的指令
- CPU：本来这一部分应该是一大堆电路，但是这里我们可以通过操作指针和寄存器的方式，用一系列程序，简单的模拟它
计算机内部实现
内存
首先是内存部分，一般情况下，内存会被分成几个段。由于我们是简单实现的理想模型，我们只需要设置几个最基本的部分就可以了：
- 代码段： 我们分析得到的指令就被存放在这里
- 数据段： 这里用来存放我们源程序中用的数据，通常和token信息绑定
- 栈段： 我们处理函数调用将会用到它，存放栈帧和局部变量等数据
现在我们就可以简单的对我们的模拟的计算机内存进行初始化：
......
// 内存布局
int *text; // 代码段
int *old_text; // 代码段备份
int *stack; // 栈
char *data; // 数据段
int main(int argc, char *argv[]) {
......
// 内存初始化
{
if(!(text = old_text = malloc(poolsize))){
printf("Could not malloc %d bytes for text\n", poolsize);
exit(1);
}
if(!(stack = malloc(poolsize))){
printf("Could not malloc %d bytes for stack\n", poolsize);
exit(1);
}
if(!(data = malloc(poolsize))){
printf("Could not malloc %d bytes for data\n", poolsize);
exit(1);
}
memset(text, 0, poolsize);
memset(stack, 0, poolsize);
memset(data, 0, poolsize);
}
program();
return eval();
}
寄存器
寄存器用来存放计算机的运行状态，我们的虚拟机中只简单的使用四个寄存器，分别是：
PC程序计数器，用于存放一个内存地址，该地址中用于存放下一条要执行的指令SP寄存器，永远指向当前的栈顶（注意这里的栈是从高地址向低地址增长的）BP基址寄存器，用于指向栈底，当我们在函数调用解析参数时需要用到它AX通用寄存器，用来存放一条指令执行后的结果
我们对他们进行简单的初始化：
......
// 寄存器
int *pc; // 程序计数器
int *bp; // 基址指针
int *sp; // 栈指针
int ax; // 通用寄存器
int cycle; // 时钟周期
int main(int argc, char *argv[]) {
......
// 寄存器初始化
{
bp = sp = (int*)((char*)stack + poolsize);
ax = 0;
cycle = 0;
}
program();
return eval();
}
指令
现在我们的虚拟机已经有了基本的骨架，我们可以开始尝试实现我们我们虚拟机最基本的指令集。不过首先我们需要明确我们需要用到哪些指令。这里我们直接照搬C4的指令集就行了：
enum {
LEA, IMM, JMP, CALL, JZ, JNZ, ENT, ADJ, LEV,
LI, LC, SI, SC, PUSH,
OR, XOR, AND, EQ, NE, LT, GT, LE, GE,
SHL, SHR, ADD, SUB, MUL, DIV, MOD,
OPEN, READ, CLOS, PRTF, MALC, MSET, MCMP, EXIT
};
这些指令顺序是有意的，带有参数的指令在前，没有参数指令的放在后面，为了方便我们之后打印调试信息。
MOV
MOV dest,srcx86中最基础重要的一个公式，它将SOURCE中的内容放在DEST中。但在我们的虚拟机中只提供了一个通用寄存器AX，加上由于对参数类型的识别是一件复杂的事情，所以我们将MOV拆分成五个子操作来实现：
IMM <num>将num放入寄存器ax中LC将对应地址中的字符载入ax中，要求ax中存放地址LI将对应地址中的整数载入ax中，要求ax中存放地址SC将ax中的数据作为字符存放入地址中，要求栈顶存放地址SI将ax中的数据作为整数存放入地址中，要求栈顶存放地址
这样的拆分，极大程度上的减小了指令实现的复杂度，现在我们可以开始具体的实现了：
int eval() {
int op, *tmp;
while(1){
if(op == IMM) {ax = *pc++;}
else if(op == LC) {ax = *(char*)ax;}
else if(op == LI) {ax = *(int*)ax;}
else if(op == SC) { *(char*)*sp++ = ax;}
else if(op == SI) { *(int*)*sp++ = ax;}
}
return 0;
}
这里得*sp++实际上就是一个退栈操作，将值存储到弹出得地址中。
这里我之前一直没有搞懂，为什么LI/LC要将对应地址中的字符载入ax中，因为我们的默认的计算结果是存储在ax中的，也就是我们指令计算出的地址，可以直接被LI/LC所使用，这样就很高效。
PUSH
PUSH的作用很简单，就是将值或者寄存器压入到栈中。在这里我们PUSH的作用给就是将ax的值压入栈中，因为我们只有这一个寄存器：
else if(op == PUSH) {*--sp = ax;}
JMP
JMP <addr>是跳转指令，无条件的将当前的PC寄存器设置为指定的<addr>，实现如下：
else if(op == JMP) {pc = (int*)*pc;}
pc始终指向的是下一条指令，所以此时它存放的存放的是JMP指定的参数，即<addr>的值
JZ/JNZ
为了实现if语句 我们也需要条件判断相关的指令。这里我们只需要实现两个最简单的条件判断，即ax==0/ax!=0的情况下的跳转：
else if(op == JZ) {pc = ax ? pc+1 : (int*)*pc;}
else if(op == JNZ) {pc = ax ? (int*)*pc : pc+1;}
子函数调用
这个是比较重要的一部分，我很大程度上也是为了这一部分重新回头别写这个编译器。这里我们将根据子函数调用约定，用几个最简单的指令来实现这个过程，我们要引入的指令有CALL ENT ADJ LEV。
首先我们介绍CALL，它用于跳转到一个子函数的开始地址。程序将会跳转到地址<addr>，并将当前的位置信息保存起来，以用于函数调用后的返回。这里我们将返回的PC存放在栈中：
else if(op == CALL) {*--sp = (int)(pc+1); pc = (int*)*pc;}
现在我们能进入调用函数了，那么我们便需要进一步的规范我们的函数调用规则。在实际的函数调用中，我们不仅要考虑函数的地址，也要考虑如何传递参数和返回结果，这里我们将每次的返回结果保存在ax中，对于参数传递，我们需要遵循C语言的调用标准：
- 由调用者将参数入栈
- 调用结束时，由调用者将参数出栈
- 参数逆序入栈（因为先进后出）
我们可以看下面的这个例子：
int callee(int, int, int);
int caller(void){
int i, ret;
ret = callee(1, 2, 3);
ret += 5;
return ret;
}
会生成下面的汇编代码：
caller:
; make new call frame
push ebp
mov ebp, esp
sub 1, esp ; save stack for variable: i
; push call arguments
push 3
push 2
push 1
; call subroutine 'callee'
call callee
; remove arguments from frame
add esp, 12
; use subroutine result
add eax, 5
; restore old call frame
mov esp, ebp
pop ebp
; return
ret
但是我们的虚拟机难以解决其中的几个问题：
push ebp我们的PUSH无法指定寄存器mov ebp,esp我们的MOV也无法直接指定源和目的add esp,12我们的ADD也无法直接实现两个操作数的加法
所以我们需要额外的指令来代替这几个的功能，所以我们需要定义以下几个指令：
ENT
ENT <size>指的是enter我们用它实现make new call frame的操作，即保存当前的栈指针，并在栈上保留一定的空间，用来存放局部变量，汇编代码的表现形式如下：
; make new call frame
push ebp
mov ebp, esp
sub size, esp ; save stack for variable
我们可以通过以下形式实现它：
else if(op == ENT) {*--sp = (int)bp; bp = sp; sp = sp - *pc++;}
ADJ
ADJ <size>用于实现remove argument from frame。用于将调用子函数时压入栈中的数据清楚，之所以单独定义这个指令，是对我们ADD功能局限做出的妥协。其汇编实现如下：
; remove arguments from frame
add esp, size
我们可以通过以下形式实现它：
else if(op == ADJ) {sp = sp + *pc++;} // add esp <size>
LEV
本质上这个指令并不是必需的而且我们的指令集中并没有POP的指令，所以为了简洁的进行函数的退出操作，我们专门定义了LEV的封装。对应的汇编操作如下：
; restore old call frame
mov esp, ebp
pop ebp
; return
ret
我们用以下形式实现：
else if(op == LEV) {sp = bp; bp = (int*)sp++; pc = (int*)*sp++;}
LEA
上述的指令解决了调用帧的问题，解决了我们函数的运行和返回的问题。现在，为了进一步的执行调用函数，我们需要想办法获取先前压入的参数。在此之前，我们首先需要了解当参数调用时，栈中的调用帧是什么样的：
sub_function(arg1, arg2, arg3);
| .... | high address
+---------------+
| arg: 1 | new_bp + 4
+---------------+
| arg: 2 | new_bp + 3
+---------------+
| arg: 3 | new_bp + 2
+---------------+
|return address | new_bp + 1
+---------------+
| old BP | <- new BP
+---------------+
| local var 1 | new_bp - 1
+---------------+
| local var 2 | new_bp - 2
+---------------+
| .... | low address
我们首先将参数压入栈中，然后进行调用，调用会将返回地址压入栈中，然后保存当前的栈基址（我们将这个保存的栈帧称为old_bp），准备创建下一个栈帧。当前视图就是进行push rbp; mov rbp,rsp;之后的栈帧状态。此时如果我们想要访问函数的第一个参数，我们就需要访问new_bp+4地址上的内容。
但是这里有一个问题，我们的ADD指令无法对bp进行运算，所以我们需要设置一个新的指令，用于访问栈帧上的地址LEA <offset>。我们具体的实现如下：
else if(op == LEA) {ax = (int)(bp + *pc++);}
现在，我们就完成了实现函数调用的所有指令了。
运算符指令
我们在C语言中支持的各种运算符号都是二元的，所以我们指令的参数也应该是由两个的，但是我们只有一个通用寄存器，这就导致我们需要将其中一个参数放在栈上，另一个参数存放在ax中，我们通过指令计算出来的结果也存放在ax上。
我们的实现如下：
else if (op == OR) ax = *sp++ | ax;
else if (op == XOR) ax = *sp++ ^ ax;
else if (op == AND) ax = *sp++ & ax;
else if (op == EQ) ax = *sp++ == ax;
else if (op == NE) ax = *sp++ != ax;
else if (op == LT) ax = *sp++ < ax;
else if (op == LE) ax = *sp++ <= ax;
else if (op == GT) ax = *sp++ > ax;
else if (op == GE) ax = *sp++ >= ax;
else if (op == SHL) ax = *sp++ << ax;
else if (op == SHR) ax = *sp++ >> ax;
else if (op == ADD) ax = *sp++ + ax;
else if (op == SUB) ax = *sp++ - ax;
else if (op == MUL) ax = *sp++ * ax;
else if (op == DIV) ax = *sp++ / ax;
else if (op == MOD) ax = *sp++ % ax;
内置命令
有很多由系统支持的函数，我们往往难以在机器上支持实现，所以这里我们简单的对函数进行封装，设置为内置的指令，用来支持一些常用的库函数调用。
这里我们就简单的对exit open close read printf malloc memset指令进行封装以确保我们的程序有基本的能力：
else if(op == EXIT) {printf("exit(%d)", *sp); return *sp;}
else if(op == OPEN) {ax = open((char *)sp[1], sp[0]);}
else if(op == CLOS) {ax = close(*sp);}
else if(op == READ) {ax = read(sp[2], (char*)sp[1], *sp);}
else if(op == PRTF) {tmp = sp+pc[1]; ax = printf((char*)tmp[-1],tmp[-2],tmp[-3],tmp[-4],tmp[-5],tmp[-6]);}
else if(op == MALC) {ax = (int)malloc(*sp);}
else if(op == MSET) {ax = (int)memset((char*)sp[2], sp[1], *sp);}
else if(op == MCMP) {ax = memcmp((char*)sp[2], (char*)sp[1], *sp);}
这里我们的参数在函数调用时是顺序入栈，所以看起来比较反直觉，结合栈是自顶向下索引的，所以我们最终可以很好的理解我们的参数调用顺序。
最后在加上一个错误判断，我们的虚拟机指令就完成了：
else {
printf("unknown instruction:%d\n", op);
return -1;
}
测试
现在我们的虚拟机指令就完成了，我们可以做一个简单的测试，来看我们的机器能否正确的运行：
i = 0;
pc = text;
text[i++] = IMM;
text[i++] = 12;
text[i++] = PUSH;
text[i++] = IMM;
text[i++] = 5;
text[i++] = DIV;
text[i++] = PUSH;
text[i++] = IMM;
text[i++] = 1;
text[i++] = EXIT;
程序执行的结果是：
ylin@Ylin:~/Program/c4$ ./a.out
exit(2)
至此我们的虚拟机以及指令架构就完成了