C语言解释器的实现

1 年前

封狼居胥

止鼾器-睡眠的定义者

序言

在写CuteC文本编辑器的同时，为了使之有脚本执行能力。特意实现了一个简易的C语言解释器，所谓的解释器，就是它是解析执行脚本文件的，并不产生可执行的目标代码。它具备了C语言的几乎全部的语法。随着时间的推移，我打算把它作为一个独立的项目来开发了。在这个过程中，自己也学到了不少的知识，所以也打算跟大家分享。写这些东西，虽然是重复发明轮子的事，但也不至于是在浪费生命。程序员嘛，我总觉得应该是要理解我们每天所编译出来的程序是怎么被执行，应该明白我们敲打的每行代码的实际意义。
我打算写一个系列的文章来说明这个解释器的实现过程，其中对于编译原理的理论知识不做太多的讲解，一是不容易提高大家的积极性，二是自己水平有限。所以我觉得大部分从例子出发，讲解一个个目标的实现过程，大家慢慢体会，估计收获会比较大。

通过这一系列的文章，大家应该可以学到以下的知识。
1.更深入的理解C的内部细节，对以后的开发总是有好处的。例如，你能很清楚C语言的类型定义，通过基本的类型为何能够定义出无穷的各种类型。
2.了解表达式的解析，中间代码的产生。这点非常有意思，了解了这点，可以用同样的方法做很多事情，包括设计个计算器，解析复杂的配置文件，在软件中解析命令等等。
3.对编译器有一个感性的认识，虽然离写出编译器还比较遥远，但对于语法解析，预编译，理解的就比较深入了。现在很多软件都有预编译的模块在里面，比如Pro*C, GSoap等等。
4.我们产生的中间代码其实已经非常接近汇编代码，这对理解C的执行过程总是有好处的。

总之，晒晒自己的成果，怎么说也是我亲亲苦苦写出来的，希望大家能找到点可以借鉴的东西吧~代码我还在努力的编写，过一段时间再放出来一个初级的版本。如果工作忙，那估计就要再等一段时间了。

以前我发过上一个版本的解释器，可以在这篇文章中下载，不过我现在已经重写了解释器，所以要看结果可以先下载下来看看:）。

存储结构(一)

1. 内存池

2. 栈

3. Hash表

1.内存池

在一些小的程序里，没什么必要添加内存管理模块在里面。但是对于比较复杂的代码，如果需要很多的内存操作，那么加入自己的内存管理是有必要的。至少有一些好处：能够加快内存的申请和释放；能够轻松的查找内存泄露问题；能够对整个软件的内存消耗做一个比较精确的统计；对以后的优化有很大的好处等等。所以，在我的解释器里，我加入了一个简单的内存管理模块，仿造了内存池的做法。
主要思想是这样的：
a.记录所有的申请的内存
b.当释放内存时，记录下来以供下次申请使用
c.申请内存时，可以直接使用前面释放过的内存
为了达到以上的功能。我为申请内存的大小划分粒度，例如：我得粒度这么安排{16,32,64,128,...}那么申请17个字节的大小时候，我会申请32个字节的大小。这样子方便管理。并且为每个粒度创建一个可用内存的双向链表。申请内存时，就可直接从这些链表头中申请（即将一个节点从链表头移除，作为被申请的空间，并插入到在使用的链表中），内存的释放则是一个想法的过程。这些的存储结构如下所示：

typedef struct _pool_block{
    int size;
    void * data;
    struct _pool_block * next;
    struct _pool_block * pre;
}pool_block_t;
typedef struct _pool{
    int num_all;
    int num_free;
    pool_block_t * list_all;
    pool_block_t * list_free[POOL_ATOM_NUM];
}pool_t;
int pool_atom_tab[POOL_ATOM_NUM] = {
    32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, -1
};

说明：
a.内存的申请会按照pool_atom_tab数组中的大小对齐，比如申请10byte，那么，我会申请32byte.
b.为每个粒度保存一个双向链表，用于保存被释放的内存。如果要申请的内存超过8192，那么我直接调用系统的malloc，释放时，直接调用free.
c.内存申请过程：到相应的粒度链表（list_free）中查看是否有可用内存，如果有，直接将它从该list_free链表中移动到list_all链表。
d.内存释放过程：要释放的内存必定保存在list_all中，根据它的大小，把它移动到相应的list_free链表。
e.pool_block_t结构被放置在申请内存的前面，则在释放时，直接根据Buffer指针就可得到pool_block_t的位置，从而得到next和pre，快速的在链表中移动。

2.栈

栈在解释器中用到的地方很多，不管是表达式的解析，还是代码块的解析，类型的解析，等等都用到了栈。所以不实现它是不可能的事，不过在数据结构中他是最简单的了，无非就是申请一个空间，按一个一个的节点保存进去，按一个一个的节点取出来。没什么技巧在里面，只是这个我让栈的大小空间是自动增长和减小的，这么做的目的是：栈的空间仅仅限制于内存的大小。但是，这么做得缺点是，当栈的空间大小自动变化时，栈内的数据要被复制一遍，这务必会影响效率。但没有办法，暂时之能这样了。唯一的办法是在时间和空间上做一个选择。
栈的存储结构如下：

typedef struct _stack{
    int item_len;
    int item_num;
    int stack_size;
    char *p;
}stack_t;

说明：
item_len: 保存每个节点的长度
item_num: 栈中节点的个数
stack_size: 栈中可保存的节点个数
p: 指向栈空间
a.当节点的个数item_num大于stack_size,那么必须重新申请空间，将原来的数据拷贝到新的空间。
b.当节点的个数减小到一定的数量时，可以重新申请小的数据空间，释放原来大的空间。

3.hash表

hash由于其快速的查找能力而著称，但是它太浪费内存了，所以用得的比较少，仅仅是在函数的调用时被使用。因为函数的调用是频繁的，如果从头查找函数，那将浪费很多的时间。这里引入hash也是必要的。

#define HH_TAB_SIZE 128
typedef struct _hh_node{
    unsigned int hash, klen, dlen;
    void * key;
    void * data;
    struct _hh_node *next;
}hh_node_t;
typedef struct _hh_head{
    unsigned int node_num;
    hh_node_t *  node_list;
}hh_head_t;
typedef struct _hh_hash{
    hh_opts_t opts;
    hh_head_t tabs[HH_TAB_SIZE];
}hh_hash_t;
typedef struct _hh_opts{
    int (*cmp_key)(void *key1, void *key2);
    unsigned int (*get_hash)(void *key);
    void * (*new_key)(int);
    void * (*new_data)(int);
    void (*del_key)(void *key);
    void (*del_data)(void *data);
}hh_opts_t;

词法分析(二)

词法分析是编译原理中最容易理解的，就算没有了解过编译原理，也能写出一个词法分析器。我们不用理解正则表达式，不用理解状态机原理，就可以轻松的完成词法的分析。

这里首先介绍下自顶向下的解析过程，所谓的自顶向下，按我的理解，就是从一个大的集合解析到小的集合。例如：解析一个文件，那么进入文件，解析一个函数，进入一个函数，解析局部变量，解析表达式，进入表达式，解析变量、常量等等，最终完成一个C文件的解析过程。整个过程，其实就是一个猜测的过程。但是这个过程中，我们必须依赖于文件中的每个词（token），token可以看成是解析过程中的一个单位。

例如：

1. 关键词有：int char double long for while ......

2. 运算符有：+ - * / ......

3. 数字常量：12 0x34 3.45

4. 字符串："hello"

...

等等.

那么我们必须实现一个函数get_token，执行这个函数，我们获取文件中的一个token。例如现在一个C文件：

  int main(int agrc, char **argv ){
      return 0;
  }

那么多次执行get_token，分别得到的token为：

  int
  (           <----③
  ...

除了一个get_token函数外，还需要一个叫做put_back的函数，因为脚本解析是一个猜测的过程。有时候我们必须知道下一个的token是什么，才能判断该走哪个分支。还是上面的例子，在③的地方，我们得到了"("，所以知道main是一个函数，那么如果该token不是"("，而是"=", 我们知道它不是一个函数，而是一个基本的变量定义，并且需要初始化。那么我们必须调用put_back函数，把该token重新放到缓存中，使得下次get_token的时候，还会拿到这个token,而不是下个token。

至于get_token和put_back函数如何实现，我就不多说了。我使用了最笨的方法，无非就是每个字符一个一个的向后扫描，判断是该返回什么标示。每个token被分为各种类型token_type:

  enum tok_types{ DELIMITER = 1, IDENTIFIER, KEYWORD, TEMP, STRING, CHARACTOR, NUMBER, TYPE, BLOCK, PRECOMPILE };

类型意义例如

-----------------------------------------------------------------------------

DELIMITER 标示分隔符 ; | + -

IDENTIFIER 标示ID标示符 var hello

KEYWORD 关键字 int char while do

STRING 字符串 "string"

CHARACTOR 字符 'c'

NUMBER 数字常量 123 012 0x34

TYPE 类型 typedef int int32; 那么int32就被标示为TYPE

BLOCK 块标志 { }

PRECOMPILE 预编译行 #define

TEMP 保留

词法分析的目的就是扫描源码，区分出这些类型，变返回该token。供解释器的其他模块使用。

类型解析(三)

1.类型的表示

C语言的类型是相当灵活的，除了标准的类型(int char float double long 等等)外，自己根据需求，能定义出无穷的类型。一个具体的例子：
int * a[10];
它表示的意思是：
a is ARRAY 0..9 of POINTER to INT
仔细观察它的意思，就会发现，这个类型是其他基本类型按照一定顺序的组合：ARRAY|POINTER|INT。要表示这种形式，链表是最合适不过的了。如下图：

还有一些情况，比如结构体类型，那么上述的表示就不大合适了。例如下面的结构体：

      struct _a{
          int n;
          char * p[10];
      };

结构中的每个域分别是由一个个的类型组成的。那么，我们可以用一个类型链表组成。具体就是：

      _a is STRUCT of
          n: INT
          p: ARRAY 0..9 of POINTER to INT

如下图所示：

程序中的类型定义如下：

      typedef struct type_t ttype_t;
      typedef struct type_t * ptype_t;
      typedef struct type_list_t ttype_list_t;
      typedef struct type_list_t * ptype_list_t;
      struct type_t{
          int bty;
          int size;
          ptype_t ty;
          ptype_list_t sty;
          char * name;
          char * tag;
          char * pos;
      struct type_list_t{
          ptype_t ty;
          ptype_list_t next;
      };

2.类型解析

定义一个类型，我们可以把它分成三个部分：
specifier + id + dclor
对应到一个具体的定义：int * p[10]; 这三部分分别是：
specifier int *
id p
dclor [10]
类型的解析过程是这样的，首先找到id，然后根据一个规则（向右再向左），依次解析出这个类型：

在第2步，有几种情况：
a. [ 表示数组，如果遇到[ 则进入解析数组函数
b. ( 表示函数，如果遇到( 则进入解析参数列表函数

所以我们的解析函数是这样的：

      void dclor( ptype_t ty ){
          switch( *token ){
          case ALY: dcl_arrays(ty); break;
          case '(': ty->pos = prog;  dcl_args(ty); break;
          dcl_pointers(ty);
          while(tok_top >= 0){
              if( *tok_stack[tok_top].token == '(' ){  //左边是( 继续向右解析
                  token_pop();
                  get_token();
                  dclor(ty);
              else{
                  struct token_node  node;
                  node = token_pop();
                  if( strcmp( node.token, "splitor" ) == 0 ){
                      break;
                  if( node.ty != NULL ){ 
                      sbt.ty = node.ty;
                  dcl_specifier( node.tok, NULL ); 
      }

对于类型的解析，我这里推荐下《C专家编程》中的类型解释部分，里面讲解得更加透彻。

表达式解析(四)

1. BNF定义

虽然不想多提理论知识，但是有些东西还是避免不了。在解析表达式的时候，我们必须知道它的BNF定义，这样解析起来就非常方便了。所谓的BNF定义，相信大家看一眼就知道了：
exp_additive -> exp_multiplicative ( "+"|"-" ) exp_multiplicative
exp_multiplicative -> exp_cast ( "*"|"/"|"%" ) exp_cast
exp_cast -> ...
意思是：
加法表达式可以表示为 “乘法表达式 + 乘法表达式”
乘法表达式可以表示为 “类型转换表达式 *或/或% 类型转换表达式”
...

知道了整个C语言的BNF定义，我们就可以很简单的按照这个定义来解析了。整个C的BNF定义可以查看以下的链接：
http:// lists.canonical.org/pip ermail/kragen-hacks/1999-October/000201.html

2. 表达式解析

知道了上面的BNF定义，那么我们的解析代码就可以这么写：
void exp_additive(){
char op;
exp_multiplicative();
while(
(op = OPERATOR( '+' )) ||
op = OPERATOR( '-' )) ){
get_token();
exp_multiplicative();
...
}
}

void exp_multiplicative(){
char op;
exp_cast();
while(
(op = OPERATOR( '*' )) ||
(op = OPERATOR( '/' )) ||
(op = OPERATOR( '%' )) ){
get_token();
exp_cast();
...
}
}
过程是这样的：
a. 调用exp_additive时，先调用exp_multiplicative
b. 然后判断后面是否是 + 或 -，如果是，再次调用exp_multiplicative
这样就完成了加法表达式的解析。如果非要问为什么这么写就能解析出表达式，那么我们可以举个例子：
a = a * b + c * d;
那么，他的语法树应该是这样的：

（图4.2 语法树）
我们向下递归调用的过程，其实就是构造这个语法树的过程。但是我们不会真的创建出这个语法树，而是保存了一个与它等价的一种形式--后缀表达式,其实后缀表达式就是语法树的后续遍历。

3. 后缀表达式

什么是后缀表达式？我们还是从例子出发，上面的表达式，转化成后缀表达式就是这样子的：
a a b * c d * + =
为什么要写成这种奇怪的形式？我们不是吃饱了撑着，从左往右分别查看这个表达式您就知道原因了。
a
a
b
* 得到*号，那么拿前面的两个变量a b求和
c
d
* 得到*号，那么拿前面的两个变量c d求和
+ 的到+号，获取前面的两个变量 a*b c*d 的结果，求和
= 得到=号，将前面的结果赋给a
为了生成后缀表达式，我们要改造上面的解析函数。
void exp_additive(){
char op;
exp_multiplicative();
while(
(op = OPERATOR( '+' )) ||
op = OPERATOR( '-' )) ){
get_token();
exp_multiplicative();
EXP_OPR( op ); <--将运算符入栈
}
}

void exp_multiplicative(){
char op;
exp_cast();
while(
(op = OPERATOR( '*' )) ||
(op = OPERATOR( '/' )) ||
(op = OPERATOR( '%' )) ){
get_token();
exp_cast();
EXP_OPR( op ); <--将运算符入栈
}
}
那么解析完成以后，我们的栈中就会形成后缀表达式了。有了表达式的后缀形式，我们就可以很轻松的产生后缀表达式的中间代码了。

4.后缀表达式到中间代码

首先我们先说明一下我们的中间代码是怎样的一种形式，这里暂且叫它为三元表达式，是因为这个种中间代码的形式是固定的。例如，紧接上节的例子，表达式 a = a * b + c * d;的中间代码最终应该是这样子的：

@1 = a * b;
@2 = c * d;
@3 = @1 + @2;
@4 = a = @3;

其中以@开头的都是我们为之产生的中间变量。生成上述的中间代码后，将会对我们后续的解析提供很大的帮助，应为它结构固定，所以我们不用再去解析源程序，而是通过这个中间代码产生最终的执行代码。这里先声明下，我所说的执行代码，不是真正意义上得可执行代码，而是能够被我的软件解析的命令序列。其实它已经非常接近汇编代码。但是我们的目标是解析执行，并不产生汇编代码，所以产生简单的命令序列已经可以完成目标了。

我们前面解析表达式，产生后缀形式，为的就是生产这种中间表达式。表达式"a = a * b + c * d;"的后缀形式是"a a b * c d * + =;" 我们要根据这个后缀形式产生中间代码的过程如下：

5.中间代码的表示

  typedef struct _code code_t;
  typedef struct _code * pcode_t;
  struct _code{
      char opr;
      struct{
          int  i, n, t;
      }lab;
      v_t var[4];
      code_t * next; 
  };

它是一个链表，每个节点保存了一个形如"@1 = a * b;"的中间代码。其中，opr表示运算符"*";lab表示该节点为一个LAB,留到后面章节讲解;var表示运算变量，如上面表达式的"@1, a, b"。
这样子，当一个表达式解析完成后，会生成一个链表，表示该表达式的中间代码。

语法解析(五)

1.代码块

代码块是由多个表达式组成的一组代码。它可以看成是以下的形式：

  {
  }

它由"{"开始，由"}"结束，中间包含多条表达式，或者是控制语句。如果不是以"{"开始，那么，一个代码块就是一条表达式。在上面的章节，我们已经介绍过了，每个表达式会产生一个中间代码。它是一个链表 struct _code * ，而一个代码块，是由多个表达式组成的，所以我们将每个表达式的中间代码链表连到一起就成了代码块的中间代码了。
如果代码块中包含控制语句，那么，我们必须做一些处理，即在代码链表中插入跳转语句，和跳转位置(Lab)。

2.控制语句

2.1 C语言中，控制语句有这些：

 a. if( exp ) stmt else stmt
 b. do stmt while( exp )
 c. while( exp ) stmt
 d. for( exp1; exp2; exp3 ) stmt
 e. switch( exp ) stmt
 f. goto lab

其中，stmt表示一个代码块。我们如何为这些代码产生中间代码呢？这里还要说明的是跳转语句。比如一个if语句：
if( exp ) stmt1 else stmt2
那么,它的意思是，当 exp == 0 时，跳转到stmt2位置；当exp != 0的时候不做跳转，但是stmt1执行完成后要跳转到stmt2的后面。所以，这中间涉及了两个东西：跳转语句和跳转的位置。跳转语句我们用三种命令表示：JE、JNE、JMP，即不等于跳转，等于跳转，无条件跳转。跳转的位置我们用Lab表示，即在代码链表中插入一个标签，供跳转语句查找要跳转的位置。
还是上面的if语句，它产生后的代码应该是这样的：

  A.  if( exp ) stmt1 else stmt2 -->
 JE L1
        stmt1
 JMP L2
        stmt2

其中，L1 L2分别占用代码链表的一个节点，在code_t结构体中，用lab域表示。

2.2 控制语句中的break和continue .
在一些控制语句中，他们支持break和continue，即如果在代码块总出现break，那么他应该跳转到代码块的外面，如果是continue,那么跳转到条件语句继续执行。例如下面的do while语句：

B. do stmt while( exp ) -->
L1:
stmt <-- 如果这里出现break，那么JMP L3；如果出现continue, 那么JMP L2
L2:
exp
JNE L1
L3:
因为在解析stmt的时候，L1,L2和L3都已经固定好了，所以，在处理break和continue的时候，跳转的LAB都已经明确，可以用参数将L2和L3传递个stmt()函数，stmt函数中解析break和continue的时候，仅仅是添加一条跳转语句。

2.3 其他控制语句的代码形式 ：

C. while( exp ) stmt -->
JMP L2
L1:
stmt
L2:
exp
JNE L1
L3:

D. for( exp1; exp2; exp3 ) stmt -->
exp1
JMP L3
L1:
stmt
L2:
exp3
L3:
exp2
JNE goto L1
L4:

E. switch( exp ){
case 1: stmt1
case i: stmti
default: stmt
...
}

exp
selete i and jmp(L1..Ln,L)
Li: stmti
L: stmt
LL:

selete i and jmp(L1..Ln,L) 表示如果exp的结果是i,那么跳转到Li,否则跳转到L。switch语句跟别的控制语句不一样，其他的控制语句在还没解析代码块的时候，我们就已经知道应该创建几个Lab了，所以我们可以事先创建好Lab，然后在适当的位置插入JMP语句，这个JMP语句中跳转到的Lab这时候已经确定了。但是对于switch语句，我们事先不知道case在什么地方，所以不知道"selete i and jmp(L1..Ln,L)"应该对应什么代码。所以，我们必须解析完stmt(代码块)之后才能产生代码。具体的做法是在解析代码快的时候记录下所以的Lab，解析完成后再做相应的处理，即构造"selete i and jmp(L1..Ln,L)"代码，将它连接到中间代码的前面。

F. goto Lab -->
JMP Lab

在解析goto的时候，必须将"Lab"名称转换成我们的Lab的表示形式。

3.局部变量的生命周期

在一个函数中定义的变量称之为局部变量，但是局部变量有自己的生命周期，即在自己的代码块中定义的，那么它只对这个代码块的代码可见。例如有下面的代码：

    {
        int a;
            int a;
        printf("%d\n", a);
    }

那么第二个a对printf语句处是不可见的。为了表示变量的生命周期，我们为每个变量加入了begin和end域，用来保存该变量对[begin,end]区间的代码是可见的。所以，这里begin,和end怎么解析是个问题，begin不难，在解析定义的时候就可以确定，但是end确实比较难，因为必须在一个代码块中结束后（即解析到"}"后），才知道end的值。所以为了确定end的值，栈在这里又被征用了。

{ <-- 代码块开始，创建一个stack1
int a; <-- 解析完a,将a压入stack1, 此时 a.begin已经确定
{ <-- 遇到"{" 递归调用解析函数，创建一个stack2
int a; <-- 解析完a,将a压入stack2, 此时 a.begin已经确定
} <-- 遇到"}"，表示该代码块完成，将a从stack2中pop出来，设置a.end ！
此时，递归调用结束。返回到上一个代码块处理函数。
printf("%d\n", a); <--
} <-- 到"}"，表示该代码块完成，将a从stack1中pop出来，设置a.end ！

经过上面的过程，第一个a和第二个a的begin和end值都被确定。在代码的处理过程中，我们根据变量名查找变量时，必须根据当前代码的位置，来判断位置是否属于[begin,end]区间，而不仅仅是判断变量名。

4.函数解析

一个函数包括这几个部分：
a. 返回值类型
b. 形参列表
c. 局部变量
d. 代码块
例如下面的函数：

    int add( int a, int b )
        int c;
        c = a + b;
        return c;
    }

那么它的返回值类型是int, 参数列表是a、b，局部变量有c, 执行代码是 " c = a + b; return c; " 。仔细观察，它其实是由函数声明和一个代码块组成的。所以解析这个函数也很简单，其实就是解析声明，得到函数名，参数列表和返回值类型。然后执行上一章节描述的解析代码块函数，得到该函数的中间代码链。

5.附

比如有如下的代码：

  int main( int argc, char **argv ){
      int a, b;