脚本引擎作为一种组件，在游戏开发甚至软件开发中具有广泛的应用。现在存在着许多像Lua、Python的脚本，还有wscript，都可以很方便地在你的程序中实现对脚本的支持。不过有时候由于特殊的原因，需要自己来实现一个脚本。这个时候就需要了解脚本引擎的结构，从而让自己的脚本更高效更强壮。

一般来说，脚本引擎都包含编译器和虚拟机两大部分。联系着编译器和虚拟机的是一种指令代码，联系着宿主程序和虚拟机的则是数据交换接口。那么，如何从0开始开发一个具有应用价值的脚本引擎呢？事实上具体的结构通常因为目标的不同而不同，而且那些需要极高速度的脚本的虚拟机通常都包含着一个JIT引擎和与操作系统相关的debugger。不过这个部分不是本文所关注的，我们讨论的是脚本引擎的通用结构。

一、指令集

虽然在代码上指令集只是一个数据结构，不过这个数据结构的好坏通常直接关系到整个脚本引擎的质量。不过事实上为了编译的方便，大部分时候还是在指令集中保留了基本数据类型和函数的框架的。在调用函数的时候，函数堆栈一般都是虚拟机自己维护的。而且如果把太多的东西都交给指令计算的话，会降低整个执行的效率。
一般来说，指令集的设计跟虚拟机维护的数据操作方式有关。当然这并不是说需要用脚本去处理整个结构的细节，而是说在指令的设计上要使用一些技巧以便把这些结构的细节统一管理。
举个例子，对于有垃圾收集跟没有垃圾收集的脚本来说，数组的内部数据是不同的：

gc：

no gc：

于是gc和非gc的指令，复制数据的指令的区别就在于：
Move Dest , Source , Type和Move Dest , Source , Bytes

当然，除了数据结构以外，数据存储的地点也是设计指令的时候需要关注的一个方面。大部分的脚本引擎在处理数据的时候，存储方式都分成两大派。第一种是通过内部的数据结构来处理，第二种是把所有的数据都放进一块连续的空间，通过内部约定的数据排列方式来处理。不过反映在指令集的语法上，又有所区别。语法的设计也是分成两派：第一种是使用临时变量，第二种是使用堆栈来存储临时空间。

完全通过临时变量来存储中间结果的好处是可以使用某些空间来存放相同的表达式的运行结果以避免重复运算带来的耗时，缺点是每一个函数在启动的时候都要占用过多的空间，而且在有gc的情况下，每一个临时变量占用的空间还需要有表示该变量类型的一个区域以便在函数退出或者着抛出异常的时候可以正确地清除堆栈的对象。这样每次都会造成过多的gc操作。

完全通过对占存储中间结果的好处是可以最小化内存占用的操作，并且可以在脚本具有gc功能的时候避免不必要的gc操作，缺点是无法充分利用代码优化所带来的好处。

因此，一般的做法都是经过代码优化后尽可能少的使用临时变量，并且利用堆栈来存储其他的中间结果。不过指令集的设计方法因人而异，特别是针对JIT的指令集更是要设计成可以方便转换到机器指令的形式。

二、编译器

根据理论上的定义，编译器就是一个可以把用一种程序语言描述的一段程序转换到另一种程序语言描述的程序。不过对于脚本引擎来说，编译器的任务就是把脚本代码转换成虚拟机可以接受的那种形式。无论是解释型的语法树还是半编译型的指令序列，前期所需要做的工作都是一致的：分析代码，列举错误，产生语法树。

一般的编译器的结构如下：

看起来好像很多东西一样，不过其实也不复杂。说一些题外话，当初看《编译原理》的时候，被书里各种各样的DFA、NFA、正则表达式还有各种各样的东西搞到晕头转向，最后实在看不下去了，就干脆把书一合，写了一个微型的编译器。当我把这个东西调试好之后，发现那本书不会的东西少了一半。接着发现其实《编译原理》也是一个编译器，告诉你如何写一个程序，输入语言的定义，输出一套编译器的源代码。当然，在本文的这种背景环境下，笔者假定读者在开发脚本引擎的时候，面对着一套已经确定的语言定义，工作是输入语言的定义，用大脑输出一套编译器的源代码。

上图定义的结构只是用于剖析一个编译器的内部结构，具体实现一般都不会按照这种方法。一个典型的方法就是把词法、语法和语义都合成一个步骤，因为虽然它们之间存在着依赖关系，但是并不需要把整段代码严格地先全部词法分析、然后全部语法分析最后在全部语义分析。不过事实上有些时候为了调试的方便也会这么实现。那么，词法分析、语法分析和语义分析分别是什么呢？下边笔者会为大家举一个简单的例子来说明，并尽量扫除实验室的味道。

假设现在需要开发一个比单纯的表达式计算器里还那么一点点的脚本引擎，支持函数调用和自定义函数操作。为了方便描述，只存在有限的若干简单数据类型。（以下语法描述并不严谨）
数据类型：integer , real
integer常数：{0-9}*
real常数：{0-9}*.{0-9}*
{x}*代表1或以上的重复
操作符：+ , - , * , / , % , := , < , > , = , and , or
函数定义：
function 函数名(参数表)[:类型];
var
很多变量
begin
很多代码
end;

参数表：[参数1:类型1 [, 参数2:类型2 ,...]]
变量：变量:类型;
代码：(表达式;|分支;|标号|跳转;|返回;)
表达式：表达式A 操作符 表达式B
表达式：(表达式)
分支：if integer表达式 else begin 很多代码 end [else begin 很多代码 end]
标号：标号名称:
跳转：goto 标号名称
返回：函数名:=表达式

那么，面对如下代码，编译器是如何工作的呢？

function Func(i : integer): integer;
var
result:integer;
begin
result:=0;
LoopHead:
result:=result+i;
i:=i-1;
if(i=0)then goto LoopHead;
Func:=result;
end;
function entry();
var
data:integer;
begin
input(data);
data:=Func((data+1)*(data-1))*3.1416;
output(data);
end;
这段代码先输入到词法分析器里。词法分析器用于读取一个字符序列，输出相应的记号序列。
事实上让我们看第一行代码

词法分析器使用一个预先制定好的状态图来分析这段代码：

让我们用另一个图来表示字符序列在这个状态图里运转的过程：

初始状态=1，每一个字符下边记录着状态转移的过程。

我们可以考察这个过程。初始状态1。当输入遇到F的时候，因为F是字母，因此转换到9。然后依次输入unction，状态依然停留在9。当输入空格的时候，空格是符号，因此状态转换到11，并且执行流后退。接着转换到初始状态。接着输入的还是空格（因为执行流后退，读入的字符会被重新处理），因此转换到13、14、1。这个过程一直进行到“;”。状态转换到1的时候，因为输入已经结束（事实上接受的是换行符，还是属于符号。不过为了讨论方便，假定如此），于是转移到结束状态16。词法分析器执行完毕。经过若干个输出后，词法分析器输出的结果如下图：

事实上词法分析器的绝大部分内容已经可以用上图的状态转移图表示出来。当我们在写词法分析器的时候，1-16这些状态通常可以实现为一个const int，每当输入的时候，就根据当前的状态以及输入的符号根据状态转移图转移到新的状态上。当状态到达结束状态（即图中的16）的时候就可以结束词法分析器的工作（听起来像是数字逻辑课程的东西，不过这个模型则是来源于离散数学）。获得的就是一段一段的具有概要类型修饰的字符串。于是数据从字符流经过词法分析器的处理就变成了记号流，送往语法分析器。

语法分析器事实上也是一个复杂的状态图。啊，不过这么说的话似乎对读者有点不负责任。一个小小的词法分析器就要在一张好大的纸上画那些花花绿绿的东西然后变成类似“低级语言”那样的判断——跳转……不过事实上语法分析器可以不这么做。大部分语言的语句的第一个记号通常都可以用来判断这个语句的类型。这也给了我们一点启发。如果我们把脚本的语句设计成可以从第一个记号判断出语句类型的话，可以带给我们很多好处。

回到我们的这个例子上。针对这个语法，我们可以制定一个简单的策略来分析这份语法。策略的详细内容在这里就不打算细说了，事实上由于这份语法过于简单，我们只需要分析出我们在语法分析的时候需要得到什么样的内容，剩下的部分很容易实现。

作为一个中间语言，在语法树的基础上，我们要做一些结构。在这个语法中，最大的结构是一个函数列表。函数装有函数名称、返回类型、参数表、变量表和语句表。语句表基本上等价于语法树。见下图：

语法分析器的任务就是扫描从词法分析器得到的记号流，填满这个大结构。对于复杂的语法而言，符号表应该做成一个链式结构并且把访问头嵌入在各个语句块中，不过就这个例子而言，每一个Name(Function , Param , Variable)都是符号表的一个部分。因此，这个语法分析器，除了生成语法树的算法以外，最重要的东西就是如何组织错误信息了。

错误信息的组织应该面向人而不是电脑。由于每一个错误信息都要有相对于代码文件的行号，因此词法分析器还应该负责往记号上记录该记号所在的行号。

举个例子。根据语法的规定，代码文件的第一个输入是函数，函数的第一个输入是’function”。如果第一个输入发现并不是”function”，则可以向外大吼“function不见啦！”，然后继续。现在就有两条路可以选择。第一：找到下一个function并继续；第二：根据语法的规定，事实上function这个关键字有没有存在对语意都是没有影响的，因此可以把当前输入的记号当成函数名处理。如果扫描到应该是函数名的地方然后去出现“(”或者“;”，那么又可以大吼“函数名不见啦！”继续出错……继续使用某种策略往下扫描……

于是这张表就慢慢的填满……一直填到表达式那里。现在需要处理的就是如何从一个记号序列生成一棵表达式树，只要做好了这一部分，语法树的工作就趋于简单化了。这个部分网上的资料很多，就不详细描述了。

记号流变成语法树输入了语义分析部分。语义分析承担的工作大部分是检查各个语句之间的类型配对是否正确。对于这个例子来说，检查的结果可以通过插入隐式转换从而使得类型配对达到正确。
让我们来看示例代码中的一个片断：data:=Func((data+1)*(data-1))*3.1416;
这个片断经由词法分析和语法分析之后被处理成如下的一棵语法树：

比较容易决定每一个节点的类型的一个方法是自下往上分析，如下图所示：

在图中我们可以很清楚地看到“类型碰撞”的地方。语义分析出了分析每一个节点的类型之外，还要处理这些问题。当然简单的方法就是强制一个类型转换到另一个类型。转换的规则需要我们自己根据实际情况总结。当然，在这种简单的情况里。integer * real需要变成real(integer)*real，而integer:=real则需要变成integer:=integer(real)，因此语义分析可以决定往语法树中插入若干节点，以便消除“类型碰撞” 。

事实上语义分析看起来这么简单的根本因素在于例子的语法是非常简单的。有的时候判断一个记号的类型是很复杂的，因为有一层一层的符号scope。而且类的继承加上函数和(预定义)操作符的重载，对判断一个函数名的实际对象也是有很大影响的。而且语义分析还应该包括检查声明部分的语义是否有碰撞。
语义分析器的任务到此就结束了。接下来就是生成可供虚拟机读取的指令了。接下来指令的例子将会为这个语法量身订造。

生成指令

面对着这个语法，我们应该怎么设计指令集呢？最好的办法是把指令集抽象的范围先决定好。要不要直接支持函数呢？指令集支持函数的一个好处是可以直接描述参数和变量。因为这个语法应该归于强类型语言，因此支持函数比不支持处理起来会方便一些。因此现在可以把那段代码翻译成类似于下面的这种结构：
function Func
integer @
integer i
var
integer result
begin
代码
end

function entry
var
integer data
begin
代码
end
执行的指令需要什么功能呢？根据语法定义，至少应该由执行操作符、条件测试、跳转和函数调用的功能。为了简单起见，笔者把指令设计成强依赖堆栈型的一套指令。
这种指令操作数是不放在运算指令上的，譬如a+b通常被翻译为：
push a
push b
+
于是模拟这一种方法，我们可以尝试翻译第一个函数：
push result
push 0
:=
LoopHead:
push result
push result
push i
+
:=
push i
push i
push 1
-
:=
push i
push 0
=
jump_false LABEL_0
jump LoopHead
LABEL_0:
push @
push result
:=
我们可以来考察一下。粗略的看起来好像没什么问题，但是实际上:=这个指令的左操作数那么设计是不合适的。譬如说最后3个指令，push @的意思是把@的内容放进堆栈，可是:=的左操作数需要的是一个引用，因此我们可以考虑增加一个push_ref的指令，如下例子所示：
push_ref @
push result
:=
于是我们再来考虑第二个函数，参考引用的问题，我们可以把entry函数编译成类似如下的指令：
push_ref data
input
push_ref data
push data
push 1
+
push data
push 1
-
*
call Func
push 3.1416
*
:=
push data
output

看起来好像匹配的还很好，那么我们就可以根据这个框架来制定所需要的指令集。
观察发现，需要的指令有push、push_ref、操作符、call、jump、jump_false、标号、系统命令这几种。关于系统命令的问题我会在虚拟机那一节描述。

于是可以开始考虑如何把语法树翻译成指令。表达式树的翻译事实上是非常简单的。叶节点push或push_ref，操作节点就是操作符或者call或者系统命令。我们可以回过头来看那个示例的表达式树，用这个规则把指令写到节点上：

接下来就是最重要的一步：后序遍历，依次输出结果。于是得到如下排列：
push_ref data
push data
push 1
+(int)
push data
push 1
-(int)
*(int)
call Func
to_real
push 3.1416
*(real)
to_int
:=(int)
表达式树就被顺利地处理成指令序列了。这个结果比刚才粗略探索的结果多出了两个指令：to_int和to_real。这两个指令分别做real->integer的转换和integer->real的转换。这样在得到一个integer和一个real并且要相乘的时候，为了可以让*指令正确地读到两个参数，于是就有to_real控制。

读者可能会注意到，操作符都跟着一个(type)的描述，需要这个属性的原因是int + int和real + real的两个+实际上是不同的，处理的过程有很大区别。但是如果因为这样把指令搞得太多会不便于管理，因此就往+指令上加参数，以便达到这个目的。

那么剩下的if 语句如何处理呢？其实我们可以为这个语句想一个策略。假设存在if expression then statement1 else statement2，我们可以大概编译出如下的指令：
push expression
jump_false LABEL_1
statement1
jump LABEL_2
LABEL_1:
statement2
LABEL_2:
那么如何产生LABEL_X这些名字呢？其实我们的目的只是想要不同的LABEL得到在函数内部不同的名字而已，这个有各种各样的方法解决。

最后只剩下一些手尾，一个完整的编译器就诞生了。
最后，给出示例程序的编译结果：
function Func
integer @
integer i
var
integer result
begin
push_ref result
push 0
:=(int)
LoopHead:
push_ref result
push result
push i
+(int)
:=(int)
push_ref i
push i
push 1
-(int)
:=(int)
push_ref i
push 0
=(int)
jump_false LABEL_0
jump LoopHead
LABEL_0:
push_ref @
push result
:=(int)
end

function entry
var
integer data
begin
push_ref data
input
push_ref data
push data
push 1
+(int)
push data
push 1
-(int)
*(int)
call Func
to_real
push 3.1416
*(real)
to_int
:=(int)
push data
output
end
这个指令集中没有被解释的一些事情，将在下一节的虚拟机中得到描述。

虚拟机

事实上思维到了这个时候，指令集还没有被最终确定下来。根本的原因在于我们目前指令的设计依赖的仅仅是脚本的语法。对于虚拟机的内部机制以及宿主程序跟脚本的数据交流接口的实现跟指令集也是有很大关系的。为什么需要数据交流呢？事实上我们在脚本里使用input和output两个函数的时候，脚本引擎本身是不可能实现这两个函数的功能的，因为这个功能跟宿主程序有很大关系，所以应该交由宿主程序完成。因此，至少我们就有要把调用的系统命令传递给宿主程序的需求。而且为了可以扩展脚本，我们还应该增加一个函数的声明：

函数头;system “命令字符串”;
因此在编译器里就面临了两种函数的调用，因为这种函数在脚本里是找不到相应的代码的。譬如以下两个函数：
function Func1(i:integer):integer;
function Func2(i:integer):integer;system “FUNCTION”;
在调用的时候，产生出来的指令大概的区别如下：
1：
push NUMBER
call Func1
2：
push NUMBER
call_system “FUNCTION”
而且因为我们没有引用参数这个特性，因此input(data);很可能会被修改成为data:=input();这样的话我们可以为这两个函数写出如下声明：
function input():integer;system “INPUT”;
function output(data:integer);system “OUTPUT”;

当然，本文并不想在代码的级别上实现一个脚本引擎，因此脚本语言的语法设计也就到此为止了，现在开始也不关心这个小改动会如何影响到编译器的实现。我们需要考虑的是，当虚拟机执行到call_system这条指令的时候，具体操作应该是什么样子的。因此，我们必须先了解虚拟机的结构，并且完成执行非交互指令的工作。

虚拟机的作用是执行指令，指令可以被描述成为一个指令流。虽然指令流会方便操作，但是我们设计出来的指令事实上是一个函数片断，并且标号这种指令实际上只是代表某个指令地址常量。因此虚拟机在读入指令的时候，应该先对指令进行处理。
我们可以很清楚地看到，编译器产生的指令的结构如下图：

这样做在每执行一条指令的时候，记录的指令指针就需要两个数据：函数和代码索引。为了方便管理，我们应该想办法把这些指令都合成为一段。事实上我们可以从MASM的汇编上得到启发，因为结构是相似的。我们可以采用以下的方案(不是唯一的方案)：

类似于这种结构，我们通过在每一小段指令序列的前后添加必要的指令，从而把指令安全地从函数列表中抽取出来，并且函数列表的每一个项目的入口指向的都是这段大的指令序列的某一个指令。

接下来，我们需要的是安排脚本语言在实际执行的过程中，数据的存储方法。在我们这个例子中，因为脚本没有动态储存的语法，所以不需要使用到“堆”，只需要“栈”。所以我们可以知道，虚拟机需要一个数据堆栈。因为脚本只有integer和real两种无结构类型，这个数据堆栈可以简化到只剩下一段内存和一个指向结尾的指针。

虽然我们的指令在存储上已经没有函数结构，但是在概念上还是存在很强的函数结构的。因此在调用call指令的时候，我们有必要作一些工作，使得在这个函数结束之后，可以回到下一条指令继续执行，并且数据不影响当前函数的参数和变量。所以我们又可以得知，虚拟机需要维护一个调用堆栈。具体方式我们仍然可以从x86的体系结构中得到启发。

x86在执行call和ret指令的时候，维护了esp和eip两个寄存器。因此我们可以通过模拟esp和eip来达到维护调用堆栈的目的。因此，简化过的堆栈如下：

最底层的就是宿主程序直接调用的函数，然后这个函数在调用另外的函数，调用堆栈就这样一个一个的网上堆，一直到函数一个一个地结束，并且这个调用堆栈被清空的时候，脚本也就结束了。
大概地，我们可以理出虚拟机的结构了：

考虑到用户还需要指定函数运行和处理系统命令的功能，因此我们可以为这一份结构图再加上一些描述，构成一幅具有实际意义的虚拟机结构图：

那虚拟机的执行流程是怎么样的呢？在虚拟机执行指令之前，用户必须先告诉虚拟既要执行的函数。因此用户就必须操作任务管理器，任务管理器就会为调用堆栈生成一个启动函数的环境。接下来就是不断地执行指令执行器。一直到指令执行器执行到call_system的时候，就发生中断，把信息传送到系统命令控制器并通知用户去读取。用户在操作系统命令控制器的时候，系统命令控制器就会操作数据堆栈把参数提取出来，并且为返回值提供空间。用户在处理完提交的系统命令之后，就继续执行指令执行器，一直到调用堆栈被清空。这个时候，指定的函数也就执行完毕了。

到了这一步，一个完整的脚本引擎的结构也就差不多了，我想读者也应该知道如何开发一个脚本引擎了。笔者在读大一曾经开发过一个脚本引擎。这个脚本引擎具有类及继承、虚函数、函数重载等面向对象元素，而且还具有连接到垃圾收集器的数组、字符串和类实例等功能，并且还加入了一个可以添加限制的模板功能。经过初步估算，整个工程的代码量有1万8千行。当然，编译器和虚拟机的结构也比本文所描述的要复杂得多。但是，无论脚本的需求如何变化，最基本的概念总是不变的。这个概念或者想法就是笔者试图通过这篇文章想要告诉大家的东西。如果读者对脚本引擎的开发有兴趣，或者对笔者所开发的那个脚本引擎有兴趣，都可以通过 vczh@163.com联系到笔者。