IF-ELSE條件語句的翻譯程序設計(LL(1)法、輸出三地址表示) 2

1、武漢理工大學編譯原理課程設計說明書IF-ELSE條件語句的翻譯程序設計1 問題描述 要求用LL(1)自頂向下分析方法及三地址中間代碼，對IF-THEN-ELSE條件語句完成編譯各階段過程，包括詞法、語法、語義等分析。2 問題分析及編譯系統(tǒng)的概要設計 編譯過程一般分為六個階段的過程，可以由六個模塊完成，它們稱為詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標代碼生成程序，此外，一個完整編譯程序還必須包括“表格管理程序”和“出錯處理程序”。 這次實驗涉及到詞法分析、語法分析、語義分析及表格管理和出錯管理。其中，詞法分析至少要能識別關鍵字“if”、“then”和“els

2、e”，標識符（即自定義變量），數(shù)字，和運算符等等；語法分析要分析程序結構的合法性，即是否為文法的句子；語義分析要能夠語法制導翻譯出中間代碼（三地址）并將其輸出；表格管理是指符號表；出錯處理是指在語法分析時，所有非文法句子的錯誤類型處理.3 文法及屬性文法的定義 3.1 文法：文法是用于描述語言的語法結構的形式規(guī)則（即語法規(guī)則）。這些規(guī)則必須是準確的、易于理解的以及有相當強的描述能力。由這種規(guī)則所產生的程序語言應有利于句子分析和翻譯，而且，最好能通過這些規(guī)則自動產生有效的語法分析程序.IF-ELSE條件語句的文法如下所示： 0A->EB 1.B->+EB|-EB| 2.E->F

3、T 3.T->*FT|/FT| 4.F->i|(E) 或者能夠更簡潔一點: 0.S->if A THEN B ELSE C 1.A->m rop n 2.B->x=m arop n 3.C->x=n arop m 4.rop->=|<|> 5.arop->+|-|*|/3.2 屬性文法： 屬性文法是在上下文無關文法的基礎上，為每個文法符號（終結符或者非終結符）配備若干相關的“值”（與文法符號相關的屬性）。 在一個屬性文法中，對應于每個產生式Aa都有一套與之相關聯(lián)的語義規(guī)則，每規(guī)則的形式為：b:=f(c1,c2,，ck)其中f是一個函數(shù)

4、，而且或者b是A的一個綜合屬性并且c1,c2,，ck是產生式右邊文法符號的屬性或者非終結符既可有綜合屬性也可有繼屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值。屬性文法為：if(VTopr='=') /"="判斷；arrd1=arr_iopd;arrd0='='arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='>') /">"判斷；arrd1=arr_iopd;arrd0='>'arrd2=i

5、d;arrd3=' 'arrd4=' 'id+;else if(VTopr='<') /"<"判斷；arrd1=arr_iopd;arrd0='<'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='+') /"+"判斷；arrd1=arr_iopd;arrd0='+'arrd2=id;arrd3=' 'arrd4=' 'id+;else

6、if(VTopr='-') /"-"判斷；arrd1=arr_iopd;arrd0='-'arrd2=id;arrd3=' 'arrd4=' 'id+; else if(VTopr='*') /"*"判斷；arrd1=arr_iopd;arrd0='*'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='/') /"/"判斷；arrd1=arr_iopd

7、;arrd0='/'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(opr=-2) /其他字符判斷；arrd1=id-1; arrd0=' 'arrd2=arr_iopd;arrd3=' 'arrd4=' 'else if(VTopr!='<'&&VTopr!='>'&&VTopr!='+'&&VTopr!='-'&&VTopr!=

8、'*'&&VTopr!='/')/"#"結束符判斷； arrd1=id-1;d+;4 詞法分析 首先應該創(chuàng)建一個枚舉類型的變量來存放一些關鍵字： char VN11='K','L','P','S','E','G','T','R','F','Q','0' /產名生式頭 char VT16='i','=','<&

9、#39;,'>','+','-','*','/','(',')','f','t','e','','0' /特征字符集 再創(chuàng)建一個結構體，用來存放詞法分析的結果，共有兩個域，一個關鍵字域，表明他是什么類型，以及它自身的內容。 這個詞法分析程序比較簡單，因為本身的程序就局限在if-else語句，所以保留字的類型我就只寫了if、then和else三個；碰到數(shù)字開頭的除了關鍵字就是標識符；碰到數(shù)字開頭的就是

10、數(shù)字；碰到界限符和操作符（因為引入的類型也很少），所以也很容易區(qū)別。 在詞法分析結束之后，就應該把分析的結果輸出來。輸出的格式是【（單詞，類型編號） 類型名】 源程序文件字符的分離 單詞的判斷查找相應的表單詞的類型的判斷調用不同類型的單詞處理函數(shù)進行單詞的處理產生類型碼將中間單詞和其類型碼存入數(shù)組處理完畢 詞法分析程序如下： void lexical() /"ifm>n theni=i+9 elseb=b/3#"是其一條特殊的例子 int i,j,d; char ch; j=d=0; for(i=0;vari!='#'i+) ch=vari; if(c

11、h='i'&&vari+1='f') cout<<"if"<<'t'<<"keyword"<<'t'<<'t'<<"關鍵字"<<endl; queuej+='f'i+=1; /判斷"if"關鍵字 else if(ch='t') ch=vari+1; if(ch='h') ch=vari+2;

12、 if(ch='e') ch=vari+3; if(ch='n') ch=vari+4;cout<<"then"<<'t'<<"keyword"<<'t'<<'t'<<"關鍵字"<<endl;queuej+='t'i+=3;/判斷"then"關鍵字else if(ch='e')ch=vari+5;if(ch='l&

13、#39;)ch=vari+6;if(ch='s')ch=vari+7;if(ch='e')ch=vari+8;cout<<"else"<<'t'<<"keyword"<<'t'<<'t'<<"關鍵字"<<endl;queuej+='e'i+=3;/判斷"else"關鍵字else if(index(ch,VT)<=0)if(ch!=&

14、#39;'&&ch!=''&&ch!='('&&ch!=')')cout<<ch<<'t'<<"variable:i"<<d+<<""<<'t'<<"標示符"<<endl;arr_id-1=ch;queuej+='i'else cout<<ch<<'t'

15、;<<"bound"<<'t'<<'t'<<"括 號"<<endl;else if(index(ch,VT)>0)cout<<ch<<'t'<<"operator"<<'t'<<"運算符"<<endl;queuej+=ch; queuej='#'/"#"就直接跳出 for(i=0;

16、queuei!='#'i+)cout<<queuei; cout<<endl; 5 語法分析 主要的思想是設置一個分析棧和一個輸入串隊列，棧中最開始時存放的是文法開始符和“#”。因為我這個程序本身已經確定是以if語句開頭，所以，就不再把if放在輸入串中，而只是分析if以后的句子。在語法分析之前應該判定該文法是不是一個LL(1)文法。判別的主要方法是做出文法中所有產生式的select集，對于同一個非終結符的不同產生式，如果他們的select集合沒有交集，則說明這個文法是LL(1)文法。這個文法的預測分析表也設計的比較簡單，如下表所示： -1, -1, -1

17、, -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, -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,

18、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, -1,- 1,- 1, -1, /預測分析表注：除了-1代表此處有產生式與之對應，具體的產生式在程序中給出。-1代表此處無產生式與之對應。void syntax()int n;

19、count+;print();X=stacksp;a=queuefront;if(X='#'&&a='#')f=4;if(X<'A'|X>'Z') /判斷字符集不是大寫字母集合if(X=a)sp-;front+;if(a!='i') /"i"是特征字母if(a!='f'&&a!='t'&&a!='e'&&a!=''&&a!='#

20、9;)opr=index(a,VT);semantic();else if(a=''|a='e'|a='t'|a='#') opr=-2;semantic();cout<<'t'<<'''<<a<<"'匹配"<<endl;elseopd=c;/cout<<opd1<<" "<<opd2;cout<<'t'<<&

21、#39;''<<arr_ic+<<"'匹配"<<endl;else f=1; /字符不匹配,轉去出錯處理elseint tx=index(X,VN);/索引選擇int ta=index(a,VT);/索引選擇n=Mtxta; /產生式選擇tdt+=Mtxta; /產生式選擇if(ta=-1)f=2;cout<<a<<endl; /字符沒有出現(xiàn)在產生式終結符集VT中,轉去出錯處理else if(n=-1)f=3; /沒有找到合適的候選產生式來做進一步推導,轉去出錯處理else /用產生式Mtx

22、ta來做進一步推導sp-;cout<<'t'<<X<<"->"if(len(pn)!=0)for(int i=len(pn)-1;i>=0;i-)stack+sp=pni;cout<<pnlen(pn)-1-i;cout<<endl;else cout<<"空串"<<endl; if(f=0)syntax();else tdt='-1'err(f);因為在推導過程中，會一并完成產生式后面附加的語義動作，所以這兩部分是一起做的。另

23、外，在LL(1)分析過程中，會出現(xiàn)錯誤信息，如字符不匹配，或字符沒有出現(xiàn)在產生式終結符集VT中，或沒有找到合適的候選產生式來做進一步推導，會調用相應的出錯處理函數(shù)err(f)。另外，此函數(shù)是遞歸實現(xiàn)，結束標志是f!=0，即成功或失敗。6 出錯處理由于輸入的表達式有錯誤就要產生相應的出錯處理函數(shù)void err(int n)if(n=1)cout<<"字符不匹配"<<endl;else if(n=2)cout<<"字符沒有出現(xiàn)在產生式終結符集VT中"<<endl;else if(n=3)cout<<

24、;"沒有找到合適的候選產生式來做進一步推導"<<endl;else cout<<"該句子是文法語言的句子！"<<endl;7 語義分析及中間代碼輸出 根據上面給出的屬性文法所規(guī)定的翻譯方案，即可對輸入的程序進行相應的語義分析。對于中間代碼部分，老師給的題目是以三地址的形式輸出。對于三地址形式，在學習編譯原理的時候接觸的不是很多。我們接觸的多的一般都是逆波蘭式和四元式。仔細看書才發(fā)現(xiàn)，三地址和四元式是很相近的。比如說計算一個表達式a+b-c，四元式的形式是（+，a,b,t1）,(-,t1,c,t2)。而三地址的形式為t1

25、:=a+b,t2=t1-c。而對于跳轉語句，無條件跳轉如jump L1的四元式形式為(jump,-,-,L1)；而其對應的三地址形式為goto L1。而對于條件跳轉語句，則四元式為（jrop，a，b，L1），而三地址形式為if a rop b goto L1。產生跳轉的主要有三個地方，第一，就是if條件成立，則跳轉到then后面的語局；第二，執(zhí)行完then后面的語句后跳轉到程序的出口；第三，就是if條件不成立則跳轉到else后面的語句。在判斷完if后面的條件后，保存這個布爾值，并產生跳轉地址，這時，應該繼續(xù)向前讀取，如果碰到then這個關鍵字，則回填地址到then前面，否則報錯。 關鍵是回填地

26、址的那個函數(shù)一定要寫準確。在有跳轉的語句后面，一定要有跳轉的地址，即要跳到什么地方。產生跳轉的語句有在token這個結構體中有個地址域，用來保存轉向的地址。而在產生運算結果的語句中，token這個結構體中有個result域，用來保存這個結果。 /打印詞法分析結果void print()cout<<"("if(count<10)cout<<'0'cout<<count<<")"int i;for(i=0;i<=sp;i+)cout<<stacki;for(;i<=

27、20;i+)cout<<" "for(i=0;i<front;i+)cout<<" "for(;queuei!='#'i+)cout<<queuei;cout<<queuei;for(;i<=20;i+)cout<<" "/語義分析程序void semantic()if(VTopr='=') /"="判斷；arrd1=arr_iopd;arrd0='='arrd2=id;arrd3=' &

28、#39;arrd4=' 'id+;else if(VTopr='>') /">"判斷；arrd1=arr_iopd;arrd0='>'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='<') /"<"判斷；arrd1=arr_iopd;arrd0='<'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTo

29、pr='+') /"+"判斷；arrd1=arr_iopd;arrd0='+'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='-') /"-"判斷；arrd1=arr_iopd;arrd0='-'arrd2=id;arrd3=' 'arrd4=' 'id+; else if(VTopr='*') /"*"判斷；arrd1=arr_iopd;arrd0

30、='*'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='/') /"/"判斷；arrd1=arr_iopd;arrd0='/'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(opr=-2) /其他字符判斷；arrd1=id-1; arrd0=' 'arrd2=arr_iopd;arrd3=' 'arrd4=' 'else if(VTopr!=&

31、#39;<'&&VTopr!='>'&&VTopr!='+'&&VTopr!='-'&&VTopr!='*'&&VTopr!='/')/"#"結束符判斷； arrd1=id-1;d+;/輸出三地址cout<<"輸出三地址:"<<endl;for(i=0;i<d;i+)for(int j=0;j<5;j+)if(arrij>=0&

32、&arrij<=9)cout<<"("<<char(arrij+'0')<<")"<<" "else cout<<arrij<<" "cout<<endl; 而三元式的輸出則很簡單。但也要根據它具體的語義來進行輸出。如果是if語句，則要根據if后面的bool語句來實現(xiàn)跳轉。如果為真，應該調到then后面的語句，如果為假，則跳轉到else后面的語句，每個語句都有自己的標號，用label來標識。而對于每個計

33、算結果的表達式，則首先用一個中間變量來存放結果，每次按照運算符的優(yōu)先級算出一個結果，保存在中間變量中，最后將中間變量的結果賦給語句中的變量。 8 軟件測試方法和結果 輸入一組正確的詞法和語法的if-else語句，和一組有詞法錯誤和語法錯誤的if語句。 1. if m>n then i=i+3else b=b/2 測試結果如下： 2. if1 m>n then i=i*3else b=b-1測試的結果如下所示：9 分析本次設計 這次設計大體上還是自己動腦筋去想了，去做了。所以覺得并不是那么的難。關鍵的步驟就是三個，設計詞法分析程序，語法分析程序，及語義分析程序和中間代碼的輸出程序。詞

34、法分析程序由于上次實驗做過了，所以這次做起來還是比較的順手，只是這次的單詞設計的比較簡單，如關鍵字就只有三個，if、else和then；用戶自定義變量的標識符也沒有考慮以下劃線開頭的部分。 我做的語法分析方法是ll（1）的分析方法，這個方法的關鍵首先要構造一個if else語句的文法，然后將其轉換為ll（1）文法，再根據每個產生式的select集構造預測分析表。然后就是相應的分析。構造一個分析棧和一個輸入串隊列，棧的初始內容是文法的開始符號和“#”，輸入串隊列則是輸入串的內容。然后根據預測分析表做出相應的推導和匹配動作，最后如果棧里的內容和隊列里的內容都是以“#”號的形式匹配的話，這個語句就分

35、析成功。我這次主要只是考慮了表達式的分析過程，而沒有把if else then這些關鍵字的分析過程加入進來。因為我們這次設計也是針對一個特定的語句（如我的if else語句）來進行分析的，所以我就假設所有的輸入串當中都在相應的位置有那些關鍵字了。所以程序做起來就比較簡單，容易實現(xiàn)。 而語義分析則是要識別這句話要做什么，并且將其要做的事情用三地址的形式翻譯出來。這個對我來說的確有點困難，所以見參考了一下其他同學的設計方法。這個也是這次設計的不足之處，望老師見諒-。10 參考文獻1 張素琴、呂映芝、蔣維杜、戴桂蘭等編譯原理（第2版）清華大學出版社2005年2月參考書：2 程序設計語言編譯原理 國防

36、工業(yè)出版社 陳火旺著3 編譯原理習題與解析 清華大學出版社出版社 伍春香著 11 源程序清單#include<iostream.h>#define MAX 100 char X,a;char VN11='K','L','P','S','E','G','T','R','F','Q','0' /產名生式頭char VT16='i','=','<','&

37、gt;','+','-','*','/','(',')','f','t','e','','0' /特征字符集char p188="fLtLeS0","SP0","0","0","iQE0","TG0","+TG0","-TG0","0"

38、,"FR0","*FR0","/FR0","0","(E)0","i0","=0","<0",">0"/產生式集合數(shù)組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,-

39、1,-1,-1,-1,-1,-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

40、,-1,-1,-1,-1,-1,-1,; /預測分析表int f=0;int count=0;int c=0;char arr_iMAX; /字符管理char varMAX; /表格管理int tdMAX; /輸出產生式序列int t=0;int opd=-1;int opr=-1;int id=0;/int ptrMAX;int d=0;char arrMAX5; /存放待輸出的三地址/char keyword211="if0","then0","else0"int len(char str)int i=0;while(stri!=

41、'0')i+;return i;int index(char ch,char str)int i=0;while(stri!='0')if(ch!=stri)i+;else break;if(stri='0')return -1;return i;/出錯管理選項void err(int n)if(n=1)cout<<"字符不匹配"<<endl;else if(n=2)cout<<"字符沒有出現(xiàn)在產生式終結符集VT中"<<endl;else if(n=3)cou

42、t<<"沒有找到合適的候選產生式來做進一步推導"<<endl;else cout<<"該句子是文法語言的句子！"<<endl;/打印此法分析結果void print()cout<<"("if(count<10)cout<<'0'cout<<count<<")"int i;for(i=0;i<=sp;i+)cout<<stacki;for(;i<=20;i+)cout<&

43、lt;" "for(i=0;i<front;i+)cout<<" "for(;queuei!='#'i+)cout<<queuei;cout<<queuei;for(;i<=20;i+)cout<<" "/語義分析程序void semantic()if(VTopr='=') /"="判斷；arrd1=arr_iopd;arrd0='='arrd2=id;arrd3=' 'arrd4='

44、 'id+;else if(VTopr='>') /">"判斷；arrd1=arr_iopd;arrd0='>'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='<') /"<"判斷；arrd1=arr_iopd;arrd0='<'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='+')

45、 /"+"判斷；arrd1=arr_iopd;arrd0='+'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='-') /"-"判斷；arrd1=arr_iopd;arrd0='-'arrd2=id;arrd3=' 'arrd4=' 'id+; else if(VTopr='*') /"*"判斷；arrd1=arr_iopd;arrd0='*'arr

46、d2=id;arrd3=' 'arrd4=' 'id+;else if(VTopr='/') /"/"判斷；arrd1=arr_iopd;arrd0='/'arrd2=id;arrd3=' 'arrd4=' 'id+;else if(opr=-2) /其他字符判斷；arrd1=id-1; arrd0=' 'arrd2=arr_iopd;arrd3=' 'arrd4=' 'else if(VTopr!='<'&a

47、mp;&VTopr!='>'&&VTopr!='+'&&VTopr!='-'&&VTopr!='*'&&VTopr!='/')/"#"結束符判斷； arrd1=id-1;d+;/語法分析程序void syntax()int n;count+;print();X=stacksp;a=queuefront;if(X='#'&&a='#')f=4;if(X<'A&

48、#39;|X>'Z') /判斷字符集不是大寫字母集合if(X=a)sp-;front+;if(a!='i') /"i"是特征字母if(a!='f'&&a!='t'&&a!='e'&&a!=''&&a!='#')opr=index(a,VT);semantic();else if(a=''|a='e'|a='t'|a='#') opr

49、=-2;semantic();cout<<'t'<<'''<<a<<"'匹配"<<endl;elseopd=c;/cout<<opd1<<" "<<opd2;cout<<'t'<<'''<<arr_ic+<<"'匹配"<<endl;else f=1; /字符不匹配,轉去出錯處理elsei

50、nt tx=index(X,VN);/索引選擇int ta=index(a,VT);/索引選擇n=Mtxta; /產生式選擇tdt+=Mtxta; /產生式選擇if(ta=-1)f=2;cout<<a<<endl; /字符沒有出現(xiàn)在產生式終結符集VT中,轉去出錯處理else if(n=-1)f=3; /沒有找到合適的候選產生式來做進一步推導,轉去出錯處理else /用產生式Mtxta來做進一步推導sp-;cout<<'t'<<X<<"->"if(len(pn)!=0)for(int i=len

51、(pn)-1;i>=0;i-)stack+sp=pni;cout<<pnlen(pn)-1-i;cout<<endl;else cout<<"空串"<<endl; if(f=0)syntax();else tdt='-1'err(f);/測法分析程序void lexical() /"ifm>n theni=i+9 elseb=b/3#"是其一條特殊的例子int i,j,d;char ch;j=d=0;for(i=0;vari!='#'i+)ch=vari;if(c

52、h='i'&&vari+1='f')cout<<"if"<<'t'<<"keyword"<<'t'<<'t'<<"關鍵字"<<endl; queuej+='f'i+=1;/判斷"if"關鍵字else if(ch='t')ch=vari+1;if(ch='h')ch=vari+2;if(ch=

53、'e')ch=vari+3;if(ch='n')ch=vari+4;cout<<"then"<<'t'<<"keyword"<<'t'<<'t'<<"關鍵字"<<endl;queuej+='t'i+=3;/判斷"then"關鍵字else if(ch='e')ch=vari+5;if(ch='l')ch=va

54、ri+6;if(ch='s')ch=vari+7;if(ch='e')ch=vari+8;cout<<"else"<<'t'<<"keyword"<<'t'<<'t'<<"關鍵字"<<endl;queuej+='e'i+=3;/判斷"else"關鍵字else if(index(ch,VT)<=0)if(ch!=''&&ch!=''&&ch!='('&&ch!=')')cout<<ch<<'t'<<"variable:i"<<d+<<""<<'