編譯原理大作業(yè)

1、課程論文遞歸下降分析器的實(shí)現(xiàn)課程名稱(chēng) 所屬學(xué)院 班 級(jí) 學(xué)生姓名 學(xué) 號(hào) 二零一四年十二月目錄1、遞歸下降分析器的設(shè)計(jì)思想11.1自頂向下的語(yǔ)法分析方法11.2遞歸下降分析法11.3遞歸下降分器意義：11.4遞歸下降分析器思想：11.5遞歸下降分析器的作用：11.6遞歸下降分析器的形成過(guò)程：22、遞歸向下分析器實(shí)現(xiàn)22.2待分析的簡(jiǎn)單詞法22.3要求構(gòu)造的遞歸下降程序32.4主函數(shù)分析33、輸入串運(yùn)行分析：44、關(guān)鍵代碼分析及運(yùn)行過(guò)程：54.1關(guān)鍵代碼分析54.2文法函數(shù)調(diào)用過(guò)程65、程序測(cè)試：65.1、當(dāng)程序運(yùn)行時(shí)出現(xiàn)如下輸入程序界面65.2、當(dāng)程序運(yùn)行時(shí)出現(xiàn)如下輸入程序界面7總結(jié)8參考文獻(xiàn)

2、：8附錄：9信息工程學(xué)院編譯原理課程論文遞歸下降分析器的實(shí)現(xiàn)摘要：本文分析了遞歸下降分析器的實(shí)現(xiàn)以及具體的功能，所謂遞歸下降分析法，就是對(duì)文法中的每個(gè)非終結(jié)符編寫(xiě)一個(gè)函數(shù)（子程序），每個(gè)函數(shù)（子程序）的功能是識(shí)別由該非終結(jié)符所標(biāo)示的語(yǔ)法成分。由于描述語(yǔ)言的文法通常是遞歸定義的，因此相應(yīng)的這組函數(shù)（子程序）一定是相互遞歸的方式進(jìn)行調(diào)用，所以將此種分析方法稱(chēng)為遞歸下降分析法。關(guān)鍵詞：遞歸下降分析器 消除遞歸 非終結(jié)符1、遞歸下降分析器的設(shè)計(jì)思想1.1自頂向下的語(yǔ)法分析方法自頂向下分析法也稱(chēng)面向目標(biāo)的分析方法，也就是從文法的開(kāi)始符號(hào)出發(fā)企圖推導(dǎo)出與輸入的單詞串完全相匹配的句子，若輸入串是給定文法的句

3、子，則必能推出，反之必然出錯(cuò)。自頂向下的確定分析方法需對(duì)文法有一定的限制，但由于實(shí)現(xiàn)方法簡(jiǎn)答、直觀，便于手工構(gòu)造或自動(dòng)生成語(yǔ)法分析器，因而仍是目前常用的方法之一。而自頂向下的不確定分析方法是帶回溯的分析方法，這種方法實(shí)際上是一種窮舉的試探方法，因此效率低，代價(jià)高，因而極少使用。1.2遞歸下降分析法 遞歸下降分析法是確定的自上而下分析法，它要求文法是LL(1)文法。它的基本思想是：對(duì)文法中的每個(gè)非終結(jié)符編寫(xiě)一個(gè)函數(shù)或子程序，每個(gè)函數(shù)或子程序的功能是識(shí)別由該非終結(jié)符所表示的語(yǔ)法成分。并且由遞歸下降分析法，得出了遞歸下降分析器。1.3遞歸下降分器意義：遞歸下降分析器，可以使已經(jīng)消除左遞歸，回溯的文法

4、，迅速判斷出輸入串是否滿(mǎn)足該文法，并按照遞歸的方法，算出終結(jié)符,此分析器解決的手工計(jì)算繁瑣問(wèn)題。1.4遞歸下降分析器思想：遞歸下降分析法是一種自頂向下的分析法，文法中的每一個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)遞歸過(guò)程（函數(shù)）。分析過(guò)程就是從文法開(kāi)始符出發(fā)執(zhí)行一組遞歸過(guò)程（函數(shù)），這樣向下推到直到推出句子；或者是從根節(jié)點(diǎn)出發(fā)，自頂向下為輸入串尋找一個(gè)最左匹配序列，建立一個(gè)語(yǔ)法樹(shù)。1.5遞歸下降分析器的作用：（1）讀入輸入的符號(hào)串；（2）對(duì)輸入的符號(hào)串逐個(gè)與棧中的終結(jié)符比較；（3）識(shí)別出匹配的輸入字符；（4）確定文法是否能推導(dǎo)出輸入串1.6遞歸下降分析器的形成過(guò)程：實(shí)現(xiàn)遞歸下降分析器，首先要消除產(chǎn)生式的左遞歸，其次

5、要消除產(chǎn)生式的回溯，得到可以編寫(xiě)遞歸下降分析器的文法如（圖1）圖1遞歸下降分析器形成過(guò)程2、遞歸向下分析器實(shí)現(xiàn)2.2待分析的簡(jiǎn)單詞法（1）非終結(jié)符：E E T TF(代碼中T用T1代替) (代碼中E用E1代替)（2）終結(jié)符+ * （ ） i2.3要求構(gòu)造的遞歸下降程序文法GE:E->E+T|TT->T*F|FF->(E)|i首先，消除該文法的左遞歸，得到文法GE:E->TE'E'->+TE'|T->FT'T'->*FT'|F->(E)|i然后，根據(jù)LL(1)文法的判斷條件，對(duì)非終結(jié)符S和T的不同產(chǎn)生

6、式的集進(jìn)行考察，經(jīng)驗(yàn)證改進(jìn)后的文法已經(jīng)是LL(1)文法。最后構(gòu)造遞歸下降分析程序。每個(gè)函數(shù)名是相應(yīng)的非終結(jié)符，函數(shù)體則是根據(jù)規(guī)則右部符號(hào)串的結(jié)構(gòu)編寫(xiě)。（非終結(jié)符在這里統(tǒng)稱(chēng)為A）輸入的字符串以#結(jié)束。（1）當(dāng)遇到終結(jié)符a時(shí)，則編寫(xiě)語(yǔ)句If(當(dāng)前讀到的輸入符號(hào)=a)讀入下一個(gè)輸入符號(hào)（2）當(dāng)遇到非終結(jié)符A時(shí)，則編寫(xiě)語(yǔ)句調(diào)用A()。（3）當(dāng)遇到A->規(guī)則時(shí)，則編寫(xiě)語(yǔ)句。If(當(dāng)前讀到的輸入符號(hào)不屬于Follow(A)error() (退出)。（4）當(dāng)某個(gè)非終結(jié)符的規(guī)則有多個(gè)候選式時(shí)，按LL(1)文法的條件能唯一地選擇一個(gè)候選式進(jìn)行推導(dǎo)。2.4主函數(shù)分析此文發(fā)一共可分為個(gè)函數(shù)，分別為E(),E(

7、),T(),T(),F(),其中在E函數(shù)中可調(diào)用T(),E'()兩個(gè)函數(shù)。在E()函數(shù)中可以判斷輸出串“+”，并調(diào)用T（），E'（）兩個(gè)函數(shù)，在T()函數(shù)中可以調(diào)用F()，T()兩個(gè)函數(shù)。在T'()函數(shù)中可以判斷輸入串“*”，并調(diào)用F()和T()兩個(gè)函數(shù)。在F()函數(shù)中可以調(diào)用E()函數(shù)并判斷輸入串“ (”，“)”，或判斷輸入串是否為“i”。通過(guò)遞歸調(diào)用實(shí)現(xiàn)進(jìn)棧，匹配出棧，最終達(dá)到檢測(cè)效果。3、輸入串運(yùn)行分析：當(dāng)輸入串為i*(i+i)時(shí)，用棧的形式表現(xiàn)出運(yùn)行過(guò)程以#為結(jié)束，首先將E和分文法開(kāi)始符E壓入棧中，開(kāi)始分析。首先將“#”和文法開(kāi)始符E壓入棧，可以從詞條文法中的到

8、終結(jié)符，并判斷終結(jié)符是否與輸入串的的字符相符合，如果符合出棧，并判斷在棧中的下一個(gè)非終結(jié)符，在文法中找到對(duì)應(yīng)的產(chǎn)生式，判斷期棧頂?shù)慕K結(jié)符是否與輸入串一致，一致出棧，不一致則跳出，此文法無(wú)法得到輸入串。如最后棧底?！?“，并且輸入串最后剩#，此輸入串符合文法，語(yǔ)法分析成功如（圖2）。圖2輸入串運(yùn)行分析在圖中第五步執(zhí)行函數(shù)F（）時(shí)，因當(dāng)前掃描的字符為“（”，所以匹配后應(yīng)執(zhí)行E（）（用棧模型將E壓棧）；并且；在執(zhí)行完E（）后還應(yīng)執(zhí)行其后的判斷“）”與匹配“）”語(yǔ)句，這在棧的模擬中則是標(biāo)出此時(shí)E壓棧之前的位置如圖步驟（714）即出棧至此14步結(jié)束并執(zhí)行這個(gè)判斷“）”與匹配“）”語(yǔ)句。4、關(guān)鍵代碼分析及

9、運(yùn)行過(guò)程：4.1關(guān)鍵代碼分析void E() /文法中調(diào)用E if(SIGN=0)T(); /并在E中分別調(diào)用TE1(); /調(diào)用Evoid E1() /進(jìn)入E if(SIGN=0)if(si='+') /判斷輸入串是否是非終結(jié)符+，如果是則出棧readin(); T(); /并繼續(xù)調(diào)用T函數(shù)進(jìn)入文法TE1(); /出T函數(shù)進(jìn)去E中判斷是否是else if(si!='#'&&si!=')')printf("輸入串字符不符合文法定義！n");SIGN=1;readin();void T()if(SIGN=0)F(

10、);T1();4.2文法函數(shù)調(diào)用過(guò)程 如（圖3）中用二叉樹(shù)表示出遞歸下降分析器的遞歸過(guò)程，可得出詳細(xì)的分析過(guò)程。圖3文法函數(shù)調(diào)用過(guò)程5、程序測(cè)試：5.1、當(dāng)程序運(yùn)行時(shí)出現(xiàn)如下輸入程序界面如（圖4），（圖5）所示時(shí)匹配成功：圖4 第一個(gè)輸入串匹配圖5 第二個(gè)輸入串匹配5.2、當(dāng)程序運(yùn)行時(shí)出現(xiàn)如下輸入程序界面如（圖6）所示時(shí)匹配失敗，文法無(wú)法得到輸入串（）圖6匹配失敗總結(jié)首先遇到的困難是對(duì)遞歸下降的分析法的不理解。雖然課上老師曾細(xì)致講解過(guò)但還是生疏。所以，花費(fèi)大量時(shí)間重新學(xué)習(xí)遞歸。重點(diǎn)回顧了進(jìn)棧，匹配出棧等知識(shí)。讓我更清楚的認(rèn)識(shí)到自頂向下的語(yǔ)法分析并且清楚的知道了遞歸向下分析器的分析法的用法，加深

11、了C語(yǔ)言編譯器的用法，并更加清楚的熟練的運(yùn)用了消除遞歸，和消除回溯的用法，并自己進(jìn)行了消除遞歸，消除回溯的計(jì)算。并運(yùn)用了遞歸的方法實(shí)現(xiàn)了算法，我對(duì)語(yǔ)法分析有了深入的認(rèn)識(shí)，并在最后對(duì)算法進(jìn)行了改進(jìn)，不結(jié)束程序的情況下繼續(xù)分析。其次就是課程設(shè)計(jì)報(bào)告的書(shū)寫(xiě)。我也也需要很大的精力，查找資料，請(qǐng)教同學(xué)，強(qiáng)老師請(qǐng)求幫助。在對(duì)word的排版方面，有很多的細(xì)節(jié)需要認(rèn)真注意。雖然已經(jīng)對(duì)代碼有了清楚的認(rèn)識(shí)，但在論文方面還是遇到了很多問(wèn)題，比如專(zhuān)業(yè)術(shù)語(yǔ)欠缺，分析不夠詳細(xì)，但是在我請(qǐng)教了吳剛老師后，對(duì)概念有了更加深刻的認(rèn)識(shí)。自己獨(dú)立完成課程設(shè)計(jì)，熟悉程序設(shè)計(jì)中出現(xiàn)的所有問(wèn)題以及解決方案，這無(wú)疑加深了程序設(shè)計(jì)人員對(duì)設(shè)計(jì)

12、的項(xiàng)目的印象，并重現(xiàn)拾起了很久不使用的C語(yǔ)言。為以后的的課程設(shè)計(jì)和大作業(yè)打下了基礎(chǔ)。參考文獻(xiàn)：1 張素琴等編著.編譯原理M. 清華大學(xué)出版社, 2005 2 胡元義主編.編譯原理教程M. 西安電子科技大學(xué)出版社, 20033 李文生編著.編譯程序設(shè)計(jì)原理與技術(shù)M. 北京郵電大學(xué)出版社, 20024 程妍. 編譯原理實(shí)驗(yàn)教學(xué)體系綜述與改革探討J. 福建電腦. 2008(05) 5 李峰. 提高編譯原理實(shí)驗(yàn)效果的實(shí)踐J. 重慶三峽學(xué)院學(xué)報(bào). 2007(03)附錄：#include<stdio.h>void E();void T();void E1();void T1();void F(

13、);void readin();char s100;int i,SIGN,n;void main()n=1;while( n )printf("請(qǐng)輸入一個(gè)語(yǔ)句，以#號(hào)結(jié)束語(yǔ)句n");SIGN = 0;i=0;scanf("%s",&s);if( s0 = '#')printf("無(wú)語(yǔ)句輸入n");continue;E();if(si='#' && SIGN=0)printf("輸入串正確，結(jié)束語(yǔ)句符號(hào)正確！n");else if(si='#'

14、&& SIGN=1)printf("結(jié)束語(yǔ)句符號(hào)正確！n");else printf("結(jié)束語(yǔ)句符號(hào)不正確！n");printf("是否繼續(xù)輸入 1為繼續(xù)，0為推出n");scanf("%d",&n);printf("n");void E()if(SIGN=0)T();E1();void E1()if(SIGN=0)if(si='+')readin();T();E1();else if(si!='#'&&si!=')')printf("輸入串字符不符合文法定義！n");SIGN=1;readin();void T()if(SIGN=0)F();T1();void T1()if(SIGN=0)if(si='*')readin();F();T1();else if(si!='#'&&si!=')'&&si!='+')printf("輸入串字符不符合文法定義！n");SIGN=1;void F()if(SIGN=0)if(si='(