《編譯原理》課程設計DOWHILE循環(huán)語句的翻譯程序設計（LL（1）法、輸出三地址表示）

1、學 號： 課 程 設 計題 目編譯原理學 院計算機科學與技術專 業(yè)計算機科學與技術班 級姓 名指導教師2年月日課程設計任務書學生姓名： 專業(yè)班級： 指導教師： 工作單位： 題目: do-while循環(huán)語句的翻譯程序設計（ll（1）法、輸出三地址表示）初始條件：理論：學完編譯課程，掌握一種計算機高級語言的使用。實踐：計算機實驗室提供計算機及軟件環(huán)境。如果自己有計算機可以在其上進行設計。要求完成的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求）（1） 寫出符合給定的語法分析方法的文法及屬性文法。（2） 完成題目要求的中間代碼三地址表示的描述。（3） 寫出給定的語法分析方法的

2、思想，完成語法分析和語義分析程序設計。（4） 編制好分析程序后，設計若干用例，上機測試并通過所設計的分析程序。（5） 設計報告格式按附件要求書寫。課程設計報告書正文的內容應包括：1 系統(tǒng)描述（問題域描述）；2 文法及屬性文法的描述；3 語法分析方法描述及語法分析表設計；4 按給定的題目給出中間代碼形式的描述及中間代碼序列的結構設計；5 編譯系統(tǒng)的概要設計；6 詳細的算法描述（流程圖或偽代碼）；7 軟件的測試方法和測試結果；8 研制報告（研制過程，本設計的評價、特點、不足、收獲與體會等）；9 參考文獻（按公開發(fā)表的規(guī)范書寫）。時間安排：設計安排一周：周1、周2：完成系統(tǒng)分析及設計。周3、周4：完

3、成程序調試及測試。周5：撰寫課程設計報告。設計驗收安排：設計周的星期五第1節(jié)課開始到實驗室進行上機驗收。設計報告書收取時間：設計周的次周星期一上午10點。指導教師簽名： 2011年 12月 23日系主任（或責任教師）簽名： 2011年 12月 23日do-while語句的翻譯程序設計(ll（1）文法輸出3地址表達式)1課設的描述1.1課設要求首先按照課程設計的要求，寫一個能識別do-while循環(huán)語句的文法，并使它符合ll(1)法的要求，按照這個文法編寫一個程序，該程序能識別輸入的語句是否符合do-while語句的文法，或者通過文法的開始符號能判斷是否能推導出該語句。程序應該包括詞法分析器，能

4、對輸入的語句進行詞法分析，對輸入的源程序從左到右進行掃描并將其分解為一個個的單詞符號。然后再對結果進行語法分析。詞法分析器應能識別關鍵字，標識符，常量，操作符等。該程序的語法分析器能對輸入的語法進行分析，判斷輸入語句能否滿足do-while循環(huán)語句的文法，如果不是則提示錯誤，如果滿足do-while循環(huán)語句文法，判斷是否符合ll(1)法，運用最左推導對其進行分析，看能否通過開始符號推導出來。將語法和語義分析的結果用輸出三地址形式表示出來。1.2課設中所用概念1) 詞法分析：輸入源程序，對構成源程序的字符串進行掃描和分解，識別出一個個的單詞符號：關鍵字(do,while)、標識符、常量、操作符等

5、。2) 語法分析：在詞法分析的基礎上，根據(jù)語法規(guī)則，把單詞符號串分解成各類語法單位。3) 語義分析與中間代碼產(chǎn)生：對語法分析所識別出的各類語法范疇，分析其含義，并進行初步翻譯(產(chǎn)生中間代碼)。4) ll(1)文法：ll(1)文法是一種自上而下的語法分析方法。第一個l是自上而下的分析，第二個l是從最左單詞開始分析，1代表只通過下1個單詞分析需要用到的語法。5) 預測分析程序：實現(xiàn)ll(1)法分析的一種有效方法，使用一張預測分析表和一個棧進行聯(lián)合控制。預測分析程序就是屬于這種類型的ll(1)分析器。2文法的描述2.1 do. while 語句文法描述k-dlws l-spp-;sp p-s-iqe

6、 e-tgg-+tg g-tgg- t-frr-*fr r-/frr- f-(e)f-i q-=q-非終結符集 vnk,l,p,s,g,r,e,f,q,t終結符集v* do,while,(,), ,+,-,*,/,i,=,;預測分析表i=+-*/()do;whilekdlwslspp;spsiqee-tgtgg+tg-tgtfrfrr*fr/frfi(e)q=3語法分析方法及中間代碼形式的描述3.1語法分析方法描述 ll(1)文法的定義： first 集： 設g=vt,vn,s,p是上下文無關文法 first()=a|=a,avt,v* 若a=，則規(guī)定first()，稱為first()為的開始

7、符號集或首符號集。 follow 集： 設g=vt,vn,s,p是上下文無關文法 follow(a)=a|s=a且avt,afirst(),v*t,v+ 若s=a,且=,則#follow(a) select 集: 給定上下文無關文法的產(chǎn)生式 a- avn,v* ,若,則select(a-)=first() 如果=,則select(a-)=(first()-)u follow(a). ll(1)文法: 一個上下文無關文法是ll(1)文法的充分必要條件是,對每個非終結符a的兩個不同的產(chǎn)生式,a- a-,滿足 select(a-)select(a-)= 其中,不能同時推導出空. 3.2 中間代碼形式

8、 三地址碼是由下面一般形式的語句構成的序列： x := y op z 其中，x y z為名字、常數(shù)或臨時變量；op代表運算符號。每個語句中只能有一個運算符。三地址碼類似于匯編語言代碼。語句可以帶有符號標號，而且存在各種控制流語句，本程序輸出中用到了：復制語句 x := y 條件轉移語句 if x relop y goto l /l為帶標號l的三地址語句無條件轉移語句 goto l /轉移到標號為l的三地址語句。4簡要的分析與概要設計 4.1 基本框架 輸入do while語句 詞法分析 語法語義分析 輸出三地址代碼 4.2 構成圖 4.2.1 主函數(shù)構成 詞法分析語法語義分析main( )控制

9、輸出三地址碼 4.3 各個部分構成整個工程分為四個部分,詞法分析部分,和語法分析部分,具體函數(shù)執(zhí)行部分,以及語義分析部分(最終部分在main函數(shù)中執(zhí)行的)lexical() - 程序的入口點，讀入輸入的待分析的字符串后,把其裝入一給定數(shù)組,先進行詞法分析，然后輸出生成的詞法分析結果。syntax() - 語法分析階段,利用wordanalyze() 中分析出的詞法,進行語法 分析.如果不是ll(1)文法則輸出語法出錯,僅對ll(1)文法的輸入進行分析.具體函數(shù)執(zhí)行部分 - 定義了各種操作函數(shù)以方便調用,入讀入輸入的句字的函數(shù),提 取字符函數(shù),判斷字符函數(shù)等等語義分析式部分-主函數(shù)中進行的輸出,

10、形式為給定句子的三地址表達式5算法描述5.1詞法分析的主要算法 void lexical() /詞法分析 int i,j,d;char ch;j=d=0;for(i=0;vari!=#;i+) /判斷關鍵字ch=vari;if(ch=d&vari+1=o)coutdot關鍵字endl;queuej+=d;i+=1;else if(ch=w) ch=vari+1;if(ch=h)ch=vari+2;if(ch=i)ch=vari+3;if(ch=l)ch=vari+4;if(ch=e)ch=vari+5;coutwhilet關鍵字endl;queuej+=w;i+=4;else if(index

11、(ch,vt)=0) /判斷標示符分隔符運算符if(ch!=&ch!=&ch!=(&ch!=)coutcht標識符endl;arr_id-1=ch;queuej+=i;else coutcht分隔符0)coutcht運算符endl;queuej+=ch;queuej=#;for(i=0;queuei!=#;i+)coutqueuei;coutendl;語法分析主要算法void syntax() /語法分析int n;count+;print();x=stacksp;a=queuefront;if(x=#&a=#)f=4;if(xz)if(x=a)sp-;front+;if(a!=i)if(a!

12、=d&a!=w&a!=;&a!=#)opr=index(a,vt);else if(a=;|a=w|a=#)opr=-2;coutta匹配endl;elseopd=c;couttarr_ic+匹配endl;else f=1; /字符不匹配,轉去出錯處理else int tx=index(x,vn);int ta=index(a,vt);n=mtxta;tdt+=mtxta;if(ta=-1)f=2;coutaendl; /字符沒有出現(xiàn)在產(chǎn)生式終結符集vt中,轉去出錯處理else if(n=-1)f=3; /沒有找到合適的候選產(chǎn)生式來做進一步推導,轉去出錯處理else /用產(chǎn)生式mtxta來做進

13、一步推導sp-;couttx;if(len(pn)!=0)for(int i=len(pn)-1;i=0;i-)stack+sp=pni;coutpnlen(pn)-1-i;coutendl;else cout空串endl;if(f=0)syntax();else tdt=-1;err(f); 具體執(zhí)行函數(shù)： len 求字符串長度 index 查找字符串中是否有ch 返回ch位置 err 輸出錯誤和錯誤原因 print 打印 6上機測試6.1測試方法在visual c+ 6.0 下調試并通過.輸入不同的語句進行測試，測試的主要目的是看程序能否正確判斷條件語句是否正確，賦值語句的格式有沒有錯誤以

14、及最后結果輸出的三地址是否正確。6.2測試過程和結果現(xiàn)用一下用例來測試本程序：測試1：輸入一個最簡單的do while循環(huán)語句，正確輸入看能否得出正確結果，程序運行結果如下：測試2：輸入一錯誤語句查看結果：如下程序不能認出so所以程序不能編譯。7 結果7.1研制過程 這次課程設計要求我用ll（1）分析法來翻譯do-while循環(huán)語句，這就要求對編譯原理語法分析方面有一定的了解，熟悉各種語法分析的方法，特別是本題中所要求的ll（1）法，需要弄清楚ll（1）法的概念，過程，需要注意的地方等。另外還需要對編程語言聯(lián)系，才能編出符合要求的程序?？吹筋}目以后，首先將編譯原理書上相關知識仔細看了一遍，不清

15、楚的地方搞清楚特別是關系程序設計的部分。然后參閱了編譯程序構造方面的書籍，對編譯程序的實現(xiàn)有了一定的了解。最后是從編程語言方面，根據(jù)編譯原理方面的知識，找出實現(xiàn)課程設計要求的解決方式，然后編寫程序來實現(xiàn)。編好以后，對其測試，找出其中存在的問題，不過程序不能像c+一樣很好的實現(xiàn)對do-while的翻譯，有些復雜的輸入還是不能識別。7.2 本次課程設計的缺點 這個對do-while的編譯程序不能像c+那樣完美的編譯，不能識別太過復雜的語句，循環(huán)的嵌套，帶小括號的運算是這次課程設計的缺點。7.3本次課程設計的收獲課程設計是不同于上機實驗的一種更考驗學生能力的方式，由于每個人的課設題目都不一樣所以很大

16、程度的消除了學生的依賴感。本次課設我學到了很多。首先,鞏固了編譯原理的知識。為了做好這次課程設計,要求我必須重新復習一遍編譯的課本,特別是需要實現(xiàn)的那部分原理。除此之外,還有上網(wǎng)查詢一些編譯資料，和一些實際問題實現(xiàn)的例子，通過看別人實現(xiàn)的過程，學習實現(xiàn)的一些基本思路。這次課程設計的題目是用ll（1）進行do-while循環(huán)語句的語法分析,并輸出三地址表達式.設計的特點是利用定義每個終極符和非終極符之間優(yōu)先關系,來進行符號的移進與規(guī)約,如果棧頂符號優(yōu)先級低于該單詞，繼續(xù)讀入；若棧頂符號優(yōu)先級高于或等于讀入符號，則找句柄進行歸約，找不到句柄就繼續(xù)讀入。這樣使得程序簡化,只需定義一個棧用來存放移進的

17、字符,然后用棧頂指針指向它后與待移進字符比較優(yōu)先級即可,設計簡單.此設計的嚴重不足是只能進行一個固定句子的詞法與語法分析,因為在定義優(yōu)先關系時已固定了do,和while的每個字符之間的優(yōu)先關系,且賦值表達式和條件式也已固定,所以只能進行本程序已約定好的語句.最大的收獲是在提出一個難題以后，如果能比較順手的解決的話，那是一件比較開心的事。只是有些時候越想問題就會越多，也越難解決，那就得慢慢調試，慢慢推導了。相信只要想得出，就能調得出，當然耐心是很重要的，花在上面的時間也是要多一點的。其次,通過本次課程設計檢驗了我的數(shù)據(jù)結構的知識。因為在語法分析中需要用到數(shù)據(jù)結構的一些知識,這就敦促我去重新溫習數(shù)

18、據(jù)結構中相關的知識。8參考文獻(1)編譯原理（第2版） 清華大學出版社 張素琴 呂映芝 等人著 本科生課程設計成績評定表班級：姓名：學號：序號評分項目滿分實得分1學習態(tài)度認真、遵守紀律102設計分析合理性103設計方案正確性、可行性、創(chuàng)造性204設計結果正確性405設計報告的規(guī)范性106設計驗收10總得分/等級評語：注：最終成績以五級分制記。優(yōu)（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下為不及格指導教師簽名：2012 年 1月日源代碼#include#define max 100 char x,a;char vn11=k,l,p,s,e,g,t,

19、r,f,q,0;char vt15=i,=,+,-,*,/,(,),d,w,;,#,0;char p186=dlws0,sp0,;sp0,0,iqe0,tg0,+tg0,-tg0,0,fr0, *fr0,/fr0,0,(e)0,i0,=0,0;char stackmax;char queuemax;int sp,front;int m1014= -1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,-1,-1,-1, 1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 3, 2,-1,

20、 4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 5,-1,-1,-1,-1,-1,-1,-1, 5,-1,-1,-1,-1,-1,-1,-1,-1,-1, 6, 7,-1,-1,-1,-1,-1, 8, 8, 8, 9,-1,-1,-1,-1,-1,-1,-1, 9,-1,-1,-1,-1,-1,-1,-1,-1,-1,12,12,10,11,-1,-1,-1,12,12,12,14,-1,-1,-1,-1,-1,-1,-1,13,-1,-1,-1,-1,-1,-1,15,16,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,;int f

21、=0;int count=0;int c=0;char arr_imax;char varmax;int tdmax; /輸出產(chǎn)生式序列int t=0;int opd=-1;int opr=-1;int id=0;int d=0;char arrmax10;/存放待輸出的三地址int len(char str) /求字符串長度int i=0;while(stri!=0)i+;return i;int index(char ch,char str) /查找字符串中是否有ch 返回ch位置int i=0;while(stri!=0)if(ch!=stri)i+;else break;if(stri

22、=0)return -1;return i;void err(int n) /輸出錯誤和錯誤原因if(n=1)cout字符不匹配endl;else if(n=2)cout字符沒有出現(xiàn)在產(chǎn)生式終結符集vt中endl;else if(n=3)cout沒有找到合適的候選產(chǎn)生式來做進一步推導endl;else cout該句子是文法語言的句子！endl;void print()cout(;if(count10)cout0;coutcount);int i;for(i=0;i=sp;i+)coutstacki;for(;i=20;i+)cout ;for(i=0;ifront;i+)cout ;for(;

23、queuei!=#;i+)coutqueuei;coutqueuei;for(;i=20;i+)cout ;void semantic()int j=0,k;while(varj!=0)if(varj=)k=0;for(j=j-1;(varj!=;)&(varj!=);j+,k+)arrdk=varj;arrdk=0;d+;j-;if(varj=)k=0;for(j=j-1;varj!=;j+,k+)arrdk=varj;arrdk=0;d+;j-;j+;void syntax() /語法分析int n;count+;print();x=stacksp;a=queuefront;if(x=#&

24、a=#)f=4;if(xz)if(x=a)sp-;front+;if(a!=i)if(a!=d&a!=w&a!=;&a!=#)opr=index(a,vt);else if(a=;|a=w|a=#)opr=-2;coutta匹配endl;elseopd=c;couttarr_ic+匹配endl;else f=1; /字符不匹配,轉去出錯處理else int tx=index(x,vn);int ta=index(a,vt);n=mtxta;tdt+=mtxta;if(ta=-1)f=2;coutaendl; /字符沒有出現(xiàn)在產(chǎn)生式終結符集vt中,轉去出錯處理else if(n=-1)f=3;

25、/沒有找到合適的候選產(chǎn)生式來做進一步推導,轉去出錯處理else /用產(chǎn)生式mtxta來做進一步推導sp-;couttx;if(len(pn)!=0)for(int i=len(pn)-1;i=0;i-)stack+sp=pni;coutpnlen(pn)-1-i;coutendl;else cout空串endl;if(f=0)syntax();else tdt=-1;err(f);void lexical() /詞法分析 int i,j,d;char ch;j=d=0;for(i=0;vari!=#;i+)ch=vari;if(ch=d&vari+1=o)coutdot關鍵字endl;queuej+=d;i+=1;else if(ch=w)ch=vari+1;if(ch=h)ch=vari+2;if(ch=i)ch=vari+3;if(ch=l)ch=vari+4;if(