文法分析器

如何手寫文法分析器

陳梓瀚

華南理工大學軟體05級大學

在寫可配置的文法分析器之前，我覺得還是先說說如何手寫文法分析器好。因為對于大部分人來說，開發一個可配置的文法分析器并沒有什麼作用，反而針對某種特定的文法開發特定的文法分析器是特别有必要的。典型的有表達式電腦、某種格式化的檔案（HTML、XML等）或者是其他的複雜而且符合樹型結構的字元串。根據目前論壇的反應來看，有一些朋友們對如何開發一套自己的腳本引擎比較感興趣。等基礎的文章都寫完以後我會考慮撰寫一個系列的文章介紹如何開發自己的腳本引擎。

這篇文章會附帶一些必要的代碼以便幫助讀者們了解。為了友善，代碼使用DevC++開發。

一、定義文法

在開發文法分析器之前，有必要講一下文法的定義。這篇文章給出的是一個比較機械化的方法，掌握了這個方法之後手寫文法分析器會變成一件沒什麼挑戰性但是很麻煩的工作。因為設計起來太簡單，但是代碼很多。有些人為了連麻煩的工作也不要會去開發可配置的文法分析器。不過這裡先不管這麼多，首先給出一個比較使用的文法。

我們考慮一個經常從書上或者經常見到的例子：LISP語言。這門語言的表達式相當奇怪，操作符基本上當成函數處理，而且強迫使用者給出優先級。因為LISP的操作符是沒有優先級的。譬如(1+2)*(3+4)在LISP會被寫成(* (+ 1 2) (+ 3 4) )。

讓我們看一下這種文法的結構。括号内可以寫很多個值，第一個被約定為是函數，之後的是參數。參數的個數是不确定的。一個函數調用的結果仍然是值，這就允許表達式進行嵌套。一個複雜一點的例子：2sinxcosx在LISP内被寫成(* 2 (sin x) (cos x))。我們注意到最外層的乘法有3個參數，是以代表連乘。其次，(1)跟1的結果是一樣的。

于是我們如何規定這種表達式的文法呢？我們可以給出若幹條。為了友善我們去掉LISP語言允許的curry屬性，也就是說(+ 1 2)等價于( ( (+) 1) 2)。

1、  數字可以為值

2、  一個值可以構成參數清單，參數清單後緊接着一個值仍然是參數清單

3、  表達式可以為值，或者是括号内包含操作符或函數名外加可選的參數清單

于是我們可以使用一種形式化的方法來寫出這個表達式。首先我們可以為表達式命名，譬如表達式我們使用expression或者exp等。其次name=rule代表複雜的rule将會使用一個名字name來代替。最後，a b代表a之後緊接着b。

這樣的話，我們就可以使用一種比較簡潔的方法來表示上面提到的簡化後的LISP表達式文法：

Operator=”+”

Operator=”-“

Operator=”*”

Operator=”/”

Expression=<數字>

Expression= “(” Operator Expression Expression “)”

Expression=“(”Expression “)”

這樣寫的話覺得很煩，我們可以追加多兩種定義文法的文法：

1、A | B代表A或者B都可以，并且如果字元串被A比對成功的話将不會考慮B

2、[ A ]代表A是可以存在或者不存在的，但是盡量使其存在

于是我們可以把上面的文法改寫成如下形式：

1)       Operator=”+” | “-” | “*” | “/”

2)       Expression=<數字> | “(“ Expression “)” | “(“ Operator Expression Expression “)”

第一條文法規則說的是Operator，也就是操作符，可以是加号、減号、乘号或者除号。第二條文法規則說的是一條表達式可以隻由數字構成、一個加了括号的表達式或者一個加上了括号的操作符和兩個參數。

二、根據文法寫代碼

到了這裡，我們可以考慮一下如何通過文法組織我們的代碼了。上面的文法并沒有包含如何去除空格的文法，這個事情文法表達隻會徒增煩惱，是以我們自己解決可能會更好一點。在文法分析的時候，我們都是一點一點讀入字元串的，是以我們的函數的的形式大概如下：

·讀入字元串，傳回結果或者錯誤資訊

·如果沒有錯誤的話，則将字元指針偏移到尚未讀取的位置

·如果有錯誤的話，保持字元指針不變

好了，現在我們來看第一條文法。我們需要一個方法來檢查輸入是否由我們需要的字元串開頭，當然這裡仍然需要考慮空格的問題。我們可以寫一個函數，輸入字元指針和一個字元串。這個函數先過濾掉空格然後檢查剩下的地方是不是由指定的字元串開始的。正确的話傳回true并将輸入的字元指針往後諾到尚未讀取的地方：

bool Is(char*& Stream , const char* Text)

{

    size_t len=strlen(Text);

    char* Read=Stream;

    while(*Read==' ')Read++;

    if(strncmp(Read,Text,len)==0)

    {

        Stream=Read+len;

        return true;

    }

    else

    {

        return false;

    }          

}

代碼很短我就不解釋了。當然，有了這個函數之後我們可以很輕松地寫出一個判斷字元串是否由操作符開頭的函數：

char IsOperator(char*& Stream)

{

    if(Is(Stream,"+") || Is(Stream,"-") || Is(Stream,"*") || Is(Stream,"/"))

    {

        return Stream[-1];

    }

    else

    {

        return 0;

    }       

}

第一條文法到了這裡就結束了。然後我們考慮第二條文法。這條文法判斷一個字元串是否表達式，首先判斷一個字元串是否數字，失敗的話再檢查是否由括号打頭。是以我們需要一個判斷字元串是否由數字開頭。這裡我們先引進一個struct：

struct Expression

{

    int Result;     

    char* Error;    

    char* Start;    

}; 

這個Expression結構用于表達字元串的分析結果。Result是表達式的計算結果，Error如果非0則儲存了錯誤資訊，此時Start儲存了錯誤資訊在字元串的什麼地方被引發。有了這個Expression之後我們就可以寫出如下判斷字元串是否由數字開頭的函數了。為了友善，這個函數隻判斷非負整數。

Expression GetNumber(char*& Stream)

{

    Expression Result;

    Result.Result=0;

    Result.Error=0;

    Result.Start=0;

    bool GotNumber=false;

    char* Read=Stream;

    while(*Read==' ')Read++;

    while(true)

    {

        char c=*Read;

        if('0'<=c && c<='9')

        {

            Result.Result=Result.Result*10+(c-'0');

            GotNumber=true;

            Read++;

        }

        else

        {

            break;

        }   

    }

    if(GotNumber)

    {

        Stream=Read;

    }

    else   

    {

        Result.Error="這裡需要數字";

        Result.Start=Read;

    }   

    return Result;

}

這個函數仍然會過濾掉字元串開頭的空格。如果成功的話，也就是Result.Error==0的時候，參數Stream會被偏移到已經分析的數字後面。

讓我們看一看第二條文法接下來的部分：“(“ Expression “)” | “(“ Operator Expression Expression “)”。我們注意到，這兩個部分都是使用括号開始和結束的，是以在寫代碼的時候可以把它們寫在一起，隻把中間的部分分開。這種方法在課本中通常被稱為合并字首。于是我們可以寫一個GetExpression函數。這個函數首先判斷字元串是不是由數字開頭，否則的話看一看是否由括号開頭。如果是括号開頭的話，那麼檢查接下來的是Operator還是一個Expression。如果是Expression則到此結束，如果是Operator的話還要再輸入兩個Expression。然後判斷一下是不是由右括号結束字元串：

Expression GetExpression(char*& Stream)

{

    char* Read=Stream;

    Expression Result=GetNumber(Read);

    if(Result.Error)

    {

        if(Is(Read,"("))

        {

            Result.Error=0;

            char Operator=0;

            if(Operator=IsOperator(Read))

            {

                Expression Left=GetExpression(Read);

                if(Left.Error) return Left;

                char* RightRead=Read;

                Expression Right=GetExpression(Read);

                if(Right.Error) return Right;

                switch(Operator)

                {

                    case '+':

                        Result.Result=Left.Result+Right.Result;

                        break;

                    case '-':

                        Result.Result=Left.Result-Right.Result;

                        break;

                    case '*':

                        Result.Result=Left.Result*Right.Result;

                        break;

                    case '/':

                        if(Right.Result==0)

                        {

                            Result.Error="除錯";

                            Result.Start=RightRead;

                        }

                        else

                        {   

                            Result.Result=Left.Result/Right.Result;

                        }   

                        break;

                    default:

                        Result.Error="未知操作符";

                        Result.Start=Read;

                        return Result;

                }   

            }

            else

            {

                Result=GetExpression(Read);

                if(Result.Error) return Result;

            }

            if(!Is(Read,")"))

            {

                Result.Error="此處缺少右括号";

                Result.Start=Read;

            }  

        }   

    }

    if(Result.Error==0)

    {

        Stream=Read;

    }   

    return Result;          

}

到了這裡表達式的分析就完成了，我們得到了一個工具：GetExpression。我們可以将一個字元串輸入GetExpression，然後看看傳回了什麼。當然，有可能傳回計算結果，也有可能傳回錯誤資訊以及錯誤位置。為了解釋如何使用GetExpression，我也寫了一個main函數：

int main(int argc, char *argv[])

{

    char Buffer[1000];

    cout<<"輸入一個表達式："<<ends;

    gets(Buffer);

    {

        char* Stream=Buffer;

        Expression Result=GetExpression(Stream);

        if(Result.Error)

        {

            cout<<"發生錯誤"<<endl;

            cout<<"位置："<<Result.Start<<endl;

            cout<<"資訊："<<Result.Error<<endl;

        }

        else

        {

            cout<<"結果："<<Result.Result<<endl;

        }       

    }   

    system("PAUSE");  

    return 0;

}

這個函數輸入一個字元串，然後計算結果或者輸出錯誤資訊。當然，錯誤的檢查時不完全的，因為GetExpression隻負責檢查字首，至于剩下的部分是什麼是不管的。是以實際上還要檢查一下剩下的字元是不是全都是空格，不是的話就要自己報錯了。完整的代碼見附帶的檔案夾Code_1_LISP。

三、處理左遞歸

上面的方法其實還是不完全的。我們有時候會遇到一些自己産生自己的文法。譬如我們在表達一個使用逗号隔開的數字清單的時候，有如下兩種寫法：

1）  List=<數字> [“,” List]

2）  List=[List “,”]<數字>

這兩種寫法所産生的效果是一緻的，但是我們如果按照第二種方法直接寫出代碼的話就會陷入無限循環。這種自己導出自己的特征就叫做左遞歸了。像這種情況左遞歸還是能避免的，但并不是所有的最遞歸都能直接避免的。雖然不能避免，但是仍然有一個通用的辦法來解決，隻不過或破壞一點點美感。

分析了LISP的表達式之後，我們進入下一個例子：分析四則運算式子。我們的四則運算式子由加減乘除、括号和數字構成。為了友善不考慮正負。使用文法規則是可以表達出操作符的優先級的。下面就讓我們來思考如何構造四則運算式子的文法。

我們将一個表達式定義為Expression。首先，數字可以成為Expression，其次，加了括号的Expression仍然是Expression：

Expression=<數字> | “(“ Expression “)”

但是這裡有一個問題，操作符号的優先級并不能當純通過寫Expression=Expression “+” Expression來完成。是以我們進入進一步的思考。

我們考慮一下乘除先于加減背後的本質是什麼。看一下一條比較長的表達式：

1*2*3+4*5*6+7*8*9

我們在計算的時候會把他們分成三個部分：1*2*3、4*5*6、7*8*9，分别計算出結果，然後相加。如果我們可以把僅僅由乘除組成的表達式的文法寫出來，那麼寫出四則運算式子的文法也就有希望了。事實是可以的。于是我們要對之前的結果做一下調整。無論是數字或者是括号包含的表達式都不可能因為在旁邊添加其他操作符而對優先級有所影響，是以我們抽象出一個類型叫Term：

Term=<數字> | “(“ Expr “)”

然後我們就可以寫一條隻用乘除構成的表達式的文法了：

Factor=Term | Factor “*” Term | Factor “/” Term

最後，我們可以寫出一條隻用加減和Factor構成的表達式的文法：

Exp=Factor | Exp “+” Factor | Exp “-“ Factor

到了這裡表達式的文法就大功告成了。上面的三條文法中的Exp就是四則運算的文法了。

我們注意到Exp和Factor都是左遞歸的。在這裡我介紹一種消除左遞歸的方法。我們考察一下文法Factor=Term | Factor “*” Term這一條。為了形象的表達出什麼是Factor，我們反過來可以考察一下Factor究竟可以産生出什麼樣的東西來。

一個Factor可以産生出一個Term。然後，一個Factor可以變成Factor “*” Term。如果我們把Factor “*” Term中的Factor替換成已知的結果的話，那麼我們可以得到一個結論：一個Factor可以産生出Term “*” Term。同理，我們又可以知道一個Factor可以産生出Term “*” Term “*” Term，為Factor可以産生出Term “*” Term。于是我們大概可以猜出解決左遞歸的方法：

假設存在如下表達式：

A=B1

…

A=Bn

A=A C1

…

A=A Cn

我們可以将這個文法修改為如下形式：

A’=C1 | C2 | … | Cn [A’]

A=(B1 | B2 | … | Bn) [A’]

我們可以看到現在的A沒有發生變化，但是新的文法已經不存在左遞歸了。我們為了簡化表達，可以引進一種新的文法：我們讓X*代表X、X、X等等隻由A組成的字元串或者空字元串，那麼上面這個文法就可以被修改成A=(B1 | B2 | … | Bn) (C1 | C2 | … | Cn)*了。

于是，我們重新寫一下四則運算式子的文法：

1)       Term=<數字> | “(“ Exp “)”

2)       Factor = Term ( ( “*” | “/” ) Term) *

3)       Exp = Factor ( ( “+” | “-“ ) Factor) *

我在這裡仍然要寫出四則運算分析的代碼。但是這一次我不求值了，這個新的程式将把四則運算式子轉換成等價的LISP表達式然後輸出。

代碼的結構是這樣的。首先，仍然會存在上文中的函數Is。其次，表達式Expression的結構将被我替換成一個遞歸的二叉樹，異常資訊使用C++的異常處理機制實作。

在這裡貼出GetTerm和GetFactor的代碼，GetExp與GetFactor結構相似。

Expression* GetTerm(char*& Stream);

Expression* GetFactor(char*& Stream);

Expression* GetExp(char*& Stream);

Expression* GetTerm(char*& Stream)

{

    try

    {

        return GetNumber(Stream);

    }   

    catch(Exception& e)

    {

        char* Read=Stream;

        if(Is(Read,"("))

        {

            Expression* Result=GetExp(Read);

            if(Is(Read,")"))

            {

                Stream=Read;

                return Result;

            }

            else

            {

                delete Result;

                throw Exception(Stream,"此處需要右括号");

            }       

        }   

        else

        {

            throw e;

        }   

    }   

}   

Expression* GetFactor(char*& Stream)

{

    char* Read=Stream;

    Expression* Result=GetTerm(Read);

    while(true)

    {

        char Operator=0;

        if(Is(Read,"*"))

            Operator='*';

        else if(Is(Read,"/"))

            Operator='/';

        else

            break;

        if(Operator)

        {

            try

            {

                Result=new Expression(Operator,Result,GetTerm(Read));

            }

            catch(Exception& e)

            {

                delete Result;

                throw e;

            }       

        }   

    }

    Stream=Read;

    return Result;   

} 

完整的代碼見檔案夾Code_2_EXP2LISP。

這份代碼跟分析LISP表達式代碼不同的是這裡展示了給出樹形結構而不僅僅是計算出結果的代碼。這兩種方法的差別僅僅是獲得了資料之後如何處理的問題，但是代表了兩種經常需要處理的任務。

四、尾聲

這篇文章相比起以前的兩篇正規表達式來的确是短了不少。遞歸下降法是一種适合人腦使用而不是電腦使用的方法。這種方法非常好用，是以大部分編譯原理的教科書都會專門使用一個章節來說明遞歸下降的實作、局限性以及遇到的問題的解決方法。這篇文章不是理論文章，是以有一些本文沒闡述到的問題可以通過人的智商來解決。

在文法處理過程中遇到的一個問題是出現異常的時候如何組織錯誤資訊。在寫編譯器的時候我們并不能通過異常處理來向外傳播異常資訊，因為編譯器需要輸出許多異常。不過大部分分析工作還是僅僅需要第一個異常資訊的。

第二個常見的問題是如何在發生異常的時候處理分析結果。在本文的第二個例子裡面，在抛出異常之前總是會手動delete掉已經産生的指針。其實這樣做是很容易漏掉一些處理進而造成記憶體洩漏的，如果讀者使用C++的話，那麼我推薦使用STL的auto_ptr或者Boost的smart_ptr，或者幹脆自己寫吧。樹型結構的文檔通常不會有循環引用的問題，是以在這種情況下無論如何産生文檔或者産生異常，使用auto_ptr或者smart_ptr都是沒有問題的。

第三個問題是寫不出文法。這個問題沒有什麼好的辦法，隻有通過練習來解決了。或者幹脆做一個YACC出來，經過一次非常深入的思考也能獲得很多經驗。就像寫出一手好的正規表達式的人，要麼就是練習了很多次，要麼就是寫過正規表達式引擎一樣。不過這種方法比較耗時間，不是非常有興趣的讀者們還是不要這麼做的好。

最後說明一下，本文使用四則運算式子作為例子僅僅是為了友善。實際上分析四則運算獅子已經有各種各樣的好方法了。但是讀者們将來卻很難遇到分析四則運算的工作，而是分析各種各樣複雜字元串的工作。這個時候遞歸下降法起得作用是在代碼還沒開始寫之前，就已經把思考不慎密導緻的bug都消除了大半了。因為設計文法的過程很容易讓人深入的思考問題。遞歸下降法能夠用最快的速度從文法産生出代碼，但是還是要根據實際情況調整細節。