1、編譯原理實驗合肥工業(yè)大學計算機科學與技術計算機科學與技術 13-3 班2013211678完成日期：2015.6.3實驗一詞法分析設計一、實驗功能：1、對輸入的 txt 文件內的內容進行詞法分析：2、由文件流輸入 test.txt 中的內容，對文件中的各類字符進行詞法分析3、打印出分析后的結果；二、程序結構描述：（源代碼見附錄）1、分別利用 k,s1,s2,s3構造關鍵字表，分界符表，算術運算符表和關系運算符表。2、 bool isletter() 用來判斷其是否為字母，是則返回 true，否則返回 false； bool isdigit() 用來判斷其是否為數(shù)字，是則返回 true，否則返回

2、 false； bool iscalcu() 用來判斷是否為算術運算符，是則返回 true，否則返回 false；bool reserve(string a) 用來判斷某字符是否在上述四個表中，是則返回 true，否則返回 false；void concat() 用來連接字符串；void getn() 用來字符；void getb() 用來對空格進行處理；void retract()某些必要的退格處理；ysis() 對一個單詞的單詞種別進行具體判斷；在主函數(shù)中用 switch 決定輸出。三、實驗結果四、實驗總結詞法分析器一眼看上去很復雜，但深入的去做就會發(fā)現(xiàn)并沒有一開始那么。對于一個字符的種別

3、和類型可以用 bool 函數(shù)來判斷，對于關鍵字和標示符的識別（尤其是3b）則費了一番功夫，最后對于常數(shù)的小數(shù)點問題處理更是麻煩。另外，這個實驗要設定好時候退格，否則將會導致字符漏讀甚至造成字符重復。我認為，這個實驗在程序實現(xiàn)上大體不算，但在細節(jié)的處理上則需要好好功夫去想，否則最后的程序很可能會出現(xiàn)看上去沒有問題，但實際上的狀況。將學過的知識應用到實際中并不簡單，只有自己不斷嘗試將知識轉化成程序才能避免眼高手低，對于知識的理解也必將更加深刻。實驗二 LL(1)分析法一、實驗原理：1、寫出 LL（1）分析法的：當一個文法滿足 LL(1)條件時，就可以為它構造一個不帶回溯的自上而下的分析程序，這個分

4、析程序是有一組遞歸過程組成的，每個過程對應文法的一個非終結符。實現(xiàn) LL(1)分析的一種有效的方法分析表是一個 MA,a形式的矩是使用一張分析表和一個站進行聯(lián)合控制。陣，著分析規(guī)則；棧STACK 用于存放文法符號。從棧頂取符號，按照分析表給出的規(guī)則進行有步驟的分析。2.實驗要求實現(xiàn)的文法：（1）E-TG（2）G-+TG|TG（3）G-（4）T-FS（5）S-*FS|/FS（6）S-（7）F-(E)（8）F-i二、程序結構：string M58用來定義分析表 ；char input50 用來存放輸入的句子；vectorysis用來存放分析棧；bool flag = true 用來判斷是否成功的標

5、志 ；reference(char a,char i) 查詢分析表，其中 a 為分析棧頂符號，i 為輸入串符號 ; pro(char a,char in) 用以做出具體的分析；三、實驗結果：運行程序，輸入需要分析的語句，結果如下：四、實驗總結：本次試驗用代碼實現(xiàn)了 LL（1）文法，在過程中對于非終結符向終結符轉換的過程中出現(xiàn)了一些問題，之后通過向同學請教得已解決。本代碼中的分析表寫在了主函數(shù)中，可以說本程序只對這一個文法有效，這也是這個程序的局限性。實驗三 LR(1)分析法一、實驗原理LR（1）分析法實驗設計及算法(1)總控程序，也可以稱為驅動程序。對所有的 LR 分析器總控程序都是相同的。

6、(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的 LR 分析器不同時，分析表將不同，分析表又可以分為動作表（ACTION）和狀態(tài)轉換（GOTO）表兩個部分，它們都可用二維數(shù)組表示。(3)分析棧，包括文法符號棧和相應的狀態(tài)棧，它們均是先進后出棧。分析器的動作就是由棧頂狀態(tài)和當前輸入符號所決定。二、程序結構action126 定義動作表；go123 定義轉換表；input50 存放輸入串；referaction(s,char i) 查詢 action 表，a 為分析棧頂?shù)臓顟B(tài)，i 為輸入串的符號；refergo(s,char i) 查詢 go 表 ；reduce(n) 就近規(guī)約 ；

7、ysis(st,char in)具體分析；其中:SP 為棧指針，Si為狀態(tài)棧，Xi為文法符號棧。狀態(tài)轉換表用 GOTOi，X=j 表示，規(guī)定當棧頂狀態(tài)為i，遇到當前文法符號為X 時應轉向狀態(tài)j，X 為終結符或非終結符。ACTIONi，a規(guī)定了棧頂狀態(tài)為 i 時遇到輸入符號a 應執(zhí)行。動作有四種可能：(1)移進：actioni，a= Sj：狀態(tài)j 移入到狀態(tài)棧，把a 移入到文法符號棧，其中i,j 表示狀態(tài)號。(2)歸約：actioni，a=rk：當在棧頂形成句柄時，則歸約為相應的非終結符 A，即文法中有A- B 的產生式，若 B 的長度為 R(即|B|=R)，則從狀態(tài)棧和文法符號棧中自頂向下去掉

8、R 個符號，即棧指針SP 減去 R，并把A 移入文法符號棧內， j=GOTOi,A移進狀態(tài)棧，其中i 為修改指針后的棧頂狀態(tài)。接受 acc:當歸約到文法符號棧中只剩文法的開始符號S 時，并且輸入符號串已結束即當前輸入符是#，則為分析成功。報錯:當遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入端不是該文法能接受的符號串。三、實驗結果：輸入需要規(guī)約的字符串，結果如下：四、實驗總結1、與算符優(yōu)先分析方法比較，用 LR 分析時，設計特定出錯處理子程序比較容易，因為不會發(fā)生不正確的歸分析表的每一個空項內，可以填入一個指示器，指向特定的出錯處理子程序，第一類錯誤的處理一般采用、刪除或修

9、改的辦法，但要注意，不能從棧內移去任何那種狀態(tài)，它代表已成功地分析了程序中的某一部分。2、LR 分析法的歸約過程是規(guī)范推導的逆過程，所以 LR 分析過程是一種規(guī)范歸約過程。LR分析法正是給出一種能根據(jù)當前分析棧中的符號串(通常以狀態(tài)表示)和向右順序查看輸入串的 K 個(K0)符號就可唯一地確定分析器的動作是移進還是歸約和用哪個產生式歸約，因而也就能唯一地確定句柄。其中 LR(0)分析器是在分析過程中不需向右查看輸入符號，因而它對文法的限制較大，然而，它是構造其它 LR 類分析器的基礎。因此，首先應學好 LR(0)項目集規(guī)范族構造的基本原理和方法。當 K=1 時，已能滿足當前絕大多數(shù)高級語言編譯

10、程序實現(xiàn)的需要。SLR(1)分析是為學習 LR(1)分析做準備，LR(1)項目集族的構造是 LALR(1)分析器的構造原理和基礎。LALR(1) 分析器是當前大多數(shù)高級程序設計語言編譯程序所采用的語法分析技術，也是編譯程序語法分析器自動構造工具 YACC 的實現(xiàn)基本原理。由此， LR(0)、SLR(1)、LALR(1)、LR(1)四種分析器的構造方法都必須深入理解和掌握。3、經過以上三個實驗的錘煉，不得不說自己編譯原理這門課的認識又提高了一個階層，對編譯原理的知識運用更加深入，編寫過程中遇到不少，結合及強大的網絡資源，在完成的過程中得到很多收獲，不僅來自于對知識點的了解更加深入，更是對自己編程

11、能力的一次很好的鍛煉，希望有這樣實驗的機會。4、本人很希望在完成實驗后，老師可以根據(jù)自己講的，將自己所寫的程序花一段時間來講解，這樣會對不會編寫的是一種教學，對會了的同學是一種榜樣效應，可以讓有個目標追求，這樣收獲了的也會更加準確與豐富。附錄：實驗一源代碼：#include #include #include using namespatd;string k = do,end,for,if,prf,scanf,then,while;/關鍵字string s1= ,;,(,),;/分界符string s2= +,-,*,/,+,-;/算術運算符string s3= ,=,!=;/關系運算符str

12、ing id100; string ci100;ifstream in;char ch;row =1,col = 0;/行數(shù)與列數(shù) idcount = 0,cicount = 0;string strtoken;bool isletter()/用來判斷其是否為字母 if(ch = A & ch = 0 & ch = 9)return true;elsereturn false;bool iscalcu()/用來判斷是否為算術運算符 if(ch=+|ch=-|ch=*|ch=/)return true;elsereturn false;void insertid()ididcount = str

13、token; idcount+;void insertci()cicicount = strtoken; cicount+;bool reserve(string a)/用來判斷某字符是否在表中count;if(a0 = do)count = 8;else if(a0 = ,)count = 6;else if(a0 = +)count = 6; else if(a0 = )count = 6;for(i = 0; i count; i+) if(ai = strtoken)return true;return false;void concat()/用來連接字符串 strtoken += c

14、h;void getn()/字符in.read(&ch, 1);if(ch = n)in.read(&ch,1); row+;col = 1;void getb()/空格處理 while(ch = )in.read(&ch,1);void retract()/某些必要的退格處理size=sizeof(ch);in.seekg(-size*2,ios:cur);ysis()/對一個單詞的單詞種別進行具體判斷 col+;getn();getb();if(in.eof()return 7; if(isletter()while(isletter()|isdigit() concat();getn()

15、;retract(); if(reserve(k)return 1;elseinsertid(); return 6;else if(isdigit()bool multipobool insertpo= false;= false;while(isdigit()|ch = .)if(ch = .)if(insertpo= false)concat();getn();insertpo= true;elseconcat();getn();multipo= true;if(isdigit()concat();getn();bool haveletter = false; while(islette

16、r()haveletter = true; concat();getn();retract(); if(haveletter)return 0; if(multipo)return 0;insertci(); return 5;else if(iscalcu() while(iscalcu()concat();getn();if(reserve(s2)return 3;elsereturn 0;concat(); if(reserve(s1)return 2;else if(reserve(s3) getn();if(ch = =)concat(); if(reserve(s3)return

17、4;elseretract(); return 4;return 0;main() in.open(file.txt); if(!in)cerr文件不存在endl;return 1;cout文件成功code;endl;cout*分析結果如下*endl; cout單詞tt二元序列t類型tt位置endlendl; while(!in.eof()strtoken = 0;code =ysis();switch(code) case0:coutstrtokenttErrorttErrortt(row,col)endl;brea k;case 1:if(strtoken.size() 4)coutstr

18、tokentt(code,strtoken)tt 關鍵字tt(row,col)endl;elsecoutstrtokentt(code,strtoken)t 關鍵字tt(row,col)endl;break;case 2:coutstrtokentt(code,strtoken)tt 分 界符 tt(row,col)endl;break;case 3:coutstrtokentt(code,strtoken)tt算術運算符t(row,col)endl;break;case 4:coutstrtokentt(code,strtoken)tt關系運算符t(row,col)endl;break;ca

19、se5:coutstrtokentt(code,strtoken)tt 常 數(shù)tt(row,col)endl;break;case 6:coutstrtokentt(code,strtoken)tt 標 識符 tt(row,col)endl;break;return 0;實驗二源代碼：#include #include #include #include #include using namespatd;string M58 ;/定義分析表char input50;/用來存放輸入的句子vectorysis;/用來存放分析棧bool flag = true;/用來判斷是否成功的標志 ，false

20、 為成功i = 0; /輸入串的指針string reference(char a,char i)/查詢分析表，其中 a 為分析棧頂符號，i 為輸入串符號x,y; switch(a)case E:x = 0; break;case T:x = 1; break;case F:x = 2; break;case G:x = 3; break;case S:x = 4; break;switch(i)case (:y = 0; break;case ):y = 1; break;case +:y = 2; break;case -:y = 3; break;case *:y = 4; break;

21、case /:y = 5; break;case i:y = 6; break;case #:y = 7; break;return Mxy;void pr(char i) couti;void prin()/用來打印輸入串 j = i;for(;inputj != 0;j+) coutinputj;void pro(char a,char in)/分析程序 if(a = in)if(a = #)flag = false;cout分析已全部完成endl; return;elsei+;ysis.pop_back();for_each(ysis.begin(), couttt;prin();ysi

22、s.end(),pr);coutttttGETNEXT(I)ysis.push_back(exprej);j-;for_each(ysis.begin(), cout3)ysis.end(),pr);coutttexprettPOP,PUSH(expre)endl; elsecoutttexprettPOPTG;M06 = E-TG;M10 = T-FS;M16 = T-FS;M20 = F-(E);M26 = F-i;M31 = G-;M32 = G-+TG;M33 = G-TG;M37 = G-;M41 = S-;M42 = S-;M43 = S-;M44 = S-*FS;M45 S-/F

23、S;M47 = S-;ysis.push_back(#); ysis.push_back(E);coutinput;cout分析棧tt剩余輸入串t所用產生式t動作endl;=for_each(ysis.begin(), couttt;prin();ysis.end(),pr);couttttt初始化endl;while(flag)pro(ysis.back(),inputi);return 0;實驗三源代碼：#include #include #include #include using namespatd;string action126 = S5,S4,S6,acc,r2,S7,r2,r

24、2,r4,r4,r4,r4,S5,S4,r6,r6,r6,r6,S5,S4,S5,S4,S6,S11,r1,S7,r1,r1,r3,r3,r3,r3,r5,S5,r5,r5,;/定義動作表string grammer6 = E-E+T,E-T,T-T*F,T-F,F-(E),F-i; /文法go123;/定義轉換表 char input50;/存放輸入串i = 0;bool flag = true;/判斷是否成功 vector symbol;/定義分析表 vector sus;/定義符號棧string referaction( y;switch(i)s,char i)/查詢 action 表，

25、a 為分析棧頂?shù)臓顟B(tài)，i 為輸入串的符號case i:y = 0; break;case +:y = 1; break;case *:y = 2; break;case (:y = 3; break;case ):y = 4; break;case #:y = 5;break;return actionsy;refergo(y;s,char i)/查詢 go 表switch(i)case E:y = 0; break;case T:y = 1; break;case F:y = 2; break;return gosy;void pr(n)coutn;void prchar(char c) coutc;void prin()/用來打印輸入串 j = i;for(;inputj != 0;j+) coutinputj;void reduce(n)/就近規(guī)約j = grammern.size() - 3;while(j-)sus.pop_back(); symbol.pop_back();symbol.push_back(grammern0);stu = refergo(sus.back(),symbol.back();