IF-ELSE條件語句的翻譯程序設(shè)計(LL(1)法、輸出四元式).doc

武漢理工大學(xué)編譯原理課程設(shè)計說明書目錄課程設(shè)計任務(wù)書.21. 問題描述.32. 問題分析及編譯系統(tǒng)的概要設(shè)計.33. 文法及屬性文法的定義.3 3.1文法.3 3.2屬性文法的描述.43.2.1 屬性文法的定義形式.43.2.2 IF THEN ELSE 語句的屬性文法.44.語法分析方法描述及語法分析表設(shè)計.5 4.1語法分析方法描述.55. 語法分析.86. 中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計.127. 語義分析及中間代碼輸出.128. 程序流程圖.149. 設(shè)計結(jié)果顯示.1510.研制報告.1610.1研制過程.1610.2本設(shè)計的評價、特點、不足、收獲與體會等.1611.源程序清單.17課程設(shè)計任務(wù)書學(xué)生姓名： 專業(yè)班級： 指導(dǎo)教師： 高 曙 工作單位：計算機科學(xué)與技術(shù)學(xué)院 題目: IF-ELSE條件語句的翻譯程序設(shè)計（LL（1）法、輸出四元式）初始條件：理論：學(xué)完編譯課程，掌握一種計算機高級語言的使用。實踐：計算機實驗室提供計算機及軟件環(huán)境。如果自己有計算機可以在其上進行設(shè)計。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）（1） 寫出符合給定的語法分析方法的文法及屬性文法。（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、周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日1.問題描述 要求用LL(1)自頂向下分析方法及中間代碼四元式，對IF-THEN-ELSE條件語句完成編譯各階段過程，包括詞法、語法、語義等分析，并完成以下要求： (1)寫出符合給定的語法分析方法的文法及屬性文法。 (2)完成題目要求的中間代碼四元式的描述。 (3)寫出給定的語法分析方法的思想，完成語法分析和語義分析程序設(shè)計。 (4)編制好分析程序后，設(shè)計若干用例，上機測試并通過所設(shè)計的分析程序。 (5)設(shè)計報告格式按附件要求書寫。2.問題分析及編譯系統(tǒng)的概要設(shè)計 編譯過程一般分為六個階段的過程，可以由六個模塊完成，它們稱為詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序，此外，一個完整編譯程序還必須包括“表格管理程序”和“出錯處理程序”。 這次實驗涉及到詞法分析、語法分析、語義分析及表格管理和出錯管理。其中，詞法分析至少要能識別關(guān)鍵字“if”、“then”和“else”，標(biāo)識符（即自定義變量），數(shù)字，和運算符等等；語法分析要分析程序結(jié)構(gòu)的合法性，即是否為文法的句子；語義分析要能夠語法制導(dǎo)翻譯出中間代碼四元式并將其輸出；表格管理是指符號表；出錯處理是指在語法分析時，所有非文法句子的錯誤類型處理。3.文法及屬性文法的定義 3.1 文法 文法是用于描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。這些規(guī)則必須是準(zhǔn)確的、易于理解的以及有相當(dāng)強的描述能力。由這種規(guī)則所產(chǎn)生的程序語言應(yīng)有利于句子分析和翻譯，而且，最好能通過這些規(guī)則自動產(chǎn)生有效的語法分析程序。IF-ELSE條件語句的文法如下所示： 0.A-EB 1.B-+EB|-EB| 2.E-FT 3.T-*FT|/FT| 4.F-i|(E)根據(jù)條件語句： IF 布爾表達式 THEN 賦值語句 ELSE 賦值語句，描述相應(yīng)的文法，其中非終結(jié)符集為VN(A，B，E，T, F),終結(jié)符集為VT(+，-，*，/，i，(，) )。E為布爾表達式，B為賦值語句。 3.2 屬性文法的描述 3.2.1 屬性文法的定義形式 屬性文法是在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號（終結(jié)符或者非終結(jié)符）配備若干相關(guān)的“值”（與文法符號相關(guān)的屬性）。在一個屬性文法中，對應(yīng)于每個產(chǎn)生式Aa都有一套與之相關(guān)聯(lián)的語義規(guī)則，每規(guī)則的形式為：b:=f(c1,c2,，ck)其中f是一個函數(shù)，而且或者b是A的一個綜合屬性并且c1,c2,，ck是產(chǎn)生式右邊文法符號的屬性或者非終結(jié)符既可有綜合屬性也可有繼屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值。 3.2.2 IF THEN ELSE 語句的屬性文法其屬性文法為：0.S-if A THEN B ELSE C S.chain:=merge(A.chain,B.chain, C.chain) 1.A-m rop n A.true:=nextstat; A.false=nextstat+1; backpatch(A.chain,nextstat); emit(“if p” rop “q goto ”) emit(“goto ”) ; 2.B-x=m arop n backpatch(B.chain,nextstat);emit(“ x:= m” arop “n”);emit(“goto ”); 3.C-x=n arop m backpatch(C.chain,nextstat);emit(“ x:= n” arop “m”);emit(“goto ”); 4.rop - = emit(“ = ”); 5. rop - emit(“ emit(“ ”); 7. arop - + emit(“ + ”); 8. arop- - emit(“ - ”); 9.arop- * emit(“ * ”); 10.arop- / emit(“ / ”); 4. 語法分析方法描述及語法分析表設(shè)計 4.1語法分析方法描述 首先應(yīng)該創(chuàng)建一個枚舉類型的變量來存放一些關(guān)鍵字，enum keyword$right_paren,$left_paren,$mul,$div,$add,$sub,$fenhao,$equal,$IF,$THEN,$ELSE,$greater,$less,$id,$num,$end; 再創(chuàng)建一個結(jié)構(gòu)體，用來存放詞法分析的結(jié)果，共有兩個域，一個關(guān)鍵字域，表明他是什么類型，以及它自身的內(nèi)容。 這個詞法分析程序比較簡單，因為本身的程序就局限在if-else語句，所以保留字的類型我就只寫了if、then和else三個；碰到數(shù)字開頭的除了關(guān)鍵字就是標(biāo)識符；碰到數(shù)字開頭的就是數(shù)字；碰到界限符和操作符（因為引入的類型也很少），所以也很容易區(qū)別。在詞法分析結(jié)束之后，就應(yīng)該把分析的結(jié)果輸出來。輸出的格式是【(單詞，類型編號) 類型名】其流程圖為： 源程序文件 字符的分離 單詞的判斷 查找相應(yīng)的表 單詞的類型判斷調(diào)用不同類型的單詞處理函數(shù) 進行單詞的處理 產(chǎn)生類型碼 將中間單詞和其類型碼存入數(shù)組 處理完畢 詞法分析程序如下：bool accidence()int k=0;char buf16;char ch;while(1)insch;if(ins.fail()break;while(ch= )insch;if(ch=I)insbuf;if(strcmp(buf,F)=0)tokentabletotal_len+.type=$IF;else if(ch=T)insbuf;if(strcmp(buf,HEN)=0)tokentabletotal_len+.type=$THEN;else if(ch=E)insbuf;if(strcmp(buf,LSE)=0)tokentabletotal_len+.type=$ELSE;else if(ch=)tokentabletotal_len+.type=$greater;else if(ch=A& ch=a & ch=0 & ch=9)tokentabletotal_len.type=$num; tokentabletotal_len+.ch =ch;elseswitch (ch)case + :tokentabletotal_len.type=$add; tokentabletotal_len+.ch =ch; break; case - :tokentabletotal_len.type=$sub; tokentabletotal_len+.ch =ch; break; case / : tokentabletotal_len.type=$div; tokentabletotal_len+.ch =ch; break; case * :tokentabletotal_len.type=$mul; tokentabletotal_len+.ch =ch;break; case ; :tokentabletotal_len.type=$fenhao; tokentabletotal_len+.ch =ch;break;case ( :tokentabletotal_len.type=$left_paren; tokentabletotal_len+.ch =ch; break;case ) :tokentabletotal_len.type=$right_paren; tokentabletotal_len+.ch =ch;break; default:cout!endl; return true;5.語法分析 語法分析的主要思想是設(shè)置一個分析棧和一個輸入串隊列，棧中最開始時存放的是文法開始符和“#”。因為我這個程序本身已經(jīng)確定是以if語句開頭，所以，就不再把if放在輸入串中，而只是分析if以后的句子。在語法分析之前應(yīng)該判定該文法是不是一個LL(1)文法。判別的主要方法是做出文法中所有產(chǎn)生式的select集，對于同一個非終結(jié)符的不同產(chǎn)生式，如果他們的select集合沒有交集，則說明這個文法是LL(1)文法。這個文法的預(yù)測分析表也設(shè)計的比較簡單，如下表所示：i + - * / ( ) #E 1 0 0 0 0 1 0 0 A 0 1 1 0 0 0 1 1 T 1 0 0 0 0 1 0 0 B 0 1 1 1 1 0 1 1 F 1 0 0 0 0 1 0 0注：1代表此處有產(chǎn)生式與之對應(yīng)，具體的產(chǎn)生式在程序中給出。0代表此處無產(chǎn)生式與之對應(yīng)。/算法函數(shù)char dosome(void) int t,a=0;char bian1,bian2; OpKind opa;char c=$;next();for(;) pop();if(cur.type!=$id & cur.type!=$num)curchar=cur.ch;elsecurchar=i;coutendl;coutcurchar curtocmp1) return c;else return bian1;因為在推導(dǎo)過程中，會一并完成產(chǎn)生式后面附加的語義動作，所以這兩部分是一起做的。另外，在LL(1)分析過程中，會出現(xiàn)錯誤信息，如字符不匹配，或字符沒有出現(xiàn)在產(chǎn)生式終結(jié)符集VT中，或沒有找到合適的候選產(chǎn)生式來做進一步推導(dǎo)，會調(diào)用相應(yīng)的出錯處理函數(shù)err(f)。另外，此函數(shù)是遞歸實現(xiàn)，結(jié)束標(biāo)志是f!=0，即成功或失敗。6.中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計 四元式是一種比較普遍采用的中間代碼形式。四元式的四個組成部分是：操作符OP，第一個和第二個運算 對象ARG1和ARG2及運算結(jié)果RESULT。運算對象和運算結(jié)果有時指用戶自己定義的變量，有時指編譯程序引進的臨時變量。例a:=b*c+b*d的四元式表示如下：(1)(*,b,c,t1)(2)(*,b,d,t2)(3)(+,t1,t2,t3)(4)(:=,t3,-,a)7.語義分析及中間代碼輸出 根據(jù)上面給出的屬性文法所規(guī)定的翻譯方案，即可對輸入的程序進行相應(yīng)的語義分析。對于中間代碼部分，題目是以四元式的形式輸出。對于四元式形式，在學(xué)習(xí)編譯原理的時候接觸的是比較多的了，所以是比較熟悉了。而對于跳轉(zhuǎn)語句，條件跳轉(zhuǎn)如jump L1的四元式形式為(jump,-,-,L1)；而其對應(yīng)的三地址形式為goto L1。而對于條件跳轉(zhuǎn)語句，則四元式為（jrop，a，b，L1）。產(chǎn)生跳轉(zhuǎn)的主要有三個地方，第一，就是if條件成立，則跳轉(zhuǎn)到then后面的語句；第二，執(zhí)行完then后面的語句后跳轉(zhuǎn)到程序的出口；第三，就是if條件不成立則跳轉(zhuǎn)到else后面的語句。在判斷完if后面的條件后，保存這個布爾值，并產(chǎn)生跳轉(zhuǎn)地址，這時，應(yīng)該繼續(xù)向前讀取，如果碰到then這個關(guān)鍵字，則回填地址到then前面，否則報錯。關(guān)鍵是回填地址的那個函數(shù)一定要寫準(zhǔn)確。在有跳轉(zhuǎn)的語句后面，一定要有跳轉(zhuǎn)的地址，即要跳到什么地方。產(chǎn)生跳轉(zhuǎn)的語句有在token這個結(jié)構(gòu)體中有個地址域，用來保存轉(zhuǎn)向的地址。而在產(chǎn)生運算結(jié)果的語句中，token這個結(jié)構(gòu)體中有個result域，用來保存這個結(jié)果。/產(chǎn)生數(shù)值語句的四元式void AD_RESULT(int nlabel,OpKind nop,char npar1,char npar2, char nresult)quadquad_len.label=nlabel; quadquad_len.op=nop; quadquad_len.par1=npar1; quadquad_len.par2=npar2; quadquad_len.result=nresult; quad_len+; /產(chǎn)生跳轉(zhuǎn)地址的四元式void AD_ADDRESS(int nlabel,OpKind nop,char npar1,char npar2,int naddress) quadquad_len.label=nlabel; quadquad_len.op=nop;quadquad_len.par1=npar1;quadquad_len.par2=npar2; quadquad_len.address=naddress;quad_len+; /回填出口void backpath(int nlabel,int addr) quadnlabel.address=addr;8.程序流程圖 開始 “#”“S”進棧，讀輸入流一符號=a對產(chǎn)生式右部x1x2.xn按逆序即xnxn-1.x1 壓入棧中棧頂元素出棧并送X讀入符號=aX=a？XVTyy YN N出錯處理X=#？MX,a為產(chǎn)生式？NNN NX=a? 出錯處理N結(jié)束Y9.設(shè)計結(jié)果顯示輸入要編譯文件的文件名:test.txt測試結(jié)果如下： 10.研制報告10.1研制過程 拿到設(shè)計題目以后，首先是構(gòu)造符合題意的文法，然后構(gòu)造文法所對應(yīng)的優(yōu)先關(guān)系表。完成這兩步之后，開始編寫源程序。編譯程序主要分成三大模塊，詞法分析模塊、語法語義分析模塊和中間代碼生成和輸出。 首先進行詞法分析，對輸入的符號串進行分析，判斷出關(guān)鍵字，數(shù)字，終結(jié)符和非終結(jié)符。然后進行語法分析，根據(jù)每個產(chǎn)生式的select集，然后得出文法的預(yù)測分析表。最后通過語義分析，完成分析過程，并生成相應(yīng)的中間代碼。最后，將生成的中間代碼輸出。 10.2本設(shè)計的評價、特點、不足、收獲與體會等 本程序能正確實現(xiàn)對IF-ELSE條件語句的翻譯工作，能夠?qū)λ斎氲淖址Z句進行詞法分析、語法語義分析以及生成相應(yīng)的四元式中間代碼并輸出，正確完成了實驗的要求。但是，程序本身還是不夠完善的，如不能實現(xiàn)IF語句的嵌套，還有對單詞的容錯能力不強,另外，還有表達式的分析過程，而沒有把if-else-then這些關(guān)鍵字的分析過程加入進來。雖然課設(shè)時間有限，但我相信隨著自己編程水平的提高，這些缺陷一定會得到解決的。 LL(1)的分析方法，這個方法的關(guān)鍵首先要構(gòu)造一個if-else語句的文法，然后將其轉(zhuǎn)換為LL(1)文法，再根據(jù)每個產(chǎn)生式的select集構(gòu)造預(yù)測分析表。然后就是相應(yīng)的分析。然后根據(jù)預(yù)測分析表做出相應(yīng)的推導(dǎo)和匹配動作，最后如果棧里的內(nèi)容和隊列里的內(nèi)容都是以“#”號的形式匹配的話，這個語句就分析成功。這次設(shè)計也是針對一個特定的語句來進行分析的，所以我就假設(shè)所有的輸入串當(dāng)中都在相應(yīng)的位置有那些關(guān)鍵字了。所以程序做起來就比較簡單，容易實現(xiàn)。 這次課程設(shè)計使得我受益匪淺，尤其是對優(yōu)先關(guān)系分析方法有了更深的理解和掌握。通過這次課程設(shè)計，我的編程能力又得到進一步的提高，同時也培養(yǎng)了我思維能力?？傊@次課程設(shè)計不僅豐富了我的理論知識，也加強了我的動手能力，還鍛煉了我的思維能力。在實驗程序編寫和調(diào)試過程中我學(xué)會了很多，也認(rèn)識到了自己的不足，我還需要進一步的努力，以致取得更大的進步。我需要的就是要對自己有信心，腳踏實地，持之以恒，遇到困難時要冷靜思考，勇敢面對，直到得出結(jié)果。在實驗設(shè)計過程中，我也養(yǎng)成了較好地習(xí)慣，先有框架，然后跟著框架發(fā)展，最后就是要注重細(xì)節(jié)，要做到嚴(yán)謹(jǐn)和縝密。不可否認(rèn)這種好習(xí)慣讓我受益無限，我也必須擁有它，以致我獲得更多。11.源程序清單 /基于LL(1)法的條件語句語法語義分析程序 #include#include#include#include#includeenum keyword $right_paren,$left_paren,$mul,$div,$add,$sub,$fenhao, $equal,$IF,$THEN,$ELSE,$greater,$less,$id,$num,$end;typedef struct Token keyword type;char ch;Token;typedef enumJUMP,JG,JL,equal,END,add,mul,sub,divOpKind;typedef struct int label;/標(biāo)號OpKind op;/操作符char par1,par2;/操作數(shù)unionchar result;/結(jié)果int address;/地址;Quad; /四元式入口#define MAX_TOKEN 256/Token表大小#define MAX_QUAD 256/四元式數(shù)組大小Token tokentableMAX_TOKEN;Quad quadMAX_QUAD;int token_index;/token表索引int total_len;/token表有效長度int quad_len;/四元式表有效長度int quad_index;/四元式索引Token cur;Token queue10;int label,k,one; /標(biāo)記接口char curchar;/存儲當(dāng)前待比較字符char curtocmp;/存儲當(dāng)前棧頂字符ifstream ins;int trueadd,falseadd,end; int table58=1,0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,0,0,0,1,0,0,0,1,1,1,1,0,1,1,1,0,0,0,0,1,0,0; /存儲預(yù)測分析表，1為有產(chǎn)生式，0為沒有int i,j;int flag;struct Lchar char char_ch;struct Lchar *next;Lchar,*temp,*top,*base;int right;/定義開關(guān)項bool initialize(char filename255);/文件打開初始化bool accidence();/詞法分析void print();/輸出單詞表void backpath(int,int);/回填出口void ERROR();void sentence();/分析語句void boolean();/ 分析E-id id語句bool nexttoken();/讀下一單詞char newchar();void push();/進隊列char dosome(void);/算法函數(shù)void pushs(char pchar);/入棧函數(shù)void pop(void);/出棧函數(shù)void doforpush(int t);/根據(jù)數(shù)組下標(biāo)計算的值產(chǎn)生式入棧void changchartoint();/根據(jù)curchar,curtocmp轉(zhuǎn)為數(shù)字以判斷是否有產(chǎn)生式void semantic();/語法語義分析char LL1();/LL(1)文法分析void printQuad();/輸出四元式void ERROR(char str20);void AD_ADDRESS(int nlabel,OpKind nop,char npar1,char npar2,int naddress);void AD_RESULT(int nlabel,OpKind nop,char npar1,char npar2, char nresult);void main() cout endl 基于LL(1)法的條件語句語法語義分析程序 endl endl;coutfname;if(!initialize(fname)return;if(!accidence()return;char ch;while(1) if(ins.eof()break;insch;coutendl詞法分析結(jié)果如下:;print();coutendl;cout詞法分析結(jié)束。endlendl;semantic(); /語法語義分析coutendl輸出四元式:endl;printQuad();if(right=1)cout分析成功endl;elsecout分析失敗endl;cout語法語義分析結(jié)束endl;char newchar() char p; p=char(k);k+;return p; /文件打開初始化bool initialize(char filename100) one=0;token_index=0;total_len=0;quad_len=0;quad_index=0;label=0;end=0;k=48;ins.open(filename,ios:nocreate | ios:in);if(ins.fail() cout文件打開出錯!ch;if(ins.fail()break;while(ch= )insch;if(ch=I) insbuf;if(strcmp(buf,F)=0)tokentabletotal_len+.type=$IF;else if(ch=T) insbuf;if(strcmp(buf,HEN)=0)tokentabletotal_len+.type=$THEN;else if(ch=E) insbuf;if(strcmp(buf,LSE)=0)tokentabletotal_len+.type=$ELSE;else if(ch=) tokentabletotal_len+.type=$greater;else if(ch=A& ch=a & ch=0 & ch=9)tokentabletotal_len.type=$num; tokentabletotal_len+.ch =ch;elseswitch (ch)case + :tokentabletotal_len.type=$add; tokentabletotal_len+.ch =ch; break; case - :tokentabletotal_len.type=$sub; tokentabletotal_len+.ch =ch; break; case / : tokentabletotal_len.type=$div; tokentabletotal_len+.ch =ch; break; case * :tokentabletotal_len.type=$mul; tokentabletotal_len+.ch =ch;break; case ; :tokentabletotal_len.type=$fenhao; tokentabletotal_len+.ch =ch;break;case ( :tokentabletotal_len.type=$left_paren; tokentabletotal_len+.ch =ch; break;case ) :tokentabletotal_len.type=$right_paren; tokentabletotal_len+.ch =ch;break; default:cout!endl; return true;/語法語義分析void semantic() if(!nexttoken()ERROR(s(0); cout開始進行語法語義分析:endl 所使用的產(chǎn)生式:endl - if E then S else Sendl if E then else P2endl abendl x:=a*cendl x:=b*cendl 語法語義分析過程如下:=total_len)return false;if(tokentabletoken_index.type=$fenhao)token_index+;cur.type=tokentabletoken_index.typ