开发自己的编译器和虚拟机(一)
有朋友问我有关编译原理的问题, 但事实上我并不是很了解编译原理的每个细节, 即使是了解但是有时候要解释清楚也非常费力, 特别是有的朋友一开始就问我如果写一个编译器, 让我很难回答清楚. 而且遗憾的是, 我一直太忙了,根本没有太多时间.所以很对不起这些朋友. 我想是该写一篇东西了, 也许可以解答许多朋友关心的问题.
1. 什么是脚本引擎
所谓脚本引擎(script engine), 就是一个脚本语言的编译器和虚拟机(执行器). 你可以使用这种脚本语言编写程序, 然后调用SE的接口进行编译和执行.
SE的优点是
1. 把应用逻辑或游戏的情节(一般是server端的逻辑)从系统代码中分离出来, 使他们有相对更高的灵活性
2. 降低应用开发的工作量和周期
2. 支持在线脚本修改和运行, 可以在运行时修改应用逻辑.
从某种角度上说， java， c#, 都是一种脚本引擎. 因为无非是编译器生成中间代码，虚拟机来执行他们。
3. 为什么使用脚本引擎
2001年的3月至5月间, 我写了这个脚本引擎. 因为需要写一个与应用无关的中间层服务平台(类似中间件), 需要有一个方案解决应用逻辑的易变性带来的问题.
当时我第一个想到的是plugin 模式. 即除了一个核心平台提供通信层，数据库访问，事务管理，用户管理等等之外， 所有的应用通过外挂DLL来加入系统.每个dll必须提供最基本的统一接口供平台调用. 比如ProcessRequest()等等, request 的数据结构
是固定的, 也就是说平台和应用的dll有一个协议, 这个协议适用任何形式的请求. 平台负责把请求分发到相关的dll, 由dll返回处理结果.
然后， 我们会提供相应的图形界面的应用开发工具让用户可以更直接更方便的开发应用。
两年后, 我在移植ISAPI 到AIX(是一个用户的变态需求)时, 发现这个想法几乎和ISAPI的架构一摸一样, 只不过ISAPI只适用于web http请求.
但是, 这个想法在当时被认为是过于丑陋. 我也同意了, 但是这种设计的perfomance会比较高.
于是, 第二个想法是用类似sql语句的方法来表达请求, 平台内置一个sql的解释器, 但是发现sql语句并不能使用所有复杂的需求, 比如复杂的计算,
复杂的数据结构, 复杂的应用逻辑. 并且不能使用平台外部的API， 比如想进行文件I/O操作， 或者想调用诸如Tuxedo之类的外部系统的功能也是不可能的。s
所以, 最终我提出了使用自己的脚本语言来描述逻辑, 并且该脚本语言可以调用外部dll中的库函数. 这样再复杂的逻辑也可以实现, 而且底层I/O操作, 数据库操作, 或者其他的底层操作可以封装在外部的dll*脚本调用, 每个dll的重用性提高了， 应用的开发者只需要关注于编写教崩就可以了, 系统的扩展性和灵活性完全实现了。 这样, 整个系统框架便完整了.
见图
4. 编译器
1. 语言设计
一开始, 没有决定使用c 语言, 因为希望语法比较简单. C 给人的感觉总是复杂. 希望是basic, 但是我一直不喜欢basic和pascal的语法, 觉得好涩, 一点不流畅. 就语言来讲, 我还是偏爱C, 怎么看怎么顺眼, 呵呵. java给人的感觉也不错, 但是那是晚辈, 无法和C相比.
我觉得, 任何语言, 最主要的也就是表达顺序, 分支和循环这三种逻辑, 以及算术, 逻辑, 关系, 赋值表达式, 所以最终的模样总是差不多的,
所以, 还是选择C.
为什么不自己创造语言呢?
1. 没有时间
2. 我自己设计的语法看起来总是和c很像:P，所以还不如用c呢.
考虑过参考mudos的源代码, 但那是个及其混乱的开源项目, 风险太大.
2. 解释器的生成器
第一个想用的的是yacc/bison.
但是看完说明书, 就觉得时间不够, 还有一个月, 需要写的东西太多.
于是找到了cocoR, 太棒了, 很直观, 给它一个语法说明, 他就给我一个workable的编译器.
我可以立刻去写代码生成可执行代码.
是不是太简单了, 呵呵.
但是这还只是个解释器, 要成为编译器, 需要生成代码.
一个月的时间, 不想去生成语法树和考虑什么预编译和中间代码优化了.
3. 生成代码
最头疼的工作来了.
必须把脚本翻译成可以执行的虚拟机指令.
1. 表达式栈
学过编译原理的同学都知道, 表达式必须用栈来分析. 没什么需要多说的, 碰到了你就会做的.
2. 浮点运算
一开始没有打算实现浮点运算. 可是, 忽然发现我们的应用多数和钱相关, 所以必须有浮点.
由于一开始没有考虑, 所以费了不少力气去支持浮点.
3. 栈机?
有两个选择, 支持栈和不支持栈.
如果虚拟机是一个"栈机"(stack machine), 那么所有临时的数据都会push到栈上. 栈机的缺点是有大量的push和pop操作。
如果你的虚拟机没有堆栈段， 那么所有临时变量都是预先分配的。这样做的优点是performance会比较好， 但是， 一个复杂的函数会占用大量内存。
因为我们需求是performance尽量高， 并且不会有非常非常复杂的逻辑， 所以， 我的虚拟机没有栈。
4. 类型转换
不支持强制类型转换, 但implicit的类型转换是必须支持的.
否则浮点和整数间的运算无法解决.
这是一个比较烦的问题, 分析表达式的时候必须判断是否需要进行类型转换, 那个操作数需要转换, 如何进行这种转换, 最终被转换出的操作数存放在新的地址上或寄存器中. 后面会讲到。
1. 什么是脚本引擎
所谓脚本引擎(script engine), 就是一个脚本语言的编译器和虚拟机(执行器). 你可以使用这种脚本语言编写程序, 然后调用SE的接口进行编译和执行.
SE的优点是
1. 把应用逻辑或游戏的情节(一般是server端的逻辑)从系统代码中分离出来, 使他们有相对更高的灵活性
2. 降低应用开发的工作量和周期
2. 支持在线脚本修改和运行, 可以在运行时修改应用逻辑.
从某种角度上说， java， c#, 都是一种脚本引擎. 因为无非是编译器生成中间代码，虚拟机来执行他们。
3. 为什么使用脚本引擎
2001年的3月至5月间, 我写了这个脚本引擎. 因为需要写一个与应用无关的中间层服务平台(类似中间件), 需要有一个方案解决应用逻辑的易变性带来的问题.
当时我第一个想到的是plugin 模式. 即除了一个核心平台提供通信层，数据库访问，事务管理，用户管理等等之外， 所有的应用通过外挂DLL来加入系统.每个dll必须提供最基本的统一接口供平台调用. 比如ProcessRequest()等等, request 的数据结构
是固定的, 也就是说平台和应用的dll有一个协议, 这个协议适用任何形式的请求. 平台负责把请求分发到相关的dll, 由dll返回处理结果.
然后， 我们会提供相应的图形界面的应用开发工具让用户可以更直接更方便的开发应用。
两年后, 我在移植ISAPI 到AIX(是一个用户的变态需求)时, 发现这个想法几乎和ISAPI的架构一摸一样, 只不过ISAPI只适用于web http请求.
但是, 这个想法在当时被认为是过于丑陋. 我也同意了, 但是这种设计的perfomance会比较高.
于是, 第二个想法是用类似sql语句的方法来表达请求, 平台内置一个sql的解释器, 但是发现sql语句并不能使用所有复杂的需求, 比如复杂的计算,
复杂的数据结构, 复杂的应用逻辑. 并且不能使用平台外部的API， 比如想进行文件I/O操作， 或者想调用诸如Tuxedo之类的外部系统的功能也是不可能的。s
所以, 最终我提出了使用自己的脚本语言来描述逻辑, 并且该脚本语言可以调用外部dll中的库函数. 这样再复杂的逻辑也可以实现, 而且底层I/O操作, 数据库操作, 或者其他的底层操作可以封装在外部的dll*脚本调用, 每个dll的重用性提高了， 应用的开发者只需要关注于编写教崩就可以了, 系统的扩展性和灵活性完全实现了。 这样, 整个系统框架便完整了.
见图
4. 编译器
1. 语言设计
一开始, 没有决定使用c 语言, 因为希望语法比较简单. C 给人的感觉总是复杂. 希望是basic, 但是我一直不喜欢basic和pascal的语法, 觉得好涩, 一点不流畅. 就语言来讲, 我还是偏爱C, 怎么看怎么顺眼, 呵呵. java给人的感觉也不错, 但是那是晚辈, 无法和C相比.
我觉得, 任何语言, 最主要的也就是表达顺序, 分支和循环这三种逻辑, 以及算术, 逻辑, 关系, 赋值表达式, 所以最终的模样总是差不多的,
所以, 还是选择C.
为什么不自己创造语言呢?
1. 没有时间
2. 我自己设计的语法看起来总是和c很像:P，所以还不如用c呢.
考虑过参考mudos的源代码, 但那是个及其混乱的开源项目, 风险太大.
2. 解释器的生成器
第一个想用的的是yacc/bison.
但是看完说明书, 就觉得时间不够, 还有一个月, 需要写的东西太多.
于是找到了cocoR, 太棒了, 很直观, 给它一个语法说明, 他就给我一个workable的编译器.
我可以立刻去写代码生成可执行代码.
是不是太简单了, 呵呵.
但是这还只是个解释器, 要成为编译器, 需要生成代码.
一个月的时间, 不想去生成语法树和考虑什么预编译和中间代码优化了.
3. 生成代码
最头疼的工作来了.
必须把脚本翻译成可以执行的虚拟机指令.
1. 表达式栈
学过编译原理的同学都知道, 表达式必须用栈来分析. 没什么需要多说的, 碰到了你就会做的.
2. 浮点运算
一开始没有打算实现浮点运算. 可是, 忽然发现我们的应用多数和钱相关, 所以必须有浮点.
由于一开始没有考虑, 所以费了不少力气去支持浮点.
3. 栈机?
有两个选择, 支持栈和不支持栈.
如果虚拟机是一个"栈机"(stack machine), 那么所有临时的数据都会push到栈上. 栈机的缺点是有大量的push和pop操作。
如果你的虚拟机没有堆栈段， 那么所有临时变量都是预先分配的。这样做的优点是performance会比较好， 但是， 一个复杂的函数会占用大量内存。
因为我们需求是performance尽量高， 并且不会有非常非常复杂的逻辑， 所以， 我的虚拟机没有栈。
4. 类型转换
不支持强制类型转换, 但implicit的类型转换是必须支持的.
否则浮点和整数间的运算无法解决.
这是一个比较烦的问题, 分析表达式的时候必须判断是否需要进行类型转换, 那个操作数需要转换, 如何进行这种转换, 最终被转换出的操作数存放在新的地址上或寄存器中. 后面会讲到。
5. 虚拟机
在生成可执行代码之前, 必须设计虚拟机.
因为有了虚拟机才有指令系统, 你才知道生成什么代码.
1. 虚拟机架构的指令系统
虚拟机的设计完全模仿X86.
AX, BX, CX, DX是通用寄存器.
其他有一堆特殊用途的寄存器, 用来存放内存的段地址, 系统变量(比如IP, PSW), 等等.
见下图.
接下来是设计指令系统. 也就是有哪些指令, 指令的格式, 以及寻址方式.
指令表(部分)
| 指令名称 |
操作码 |
格式 |
说明 |
| __mov |
0x1010 |
mov op1, op2 |
传送指令 |
| __add |
0x1021 |
add op1, op2 |
加法 |
| __sub |
0x1050 |
sub op1, op2 |
减法 |
| __mul |
0x1070 |
mul op1, op2 |
乘法 |
| __div |
0x1090 |
div op1, op2 |
除法 |
| __jmp |
0x10a0 |
jmp op1 |
跳转 |
| __jz |
0x10a1 |
jz op1 |
PSW的第0位为1时跳转 |
| __jnz |
0x10a2 |
jnz op1 |
PSW的第0位为0时跳转 |
| __callpub |
0x10a3 |
callpub op1 |
准备调用基本函数 |
| __parampub |
0x10a4 |
parampub op1 |
向基本函数传送参数 |
| __endcallpub |
0x10a5 |
endcallpub op1 |
调用基本函数 |
| __not |
0x10d0 |
not op1 |
非 |
| __test |
0x10f2 |
test op1, op2, op3 |
条件测试 |
| __ret |
0x10f3 |
ret |
返回 |
| __ea |
0x10f4 |
ea op1, op2 |
取地址 |
| __mod |
0x10f0 |
mod op1, op2 |
取模 |
| __cast |
|
cast op1, op2, op3 |
类型转换 |
基本寻址方式有5种:
立即数 直接寻址 寄存器寻址 数组寻址 常量段寻址
| 14~15bit |
12~13bit |
8~b11bit |
6~7bit |
4~5bit |
0~3bit |
| 字操作还是, 字节操作,双字操作 |
间接寻址的深度 |
基本寻址方式 |
字操作还是, 字节操作,双字操作 |
间接寻址的深度 |
基本寻址方式 |
2. 实现每一个指令.
我为每个指令写了一个函数, 来运行这个指令, 参数是指令本身.
第一步, 指令预处理, 根据寻址方式把操作转成物理地址, check地址是否有效
第二步, 执行指令的任务
第三步, 做退出前的动作, 比如IP++等等
指令函数的流程图：
1． 指令预处理
预处理的作用是根据指令的寻址方式和操所数， 得到操作数的实际地址， 使指令的实现了解如何得到地址， 统一处理实际地址， 就像在当前的系统中一样处理。
函数声明： BOOL CVirtualMachine::Preprocess1(PCOMMAND cmd, int &op1mode, int &op1reflvl, unsigned char* &dest, BOOL bValidate)
函数功能： 指令预处理（单操作数指令）
参数说明：
[IN]PCOMMAND cmd - 指令内容
[OUT]int &op1mode - 操作数1的寻址方式字
[OUT]int &op1reflvl - 操作数1的间接级别
[OUT]unsigned char* &dest - 实际地址
[IN]BOOL bValidate - 是否进行地址验证
返 回 值： BOOL - 成功或失败
2． 地址验证
地址验证是用来验证操作数的实际地址是否合法， 防止不正确的内存操作导致系统崩溃。
函数声明： BOOL CVirtualMachine::ValidateAddress(unsigned char* address)
函数功能： 验证地址是否合法
参数说明： [IN]unsigned char* address - 地址
返 回 值： BOOL - 成功或失败
3． 加载脚本函数
当虚拟机执行脚本时:
第一步, 载入脚本, 也就是载入代码到代码段, 载入静态数据到数据段. 没有栈, 原因前面面已经解释
第二步, 从第一条指令开始执行, 直到结束. 也就是遇到ret指令.
第三步, 释放资源.
函数声明： BOOL CVirtualMachine::LoadFunction(CFunction *pFunc)
函数功能： 加载脚本函数
参数说明：
[IN]CFunction *pFunc - 函数指针
返 回 值： BOOL - 成功或失败
