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

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

2、lt;/b></p><p>　　學 號 ： </p><p><b>　　指導教師 ： </b></p><p><b>　　設計日期 ：</b></p><p><b>　　目 錄</b></p><p><b>

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

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

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

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

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

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

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

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

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

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

16、p><p>　　int temp=0; //數組下標</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<<"請輸入您要分析的字符串以#結束（^為空字符）:"<<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個字符，輸入完算術表達式后要以“#”號結束。</p><p><b

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

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

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

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

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