数学建模社区-数学中国

标题: 手把手教你写脚本引擎（三）——简单的高级语言（1,基本原理） [打印本页]

作者: Vir 时间: 2012-10-21 11:46
标题: 手把手教你写脚本引擎（三）——简单的高级语言（1,基本原理）

手把手教你写脚本引擎（三）——简单的高级语言（1,基本原理）

陈梓瀚

华南理工大学软件本科05级

http://www.cppblog.com/vczh/

这一篇文章开始讲述如何实现一个高级语言的脚本引擎了。由于工程量较为庞大，因此将分开几篇文章讲。学习做脚本还是要从简单的东西做起的。上一篇文章介绍的命令脚本为实现高级语言的原理做了铺垫。首先，高级语言和低级语言脚本的架构是一致的。其次，为了具有较大的优化的空间，我们将把高级语言转换成低级语言，并配合一个低级语言的脚本引擎来实现高级语言的脚本引擎。当然，习惯上，在这种情况下我们把低级语言叫『指令』。

在这个阶段，我们实现的这门语言是非惰性计算的、弱类型的、仅支持基本类型、数组和函数指针的语言。作为扩展，隐式类型转换和函数重载也将包含在这几篇文章的主题中。好了，开始介绍语法吧。

为了免去分析C语言函数指针声明的一堆麻烦问题，在这里我借用了pascal的语法。我们将构造出一门非常类似pascal的语言出来。

文件结构：
我们将实现的高级语言脚本是支持多文件的。脚本引擎总是需要外部函数的。为了方便的让宿主程序提供外部函数的声明，因此我们做成了多文件的脚本引擎。也就可以有类似C语言#include那样子的东西了。pascal有一个奇怪的注释规则：使用大括号注释。

结构如下：
unit 单元名;

uses 单元名1,单元名2,……;

type
新类型名称=类型声明;
……

var
变量名组:类型;
……

interface
公开的函数声明;

implementation
公开和非公开的函数实现（非公开函数不需要声明）
end.

对于语言本身来说，type和uses最好应该属于interface和implementation的。不过我们为了方便，姑且就这么做吧。不然的话，既不能揭示更多的原理，又给自己添麻烦。

类型声明：
类型声明有普通类型、数组类型和函数指针。
普通类型有boolean、integer、real、char和string。
数组类型的声明方法是array of 类型。
函数指针的声明方法跟函数声明一致，唯一的区别是函数指针不可出现函数名。譬如我们需要一个输入两个整数输出一个整数的函数指针，我们写：
type MyPointer=function(a,b:integer):integer;

函数声明：
pascal的函数根据有没有返回值的区别使用不同的语法。基本语法如下：
procedure 函数名(参数表)和function 函数名(参数表):返回类型
参数表的语法：[var]参数名组1:类型; [var]参数名组2:类型;……[var]参数名组n:类型。其中参数名组可以为多个用逗号隔开的参数名，也可以仅为一个参数名。其中var代表引用参数。

函数实现：
函数实现的语法由函数声明、分号、可选的变量声明、语句、分号构成。其中变量声明由var开头，后面街上多个“变量名组:类型;”构成。

语句：
一般语句：表达式、new 类型[长度]
赋值语句：变量名:=表达式
分支语句：if 布尔表达式 then 语句 [else 语句]
循环语句：
for 变量:=值 to|downto 值 do 语句
while 布尔表达式 do 语句
repeat 语句块 while 布尔表达式
复合语句：begin 语句块 end
命令语句：continue、break、exit
语句块为多个“语句;”连接而成。

表达式：
表达式由变量、操作符、常数以及函数调用构成。支持的操作符有+、-、*、div、mod、/、and、or、xor、not。其中/的返回值一定是real，div用于两个整数的整除，mod用于求余数。在这里我们修改一下pascal的语法，我们默认字符串的下标从0开始，而不是1。
数组和字符串可以用“表达式[下标]”来获得指向元素的引用。数组赋值的时候使用引用复制，字符串也使用引用复制。不过字符串修改的时候保证不影响到其他的副本，这个工作由虚拟机完成。

既然有了这个简单的语法规定，我们可以试着来写一个程序。跟上一篇文章相同，我们写一个判断一个数字是否质数的函数：
unit PrimeTest;

uses IO;{writeln和read}

interface
function IsPrime(Num:integer):boolean;

implementation

function IsPrime(Num:integer):boolean;
var i:integer;
begin
result:=true; {这是delphi设置返回值的方法，此处借用。exit用于退出函数，result变量仅仅用于设置返回值}
if Num<2 then
result:=false;
else if Num>2 then
for i:=2 to Num-1 do
if Num mod i=0 then
result:=false;
end;

end.

语法的介绍就到此结束了。在这里发一下牢骚。虽然我们知道C++很强大，但是其语法却是很不利于分析的。举个例子：
A*B;知道是什么吗？乘法？指针声明？
a<b,c>d;知道是什么吗？逗号表达式？一个类型为某模板类的变量？
因此，各位有志于分析C++语法的大大们注意了，传统的先语法分析后语义分析的方法在C++面前基本上是一点用都没有。如果你不知道上述代码中两个A代表着什么（类型还是对象），你就无法正确得到你想要的语法树，那么你就惨了。所以，要分析C++，想个办法吧语法分析和语义分析揉在一起吧。在这里我很想知道早期的gcc为什么能用yacc来搞，用yacc写出来的C/C++编译器的代码肯定很难看的，虽然写得出来。

回到我们的主题中。这个语言拥有可以递归调用的函数以及全局变量，我们需要准备一个堆栈和一个堆才可以支撑所有的内存操作。堆栈有很多种实现的方法，可以放在堆里也可以不放在堆里。这个决策将对接下去的指令集将会有一点小影响。

现在让我们考虑一下各种类型的结构。首先，boolean、integer、char和real都是实体类型，只需要那么一段数据就行了。在32位的机器上分别是1、4、1、8个字节。其次是函数指针。我们可以使用一个全局的ID指向一个函数，就跟我们拿函数去编号一样，一个函数一个编号。那么，函数指针跟integer就一致了，区别在于函数指针不能计算也不能转换类型。

接下来是字符串和数组，字符串和数组的结构都是一致的，我们可以使用引用计数来达到垃圾收集的功能。根据类型理论我们可以知道我们刚刚设计的语言是不可能存在内存泄漏的（如果所有的数据都只让脚本修改）。于是，我们可以让数组和字符串的结构如下：
[引用计数:int][数据]
当创建一个数组变量的时候，我们让数组的值为nil，让其为空，需要使用new创建一个数组。new创建的数组的引用计数是1。如果这个数组被复制的话，那么引用计数也会随之增大。当引用计数为0，也就是所有的变量都不指向这个数组的时候，数组就该释放了。而且刚刚设计的这门语言是保险的，也就是说，只要我们无法访问到这个数组，那么这个数组就一定会被释放。至于原因就留给大家思考了。

字符串的结构跟array of char是一致的，但是字符串有一个特殊的地方。我们将一个字符串赋值给另一个字符串的时候，两个字符串变量其实指向相同的空间。但是我们对其中一个字符串进行修改的时候，是不影响到另一个字符串的。我们可以在修改之前将被修改的字符串进行复制。举个例子：
a="vczh";
b=a;
这个时候字符串的引用计数是2。当我们修改b（而不是对b赋值），譬如说b[0]= 'V'的时候，我们对b进行复制。这个时候内存中就有两个引用计数为1而且内容都是vczh，但是指向的空间不同的字符串了。这个时候我们对b指向的空间进行修改的时候，a指向的空间是不变的。这种方法是经常被使用的。

接下来我们考虑堆栈的构造。堆栈是用来存放不支持闭包的语言的函数中的参数和变量的。对于我们刚刚说的这门语言来说，堆栈是相当合适的数据结构。堆栈是分段的，一个段记录的内容有参数、变量、临时信息、函数参数起始位置以及函数的执行位置。函数的执行位置用于记录当前函数在调用新函数之前所执行的指令。有了这个信息之后，我们就可以在函数返回的时候找到合适的指令继续执行了。

如果堆栈中存放字符串或者数组的话，在堆栈的一个段被销毁的同时，我们需要减少相应的字符串或数组的引用计数，并在适当的时候释放他们。那么，我们如何知道堆栈的什么地方记录着什么类型的变量呢？因为表达式也会频繁地使用堆栈的临时空间进行计算，因此类型信息有必要放在堆栈里面。如果不这样做的话，我们就要在指令集里面加入各种不同的pop指令，并在函数的很多地方使用。这两种做法各有利弊，在实现的时候需要衡量一下。

函数调用的时候需要大量更改堆栈的内容。在这里我举一个例子。已知如下代码：
function A(x:integer):integer;
begin
result:=B(x+1,x-1);
end;

function B(x,y:integer):integer;
begin
result:=x*y;
end;

我们可以假想出一个编译后的指令：
FUNCTION_A:
00 push x;
01 push 1;
02 add;
03 push x;
04 push 1;
05 sub;
06 call FUNCTION_B;
07 pushref result;
08 assign;
09 ret 1;
FUNCTION_B:
10 push x;
11 push y;
12 mul;
13 pushref result;
14 assign;
15 ret 2;

当我们执行A(5)的时候，堆栈如下：

地址内容
<以前的内容>
100 5{x}
104 0{result变量}
108 100{FUNCTION_A参数起始地址}
112 ×××{FUNCTION_A返回的时候的地址}

好了，我们一直执行指令，直到05（sub;）。这个时候堆栈上有了x+1和x-1两个数：

地址内容
<以前的内容>
100 5{x}
104 0{result变量}
108 100{FUNCTION_A参数起始地址}
112 ×××{FUNCTION_A返回的时候的地址}
116 6
120 4

现在执行06（call FUNCTION_B;），堆栈变成这样：

地址内容
<以前的内容>
100 5{x}
104 0{result变量}
108 100{FUNCTION_A参数起始地址}
112 ×××{FUNCTION_A返回的时候的地址}
116 6
120 4
124 0{新的result 变量}
128 116{FUNCTION_B参数起始地址}
132 07{FUNCTION_B返回的时候的地址，指向pushref result;指令}

然后一直执行，终于FUNCTION_B执行完了，到了15（ret 2）。

地址内容
<以前的内容>
100 5{x}
104 0{result变量}
108 100{FUNCTION_A参数起始地址}
112 ×××{FUNCTION_A返回的时候的地址}
116 6
120 4
124 24{新的result 变量，被更改}
128 116{FUNCTION_B参数起始地址}
132 07{FUNCTION_B返回的时候的地址，指向pushref result;指令}

于是执行15（ret 2）。ret 2的意思是属于FUNCTION_B的参数和变量一共有2个。虚拟机寻找有没有字符串和数组，发现没有。这时，虚拟机将132处的返回地址07拿出来，并将124处的函数返回值24保存好，最后将堆栈顶部重新指向116，并push函数返回值。这个时候堆栈如下：

地址内容
<以前的内容>
100 5{x}
104 0{result变量}
108 100{FUNCTION_A参数起始地址}
112 ×××{FUNCTION_A返回的时候的地址}
116 24{函数执行结果}

这就是一次函数调用和函数返回之后堆栈中数据的变动了。当然，我们可以加入新的指令以调整result变量、函数参数、起始地址以及返回地址的位置，让call和ret指令轻松一些，效率也提高一些。不过这是后话了。事实上上述指令中ret指令的参数是需要一个函数的参数表和变量表才能正确工作的。不同的解决方案中的ret有不同的意义。

这篇文章就到此为止了。刚刚开始实习，杂七杂八的事情比较多，因此写文章的速度会慢一些。下一批文章将讲述如何对我们构造的一门脚本语言进行语法分析以及语义分析。语法分析和语义分析主要还是用来分析代码并检查语法错误的，并附带给出一个描述语言的数据结构，用于接下来的代码生成等问题。

作者: jt202010 时间: 2012-10-21 12:06
真的太有才了

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)