編譯原理課程設(shè)計(jì) LL遞歸下降分析器

1、仲愷農(nóng)業(yè)技術(shù)學(xué)院編譯原理課程設(shè)計(jì)課程設(shè)計(jì)題目 ：LL(1)遞歸下降分析器姓 名 ：院（系） ： 專業(yè)班級(jí) ：學(xué) 號(hào) ： 指導(dǎo)教師 ： 設(shè)計(jì)日期 ：目 錄1、需求分析12、概要設(shè)計(jì)23、詳細(xì)設(shè)計(jì)34、測(cè)試分析85、用戶手冊(cè)96、課程總結(jié)97、參考文獻(xiàn)10題目：LL（1）遞歸下降分析器1、需求分析語(yǔ)法分析是編譯過(guò)程的核心部分。語(yǔ)法分析器的任務(wù)是識(shí)別和處理比單詞更大的語(yǔ)法單位。如：程序設(shè)計(jì)語(yǔ)言中的表達(dá)式，各種說(shuō)明和語(yǔ)句乃至全部源程序，指出其中的語(yǔ)法錯(cuò)誤；必要時(shí)，可生成內(nèi)部形式，便于下一階段處理。我們知道，語(yǔ)言的語(yǔ)法結(jié)構(gòu)是用上下文無(wú)關(guān)文法描述的。按照語(yǔ)法分析樹(shù)的建立方法，我們可以粗略地把語(yǔ)法分析辦法分

2、成兩類，一類是自上而下分析，另一類是自下而上分析法。而自上而下這種方法是帶“回溯”的，且存在許多困難和缺點(diǎn)。首先，是文法的左遞歸性問(wèn)題。一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符P且，含有左遞歸的文法使上述的自上而下的分析過(guò)程陷入無(wú)限循環(huán)。即，當(dāng)試圖用P去匹配輸入串時(shí)，我們會(huì)發(fā)現(xiàn)，在沒(méi)有識(shí)別任何輸入符號(hào)的情況下，有得重新要求P去進(jìn)行新的匹配。因此，使用自上而下分析法必須消除文法的左遞歸性。其次，由于回溯，就碰到一大堆麻煩問(wèn)題。如果我們走了一大段錯(cuò)路，最后必須回頭，那么，就應(yīng)把已經(jīng)做的一大堆語(yǔ)義工作（指中間代碼產(chǎn)生工作和各種表格的簿記工作）推倒重來(lái)。這些事情既麻煩又費(fèi)時(shí)間，所以，最好應(yīng)設(shè)法消除回溯

3、。第三，在自上而下分析過(guò)程中，當(dāng)一個(gè)非終結(jié)符用某一候選匹配成功時(shí)，這種成功可能僅是暫時(shí)的。第四，當(dāng)最終報(bào)告分析不成功時(shí)，我們難于知道輸入串中出錯(cuò)的確切位置。最后，由于帶回溯的自上而下分析實(shí)際上采用了一種窮盡一切可能的試探法，因此，效率很低，代價(jià)極高。嚴(yán)重的低效使得這種分析法只有理論意義，而在實(shí)踐上價(jià)值不大。由于上述原因，我們需要把原算術(shù)表達(dá)式改寫為L(zhǎng)L(1)文法，LL(1)文法的文法條件如下：文法不含左遞歸。對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首集符兩兩不相交。即，若，則 對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含，則LL(1)中的第一個(gè)L表示從左到右掃描輸入串，第二個(gè)L表示

4、最左推導(dǎo)，1表示分析時(shí)每一步只需向前查看一個(gè)符號(hào)。當(dāng)一個(gè)文法滿足LL(1)條件時(shí)，我們就可以為它構(gòu)造一個(gè)不帶回溯的自上而下分析程序，這個(gè)分析程序是由一組遞歸過(guò)程組成的，每個(gè)過(guò)程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。2、概要設(shè)計(jì)編程實(shí)現(xiàn)給定算術(shù)表達(dá)式的遞歸下降分析器。算術(shù)表達(dá)式文法如下： E->E+T|E-T|TT->T*F|T/F|FF->(E)| i首先改寫文法為L(zhǎng)L(1)文法；然后為每一個(gè)非終結(jié)符，構(gòu)造相應(yīng)的遞歸過(guò)程，過(guò)程的名字表示規(guī)則左部的非終結(jié)符；過(guò)程體按規(guī)則右部符號(hào)串的順序編寫。上述算法表達(dá)式文法屬于比較典型的遞歸下降語(yǔ)法分析。需要先將原算術(shù)

5、表達(dá)式方法改寫為L(zhǎng)L(1)文法為：E->TEE->+TE|-TE| T->FTT->*FT|/FT| F->(E)| i然后再為每個(gè)非終結(jié)符設(shè)計(jì)一個(gè)對(duì)應(yīng)的函數(shù)，通過(guò)各函數(shù)之間的遞歸調(diào)用從而實(shí)現(xiàn)遞歸下降語(yǔ)法分析的功能。具體方法為：（1）當(dāng)遇到終結(jié)符a時(shí)，則編寫語(yǔ)句If(當(dāng)前讀到的輸入符號(hào)=a)讀入下一個(gè)輸入符號(hào)（2）當(dāng)遇到非終結(jié)符A時(shí)，則編寫語(yǔ)句調(diào)用A()。（3）當(dāng)遇到A->規(guī)則時(shí)，則編寫語(yǔ)句If(當(dāng)前讀到的輸入符號(hào)不屬于Follow(A) error()（4）當(dāng)某個(gè)非終結(jié)符的規(guī)則有多個(gè)候選式時(shí)，按LL(1)文法的條件能唯一地選擇一個(gè)候選式進(jìn)行推導(dǎo).遞歸下降子

6、程序流程圖：圖1遞歸下降子程序流程圖3、詳細(xì)設(shè)計(jì)#include<iostream.h>char inputstream50; /存儲(chǔ)輸入句子int temp=0; /數(shù)組下標(biāo)int right; /判斷輸出信息void e();void e1();void t();void t1();void f();void main()right=1;cout<<"-"<<endl;cout<<"請(qǐng)輸入您要分析的字符串以#結(jié)束（為空字符）:"<<endl;cin>>inputstream;co

7、ut<<"-"<<endl;cout<<endl;cout<<"開(kāi)始進(jìn)行語(yǔ)法分析"<<endl;e();if(inputstreamtemp='#')&&right)cout<<"分析成功"<<endl;elsecout<<"分析失敗"<<endl;void e()cout<<"E->TE'"<<endl;t();e1(

8、);void e1()if(inputstreamtemp='+')cout<<"E'->+TE'"<<endl;temp+;t();e1();else if(inputstreamtemp='-')cout<<"E'->-TE'"<<endl;temp+;t();e1();else if(inputstreamtemp!='#'|inputstreamtemp!=')')cout<<&q

9、uot;T'->"<<endl;return;elseright=0;void t()cout<<"T->FT'"<<endl;f();t1();void t1()if(inputstreamtemp='*')cout<<"T'->*FT'"<<endl;temp+;f();t1();else if(inputstreamtemp='/')cout<<"T'->/FT&

10、#39;"<<endl;temp+;f();t1();else if(inputstreamtemp!='#'&&inputstreamtemp!=')'&&inputstreamtemp!='+'&&inputstreamtemp!='-')cout<<"T'->"<<endl;right=0;void f()if(inputstreamtemp='i')cout<<&quo

11、t;F->i"<<endl;temp+;elseif(inputstreamtemp='(')cout<<"F->(E)"<<endl;temp+;e();if(inputstreamtemp=')')cout<<"F->(E)"<<endl;temp+;elseright=0;else right=0;4、測(cè)試分析圖2 測(cè)試分析成功圖3 測(cè)試分析失敗5、用戶手冊(cè)開(kāi)發(fā)工具：開(kāi)發(fā)環(huán)境：windows XP操作系統(tǒng)運(yùn)行環(huán)境：windows

12、9x,windows NT,Windows 2000,windows XP注意：輸入時(shí)，程序最多只能接受50個(gè)字符，輸入完算術(shù)表達(dá)式后要以“#”號(hào)結(jié)束。6、課程總結(jié)通過(guò)一個(gè)星期的努力，終于把編譯原理課程設(shè)計(jì)給完成了。我覺(jué)得編譯原理這門課是一門非常難學(xué)的課程，它涉及文法、詞法分析、語(yǔ)法分析屬性文法和語(yǔ)義分析等等一系列內(nèi)容，課本里的內(nèi)容和定義也非常的抽象且枯燥。如果上課沒(méi)有好好的認(rèn)真聽(tīng)課，自己獨(dú)自學(xué)習(xí)就感到非常的吃力，而且效果也不好。本人因?yàn)樯险n無(wú)法做到打醒十二分專心聽(tīng)課，經(jīng)常會(huì)分神，所以學(xué)習(xí)的效果也不怎么好。這也給做編譯原理課程設(shè)計(jì)帶來(lái)了困難。本次課程設(shè)計(jì)，我選的課程設(shè)計(jì)題目是LL(1)遞歸下降

13、分析器，這個(gè)題目涉及的內(nèi)容有關(guān)課本第四章 語(yǔ)法分析自上而下分析里面的內(nèi)容。在開(kāi)始動(dòng)手對(duì)題目進(jìn)行設(shè)計(jì)和編程之前，我重復(fù)的仔細(xì)認(rèn)真的閱讀和理解課本第四章里面的內(nèi)容，弄懂自上而下分析面臨的問(wèn)題、何謂左遞歸，搞清楚如何消除左遞歸、如何消除回溯、提左因子，理解構(gòu)造LL(1)文件需要什么條件。雖然這花費(fèi)了一定的時(shí)間和精力，但那點(diǎn)付出也是值得的，通過(guò)復(fù)習(xí)讓我加深理解了有關(guān)自上而下語(yǔ)法分析的內(nèi)容，而且也為用高級(jí)語(yǔ)言實(shí)現(xiàn)遞歸下降分析器帶來(lái)便利。在用C+編程時(shí)，基本上沒(méi)有遇到什么困難，只需把所有遞歸過(guò)程都寫出就行了。但是要注意的是，在編寫代碼時(shí)，要根據(jù)LL(1)文法的工作原理去設(shè)計(jì)。通過(guò)本次課程設(shè)計(jì)清楚地了解到遞歸下降分析法的優(yōu)缺點(diǎn)，其優(yōu)點(diǎn)是簡(jiǎn)單、直觀，易于構(gòu)造分析程序。缺點(diǎn)是對(duì)文法要求高，必須是LL(1)文法，同時(shí)由于遞歸調(diào)用較多，影響分析器的效率。課程設(shè)計(jì)雖然只有短短的一周，但讓我認(rèn)識(shí)到學(xué)習(xí)好編譯原理，是對(duì)程序設(shè)計(jì)和編譯的一個(gè)很好的進(jìn)化橋梁和奠基石。今后學(xué)習(xí)的日子還很長(zhǎng)，希望通過(guò)這次編譯原理的課程設(shè)計(jì)，不僅對(duì)編程語(yǔ)言的進(jìn)一步復(fù)習(xí)，還是對(duì)更深層次的學(xué)習(xí)作一個(gè)簡(jiǎn)單的準(zhǔn)備。編程的能力不是一朝一夕能鍛煉出來(lái)，堅(jiān)持學(xué)習(xí)，堅(jiān)持編程的學(xué)習(xí)，多看，多編是最好的學(xué)習(xí)和提高方法。通過(guò)本次編譯原理課