C语言解释器实现基础知识

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

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

3、, GSoap等等。 4.我们产生的中间代码其实已经非常接近汇编代码，这对理解C的执行过程总是有好处的。 总之，晒晒自己的成果，怎么说也是我亲亲苦苦写出来的，希望大家能找到点可以借鉴的东西吧代码我还在努力的编写，过一段时间再放出来一个初级的版本。如果工作忙，那估计就要再等一段时间了。 以前我发过上一个版本的解释器，可以在 HYPERLINK /linxr/archive/2011/03/23/1992644.html 这篇文章中下载，不过我现在已经重写了解释器，所以要看结果可以先下载下来看看:）。(二)1.内存池 在一些小的程序里，没什么必要添加内存管理模块在里面。但是对于比较复杂的代码，如果

4、需要很多的内存操作，那么加入自己的内存管理是有必要的。至少有一些好处：能够加快内存的申请和释放；能够轻松的查找内存泄露问题；能够对整个软件的内存消耗做一个比较精确的统计；对以后的优化有很大的好处等等。所以，在我的解释器里，我加入了一个简单的内存管理模块，仿造了内存池的做法。 主要思想是这样的： a.记录所有的申请的内存 b.当释放内存时，记录下来以供下次申请使用 c.申请内存时，可以直接使用前面释放过的内存 为了达到以上的功能。我为申请内存的大小划分粒度，例如：我得粒度这么安排16,32,64,128,.那么申请17个字节的大小时候，我会申请32个字节的大小。这样子方便管理。并且为每个粒度创建

5、一个可用内存的双向链表。申请内存时，就可直接从这些链表头中申请（即将一个节点从链表头移除，作为被申请的空间，并插入到在使用的链表中），内存的释放则是一个想法的过程。这些的存储结构如下所示： （图1.1 内存池的存储结构）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; po

6、ol_block_t * list_freePOOL_ATOM_NUM;pool_t;int pool_atom_tabPOOL_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）中查看是否有可用内存

7、，如果有，直接将它从该list_free链表中移动到list_all链表。 d.内存释放过程：要释放的内存必定保存在list_all中，根据它的大小，把它移动到相应的list_free链表。 e.pool_block_t结构被放置在申请内存的前面，则在释放时，直接根据Buffer指针就可得到pool_block_t的位置，从而得到next和pre，快速的在链表中移动。2.栈 栈在解释器中用到的地方很多，不管是表达式的解析，还是代码块的解析，类型的解析，等等都用到了栈。所以不实现它是不可能的事，不过在数据结构中他是最简单的了，无非就是申请一个空间，按一个一个的节点保存进去，按一个一个的节点取出来

8、。没什么技巧在里面，只是这个我让栈的大小空间是自动增长和减小的，这么做的目的是：栈的空间仅仅限制于内存的大小。但是，这么做得缺点是，当栈的空间大小自动变化时，栈内的数据要被复制一遍，这务必会影响效率。但没有办法，暂时之能这样了。唯一的办法是在时间和空间上做一个选择。 栈的存储结构如下： （图1.2 栈的存储结构）typedef struct _stack int item_len; int item_num; int stack_size; char *p;stack_t; 说明： item_len: 保存每个节点的长度 item_num: 栈中节点的个数 stack_size: 栈中可保存的

9、节点个数 p: 指向栈空间 a.当节点的个数item_num大于stack_size,那么必须重新申请空间，将原来的数据拷贝到新的空间。 b.当节点的个数减小到一定的数量时，可以重新申请小的数据空间，释放原来大的空间。3.hash表 hash由于其快速的查找能力而著称，但是它太浪费内存了，所以用得的比较少，仅仅是在函数的调用时被使用。因为函数的调用是频繁的，如果从头查找函数，那将浪费很多的时间。这里引入hash也是必要的。#define HH_TAB_SIZE128typedef struct _hh_node unsigned int hash, klen, dlen; void * key

10、; 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 tabsHH_TAB_SIZE;hh_hash_t;typedef struct _hh_opts int (*cmp_key)(void *key1, void *key2); unsigned int (*get_hash)(void *key

11、); void * (*new_key)(int); void * (*new_data)(int); void (*del_key)(void *key); void (*del_data)(void *data);hh_opts_t;(三)词法分析是编译原理中最容易理解的，就算没有了解过编译原理，也能写出一个词法分析器。我们不用理解正则表达式，不用理解状态机原理，就可以轻松的完成词法的分析。 这里首先介绍下自顶向下的解析过程，所谓的自顶向下，按我的理解，就是从一个大的集合解析到小的集合。例如：解析一个文件，那么进入文件，解析一个函数，进入一个函数，解析局部变量，解析表达式，进入表达式，解析

12、变量、常量等等，最终完成一个C文件的解析过程。整个过程，其实就是一个猜测的过程。但是这个过程中，我们必须依赖于文件中的每个词（token），token可以看成是解析过程中的一个单位。 例如： 1. 关键词有：int char double long for while . 2. 运算符有：+ - * / . 3. 数字常量：12 0 x34 3.45 4. 字符串 ：hello . 等等. 那么我们必须实现一个函数get_token，执行这个函数，我们获取文件中的一个token。例如现在一个C文件： int main(int agrc, char *argv ) return 0; 那么多次执行get_token，分别得到的token为： int main ( pos = prog;dcl_args(ty);break; dcl_pointers(ty); while(tok_top = 0) if( *tok_stacktok_top.token = ( )/左边是( 继续向右解析 token_pop();