C解释引擎

(C Explain Engine)

二〇一一年十一月

文件标识

文件状态 文件标识： D20111102 当前版本： V1.0 作 者： 完成日期： 20120419 【 】 草稿文件 【 】 正式文件 【√】 更改正式文件 版本历史

版本/状态 V1.0 V0.5

作者 参与者 起止日期 20120416-0421 20111102-1120 备注 目录

C解释引擎 ...................................................................................................................... 1 (C Explain Engine) ..................................................................................................... 1 1. 解释语言和编译语言.................................................................................................... 4

1.1. 解释类 ............................................................................................................... 4 1.2. 编译类 ............................................................................................................... 4 1.3. 编译和解释的区别.............................................................................................. 4 2. 解释引擎 ..................................................................................................................... 5

2.1. 存储结构............................................................................................................ 5

2.1.1. 内存池 ..................................................................................................... 5 2.1.2. 栈 ............................................................................................................ 5 2.2. 词法分析............................................................................................................ 5 2.3. 类型解析............................................................................................................ 6

2.3.1. 类型的表示 .............................................................................................. 6 2.3.2. 类型解析 .................................................................................................. 6 2.4. 表达式解析 ........................................................................................................ 6

2.4.1. BNF定义 .................................................................................................. 6

2.4.2. 2.4.3. 2.4.4. 2.4.5.

表达式解析 .............................................................................................. 7 后缀表达式 .............................................................................................. 7 后缀表达式到中间代码 ............................................................................. 7 中间代码的表示 ....................................................................................... 8

2.5. 语法解析............................................................................................................ 8

2.5.1. 代码块 ..................................................................................................... 8 2.5.2. 控制语句 .................................................................................................. 8

2.5.2.1. C语言中，控制语句 ........................................................................ 8 2.5.2.2. 控制语句中的break和continue ....................................................... 8 2.5.2.3. 其他控制语句的代码形式 ................................................................ 8 2.5.3. 局部变量的生命周期 ................................................................................ 9

第 2 页 共 10 页

2.5.4. 函数解析 .................................................................................................. 9 2.6. 运行脚本............................................................................................................ 9

2.6.1. 脚本的执行要素 ....................................................................................... 9 2.6.2. 栈的模拟. ................................................................................................. 9 2.6.3. 变量在栈中的地址计算 ............................................................................10

2.6.4. 函数的调用过程 ......................................................................................10 2.6.5. 命令的解析 .............................................................................................10 2.6.6. C的库函数调用........................................................................................10

第 3 页 共 10 页

1. 解释语言和编译语言

高级语言所编制的程序不能直接被计算机识别，必须经过转换才能被执行，按转换方式可 将它们分为两类。

1.1. 解释类

执行方式类似于我们日常生活中的“同声翻译”，应用程序源代码一边由相应语言的解释引擎“翻译”成目标代码(机器语言)，一边执行，因此效率比较低，而且不能生成可独立执行的可执行文件，应用程序不能脱离其解释引擎，但这种方式比较灵活，可以动态地调整、修改应用程序，典型的解释型的高级语言有BASIC。

1.2. 编译类

编译是指在应用源程序执行之前，就将程序源代码“翻译”成目标代码(机器语言)，因此其目标程序可以脱离其语言环境独立执行，使用比较方便、效率较高。但应用程序一旦需要修改，必须先修改源代码，再重新编译生成新的目标文件(＊.OBJ)才能执行，只有目标文件而没有源代码，修改很不方便。现在大多数的编程语言都是编译型的，例如Visual C＋＋、Delphi等。

高级语言里一个程序的编译和执行大概是下面的情况：编译器将高级语言从源代码翻译成与之等价的目标程序（就相当于从中文翻译成中文），而后就隐退了。在随后的某个时刻，用户启动目标程序由操作系统执行。实现高级语言的另外一种方式为解释。

1.3. 编译和解释的区别

与编译不同的是，解释引擎在目标程序（其实根本就没有目标程序，只是与编译来对比）执行期间，解释引擎一直随之运行。这种执行过程完全由解释引擎控制的。从效果上看，解释引擎实现了一台“虚拟计算机”，其“机器语言”就是高级语言，解释引擎一次读入一条或多条语句，按照其自身规定的方式去执行相应的操作。一般说来，解释比编译有着很好的灵活性；编译一般有着较好的性能。

第 4 页 共 10 页

2. 解释引擎

2.1. 存储结构

2.1.1. 内存池

在一些小的程序里，没什么必要添加内存管理模块在里面。但是对于比较复杂的代码，如果需要很多的内存操作，那么加入自己的内存管理是有必要的。至少有一些好处：能够加快内存的申请和释放；能够轻松的查找内存泄露问题；能够对整个软件的内存消耗做一个比较精确的统计；对以后的优化有很大的好处等等。所以，在我的解释引擎里，我加入了一个简单的内存管理模块，仿造了内存池的做法。 主要思想是这样的： a.记录所有的申请的内存

b.当释放内存时，记录下来以供下次申请使用 c.申请内存时，可以直接使用前面释放过的内存

为了达到以上的功能。我为申请内存的大小划分粒度，例如：我得粒度这么安排{16,32,64,128,...}那么申请17个字节的大小时候，我会申请32个字节的大小。这样子方便管理。并且为每个粒度创建一个可用内存的双向链表。申请内存时，就可直接从这些链表头中申请（即将一个节点从链表头移除，作为被申请的空间，并插入到在使用的链表中），内存的释放则是一个想法的过程。

2.1.2. 栈

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

2.2. 词法分析

词法分析是编译原理中最容易理解的，就算没有了解过编译原理，也能写出一个词法分析器。我们不用理解正则表达式，不用理解状态机原理，就可以轻松的完成词法的分析。 这里首先介绍下自顶向下的解析过程，所谓的自顶向下，按我的理解，就是从一个大的集合解析到小的集合。例如：解析一个文件，那么进入文件，解析一个函数，进入一个函数，解析局部变量，解析表达式，进入表达式，解析变量、常量等等，最终完成一个C文件的解析过程。整个过程，其实就是一个猜测的过程。但是这个过程中，我们必须依赖于文件中的每个词（token），token可以看成是解析过程中的一个单位。

第 5 页 共 10 页

2.3. 类型解析

2.3.1. 类型的表示

C语言的类型是相当灵活的，除了标准的类型(int char float double long 等等)外，自己根据需求，能定义出无穷的类型。一个具体的例子： int * a[10]; 它表示的意思是：

a is ARRAY 0..9 of POINTER to INT

2.3.2. 类型解析

定义一个类型，我们可以把它分成三个部分：

specifier + id + dclor

对应到一个具体的定义：int * p[10]; 这三部分分别是： specifier int * id p

dclor [10]

类型的解析过程是这样的，首先找到id，然后根据一个规则（向右再向左），依次解析出这个类型。 有几种情况：

a. [ 表示数组，如果遇到[ 则进入解析数组函数 b. ( 表示函数，如果遇到( 则进入解析参数列表函数

2.4. 表达式解析

2.4.1. BNF定义

虽然不想多提理论知识，但是有些东西还是避免不了。在解析表达式的时候，我们必须知道它的BNF定义，这样解析起来就非常方便了。所谓的BNF定义，相信大家看一眼就知道了：

exp_additive -> exp_multiplicative ( \"+\"|\"-\" ) exp_multiplicative exp_multiplicative -> exp_cast ( \"*\"|\"/\"|\"%\" ) exp_cast exp_cast -> ... 意思是：

加法表达式可以表示为 “乘法表达式 + 乘法表达式”

乘法表达式可以表示为 “类型转换表达式 *或/或% 类型转换表达式”

第 6 页 共 10 页

2.4.2. 表达式解析

a. 调用exp_additive时，先调用exp_multiplicative

b. 然后判断后面是否是 + 或 -，如果是，再次调用exp_multiplicative

这样就完成了加法表达式的解析。如果非要问为什么这么写就能解析出表达式，那么我们可以举个例子： a = a * b + c * d;

2.4.3. 后缀表达式

什么是后缀表达式？我们还是从例子出发，上面的表达式，转化成后缀表达式就是这样子的： a a b * c d * + =

为什么要写成这种奇怪的形式？我们不是吃饱了撑着，从左往右分别查看这个表达式您就知道原因了。 a a

b

* 得到*号，那么拿前面的两个变量a b求和

c d

* 得到*号，那么拿前面的两个变量c d求和

+ 的到+号，获取前面的两个变量 a*b c*d 的结果，求和 = 得到=号，将前面的结果赋给a

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

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

@4 = a = @3;

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

第 7 页 共 10 页

2.4.5. 中间代码的表示

2.5. 语法解析

2.5.1. 代码块

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

exp1 exp2 ...

}

它由\"{\"开始，由\结束，中间包含多条表达式，或者是控制语句。如果不是以\"{\"开始，那么，一个代码块就是一条表达式。在上面的章节，我们已经介绍过了，每个表达式会产生一个中间代码。它是一个链表 struct _code * ，而一个代码块，是由多个表达式组成的，所以我们将每个表达式的中间代码链表连到一起就成了代码块的中间代码了。

2.5.2. 控制语句

2.5.2.1. C语言中，控制语句

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

2.5.2.2. 控制语句中的break和continue

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

2.5.2.3. 其他控制语句的代码形式

第 8 页 共 10 页

2.5.3. 局部变量的生命周期

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

int a; { int a;

}

printf(\"%d\\n\ }

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

2.5.4. 函数解析

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

2.6. 运行脚本

2.6.1. 脚本的执行要素

一个脚本要被执行，必须要为它创建一个环境，就想操作系统中为没有程序创建一个进程一样。

一个C语言程序，其实只有几个要素：运算符，变量，函数。所以，一个C脚本要被执行，首先，它必须具备中间代码命令的解析；其次，必须要有变量的内存空间；再次，必须要有函数的调用解析，即函数调用栈的模拟。所以，一个脚本的执行，最重要的是变量内存的分配和栈的维护，还有命令的执行。

2.6.2. 栈的模拟.

在执行时，我们不能直接根据变量名去查找变量，这样既麻烦，而且效率也很低；而是应该

第 9 页 共 10 页

根据变量的地址去存取变量。但是变量保存在哪里，怎么计算，这就是引入栈的原因了。 为了方便处理，我们将中间变量也放到栈里面，但是，中间变量的地址是可以被重用的，因为一条语句被执行完后，这条语句的中间变量就不会再被用到，所以，上一条语句的中间变量是可以被回收的

2.6.3. 变量在栈中的地址计算

首先，每个函数中，都有一个固定的esp，可以视为该函数在栈中的起始位置。然后其他的变量都被表示为距离esp的值，即偏移量。例如上面的例子，我们在解析出一个函数的中间代码时，就知道了这个函数的所有的局部变量，形参列表，并且知道这些变量的类型。所有我们可以根据类型的大小，计算他们在栈中的位置。

2.6.4. 函数的调用过程

2.6.5. 命令的解析

每条中间变量都由一个操作符和若干个操作数组成，这里没办法罗列出所有的操作符的解析。仅仅说明一个最简单的情况：

@1 = a + b 对应于 [esp+12] = [esp-20] + [esp-16];

这条中间代码，它的操作符是\"+\操作数是[-20],[-16], 目标操作数是[12]。所以解析过程相当简单，变成C代码就是这样的：

*(int*)(esp+12) = *(int*)(esp-12) + *(int*)(esp-16);

2.6.6. C的库函数调用

C语言有它的库函数，如果我们的解释器要自己实现这些库函数的话，那么工作量就大大增加了，有什么办法直接调用系统的库函数呢。如果能做到这点，那么也就能解释器的使用者提供更加强大的交换方式----即使用者可以注册自己的函数，供脚本使用。

第 10 页 共 10 页