手把手教你寫腳本引擎（四）——簡(jiǎn)單的高級(jí)語(yǔ)言（2，處理語(yǔ)法）

陳梓瀚

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

vczh@163.com

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

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

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

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

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

    2：做一個(gè)死循環(huán)不斷的計(jì)算新Status。對(duì)于某個(gè)Status我們總是能夠知道輸入什么字符跳轉(zhuǎn)到什么新的Status上去。不同的人寫出來(lái)的DFA可能會(huì)有所區(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)總是會(huì)結(jié)束。結(jié)束了之后，我們檢查Last。如果Last仍然是NULL，那么代表輸入的字符串是有問(wèn)題的。如果不是，那么我們所需要的一個(gè)記號(hào)就從Input開(kāi)始到Last結(jié)束了。如果記號(hào)的類型有需要保留的話，那么我們只需要添加一個(gè)新的代表類型的變量，在每一次修改Last的時(shí)候修改這個(gè)保存類型的變量就行了。因?yàn)橐粋€(gè)終結(jié)狀態(tài)只能代表一種類型的結(jié)束（反過(guò)來(lái)不成立，一種類型可能有好幾個(gè)終結(jié)狀態(tài)）。

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

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

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

    2：取出一個(gè)單元。一個(gè)單元指的是一個(gè)用括號(hào)包括起來(lái)的完整的表達(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á)式的語(yǔ)法不正確。我們做一個(gè)死循環(huán)一直到遇到右括號(hào)、逗號(hào)等這些結(jié)束表達(dá)式的記號(hào)為止，對(duì)于每一個(gè)輸入執(zhí)行第4步。

    4：取出一個(gè)二元操作符和一個(gè)單元。然后從當(dāng)前節(jié)點(diǎn)往父節(jié)點(diǎn)找，一直到根節(jié)點(diǎn)或者父節(jié)點(diǎn)優(yōu)先級(jí)比當(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)先級(jí)比自己小）從父節(jié)點(diǎn)脫離，整個(gè)節(jié)點(diǎn)作為操作符的左操作數(shù)，單元作為右操作數(shù)，然后用這個(gè)二元操作符接上父節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

    class ExpBase

    {

    public:

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

    };

    我們拿到了一個(gè)表達(dá)式之后，轉(zhuǎn)換成表達(dá)式樹，就會(huì)得到一個(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ù)組訪問(wèn)可以加進(jìn)二元操作符也可以不加，不過(guò)我個(gè)人還是傾向于不加的，因?yàn)楹罄m(xù)的處理邏輯有很大的不同。

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

    class ExpInvoke : public ExpBase

    {

    public:

        ExpBase* Name;

        vector<ExpBase*> Params;

    };

    所有的符合表達(dá)式就構(gòu)造完了，但是我們?nèi)匀恍枰粋€(gè)代表單一記號(hào)的表達(dá)式，譬如變量名啊數(shù)字等等。我們直接把一個(gè)記號(hào)放進(jìn)去就好了，因?yàn)橛浱?hào)里面有常量的類型信、也有變量名：

    class ExpToken : public ExpBase

    {

    public:

        Token* Content;

    };

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

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

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