IFELSE條件語句翻譯程序設(shè)計(jì)方案(LR方法輸出元式)

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

2、點(diǎn)與不足 228.2 收獲與體會(huì) 229 參考文獻(xiàn) 221010 本科生課程設(shè)計(jì)成績?cè)u(píng)定表 .： 2222IF-ELSE 條件語句的翻譯程序設(shè)計(jì)（LR 方法、輸出四元式）1系統(tǒng)描述（問題域描述）對(duì)條件語句：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á)式在程序會(huì)

3、判斷其類型。2.2 屬性文法S-CS S.clain:=merge(C.clain,S.clain)S-TS S.clain:=merge(T.clain,S.clain)S-A S.clain:0/*空鏈*/ C-if E thenbackpatch(E.true,nextstat) C.clain:=E.false T-C S else q:=nextstat Emit(GOTO) Backpatch(C.clain,nextstat) T.clain:=merge(S.clain,q)3 語法分析方法描述及語法分析表設(shè)計(jì)3.1語法分析方法描述3.1.1 LR方法的基本思想一個(gè)LR分析器實(shí)

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

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

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

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

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

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

10、變量。例如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è)計(jì)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è)計(jì)本課程設(shè)計(jì)需要寫一個(gè)條件語句的LR文法及其屬性文法,運(yùn)用LR分析方法對(duì) 此文法進(jìn)行語法和語義分析,中間代碼采用四元式輸出。在這個(gè)條件語句的翻 譯分析程序設(shè)計(jì)中,

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

12、序 中，以；為結(jié)束符號(hào)來判斷一條條的條件語句，并且獨(dú)立的對(duì)每條語句進(jìn) 行語法分析。并把算法中的移近、規(guī)約操作3.語義分析、輸出四元式。在進(jìn)行語法分析的同時(shí)進(jìn)行語義分析，在此次設(shè)計(jì) 中式將二者結(jié)合起來作為一遍進(jìn)行處理的。在進(jìn)行語義時(shí)同時(shí)生成中間語言四 兀式。4.出錯(cuò)處理。如果在詞法分析時(shí)遇到非法字符就會(huì)輸出出錯(cuò)信息，同時(shí)輸出從 出錯(cuò)點(diǎn)開始往后的一串字符，但是它仍然能跳過該非法字符繼續(xù)分析；如果在 語法分析中有錯(cuò)誤的話，就會(huì)顯示在DOS環(huán)境下輸出“ERROR，但是它能跳過 出錯(cuò)的地方繼續(xù)往后執(zhí)行，分析出一部分結(jié)果并保存在文件中。6 詳細(xì)的算法描述6.1 系統(tǒng)流程圖初始化語法詞法分析語法分析語義分析

13、結(jié)束6.2 算法描述本程序中，選用C+程序設(shè)計(jì)語言的部分常用的單詞作為詞法分析的對(duì)象, 詞法分析后，將識(shí)別的所有單詞符號(hào)以及相關(guān)信息保存在數(shù)組中，以便后面語法分析和語意分析及中間代碼生成使用，同時(shí)將識(shí)別出的單詞符號(hào)輸出到文件中，并分類別地存儲(chǔ)到相應(yīng)的數(shù)組中一便進(jìn)行查看。采用SLR(1分析法，生成狀態(tài)表，然后根據(jù)棧的移近、移出生成分析過程表。在經(jīng)過語法、語義分析之后，生成中間代碼四元式，同時(shí)進(jìn)行出錯(cuò)管理。void initGrammar()。/初始化產(chǎn)生式表bool isJchar(char c)檢測是否為分界符int word() /進(jìn)行詞法分析，并存到fenxi.txt文件中wnode* l

14、excial(wnode *head)/把詞法分析得來的詞分類別放到表達(dá)式數(shù)組int check(int s,char v)。/查LR分析表void gammarAnalysis(wnode *head)。/語法分析及進(jìn)行相應(yīng)的語義操作并產(chǎn)生四元式void showS(int opS,int tops,char opC,int topc,wnode *hp)。/顯示分析棧的內(nèi)源程序代碼：# include #include #include # include #include #include usingnamespace std char Filename100。struct wnodec

15、har id。int n。/編號(hào)char text20。wnode * next。struct Gnode/存儲(chǔ)產(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)的語義操作并產(chǎn)生四元式void showS( int opS, int tops, char opC, /用于if-else分析int LR119=/_

16、ACTION_|_GOTO_/ i t e A E # S C T105, 0, 0,104, 0, 0,101,102,103, 0, 0,0, 0, 0, -1, 0, 0, 0, 105, 0, 0,104, 0,0,106,102,103, 105, 0, 0,104, 0,0,110,102,103, 0, 0, 3, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0,108, 0, 0, 0, 0, 0, 0,107, 0,0, 1, 0, 0, 0, 5, 0, 0, 5, 0, 0, 0, 0, 0, 0,109, 0, 0, 0, 0, 0, 0, 0, 4, 0,

17、0, 4, 0,0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0。void initGrammar()grammar0.gen= S-S。grammar0.id=0。grammar1.gen=S-CS。grammar1.id=1。grammar2.gen= S-TS。grammar2.id=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。int top

18、c,wnode *hp）。/顯示分析棧的內(nèi)容/0/1/2/3/4/5/6/7/8/9/10for (i=1oi6。i+)coutgrammari.id-1 tcout5 telse endlgrammari.genendlcout注：i-if t-then e-elseendlcout E 布爾表達(dá)式（在語法分析中看成是終結(jié)符）endlcout A賦值語句（在語法分析中看成是終結(jié)符）endlocout SLR(1)分析表：endl。coutsetw(22) ACTIONsetw(18) | setw(10) GOTOendlcoutsetw(8) i setw(6) t setw(6) e s

19、etw(6) A setw(6) Esetw(6) # setw(6) S setw(6) C setw(6) T endlofor (i=0oi11oi+)coutsetw(2)i。for (j=0oj=110) coutsetw(4) S 100)coutsetw(5) S 0)coutsetw(5) r LRijoelseif (LRij=0)coutsetw(6) oelsecoutsetw(6) ACCocoutendlobool isJchar( char c) /檢測是否為分界符bool r= falseoswitch (c)case :casen :caseo :r= true

20、obreakodefault :oreturn roint word()char ch= oint num=0oifstream source( source.txt ) ofstream fenxi( fenxi.txt )ochar yunsuanfu11= +11 1 11 1/I, ,= ,! ,% ,&,|ochar jiefu9=, ,o , (, ) , , , , ,#ochar*guanjianzi20= int, if, else , then ,do , while , break , continue, switch ,return , when , for ,

21、 double, main ,break , include , sho rt,long ,float, char ,ochar *biaoshifu100=0 o/while (!source.eof()source.get(ch)char shuzi20= 。inti=1。if (ch= 0 &ch= 0 &ch=9 )|ch= . )&!source.eof()shuzii+=chfor (i=0oi=10。i+)if (ch=yunsuanfui)coutchoosource.get(ch)ofenxishuzi 數(shù)字 endl/運(yùn)算符判斷for (i=0oi9

22、oi+)if (ch=jiefui)fenxich 運(yùn)算符 = a &ch=z )charstr120oint sign=0ointn=0ofenxich 界符 = a &ch= 0 &ch=9 )|ch= _ )&!source.eof()str1n=chosource.get(ch)on+ostr1n= 0for (i=0oi20。i+)if (!strcmp(str1,guanjianzii)fenxistr1 關(guān)鍵字 endl sign=1ofenxistr1 標(biāo)識(shí)符 endl/運(yùn)算符判斷fenxich 運(yùn)算符 endlo/界符fenxich 界符 en

23、dlofenxi.close()osource.close()oreturn 0ownode* lexcial(wnode *head)string stroint loc=-1ochar coint i,k=0,mark=0oint Acount=0,Ecount=0ownode *p,*qoif (sign=0)for (i=0oi=10oi+)if (ch=yunsuanfui)for (i=0oitext0= 0。q-n=0。q-next=NULL。fstream infile(Filename)。/根據(jù)輸入的路徑名來打開這個(gè)文件while (infile.get(c)if (isJc

24、har(c)if (mark=1)q-textk=0。for (i=0。q-texti!= 0。i+)if (q-texti= )loc=iif (p-id= i )q-id=E。q-n=+Ecount。elseif (loc!=-1)q-id=A。q-n=+Acount。elseq-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/在末尾加上一個(gè)#q= newwnode。q-next=NUL

25、L。q-id= #。q-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!exit(1)。cout 語法分析過程： endl。cout 分析棧 輸入串 操作 next。int tops=0。int topc=0。opStops=0。opC

26、topc= #。while (p)showS(opS,tops,opC,topc,p)。if (topstopc)c=opCtops+1elseidif (c= E )for (i=0。itexti!=0。i+)Ei=p-textiEi= 0。if (c=A )for (i=0。itexti!=0。i+)Ai=p-textiAi+= Ai= 0mark=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。coutt t歸約 grammar1.genendl。break。case 2:tops=tops-2。topc=topc-1。opCtopc= S。coutt t歸約 grammar2.genendl。break。case 3:tops=tops-1。topc=topc-0。opCtopc= S。coutt t歸約 grammar3.genendl。r=A3。d1=A2。d2=A4。table+loc t( rt d1t d2t T +tn) endltable+loc t( = t T tn t t A0 ) endl break。case 4:tops=tops-3。t

28、opc=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 td1td2tloc+2) endl。else table td1td2tloc+2) endl。if (en=1)goto tttloc+4) endlelsetable+loc t( goto tttloc+4+2*(en) ) endlbreaktable+loc t(case 5:tops=tops-3。topc=topc-2。opCtopc= T。co

29、ut t t歸約grammar5.genendl。table+loc t( goto tttloc+3) next。opS+tops=mark-100。if (topstopc)opC+topc=c cout tt移入 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 *tp=hp。for (i=0。i=topc。i+)coutopCi。coutt。while (tp)coutid。tp=

30、tp-next。coutendl。for (i=0。i=tops。i+)coutopSi。/coutendl。int check( int s, char v)int t=-1。switch (v)casei:t=0。breakcaset:t=1。breakcasee:t=2。breakcaseA:t=3。breakcaseE:t=4。breakcase#:t=5。breakcaseS:t=6。breakcaseC:t=7。breakcaseT:t=8。breakdefault:。int r=LRst。returnr。int main()FILE *fp。int n=100。cout n*IF

31、-ELSE條件語句的翻譯程序設(shè)計(jì)(LR方法、輸岀四元式)* endl initGrammar()。cout 請(qǐng)輸入文件名:。cin.getline(Filename,n)。fp=fopen(Filename, r )。while (fp=NULL) /若打入的文件沒有，則提示繼續(xù)打入有效的路徑名coutSorry,文件不存在! endl。coutid= #。wlist-n=0。wlist-text0= 0。wlist-next=NULL。wlist=lexcial(wlist)。fclose(fp)。word()。gammarAnalysis(wlist)。ifstream fin( siyu

32、anshi.txt )。string s。cout 輸出四元式為： endl while ( getline(fin,s) ) cout s b) then x=yz;else x=y-z, |詞法分析單詞表:2GOTO0S5SIACCS88235aftCTIONe8-CSS-TSS-ftC_if E thenT-CS elseT-eIsei一if tthen e-eIseE布爾圭達(dá)去 （在語法分析 語句（在語注分析中;瀟轡卅句的翻譯程序刖呢、輸岀四忒010請(qǐng)輸入文件名壓C:Wj n dowssystem 3 2cmd,exe輸入保存已寫好的程序的文件名source.txt,source.tx

33、t,回車鍵，詞法分析生成單詞表，語法分析生成語法分析過程和中間代碼四元式I fenxi -記事本文件(F)錨(E)梧式(0)查看(V)務(wù)助(H)字字歳符識(shí)算識(shí)符嘆識(shí)算識(shí)算識(shí)符疔識(shí)算識(shí)算識(shí)跌掾運(yùn)標(biāo)界he標(biāo)運(yùn)麻運(yùn)標(biāo)界1S標(biāo)運(yùn)標(biāo)譴標(biāo)i( a/b)t X = y + Z / e X - y - zSJ C:Windowssystem32cmd.exeS!8i;source-txt4 cfa輸人串操作ttiEtAeAtt0移入U(xiǎn)iEtAeAtt05移入ttiEt AeA#058移入ttiEtAeAtt0589歸約C-if E thenttCAeAtt0移入ttCAeAtt02移入ttCAefttt024歸約S-AttCSeAtt02移入ttCSeAtt026移入ttCSeAtt0267歸約TCS elsettTAtt0移入ttTAtt03移入#TA034歸約S-A#TStt03移入#TStt0310歸約S-TSttStt0移入ttStt01語法分析n 翻譯成功一_C:Windowssystem