1、河南師范大學軟件學院實驗報告 編譯(biny)原理 實驗報告2014年 12月 25 日 學號1228524012姓名王宇菲時間2014.12.25專業Java班級2012實驗題目：詞法語法語義分析器實驗目的：實現詞法分析，語法分析，語義分析等功能的分析其詞法分析：消除白空格消除注釋詞法分析語法分析：遞歸下降手工編碼first集合的計算follow集合的自動計算selection表自動生成遞歸下降自動生成LL（1）分析手工編碼LL（1）自動生成LR（1）分析手工編碼左遞歸消除語義分析以及中間代碼生成：中綴式轉后綴式遞歸下降編碼中綴式轉后綴式LL(1)編碼中綴式轉后綴式LR1)編碼表達式求值LL

2、(1)表達式求值LR(1)四元式實驗內容與步驟：開發過程詞法分析消除白空格以及注釋這個模塊實現的功能主要是對代碼中多余的白空格以及注釋進行消除。在文本中輸入一段代碼，其中可以有多余的空格和注釋，經過這個程序運行后，將實現多余空格，注釋去除。設計思路：這個模塊一共有6個狀態，設為0,1,2,3,4,5，其中狀態轉換圖：詞法分析設計思路：把消除白空格、消除注釋、識別標識符id，識別整數di，識別運算符、識別界符、識別雙引號內的注釋分層次畫狀態機，使狀態機清晰易懂，方便其他同學學習；以0狀態為中轉，每一層次的狀態機遇到不是該層次的內容（識別了一個詞元，當前輸入不是該詞元的內容了），回到0狀態去判斷該

3、字符應轉向的狀態。使用了ungetc（）函數，輸入回退一個字符，回到0狀態中轉之前，如果該字符并沒有做處理，要ungetc，回退到輸入流，那么從0狀態會再讀出之前沒有處理的字符，再判斷轉換；詞元存儲，用結構體存儲數組存儲；不同類型的詞元對應不同的表，詞元結構體中存儲的是，該詞元的類型（也即表的類型）、在該表中的下標（可以通過該下標找到對應詞元的相關信息，便于后期擴展）、該詞元在測試代碼中的坐標（x，y）。不同類型的詞元表有程序動態維護。表的動態維護對與整個編譯程序很重要。 struct Dataint type;/表類型：id=0,num=1,運算符 2 界符 3int value; /在表中

4、的下標int pos_x,pos_y;/源代碼位置;.語法分析遞歸下降手工編碼這個模塊是給定狀態轉換表，action表，之后對輸入的表達式進行詞法分析，判斷表達式正誤。其中文法如下：E:=TEE:=+TE|T:=FTT:=*FT|F:=id|di|(E)所定義的函數為：void f_exp();void f_term();void f_factor();void f_term_remains();void f_exp_remains();first集合的計算這個模塊進行的是first集合的計算。定義的文法存儲數據結構為：struct define char left;string right;

5、 ; 設計思路：整體上采用不動點算法依次掃描每條文法右部，若遇到終止符，則將該終止符加入文法左部非終止符的first集中。如果遇到非終止符，則先判斷該終止符的first集合中是否包含（“”代表“可空”），如果不包含，則將該非終止符的first集加到文法左部的非終止符的first集中；如果包含，并且該非終止符不是最后一個非終止符，則將該非終止符的first集合去掉后，加到文法左部的first集合中；否則直接將此非終止符的first集合加到文法左部的first集合中。具體描述如下：對于任意給定的LL(1)文法G,為了構造它的預測分析表M,我們就必須構造與文法G有關的集合First和fellow.首

6、先我們對每一個XVTUVn,構造FIRST(X),辦法是,連續使用下面的規則,直至每個集合FIRST不再增大為止.(1)若XVT,則FIRST(X)=X.(2)若XVn,且有產生式X-a,則把a加入到FIRST(X)中,若X-,也是一條產生式,則把也加到FIRST(X)中.(3)若X-Y是一個產生式且YVn,則把FIRST(Y)中所有非-元素都加到FIRST(X)中,若X-Y1Y2YK,是一個連續的產生式,Y1Y2Yi-1都是非終結符,而且,對于任何j,1ji-1,FIRST(Yj)都含有(即Y1Y2Yi-1=),則把FIRST(Yi)中的所有非-元素都加到FIRST(X)中,特別是,若所有的

7、FIRST(Yj)均含有,j=1,2,k,則把加到FIRST(X)中.輔助函數：/*統計文法條數，非終止符個數，終止符個數，并把非終止符，終止符弄成一個字符串，用于查找下標*/void get_gene() /獲得產生式，并統計int get_index(char b); /得到終止符或非終止符的統一下標void add(string &tLeft , string s);將s添加到tLeft中，即將右邊的字符串添加到左邊的字符串中，去掉重復，如果右邊存在新的字符，要將flag置為 1 ，用于不動點算法。 左遞歸消除設計思路：將間接左遞歸變成左遞歸，然后消除直接左遞歸。把文法的所有非終止符按某

8、一順序排序，如：A1，A2，.An；從A1開始消除都為A1的產生式的直接左遞歸，然后把左部為A1的所有規則的右部逐個替換為A2開始的產生式中的A1，并消除左部位A2的產生式中的直接左遞歸，繼而以同樣的方式吧A2的右部代入左部為A3右部以A1或A2開始的產生式中，消除左部為A3的產生式之直接左遞歸，直到把左部為A1，A2，.An-1的右部代入左部為An的產生式中，從An中消除直接左遞歸。把上述算法歸結為：如非終止符的排序為：A1，A2，.AnFOR i:=1 TO N DOBEGINFOR j:=1 TO i-1 DOBEGIN如Aj的所有產生式為：Aj-a1|a2|.|ak替換形成Ai-Ajr

9、的產生式變為：Ai-a1r|a2r|.|akrEND消除Ai中的一切直接左遞歸.END.去掉無用產生式。selection表自動生成設計思路：掃描文法，計算文法右部的first集合（“”不計算在內），直接將文法去右部填入文法右部計算得到的相應first集合和文法左部對應的selection表項中。此代碼比較簡單，附如下：void count_selection(define *p,string *first,string *follow,string *selection,int count,int count_T)for(int i = 0;icount;i+)string first_ri

10、ght = first_str(pi.right);string rights = pi.right;char lefts= pi.left;for(int j = 0; j (first_right.length(); j+)selectionget_index(lefts)get_index(first_rightj) = rights;if( firstget_index(lefts).find()!=-1 ) /如果屬于firstpi.leftstring follows = followget_index(lefts);for(j = 0; j產生式，而的長度為r（即| |=r），則

11、從狀態棧和文法符號棧中自棧頂向下去掉r個符號，即棧指針SP減去r。并把A移入文法符號棧內，再把滿足Sj=GOTOSi,A的狀態移進狀態棧，其中Si為修改指針后的棧頂狀態（3）接受acc：當歸約到文法符號棧中只剩文法的開始符號S時，并且輸入符號串已結束即當前輸入符是#，則為分析成功（4）報錯：當遇到狀態棧頂為某一狀態下出現不該遇到的文法符號時，則報錯，說明輸入串不是該文法能接受的句子。本模塊功能主要對表達式進行LR(1)分析后，并對表達式進行求值。產生式存儲結構定義為：struct define /產生式char left; string right;；其他定義：stacks_sign; /符號

12、棧stacks_state; /狀態棧char Get_ch100; /用于存儲測試字符串define *p = new define10;int count=0;/用于記錄測試字符串的長度int counts ; /產生式個數int tCount ;/終止符個數int ntCount ;/非終止符個數string s_NT=,s_T=;int get_index(char b);void get_gene();void get_ch();void init(); /初始化int parseInt(string); /將字符串轉換為int四元式本模塊基于LR手工編碼，主要是將表達式表示成四元式

13、，如運算符，運算對象1，運算對象2，結果）。四元式存儲結構定義為：struct four_element /四元式結構體char op; /操作符string x1,x2; /兩個操作數string re; /結果;主要函數為：string test(string Action126,int Goto123,string input)；測試過程消除白空格以及注釋運行結果截圖：原文件：輸出文件：詞法分析運行結果截圖：遞歸自動生成運行結果截圖：LR(1)手工編碼運行結果截圖：消除左遞歸運行結果截圖：四元式運行結果截圖：總結這次的課程設計項目，我擔任的是原型設計，并參與了部分編碼工作。在設計的時候遇

14、到很多困難，并且由于編譯原理本身的復雜性，系統性，讓我在設計的時候對整體的把握和取舍上需要有一定的決策能力和判斷能力。例如詞法分析中真正要考慮完全，會發現很多問題，要處理的細節太多，這樣狀態也太多，轉換表以及action表比較難畫，也比較容易出錯，不利于初次原形設計和小組學習，于是我選擇一個這種的方式，只考慮了一些常規的詞元，并且狀態圖采用層次型，清晰，便于小組學習和深入，雖然這樣做代碼效率不高。另外一些算法性、知識性較強的算法設計，如first、follow集合計算、消除左遞歸的，需要對上課講訴的內容深入理解，并自己手工模擬才能深入理解，并設計原形。設計原形后設計與編碼人員的溝通問題；由于部

15、分編碼人員對算法思想不夠理解，需要耐心溝通，并且對一些大家都要用到的數據結構進行統一，對某些通用的函數可以整合到一個.cpp文件，這樣加強了小組代碼的規整性。經過這次課程設計，不僅讓我學習到了編譯器的編譯過程，詞法分析，語法分析，語義分析，中間代碼生成，代碼優化。而且培養了我們的團隊合作分工意識。使我們認識到了，進行項目開發，不是單靠個人力量可以成功完成的。按照每個人的專業擅長，給每個人分工，能力比較強的同學擔任項目的原型設計工作，編碼能力強的同學進行項目的編碼工作，編碼能力相對較弱的同學可以擔任測試工作，管理能力較強的同學擔任項目中組織以及管理的工作。只有整個團隊分工細致地合作，每個環節緊扣

16、相應的環節，這樣才能把項目做好，做強。這次的課程設計讓我們能把所學的知識運用到實際的項目編碼中來，真的讓我們成長起來了，這樣的教學方式是值得肯定和支持的。參考文獻編譯原理（第2版）張素琴清華大學出版社2012年5月代碼附錄消除白空格以及注釋：#include#includeusing namespace std;void f_save();void f_delete();void f_change();void f_add();char srcstr;ofstream out(test1.txt,ios:binary);int main()ifstream in(test.txt,ios:in

17、|ios:binary);char ch_in,ch_in_Type;int S_B = 0 , S_A = 0;int State_Trans_Table65 = 0,1,2,0,1,0,1,2,0,1,0,0,3,4,0,3,3,3,3,1,4,4,4,5,4,4,4,1,4,4;char Ch_Type_Table128 = 0;Ch_Type_Tabler=Ch_Type_Tablen=4; /r,nCh_Type_Table/=2; /Ch_Type_Table*=3; /*Ch_Type_Table =Ch_Type_Tablet=1; /空格，/t/返回類型(指針變量名)（參數列

18、表）；定義函數指針void(*Action_Table66)(void)= f_save,f_change,f_delete,NULL,NULL,NULL,f_save,f_delete,f_delete,NULL,NULL,NULL,f_add,NULL,NULL,f_delete,f_delete,NULL,NULL,f_change,NULL,f_delete,NULL,NULL,NULL,NULL,NULL,NULL,f_delete,f_delete,NULL,f_change,NULL,NULL,f_delete,NULL;while(in) /當文件讀取沒有結束S_B = S_A

19、;in.get(ch_in);srcstr = ch_in;ch_in_Type = Ch_Type_Tablech_in;S_A = State_Trans_TableS_Bch_in_Type;Action_TableS_BS_A();out.close();in.close();return 0;void f_save() / f_留outsrcstr;void f_delete() /f_刪void f_change() / f_改out ;void f_add() /f_補out/;out ;遞歸下降自動編碼：/*采用文法：E = TEE=+TE| /表示空T=FTT=*FT|F=i

20、d|di|(E)*/#includeusing namespace std;char c ;int flag = 1 ; /flag為1要getchar()void f_exp();void f_term();void f_factor();void f_term_remains();void f_exp_remains();int main()cout請輸入一個簡單的算數表達式：endl;f_exp();cout表達式正確！endl; /遞歸調用中遇到錯誤，就exit(0)，終止了程序，即如果有錯，不會輸出此句return 0;void f_exp()f_term();f_exp_remai

21、ns();void f_term() f_factor(); f_term_remains();void f_factor()if(flag = 1)c = getchar();if( (c = 0) | (c= a & c= z)return;else if( c = ()f_exp();if(c = ) return ;else cout括號匹配錯誤;exit(0);elsecout當前錯誤字符：cendl;exit(0);void f_exp_remains()if(flag = 1)c = getchar();if(c = $)flag = 1;return;if(c = +)flag

22、 = 1;f_term();f_exp_remains();else if(c = )flag = 0;return ;elsecout當前錯誤字符：cendl;exit(0);void f_term_remains() if(flag = 1)c = getchar();if(c = *)flag = 1;f_factor();f_term_remains();elseflag = 0; /這里如果不是*，T直接取空，遞退到上級函數處理，所以當前輸入字符沒有處理，flag = 0，調用的下一個函數不能輸入新的字符return;fisrt集計算:#include #include #inclu

23、de using namespace std;struct define /文法存儲形式 char left; string right; ;/*統計文法條數，非終止符個數，終止符個數，并把非終止符，終止符弄成一個字符串，用于查找下標*/void get_gene(); /獲得產生式，并統計int get_index(char b); /得到終止符，或非終止符統一下標void add(string &tLeft , string s);/將s添加到tLeft中，即將右邊的字符串添加到左邊的字符串中，去掉重復，如果右邊存在新的字符，要將flag置為 1 ，用于不動點算法。void first()

24、; /計算first集string s_NT=,s_T=; /用于存儲所有出現的非終止符，終止符（統一下標查找）struct define *p = new define10; /文法數組string *tFirst=new string 10;/存非終結符的first集int counts , tCount , ntCount;/文法條數，終結符符數，非終結符個數bool flag=1; /用于不動點算法int main()int i;get_gene(); /獲得產生式，并統計first();cout=first=endl;for(i=0;intCount;i+)couts_NTittFi

25、rstiendl;cout=endl;return 0;void first()int i,j;string rights,tmp;flag=1;while(flag)flag=0;/若無更新，下一循環將退出for(i=0;icounts;i+)rights=pi.right;for(j=0;jrights.length();j+)/對文法右部掃描if(!(rightsj=A)/終結符tmp.append(1,rightsj);/將字符轉為字符串add(tFirstget_index(pi.left),tmp);/若是終止符，則直接加入該first集tmp=;/恢復為空串break;elsei

26、f(int)(tFirstget_index(rightsj).find()=-1)/該終結符不含add(tFirstget_index(pi.left),tFirstget_index(rightsj);/將非終結符的rightsj集加到pi.left的first集中break;else if(int)(tFirstget_index(rightsj).find()!=-1&j pcounts.left b pcounts.right) /輸入文法，一次獲取一行counts+;in.close();coutcountsendl;for(i=0;icounts;i+)/從文件將所有文法讀出co

27、utpi.left b pi.rightendl; /*統計非終止符，終止符*/for(i=0;icounts;i+)if(int)s_NT.find(pi.left) = -1)/將不重復的非終結符加入臨時表中s_NT+=pi.left;if(s_NT.length()=1)/將follow集的第一個非終結符入#tFollow0=#;string rights = pi.right;for( int j=0;jrights.length();j+)if( !(rightsj=A) & (int)s_T.find(rightsj) = -1)s_T+=rightsj;s_T+=#;tCount

28、 = s_T.length();ntCount = s_NT.length();int get_index(char b) /得到下標if( b=A)return s_NT.find(b);elsereturn s_T.find(b);return -1;void add(string &tLeft,string s)/將s添加到tLeft中char c;for(int j=0;js.length();j+)/提取s里面的所有字符c=s.at(j);if(int)tLeft.find(c)=-1)/進行字符過濾處理，已存在first集里將不再添加tLeft.append(1,c);flag=1

29、;/有更新，將flag置1，繼續進行循環遞歸下降自動生成:#include #include #include #include #include #include using namespace std;/中綴轉后綴新添加char fuhao100; int fu=0; struct define /產生式char left; string right;void first(); /計算first，follow，selection，這幾個函數可以不寫，只在此給出定義void follow();void count_selection(define *p,string *first,strin

30、g *follow,string *selection,int count,int count_T);int get_index(char ch);/下劃線的表示和前面的函數一樣，在此就不重復了void get_gene();void add(string &t,string s);/將右邊的字符串添加到左邊void get_ch();void lookup(char ch,string *selection);void main()p = new definecounts; /定義文法數組first = new stringntCount;follow = new stringntCount

31、;get_gene();/代替原來的一串手動定義，表示由這兩個函數計算first();/計算first集follow();/計算follow集string *selection = new string*ntCount; /定義并初始化selection表for(int i=0;itCount;i+)selectioni = new stringtCount;for(i = 0;intCount;i+)for(int j = 0; jtCount;j+)selectionij = %;count_selection(p,first,follow,selection,counts,tCount)

32、; /遞歸自動生成/ get_ch(); lookup(s_NT0,selection);if(Get_chsearch=#)cout恭喜你-匹配成功！-endl;void lookup(char ch,string *selection)/語法分析int x;int y;char c;string str;/接收查詢selection表中的字符串x=get_index(ch);/得到當前橫坐標 if(searchcount) y=get_index(Get_chsearch);if(y=-1)/識別當前表達式字符是否出現錯誤，出現錯誤則報錯并返回cout表達式 字符為：Get_chsearc

33、h 錯誤!endl;exit(0);str=selectionxy;int len;/當前文法字符的長度 len=str.length();for(i=0;ilen;i+)c=stri;if(c=%)/當當前文法出現錯誤時，報錯并返回 coutnow文法 字符為：c 錯誤!endl;exit(0) ;/中綴轉后綴新添加else if(c=$) coutfuhao-fu= A & c= Z)/如果當前文法字符為非終止符時，則查找selectionlookup(stri,selection); else if(c=)/如果當前的文法字符為空值時,則不做任何操作return;else/當識別到終止符

34、時，則比較當前表達式的字符是否匹配if(c!=Get_chsearch)/識別不成功coutnow表達式 字符為： Get_chsearchnow文法 字符為：c 匹配不成功！endl; exit(0) ;else/識別成功，則數組繼續讀取下一個表達式字符 cout-【Get_chsearch】-匹配成功！endl;/中綴轉后綴新添加 if(Get_chsearch=+|Get_chsearch=*)fuhaofu+=Get_chsearch;else if(Get_chsearch!=(&Get_chsearch!=)coutGet_chsearch ; search+; return;vo

35、id get_ch()freopen(in.txt,r,stdin);char ch=0;int i=0;while(ch=getchar()!=EOF)Get_chi+=ch;count+;coutch;coutendl;四元式（基于LR1）：#include LR_1.hextern stacks_sign;/符號棧extern stacks_state;/狀態棧/extern char Get_ch100;/輸入串表格數組extern define *p;/文法指針數組extern four_element *fe;/文法指針數組extern string s_NT;extern int

36、 feCount,tpCount;int actionLen;/action的長度int parseInt(string);string test(string Action126,int Goto123,string input)int top_st;/狀態棧的棧頂變量int subScript=0;/輸入串的下標/char tmp;/臨時變量，用于對字符串到字符的轉換char ch=inputsubScript;/取輸入串數組中的當前字符stack result;/stack result;while(1)top_st=s_state.top();/取得狀態棧的棧頂元素int index

37、= get_index(ch);string action=Actiontop_stindex;actionLen=action.length();couttop_st=top_st ch=ch index=index action=actionendl;if(action0=S)string rString= action.substr(1,actionLen-1);int tmp_int = parseInt(rString);s_sign.push(ch); /壓入到符號棧的是當前字符，只是轉換查action的時候要找類型s_state.push(tmp_int);ch=input+su

38、bScript;/提取下一個輸入串的字符else if(action0=r)/需要進行規約string rString= action.substr(1,actionLen-1);int tmp_int = parseInt(rString);int k=ptmp_int.right.length();/取得該條文法的長度/coutptmp_int.right=ptmp_int.rightendl;for(int i=0;i=a & pop_sign=z )/cout-push pop_sign to resultendl;result.push(x+pop_sign);/cout- result.top()= result.top()*pop_signendl;else if(pop_sign = +|pop_sign = *)if(pop_sign = +)fefeCount.op = +;elsefefeCount.op = *;fefeCount.x