可嵌入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