IFELSE條件語句翻譯程序設(shè)計方案

1、目錄1 系統(tǒng)描述（問題域描述） 22 文法及屬性文法的描述 22.1 文法 22.2 屬性文法 23 語法分析方法描述及語法分析表設(shè)計 33.1 語法分析方法描述 33.1 . 1 LR方法的基本思想 33.1.2 LR分析器模型 43.2 語法分析表設(shè)計 54 中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計 64.1 中間代碼形式的描述 64.2 中間代碼序列的結(jié)構(gòu)設(shè)計 65 編譯系統(tǒng)的概要設(shè)計 66 詳細(xì)的算法描述 76.1 系統(tǒng)流程圖 76.2 算法描述 77 軟件的測試方法和測試結(jié)果 187.1 軟件的測試方法 187.2 測試結(jié)果 188 設(shè)計的特點(diǎn)、不足、收獲與體會 218.1 特點(diǎn)與

2、不足 218.2 收獲與體會 219 參考文獻(xiàn) 2110本科生課程設(shè)計成績評定表 .22IF-ELS條件語句的翻譯程序設(shè)計（LR方法、輸出四元式）1 系統(tǒng)描述（問題域描述）對條件語句： if 布爾表達(dá)式 then 賦值語句 else 賦值語句， 進(jìn)行詞法， LR（1） 語法分析，并根據(jù)語法制導(dǎo)翻譯方法將條件語句翻譯成四元式 中間代碼形式，最后輸出翻譯后的四元式代碼。2 文法及屬性文法的描述2.1 文法GS: S-CSS-TSS-AC-if E thenT-CS elseT-else其中， E 代表布爾表達(dá)式，可由界符()括起來， A 代表賦值表達(dá)式。在這里 E、 A都代表終結(jié)符，具體的表達(dá)式在

3、程序會判斷其類型。2.2 屬性文法S-C SS.clain:=merge(C.clain,S.clain)S-T S S.clain:=merge(T.clain,S.clain)S-AS.clain:0/* 空鏈 */C-if E thenbackpatch(E.true,nextstat) C.clain:=E.falseT-C S else q:=nextstatEmit(GOTO)Backpatch(C.clain,nextstat)T.clai n:=merge(S.clai n,q)3語法分析方法描述及語法分析表設(shè)計3.1語法分析方法描述3.1. 1 LR方法的基本思想一個LR分析

4、器實質(zhì)上是一個帶先進(jìn)后出存儲器的確定有限狀態(tài)自動機(jī)。我 們將把“歷史”和“展望”材料綜合地抽象成某些“狀態(tài)”。分析棧用來存放狀 態(tài)。棧里的每個狀態(tài)概括了從分析開始直到某一歸約階段的全部“歷史”和“展 望”資料。任何時候，棧頂?shù)臓顟B(tài)都代表了整個的歷史和已推測出的展望。因此,在任何時候都可從棧頂狀態(tài)得知所想了解的一切， 而絕對沒有必要從稱底而上翻 閱整個棧。LR分析器的每一步工作都是由棧頂狀態(tài)和現(xiàn)行輸入符號所唯一決定的。 為了有助于明確歸約手續(xù)，我們把已歸約出 的文法符號串也同時放在棧里。于是，我們可以把棧的結(jié)構(gòu)看成是：I1i111S1XIsoxo狀態(tài) 符號棧頂圖一棧的結(jié)構(gòu)圖棧的每一項內(nèi)容包括狀態(tài)

5、S和文法符號X兩部分。（SO, #）為分析開始前 預(yù)先放到棧里的初始狀態(tài)和句子括號。棧頂狀態(tài)為SM符號串X1X2-.XM是至今已 移進(jìn)歸約出的部分。3.1.2 LR分析器模型LR分析器模型如下圖分析表圖二LR分析器模型LR分析器的核心部分是一張分析表。這張分析表包括兩部分，一是“動作”（ACTION表，另一個是“狀態(tài)轉(zhuǎn)換表”（GOTO表o它們都是二維數(shù)組。ACTIONS a規(guī)定了當(dāng)狀態(tài)s面臨輸入符號a時應(yīng)采取什么動作。GOTO a規(guī)定了狀態(tài)s 面對文法符號X （終結(jié)符或非終結(jié)符）時下一個狀態(tài)是什么。顯然 GOTOS x 定義了一個以文法符號為字母表的 DFA每一項ACTIONs a所規(guī)定的動作

6、不外是下述四種可能之一：1. 移進(jìn) 把（S, A）的下一狀態(tài)S= GOTOS A和輸入符號A推進(jìn)棧，下一 輸入符號變成現(xiàn)行輸入狀態(tài)。2. 規(guī)約 指用某一產(chǎn)生式A- 進(jìn)行規(guī)約。假若 的長度為r,歸約動作是A, 去除棧頂?shù)膔個項，使?fàn)顟B(tài)Sm-r變成棧頂狀態(tài)，然后把（Sm-r, A）的下一狀態(tài) S仁GOTOSm-r,A和文法符號At進(jìn)棧。歸約動作不改變現(xiàn)行輸入符號。執(zhí)行歸約動作意味著（二Xm-葉1.Xm）已呈現(xiàn)于棧頂而且是一個相對于 A的句柄。3. 接受宣布分析成功，停止分析器的工作。4. 報錯 發(fā)現(xiàn)源程序含有錯誤，調(diào)用出錯處理程序。LR分析器的總控程序本身的工作是非常簡單。 它的任何一步只需要按棧

7、頂狀態(tài) 和現(xiàn)行輸入符號a執(zhí)行ACTIONS a所規(guī)定的動作。不管什么分析表，總控程 序都是一樣地工作。一個LF分析器的工作過程可看成是棧里的狀態(tài)序列，已歸約串和輸入串所構(gòu)成的三元式的變化過程。分析地的初始三元式（S0,#,a1a2an#）其中，SQ為分 析器的初態(tài)；#為句子的左括號；a1a2an為輸入串；其后的#為結(jié)束符。分析 過程每步的結(jié)果可表示為(sOs1sm,# X1X2,ai.an#)分析器的下一步動 作是由棧頂狀態(tài)Sn和現(xiàn)行輸入符號ai所唯一決定。即，執(zhí)行ACTIONSm,ai所 規(guī)定的動作。經(jīng)執(zhí)行每種可能的動作之后，三元式的變化的情形是：(1) 若ACTIONSm,ai為移進(jìn)，且S

8、=GOTOSm,ai則三元式變成：(S0S1 Sm,#X1X2Xmaia n#)(2) 若ACTIONSm,ai = A ，則按產(chǎn)生式A- 進(jìn)行歸約。此時三元式變 為(S0S1Sm-rS,#X1 Xm-rA,aiai+1 an#)此處S = GOTOSm-r,A, r為 的長度， =Xm-葉1Xm(3) 若ACTIONSm,ai為：接受，則三元式不再變化，變化過程終止，宣布分 析成功。(4) 若ACTIONSm,ai為“報錯”，則三元式的變化過程終止，報告錯誤。 一個LR分析器的工作過程就是一步一步地變換三元式，直至執(zhí)行“接受”或“報錯”為止。3.2語法分析表設(shè)計在做語法分析前需建立SLR(1

9、)語法分析表ACTIONGOTOiteAE#SCT0S5S4S1S2S31ACC2S5S4S6S2S33S5S4S10S2S34r3r35S86S7r17r5r58S99r4r410r2r2此表中引用記號的意義是:(1)Sj把卜一狀態(tài)j和現(xiàn)行輸入符號移進(jìn)棧;(2)rj按第j個產(chǎn)生式進(jìn)行規(guī)約；(3)acc接受；(4)空白格出錯標(biāo)志，報錯；4 中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計4.1 中間代碼形式的描述四元式是一種比較普遍采用的中間代碼形式。 四元式的四個組成部分是： 操作符OP第一個和第二個運(yùn)算 對象ARG1和ARG2及運(yùn)算結(jié)果RESULT運(yùn) 算對象和運(yùn)算結(jié)果有時指用戶自己定義的變量，有

10、時指編譯程序引進(jìn)的臨時 變量。例如 a:=b*c+b*d 的四元式表示如下：(1) (*,b,c,t1)(2) (*,b,d,t2)(3) (+,t1,t2,t3)(4) (:=,t3,-,a)4.2 中間代碼序列的結(jié)構(gòu)設(shè)計If E then A1else A2100 （關(guān)于E的布爾表達(dá)式）101 （ goto, - , - ,104）102 （關(guān)于 A1 的賦值表達(dá)式 ）103 （ goto, - , - ,105）104 （關(guān)于 A2 的賦值表達(dá)式 ）105 exit5 編譯系統(tǒng)的概要設(shè)計本課程設(shè)計需要寫一個條件語句的 LR文法及其屬性文法，運(yùn)用LR分析方法對此 文法進(jìn)行語法和語義分析，

11、中間代碼采用四元式輸出。 在這個條件語句的翻譯分 析程序設(shè)計中，主要通過以下四個過程來完成：1. 詞法分析。由于編譯程序是在單詞的級別上來分析和翻譯源程序的，那么在這 里，詞法分析的任務(wù)是： 從左至右逐個字符地對源程序進(jìn)行掃描， 產(chǎn)生一個一個 的單詞符號， 把作為字符串的源程序改造成為單詞符號串的中間程序。 所以詞法 分析是編譯的基礎(chǔ)。 在此程序中是將詞法分析作為一遍處理的， 通過一次分析把 全部的字符串都分析完成，并將其保存在數(shù)組中便于下一步進(jìn)行語法分析。2. 語法分析。在完成詞法分析的基礎(chǔ)上對條件語句進(jìn)行語法分析，在這里我采 用了自下而上分析法SLR(1分析方法，來分析判定程序的語法結(jié)構(gòu)是

12、否符合語法 規(guī)則，在分析前首先要構(gòu)造SLR(1分析表，然后在進(jìn)行語法分析，在此程序中， 以；為結(jié)束符號來判斷一條條的條件語句，并且獨(dú)立的對每條語句進(jìn)行語法 分析。并把算法中的移近、規(guī)約操作3. 語義分析、輸出四元式。在進(jìn)行語法分析的同時進(jìn)行語義分析，在此次設(shè)計中 式將二者結(jié)合起來作為一遍進(jìn)行處理的。在進(jìn)行語義時同時生成中間語言四元式。4. 出錯處理。如果在詞法分析時遇到非法字符就會輸出出錯信息，同時輸出從出 錯點(diǎn)開始往后的一串字符，但是它仍然能跳過該非法字符繼續(xù)分析；如果在語法 分析中有錯誤的話，就會顯示在 DOS環(huán)境下輸出“ ERROR，但是它能跳過出錯 的地方繼續(xù)往后執(zhí)行，分析出一部分結(jié)果

13、并保存在文件中。6詳細(xì)的算法描述6.1系統(tǒng)流程圖開始初始化語法詞法分析語法分析語義分析中間代碼生成出錯處理結(jié)束6.2算法描述本程序中，選用C+程序設(shè)計語言的部分常用的單詞作為詞法分析的對象， 詞法分析后，將識別的所有單詞符號以及相關(guān)信息保存在數(shù)組中，以便后面語法 分析和語意分析及中間代碼生成使用，同時將識別出的單詞符號輸出到文件中，并分類別地存儲到相應(yīng)的數(shù)組中一便進(jìn)行查看。采用SLR(1分析法，生成狀態(tài)表，然后根據(jù)棧的移近、移出生成分析過程表。 在經(jīng)過語法、語義分析之后，生成中間代碼四元式，同時進(jìn)行出錯管理。 void initGrammar();/ 初始化產(chǎn)生式表bool isJchar(c

14、har c)檢測是否為分界符int word() / 進(jìn)行詞法分析，并存到 fenxi.txt 文件中wnode* lexcial(wnode *head)/ 把詞法分析得來的詞分類別放到表達(dá)式數(shù)組int check(int s,char v);查 LR分析表void gammarAnalysis(wnode *head);/ 語法分析及進(jìn)行相應(yīng)的語義操作并產(chǎn)生 四元式void showS(i nt opS,i nt tops,char opC,i nt topc,w node *hp); 顯示分析棧的內(nèi)源程序代碼：# include #include #include # include #

15、include #include using namespacestd;char Filename100;struct wnodechar id;int n; / 編號char text20;wnode * next;struct Gnode/ 存儲產(chǎn)生式string gen;int id;Gnode grammar6;void initGrammar(); / 初始化產(chǎn)生式表wnode* lexcial(wnode *head);int check( int s, char v); / 查 LR分析表void gammarAnalysis(wnode *head); / 語法分析及進(jìn)行相應(yīng)的

16、語義操作并產(chǎn)生四元式void showS(int opS, int tops, char opC, int topc,wnode *hp);/ 顯示分析棧的內(nèi)容/ 用于 if-else 分析int LR119=/ACTION|_GOTO_/ i t e A E # S C T105, 0, 0,104, 0, 0,101,102,103, /0 0, 0, 0, 0, 0, -1, 0, 0, 0, /1 105, 0, 0,104, 0, 0,106,102,103,/2105, 0, 0,104, 0, 0,110,102,103,/3 0, 0, 3, 0, 0, 3, 0, 0, 0,

17、 /4 0, 0, 0, 0,108, 0, 0, 0, 0,/5 0, 0,107, 0, 0, 1, 0, 0, 0,/6 5, 0, 0, 5, 0, 0, 0, 0, 0, /7 0,109, 0, 0, 0, 0, 0, 0, 0, /8 4, 0, 0, 4, 0, 0, 0, 0, 0,/9 0, 0, 2, 0, 0, 2, 0, 0, 0/10 ;void initGrammar()grammar0.gen= S-S ;grammar0.id=0;grammar1.gen= S-CS ;grammar1.id=1;grammar2.gen= S-TS ;grammar2.id

18、=2;grammar3.gen= S-A ;grammar3.id=3;grammar4.gen= C-if E then ;grammar4.id=4;grammar5.gen= T-CS else ;grammar5.id=5;cout 所用文法 : endl;int i,j;for (i=1;i6;i+)coutgrammari.id-1 t grammari.genendl;cout 5 t else endl;cout 注： i-if t-then e-elseendl;cout E 布爾表達(dá)式(在語法分析中看成是終結(jié)符) endl;cout A 賦值語句(在語法分析中看成是終結(jié)符)

19、 endl;cout SLR(1) 分析表： endl;coutsetw(22) ACTIONsetw(18) | setw(10) GOTO endl;coutsetw(8) i setw(6) t setw(6) e setw(6) A setw(6) E setw(6) # setw(6) S setw(6) C setw(6) T endl;for (i=0;i11;i+)coutsetw(2)i;for (j=0;j=110) coutsetw(4) S 100) coutsetw(5) S 0) coutsetw(5) r LRij;else if (LRij=0) coutset

20、w(6) ;else coutsetw(6) ACC; coutendl;bool isJchar( char c) / 檢測是否為分界符bool r= false ;switch (c)case :case n :case ; :r= true ; break ;default :; return r;int word()char ch= ;int num=0;ifstream source( source.txt );ofstream fenxi( fenxi.txt );char yunsuanfu11= + ,- ,* ,/ , ,= ,! ,% ,& ,| ; char jiefu9

21、= , ,; ,( , ) , , , , ,# ;char*guanjianzi20= int , if , else , then ,do , while , break , continue , switch ,ret urn , when , for , double , main , break , include , short , long , float , char ,; char *biaoshifu100= 0 ;/while (!source.eof()source.get(ch);char shuzi20= ;int i=1;if (ch= 0 &ch= 0 &ch=

22、9 )|ch= . )&!source.eof() coutch;shuzii+=ch;source.get(ch); fenxishuzi 數(shù)字 endl;for (i=0;i=10;i+) / 運(yùn)算符判斷if (ch=yunsuanfui)fenxich 運(yùn)算符 endl;for (i=0;i9;i+) / 界符if (ch=jiefui)fenxich 界符 = a &ch= a &ch= 0 &ch=9 )|ch= str1n=ch;source.get(ch);n+;str1n= 0 ;for (i=0;i20;i+)if (!strcmp(str1,guanjianzii) fen

23、xistr1 關(guān)鍵字 endl; sign=1;if (sign=0) fenxistr1 標(biāo)識符 endl;/ 運(yùn)算符判斷/ 界符for (i=0;i=10;i+)if (ch=yunsuanfui) fenxich 運(yùn)算符 endl;for (i=0;i9;i+)if (ch=jiefui) fenxich 界符 text0= 0 ; q-n=0;q-next=NULL;fstream infile(Filename); / 根據(jù)輸入的路徑名來打開這個文件 while (infile.get(c)if (isJchar(c)if (mark=1)q-textk= 0 ;for (i=0;q

24、-texti!= 0 ;i+)if (q-texti= = ) loc=i;if (p-id= i ) q-id= E ;q-n=+Ecount; else if (loc!=-1)q-id= A ;q-n=+Acount;else q-id=q-text0;if (q-id= i ) head-n+;p-next=q;p=q; mark=0; elseif (mark=0)q= newwnode;q-n=0; q-next=NULL; loc=-1; k=0;mark=1; q-textk+=c;/ 在末尾加上一個 #q= newwnode; q-next=NULL; q-id= # ; q

25、-text0= 0 ;q-n=0;p-next=q;return head;/ 語法分析void gammarAnalysis(wnode *head)char E20;char A20;char r,d1,d2;int tn=0,en=head-n;ofstream table; table.open( siyuanshi.txt );if (!table)cout Cannot open output file! endl; exit(1);cout 語法分析過程： endl;cout 分析棧 輸入串 操作 next;int tops=0;int topc=0;opStops=0;opCt

26、opc= # ;while (p)showS(opS,tops,opC,topc,p);if (topsid;if (c= E )for (i=0;itexti!= 0 ;i+) Ei=p-texti;Ei= 0if (c= A )for (i=0;itexti!= 0 ;i+) Ai=p-texti;Ai+= ; ;Ai= 0 ;mark=check(opStops,c);switch (mark)case -1:cout t 語法分析 , 翻譯成功 endl;table+loc;table.close(); return ;case 1:tops=tops-2;topc=topc-1;op

27、Ctopc= S ;cout t t 歸約 grammar1.genendl; break ;case 2:tops=tops-2;topc=topc-1;opCtopc=S ;cout t t 歸約 grammar2.genendl; break ;case 3:tops=tops-1;topc=topc-0;opCtopc=S ;cout t t 歸約 grammar3.genendl; r=A3;d1=A2;d2=A4;table+loc t( rt d1t d2t T +tn) endl; table+loc t( = t T tnt t A0 ) endl; break ;case

28、4:tops=tops-3;topc=topc-2;opCtopc= C ;cout t t 歸約 grammar4.genendl;r=E2;d1=E1; if (r= = )d2=E4; else d2=E3; table+loc t( r;if (r= = )tabler t d1t d2t loc+2 ) endl; else table t d1t d2t loc+2 ) endl;if (en=1)table+loc t( goto t t t loc+4 ) endl; elsetable+loc t( goto t t t loc+4+2*(en) ) endl; break

29、;case 5:tops=tops-3;topc=topc-2;opCtopc= T ;cout t t 歸約 grammar5.genendl;table+loc t( goto t t t loc+3) next;opS+tops=mark-100; if (topstopc)opC+topc=c; cout t t 移入 endl; break ;case 0:cout ERROR!endl; return ;void showS( int opS, int tops, char opC, int topc,wnode *hp)/ coutendl;int i=0,j=0;wnode *

30、tp=hp;for (i=0;i=topc;i+)coutopCi;cout t ;while (tp)coutid;tp=tp-next;coutendl;for (i=0;i=tops;i+)coutopSi;/coutendl;int check( int s, char v)int t=-1;switch (v)case i :t=0; break ;case t :t=1; break ;case e :t=2; break ;case A :t=3; break ;case E :t=4; break ;case # :t=5; break ;case S :t=6; break

31、;case C :t=7; break ;case T :t=8; break ; default :;int r=LRst; return r;int main()FILE *fp; int n=100;cout n*IF-ELSE 條件語句的翻譯程序設(shè)計(LR方法、輸岀四元式)* endl; initGrammar();cout 請輸入文件名 : ;cin.getline(Filename,n);fp=fopen(Filename, r );while (fp=NULL) / 若打入的文件沒有，則提示繼續(xù)打入有效的路徑名coutSorry, 文件不存在 ! endl;coutid= # ;

32、wlist-n=0;wlist-text0= 0 ;wlist-next=NULL;wlist=lexcial(wlist);fclose(fp);word();gammarAnalysis(wlist);ifstream fin( siyuanshi.txt );string s;cout 輸岀四元式為： endl;while ( getline(fin,s) )cout s CSS-TSS-ftC-if E thenT-CS elseT-eIsei一if tthen e-eIseE 布爾義達(dá)去（在語法分析A 二賦值語句（在語注分析中;勰弈件語句的翻譯程職計扇法、輸出辰10請輸入文件名虛3

33、C:Wn dov. ssystem3 2cmd.exe輸入保存已寫好的程序的文件名source.txt,回車鍵，詞法分析生成單詞表，語法分析生成語法分析過程和中間代碼四元式條件語句代碼:sou rce -記事本文樣（F）磊回楷式電誓麗jif （,ab） then k二y+z;else x=y-z;|詞法分析單詞表：逼fenxi -記事本 艮牛（K 鉀啟 梧式（0）查看M與SUH SUSUH 符識算尊詠識算識算識魯識算識算識襦 需運(yùn)標(biāo)界he標(biāo)運(yùn)標(biāo)運(yùn)標(biāo)界1S標(biāo)運(yùn)標(biāo)運(yùn)標(biāo)橐 (a XZ b), tM = y+z-es- y - M;5 ttiE 058 ttLEt 05即操作移入EtAeAtt移入移入AeAtt歸約AeAtt移入AeAtt彳牛：口 :source.txt輸入串 iEtAeAttC-iFE thenSB C：Windows；system32cmd.exeS-A移入eAtt移入歸約TCS else移入移入tt歸約S-Atttt歸約S-TStt移入(124 ItCSttGS026 ttCSe 0267It!ns01BneAtl4t語法3ttT 03 ttTA 034 ttTSttTS 0310 bsrow C:Wi n dowsXsystem 3 2cmd. exe輸出四元式為；