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

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

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

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

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

5、,while)、標(biāo)識(shí)符、常量、操作符等。2) 語(yǔ)法分析：在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)法規(guī)則，把單詞符號(hào)串分解成各類語(yǔ)法單位。3) 語(yǔ)義分析與中間代碼產(chǎn)生：對(duì)語(yǔ)法分析所識(shí)別出的各類語(yǔ)法范疇，分析其含義，并進(jìn)行初步翻譯(產(chǎn)生中間代碼)。4) ll(1)文法：ll(1)文法是一種自上而下的語(yǔ)法分析方法。第一個(gè)l是自上而下的分析，第二個(gè)l是從最左單詞開(kāi)始分析，1代表只通過(guò)下1個(gè)單詞分析需要用到的語(yǔ)法。5) 預(yù)測(cè)分析程序：實(shí)現(xiàn)ll(1)法分析的一種有效方法，使用一張預(yù)測(cè)分析表和一個(gè)棧進(jìn)行聯(lián)合控制。預(yù)測(cè)分析程序就是屬于這種類型的ll(1)分析器。2文法的描述2.1 do. while 語(yǔ)句文法描述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ù)測(cè)分析表i=+-*/()do;whilekdlwslspp;spsiqee-tgtgg+tg-tgtfrfrr*fr/frfi(e)q=3語(yǔ)法分析方法及中間代碼形式的描述3.1語(yǔ)法分析方法描述 ll(1)文法的定義： first 集： 設(shè)g=vt,vn,s,p是上下文無(wú)關(guān)文法 first()=a|=a,avt,v* 若a=，則規(guī)定fi

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

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

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

10、等語(yǔ)義分析式部分-主函數(shù)中進(jìn)行的輸出,形式為給定句子的三地址表達(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)示符分隔符運(yùn)算符if(ch!=&ch!=&ch!=(&ch!=)coutcht標(biāo)識(shí)符endl;arr_id-1=ch;queuej+=i;else coutcht分隔符0)coutcht運(yùn)算符endl;queuej+=ch;queuej=#;for(i=0;queuei!=#;i+)coutqueuei;coutendl;語(yǔ)法分析主要算法void syntax() /語(yǔ)法分析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)去出錯(cuò)處理else int tx=index(x,vn);int ta=index(a,vt);n=mtxta;tdt+=mtxta;if(ta=-1)f=2;coutaendl; /字符沒(méi)有出現(xiàn)在產(chǎn)生式終結(jié)符集vt中,轉(zhuǎn)去出錯(cuò)處理else if(n=-1)f=3; /沒(méi)有找到合適的候選產(chǎn)生式來(lái)做進(jìn)一步推導(dǎo),轉(zhuǎn)去出錯(cuò)處

13、理else /用產(chǎn)生式mtxta來(lái)做進(jìn)一步推導(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 求字符串長(zhǎng)度 index 查找字符串中是否有ch 返回ch位置 err 輸出錯(cuò)誤和錯(cuò)誤原因 print 打印 6上機(jī)測(cè)試6.1測(cè)試方法在visual c+ 6.0 下調(diào)試并通過(guò).輸入不同的語(yǔ)句進(jìn)行測(cè)試，測(cè)試的主要目的是看程序能否正確判斷條件語(yǔ)

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

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

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

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

18、結(jié)構(gòu)的一些知識(shí),這就敦促我去重新溫習(xí)數(shù)據(jù)結(jié)構(gòu)中相關(guān)的知識(shí)。8參考文獻(xiàn)(1)編譯原理（第2版） 清華大學(xué)出版社 張素琴 呂映芝 等人著 本科生課程設(shè)計(jì)成績(jī)?cè)u(píng)定表班級(jí)：姓名：學(xué)號(hào)：序號(hào)評(píng)分項(xiàng)目滿分實(shí)得分1學(xué)習(xí)態(tài)度認(rèn)真、遵守紀(jì)律102設(shè)計(jì)分析合理性103設(shè)計(jì)方案正確性、可行性、創(chuàng)造性204設(shè)計(jì)結(jié)果正確性405設(shè)計(jì)報(bào)告的規(guī)范性106設(shè)計(jì)驗(yàn)收10總得分/等級(jí)評(píng)語(yǔ)：注：最終成績(jī)以五級(jí)分制記。優(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) /求字符串長(zhǎng)度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) /輸出錯(cuò)誤和錯(cuò)誤原因if(n=1)cout字符不匹配endl;else if(n=2)cout字符沒(méi)有出現(xiàn)在產(chǎn)生式終結(jié)符集vt中endl;else if(n=3)cout沒(méi)有找到合適的候選產(chǎn)生式來(lái)做進(jìn)一步推導(dǎo)endl;else cout該句子是文法語(yǔ)言的句子！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() /語(yǔ)法分析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)去出錯(cuò)處理else int tx=index(x,vn);int ta=index(a,vt);n=mtxta;tdt+=mtxta;if(ta=-1)f=2;coutaendl; /字符沒(méi)有出現(xiàn)在產(chǎn)生式終結(jié)符集vt中,轉(zhuǎn)去出錯(cuò)處

25、理else if(n=-1)f=3; /沒(méi)有找到合適的候選產(chǎn)生式來(lái)做進(jìn)一步推導(dǎo),轉(zhuǎn)去出錯(cuò)處理else /用產(chǎn)生式mtxta來(lái)做進(jìn)一步推導(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