1、word 編譯原理 實驗報告本文檔集合了編譯原理大作業的實驗報告加代碼實驗主要內容為用C+實現了詞法分析程序；語法語義以及四元式生成程序代碼見附錄，復制進VS后程序絕對可編譯執行。文檔代碼為原創，謹慎使用姚礪的大作業實 驗 設 計 一一、實驗名稱 詞 法 分 析 程 序二、實驗目的1設計一個詞法分析程序，每調用一次就從源程序文件中順序識別出一個單詞符號，并返回該單詞符號的內部編碼、單詞符號自身、行列位置信息。2要能處理單行注釋。 三、實驗內容及要求單詞種類與識別規那么(1) 標識符：首字符為字母或下劃線，其后由字母、數字或下劃線組成、長度不超過255個字符；(2) 整數：由1到8個數字組成。(

2、3) 小數：數字串1 . 數字串2，其中：數字串1由1-8個數字符組成； 數字串2由0-8個數字符組成，即：數字串2可以為空。(4) 字符串：由一對“括起來的符號串，長度不超過255個字符；(5) 保存字：if、else、while、do、integer、float、string、input、output、and、or、function、end、def、as、begin(6) 數學運算符： 、*、/、= (7) 比擬運算符： <、<=、>、>=、<>、=(8) 邏輯運算符： and、or(9) 分隔符： 、(、)、；、， 四、實驗環境操作系統：Win7/其他

3、編譯工具：VC+6.0/CFree /VS2012五、設計 1設計大體思路將讀取的文件采用一遍掃描的方法，即從左到右只掃描一次源程序，將讀取的數據存放在一個二維數組里。然后通過掃描函數scan，再從數組中一行一行的讀取數據，每調用其依次返回一個單詞的類型，同時單詞本身以及行列號存放在全局變量中。而說詞法分析作為語法分析的一個子程序，故在編寫詞法分析程序時，將會反復調用scan函數來獲取一個個單詞信息。3設計流程圖4函數設計/*詞法分析函數*/int scan( string s ,int line ) 框架：初始化工作是空格直接跳過，知直到讀取到一個字符if( 是字母 )查表判斷是否為關鍵字判

4、斷是否為邏輯運算符and或orElse那么為標識符else if( 是否為數字 ) 判斷是整數Else是小數Else其余情況判斷是否為運算符，字符串等else if( getchar=/ )if( contentlinei+1='/')/向前看一個,確定是否為行注釋；如果是，那么游標指向行末，跳過行注釋if( contentlinei+1='/*')如果向前看一個發現時塊注釋那么一直向前掃描直到出現“*/停止，略過塊注釋如果都不是那么Else判斷為除號，返回運算符類型2對其中局部實現的說明(1)數字識別while( contentlinei>='0

5、' && contentlinei<='9' )/判斷是否為數字text += contentlinei;i+;flag=1;if( flag=1 )if( contentlinei='.' )text += contentlinei;i+;while( contentlinei>='0' && contentlinei<='9' )/判斷是否為數字text += contentlinei;i+;return 2; /整數return 3;/小數每讀入一個字符，判斷是否數字

6、，然后找小數點，找到即為小數 (2) 標識符處理 while( (contentlinei>=65 && contentlinei<=90) | (contentlinei>=91 && contentlinei<=122) | contentlinei>='0' && contentlinei<='9' ) /判斷是否為數字或者字母或者下劃線text += contentlinei;i+;for( j=0; j<=13 ; j+ )if( text=keyj )/查表判斷

7、是否為保存字return 5;檢查到讀取的字符為字母時，進行查表判斷，找到即說明為關鍵字(3) 空格，注釋，行號的處理if( mode=0 )if( i<contentk.length() ) i+;/如果為行注釋 直接跳到下一行elseif( mode=-1 )/如果為塊注釋 找回行號k=templine; 六、程序源代碼見源代碼文件。七、實驗數據、結果測試數據見文件八、總結之前的每周作業曾經寫過一個詞法分析程序，所以這次寫詞法分析程序沒什么太多困難。在讀取源文件時，最初的想法是一行一行的讀取，讀一次就存一行，這樣可以節省空間資源，提高效率。但是仔細一想考慮到塊注釋分布在不同的行中，而

8、且這樣對行列的操作十分麻煩，而且許多地方涉及到要向前看，比方判斷注釋與/除號運算符時,最后只好一次全部讀完，存在一個二維數組中。再用scan函數來處理。這樣一來行列的處理就自由多了。第二點，在寫scan函數的時候，最初的想法是每調用一次，返回一個單詞，然后在語法分析時不斷調用它。但是僅僅返回單詞是不夠的，于是打算返回一個結構體，把單詞信息行列號什么的全部存進去，這個在后來的語法語義分析中可以看到，這里任然采用的是返回一個單詞類型。單詞本身，和行列號作為全局變量保存。然后只要按照流程圖一步一步判斷，慢慢寫就行了，沒有太多難度，唯一要注意的是單詞位置行列的計算一定要細心。這個是要穿插在整個詞法分析

9、的全部地方的。所有涉及到讀入一個字符的地方都需要考慮到如何修改行列變量。尤其是本程序拓展了塊注釋，要注意行列變化。實 驗 設 計 二注：由于語義分析和四元式生成都是在語法分析的根底上拓展得到的，這一章實驗報告囊括了語法，語義和四元式。一、實驗名稱 語 法 語 義 以 及 四 元 式 分 析 程 序二、實驗目的設計一個語 法 語 義 以 及 生 成 四 元 式 的 分 析 程 序 三、實驗內容及要求設計要求：構造相應文法的語法分析程序，應能指出源程序中出現的錯誤。為語法分析程序中添加類型檢查功能，包括： 變量重復定義； 變量未定義就使用； 變量未賦值就引用；將語法正確的源程序翻譯成四元式。文法見

10、附錄四、實驗環境操作系統：Win7/其他編譯工具：VC+6.0/CFree /VS2012五、設計 1.語法分析設計（1） 相關數據機構 struct Tokenstring value;/值int mode;/類型int row;/行int col;/列token;說明：這本應是詞法分析時的結構，但是scan函數返回的是但單一值，于是又設計了Token函數，對scan函數進行擴充，每個單詞的信息均保存一次在結構體中，方便錯誤報告函數進行處理。2各個非終結符函數形式/*/*語法語義 各產生式 函數*/void chengxu();void hanshukuai();void hanshu();

11、void yujukuai();void yuju();void bianliangdingyiyuju();void shujuleixing();void shuruyuju();void shuchuyuju();void fuzhiyuju();void fenzhiyuju();void xunhuanyuju();void biaodashi();void xiang();void yinzi();void buerbiaodashi();void guanxibiaodashi();void guanxi();其他函數：void error();void warning();每個

12、函數具體作用在代碼中都有注釋說明3語法分析整體設計思路采用遞歸下降的方法，為每個非終結符設計一個函數，在函數中對此處可能出現的語法錯誤進行處理。處理也語法錯誤的思路主要分兩種：1. 查找關鍵字由于進行語法分析時檢查到錯誤不可能就此停下，要一次性盡量找到所有的錯誤，而且測試數據的語法錯誤形式千奇百怪，這就要求發現錯誤之后如何找到繼續進行分析的位置。這里對于一些不常見的錯誤采取查找關鍵字的方法，一旦出現錯誤在相應函數中查找下一個出現的關鍵字的位置，然后繼續分析。2. 跳過錯誤單詞，直接分析下一個單詞由于查找關鍵字方法會跳過許多代碼，從而有可能造成一些信息不必要的遺漏。尤其是對于漏分號這種錯誤，與是

13、這里采取，直接當前錯誤，默認后續單詞可能就是正確單詞，繼續分析。但是這個方法在一些地方并不適用，可能會導致一連串的錯誤出現，于是在使用時要考慮好取舍。編譯錯誤處理函數：void error( Token token,char *msg) /編譯錯誤處理函數cout << "編譯錯誤：" printf( "%s",msg); cout << endl << "錯誤位置：第" << token.row << "行，第" << token.col &

14、lt;< "列 -> " <<token.value;cout << endl;cout << endl;errornum+;每出現錯誤時，通過傳遞錯誤信息參數以及單詞信息，調用編譯錯誤處理函數進行實時報錯。3測試數據和結果見后文語義分析局部(4) 語法分析局部的小總結原本打算試試自底向上歸約方法設計的，結果想了想發現實在麻煩，老師給的文法又挺龐雜的，創立分析表什么的就要好久。后來一想用遞歸下降方法好處很多，做到之后的語義分析和四元式生成的時候在語法分析的根底上拓展很方便，整體框架非常清晰。在錯誤處理方面考慮的還是挺合理的，對

15、于一些常見錯誤都能有效指出。并且程序只有一個出口，任何代碼輸入都會從那一個出口結束，不會引起程序崩潰。2、語義分析設計語義分析主要實現3個功能 變量重復定義； 變量未定義就使用； 變量未賦值就引用；(1)相關數據結構struct Symtable /符號表結構string name;int type;bool value;S;struct compare: binary_function<Symtable, string,bool> /仿函數和綁定器bool operator()( Symtable s, string str) constif (= str)retur

16、n true;elsereturn false;(2)相關函數void push_in_token( Token token ) /進表操作S.name = token.value;S.type = -1;S.value = false;ST.push_back( S );vector<Symtable> : iterator find_token( Token token ) /查表操作it = find_if( ST.begin(), ST.end(), bind2nd( compare(),token.value );return it;（2） 測試數據和結果4設計思路語義局

17、部主要采用符號表結構，符號表中記錄了每個非終結符的信息。名稱，類型，是否賦值。然后再程序中每次調用Token函數發現讀取到標識符時都進行查表操作。根據查表結果進行相關分析。在賦值函數中，如果查表找到其信息就說明重復定義。再其余函數中1.沒有找到說明為聲明就使用。 2.找到發現未賦值說明未賦值就引用。5語義局部小總結假設只實現以上3個功能語義局部并不難，關鍵是符號表的構建以及進表查表等操作。在這一局部我使用了仿函數和綁定器進行查表。由于我把相應表結構都存在vector內，導致查找結構內成員信息的不便，但是自己寫一套查找操作代碼估計效率不高，索性使用仿函數進行查找，泛型操作一般效率較高而且代碼較少

18、也很清晰。假設時間更充足一點其實還可以把數據類型匹配這一局部拓展一下，畢竟也是查表比擬，但是時間有限只好先完成要求的3個任務。3、四元式分析設計1相關數據結構struct Quaternary/四元式結構int serial;string op;string v1;string v2;string result;Q;stack<string> operator_stack;/操作數堆棧stack<string> operand_stack;/操作符堆棧2相關函數Quaternary Quaternary_generater( int serial, string op,

19、 string v1, string v2, string result )/四元式生成函數Q.serial = serial;Q.op = op;Q.v1 = v1;Q.v2 = v2;Q.result = result;return Q;void Quaternary_maker()while( !operand_stack.empty() && !operator_stack.empty() )op = operator_stack.top();operator_stack.pop();v1 = operand_stack.top();operand_stack.pop(

20、);v2 = operand_stack.top();operand_stack.pop();res = resultr;r+;Q = Quaternary_generater( serial, op, v1, v2, res );serial+;QV.push_back( Q );/for( it2=QV.begin(); it2!=QV.end(); it2+ )/找回真出口if( (*it2).result="null" )stringstream ss; ss<<QV.back().serial;string s=ss.str(); (*it2).res

21、ult=s;break;/operand_stack.push( res );void Quaternary_output()while( !QV.empty() )cout << QV.front().serial << " ( " << QV.front().op << " , " << QV.front().v2 << " , " << QV.front().v1 << " , " << QV.fron

22、t().result << " ) " << endl;it2 = QV.begin();QV.erase( it2 );（3） 測試數據和結果4設計思路賦值運算局部整體結構流程如下：說明：首先建立操作符棧和運算符棧。每次掃描遇到操作符遍進棧，遇到運算符如果當前棧空那么進棧，否那么和棧頂操作符的優先級進行比擬，如果小于等于其優先級，那么pop棧頂符號，進行四元式生成，再將四元式壓入四元式隊列，然后繼續與棧頂元素比擬直至其優先級大于其優先級或?？漳敲催M棧。If語句局部在對布爾表達式進行判斷時，先讓操作符和運算符進棧，轉移序號先賦為null等到掃描到if

23、 then之后的局部通過對其四元式生成確定了序號，這時候再查找隊列進行回填序號。函數具體結構：void biaodashi()xiang();while( token.value="+" | token.value="-" )/四元式while( !operator_stack.empty() && operator_stack.top()!="=" )/此處要注意用while循環，if會出錯，因為需要不斷判斷直至棧頂的符號優先級小于需要壓棧的符號此處生成四元式，四元式進隊列for( it2=QV.begin(); i

24、t2!=QV.end(); it2+ )/找回真出口if( (*it2).result="null" )stringstream ss; ss<<QV.back().serial;string s=ss.str(); (*it2).result=s;break;operator_stack.push( token.value );/如果?？栈蛘邷蕚溥M棧的符號的優先級大于棧頂的優先級那么進棧token = getToken();xiang();5四元式的總結：這局部是我覺得此次試驗最難的一局部。而且也是我花費時間最多的一局部。在寫賦值運算的那局部時，把一個whil

25、e循環寫成了if我一開始以為運算符進棧只需判斷一次導致測試數據結果出錯找了好久錯誤才找到。If語句那局部的四元式的編寫也十分困難，尤其是找回真假出口讓我考慮了很久。而且測試數據整個代碼有許多這種語句，應當在每個語句結束時就輸出一次四元式，不然會導致次序的混亂。一開始我沒發現，是把所有四元式進隊列到最后程序結束時一起輸出的，最后調試了許久，才發現問題，于是在語句結果判斷分號時，就調用四元式輸出函數進行輸出。六、整體總結 這次編譯原理大作業讓真的我受益良多，整個近千行代碼根本都是我一點一點慢慢敲出來的，過程固然辛苦但是學到了不少。尤其是在做語法分析和四元式生成的局部，代碼量較大，一開始思路也不太清

26、晰，但是還是一點一點硬著頭皮往下寫，結果在寫的過程中一些思路就出來了，看來有時候還是要多動手，光苦思冥想并不行。對于這次作業我自己是比擬滿意的但是還是有一些缺乏：語法局部本來想對文法進行拓展把布爾表達式那局部的附加題解決掉，無奈時間有限，實在來不及寫，可能留到暑假自己再完善吧。四元式局部其實做得并不完完善，有些測試數據會出現錯誤結果，主要是還是因為布爾表達式那局部文法沒有拓展，在進行復雜布爾表達式判斷時會出錯，而且if語句真假口如果遇到復雜的算數運算可能會出口回填錯誤?？傮w來說，這次作業根本任務還是都完成了，通過這次大作業也對整個編譯器的設計有了比以前更深的了解和體會，看來還是實踐才能出真知。

27、附錄文法如下：1. <程序>> <函數塊> 2. <函數塊>> <函數> <函數>3. <函數>> function id ( ) <語句塊> end function 4. <語句塊>> begin 語句 語句 end 5. <語句>><分支語句>|<賦值語句>|<循環語句>| <輸入語句>|<輸出語句>|<變量定義語句>6. <變量定義語句>> def id , i

28、d as <數據類型> ；7. <數據類型>> integer | float | string8. <輸入語句>> input id , id ；9. <輸出語句>> output <表達式> , <表達式> ；10. <賦值語句>> id = <表達式> ；11. <分支語句>> if <布爾表達式> <語句塊> else <語句塊> 12. <循環語句>> while <布爾表達式> d

29、o <語句塊>13. <表達式>> <項> +| <項> 14. <項>> <因子> *|/ <因子> 15. <因子>> id | con | deci | ( <表達式> )14. <布爾表達式>> <關系表達式> and | or <布爾表達式> 15. <關系表達式>> <表達式> <關系> <表達式>16. <關系>> < | <= |

30、 > | >= | = | <>附錄： 詞法分析完整代碼復制可執行/*詞法分析程序BY 謝卓函ON June 20th */#include <iostream>#include <algorithm>#include <cstring>#include <fstream>#include <string>#define MAXLINE 30using namespace std;/標識符1，整數2，小數3，字符串4，保存字5，數學運算符6，比擬運算符7，邏輯運算符8，分隔符9string key14=&quo

31、t;if","else","while","do","float","string","begin","end","def","integer","input","output","as","function" /保存字string border5= "" , "" , "&qu

32、ot; , "(" , ")" ; /分隔符 5string arithmetic9="+" , "-" , "*" , "/" ,"<" , "<=" , "=" , ">" , ">=" ; /運算符 6string text; /記錄標識符 1string contentMAXLINE; /保存從文件讀取的內容int i=0;/i為字符游標int

33、templine = 0;int scan( string s ,int line )int j, flag =0;text = "" /賦空textwhile( contentlinei=' ' )/判斷空格i+;/是空格跳過if( (contentlinei>=65 && contentlinei<=90) | (contentlinei>=91 && contentlinei<=122) ) /判斷是否為字母或者下劃線text += contentlinei;i+;while( (contentl

34、inei>=65 && contentlinei<=90) | (contentlinei>=91 && contentlinei<=122) | contentlinei>='0' && contentlinei<='9' ) /判斷是否為數字或者字母或者下劃線text += contentlinei;i+;for( j=0; j<=13 ; j+ )if( text=keyj )/查表判斷是否為保存字return 5;if( text="and" |

35、 text="or" )/判斷是否為邏輯運算符return 8;if( j=14 )return 1;/假設查表失敗說明為標識符elsewhile( contentlinei>='0' && contentlinei<='9' )/判斷是否為數字text += contentlinei;i+;flag=1;if( flag=1 )if( contentlinei='.' )text += contentlinei;i+;while( contentlinei>='0' &

36、;& contentlinei<='9' )/判斷是否為數字text += contentlinei;i+;return 2; /整數return 3;/小數if( contentlinei= '' | contentlinei='' | contentlinei='' | contentlinei='(' | contentlinei=')' | contentlinei=',' )/判斷是否為分隔符 text = contentlinei;i+; return 9;

37、if( contentlinei= '+' | contentlinei='-' | contentlinei='*' | contentlinei='=' )/判斷是否為運算符 text = contentlinei; i+;return 6;if( contentlinei='<' | contentlinei='>' )if( contentlinei+1='=' )text = contentlinei;text += contentlinei+1;i=i+2;r

38、eturn 7;else text = contentlinei;i+; return 7;if( contentlinei='“' ) /判斷是否為字符串text += contentlinei;i+;while( contentlinei!='' )text += contentlinei;i+;text += contentlinei;i+;return 4;if( contentlinei='/' )/判斷是否為注釋if( contentlinei+1='/')i=contentline.length();return 0

39、;/如果為行注釋那么游標指向行末elseif( contentlinei+1='*' )i=i+2;while( contentlinei!='*' | contentlinei+1!='/' )if( i=contentline.length() )line+;i=0;elsei+;i=i+2;templine = line;return -1; /-1代表塊注釋else text = contentlinei;i+; return 0;return 0;int main()ifstream infile("ceshi1.txt&qu

40、ot;,ios:in);if( infile )cout << "文件讀取成功! "<< endl;elsecout << "文件讀取失敗!" << endl;int hang, mode,k=1,numline; /k用于定位行數cout << endl;cout << "測試數據如下：" << endl;while ( getline(ink) )cout << contentk << endl;k+;numline = k

41、-; /numline記錄了文件總行數cout << endl;cout << "詞法分析結果：" << endl;for( k=1; k<=numline; k+ )while( i!=contentk.length() )mode = scan( contentk, k );if( mode!=0 && mode!= -1 )cout << " 所在行數：" << k << " 所在列數：" << i-text.length(

42、)+1 << " 單詞類別："<< mode << " 單詞為：" << text <<endl ;elseif( mode=0 )if( i<contentk.length() ) i+;/如果為行注釋 直接跳到下一行elseif( mode=-1 )/如果為塊注釋 找回行號k=templine;i = 0;/一行結束定位到下一行行頭getchar(); return 0;附錄二 語法語義四元式生成代碼復制可執行/*語法+語義+四元式分析程序BY 謝卓函ON June 25th */#i

43、nclude <iostream>#include <algorithm>#include <cstring>#include <fstream>#include <string>#include <cstdio>#include <vector>#include <iterator>#include <algorithm>#include <functional>#include <stack>#include <queue>#include <

44、;cstdlib>#include <sstream>#define MAXLINE 30using namespace std;/標識符1，整數2，小數3，字符串4，保存字5，數學運算符6，比擬運算符7，邏輯運算符8，分隔符9string key14="if","else","while","do","float","string","begin","end","def","intege

45、r","input","output","as","function" /保存字string border5= "" , "" , "" , "(" , ")" ; /分隔符 5string arithmetic9="+" , "-" , "*" , "/" ,"<" , "<=&quo

46、t; , "=" , ">" , ">=" ; /運算符 6string text; /記錄標識符 1string contentMAXLINE; /保存從文件讀取的內容string resultMAXLINE = "t1","t2","t3","t4","t5","t6","t7","t8","t9","t10"/*/*語法

47、語義 各產生式 函數*/void chengxu();void hanshukuai();void hanshu();void yujukuai();void yuju();void bianliangdingyiyuju();void shujuleixing();void shuruyuju();void shuchuyuju();void fuzhiyuju();void fenzhiyuju();void xunhuanyuju();void biaodashi();void xiang();void yinzi();void buerbiaodashi();void guanxibi

48、aodashi();void guanxi();void error();void Quaternary_output();void Quaternary_maker();int i=0,k=1,numline,mode;/i為字符游標,k為行號,numline記錄了文件總行數int templine = 0;int errornum = 0;int warningnum = 0;int r = 0, serial = 1;string op,v1,v2,res;struct Tokenstring value;/值int mode;/類型int row;/行int col;/列token;s

49、truct Symtable /符號表結構string name;int type;bool value;S;struct Quaternary/四元式結構int serial;string op;string v1;string v2;string result;Q;Quaternary Quaternary_generater( int serial, string op, string v1, string v2, string result );/函數聲明vector<Symtable> ST;vector<Symtable> : iterator it;vec

50、tor<Quaternary> QV;vector<Quaternary> : iterator it2;stack<string> operator_stack;/操作數堆棧stack<string> operand_stack;/操作符堆棧struct compare: binary_function<Symtable, string,bool> /仿函數和綁定器bool operator()( Symtable s, string str) constif (= str)return true;elsereturn

51、false;void push_in_token( Token token ) /進表操作S.name = token.value;S.type = -1;S.value = false;ST.push_back( S );vector<Symtable> : iterator find_token( Token token ) /查表操作it = find_if( ST.begin(), ST.end(), bind2nd( compare(),token.value );return it;int scan( string s ,int line )int j, flag =0

52、;text = "" /賦空textwhile( contentlinei=' ' )/判斷空格i+;/是空格跳過if( (contentlinei>=65 && contentlinei<=90) | (contentlinei>=91 && contentlinei<=122) ) /判斷是否為字母或者下劃線text += contentlinei;i+;while( (contentlinei>=65 && contentlinei<=90) | (contentlin

53、ei>=91 && contentlinei<=122) | contentlinei>='0' && contentlinei<='9' ) /判斷是否為數字或者字母或者下劃線text += contentlinei;i+;for( j=0; j<=13 ; j+ )if( text=keyj )/查表判斷是否為保存字return 5;if( text="and" | text="or" )/判斷是否為邏輯運算符return 8;if( j=14 )retur

54、n 1;/假設查表失敗說明為標識符elsewhile( contentlinei>='0' && contentlinei<='9' )/判斷是否為數字text += contentlinei;i+;flag=1;if( flag=1 )if( contentlinei='.' )text += contentlinei;i+;while( contentlinei>='0' && contentlinei<='9' )/判斷是否為數字text += contentlinei;i+;return 2; /整數return 3;/小數if( contentlinei= '' | contentlinei='' | contentlinei='' | contentlinei='(