算術(shù)表達(dá)式的產(chǎn)生式的自上而下語法分析

算術(shù)表達(dá)式的產(chǎn)生式的自上而下語法分析【精品文檔-

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