編譯原理ex3over

1、實驗報告學院（系）名稱：計算機與通信工程學院姓名孟于杰學號20091985專業(yè)計算機科學與技術班級2009級1班實驗項目實驗三：語義分析與中間代碼生成課程名稱編譯原理課程代碼0668056實驗時間2012年5月11日 第1、2節(jié)2012年5月15日 第9、10節(jié)2012年5月18日 第1、2節(jié)實驗地點計算機軟件實驗室7-219批改意見成績教師簽字： 實驗內容：可選擇LL1分析法、算符優(yōu)先分析法、LR分析法之一，實現如下表達式文法的語法制導翻譯過程。文法GE如下所示：EE+T | E-T | TTT*F | T/F | FFPF | PP(E) | i要求構造出符合語義分析要求的屬性文法描述，并

2、在完成實驗二（語法分析）的基礎上，進行語義分析程序設計，最終輸出與測試用例等價的四元式中間代碼序列。實驗目的：1掌握語法制導翻譯的基本功能。2鞏固對語義分析的基本功能和原理的認識。3能夠基于語法制導翻譯的知識進行語義分析。4掌握類高級語言中基本語句所對應的語義動作。5理解并處理語義分析中的異常和錯誤。實驗要求：1在實驗二的基礎上，實現語法制導翻譯功能，輸出翻譯后所得四元式序列；2要求詳細描述所選分析方法進行制導翻譯的設計過程；3完成對所設計分析器的功能測試，并給出測試數據和實驗結果；4為增加程序可讀性，請在程序中進行適當注釋說明；5整理上機步驟，總結經驗和體會；6認真完成并按時提交實驗報告?！?/p>

3、實驗過程記錄（源程序、測試用例、測試結果及心得體會等）】算符優(yōu)先文法構造FIRSTVT、LASTVT、算符優(yōu)先關系表:在構造FIRSTVT表時，通過循環(huán)找出每條產生式中的非終結符的FIRSTVT集，并把該非終結符和終結符壓棧，設置標志位，標志一對非終結符和終結符具有對應關系。LASTVT表的構造則是將求FIRSTVT的過程翻轉過來，可以僅僅將函數中的參數稍作修改就能夠完成。算符優(yōu)先關系表是一個二維數組，用來存放任意兩個終結符之間的優(yōu)先關系。首先構造表頭，通過掃描所有產生式將終結符不重復的存放在一個一維數組中并置為優(yōu)先關系表的行和列，并將優(yōu)先關系表其他內容全部初始化為空。接著遍歷所有產生式，找出

4、任意兩個終結符之間存在的關系（可以沒有關系），并判斷任意兩終結符是否至多存在一種優(yōu)先關系，如發(fā)現優(yōu)先關系表不為空，則證明該文法不是算符優(yōu)先文法，否則，將相應的關系填入到相應的行列對應的單元中。輸入串分析過程的設計。首先將大于、小于、等于和無關系分別定義成一種類型的數據表示，通過查詢符號棧棧頂以及當前符號之間的優(yōu)先關系來判斷移進和規(guī)約的操作。計算FirstVT和LastVT初始化是否是P-a.，斷：文法的第四個字符是否屬于終結符VT否是判斷是否是P-Qa.是將P的位置和a的位置計算出，（P，a）入棧將P的位置和a的位置計算出，（P，a）入棧循環(huán)判斷是否是P-Q.,將p-Q.中的P和（T,n）中的

5、n入棧規(guī)約過程開始時，將#和文法開始符號放入棧底?？偪爻绦蛟谌魏螘r候都是根據棧頂符號X和當前的輸入符號進行工作的，它與文法無關 總控程序根據現行棧頂符號X和當前輸入符號a，執(zhí)行下列三種動作之一:1. 若Xa，則宣布分析成功，停止分析。2. 若Xa ，則把X從STACK棧頂逐出，讓指針指向下一個輸入符號。3.若X是一個非終結符，則查看分析表M。 若MX，a中存放著關于X的一個產生式，把X逐出STACK棧頂，把產生式的右部符號串按反序一一推進STACK棧(若右部符號為e，則意味不推什么東西進棧)。在把產生式的右部符號推進棧的同時應做這個產生式相應的語義動作。若MX，a中存放著“出錯標志”，則調用出

6、錯診察程序ERROR。/要分析的文法string E10=E-E+T,E-E-T,E-T,T-T*F,T-T/F,T-F,F-PF,F-P,P-(E),P-i;char upper4=E,T,F,P;char lower8=+,-,/,*,(,),i;void insert(char T,char n);/入棧操作bool SignArray2020;/標記數組，標記每一個是FIRSTVT、LastVTvoid CreateFIRSTVT(); /構造FIRSTVT的函數void PrintFirstvt();bool IsT(char); /判斷是否為終結符bool IsN(char); /

7、判斷是否為非終結符程序結構：重要代碼void zh(int n)if(n=300)coutTn-300;elsecoutchar(n);int p(char n)if(n=)return 0;else if(n=)return 10;else if(n=+|n=-)return 20;else if(n=*|n=/)return 30;else if(n=()return 40;else return -1;class CreateFirstvt /構造FIRSTVT的類public: CreateFirstvt();CreateFirstvt()void insert(char T,char

8、 n);bool SignArray2020;/標記數組，標記每一個是FIRSTVTvoid CreateFIRSTVT(); /構造FIRSTVT的函數 void PrintFirstvt();bool IsT(char); /判斷是否為終結符bool IsN(char); /判斷是否為非終結符private:string stack50;/棧int top;CreateFirstvt:CreateFirstvt()/初始化SignArraytop=0;for(int i=0;i20;i+)for(int j=0;j20;j+)SignArrayij=false;void CreateFir

9、stvt:insert(char T,char n)for(int j=0;j4;j+)/判斷是否為VT，并標記位置if(T=upperj)break;for(int k=0;k8;k+)/判斷是否為VN，并標記位置if(n=lowerk)break;if(SignArrayjk=false)SignArrayjk=true;stacktop=(;stacktop.append(1,T);stacktop+=,;stacktop.append(1,n);stacktop+=);top+;/不在棧中，則將“(P,a)”入棧void CreateFirstvt:CreateFIRSTVT()for

10、(int i=0;ia.這種情況char pos1,pos2;pos1=Ei.at(0);/P-a. 將P給pos1pos2=Ei.at(3);/p-a. 將a給pos2insert(pos1,pos2);/a屬于P的首符集if(IsN(Ei.at(3) & Ei.length()4 & IsT(Ei.at(4) /處理P-Qa.這種情況char pos1,pos2;pos1=Ei.at(0);pos2=Ei.at(4);insert(pos1,pos2);while(top!=0) /處理P-Q.這種情況string PopElement=stack-top;stacktop=;char p

11、os1,pos2;for(i=0;iQ.中的Q 相等pos1=Ei.at(0);/p-Q.的P和(T,n)中的n入棧pos2=PopElement.at(3);insert(pos1,pos2);void CreateFirstvt:PrintFirstvt()cout*endl;cout打印文法的FIRSTVT:endlendl;cout文法的FIRSTVT(E):endl;for(int i=0;i4;i+)for(int j=0;j8;j+)if(SignArrayij=true & upperi=E)coutlowerj ;if(upperi=E)break;coutendl;cout

12、文法的FIRSTVT(T):endl;for(i=0;i4;i+)for(int j=0;j8;j+)if(SignArrayij=true & upperi=T)coutlowerj ;if(upperi=T) /如果找到了，就退出本次循環(huán)break;coutendl;cout文法的FIRSTVT(F):endl;for(i=0;i4;i+)for(int j=0;j8;j+)if(SignArrayij=true & upperi=F)coutlowerj ;if(upperi=F)break;coutendl;cout文法的FIRSTVT(P):endl;for(i=0;i4;i+)fo

13、r(int j=0;j8;j+)if(SignArrayij=true & upperi=P)coutlowerj ;if(upperi=P)break; coutendl;bool CreateFirstvt:IsT(char ch)for(int i=0;i8;i+)if(ch=loweri)return true;return false;bool CreateFirstvt:IsN(char ch)for(int i=0;i4;i+)if(ch=upperi)return true;return false;class CreateLastvt /構造LASTVT的類public: C

14、reateLastvt();CreateLastvt()void insert(char T,char n);bool SignArray2020;void CreateLASTVT(); /構造LASTVT的函數 void PrintLastvt();bool IsT(char); /判斷是否為終結符bool IsN(char); /判斷是否為非終結符private:string stack50;int top;CreateLastvt:CreateLastvt()top=0;for(int i=0;i20;i+)for(int j=0;j20;j+)SignArrayij=false;vo

15、id CreateLastvt:insert(char T,char n)for(int j=0;j4;j+)if(T=upperj)break;/查出非終結符的位置for(int k=0;k8;k+)if(n=lowerk)break;/查出終結符的位置if(SignArrayjk=false)/如果再SignArray中沒有，則將其入棧SignArrayjk=true;stacktop=(;stacktop.append(1,T);stacktop+=,;stacktop.append(1,n);stacktop+=);top+;/將(P,a)入棧void CreateLastvt:Cre

16、ateLASTVT()for(int i=0;i.a這種情況char pos1,pos2;pos1=Ei.at(0);pos2=Ei.at(Ei.length()-1);insert(pos1,pos2);if(IsT(Ei.at(Ei.length()-2)=true & IsN(Ei.at(Ei.length()-1)=true) /處理P-.aQ這種情況char pos1,pos2;pos1=Ei.at(0);pos2=Ei.at(Ei.length()-2);insert(pos1,pos2);while(top!=0) /處理P-.Q這種情況string PopElement=sta

17、ck-top;stacktop=;char pos1,pos2;for(i=0;i10;i+)if(PopElement.at(1)=Ei.at(Ei.length()-1)pos1=Ei.at(0);pos2=PopElement.at(3);insert(pos1,pos2);void CreateLastvt:PrintLastvt()cout*endl;cout打印文法的LASTVT:endlendl;cout文法的LASTVT(E):endl;for(int i=0;i4;i+)for(int j=0;j8;j+)if(SignArrayij=true & upperi=E)cout

18、lowerj ;if(upperi=E)break;coutendl;cout文法的LASTVT(T):endl;for(i=0;i4;i+)for(int j=0;j8;j+)if(SignArrayij=true & upperi=T)coutlowerj ;if(upperi=T)break;coutendl;cout文法的LASTVT(F):endl;for(i=0;i4;i+)for(int j=0;j8;j+)if(SignArrayij=true & upperi=F)coutlowerj ;if(upperi=F)break;coutendl;cout文法的LASTVT(P):

19、endl;for(i=0;i4;i+)for(int j=0;j8;j+)if(SignArrayij=true & upperi=P)coutlowerj ;if(upperi=P)break; coutendl;bool CreateLastvt:IsT(char ch)for(int i=0;i8;i+)if(ch=loweri)return true;return false;bool CreateLastvt:IsN(char ch)for(int i=0;i4;i+)if(ch=upperi)return true;return false;class CreatePreTable

20、public:CreatePreTable();CreatePreTable()void CreatePreCedentTable();void PrintPreTable();bool IsT(char);bool IsN(char);int GetLocation(char);private:char PreTable88;/算符優(yōu)先關系表;CreatePreTable:CreatePreTable()/初始化for(int i=0;i8;i+)for(int j=0;j8;j+)PreTableij= ;bool CreatePreTable:IsT(char ch)for(int i=

21、0;i8;i+)if(ch=loweri)return true;bool CreatePreTable:IsN(char ch)for(int i=0;i4;i+)if(ch=upperi)return true;void CreatePreTable:CreatePreCedentTable()/CreateFirstvt firstvt;firstvt.CreateFIRSTVT();CreateLastvt lastvt;lastvt.CreateLASTVT();for(int i=0;i10;i+)for(int j=1;j(Ei.length()-3);j+)if(IsT(Ei.

22、at(j+2)=true)if(IsT(Ei.at(j+3)=true)PreTableGetLocation(Ei.at(j+2)GetLocation(Ei.at(j+3)=;/判定為等于關系if(IsN(Ei.at(j+3)=true & j=(Ei.length()-5) & IsT(Ei.at(j+4)=true)PreTableGetLocation(Ei.at(j+2)GetLocation(Ei.at(j+4)=;/判定為等于關系if(IsN(Ei.at(j+3)=true)int loc=GetLocation(Ei.at(j+2);for(int m=0;m4;m+)for

23、(int k=0;k8;k+)if(firstvt.SignArraymk=true & upperm=Ei.at(j+3)PreTablelock=;if(upperm=Ei.at(j+3)break;elseif(IsT(Ei.at(j+3)=true)int loc=GetLocation(Ei.at(j+3);for(int m=0;m4;m+)for(int k=0;k;if(upperm=Ei.at(j+2)break;void CreatePreTable:PrintPreTable()cout*endl;cout打印算符優(yōu)先文法的優(yōu)先表:endl;cout*endl;cout

24、+ - / * ( ) iendl;cout+ ;for(int j=0;j8;j+)coutPreTable0j ;coutendl;cout- ;for(j=0;j8;j+)coutPreTable1j ;coutendl;cout/ ;for(j=0;j8;j+)coutPreTable2j ;coutendl;cout* ;for(j=0;j8;j+)coutPreTable3j ;coutendl;cout ;for(j=0;j8;j+)coutPreTable4j ;coutendl;cout( ;for(j=0;j8;j+)coutPreTable5j ;coutendl;cou

25、t) ;for(j=0;j8;j+)coutPreTable6j ;coutendl;couti ;for(j=0;j8;j+)coutPreTable7j ;coutendl;cout*endl;cout*endl;int CreatePreTable:GetLocation(char ch)/獲得在VN的位置for(int i=0;i8;i+)if(loweri=ch)return i;class stackprivate:int size;char arraylength;public:stack()size=0;void push(char ch)if(sizelength)array

26、size=ch; size+;elsecoutoverflow!=0)for(int i=0;ilen;i+)chi=arraysize-len+i; size-=len; return len;elsecout參數錯誤!=0&possize)return arraypos; return 0;void peekall()for(int i=0;igetsize();i+)coutpeek(i);cout=0&ch=a&ch=a&ch=(&ch=0&ch=9)return 1; return 0;void main()CreateFirstvt firstvt;firstvt.CreateFI

27、RSTVT();firstvt.PrintFirstvt(); CreateLastvt lastvt;lastvt.CreateLASTVT();lastvt.PrintLastvt();CreatePreTable pretable;pretable.CreatePreCedentTable();pretable.PrintPreTable();char a1100;int b100;int atop=0,btop=0;string str;/char strmaxsize;stack s;/int len;cout請輸入一個句型,以#結束!str;/len=int(strlen(str)

28、; s.push(#);int k=s.getsize()-1,t=0,j;char a=str0;while(a!=#)a=strt;if(isvt(s.peek(k) j=k;elsej=k-1; while(isvt(a)&getrank(s.peek(j),a)=1) int h=j,low=j-1;if(!isvt(s.peek(low)low-;while(getrank(s.peek(low),s.peek(h)!=-1)h=low;low-;if(!isvt(s.peek(low)low-;h=s.getsize()-1;low+;int len=h-low+1;char ch

29、10;for(int p=0;p10;p+)chp=0;s.pop(ch,len);char c=guiyue(ch);s.push(c);coutch 規(guī)約為 guiyue(ch)=A&a=Z)&getrank(s.peek(j),a)=2)cout你的輸入有錯誤!endl;cout錯誤為第 t+1個字符 :strtendl;exit(0);elsecout讀入 :aendl;s.push(a);s.peekall();t+;k=s.getsize()-1;char temp10; s.pop(temp,3);if(s.getsize()=0)coutsuccessed!endl; else coutfail!k;/求四元式/for(int i=0;i1)if(stri=(&stri+1=-)cout(ss) ( uminus, ;zh(stri+2);cout, _, Tn-300