編譯原理ex3over

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

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

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

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

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

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;/標記數(shù)組，標記每一個是FIRSTVT、LastVTvoid CreateFIRSTVT(); /構(gòu)造FIRSTVT的函數(shù)void PrintFirstvt();bool IsT(char); /判斷是否為終結(jié)符bool IsN(char); /

7、判斷是否為非終結(jié)符程序結(jié)構(gòu)：重要代碼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 /構(gòu)造FIRSTVT的類public: CreateFirstvt();CreateFirstvt()void insert(char T,char

8、 n);bool SignArray2020;/標記數(shù)組，標記每一個是FIRSTVTvoid CreateFIRSTVT(); /構(gòu)造FIRSTVT的函數(shù) void PrintFirstvt();bool IsT(char); /判斷是否為終結(jié)符bool IsN(char); /判斷是否為非終結(jié)符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 /構(gòu)造LASTVT的類public: C

14、reateLastvt();CreateLastvt()void insert(char T,char n);bool SignArray2020;void CreateLASTVT(); /構(gòu)造LASTVT的函數(shù) void PrintLastvt();bool IsT(char); /判斷是否為終結(jié)符bool IsN(char); /判斷是否為非終結(jié)符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;/查出非終結(jié)符的位置for(int k=0;k8;k+)if(n=lowerk)break;/查出終結(jié)符的位置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)先關(guān)系表;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)=;/判定為等于關(guān)系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)=;/判定為等于關(guān)系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參數(shù)錯誤!=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請輸入一個句型,以#結(jié)束!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