手把手教你寫腳本引擎（四）——簡單的高級語言（2，處理語法）

 

陳梓瀚

華南理工大學(xué)軟件本科05級

vczh@163.com

http://www.shnenglu.com/vczh/

 

    有了全盤的計(jì)劃之后，我們必須先處理輸入的腳本，才能夠進(jìn)行下一步的工作。字符串處理方面可以參照一下三篇文章：《構(gòu)造可配置語法分析器》、《構(gòu)造正則表達(dá)式引擎》以及《如何手寫語法分析器》。作為補(bǔ)充，這里再說一說其他的辦法。

 

    首先是詞法分析器。我們?nèi)匀荒軌蚴褂谩稑?gòu)造可配置語法分析器》前半部分的方法人腦畫出一張合適的DFA，這個(gè)時(shí)候我們可以手工來實(shí)現(xiàn)。用于詞法分析器的DFA只有兩種狀態(tài)，一種是普通狀態(tài)，另一種是終結(jié)狀態(tài)。所以我們可以很機(jī)械地將DFA用C++寫出來。

 

    我們要為狀態(tài)編號。編號要連續(xù)，而且要從0開始，這樣的話C++的編譯器一般都會為switch-case的代碼生成一張表，用于快速跳轉(zhuǎn)。然后用下面的方法。

 

    1：將輸入的指針Input復(fù)制出一個(gè)副本，叫Current；給出一個(gè)同類型的指針Last，將其賦值為NULL；使用一個(gè)變量Status來記錄當(dāng)前的狀態(tài)。初始化狀態(tài)，一般為了方便我們把初始狀態(tài)編號成0。

 

    2：做一個(gè)死循環(huán)不斷的計(jì)算新Status。對于某個(gè)Status我們總是能夠知道輸入什么字符跳轉(zhuǎn)到什么新的Status上去。不同的人寫出來的DFA可能會有所區(qū)別。我們首先判斷當(dāng)前的Status是不是終結(jié)狀態(tài)，如果是的話將Current賦值給Last，然后繼續(xù)往下走。我們從Current指針拿出一個(gè)字符，然后計(jì)算新Status。如果Current不滿足要求那么結(jié)束循環(huán)，如果Current滿足要求那么改變Status并讓Current指向新的位置。

 

    3：因?yàn)樽址偸怯邢薜模赃@個(gè)循環(huán)總是會結(jié)束。結(jié)束了之后，我們檢查Last。如果Last仍然是NULL，那么代表輸入的字符串是有問題的。如果不是，那么我們所需要的一個(gè)記號就從Input開始到Last結(jié)束了。如果記號的類型有需要保留的話，那么我們只需要添加一個(gè)新的代表類型的變量，在每一次修改Last的時(shí)候修改這個(gè)保存類型的變量就行了。因?yàn)橐粋€(gè)終結(jié)狀態(tài)只能代表一種類型的結(jié)束（反過來不成立，一種類型可能有好幾個(gè)終結(jié)狀態(tài)）。

 

    然后是語法分析。一般來說，使用《如何手寫語法分析器》中描述的方法實(shí)現(xiàn)一個(gè)語法分析器的話是很容易的，但是一個(gè)主要問題就是如果一門語言很復(fù)雜，特別是操作符特別多的話，這些函數(shù)寫起來會很亂，因此每一個(gè)文法產(chǎn)生式的處理函數(shù)的命名和注釋就變得相當(dāng)重要了。為了簡化這件事情，我們還有另一種專門用來處理操作符的方法，而且是高度可配置的。為了簡化，我僅給出二元操作符和前綴操作符的處理方法。后綴操作符不常見，需要的話自己想辦法吧，在上一篇文章中的語法定義中并沒有出現(xiàn)后綴操作符。

 

    在這種方法中，我們把重點(diǎn)放在不包含修改優(yōu)先級的括號的表達(dá)式中。遇到一個(gè)用于修改優(yōu)先級的括號的時(shí)候，只要遞歸一下就好了。現(xiàn)在，我們通過詞法分析，已經(jīng)得到了很多記號，然后就使用以下的方法來生成一顆正確的語法樹：

 

    1：我們需要定義兩個(gè)指針，第一個(gè)用于保存根節(jié)點(diǎn)，第二個(gè)用于保存當(dāng)前節(jié)點(diǎn)。在分析的過程中，根節(jié)點(diǎn)會經(jīng)常變化，當(dāng)前節(jié)點(diǎn)也是。

 

    2：取出一個(gè)單元。一個(gè)單元指的是一個(gè)用括號包括起來的完整的表達(dá)式、一個(gè)函數(shù)調(diào)用、一個(gè)常量或變量和僅由前綴操作符與單元組成的整體。舉個(gè)例子，1是單元，a是單元，function(param1,param2+param3)是單元，(a*b+c*d)是單元，-(a+b)也是單元。但是-a+b就不是單元了。單元內(nèi)部可能有表達(dá)式，我們可以遞歸下去。取出單元以后，就把根節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)指向這個(gè)單元。

 

    3：一個(gè)正確的表達(dá)式總是由單元和二元操作組成的，如果在以下的步驟中出錯(cuò)的話，那么可以直接確定輸入的表達(dá)式的語法不正確。我們做一個(gè)死循環(huán)一直到遇到右括號、逗號等這些結(jié)束表達(dá)式的記號為止，對于每一個(gè)輸入執(zhí)行第4步。

 

    4：取出一個(gè)二元操作符和一個(gè)單元。然后從當(dāng)前節(jié)點(diǎn)往父節(jié)點(diǎn)找，一直到根節(jié)點(diǎn)或者父節(jié)點(diǎn)優(yōu)先級比當(dāng)前的二元操作符小的二元操作符為止。如果找到根節(jié)點(diǎn)，那么整個(gè)根節(jié)點(diǎn)將作為二元操作符的左操作數(shù)，單元作為右操作數(shù)，根節(jié)點(diǎn)更新，當(dāng)前節(jié)點(diǎn)指向單元。如果不是的話，將找到的節(jié)點(diǎn)（這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的優(yōu)先級比自己小）從父節(jié)點(diǎn)脫離，整個(gè)節(jié)點(diǎn)作為操作符的左操作數(shù)，單元作為右操作數(shù)，然后用這個(gè)二元操作符接上父節(jié)點(diǎn)。

 

    5：當(dāng)3與4進(jìn)行不下去的時(shí)候，我們就得到了一棵完整的表達(dá)式語法樹了。當(dāng)然，如果中間出錯(cuò)的話，我們應(yīng)當(dāng)輸出錯(cuò)誤信息。這個(gè)時(shí)候要不要繼續(xù)往下走就自己看著辦吧，因?yàn)檫M(jìn)行錯(cuò)誤恢復(fù)的話，接下去的錯(cuò)誤信息會很難看，就像VC++一樣。

 

    我給一個(gè)例子來說明如何處理這些事情。現(xiàn)在我們要分析1+2*3+4。這個(gè)算法將會產(chǎn)生一個(gè)正確的語法樹”1”，然后修改為正確的語法樹”1+2”，然后修改為正確的語法樹”1+2*3”，最后產(chǎn)生完整的正確的語法樹。

 

    第一步，產(chǎn)生一個(gè)單元的正確的語法樹：

    第二步，獲得一個(gè)二元操作符，并產(chǎn)生一個(gè)單元的語法樹”2”。因?yàn)楫?dāng)前節(jié)點(diǎn)往上就沒有了，所以執(zhí)行4中的第一種情況：

    第三步，獲得操作符”*”和一個(gè)單元的語法樹”3”。因?yàn)?/span>2的父節(jié)點(diǎn)的優(yōu)先級比”*”小，因此執(zhí)行4的第二種情況：

    第四步，獲得操作符”+”和一個(gè)單元的語法樹”4”。這個(gè)時(shí)候3的父節(jié)點(diǎn)的優(yōu)先級大于或等于”+”的優(yōu)先級，因此一直往上找，一直到根節(jié)點(diǎn)。因?yàn)楦?jié)點(diǎn)的優(yōu)先級仍然大于或等于”+”的優(yōu)先級，因此再也上不了了，執(zhí)行4的第一種情況：

    字符串結(jié)束了，中間也沒有出錯(cuò)，代表輸入的表達(dá)式”1+2*3+4”是正確的，我們也得到了一棵正確的語法樹。

 

    通過之前的文章與上述兩種簡單的方法的學(xué)習(xí)，我想分析一門語言的語法也就沒什么困難的了。不過分析字符串是次要的，得到語法樹才是主要的。就算用了一種猥瑣的處理字符串的辦法得到了語法樹，那也沒關(guān)系，以后有時(shí)間再改就行了。現(xiàn)在我們要討論一下語法樹的數(shù)據(jù)結(jié)構(gòu)問題。

 

    在這里我們需要大膽地使用虛函數(shù)。使用單一的一個(gè)class來表達(dá)整棵語法樹是不好的，因?yàn)槲覀兊恼Z法樹要表達(dá)unit、表達(dá)類型聲明、函數(shù)聲明、還有各種復(fù)雜的語句。類型是遞歸的，語句是遞歸的，表達(dá)式也是遞歸的。對于一組遞歸的結(jié)構(gòu)，我們要定義一個(gè)幾類，并派生出各種子類來表達(dá)各種類型的結(jié)構(gòu)。這樣做的好處是我們可以很方便地處理類型檢查、其它語義分析以及生成指令。多態(tài)在這里是相當(dāng)好用的，比省掉一點(diǎn)虛函數(shù)的空間（若干個(gè)同類型的對象只共享一張?zhí)摵瘮?shù)表）和一點(diǎn)調(diào)用的時(shí)候犧牲的速度好多了。我想用復(fù)雜的if或函數(shù)指針來代替多態(tài)估計(jì)也沒有多態(tài)快。

 

    因?yàn)轭愋汀⒈磉_(dá)式和語句的處理方式是類似的，因此我只為表達(dá)式建模。我們的表達(dá)式有四則運(yùn)算、數(shù)組訪問以及函數(shù)調(diào)用。首先我們給出一個(gè)基類ExpBase：

    class ExpBase

    {

    public:

       TypeBase* GetType(vector<ErrorMessage>& Errors);

    };

    我們拿到了一個(gè)表達(dá)式之后，轉(zhuǎn)換成表達(dá)式樹，就會得到一個(gè)ExpBase了，這個(gè)時(shí)候我們進(jìn)行類型檢查，只需要調(diào)用GetType就行了。各種不同的檢查由子類實(shí)現(xiàn)。

 

    然后我們?yōu)檫\(yùn)算符定義表達(dá)式節(jié)點(diǎn)：

    enum BinOpType

    {

        Plus,

        Minus,

        Multiply,

        Division,

        ……

    };

    enum SinOpType

    {

        Negative,

        Not,

        ……

    };

    class ExpBinOp : public ExpBase

    {

    public:

        ExpBase*  ParamA;

        ExpBase*  ParamB;

        BinOpType Operator;

    };

    class ExpSinOp : public ExpBase

    {

    public:

        ExpBase* Param;

        SinOpType Operator;

    };

    數(shù)組訪問可以加進(jìn)二元操作符也可以不加，不過我個(gè)人還是傾向于不加的，因?yàn)楹罄m(xù)的處理邏輯有很大的不同。

 

接下來是函數(shù)調(diào)用的表達(dá)式節(jié)點(diǎn)：

    class ExpInvoke : public ExpBase

    {

    public:

        ExpBase* Name;

        vector<ExpBase*> Params;

    };

 

    所有的符合表達(dá)式就構(gòu)造完了，但是我們?nèi)匀恍枰粋€(gè)代表單一記號的表達(dá)式，譬如變量名啊數(shù)字等等。我們直接把一個(gè)記號放進(jìn)去就好了，因?yàn)橛浱柪锩嬗谐Ａ康念愋托拧⒁灿凶兞棵?/span>

    class ExpToken : public ExpBase

    {

    public:

        Token* Content;

    };

 

    表達(dá)式的數(shù)據(jù)結(jié)構(gòu)就構(gòu)造完了，然后我們把剩下的類型信息與語句構(gòu)造萬，給出單元結(jié)構(gòu)以后就結(jié)束了。

 

    鑒于實(shí)習(xí)期間較忙，自己的時(shí)間不多，完整的代碼我就不給出來了。要是大家愿意的話可以去這里看Vczh Free Script 2.0 beta的語法樹結(jié)構(gòu)。雖然少了類型族，但也還是能看得。

 

    下一篇文章講述語義分析以及符號表的事情。語法樹不僅要代表源代碼，還需要附帶額外的信息，譬如表達(dá)式的類型、重載的選擇等等。這些在語法分析的時(shí)候很難一起產(chǎn)生，所以我們借助多態(tài)來簡化這個(gè)任務(wù)。