算術表達式的產生式的自上而下語法分析

算術表達式的產生式的自上而下語法分析【精品文檔-

doc】算術表達式的產生式的自上而下語法分析（摘自周翔）這篇文章里主要是站在編譯原理的角度講述一種語法分析程序的實現(xiàn)的方法，通過對一個典型的例子——算術表達式的分析，從而使大家了解構造一個實用的語法分析程序的方法，同時，也為廣大程序員提供一種解決實際問題的思路。本文包括以下內容:1（算術表達式的產生式;2（自上而下語法分析的算法和的產生式函數(shù)的構造;3（產生式函數(shù)的改進;4（語法分析中的出錯處理;5（自上而下語法分析程序的實現(xiàn)。1（算術表達式的產生式我在這里要實現(xiàn)的算術表達式要實現(xiàn)5種運算:加、減、乘、除和括號。比如一個簡單的算術表達式的文法G1中包含以下產生式：G1:E->E+E|E-E|E*E|E/E|（E）|i為了明確運算符的優(yōu)先權（括號的優(yōu)先權高于乘除法，乘除法的優(yōu)先權高于加減法），可改寫文法G1如下：改寫后的文法G2:E->T+E|T-E|TT->F*T|F/T|FF->（E）|i任何具有加、減、乘、除和括號運算優(yōu)先權的算術表達式都可以通過上述文法中的產生式推導出來，比如對于行如i-i*(i+i)的算術表達式，有如下推導過程(其中i是數(shù)字或變量標示符，推導需要從開始符E開始推導，以下是最左推導)：E=>T-E=>F-E=>i-E=>i-T=>i-F*T=>i-i*T=>i-i*F=>i-i*(E)=>i-i*(T+E)=>i-i*(F+E)=>i-i*(i+E)=>i-i*(i+T)=>i-i*(i+F)=>i-i*(i+i)在本文中，我們就使用文法G2中的產生式構造語法分析程序。2(自上而下語法分析的算法和的產生式函數(shù)的構造我們可以把一個對句子從開始符E到終結符的推導過程轉化為一棵語法樹，根節(jié)點(即開始符)在上、葉節(jié)點(即終結符)在下，自上而下的語法分析就是對這樣一棵語法樹“自上而下”地遍歷過程。即，每次遍歷從根節(jié)點(開始符)開始，通過各個中間節(jié)點(除開始符外非終結符)到達葉節(jié)點(終結符)。如果把每一個產生式做成一個函數(shù)，那么我們可以方便地通過對這些函數(shù)的遞歸調用和回溯來實現(xiàn)對語法樹的遍歷。那么對于文法G2中的3個產生式，我們需要3個函數(shù)：voidE_AddSub();〃對應于非終結符E的產生式voidT_MulDiv();//對應于非終結符T的產生式voidF_Number();〃對應于非終結符F的產生式我們通過對輸入字符流的分析來實現(xiàn)自上而下的語法分析。在語法分析的過程中，我們需要一個輸入字符緩沖區(qū)，用來存放輸入的算術表達式字符串，需要一個字符指示器來指示當前正在分析的字符，還需要一個出錯處理模塊。在算法設計實現(xiàn)中，我們用到了3個全局成員：ch、advance和error，它們的含義如下：第1頁共12頁ch當前指示器所指的字符advance()使指示器指向輸入字符緩沖器中的下一個字符的函數(shù)error()出錯處理程序函數(shù)由此可以構造自上而下語法分析算法，首先分析產生式E->T+E|T-E|T,不妨先把它分解成以下3個產生式:E->T+EE->T-EE->T下面首先寫出E->T+E個語法分析函數(shù)：〃清單1:產生式E->T+E的語法分析函數(shù)voidE_AddSub(){T_MulDiv();//調用非終結符T的產生式函數(shù)分析TIf(ch==?+?)//如果當前字符是?+?，{advance();//則取下一個字符E_AddSub();//調用非終結符E的產生式函數(shù)分析E}else//如果不是?+?號error();//則進行出錯處理}看到上面函數(shù)中的算法，你大概已經可以想到產生式E->T-E的自上而下語法分析算法了，即把If(ch==?+?)一句中的?+?改成?-?號即可。下面是產生式E->T的算法，很簡單:〃清單2:產生式E->T的語法分析函數(shù)voidE_AddSub(){T_MulDiv();//調用非終結符T的產生式函數(shù)分析T}大家可以看到，為每一個產生式寫一個分析函數(shù)，通過它們之間的相互調用，即可實現(xiàn)對語法樹的遍歷，從而實現(xiàn)對句子的推導。由于E->T+E、E->T-E、E->T三個產生式可以合并成E->T+E|T-E|T，我們也可以把對應的三個產生式的函數(shù)合并成一個函數(shù)，由于有產生式E->T，所以在E的產生式函數(shù)中只調用非終結符T的分析函數(shù)就可以了，即使下一個字符不是?+?或?-?也不必做錯誤處理，而E->T+E|T-E的合并用一句分支語句if(ch==?+?11ch==?-?)判斷即可，這樣，合并后E產生式的函數(shù)如下：〃清單3:產生式E->T+E|T-E|T的分析函數(shù)voidE_AddSub(){T_MulDiv();//調用非終結符T的產生式函數(shù)分析TIf(ch==?+?||ch==?-?)//如果當前字符是?+?或?-?，〃如果是?+?，則用產生式E->T+E推導，〃如果是?-?，則用產生式E->T-E推導。{advance();//則取下一個字符E_AddSub();//調用非終結符E的產生式函數(shù)分析E第2頁共12頁}〃此時產生式E->T+E|T-E的推導算法結束//如果下一個字符不是不是?+?或?-?，〃則本函數(shù)是根據產生式E->T來進行推導的，不必進行錯誤處理。}同理，你也可以容易地寫出產生式T->F*T|F/T|F和F->(E)|1的自上而下語法分析函數(shù):〃清單4:產生式T->F*T|F/T|F的分析函數(shù)voidT_MulDiv(){F_Number();//調用非終結符F的產生式函數(shù)分析FIf(ch==?*?||ch==?/?)//如果當前字符是?*?或?\?，〃如果是?*?，則用產生式T->F*T推導，〃如果是?\?，則用產生式T->F/T推導。{advance();//則取下一個字符T_MulDiv();//調用非終結符T的產生式函數(shù)分析T}〃此時產生式T->F*T|F/T的推導算法結束//如果下一個字符不是不是?*?或?/?，〃則本函數(shù)是根據產生式T->F來進行推導的，不必進行錯誤處理。}〃清單5:產生式F->(E)|i的分析函數(shù)voidF_Number(){if(ch==?(?)//如果當前的指示器指示的字符是?(?{〃則根據產生式F->(E)推導advance();//跳過?(?，指示器指向下一個字符E_AddSub();//調用非終結符E的產生式函數(shù)分析EIf(ch!=?)?)//判斷下一個字符是否是?)?，//必須保證有右括號與左括號配對使用error();//如果出錯，則進行出錯處理。Advance();//如果有?)?，語法正確，跳過?)?return;//返回}if(ch是數(shù)字)〃如果當前指示器指示的字符是數(shù)字{〃則根據產生式F->i推導advance();//跳過該數(shù)字，指示器指向下一個字符}〃語法正確，完成F->i推導else//如果當前指示器指示的字符不是數(shù)字也不是?(?error();//則出錯，轉向出錯處理程序return;//返回}由于，符合語法的句子的推導是從開始符E開始的，所以在進行語法分析時，需要在主程序中這樣實現(xiàn):第3頁共12頁//清單6:主程序intmain()//對輸入字符緩沖區(qū)和字符指示器初始化〃調用開始符E的分析函數(shù)開始自上而下語法分析:E_AddSub();//分析結束return0;}按照此方法實現(xiàn)的上述函數(shù)實現(xiàn)了對語法樹的自上到下的遍歷，從而展示了自上而下語法分析的過程，然而，這些函數(shù)并沒有實現(xiàn)具體的功能，比如執(zhí)行算術表達式或計算求值的功能，在下面的幾節(jié)里我會陸續(xù)考慮這些問題。3(產生式函數(shù)的改進前兩節(jié)我們已經實現(xiàn)了自上而下語法分析算法和產生式函數(shù)的構造，在這一節(jié)，我著重闡述對產生式函數(shù)的運行效率和占用空間進行優(yōu)化的方法。首先考察一下產生式E->T+E|T-E|T的分析函數(shù)：voidE_AddSub(){T_MulDiv();//調用非終結符T的產生式函數(shù)分析TIf(ch==?+?||ch==?-?)//如果當前字符是?+?或?-?，〃如果是?+?，則用產生式E->T+E推導，〃如果是?-?，則用產生式E->T-E推導。{advance();//則取下一個字符E_AddSub();//調用非終結符E的產生式函數(shù)分析E}〃此時產生式E->T+E|T-E的推導算法結束//如果下一個字符不是不是?+?或?-?，〃則本函數(shù)是根據產生式E->T來進行推導的，不必進行錯誤處理。}大家看到，在if語句塊中有一句E_AddSub();,這意味著在E_AddSub()函數(shù)中的語句可以調用自己本身，即函數(shù)中存在遞歸。然而在這里，我們完全可以節(jié)省一部分因遞歸占用的程序堆?？臻g，在這同時也減少了因對程序堆棧進行push/pop操作耗費的時間。在這里我要用到的一種改進的方法是用循環(huán)代替if通過消除自身遞歸來削弱遞歸深度的方法，比如改進后的E_AddSub()函數(shù)如下：〃清單7:改進后的產生式E->T+E|T-E|T的分析函數(shù)voidE_AddSub(){T_MulDiv();//調用非終結符T的產生式函數(shù)分析Twhile(ch==?+?||ch==?-?)//如果當前字符是?+?或?-?，〃如果是?+?，則用產生式E->T+E推導，〃如果是?-?，則用產生式E->T-E推導。{第4頁共12頁advance();//則取下一個字符T_MulDiv();//調用非終結符E的產生式函數(shù)分析T}〃若當前指示器指示的符號是?+?或?-?，則繼續(xù)while循環(huán)//如果下一個字符不是不是?+?或?-?，〃則本函數(shù)是根據產生式E->T來進行推導的，不必進行錯誤處理。}我們可以看到在清單7中，在把if變成while的同時，還把while語句塊中的E_AddSub()變?yōu)門_MulDiv()，這意味著把產生式(其中op為?+?或?-?):E->TopE轉換為:E->TopTopTopTop………………opT兩者是等價的。顯然對于型如iopiopiopi這樣的句子，后者有更快的推導速度，而前者需要多進行3次遞歸堆棧。因此，改進后的產生式函數(shù)更高效。同樣，T_MulDiv()也可以通過這種方法改進。然而，這種方法并不能完全消除遞歸，只是減少了遞歸的調用次數(shù)，削減了遞歸層次。每當分析到括號運算符時，因為F_Number()會被T_MulDiv()調用，T_MulDiv()會被E_AddSub()調用，所以會產生一個對開始符E的產生式函數(shù)的遞歸:voidF_Number(){if(ch==?(?)//如果當前的指示器指示的字符是?(?{〃則根據產生式F->(E)推導advance();//跳過?(?，指示器指向下一個字符E_AddSub();//調用非終結符E的產生式函數(shù)分析EIf(ch!=?)?)error();//如果出錯，則進行出錯處理。Advance();//如果有?)?，語法正確，跳過?)?return;//返回}return;//返回按照這種方法只有在分析括號運算符內的算術表達式時才增加一個遞歸層次，可以有效地提高語法分析的執(zhí)行效率。4(語法分析中的出錯處理進行出錯處理也許是件很麻煩的事。想象一個設計良好的編譯調試環(huán)境，比如VisualStudio,我們在用它開發(fā)編譯程序時，不光可以知道哪一句錯了，而且可以獲得出錯的原因。我們現(xiàn)在要做的是對一句算術表達式(如果出錯的話)找出出錯的原因，并把錯誤原因和相關信息提示給用戶。這該怎么辦呢,《編譯原理》的課本上大都講過通過考察FIRST集和FOLLOW集構造語法分析表的方法來處理錯誤，這樣可以把錯誤的處理方法填充到分析表中。然而在這里，既然我們已經構造好了文法產生式函數(shù)，簡單地，這樣，我們僅僅通過在函數(shù)中出現(xiàn)error()函數(shù)調用的地方進行分析一下即可逐步實現(xiàn)對錯誤的處理。第5頁共12頁考察清單5中產生式F->(E)|i的函數(shù)：voidF_Number(){if(ch==?(?){advance();E_AddSub();If(ch!=?)?)//如果當前指示器指示的字符不是?)?，則產生錯誤，error();//錯誤號:1advance();return;if(ch是數(shù)字){advance();}else//如果當前指示器指示的字符不是數(shù)字，則產生錯誤error();//錯誤號:2return;}在上述代碼中可以看到有兩處可能產生錯誤的地方，其中1號錯誤產生的原因很容易看出來，是“缺少與左括號匹配的右括號”。2號錯誤產生的原因是“當前指示器指示的字符不是數(shù)字”，即在算術表達式中該出現(xiàn)數(shù)字的地方沒有出現(xiàn)數(shù)字，比如當指示器指到非法表達式“23+#b”中的“#"、“1-(+”中的“+”和“2+*3”中的“*”時都屬于這種情況。2號錯誤還有兩種情況，一種是當括號內無表達式(即括號內表達式為空時)，比如“3+()”，這樣需要判斷當前指示的字符是否為?)?;第二種是表達式不完整(即表達式提前結束)，比如“4*(2+3)+”，這需要判斷當前指示的字符是否為?\0?(字符串結束符)。再考察一下清單6中的主函數(shù):intmain(){//對輸入字符緩沖區(qū)和字符指示器初始化〃調用開始符E的分析函數(shù)開始自上而下語法分析:E_AddSub();//分析結束return0;}然而，根據我們的設計，當E_AddSub()函數(shù)返回(分析結束)時，在指示器所指字符的后面有可能還有未被分析的字符，凡此時存在未被指示器掃描過的字符的表達式均為錯第6頁共12頁誤的表達式。比如當指示器指到非法表達式“2*(3+4)5”中的“5”、“2+3(4+5)”中的“(”和“23a”中的“a”時都屬于這種錯誤情況。5(自上而下語法分析程序的實現(xiàn)經過上面4步精心的準備，最令人激動的時刻到了。一般《編譯原理》課本上的代碼大都是無法在機器上運行的偽代碼，在這里，你將要看到的是一個實用的可以檢查錯誤的可以執(zhí)行求值的基于自上而下語法分析算法的計算算術表達式的程序。不失一般性，我們規(guī)定算術表達式只可以進行整數(shù)的四則運算(含括號)，這樣我們需要擴充下面3個函數(shù):intE_AddSub();〃對應于非終結符E的產生式intT_MulDiv();//對應于非終結符T的產生式intF_Number();〃對應于非終結符F的產生式大家看到，上面的函數(shù)有返回值int，我們需要讓這3個函數(shù)返回計算出的結果的值。為了計算出每個函數(shù)中子表達式的值，在E_AddSub()和T_MulDiv()函數(shù)中，我用一個變量rtn來存儲運算符左部的值，用opr2來存儲運算符右部的值，根據運算符進行相應的運算。為了保存輸入的算術表達式，我用全局靜態(tài)字符數(shù)組expr來表示輸入字符緩沖區(qū)，用pos來表示字符指示器的值，這樣，指示器取下一個字符的advance()操作可以用pos++來代替，而指示器所指示的字符可以就是expr[pos]。為了表示錯誤，我用宏定義了6種錯誤的錯誤代碼，而且定義了對應的6條錯誤信息的字符串。同時把error()函數(shù)改造為：voidError(intErrCode);這樣通過傳遞錯誤代碼可以使程序對錯誤進行相應的反應，包括指示錯誤位置、顯示錯誤信息、發(fā)出提示音等。此外，我聲明了出錯跳轉緩沖區(qū)靜態(tài)變量errjb，errjb是一個std::jmp_buf類型的結構，可以通過$?口山口()宏把當前程序的運行狀態(tài)記錄到errjb中，錯誤返回時，可以通過longjmp()函數(shù);直接跳轉到main()主程序setjmp()被調用的位置，而不是出錯的函數(shù)體中。這樣，一個功能齊全的算術表達式分析執(zhí)行器構造完畢，注意，這樣構造的程序不能識別一元運算符，比如輸入“-1+1”會報錯。下面是運行結果片段:1+(八語法錯誤 表達式非法結束或表達式不完整一請重新輸入!請輸入一個算術表達式(輸入“項”或“q”退出)：2-()八語法錯誤 括號內無表達式或表達式不完整一請重新輸入!請輸入一個算術表達式(輸入“項”或“q”退出)：2+(3+八語法錯誤 表達式非法結束或表達式不完整一請重新輸入!請輸入一個算術表達式(輸入"Q”或"q”退出)：2+(3*9)+八語法錯誤 表達式非法結束或表達式不完整?第7頁共12頁請重新輸入!請輸入一個算術表達式(輸入"Q”或"q”退出)：2*(2+4)4八語法錯誤 右括號后連接非法字符?請重新輸入！程序清單如下:/****算術表達式的分析和計算，文件名：Exp_c.cpp,代碼/注釋:hifrog*********在VC6和Dev-C下調試通過****/#include#include#include#include#include#defineEXP_LEN100//定義輸入字符緩沖區(qū)的長度/* 出錯代碼的宏定義 */#defineINVALID_CHAR_TAIL0//表達式后跟有非法字符#defineCHAR_AFTER_RIGHT1//右括號后連接非法字符#defineLEFT_AFTER_NUM2//數(shù)字后非法直接連接左括號#defineINVALID_CHAR_IN3//表達式中含有非法字符#defineNO_RIGHT4//缺少右括號#defineEMPTY_BRACKET5//括號內無表達式#defineUNEXPECTED_END6//預期外的算術表達式結束usingnamespacestd;conststringErrCodeStr[]=//表達式出錯信息{"表達式后跟有非法字符?"，"右括號后連接非法字符?"，〃數(shù)字后非法直接連接左括號?〃，〃表達式中含有非法字符?〃，"缺少右括號?"，"括號內無表達式或表達式不完整?","表達式非法結束或表達式不完整?"};staticcharexpr[EXP_LEN];//算術表達式輸入字符緩沖區(qū)staticintpos;//字符指示器標志:用來保存正在分析的字符的位置staticjmp_buferrjb;//出錯跳轉緩沖器//********以下是函數(shù)聲明*********〃產生式“E->T+E|T-E|T”的函數(shù)，用來分析加減算術表達式。intE_AddSub();〃產生式“T->F*T|F/T|F”的函數(shù)，用來分析乘除算術表達式。intT_MulDiv();〃產生式“F->i|(E)”的函數(shù)，用來分析數(shù)字和括號內的表達式。intF_Number();第8頁共12頁//出錯處理函數(shù)，可以指出錯誤位置，出錯信息。voidError(intErrCode);intmain(){intans;//保存算術表達式的計算結果boolquit=false;//是否退出計算do{〃在此設定一個跳轉目標，如果本程序的其他函數(shù)調用longjmp,//執(zhí)行指令就跳轉到這里，從這里繼續(xù)執(zhí)行。if(setjmp(errjb)==0)//如果沒有錯誤{pos=0;//初始化字符指示器為0，即指向輸入字符串的第一個字符。cout<〈"請輸入一個算術表達式(輸入"Q”或"q"退出)："<<ENDL;cin>>expr;//輸入表達式，填充表達式字符緩沖區(qū)。if(expr[0]=='q'||expr[0]=='Q')//檢查第一個字符，是否退出,quit=true;else{〃調用推導式“E->T+E|T-E|T”的函數(shù)，〃從起始符號“E”開始推導。ans=E_AddSub();//此時，程序認為對表達式的語法分析已經完畢，下面判斷出錯的原因://如果表達式中的某個右括號后直接跟著數(shù)字或其他字符，〃則報錯，因為數(shù)字i不屬于FOLLOW。)集。if(expr[pos-1]==')'&&expr[pos]!='\0')Error(CHAR_AFTER_RIGHT);//如果表達式中的某個數(shù)字或右括號后直接跟著左括號，〃則報錯，因為左括號不屬于FOLLOW(E)集。if(expr[pos]=='(')Error(LEFT_AFTER_NUM);//如果結尾有其他非法字符if(expr[pos]!='\0')Error(INVALID_CHAR_TAIL);cout<<"計算得出表達式的值為:“<<ANS<<ENDL;}}else{〃setjmp(errjb)!=0的情況：cout<〈"請重新輸入！"<<ENDL;}第9頁共12頁}while(!quit);return0;}〃產生式“E->T+E|T-E|T”的函數(shù)，用來分析加減算術表達式?！ǚ祷赜嬎憬Y果intE_AddSub(){intrtn=T_MulDiv();//計算加減算術表達式的左元while(expr[pos]=='+'||expr[pos]=='-'){intop=expr[pos++];〃取字符緩沖區(qū)中當前位置的符號到opintopr2=T_MulDiv();//計算加減算術表達式的右元//計算求值if(op=='+')//如果是"+"號rtn+=opr2;//則用加法計算else//否則(是"-"號)rtn-=opr2;//用減法計算}returnrtn;}〃推導式“T->F*T|F/T|F”的函數(shù)，用來分析乘除算術表達式?！ǚ祷赜嬎憬Y果intT_MulDiv(){intrtn=F_Number();//計算乘除算術表達式的左元while(expr[pos]=='*'||expr[pos]=='/')intop=expr[pos++];//取字符緩沖區(qū)中當前位置的符號到opintopr2=F_Number();//計算乘除算術表達式的右元//計算求值if(op=='*')//如果是"*"號rtn*=opr2;//則用乘法計算else//否則(是"\"號)rtn/=opr2;//用除法計算}return