編譯原理課程設(shè)計-DO-WHILE循環(huán)語句的翻譯程序設(shè)計LL1法、輸出三地址表示

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

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

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

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

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

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

7、rst()，稱為first()為的開始符號集或首符號集。 follow 集： 設(shè)g=vt,vn,s,p是上下文無關(guān)文法 follow(a)=a|s=a且avt,afirst(),v*t,v+ 若s=a,且=,則#follow(a) select 集: 給定上下文無關(guān)文法的產(chǎn)生式 a- avn,v* ,若,則select(a-)=first() 如果=,則select(a-)=(first()-)u follow(a). ll(1)文法: 一個上下文無關(guān)文法是ll(1)文法的充分必要條件是,對每個非終結(jié)符a的兩個不同的產(chǎn)生式,a- a-,滿足 select(a-)select(a-)= 其中,不

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

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

10、等語義分析式部分-主函數(shù)中進行的輸出,形式為給定句子的三地址表達(dá)式5算法描述5.1詞法分析的主要算法 void lexical() /詞法分析 int i,j,d;char ch;j=d=0;for(i=0;vari!=#;i+) /判斷關(guān)鍵字ch=vari;if(ch=d&vari+1=o)coutdot關(guān)鍵字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關(guān)鍵字endl;queuej+=w

11、;i+=4;else if(index(ch,vt)=0) /判斷標(biāo)示符分隔符運算符if(ch!=&ch!=&ch!=(&ch!=)coutcht標(biāo)識符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-;f

12、ront+;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; /字符不匹配,轉(zhuǎn)去出錯處理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)生式終結(jié)符集vt中,轉(zhuǎn)去出錯處理else if(n=-1)f=3; /沒有找到合適的候選產(chǎn)生式來做進一步推導(dǎo),轉(zhuǎn)去出錯處

13、理else /用產(chǎn)生式mtxta來做進一步推導(dǎo)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 下調(diào)試并通過.輸入不同的語句進行測試，測試的主要目的是看程序能否正確判斷條件語

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

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

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

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

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

19、vn11=k,l,p,s,e,g,t,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

20、,-1,-1,-1, 3, 2,-1, 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

21、,-1,-1,-1,-1,;int f=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+

22、;else break;if(stri=0)return -1;return i;void err(int n) /輸出錯誤和錯誤原因if(n=1)cout字符不匹配endl;else if(n=2)cout字符沒有出現(xiàn)在產(chǎn)生式終結(jié)符集vt中endl;else if(n=3)cout沒有找到合適的候選產(chǎn)生式來做進一步推導(dǎo)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;if

23、ront;i+)cout ;for(;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

24、=queuefront;if(x=#&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; /字符不匹配,轉(zhuǎn)去出錯處理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)生式終結(jié)符集vt中,轉(zhuǎn)去出錯處

25、理else if(n=-1)f=3; /沒有找到合適的候選產(chǎn)生式來做進一步推導(dǎo),轉(zhuǎn)去出錯處理else /用產(chǎn)生式mtxta來做進一步推導(dǎo)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關(guān)鍵字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(c