91:c4编译器回顾(1)

我们将尝试构建一个C语言的解释器，这个项目也是我C语言的大作业。现在回顾看来，当时对整个项目都是知其然不知其所以然，从现在的眼光来看，当时很多做法都是很稚嫩的。尤其是对于这个项目结构的理解也远远不足，所以打算重构一遍。

构建流程

首先是整个编译器的构建流程，一般来讲，编译器的编写有三个步骤：

1. 词法分析器，用于将文本文件转换为内部的表示结构
2. 语法分析器，在词法分析得到的标记的基础之上，构建一棵语法树
3. 目标代码的生成，将语法树转换成目标代码

但是由于这里我们编写的是一个解释器，所以我们自定义自己的虚拟机框架和指令。我们通过语法分析词法分析之后得到的语法树，来生成使用自定义虚拟机框架的指令的目标代码。

编译器的框架

仿照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)

至此我们的虚拟机以及指令架构就完成了