編譯原理課程設計-LL(1)遞歸下降分析器(共12頁)

1、精選優(yōu)質文檔-傾情為你奉上仲愷農業(yè)技術學院編譯原理課程設計課程設計題目 ：LL(1)遞歸下降分析器姓 名 ：院（系） ： 專業(yè)班級 ：學 號 ： 指導教師 ： 設計日期 ：專心-專注-專業(yè)目 錄12389910題目：LL（1）遞歸下降分析器1、需求分析語法分析是編譯過程的核心部分。語法分析器的任務是識別和處理比單詞更大的語法單位。如：程序設計語言中的表達式，各種說明和語句乃至全部源程序，指出其中的語法錯誤；必要時，可生成內部形式，便于下一階段處理。我們知道，語言的語法結構是用上下文無關文法描述的。按照語法分析樹的建立方法，我們可以粗略地把語法分析辦法分成兩類，一類是自上而下分析，另一類是自下而

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

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

4、個符號。當一個文法滿足LL(1)條件時，我們就可以為它構造一個不帶回溯的自上而下分析程序，這個分析程序是由一組遞歸過程組成的，每個過程對應文法的一個非終結符。這樣的一個分析程序稱為遞歸下降分析器。2、概要設計編程實現(xiàn)給定算術表達式的遞歸下降分析器。算術表達式文法如下： E->E+T|E-T|TT->T*F|T/F|FF->(E)| i首先改寫文法為LL(1)文法；然后為每一個非終結符，構造相應的遞歸過程，過程的名字表示規(guī)則左部的非終結符；過程體按規(guī)則右部符號串的順序編寫。上述算法表達式文法屬于比較典型的遞歸下降語法分析。需要先將原算術表達式方法改寫為LL(1)文法為：E-&g

5、t;TEE->+TE|-TE| T->FTT->*FT|/FT| F->(E)| i然后再為每個非終結符設計一個對應的函數(shù)，通過各函數(shù)之間的遞歸調用從而實現(xiàn)遞歸下降語法分析的功能。具體方法為：（1）當遇到終結符a時，則編寫語句If(當前讀到的輸入符號=a)讀入下一個輸入符號（2）當遇到非終結符A時，則編寫語句調用A()。（3）當遇到A->規(guī)則時，則編寫語句If(當前讀到的輸入符號不屬于Follow(A) error()（4）當某個非終結符的規(guī)則有多個候選式時，按LL(1)文法的條件能唯一地選擇一個候選式進行推導.遞歸下降子程序流程圖：圖1遞歸下降子程序流程圖3、詳

6、細設計#include<iostream.h>char inputstream50; /存儲輸入句子int temp=0; /數(shù)組下標int right; /判斷輸出信息void e();void e1();void t();void t1();void f();void main()right=1;cout<<"-"<<endl;cout<<"請輸入您要分析的字符串以#結束（為空字符）:"<<endl;cin>>inputstream;cout<<"-&quo

7、t;<<endl;cout<<endl;cout<<"開始進行語法分析"<<endl;e();if(inputstreamtemp='#')&&right)cout<<"分析成功"<<endl;elsecout<<"分析失敗"<<endl;void e()cout<<"E->TE'"<<endl;t();e1();void e1()if(inputst

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

9、<<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'"<<end

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

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

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

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