数学建模社区-数学中国

标题: 手把手教你写脚本引擎（二）——命令脚本 [打印本页]

作者: Vir 时间: 2012-10-17 23:09
标题: 手把手教你写脚本引擎（二）——命令脚本
本帖最后由 Vir 于 2012-10-17 23:13 编辑

手把手教你写脚本引擎（二）——命令脚本

陈梓瀚

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

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

这次要实现的是一个形式最简单的脚本。这种脚本仅有命令、标号及跳转构成，看起来就跟汇编一样，不过好是比较好读的。虽然这种脚本语言的语法非常简单，但是最基本的要素还是要有的。

作为一个脚本引擎，为了可以在各种各样的合适的宿主程序中使用，脚本本身最好不要涉及到具体的领域。当然，如果这个脚本被创建的目的仅仅是为了某个领域的话，那就无所谓了。因此，一个脚本引擎需要一个检查和运行代码的机制、运行时环境的维护以及一个功能足够使用的插件系统。一个完整的脚本引擎至少需要如下部件：

1、代码数据结构。代码的数据结构用来存放经过分析的脚本代码。事实上解释型的脚本引擎，也就是边执行边分析代码字符串的脚本引擎是比较难做，而且效率也不高的。脚本代码经过事先分析，可以检查一出一些在运行之前就能够检查的错误。而且我们把脚本的代码重新处理成一个数据结构之后，执行也变得更加容易控制。

2、运行时环境。运行时环境用于存放脚本在运行的过程中产生的数据，譬如堆栈、变量和状态信息等。对于一个已知的代码，不同的运行时环境代表不同的脚本执行流程。为了让脚本可以同时（但不一定是并发）执行，将运行时环境独立出来也就显得必要了。

3、语法分析器。语法分析器用于将代码转换成等价的代码数据结构，并在发现代码出错的时候输出合适的错误信息。

4、插件。插件是脚本与外部环境交互的途径之一。有了插件系统，我们可以为脚本引擎添加额外的、跟脚本引擎无关的功能，譬如文件操作、屏幕输入输出等。如果必要的话，插件系统可以将脚本引擎与领域信息互相隔离，系统将变得更加容易使用。

5、虚拟机。虚拟机用于执行代码并返回相应的结果。我们在使用脚本引擎时直接跟虚拟机进行交互，虚拟机则协调上述4个部件的相互协作。

在知道了这些之后，我们就可以开始开发一个基于命令的脚本引擎了。为了更加详细以及明确地讲述开发过程以及原理，在这里将构造一门简单的基于命令的语言。一门语言至少还是要有分支和循环的。但是为了简化，我们将分支和循环分解成判断与跳转。语言可以自由添加标号，标号将作为跳转的目标而出现。这门语言使用如下语法：

<值>：值可以是整数、小数、字符串或名字。
<名>：名可以是变量名或者标号等，使用字母与下划线开始，后接不定数量的字母、下划线与数字。
<名>:：名字后接冒号代表一个标号。这个标号代表着一个指令的位置，用于指定跳转目标。
goto <名>：goto用于直接跳转到一个位置继续执行。
set <名> <值>：set用于将一个值赋值给一个指定名字的变量。这个变量不存在则创建。
opcode <名> <值> <值>：opcode可以是add、minus、mul、div、idiv或mod。这6个命令将两个值进行加、减、乘、除、整除及求余，并将结果赋值给一个指定名字的变量。这个变量不存在则创建。
if <值>[ opcode <值>] goto <名>：if用于判断一个条件并在条件满足被满足的时候跳转到指定的地方。条件可以是一个值，这个值必须是整数，并且在这个值不为0的时候条件被满足。条件也可以是一个比较，这个时候opcode可以是is、is_not、less_than、greater_than、less_equal或greater_equal，分别在第一个值等于、不等于、小于、大于、小于或等于、大于或等于第二个值的时候满足条件。
exit：结束执行
<名> <值>*：如果命令名称不是上面的5种的其中一种的话，那么这个命令将被传递给插件进行执行。这个时候，命令可以有任意的参数。

在这种语法下，我们可以假设宿主程序给了我们write、writeln和read命令用于输入输出，并得到一个判断输入的数字是否质数的程序：
write "请输入一个数字："
read Number
if Number less_then 2 goto FAIL
if Number is 2 goto SUCCESS
set Divisor 2
LOOP_BEGIN:
if Number is Divisor goto SUCCESS
mod Remainder Number Divisor
if Remainder is 0 goto FAIL
add Divisor Divisor 1
goto LOOP_BEGIN
SUCCESS:
writeln Number "是质数。"
exit
FAIL:
writeln Number "不是质数。"
这个程序首先判断输入是不是小于等于2，如果不是的话则使用一种简单的方法来判断输入是不是质数。假设输入的数字为n，那么在n>2的时候，如果2到n-1中的任何一个数字能够整除n的话，那么n就不是质数了。下图是这个脚本的运行结果：

现在开始实现它。

在真正开始读脚本之前，我们需要一个在内存中表达命令的方法。命令有两种，一种是跳转标号，另一种是普通的命令。于是我们可以大概给出一个数据结构。跳转标号表用于查询一个名字所指定的命令的位置，而一个命令就由一个名字和一个参数列表构成。参数列表中的参数不仅有内容，还有类型。主要用于区分字符串和名字：

enum LexerType

{

ltString,

ltName

};

class LexerToken

{

public:

LexerType Type;

wstring Token;

};

class Command

{

public:

wstring Name;

vector<LexerToken> Parameters;

};
至于命令与标号的表示方法则用如下代码：

vector<Command> FCommands;

map<wstring , size_t> FLabels;

好了，现在让我们看看一行代码应该如何分析。由于脚本支持字符串，所以我们不能简单地使用空格来分割。如果我们遇到了“ writeln Number "是质数。"”，那么我们期望的结果是这一行代码被拆分成三个部分，分别是writeln、Number和"是质数。"。于是我们可以写一个函数，一次取出一个部分。那么我们只要一直取道换行符或者字符串结束，就能获得一行的所有部分了。

脚本代码由整数、小数、字符串、名字以及冒号组成。于是我们可以写很多类似的代码，然而格式都是int GetXXX(wchar_t*& Input);。这个函数检查Input是否由XXX开始，返回值代表XXX用掉了多少个字符，然后把Input参数往后推那么多个字符返回给你。举个例子：
wchar_t* Input=L”123vczh”;
int Chars=GetInt(Input);
这个时候Chars=3，而且Input已经往后推了三个字符，指向了”vczh”。

于是经过努力，我们就拥有了一些函数：GetInt、GetReal、GetName、GetString、GetColon、GetSpace和GetLineBreak。我们如何使用呢？首先，我们在每一次获得一个部分之前，我们都要调用GetSpace以过滤所有空格。然后就按如下顺序调用上面的5个函数：
GetColon
GetString
GetName
GetReal
GetInt
事实上只要GetInt在GetReal之下就好了。因为如果123.456被GetInt先吃掉了3个字符之后，剩下的就无法解释了。

如果全都失败（函数返回0，代表什么都没检查到）了，那么我们可以GetLineBreak。如果再次失败，那么证明这个输入的脚本就有问题了。那么报错吧。在示例代码的Lexer.h/Lexer.cpp中有一个非常类似的词法分析器用于将一行代码分段。

让我们把“ writeln Number "是质数。"”分行吧。

首先调用GetSpace，字符串指向了“writeln Number "是质数。””，然后依次调用5个函数一直到GetName成功。GetName返回7，拿到了writeln，字符串指向了“” Number "是质数。””。
然后调用GetSpace，接着仍然到了GetName成功。GetName返回6，字符串指向了“"是质数。””。
接着调用GetSpace，调用到GetString的时候就成功了。GetString返回6（注意我们用的是wchar_t），字符串指向了“”。
后面所有的调用都失败了。我们意识到字符串已经用完了，于是对这一行代码的分析就到此为止了。

到了这里，我们把所有的行都分割成一堆东西了。于是下面可以在采取一个步骤。我们首先辨别出哪一些是标号，哪一些是命令，然后填入上面的代码中提到的vector<Command>和map<wstring , size_t>中。如果我们遇到了一个标号，那么就将标号名和命令表当前存在的命令的数量加入标号表，其余的都放进命令表。于是我们在goto的时候，就可以从标号表中查到命令在命令表中的位置，从而成功跳转了。

对于上面那段检查是否质数的代码，最终的分析结果如下：
标号表：
LOOP_BEGIN: 05
SUCCESS: 10
FAIL:12
命令表：
00 write "请输入一个数字："
01 read Number
02 if Number less_then 2 goto FAIL
03 if Number is 2 goto SUCCESS
04 set Divisor 2
05 if Number is Divisor goto SUCCESS
06 mod Remainder Number Divisor
07 if Remainder is 0 goto FAIL
08 add Divisor Divisor 1
09 goto LOOP_BEGIN
10 writeln Number "是质数。"
11 exit
12 writeln Number "不是质数。"

命令表里面有13个项，每一个项都被分成了命令名和参数表两个部分。执行的时候可以通过命令名来做相应的工作。让我们来手工执行一下这个代码。

执行00，执行01，我们输入“5”。
02条件失败，03条件失败，04设置变量Divisor为2。
05条件失败，06设置Remainder=5%2=1，07条件失败，08 Divisor变成3，09跳转到05（LOOP_BEGIN）。
05条件失败，06设置Remainder=5%3=2，07条件失败，08 Divisor变成4，09跳转。
05条件失败，06设置Remainder=5%4=1，07条件失败，08 Divisor变成5，09跳转。
05条件成功，跳转到10（SUCCESS）。
10输出“是质数。”，11退出程序。

于是现在剩下了最后一个问题。write、writeln和read原本是不存在于脚本引擎的。但是脚本引擎不具有输入输出的方法也是不行的，所以我们需要实现一个插件系统。这个插件系统可以让我们在脚本引擎的外部添加命令。也就是说，我们构造了一个脚本引擎，然后在外部创建一个插件，包含write、writeln和read，然后连接他们。最后做一些手段让脚本引擎在执行到外部命令的时候将控制权转移给插件。

在这里，我们可以使用责任链模式。脚本引擎在遇到一个不认识的命令的时候，就访问第一个链接到脚本引擎的插件。这个时候插件可以返回三种结果：成功、失败或者弃权。返回成功代表命令被成功执行，脚本引擎继续往下走。返回失败代表指令被执行了，但是执行出错，这个时候脚本引擎返回错误信息并停止执行。返回弃权代表这个插件不受理这个命令，脚本引擎将这个命令传递给下一个插件。如果所有的插件都弃权的话，那么脚本引擎将返回“无效命令”并停止执行。

所以插件只需要有一个函数就行了。这个函数返回执行结果（成功、失败或弃权），参数为当前的命令以及运行时环境（保存变量的地方）。脚本引擎使用一个vector去记录所有链接的插件的指针，这样的话脚本引擎在遇到不能解释的命令的时候就可以依次访问插件了。下面是插件的示例代码：

class Plugin

{

public:

virtual PluginStatus Execute(const Command& aCommand , Environment& aEnvironment , wstring& ErrorMessage)=0;

};
vector<Plugin*> FPlugins;

命令脚本的东西就讲到这里了。接下来的一些文章将讲述如何处理高级语言，并且开发一门新的语言出来。这门语言将只支持bool、int、double、string、数组和函数。

点击这里下载本片文章的示例代码。
代码结构如下：
Lexer.h/Lexer.cpp：词法分析器
ScriptCommand.h/ScriptCommand.cpp：脚本引擎
Main.cpp：主程序
这个程序（SE_02.exe）读取一个文本文件（SE_02.txt）并执行，可以在debug文件夹下看到编译结果。

作者: zeyunma 时间: 2012-10-18 16:35

支持。

作者: Vir 时间: 2012-10-18 18:20

zeyunma 发表于 2012-10-18 16:35 & J9 j# ?5 B' ~ G/ [. }- }' A
支持。

感谢支持

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