可嵌入C++的脚本语言的设计与实现

鄢 涛, 曾 谊, 孟 飞, 刘永红, 赵卫东, 叶安胜

(1.成都大学 信息科学与工程学院, 四川 成都 610106;2.成都大学 模式识别与智能信息处理四川省高校重点实验室, 四川 成都 610106)

0 引 言

C++是一种高效率的编译型程序设计语言，在硬件、游戏及桌面程序等领域的开发中有广泛的应用[1-2].如果源程序代码被更改，则程序员首先需要重新编译代码，然后关闭正在运行的文件，替换为编译后的二进制文件.对于一些简单且经常需要变动的业务逻辑，设计人员可以使用脚本语言来实现逻辑功能，这样只需重新加载脚本文件即可实现服务器热更新，从而减少维护次数，带来更大效益.目前较为热门的脚本语言有Lua、JavaScript等，功能都比较强大，但也有明显的缺点，例如Lua实现面向对象比较麻烦，而JavaScript和C++相互调用非常困难[3-7].本研究讨论了如何利用编译原理的相关知识，设计并实现一款可嵌入C++且支持面向对象语法的脚本语言，该语言比Lua、JavaScript更贴近于C++，易学习，功能强大，能够实现C++项目热更新，可以为C++项目的开发和维护减少不必要的工作量.

1 语言设计及语法分析

1.1 语言设计

语言设计中，语法的复杂程度是一个关键点.如果语法很少，语言的功能则会受到影响，这会让程序员在实现某些功能时消耗更多精力，而如果语法很多且复杂，就会增加解释器设计的复杂度，同时可能影响语言的运行效率.在本研究中，脚本语言的设计遵守以下原则：变量使用弱类型，以简化字符串处理(字符串处理是很多业务逻辑的关键点)；面向对象，方便对数据进行抽象，也方便代码复用；支持自动垃圾回收，避免手动管理内存；支持闭包，这对脚本语言是非常重要的功能；其他语法尽量接近C++，以减少学习成本；能很方便实现与C++的相互调用；尽量不引入多余且用处不大的语法.

1.2 语法介绍

本研究依据“1.1”项下的设计原则设计出了Rose脚本语言.Rose语言被设计为弱类型语言，语法本身非常简单且与C++高度相似，此处仅简单介绍与C++的不同之处：

1)变量声明.类似于Lua语言，直接声明标识符即可，不需要也不能加类型，变量命名规则与C++完全相同.

2)函数及运算符重载.为了方便解释器的开发，Rose语言不支持函数重载，也不支持运算符重载.

3)参数传递语义.C++中，参数传递有引用传递、值传递与地址传递3种(事实上值传递和地址传递可以认为是同一种)，Rose语言只有引用传递.

4)位运算.由于Rose语言的变量设计较为特殊，所以不支持位运算.

5)部分运算符语义的调整.在C++中，〉〉和〈〈是2种用于位运算的操作符， 而Rose语言不支持位运算.此外，Rose语言中，形如“a=b;”这样的语句，会被理解为a和b实际指向同个底层变量，而不是将b值复制给a.运算符〉〉和〈〈在Rose语言中正好可以作为复制运算符，例如，“a〉〉b;”表示将a值复制给b，而“a〈〈b;”则相反.

6)模板.模板本身不适合脚本语言，因此Rose语言不支持模板.

7)函数参数.Rose语言中任何函数都默认可以接收任意个参数，函数中通过argNum关键字获取当前调用的参数个数，而通过args[i]的方式获取第i个参数.

8)函数返回值.C++中的函数返回值要么为void，要么只有一个，而Rose语言可以有任意多个返回值.

Rose语言继承了C++大多数优秀的语法，屏蔽了其中不适合脚本语言且相对复杂的语法.理论上，Rose语言仍然是图灵完备的编程语言，能做到以相对精简的语法实现各种业务逻辑.

1.3 词法分析器设计

词法分析指的是读取源代码，并逐个扫描其中的字符，并将这些字符转换为一系列有意义的单词(Token).Rose语言中的Token一共有标识符、运算符与字面量3大类，其中字面量又分为字符串字面量和数值字面量2种.对于语法复杂的语言(如C++)，其词法分析器可以使用lex工具来实现，但是Rose语言的语法远比C++简单，即使引入了面向对象的特性，所以Rose语言采用手工实现词法分析器.

若使用手工实现词法分析器，则需要理解有穷自动机的工作机制.图1展示了一个用于识别不同Token的自动机.

图1一种有穷自动机

Token签名如下：

class Token

{

public:

Token();

Token(Token &&t);

bool isIntLiteral()const;

bool isRealLiteral()const;

bool isStringLiteral()const;

bool isId()const;

bool isKeyWord()const;

std::string toString()const;

…

};

词法分析器设计为：

class Lexer

{

Lexer();

～Lexer();

void doFile(const std::string &fileName);

void doString(const std::string &code);

Token read();

Token peek(int i);

…

}

其中，doFile和doString用于处理源代码，read则用于获取Token，peek用于预读Token.

函数doFile是整个Lexer的核心，其实现并不复杂.伪码如下：

while (true)

{

char temp = peekChar();

if (temp == -1)

break;

if (isNumber(temp))

getNumber();/*获取数字字面量*/

else if (isIdStart(temp))

getId();/*获取标识符*/

else

…/*其他操作*/

}

函数getId、getNumber等是Lexer的私有函数，用于生成一个Id类或者数值类的Token.

1.4 语法分析器的设计

如果使用lex实现词法分析器，那么语法分析器可以使用yacc实现.由于本研究没有使用lex，所以语法分析也采用手工实现.

先设计用于表示表达式与语句等的类，由于其种类太多，所以需要设计一个抽象基类，具体为：

class SyntaxTree

{

SyntaxTree();

～SyntaxTree();

virtual eval()=0;

…

}

这个抽象基类是一切语法树的共同基类，其中，eval函数是Rose语言能运行的关键，作用是对当前语法树求值.事实上，一切语言的运行过程，本质上都是求值.语法分析器的设计如下：

class Parser

{

Parser();

～Parser();

void doFile(const std::string &file);

void doString(const std::string &code);

SyntaxTree getFactor();

SyntaxTree getExpr();

SyntaxTree getState();

…

}

和词法分析器类似，语法分析器依然可以处理文件或是字符串.函数getFactor、getExpr、getState等用于分析不同类型的语句，其中，factor指语句中的最小因子(比如一个id，也可以是由括号括起来的表达式)，expr指由若干个运算符拼接而成的若干个因子，state指一条语句(即以分号结尾的一个expr，或if、while等语句).SyntaxTree类型远远超过这3种，任何一种运算符都有对应的SyntaxTree类.

语法分析使用LL(K)，这种方式最适合手工实现，缺点是效率可能会降低，不过只影响编译效率，不会影响运行效率.

Rose语言的核心是运算符与表达式，以下代码展示了getExpr的工作原理：

SyntaxTree Parser::getExpr()

{

SyntaxTree left = getFactor();

if (left.get() == nullptr)

return left;

while (true)

{

OperatorValue *op = findOperator(data->

token.peek(0).getString());

if (op == nullptr)

break;

left = shift(op,std::move(left));

}

return left;

}

其原理是：首先获取一个因子，然后获取一个双目运算符.如果没有获取到，则直接返回，否则调用shift函数进行调整(因为运算符存在优先级，所以需要调整).函数shift的实现如下：

SyntaxTree Parser::doShift(OperatorValue *op, SyntaxTree left)

{

SyntaxTree right = getPrimary();

while (true)

{

OperatorValue *op1 = findOperator(t,comma);

if (op1&&isExpr(op, op1))

{

data->token.read();

right = doShift(op1,std::move(right));

}

else

break;

}

return op->make(std::move(left),std::move(right));

}

其中，isExpr用于判断2个运算符的优先级.如果存在优先级差，则递归进行调整，这样能保证生成的语法树是正确的.而make是OperatorValue类的成员函数，用于根据不同的运算符生成不同的语法树.

图2展示了表达式1*(2+3)-5经过以上语法分析后产生的语法树.

图2语法树

2 虚拟机及相关设计

2.1 虚拟机设计

虚拟机的基本设计如下：

class VirtualMachine

{

void setFunctions(std::vector functions);

bool run();

void doFile(const std::string &file);

Object getResult();

}

其中，Function是一个类，是若干个语句的集合.由于Rose语言没有goto语句，所以通常情况下，这些语句是顺序执行的(if及for等也被视为语句).

首先，通过setFunctions来为虚拟机添加函数(Rose语言的设计是基于函数的),这个函数不需要用户调用，而是由Parser调用.函数run用于执行脚本，执行的入口为函数main，如果没有函数main，则run不能执行成功.脚本执行的原理相对简单，依次调用每条语句的eval函数即可，它们会自动递归调用下属语句.函数doFile用于加载文件，由Parser具体进行解析.函数getResult则用于在脚本执行完毕之后获取运行的结果，其中，Object是表示变量的类.只有虚拟机并不足以完美运行脚本，而该虚拟机还缺少2个部分，即Object和储存Object的容器.Object的设计如下：

class Object

{

bool isNum();

bool isString();

bool isTable();

void *data;

}

Rose语言本身是弱类型的.一个Object可以是数字、字符串或者表，甚至可以是函数(具体实现为函数指针)，其中字符串和函数最简单，而数字则会根据实际情况选择使用double或者大数类来表示.表可以是数组，也可以是哈希表，也可以是对象，通过[]或者.运算符可以访问成员，例如a[1]、a.foo()等.

用于储存Object的容器设计也很简单，设计成链表的方式即可(考虑到垃圾回收机制).

2.2 垃圾回收算法设计

变量不能像C++那样离开作用域后马上被析构，这样就带来一个问题，即如何进行垃圾回收.本研究设计的垃圾回收算法如下：

1)从最顶层函数调用(通常是main，但也可以是其他)开始一直到当前调用，将其中的局部Object进行标记.每标记一个Object，都递归标记它的成员(如果这个Object是一个对象或表而非字符串或数值).递归中若遇到已经标记的Object则不再往下递归(避免死循环).

2)扫描储存所有Object的链表，移除并释放其中未被标记的Object.这些Object是应该被回收的，因为无法通过任何方式访问到它们.

3)重新扫描2)中的链表，并将所有Object的标记取消.

Rose语言的垃圾回收默认是自动的，即每进行一定次数的函数调用，便会进行垃圾回收.用户也可以设置为手动回收，使用System.gc()进行.

3 脚本语言与C++的通信

3.1 C++调用Rose

C++调用Rose的方法相对简单.由于虚拟机的run函数默认是以main为入口，只需要添加一个用于调用任意函数的函数：

bool call(const std::string&name,const std::vector