編譯原理-遞歸下降子程序-課程設(shè)計(jì)報(bào)告

編譯原理課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目遞歸下降分析程序的實(shí)現(xiàn)學(xué)生姓名 學(xué)號(hào) 專業(yè)班級(jí)計(jì)算機(jī)科學(xué)與技術(shù)指導(dǎo)教師

2011年12月2日

一、實(shí)驗(yàn)?zāi)康模赫莆兆陨隙抡Z(yǔ)法分析的要求與特點(diǎn)。掌握遞歸下降語(yǔ)法分析的基本原理和方法。掌握相應(yīng)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)方法。實(shí)驗(yàn)內(nèi)容:設(shè)計(jì)內(nèi)容及要求：對(duì)文法G設(shè)計(jì)內(nèi)容及要求：對(duì)文法G：E-E+TITT-T*F|FFf(E)|i構(gòu)造岀G的遞歸下降分析程序。程序顯示輸出匹配過(guò)程(即自上而下生成語(yǔ)法分析樹(shù)的步驟，輸出各匹配產(chǎn)生式序號(hào)即可)。三、設(shè)計(jì)思路:語(yǔ)法分析：語(yǔ)法分析是編譯程序的核心部分，任務(wù)是分析一個(gè)文法的句子結(jié)構(gòu)。遞歸下降分析程序的實(shí)現(xiàn)的功能:按照文法的產(chǎn)生式(語(yǔ)言的語(yǔ)法規(guī)則)，識(shí)別輸入符號(hào)串是否為一個(gè)句子(合式程序)。自上而下分析：從文法的開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，推出句子。可分為帶“回溯”的和不帶回溯的遞歸子程序(遞歸下降)分析方法。它的主旨是對(duì)任何輸入串，試圖用一切可能的辦法，從文法開(kāi)始符號(hào)(根結(jié)點(diǎn))出發(fā)，自上而下地為輸入串建立一棵語(yǔ)法樹(shù)?；蛘哒f(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)。也即從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找〃匹配“的推導(dǎo)。遞歸下降分析法：對(duì)每一語(yǔ)法變量(非終結(jié)符)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語(yǔ)法單位，通過(guò)子程序間的信息反饋和聯(lián)合作用實(shí)現(xiàn)對(duì)輸入串的識(shí)別。分析過(guò)程中遇到的問(wèn)題：分析過(guò)程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種匹配可能是暫時(shí)的。出錯(cuò)時(shí)，不得不“回溯”o文法左遞歸問(wèn)題。含有左遞歸的文法將使自上而下的分析陷入無(wú)限循環(huán)。構(gòu)造不帶回溯的自上而下分析算法：a.要消除文法的左遞歸性：一個(gè)文法可以消除左遞歸的條件是①不含以￡為右部的產(chǎn)生式②不含回路。

b?克服回溯，構(gòu)造不帶回溯的自上而下分析的文法條件(6)滿足LL(1)文法的三個(gè)條件：?文法不含左遞歸，.對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若A-cc1a2???|an 則FIRST(ai)QFIRST(aj)=f(iHj).對(duì)文法中的每個(gè)非終結(jié)符A,若它存在某個(gè)候選首符集包含￡，則FIRST(ai)DFOLLOW(A)=f i=l,2,.?.，n(7)因此我們可以把設(shè)計(jì)要求的文法首先改寫為L(zhǎng)L(1)文法E-TE'E'f+TE：sT-FT'Ff(E)Ff(E)然后構(gòu)造每個(gè)非終結(jié)符的FIRST和然后構(gòu)造每個(gè)非終結(jié)符的FIRST和FOLLOW集合:FIRST(E)={( ,i}FIRST(Ez)={+,e}FIRST(T) ={ (,I}FIRST(T')={*,s}FOLLOW(E) ={), #}FOLLOW(EO={),#}FOLLOW(T)={+,),#}FOLLOW(F)二{+,),#}FIRST(F)={(,I}FOLLOW(F)FIRST(F)={(,I}FOLLOW(F)二{*, +,),#}確定改寫后的文法為L(zhǎng)L(1)文法；然后為每一個(gè)非終結(jié)符，構(gòu)造相應(yīng)的遞歸過(guò)程，過(guò)程的名字表示規(guī)則左部的非終結(jié)符；過(guò)程體按規(guī)則右部符號(hào)吊的順序編寫。然后再為每個(gè)非終結(jié)符設(shè)計(jì)一個(gè)對(duì)應(yīng)的函數(shù)，通過(guò)各函數(shù)之間的遞歸調(diào)用從而實(shí)現(xiàn)遞歸下降語(yǔ)法分析的功能。(8)編寫C++代碼用到的變量和幾個(gè)功能識(shí)別函數(shù)：.advanced； //字符串小標(biāo),表示使IP指向下一輸入符號(hào)。?voidE()； //功能識(shí)別函數(shù)，表示規(guī)則E->TE,voidEl(); //功能識(shí)別函數(shù)，表示規(guī)則E—>+TE'/￡voidT(); //功能識(shí)別函數(shù)，表示規(guī)則?FT,VOidTl(); //功能識(shí)別函數(shù)，表示規(guī)則r-XFT/evoidF(); //功能識(shí)別函數(shù)，表示規(guī)則F->(E)/i因?yàn)槊總€(gè)非終結(jié)符有對(duì)應(yīng)的子程序的定義，功能識(shí)別函數(shù)的編寫過(guò)程中，當(dāng)需要從某個(gè)非終結(jié)符出發(fā)進(jìn)行展開(kāi)(推導(dǎo))時(shí)，就調(diào)用這個(gè)非終結(jié)符對(duì)應(yīng)的子程序。功能識(shí)別函數(shù)的設(shè)計(jì)與編寫：(1)當(dāng)遇到終結(jié)符a時(shí)，則編寫語(yǔ)句If(當(dāng)前讀到的輸入符號(hào)=&)讀入下一個(gè)輸入符號(hào)(2)當(dāng)遇到非終結(jié)符A時(shí)，則編寫語(yǔ)句調(diào)用A()o

(3)當(dāng)遇到A~>e規(guī)則時(shí)，則編寫語(yǔ)句If(X前讀到的輸入符號(hào)不屬于Follow(A))error()(4)當(dāng)某個(gè)非終結(jié)符的規(guī)則有多個(gè)候選式時(shí)，按LL(1)文法的條件能唯一地選擇一個(gè)候選式進(jìn)行推導(dǎo).結(jié)果截圖：1、輸入一個(gè)正確的句子:2、輸入一個(gè)錯(cuò)誤句子■inputsentence.txt本文件㈢編捐㈢格式9)查看?幫助但)i*i*(i+#|

Boutputrule.tx仁遲事本文件㈢編輯㈢格式9)查看遡幫助凹pleaseinputtherightsentence(endwith#)：E->TE‘t-》ftF->iT->問(wèn)F->iT-冶E->TE，t->ft"F->i『-〉eE‘-〉+TE'T->FT5(〉isnotmatching,error!3、輸入一個(gè)無(wú)#結(jié)束的錯(cuò)誤句子:診inputsenterKe.txt-12爭(zhēng)本文件㈢編輯?格式9）查看2幫肋?i*i*iBoutputrule.txt?記爭(zhēng)本文件㈢編輯⑥格式9）查看⑷幫助凹bTFTFTFTEinputtherightsentence(endwith#)：E~>TEbTFTFTFTEsignalofU.fail!代碼:#include<iostream>#include<fstream>usingnamespacestd;0}0}#include<string>chara[10];intadvance=0；voidE();voidEI();voidT();//字符串的存入//字符串小標(biāo)，表示使IF指向下一輸入符號(hào)//功能識(shí)別函數(shù)，表示規(guī)則E->TE,//功能識(shí)別函數(shù)，表示規(guī)則E'->+TE‘/e//功能識(shí)別函數(shù)，表示規(guī)則T->FT‘ifstreamimport(Hinputsentence.txtn);ofstreamexport(，zoutputrule?txt");voidTl()； //功能識(shí)別函數(shù)，表示規(guī)則T—XFT'/voidF();intmain()//功能識(shí)別函數(shù)，表示規(guī)則F->(E)/i//主函數(shù)吃xport<</zp1easeinputtherightsentence(endwith#) /輸入提示import?a;E(); //從首個(gè)推導(dǎo)式E開(kāi)始if((a[advance]—#'))export<<Z/Thesentenceisright,success!\n"；e1seexport?，，Nothesignalof#,fail!\n";°return0;}VOidE() //功能識(shí)別函數(shù){export?，/E->TE,\n';TO;E10;}voidE1(){if(a[advance]二二'){export?，，E,->+TE,\nH； //輸出使用E‘規(guī)則0advance++; //如果是”，則讀取下一字符T();〃根據(jù)E'—>+TE規(guī)則右部符號(hào)串的順序，調(diào)用其他非終結(jié)符的規(guī)則oEl();eIseexport?，，Er~>￡\n";}voidT()export?，，T->FT,\rT;F()；〃根據(jù)T—>FT規(guī)則右部符號(hào)串的順序，調(diào)用其他非終結(jié)符的規(guī)則T10;}voidT1(){if(a[advance]==? ) //如果是，則讀取下一字符{export<〈"T->*FT，\n"；advance++;F0;//根據(jù)T‘-XFT'規(guī)則右部符號(hào)串的順序，調(diào)用其他非終結(jié)符的規(guī)則呵1();}elseexport?，ZT"—>e\n";}voidF(){if(a[advance]=='i，) //如果是“i”,則讀取下一字符{export?，，F(xiàn)—>i\nz，；advance++；}e1seif(a[advance]=‘(')〃如果是“(J則讀取下一字符{。advance++；E(); //根據(jù)F-XE)規(guī)則右部符號(hào)串的順序,調(diào)用非終結(jié)符E的規(guī)則if(a[advance]=')'){Q export?，zF—>(E)\nH;advance++;ooo)Qelse{0 export<<，z\n()isnotmatching,error!\nM;exit(0);〃正常結(jié)束程序運(yùn)行}}else{export<<n\n()isnotmatehing,error!\n";exit(O)； 〃正常結(jié)束程序運(yùn)行六、心得體會(huì)：一個(gè)星期的課程設(shè)計(jì)，當(dāng)中有苦也有樂(lè)，但從苦樂(lè)中我學(xué)到了很多東西。通過(guò)這次課程設(shè)計(jì)我看到了自己的與別人的差距，有很多我自己不明白的地方別人都會(huì)。當(dāng)我自己一開(kāi)始進(jìn)行遞歸下降分析程序的課程設(shè)計(jì)時(shí)，我發(fā)現(xiàn)我有好多相關(guān)的小知識(shí)點(diǎn)還不太熟悉，于是我在結(jié)合書本和圖書館相關(guān)資料基礎(chǔ)上，將課堂學(xué)習(xí)的知識(shí)予以真正的吸收和應(yīng)用，功夫不負(fù)有心人，我最終琢磨出了解決該設(shè)計(jì)題的基本思路和方法。這次課程設(shè)計(jì)，不僅鞏固了課堂知識(shí)，很好的復(fù)習(xí)了一下編譯原理所學(xué)的內(nèi)容，而且提高了自己的上機(jī)實(shí)踐能力，有效的和實(shí)際結(jié)合在了一起，加強(qiáng)了我的動(dòng)手、思考、解決問(wèn)題的能力，并擴(kuò)展了所學(xué)知識(shí)。同時(shí)在設(shè)計(jì)過(guò)程中也發(fā)現(xiàn)了我的許多不足之處，比如對(duì)以前所學(xué)的知識(shí)理解的不夠深刻，掌握的不夠牢固。此外，因?yàn)樵O(shè)計(jì)程序的各項(xiàng)流程需要心靜下來(lái)慢慢思考，所以克服了最近比較浮躁的心態(tài)，同時(shí)也讓自己充實(shí)了很多。在設(shè)計(jì)過(guò)程中也遇到了一些問(wèn)題，比如編寫程序時(shí)，每讀入一個(gè)字符，要執(zhí)行相應(yīng)的遞歸函數(shù)，因?yàn)檎{(diào)用過(guò)程中有再次調(diào)用，我有好兒次把函數(shù)的調(diào)用搞混，導(dǎo)致得出的結(jié)果不是我想要的。所以要在草稿紙上先畫出程序的流程圖，理順各子程序之間的調(diào)用關(guān)系，才能避免程序出錯(cuò)。還有不僅要知道文法要改為L(zhǎng)L(1)文法，還要明白為什么要改，修