《編譯原理》課程設(shè)計(jì)說明書DOWHILE循環(huán)語(yǔ)句的翻譯程序設(shè)計(jì)(LR方法、輸出三地址表示)

1、do-while循環(huán)語(yǔ)句的翻譯程序設(shè)計(jì)（lr方法、輸出三地址表示）1.系統(tǒng)描述1.1設(shè)計(jì)目的通過設(shè)計(jì)、編制、調(diào)試一個(gè)do-while循環(huán)語(yǔ)句的語(yǔ)法及語(yǔ)義分析程序，加深對(duì)語(yǔ)法及語(yǔ)義分析原理的理解，并實(shí)現(xiàn)詞法分析程序?qū)卧~序列的詞法檢查和分析。1.2設(shè)計(jì)內(nèi)容及步驟對(duì)循環(huán)語(yǔ)句： do賦值語(yǔ)句while 表達(dá)式按給定的題目寫出符合自身語(yǔ)法分析方法要求的文法和屬性文法描述。(1)按給定的題目給出語(yǔ)法分析方法的思想及分析表設(shè)計(jì)。(2)按給定的題目給出中間代碼序列的結(jié)構(gòu)設(shè)計(jì)。(3)完成相應(yīng)的詞法分析、語(yǔ)法分析和語(yǔ)義分析程序設(shè)計(jì)。(4)編制好分析程序后，設(shè)計(jì)若干用例，上機(jī)測(cè)試并通過所設(shè)計(jì)的分析程序。2文法的描

2、述本程序所用的文法如下：gs:(1)s-doe;while(b)if b.true goto b.true else goto b.false;(2)b-i1 rop i2b.type=bool;b.val=i1.val rop i2.val;(3)e-i1=i2 op i3i1.val=i2.val op i3.val;(4)i-idi.val=id.val;注意：rop is ，op is +,-,*,/, id is any number or identifier由上可知，非終結(jié)符b表示布爾表達(dá)式，e表示賦值表達(dá)式3.語(yǔ)法分析方法描述及語(yǔ)法分析表設(shè)計(jì)3.1語(yǔ)法分析方法描述本實(shí)驗(yàn)采用lr

3、分析方法對(duì)do-while語(yǔ)句進(jìn)行語(yǔ)法分析。lr分析法是一種能根據(jù)當(dāng)前分析棧中的符號(hào)串（通常以狀態(tài)表示）和向右順序查看輸入串的k個(gè)（k=0）符號(hào)就能惟一的確定分析器的動(dòng)作是移進(jìn)還是歸約和用哪個(gè)產(chǎn)生式歸約，因而也就能惟一的確定句柄。lr分析法的歸約過程是規(guī)范推導(dǎo)的逆過程，所以lr分析過程是一種規(guī)范過程。一個(gè)lr分析器由3個(gè)部分組成：總控程序，也可以稱為驅(qū)動(dòng)程序。對(duì)所有的lr分析器，總控程序是相同的。分析表或分析函數(shù)。不同的方法分析表將不同，同一個(gè)方法采用的lr分析器不同時(shí)，分析表也不同，分析表表又可以分為動(dòng)作（action）表和狀態(tài)轉(zhuǎn)換（goto）表兩個(gè)部分，它們都可以用二維數(shù)組表示。分析棧，包

4、括文法符號(hào)棧和相應(yīng)的狀態(tài)棧。它們均是先進(jìn)后出棧。分析器的動(dòng)作由棧頂狀態(tài)和當(dāng)前輸入符號(hào)所決定。lr分析器工作過程示意圖如圖所示：輸入串xxx#總控程序action表goto表sn.s1s0xn.x1#sp輸出其中sp為棧頂指針，si為狀態(tài)棧，xi為文法符號(hào)棧。狀態(tài)轉(zhuǎn)換表內(nèi)容按關(guān)系gotosi,x=sj確定，改關(guān)系式是指當(dāng)前棧頂狀態(tài)為si遇到當(dāng)前文法符號(hào)為x時(shí)應(yīng)轉(zhuǎn)向狀態(tài)sj。x為終結(jié)符或非終結(jié)符。actionsi,a規(guī)定了棧頂狀態(tài)為sj時(shí)遇到輸入符號(hào)ci應(yīng)該執(zhí)行的動(dòng)作。動(dòng)作有以下四種可能：移進(jìn)：當(dāng)sj=gotosi，a成立，則把sj移入到文法符號(hào)棧。其中i，j表示狀態(tài)號(hào)。規(guī)約：當(dāng)在棧頂形成句柄為b

5、時(shí)，則用b歸約為相應(yīng)的非終結(jié)符a，即當(dāng)文法中有a-b的產(chǎn)生式，而b的長(zhǎng)度為r，則從狀態(tài)棧和文法符號(hào)棧中自棧頂向下去掉r個(gè)符號(hào)。并把a(bǔ)移入文法符號(hào)棧內(nèi)，再把滿足sj=gotosi，a的狀態(tài)移進(jìn)狀態(tài)棧，其中si為修改指針后的棧頂狀態(tài)。接受acc：當(dāng)歸約到文法符號(hào)棧中只剩下文法的開始符號(hào)s時(shí)，并且輸入符號(hào)串已結(jié)束即當(dāng)前輸入符是#，則為分析成功。報(bào)錯(cuò)：當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號(hào)時(shí)，則報(bào)錯(cuò)，說明輸入串不是該分發(fā)能接受的句子。3.2語(yǔ)法分析表設(shè)計(jì)3.2.1構(gòu)造文法的dfai0:s-.ss-.doe;while(b)i1:s-s.i2:s-do.e;while(b)i3:s-do.e;

6、while(b) e-.i= i op i i-.idi4:s-doe.;while(b)i5:e-i . =i op ii6:i-id.i7:s-doe;.while(b)i8:e-i=.i op i i-.idi9:s-doe;.while(b)i10:e-i = i. op ii11:s-doe;while.(b)i12:e-i=i op .ii=.idi13:s-doe;while(.b)b-.i rop ii-.idi14:e-i=i op i.i15:s-doe;while(b.)i16:b-i .rop ii17:s-doe;while(b).i18:b-i rop .ii19:

7、b-iropi.i1i0i19i4i13i9i14i15i12i6i10i8i2i7i16i11i5i3i17i183.2.2然后寫出lr分析表：狀態(tài)actiongotodo=;while()ropopid#sbei0s211acc2s33s6454s75s86r4r4r4r4r4r4r4r4r4r4r4r47s98s6109s1110s1211s1312s1413s6151614r3r3r3r3r3r3r3r3r3r3r3r315s1716s1817r1r1r1r1r1r1r1r1r1r1r1r118s61919r2r2r2r2r2r2r2r2r2r2r2r24.中間代碼形式的描述及中間代碼

8、序列的結(jié)構(gòu)設(shè)計(jì)4.1中間代碼形式的描述在本程序中作用三地址碼表示中間代碼三地址碼的表達(dá)形式為：標(biāo)號(hào)結(jié)果：=操作數(shù)1操作符操作數(shù)2常見三地址表示舉例：賦值語(yǔ)句 t1 := a op b， a:= b條件轉(zhuǎn)移 if true goto label無(wú)條件轉(zhuǎn)移 goto label4.2中間代碼序列的結(jié)構(gòu)設(shè)計(jì)本程序用標(biāo)號(hào)來(lái)表示程序的跳轉(zhuǎn)過程，示例如下100 賦值語(yǔ)句101賦值語(yǔ)句102 條件跳轉(zhuǎn)語(yǔ)句103 無(wú)條件轉(zhuǎn)移語(yǔ)句5.編譯系統(tǒng)的概要設(shè)計(jì)本編譯程序的結(jié)構(gòu)圖如下：源程序(do-while 語(yǔ)句)詞法分析(lex函數(shù))語(yǔ)法語(yǔ)義分析 （analyze函數(shù)）代碼生成程序程序輸出說明：源程序（do-whil

9、e語(yǔ)句）通過控制臺(tái)輸入。然后通過 lex函數(shù)對(duì)輸入的源程序進(jìn)行分析后，將分析結(jié)果以二元組的方式輸出到控制臺(tái)。接下來(lái)通過調(diào)用語(yǔ)法語(yǔ)義分析函數(shù)來(lái)完成對(duì)分析得到的單詞進(jìn)行文法句子的識(shí)別，并用進(jìn)行語(yǔ)法制導(dǎo)翻譯，完成屬性文法定義規(guī)定的相關(guān)語(yǔ)義動(dòng)作。本編譯程序最后完成的三地址碼輸出是通過中間文件間接輸出到控制臺(tái)上的。在執(zhí)行analyze函數(shù)的過程中，同時(shí)運(yùn)用ofstream文件流將三地址碼輸出到一個(gè)ascii碼的txt類型文件中，最后從該文件中讀出最終處理的三地址碼輸出至控制臺(tái)。6.詳細(xì)的算法描述（流程圖或偽代碼）6.1詞法分析詞法分析程序要做的工作是：從源程序的第一個(gè)字符開始，順序讀字符，一次讀一個(gè)，根

10、據(jù)所讀進(jìn)的字符識(shí)別各類單詞，同時(shí)去掉源程序中的空白和注釋。詞法分析檢查的錯(cuò)誤主要是挑出源程序中出現(xiàn)的非法符號(hào)。下面為本程序中所用來(lái)進(jìn)行詞法分析的偽代碼：輸入字符；if(字符是字母)查找關(guān)鍵詞表；if(是關(guān)鍵字do或者while)識(shí)別關(guān)鍵詞;else 判斷為標(biāo)識(shí)符；else if(字符是數(shù)字)獲取整個(gè)數(shù);else if(運(yùn)算符)if(是算術(shù)運(yùn)算符)識(shí)別算術(shù)運(yùn)算符 ；else 識(shí)別為關(guān)系運(yùn)算符;else 標(biāo)識(shí)為其他類型以下附部分源碼:int lex(char instr208,int instrlen)/0關(guān)鍵字，1標(biāo)識(shí)符2數(shù)字3界符4算符5其他char strsrcbuffursize,strd

11、st8,ch;int strcount=0,strlength,i=0;coutplease input the do-while statement:endl;gets(strsrc);strlength=strlen(strsrc);coutendl lexical analyse:endl;while(strcountstrlength)while(strsrcstrcount= ) strcount+; ch=strsrcstrcount;if(alpha(ch) i=0; do strdsti+=strsrcstrcount+;while(alpha(strsrcstrcount)|

12、digit(strsrcstrcount)&(strcountstrlength); strdsti=0;if(!strcmp(strdst,while)coutsetw(10)(0,strdst)endl;else coutsetw(10)(1,strdst)endl;for(int k=0;strdstk!=0;k+)instrinstrlenk=strdstk;instrinstrlen+k=0; else if(digit(ch)i=0; do strdsti+=strsrcstrcount+;while(digit(strsrcstrcount)&(strcountstrlength

13、); strdsti=0; coutsetw(10)(2,strdst)endl;for(int k=0;strdstk!=0;k+)instrinstrlenk=strdstk;instrinstrlen+k=0; else if(oper(ch)i=0;strdsti=ch;strdsti+1=0;if(!strcmp(strdst,;)|!strcmp(strdst,()|!strcmp(strdst,)|!strcmp(strdst,)|!strcmp(strdst,)coutsetw(10)(3,ch)endl;else coutsetw(10)(4,ch)endl;for(int

14、k=0;strdstk!=0;k+)instrinstrlenk=strdstk;instrinstrlen+k=0;strcount+;elsecoutsetw(10)(5,ch)endl;isillegal=1; coutisillegal=isillegalendl; coutnot while statement endl;break;strcount+;instrinstrlen+0=#;coutinputed stringendl; for(int j=0;jinstrlen;j+)cout instrj;coutgrammer analysisn;return instrlen;

15、6.2語(yǔ)法分析流程圖如下，具本處理過程，請(qǐng)參見本文檔3.1小節(jié)輸入串xxx#總控程序action表goto表sn.s1s0xn.x1#sp輸出此處附上語(yǔ)法語(yǔ)義分析函數(shù)void analyze(state state) int row=0,col=0,numchange=0;cout procedureendl;cout.setf(ios:left);coutstep setw(20)statestacksetw(20)symbolstacksetw(20)inputsetw(8)actionsetw(6)gotoendl;strcpy(next,state.instrstate.curinst

16、r);roporop(next);row=state.stkstatestate.curstate;col=index(next);numchange=tablerowcol;ofstream outfile(do_while.txt);while(strcmp(state.stksymbolstate.cursymbol,s)!=0&numchange!=20)if(numchange=0)isillegal=1;break;numchange=action(state,numchange,outfile);if(isillegal=0)coutsetw(4)step+ ;state.sho

17、wstate();coutsetw(8)accendl;coutprocessing semantic analysis=1&actionnum=18)choice=1;else choice =actionnum;switch(choice)case 0:isillegal=1; coutisillegal=isillegalendl;break;case 1:/移進(jìn)項(xiàng)目coutsetw(4)step+ ;state.showstate();coutsetw(8)actionnumendl;state.curstate+;state.stkstatestate.curstate=action

18、num; state.cursymbol+; strcpy(state.stksymbolstate.cursymbol,state.instrstate.curinstr);state.curinstr+;strcpy(next,state.instrstate.curinstr);roporop(next);row=state.stkstatestate.curstate;col=index(next);numchange=tablerowcol;break;case 20:/接收coutsetw(4)step+ ;state.showstate();coutsetw(8)accwhile

19、(b)e;coutsetw(4)step+ ;state.showstate();coutsetw(8)0;i-)state.stkstatestate.curstate-=0; for(i=9-1;i=0;i-)strcpy(bi,state.stksymbolstate.cursymbol);strcpy(state.stksymbolstate.cursymbol-,);outfileb.false: iropistrcpy(next,state.stksymbolstate.cursymbol);roporop(next);row=state.stkstatestate.curstat

20、e;col=index(next);numchange=tablerowcol;numchange=goto(state,numchange);break;case 22:/r2 b-iropicnt=0;coutsetw(4)step+ ;state.showstate();coutsetw(8)0;i-)state.stkstatestate.curstate-=0; for(i=3-1;i=0;i-)strcpy(bi,state.stksymbolstate.cursymbol);strcpy(state.stksymbolstate.cursymbol-,);outfile102 t

21、1:=i0b1i1endl;outfile103 if t1.val=true goto 100endl;outfile104 goto 105iropistrcpy(next,state.stksymbolstate.cursymbol);roporop(next);row=state.stkstatestate.curstate;col=index(next);numchange=tablerowcol;numchange=goto(state,numchange);break;case 23:/r3 e-i=iopi cnt=0;coutsetw(4)step+ ;state.shows

22、tate();coutsetw(8)0;i-)state.stkstatestate.curstate-=0; for(i=5-1;i=0;i-)strcpy(ei,state.stksymbolstate.cursymbol);strcpy(state.stksymbolstate.cursymbol-,);outfile100 t1:=i1e3i2endl;outfile101 i0:=t1idcoutsetw(4)step+ ;state.showstate();coutsetw(8)idstrcpy(next,state.stksymbolstate.cursymbol);roporo

23、p(next);row=state.stkstatestate.curstate;col=index(next);numchange=tablerowcol;numchange=goto(state,numchange);break;return numchange;int goto(state &state,int gotonum) int row=0,col=0,numchange=0;coutsetw(6)gotonumendl;state.curstate+;state.stkstatestate.curstate=gotonum;strcpy(next,state.instrstat

24、e.curinstr);roporop(next);row=state.stkstatestate.curstate;col=index(next);return tablerowcol;7.軟件的測(cè)試方法和測(cè)試結(jié)果(1)運(yùn)行程序，顯示如下程序界面(2)按照提示輸入合法的do-while語(yǔ)句doa=b+c;while(ab)(3)按enter確定輸入完畢，得到詞法分析結(jié)果,顯示如下：并且最后一行提示了經(jīng)過詞法分析后合法的待輸入串在棧中的存儲(chǔ)情況。(4)繼續(xù)確定，可以看見輸入的句子的按lr方法的詳細(xì)處理過程。結(jié)果顯示如下：由此可以看見在用lr方法識(shí)別d0-while句子的時(shí)候，狀態(tài)棧，符號(hào)棧以及

25、待輸入串的詳細(xì)變化情況。（說明, 其中21，22，23，24分別表示用第1、2、3、4個(gè)產(chǎn)生式進(jìn)行歸約。）(5)繼續(xù)執(zhí)行程序，最終出現(xiàn)語(yǔ)義分析結(jié)果8.研制報(bào)告8.1研制過程本次實(shí)驗(yàn)是對(duì)do-while語(yǔ)句運(yùn)用lr分析法進(jìn)行語(yǔ)法分析，分析的過程中要求運(yùn)用屬性文法和語(yǔ)法制導(dǎo)翻譯的相關(guān)知識(shí)來(lái)有效完成對(duì)一個(gè)合法的do-while語(yǔ)的語(yǔ)義分析。做實(shí)驗(yàn)如果有一個(gè)比較詳細(xì)的安排和計(jì)劃，就會(huì)使實(shí)驗(yàn)進(jìn)程井井有條。在實(shí)驗(yàn)之始，按照實(shí)驗(yàn)說明書的要求，對(duì)實(shí)驗(yàn)進(jìn)行了模塊劃分。首先大致分為三個(gè)部分，包括詞法分析，語(yǔ)法分析和語(yǔ)義分析。因?yàn)橐郧白鲞^詞法分析和語(yǔ)法分析的相關(guān)實(shí)驗(yàn)，所以這部分比較容易。于是精力大部分放在第三個(gè)部分語(yǔ)義分析上。首先，根據(jù)自己擬定文法，構(gòu)造出正確的lr分析表，文法雖然只有四個(gè)產(chǎn)生式，但經(jīng)過分析，卻產(chǎn)生了多達(dá)20個(gè)狀態(tài)。完成了lr分析，接著是確定給定文法的屬性文法，以便在語(yǔ)