鄢 濤, 曾 誼, 孟 飛, 劉永紅, 趙衛(wèi)東, 葉安勝

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院, 四川 成都 610106;2.成都大學(xué) 模式識別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室, 四川 成都 610106)

0 引 言

C++是一種高效率的編譯型程序設(shè)計(jì)語言，在硬件、游戲及桌面程序等領(lǐng)域的開發(fā)中有廣泛的應(yīng)用[1-2].如果源程序代碼被更改，則程序員首先需要重新編譯代碼，然后關(guān)閉正在運(yùn)行的文件，替換為編譯后的二進(jìn)制文件.對于一些簡單且經(jīng)常需要變動的業(yè)務(wù)邏輯，設(shè)計(jì)人員可以使用腳本語言來實(shí)現(xiàn)邏輯功能，這樣只需重新加載腳本文件即可實(shí)現(xiàn)服務(wù)器熱更新，從而減少維護(hù)次數(shù)，帶來更大效益.目前較為熱門的腳本語言有Lua、JavaScript等，功能都比較強(qiáng)大，但也有明顯的缺點(diǎn)，例如Lua實(shí)現(xiàn)面向?qū)ο蟊容^麻煩，而JavaScript和C++相互調(diào)用非常困難[3-7].本研究討論了如何利用編譯原理的相關(guān)知識，設(shè)計(jì)并實(shí)現(xiàn)一款可嵌入C++且支持面向?qū)ο笳Z法的腳本語言，該語言比Lua、JavaScript更貼近于C++，易學(xué)習(xí)，功能強(qiáng)大，能夠?qū)崿F(xiàn)C++項(xiàng)目熱更新，可以為C++項(xiàng)目的開發(fā)和維護(hù)減少不必要的工作量.

1 語言設(shè)計(jì)及語法分析

1.1 語言設(shè)計(jì)

語言設(shè)計(jì)中，語法的復(fù)雜程度是一個關(guān)鍵點(diǎn).如果語法很少，語言的功能則會受到影響，這會讓程序員在實(shí)現(xiàn)某些功能時消耗更多精力，而如果語法很多且復(fù)雜，就會增加解釋器設(shè)計(jì)的復(fù)雜度，同時可能影響語言的運(yùn)行效率.在本研究中，腳本語言的設(shè)計(jì)遵守以下原則：變量使用弱類型，以簡化字符串處理(字符串處理是很多業(yè)務(wù)邏輯的關(guān)鍵點(diǎn))；面向?qū)ο?，方便對?shù)據(jù)進(jìn)行抽象，也方便代碼復(fù)用；支持自動垃圾回收，避免手動管理內(nèi)存；支持閉包，這對腳本語言是非常重要的功能；其他語法盡量接近C++，以減少學(xué)習(xí)成本；能很方便實(shí)現(xiàn)與C++的相互調(diào)用；盡量不引入多余且用處不大的語法.

1.2 語法介紹

本研究依據(jù)“1.1”項(xiàng)下的設(shè)計(jì)原則設(shè)計(jì)出了Rose腳本語言.Rose語言被設(shè)計(jì)為弱類型語言，語法本身非常簡單且與C++高度相似，此處僅簡單介紹與C++的不同之處：

1)變量聲明.類似于Lua語言，直接聲明標(biāo)識符即可，不需要也不能加類型，變量命名規(guī)則與C++完全相同.

2)函數(shù)及運(yùn)算符重載.為了方便解釋器的開發(fā)，Rose語言不支持函數(shù)重載，也不支持運(yùn)算符重載.

3)參數(shù)傳遞語義.C++中，參數(shù)傳遞有引用傳遞、值傳遞與地址傳遞3種(事實(shí)上值傳遞和地址傳遞可以認(rèn)為是同一種)，Rose語言只有引用傳遞.

4)位運(yùn)算.由于Rose語言的變量設(shè)計(jì)較為特殊，所以不支持位運(yùn)算.

5)部分運(yùn)算符語義的調(diào)整.在C++中，〉〉和〈〈是2種用于位運(yùn)算的操作符， 而Rose語言不支持位運(yùn)算.此外，Rose語言中，形如“a=b;”這樣的語句，會被理解為a和b實(shí)際指向同個底層變量，而不是將b值復(fù)制給a.運(yùn)算符〉〉和〈〈在Rose語言中正好可以作為復(fù)制運(yùn)算符，例如，“a〉〉b;”表示將a值復(fù)制給b，而“a〈〈b;”則相反.

6)模板.模板本身不適合腳本語言，因此Rose語言不支持模板.

7)函數(shù)參數(shù).Rose語言中任何函數(shù)都默認(rèn)可以接收任意個參數(shù)，函數(shù)中通過argNum關(guān)鍵字獲取當(dāng)前調(diào)用的參數(shù)個數(shù)，而通過args[i]的方式獲取第i個參數(shù).

8)函數(shù)返回值.C++中的函數(shù)返回值要么為void，要么只有一個，而Rose語言可以有任意多個返回值.

Rose語言繼承了C++大多數(shù)優(yōu)秀的語法，屏蔽了其中不適合腳本語言且相對復(fù)雜的語法.理論上，Rose語言仍然是圖靈完備的編程語言，能做到以相對精簡的語法實(shí)現(xiàn)各種業(yè)務(wù)邏輯.

1.3 詞法分析器設(shè)計(jì)

詞法分析指的是讀取源代碼，并逐個掃描其中的字符，并將這些字符轉(zhuǎn)換為一系列有意義的單詞(Token).Rose語言中的Token一共有標(biāo)識符、運(yùn)算符與字面量3大類，其中字面量又分為字符串字面量和數(shù)值字面量2種.對于語法復(fù)雜的語言(如C++)，其詞法分析器可以使用lex工具來實(shí)現(xiàn)，但是Rose語言的語法遠(yuǎn)比C++簡單，即使引入了面向?qū)ο蟮奶匦?，所以Rose語言采用手工實(shí)現(xiàn)詞法分析器.

若使用手工實(shí)現(xiàn)詞法分析器，則需要理解有窮自動機(jī)的工作機(jī)制.圖1展示了一個用于識別不同Token的自動機(jī).

圖1一種有窮自動機(jī)

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;

…

};

詞法分析器設(shè)計(jì)為：

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用于預(yù)讀Token.

函數(shù)doFile是整個Lexer的核心，其實(shí)現(xiàn)并不復(fù)雜.偽碼如下：

while (true)

{

char temp = peekChar();

if (temp == -1)

break;

if (isNumber(temp))

getNumber();/*獲取數(shù)字字面量*/

else if (isIdStart(temp))

getId();/*獲取標(biāo)識符*/

else

…/*其他操作*/

}

函數(shù)getId、getNumber等是Lexer的私有函數(shù)，用于生成一個Id類或者數(shù)值類的Token.

1.4 語法分析器的設(shè)計(jì)

如果使用lex實(shí)現(xiàn)詞法分析器，那么語法分析器可以使用yacc實(shí)現(xiàn).由于本研究沒有使用lex，所以語法分析也采用手工實(shí)現(xiàn).

先設(shè)計(jì)用于表示表達(dá)式與語句等的類，由于其種類太多，所以需要設(shè)計(jì)一個抽象基類，具體為：

class SyntaxTree

{

SyntaxTree();

～SyntaxTree();

virtual eval()=0;

…

}

這個抽象基類是一切語法樹的共同基類，其中，eval函數(shù)是Rose語言能運(yùn)行的關(guān)鍵，作用是對當(dāng)前語法樹求值.事實(shí)上，一切語言的運(yùn)行過程，本質(zhì)上都是求值.語法分析器的設(shè)計(jì)如下：

class Parser

{

Parser();

～Parser();

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

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

SyntaxTree getFactor();

SyntaxTree getExpr();

SyntaxTree getState();

…

}

和詞法分析器類似，語法分析器依然可以處理文件或是字符串.函數(shù)getFactor、getExpr、getState等用于分析不同類型的語句，其中，factor指語句中的最小因子(比如一個id，也可以是由括號括起來的表達(dá)式)，expr指由若干個運(yùn)算符拼接而成的若干個因子，state指一條語句(即以分號結(jié)尾的一個expr，或if、while等語句).SyntaxTree類型遠(yuǎn)遠(yuǎn)超過這3種，任何一種運(yùn)算符都有對應(yīng)的SyntaxTree類.

語法分析使用LL(K)，這種方式最適合手工實(shí)現(xiàn)，缺點(diǎn)是效率可能會降低，不過只影響編譯效率，不會影響運(yùn)行效率.

Rose語言的核心是運(yùn)算符與表達(dá)式，以下代碼展示了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;

}

其原理是：首先獲取一個因子，然后獲取一個雙目運(yùn)算符.如果沒有獲取到，則直接返回，否則調(diào)用shift函數(shù)進(jìn)行調(diào)整(因?yàn)檫\(yùn)算符存在優(yōu)先級，所以需要調(diào)整).函數(shù)shift的實(shí)現(xiàn)如下：

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個運(yùn)算符的優(yōu)先級.如果存在優(yōu)先級差，則遞歸進(jìn)行調(diào)整，這樣能保證生成的語法樹是正確的.而make是OperatorValue類的成員函數(shù)，用于根據(jù)不同的運(yùn)算符生成不同的語法樹.

圖2展示了表達(dá)式1*(2+3)-5經(jīng)過以上語法分析后產(chǎn)生的語法樹.

圖2語法樹

2 虛擬機(jī)及相關(guān)設(shè)計(jì)

2.1 虛擬機(jī)設(shè)計(jì)

虛擬機(jī)的基本設(shè)計(jì)如下：

class VirtualMachine

{

void setFunctions(std::vector functions);

bool run();

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

Object getResult();

}

其中，F(xiàn)unction是一個類，是若干個語句的集合.由于Rose語言沒有g(shù)oto語句，所以通常情況下，這些語句是順序執(zhí)行的(if及for等也被視為語句).

首先，通過setFunctions來為虛擬機(jī)添加函數(shù)(Rose語言的設(shè)計(jì)是基于函數(shù)的),這個函數(shù)不需要用戶調(diào)用，而是由Parser調(diào)用.函數(shù)run用于執(zhí)行腳本，執(zhí)行的入口為函數(shù)main，如果沒有函數(shù)main，則run不能執(zhí)行成功.腳本執(zhí)行的原理相對簡單，依次調(diào)用每條語句的eval函數(shù)即可，它們會自動遞歸調(diào)用下屬語句.函數(shù)doFile用于加載文件，由Parser具體進(jìn)行解析.函數(shù)getResult則用于在腳本執(zhí)行完畢之后獲取運(yùn)行的結(jié)果，其中，Object是表示變量的類.只有虛擬機(jī)并不足以完美運(yùn)行腳本，而該虛擬機(jī)還缺少2個部分，即Object和儲存Object的容器.Object的設(shè)計(jì)如下：

class Object

{

bool isNum();

bool isString();

bool isTable();

void *data;

}

Rose語言本身是弱類型的.一個Object可以是數(shù)字、字符串或者表，甚至可以是函數(shù)(具體實(shí)現(xiàn)為函數(shù)指針)，其中字符串和函數(shù)最簡單，而數(shù)字則會根據(jù)實(shí)際情況選擇使用double或者大數(shù)類來表示.表可以是數(shù)組，也可以是哈希表，也可以是對象，通過[]或者.運(yùn)算符可以訪問成員，例如a[1]、a.foo()等.

用于儲存Object的容器設(shè)計(jì)也很簡單，設(shè)計(jì)成鏈表的方式即可(考慮到垃圾回收機(jī)制).

2.2 垃圾回收算法設(shè)計(jì)

變量不能像C++那樣離開作用域后馬上被析構(gòu)，這樣就帶來一個問題，即如何進(jìn)行垃圾回收.本研究設(shè)計(jì)的垃圾回收算法如下：

1)從最頂層函數(shù)調(diào)用(通常是main，但也可以是其他)開始一直到當(dāng)前調(diào)用，將其中的局部Object進(jìn)行標(biāo)記.每標(biāo)記一個Object，都遞歸標(biāo)記它的成員(如果這個Object是一個對象或表而非字符串或數(shù)值).遞歸中若遇到已經(jīng)標(biāo)記的Object則不再往下遞歸(避免死循環(huán)).

2)掃描儲存所有Object的鏈表，移除并釋放其中未被標(biāo)記的Object.這些Object是應(yīng)該被回收的，因?yàn)闊o法通過任何方式訪問到它們.

3)重新掃描2)中的鏈表，并將所有Object的標(biāo)記取消.

Rose語言的垃圾回收默認(rèn)是自動的，即每進(jìn)行一定次數(shù)的函數(shù)調(diào)用，便會進(jìn)行垃圾回收.用戶也可以設(shè)置為手動回收，使用System.gc()進(jìn)行.

3 腳本語言與C++的通信

3.1 C++調(diào)用Rose

C++調(diào)用Rose的方法相對簡單.由于虛擬機(jī)的run函數(shù)默認(rèn)是以main為入口，只需要添加一個用于調(diào)用任意函數(shù)的函數(shù)：

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