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