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

1、<p><b>　　編譯原理課程設(shè)計(jì)</b></p><p>　　課程設(shè)計(jì)題目 ：LL(1)遞歸下降分析器</p><p><b>　　姓 名 ：</b></p><p><b>　　院（系） ： </b></p><p><b>　　專業(yè)班級(jí) ：&

2、lt;/b></p><p>　　學(xué) 號(hào) ： </p><p><b>　　指導(dǎo)教師 ： </b></p><p><b>　　設(shè)計(jì)日期 ：</b></p><p><b>　　目 錄</b></p><p><b>

3、　　1、需求分析1</b></p><p><b>　　2、概要設(shè)計(jì)2</b></p><p><b>　　3、詳細(xì)設(shè)計(jì)3</b></p><p><b>　　4、測(cè)試分析8</b></p><p><b>　　5、用戶手冊(cè)9</b>

4、</p><p><b>　　6、課程總結(jié)9</b></p><p><b>　　7、參考文獻(xiàn)10</b></p><p>　　題目：LL（1）遞歸下降分析器</p><p><b>　　1、需求分析</b></p><p>　　語法分析是編譯過程的

5、核心部分。語法分析器的任務(wù)是識(shí)別和處理比單詞更大的語法單位。如：程序設(shè)計(jì)語言中的表達(dá)式，各種說明和語句乃至全部源程序，指出其中的語法錯(cuò)誤；必要時(shí)，可生成內(nèi)部形式，便于下一階段處理。</p><p>　　我們知道，語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的。按照語法分析樹的建立方法，我們可以粗略地把語法分析辦法分成兩類，一類是自上而下分析，另一類是自下而上分析法。而自上而下這種方法是帶“回溯”的，且存在許多困難和缺點(diǎn)。

6、</p><p>　　首先，是文法的左遞歸性問題。一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符P且，含有左遞歸的文法使上述的自上而下的分析過程陷入無限循環(huán)。即，當(dāng)試圖用P去匹配輸入串時(shí)，我們會(huì)發(fā)現(xiàn)，在沒有識(shí)別任何輸入符號(hào)的情況下，有得重新要求P去進(jìn)行新的匹配。因此，使用自上而下分析法必須消除文法的左遞歸性。</p><p>　　其次，由于回溯，就碰到一大堆麻煩問題。如果我們走了一大段錯(cuò)路，最后

7、必須回頭，那么，就應(yīng)把已經(jīng)做的一大堆語義工作（指中間代碼產(chǎn)生工作和各種表格的簿記工作）推倒重來。這些事情既麻煩又費(fèi)時(shí)間，所以，最好應(yīng)設(shè)法消除回溯。</p><p>　　第三，在自上而下分析過程中，當(dāng)一個(gè)非終結(jié)符用某一候選匹配成功時(shí)，這種成功可能僅是暫時(shí)的。</p><p>　　第四，當(dāng)最終報(bào)告分析不成功時(shí)，我們難于知道輸入串中出錯(cuò)的確切位置。</p><p>　　最

8、后，由于帶回溯的自上而下分析實(shí)際上采用了一種窮盡一切可能的試探法，因此，效率很低，代價(jià)極高。嚴(yán)重的低效使得這種分析法只有理論意義，而在實(shí)踐上價(jià)值不大。</p><p>　　由于上述原因，我們需要把原算術(shù)表達(dá)式改寫為L(zhǎng)L(1)文法，LL(1)文法的文法條件如下：</p><p><b>　　文法不含左遞歸。</b></p><p>　　對(duì)于文法中

9、每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首集符兩兩不相交。即，若，則 </p><p>　　對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含ε，則</p><p>　　LL(1)中的第一個(gè)L表示從左到右掃描輸入串，第二個(gè)L表示最左推導(dǎo)，1表示分析時(shí)每一步只需向前查看一個(gè)符號(hào)。當(dāng)一個(gè)文法滿足LL(1)條件時(shí)，我們就可以為它構(gòu)造一個(gè)不帶回溯的自上而下分析程序，這個(gè)分析程序是由一組遞歸過程組成

10、的，每個(gè)過程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。</p><p><b>　　2、概要設(shè)計(jì)</b></p><p>　　編程實(shí)現(xiàn)給定算術(shù)表達(dá)式的遞歸下降分析器。</p><p>　　算術(shù)表達(dá)式文法如下： </p><p>　　E-->E+T|E-T|T</p><p&g

11、t;　　T-->T*F|T/F|F</p><p>　　F-->(E)| i</p><p>　　首先改寫文法為L(zhǎng)L(1)文法；然后為每一個(gè)非終結(jié)符，構(gòu)造相應(yīng)的遞歸過程，過程的名字表示規(guī)則左部的非終結(jié)符；過程體按規(guī)則右部符號(hào)串的順序編寫。</p><p>　　上述算法表達(dá)式文法屬于比較典型的遞歸下降語法分析。需要先將原算術(shù)表達(dá)式方法改寫為L(zhǎng)L(1)文法為

12、：</p><p><b>　　E-->TE’</b></p><p>　　E’-->+TE’|-TE’| ε</p><p><b>　　T-->FT’</b></p><p>　　T’-->*FT’|/FT’| ε</p><p>　　F-->

13、;(E)| i</p><p>　　然后再為每個(gè)非終結(jié)符設(shè)計(jì)一個(gè)對(duì)應(yīng)的函數(shù)，通過各函數(shù)之間的遞歸調(diào)用從而實(shí)現(xiàn)遞歸下降語法分析的功能。</p><p><b>　　具體方法為：</b></p><p>　　（1）當(dāng)遇到終結(jié)符a時(shí)，則編寫語句</p><p>　　If(當(dāng)前讀到的輸入符號(hào)==a)讀入下一個(gè)輸入符號(hào)</p

14、><p>　?。?）當(dāng)遇到非終結(jié)符A時(shí)，則編寫語句調(diào)用A()。</p><p>　?。?）當(dāng)遇到A-->ε規(guī)則時(shí)，則編寫語句</p><p>　　If(當(dāng)前讀到的輸入符號(hào)不屬于Follow(A)) error()</p><p>　　（4）當(dāng)某個(gè)非終結(jié)符的規(guī)則有多個(gè)候選式時(shí)，按LL(1)文法的條件能唯一地選擇一個(gè)候選式進(jìn)行推導(dǎo).</

15、p><p>　　遞歸下降子程序流程圖：</p><p>　　圖1遞歸下降子程序流程圖</p><p><b>　　3、詳細(xì)設(shè)計(jì)</b></p><p>　　#include<iostream.h></p><p>　　char inputstream[50]; //存儲(chǔ)輸入句子</

16、p><p>　　int temp=0; //數(shù)組下標(biāo)</p><p>　　int right; //判斷輸出信息</p><p><b>　　void e();</b></p><p>　　void e1();</p><p><b>　　void t();</b>&l

17、t;/p><p>　　void t1();</p><p><b>　　void f();</b></p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　right=1;</b></p>

18、<p>　　cout<<"---------------------------------------------------"<<endl;</p><p>　　cout<<"請(qǐng)輸入您要分析的字符串以#結(jié)束（^為空字符）:"<<endl;</p><p>　　cin>>inp

19、utstream;</p><p>　　cout<<"---------------------------------------------------"<<endl;</p><p>　　cout<<endl;</p><p>　　cout<<"開始進(jìn)行語法分析"<&

20、lt;endl;</p><p><b>　　e();</b></p><p>　　if((inputstream[temp]=='#')&&right)</p><p>　　cout<<"分析成功"<<endl;</p><p><b&g

21、t;　　else</b></p><p>　　cout<<"分析失敗"<<endl;</p><p><b>　　}</b></p><p><b>　　void e()</b></p><p><b>　　{</b>&l

22、t;/p><p>　　cout<<"E->TE'"<<endl;</p><p><b>　　t();</b></p><p><b>　　e1();</b></p><p><b>　　}</b></p>&

23、lt;p><b>　　void e1()</b></p><p><b>　　{</b></p><p>　　if(inputstream[temp]=='+')</p><p><b>　　{</b></p><p>　　cout<<&quo

24、t;E'->+TE'"<<endl;</p><p><b>　　temp++;</b></p><p><b>　　t();</b></p><p><b>　　e1();</b></p><p><b>　　}</

25、b></p><p>　　else if(inputstream[temp]=='-')</p><p><b>　　{</b></p><p>　　cout<<"E'->-TE'"<<endl;</p><p><b>　

26、　temp++;</b></p><p><b>　　t();</b></p><p><b>　　e1();</b></p><p><b>　　}</b></p><p>　　else if(inputstream[temp]!='#'||inp

27、utstream[temp]!=')')</p><p><b>　　{</b></p><p>　　cout<<"T'->^"<<endl;</p><p><b>　　return;</b></p><p><b&g

28、t;　　}</b></p><p><b>　　else</b></p><p><b>　　right=0;</b></p><p><b>　　}</b></p><p><b>　　void t()</b></p><

29、p><b>　　{</b></p><p>　　cout<<"T->FT'"<<endl;</p><p><b>　　f();</b></p><p><b>　　t1();</b></p><p><b&

30、gt;　　}</b></p><p><b>　　void t1()</b></p><p><b>　　{</b></p><p>　　if(inputstream[temp]=='*')</p><p><b>　　{</b></p>

31、<p>　　cout<<"T'->*FT'"<<endl;</p><p><b>　　temp++;</b></p><p><b>　　f();</b></p><p><b>　　t1();</b></p>

32、;<p><b>　　}</b></p><p>　　else if(inputstream[temp]=='/')</p><p><b>　　{</b></p><p>　　cout<<"T'->/FT'"<<endl;&l

33、t;/p><p><b>　　temp++;</b></p><p><b>　　f();</b></p><p><b>　　t1();</b></p><p><b>　　}</b></p><p>　　else if(inputs

34、tream[temp]!='#'&&inputstream[temp]!=')'&&inputstream[temp]!='+'&&inputstream[temp]!='-')</p><p><b>　　{</b></p><p>　　cout<&

35、lt;"T'->^"<<endl;</p><p><b>　　right=0;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　void f()<

36、/b></p><p><b>　　{</b></p><p>　　if(inputstream[temp]=='i')</p><p><b>　　{</b></p><p>　　cout<<"F->i"<<endl;<

37、/p><p><b>　　temp++;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(inputstream[temp]=='(')</p><p><b>

38、;　　{</b></p><p>　　cout<<"F->(E)"<<endl;</p><p><b>　　temp++;</b></p><p><b>　　e();</b></p><p>　　if(inputstream[temp

39、]==')')</p><p><b>　　{</b></p><p>　　cout<<"F->(E)"<<endl;</p><p><b>　　temp++;</b></p><p><b>　　}</b>&

40、lt;/p><p><b>　　else</b></p><p><b>　　right=0;</b></p><p><b>　　}</b></p><p>　　else right=0;</p><p><b>　　}</b><

41、;/p><p><b>　　4、測(cè)試分析</b></p><p><b>　　圖2 測(cè)試分析成功</b></p><p><b>　　圖3 測(cè)試分析失敗</b></p><p><b>　　5、用戶手冊(cè)</b></p><p>　　開發(fā)

42、工具：visual c++ 6.0</p><p>　　開發(fā)環(huán)境：windows XP操作系統(tǒng)</p><p>　　運(yùn)行環(huán)境：windows 9x,windows NT,Windows 2000,windows XP</p><p>　　注意：輸入時(shí)，程序最多只能接受50個(gè)字符，輸入完算術(shù)表達(dá)式后要以“#”號(hào)結(jié)束。</p><p><b

43、>　　6、課程總結(jié)</b></p><p>　　通過一個(gè)星期的努力，終于把編譯原理課程設(shè)計(jì)給完成了。我覺得編譯原理這門課是一門非常難學(xué)的課程，它涉及文法、詞法分析、語法分析屬性文法和語義分析等等一系列內(nèi)容，課本里的內(nèi)容和定義也非常的抽象且枯燥。如果上課沒有好好的認(rèn)真聽課，自己獨(dú)自學(xué)習(xí)就感到非常的吃力，而且效果也不好。本人因?yàn)樯险n無法做到打醒十二分專心聽課，經(jīng)常會(huì)分神，所以學(xué)習(xí)的效果也不怎么好。這

44、也給做編譯原理課程設(shè)計(jì)帶來了困難。</p><p>　　本次課程設(shè)計(jì)，我選的課程設(shè)計(jì)題目是LL(1)遞歸下降分析器，這個(gè)題目涉及的內(nèi)容有關(guān)課本第四章 語法分析——自上而下分析里面的內(nèi)容。在開始動(dòng)手對(duì)題目進(jìn)行設(shè)計(jì)和編程之前，我重復(fù)的仔細(xì)認(rèn)真的閱讀和理解課本第四章里面的內(nèi)容，弄懂自上而下分析面臨的問題、何謂左遞歸，搞清楚如何消除左遞歸、如何消除回溯、提左因子，理解構(gòu)造LL(1)文件需要什么條件。雖然這花費(fèi)了一定的時(shí)間

45、和精力，但那點(diǎn)付出也是值得的，通過復(fù)習(xí)讓我加深理解了有關(guān)自上而下語法分析的內(nèi)容，而且也為用高級(jí)語言實(shí)現(xiàn)遞歸下降分析器帶來便利。</p><p>　　在用C++編程時(shí)，基本上沒有遇到什么困難，只需把所有遞歸過程都寫出就行了。但是要注意的是，在編寫代碼時(shí)，要根據(jù)LL(1)文法的工作原理去設(shè)計(jì)。通過本次課程設(shè)計(jì)清楚地了解到遞歸下降分析法的優(yōu)缺點(diǎn)，其優(yōu)點(diǎn)是簡(jiǎn)單、直觀，易于構(gòu)造分析程序。缺點(diǎn)是對(duì)文法要求高，必須是LL(1)

46、文法，同時(shí)由于遞歸調(diào)用較多，影響分析器的效率。</p><p>　　課程設(shè)計(jì)雖然只有短短的一周，但讓我認(rèn)識(shí)到學(xué)習(xí)好編譯原理，是對(duì)程序設(shè)計(jì)和編譯的一個(gè)很好的進(jìn)化橋梁和奠基石。今后學(xué)習(xí)的日子還很長(zhǎng)，希望通過這次編譯原理的課程設(shè)計(jì)，不僅對(duì)編程語言的進(jìn)一步復(fù)習(xí)，還是對(duì)更深層次的學(xué)習(xí)作一個(gè)簡(jiǎn)單的準(zhǔn)備。編程的能力不是一朝一夕能鍛煉出來，堅(jiān)持學(xué)習(xí)，堅(jiān)持編程的學(xué)習(xí)，多看，多編是最好的學(xué)習(xí)和提高方法。</p><

47、;p>　　通過本次編譯原理課程設(shè)計(jì)，對(duì)面向?qū)ο蟮亩x又有了更深一步的理解，對(duì)編譯程序有了進(jìn)一步的理解，同時(shí)也認(rèn)識(shí)到自己各方面知識(shí)的薄弱點(diǎn)，以后在學(xué)習(xí)中也能有針對(duì)性對(duì)這方面進(jìn)行深入學(xué)習(xí)。學(xué)習(xí)更好的知識(shí)重在基礎(chǔ)，編譯原理的學(xué)習(xí)為我們提供非常好的橋梁和道路。</p><p><b>　　7、參考文獻(xiàn)</b></p><p>　　《編譯原理》　機(jī)械工業(yè)出版社出版<