如何手寫(xiě)語(yǔ)法分析器
陳梓瀚
華南理工大學(xué)軟件05級本科
在寫(xiě)可配置的語(yǔ)法分析器之前，我覺(jué)得還是先說(shuō)說(shuō)如何手寫(xiě)語(yǔ)法分析器好。因為對于大部分人來(lái)說(shuō)，開(kāi)發(fā)一個(gè)可配置的語(yǔ)法分析器并沒(méi)有什么作用，反而針對某種特定的語(yǔ)法開(kāi)發(fā)特定的語(yǔ)法分析器是特別有必要的。典型的有表達式計算器、某種格式化的文件（HTML、XML等）或者是其他的復雜而且符合樹(shù)型結構的字符串。根據目前論壇的反應來(lái)看，有一些朋友們對如何開(kāi)發(fā)一套自己的腳本引擎比較感興趣。等基礎的文章都寫(xiě)完以后我會(huì )考慮撰寫(xiě)一個(gè)系列的文章介紹如何開(kāi)發(fā)自己的腳本引擎。
這篇文章會(huì )附帶一些必要的代碼以便幫助讀者們理解。為了方便，代碼使用DevC++開(kāi)發(fā)。
一、定義語(yǔ)法
在開(kāi)發(fā)語(yǔ)法分析器之前，有必要講一下語(yǔ)法的定義。這篇文章給出的是一個(gè)比較機械化的方法，掌握了這個(gè)方法之后手寫(xiě)語(yǔ)法分析器會(huì )變成一件沒(méi)什么挑戰性但是很麻煩的工作。因為設計起來(lái)太簡(jiǎn)單，但是代碼很多。有些人為了連麻煩的工作也不要會(huì )去開(kāi)發(fā)可配置的語(yǔ)法分析器。不過(guò)這里先不管這么多，首先給出一個(gè)比較使用的語(yǔ)法。
我們考慮一個(gè)經(jīng)常從書(shū)上或者經(jīng)常見(jiàn)到的例子：LISP語(yǔ)言。這門(mén)語(yǔ)言的表達式相當奇怪，操作符基本上當成函數處理，而且強迫用戶(hù)給出優(yōu)先級。因為LISP的操作符是沒(méi)有優(yōu)先級的。譬如(1+2)*(3+4)在LISP會(huì )被寫(xiě)成(* (+ 1 2) (+ 3 4) )。
讓我們看一下這種語(yǔ)法的結構。括號內可以寫(xiě)很多個(gè)值，第一個(gè)被約定為是函數，之后的是參數。參數的個(gè)數是不確定的。一個(gè)函數調用的結果仍然是值，這就允許表達式進(jìn)行嵌套。一個(gè)復雜一點(diǎn)的例子：2sinxcosx在LISP內被寫(xiě)成(* 2 (sin x) (cos x))。我們注意到最外層的乘法有3個(gè)參數，因此代表連乘。其次，(1)跟1的結果是一樣的。
于是我們如何規定這種表達式的語(yǔ)法呢？我們可以給出若干條。為了方便我們去掉LISP語(yǔ)言允許的curry屬性，也就是說(shuō)(+ 1 2)等價(jià)于( ( (+) 1) 2)。
1、 數字可以為值
2、 一個(gè)值可以構成參數列表，參數列表后緊接著(zhù)一個(gè)值仍然是參數列表
3、 表達式可以為值，或者是括號內包含操作符或函數名外加可選的參數列表
于是我們可以使用一種形式化的方法來(lái)寫(xiě)出這個(gè)表達式。首先我們可以為表達式命名，譬如表達式我們使用expression或者exp等。其次name=rule代表復雜的rule將會(huì )使用一個(gè)名字name來(lái)代替。最后，a b代表a之后緊接著(zhù)b。
這樣的話(huà)，我們就可以使用一種比較簡(jiǎn)潔的方法來(lái)表示上面提到的簡(jiǎn)化后的LISP表達式語(yǔ)法：
Operator=”+”
Operator=”-“
Operator=”*”
Operator=”/”
Expression=<數字>
Expression= “(” Operator Expression Expression “)”
Expression=“(”Expression “)”
這樣寫(xiě)的話(huà)覺(jué)得很煩，我們可以追加多兩種定義語(yǔ)法的語(yǔ)法：
1、A | B代表A或者B都可以，并且如果字符串被A匹配成功的話(huà)將不會(huì )考慮B
2、[ A ]代表A是可以存在或者不存在的，但是盡量使其存在
于是我們可以把上面的語(yǔ)法改寫(xiě)成如下形式：
1) Operator=”+” | “-” | “*” | “/”
2) Expression=<數字> | “(“ Expression “)” | “(“ Operator Expression Expression “)”
第一條語(yǔ)法規則說(shuō)的是Operator，也就是操作符，可以是加號、減號、乘號或者除號。第二條語(yǔ)法規則說(shuō)的是一條表達式可以只由數字構成、一個(gè)加了括號的表達式或者一個(gè)加上了括號的操作符和兩個(gè)參數。
二、根據語(yǔ)法寫(xiě)代碼
到了這里，我們可以考慮一下如何通過(guò)語(yǔ)法組織我們的代碼了。上面的語(yǔ)法并沒(méi)有包含如何去除空格的語(yǔ)法，這個(gè)事情語(yǔ)法表達只會(huì )徒增煩惱，因此我們自己解決可能會(huì )更好一點(diǎn)。在語(yǔ)法分析的時(shí)候，我們都是一點(diǎn)一點(diǎn)讀入字符串的，因此我們的函數的的形式大概如下：
·讀入字符串，返回結果或者錯誤信息
·如果沒(méi)有錯誤的話(huà)，則將字符指針偏移到尚未讀取的位置
·如果有錯誤的話(huà)，保持字符指針不變
好了，現在我們來(lái)看第一條語(yǔ)法。我們需要一個(gè)方法來(lái)檢查輸入是否由我們需要的字符串開(kāi)頭，當然這里仍然需要考慮空格的問(wèn)題。我們可以寫(xiě)一個(gè)函數，輸入字符指針和一個(gè)字符串。這個(gè)函數先過(guò)濾掉空格然后檢查剩下的地方是不是由指定的字符串開(kāi)始的。正確的話(huà)返回true并將輸入的字符指針往后諾到尚未讀取的地方：
/*
檢查Stream的前綴是否Text
是返回true并將Stream偏移strlen(Text)個(gè)字符
否則返回false
此函數會(huì )過(guò)濾Stream開(kāi)頭的空格
*/
bool Is(char*& Stream , const char* Text)
{
size_t len=strlen(Text);
/*保存參數*/
char* Read=Stream;
/*過(guò)濾空格*/
while(*Read==' ')Read++;
if(strncmp(Read,Text,len)==0)
{
Stream=Read+len;
return true;
}
else
{
return false;
}
}
代碼很短我就不解釋了。當然，有了這個(gè)函數之后我們可以很輕松地寫(xiě)出一個(gè)判斷字符串是否由操作符開(kāi)頭的函數：
/*
檢查Stream是否操作符
是的話(huà)返回操作符的字符并將Stream偏移至操作符之后
否則返回
*/
char IsOperator(char*& Stream)
{
/*A||B操作符的特性是如果A==true則不對B求值
所以表達式會(huì )在一個(gè)檢查成功后停下來(lái)
*/
if(Is(Stream,"+") || Is(Stream,"-") || Is(Stream,"*") || Is(Stream,"/"))
{
/*此時(shí)操作符已經(jīng)被越過(guò)，所以返回Read[-1]*/
return Stream[-1];
}
else
{
return 0;
}
}
第一條語(yǔ)法到了這里就結束了。然后我們考慮第二條語(yǔ)法。這條語(yǔ)法判斷一個(gè)字符串是否表達式，首先判斷一個(gè)字符串是否數字，失敗的話(huà)再檢查是否由括號打頭。因此我們需要一個(gè)判斷字符串是否由數字開(kāi)頭。這里我們先引進(jìn)一個(gè)struct：
/*表達式分析結果*/
struct Expression
{
int Result; /*表達式結果*/
char* Error; /*錯誤信息，沒(méi)有錯誤則為*/
char* Start; /*錯誤的位置*/
};
這個(gè)Expression結構用于表達字符串的分析結果。Result是表達式的計算結果，Error如果非0則保存了錯誤信息，此時(shí)Start保存了錯誤信息在字符串的什么地方被引發(fā)。有了這個(gè)Expression之后我們就可以寫(xiě)出如下判斷字符串是否由數字開(kāi)頭的函數了。為了方便，這個(gè)函數只判斷非負整數。
/*
檢查Stream是否數字，是的話(huà)則將Stream偏移到數字之后
*/
Expression GetNumber(char*& Stream)
{
/*初始化結果*/
Expression Result;
Result.Result=0;
Result.Error=0;
Result.Start=0;
bool GotNumber=false;
/*保存參數*/
char* Read=Stream;
/*過(guò)濾空格*/
while(*Read==' ')Read++;
while(true)
{
/*讀入一個(gè)字符并將Read偏移一個(gè)字符*/
char c=*Read;
/*檢查字符是否為數字*/
if('0'<=c && c<='9')
{
/*把結果添加進(jìn)Result，進(jìn)行進(jìn)位*/
Result.Result=Result.Result*10+(c-'0');
GotNumber=true;
Read++;
}
else
{
break;
}
}
if(GotNumber)
{
Stream=Read;
}
else
{
Result.Error="這里需要數字";
Result.Start=Read;
}
return Result;
}
這個(gè)函數仍然會(huì )過(guò)濾掉字符串開(kāi)頭的空格。如果成功的話(huà)，也就是Result.Error==0的時(shí)候，參數Stream會(huì )被偏移到已經(jīng)分析的數字后面。
讓我們看一看第二條語(yǔ)法接下來(lái)的部分：“(“ Expression “)” | “(“ Operator Expression Expression “)”。我們注意到，這兩個(gè)部分都是使用括號開(kāi)始和結束的，因此在寫(xiě)代碼的時(shí)候可以把它們寫(xiě)在一起，只把中間的部分分開(kāi)。這種方法在課本中通常被稱(chēng)為合并前綴。于是我們可以寫(xiě)一個(gè)GetExpression函數。這個(gè)函數首先判斷字符串是不是由數字開(kāi)頭，否則的話(huà)看一看是否由括號開(kāi)頭。如果是括號開(kāi)頭的話(huà)，那么檢查接下來(lái)的是Operator還是一個(gè)Expression。如果是Expression則到此結束，如果是Operator的話(huà)還要再輸入兩個(gè)Expression。然后判斷一下是不是由右括號結束字符串：
/*檢查Stream是否表達式，是的話(huà)則將Stream偏移至表達式之后*/
Expression GetExpression(char*& Stream)
{
/*保存參數*/
char* Read=Stream;
/*檢查是否數字*/
Expression Result=GetNumber(Read);
if(Result.Error)
{
if(Is(Read,"("))
{
/*不是數字而是左括號，則將Result的Error清*/
Result.Error=0;
char Operator=0;
/*檢查是否操作符*/
if(Operator=IsOperator(Read))
{
/*獲得左參數。如果參數獲取失敗會(huì )直接返回*/
Expression Left=GetExpression(Read);
if(Left.Error) return Left;
/*保存當前的Read變量，以便在右參數出錯的情況下正確指出錯誤的地點(diǎn)*/
char* RightRead=Read;
/*獲得右參數。如果參數獲取失敗會(huì )直接返回*/
Expression Right=GetExpression(Read);
if(Right.Error) return Right;
/*根據操作進(jìn)行計算*/
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="未知操作符";/*不可能發(fā)生，執行到這里則證明其他部分有bug*/
Result.Start=Read;
return Result;
}
}
else
{
/*不是操作符則嘗試獲得表達式*/
Result=GetExpression(Read);
/*獲取失敗則直接返回*/
if(Result.Error) return Result;
}
/*檢查是否有配對的右括號*/
if(!Is(Read,")"))
{
Result.Error="此處缺少右括號";
Result.Start=Read;
}
}
}
/*如果沒(méi)有出錯則更新Stream的位置*/
if(Result.Error==0)
{
Stream=Read;
}
return Result;
}
到了這里表達式的分析就完成了，我們得到了一個(gè)工具：GetExpression。我們可以將一個(gè)字符串輸入GetExpression，然后看看返回了什么。當然，有可能返回計算結果，也有可能返回錯誤信息以及錯誤位置。為了解釋如何使用GetExpression，我也寫(xiě)了一個(gè)main函數：
int main(int argc, char *argv[])
{
/*聲明一個(gè)長(cháng)度的字符串緩沖區，可能有溢出的危險，此處不考慮*/
char Buffer[1000];
cout<<"輸入一個(gè)表達式："<<ends;
gets(Buffer);
{
char* Stream=Buffer;
Expression Result=GetExpression(Stream);
if(Result.Error)
{
cout<<"發(fā)生錯誤"<<endl;
cout<<"位置："<<Result.Start<<endl;
cout<<"信息："<<Result.Error<<endl;
}
else
{
cout<<"結果："<<Result.Result<<endl;
}
}
system("PAUSE");
return 0;
}
這個(gè)函數輸入一個(gè)字符串，然后計算結果或者輸出錯誤信息。當然，錯誤的檢查時(shí)不完全的，因為GetExpression只負責檢查前綴，至于剩下的部分是什么是不管的。因此實(shí)際上還要檢查一下剩下的字符是不是全都是空格，不是的話(huà)就要自己報錯了。完整的代碼見(jiàn)附帶的文件夾Code_1_LISP。
三、處理左遞歸
上面的方法其實(shí)還是不完全的。我們有時(shí)候會(huì )遇到一些自己產(chǎn)生自己的語(yǔ)法。譬如我們在表達一個(gè)使用逗號隔開(kāi)的數字列表的時(shí)候，有如下兩種寫(xiě)法：
1） List=<數字> [“,” List]
2） List=[List “,”]<數字>
這兩種寫(xiě)法所產(chǎn)生的效果是一致的，但是我們如果按照第二種方法直接寫(xiě)出代碼的話(huà)就會(huì )陷入無(wú)限循環(huán)。這種自己導出自己的特征就叫做左遞歸了。像這種情況左遞歸還是能避免的，但并不是所有的最遞歸都能直接避免的。雖然不能避免，但是仍然有一個(gè)通用的辦法來(lái)解決，只不過(guò)或破壞一點(diǎn)點(diǎn)美感。
分析了LISP的表達式之后，我們進(jìn)入下一個(gè)例子：分析四則運算式子。我們的四則運算式子由加減乘除、括號和數字構成。為了方便不考慮正負。使用語(yǔ)法規則是可以表達出操作符的優(yōu)先級的。下面就讓我們來(lái)思考如何構造四則運算式子的語(yǔ)法。
我們將一個(gè)表達式定義為Expression。首先，數字可以成為Expression，其次，加了括號的Expression仍然是Expression：
Expression=<數字> | “(“ Expression “)”
但是這里有一個(gè)問(wèn)題，操作符號的優(yōu)先級并不能當純通過(guò)寫(xiě)Expression=Expression “+” Expression來(lái)完成。因此我們進(jìn)入進(jìn)一步的思考。
我們考慮一下乘除先于加減背后的本質(zhì)是什么?？匆幌乱粭l比較長(cháng)的表達式：
1*2*3+4*5*6+7*8*9
我們在計算的時(shí)候會(huì )把他們分成三個(gè)部分：1*2*3、4*5*6、7*8*9，分別計算出結果，然后相加。如果我們可以把僅僅由乘除組成的表達式的語(yǔ)法寫(xiě)出來(lái)，那么寫(xiě)出四則運算式子的語(yǔ)法也就有希望了。事實(shí)是可以的。于是我們要對之前的結果做一下調整。無(wú)論是數字或者是括號包含的表達式都不可能因為在旁邊添加其他操作符而對優(yōu)先級有所影響，因此我們抽象出一個(gè)類(lèi)型叫Term：
Term=<數字> | “(“ Expr “)”
然后我們就可以寫(xiě)一條只用乘除構成的表達式的語(yǔ)法了：
Factor=Term | Factor “*” Term | Factor “/” Term
最后，我們可以寫(xiě)出一條只用加減和Factor構成的表達式的語(yǔ)法：
Exp=Factor | Exp “+” Factor | Exp “-“ Factor
到了這里表達式的語(yǔ)法就大功告成了。上面的三條語(yǔ)法中的Exp就是四則運算的語(yǔ)法了。
我們注意到Exp和Factor都是左遞歸的。在這里我介紹一種消除左遞歸的方法。我們考察一下語(yǔ)法Factor=Term | Factor “*” Term這一條。為了形象的表達出什么是Factor，我們反過(guò)來(lái)可以考察一下Factor究竟可以產(chǎn)生出什么樣的東西來(lái)。
一個(gè)Factor可以產(chǎn)生出一個(gè)Term。然后，一個(gè)Factor可以變成Factor “*” Term。如果我們把Factor “*” Term中的Factor替換成已知的結果的話(huà)，那么我們可以得到一個(gè)結論：一個(gè)Factor可以產(chǎn)生出Term “*” Term。同理，我們又可以知道一個(gè)Factor可以產(chǎn)生出Term “*” Term “*” Term，為Factor可以產(chǎn)生出Term “*” Term。于是我們大概可以猜出解決左遞歸的方法：
假設存在如下表達式：
A=B1
…
A=Bn
A=A C1
…
A=A Cn
我們可以將這個(gè)語(yǔ)法修改為如下形式：
A’=C1 | C2 | … | Cn [A’]
A=(B1 | B2 | … | Bn) [A’]
我們可以看到現在的A沒(méi)有發(fā)生變化，但是新的語(yǔ)法已經(jīng)不存在左遞歸了。我們?yōu)榱撕?jiǎn)化表達，可以引進(jìn)一種新的語(yǔ)法：我們讓X*代表X、X、X等等只由A組成的字符串或者空字符串，那么上面這個(gè)語(yǔ)法就可以被修改成A=(B1 | B2 | … | Bn) (C1 | C2 | … | Cn)*了。
于是，我們重新寫(xiě)一下四則運算式子的語(yǔ)法：
1) Term=<數字> | “(“ Exp “)”
2) Factor = Term ( ( “*” | “/” ) Term) *
3) Exp = Factor ( ( “+” | “-“ ) Factor) *
我在這里仍然要寫(xiě)出四則運算分析的代碼。但是這一次我不求值了，這個(gè)新的程序將把四則運算式子轉換成等價(jià)的LISP表達式然后輸出。
代碼的結構是這樣的。首先，仍然會(huì )存在上文中的函數Is。其次，表達式Expression的結構將被我替換成一個(gè)遞歸的二叉樹(shù)，異常信息使用C++的異常處理機制實(shí)現。
在這里貼出GetTerm和GetFactor的代碼，GetExp與GetFactor結構相似。
Expression* GetTerm(char*& Stream);
Expression* GetFactor(char*& Stream);
Expression* GetExp(char*& Stream);
/*
檢查Stream是否一個(gè)Term
*/
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;
}
}
}
/*
檢查Stream是否一個(gè)Factor
*/
Expression* GetFactor(char*& Stream)
{
/*獲得一個(gè)Term*/
char* Read=Stream;
Expression* Result=GetTerm(Read);
while(true)
{
/*檢查接下來(lái)是否乘除號*/
char Operator=0;
if(Is(Read,"*"))
Operator='*';
else if(Is(Read,"/"))
Operator='/';
else
break;
if(Operator)
{
/*如果是乘除號則獲得下一個(gè)Term*/
try
{
Result=new Expression(Operator,Result,GetTerm(Read));
}
catch(Exception& e)
{
/*發(fā)生異常的時(shí)候，首先刪除Result，其次轉發(fā)異常*/
delete Result;
throw e;
}
}
}
Stream=Read;
return Result;
}
完整的代碼見(jiàn)文件夾Code_2_EXP2LISP。
這份代碼跟分析LISP表達式代碼不同的是這里展示了給出樹(shù)形結構而不僅僅是計算出結果的代碼。這兩種方法的區別僅僅是獲得了數據之后如何處理的問(wèn)題，但是代表了兩種經(jīng)常需要處理的任務(wù)。
四、尾聲
這篇文章相比起以前的兩篇正則表達式來(lái)的確是短了不少。遞歸下降法是一種適合人腦使用而不是電腦使用的方法。這種方法非常好用，所以大部分編譯原理的教科書(shū)都會(huì )專(zhuān)門(mén)使用一個(gè)章節來(lái)說(shuō)明遞歸下降的實(shí)現、局限性以及遇到的問(wèn)題的解決方法。這篇文章不是理論文章，所以有一些本文沒(méi)闡述到的問(wèn)題可以通過(guò)人的智商來(lái)解決。
在語(yǔ)法處理過(guò)程中遇到的一個(gè)問(wèn)題是出現異常的時(shí)候如何組織錯誤信息。在寫(xiě)編譯器的時(shí)候我們并不能通過(guò)異常處理來(lái)向外傳播異常信息，因為編譯器需要輸出許多異常。不過(guò)大部分分析工作還是僅僅需要第一個(gè)異常信息的。
第二個(gè)常見(jiàn)的問(wèn)題是如何在發(fā)生異常的時(shí)候處理分析結果。在本文的第二個(gè)例子里面，在拋出異常之前總是會(huì )手動(dòng)delete掉已經(jīng)產(chǎn)生的指針。其實(shí)這樣做是很容易漏掉一些處理從而造成內存泄漏的，如果讀者使用C++的話(huà)，那么我推薦使用STL的auto_ptr或者Boost的smart_ptr，或者干脆自己寫(xiě)吧。樹(shù)型結構的文檔通常不會(huì )有循環(huán)引用的問(wèn)題，所以在這種情況下無(wú)論如何產(chǎn)生文檔或者產(chǎn)生異常，使用auto_ptr或者smart_ptr都是沒(méi)有問(wèn)題的。
第三個(gè)問(wèn)題是寫(xiě)不出語(yǔ)法。這個(gè)問(wèn)題沒(méi)有什么好的辦法，只有通過(guò)練習來(lái)解決了?；蛘吒纱嘧鲆粋€(gè)YACC出來(lái)，經(jīng)過(guò)一次非常深入的思考也能獲得很多經(jīng)驗。就像寫(xiě)出一手好的正則表達式的人，要么就是練習了很多次，要么就是寫(xiě)過(guò)正則表達式引擎一樣。不過(guò)這種方法比較耗時(shí)間，不是非常有興趣的讀者們還是不要這么做的好。
最后說(shuō)明一下，本文使用四則運算式子作為例子僅僅是為了方便。實(shí)際上分析四則運算獅子已經(jīng)有各種各樣的好方法了。但是讀者們將來(lái)卻很難遇到分析四則運算的工作，而是分析各種各樣復雜字符串的工作。這個(gè)時(shí)候遞歸下降法起得作用是在代碼還沒(méi)開(kāi)始寫(xiě)之前，就已經(jīng)把思考不慎密導致的bug都消除了大半了。因為設計語(yǔ)法的過(guò)程很容易讓人深入的思考問(wèn)題。遞歸下降法能夠用最快的速度從語(yǔ)法產(chǎn)生出代碼，但是還是要根據實(shí)際情況調整細節。
本文作為《構造正則表達式引擎》一文的補充而出現，因為有一些朋友們反映在析正則表達式的結構以及合法性遇到了一些困難。因為正則表達式的語(yǔ)法跟四則運算很像，因此參考一下本文對這些朋友們來(lái)說(shuō)可能會(huì )有幫助。
正文(docx)以及附帶的代碼，點(diǎn)擊這里下載。
聯(lián)系客服
