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

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

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

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

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

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

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

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

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

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

10、的，每個過程對應(yīng)文法的一個非終結(jié)符。這樣的一個分析程序稱為遞歸下降分析器。</p><p><b>　　2、概要設(shè)計</b></p><p>　　編程實現(xiàn)給定算術(shù)表達式的遞歸下降分析器。</p><p>　　算術(shù)表達式文法如下： </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>　　首先改寫文法為LL(1)文法；然后為每一個非終結(jié)符，構(gòu)造相應(yīng)的遞歸過程，過程的名字表示規(guī)則左部的非終結(jié)符；過程體按規(guī)則右部符號串的順序編寫。</p><p>　　上述算法表達式文法屬于比較典型的遞歸下降語法分析。需要先將原算術(shù)表達式方法改寫為LL(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>　　然后再為每個非終結(jié)符設(shè)計一個對應(yīng)的函數(shù)，通過各函數(shù)之間的遞歸調(diào)用從而實現(xiàn)遞歸下降語法分析的功能。</p><p><b>　　具體方法為：</b></p><p>　?。?）當(dāng)遇到終結(jié)符a時，則編寫語句</p><p>　　If(當(dāng)前讀到的輸入符號==a)讀入下一個輸入符號</p

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

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

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<<"請輸入您要分析的字符串以#結(jié)束（^為空字符）:"<<endl;</p><p>　　cin>>inp

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

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、測試分析</b></p><p><b>　　圖2 測試分析成功</b></p><p><b>　　圖3 測試分析失敗</b></p><p><b>　　5、用戶手冊</b></p><p>　　開發(fā)

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

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

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

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

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

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