詞法分析程序+語法語義分析四元式生成+實驗報告.doc

編譯原理實驗報告本文檔集合了編譯原理大作業(yè)的實驗報告加代碼實驗主要內(nèi)容為用C+實現(xiàn)了詞法分析程序；語法語義以及四元式生成程序代碼見附錄，復(fù)制進VS后程序絕對可編譯執(zhí)行。文檔代碼為原創(chuàng)，謹慎使用（姚礪的大作業(yè)）實 驗 設(shè) 計 一一、實驗名稱 詞 法 分 析 程 序二、實驗?zāi)康模?）設(shè)計一個詞法分析程序，每調(diào)用一次就從源程序文件中順序識別出一個單詞符號，并返回該單詞符號的內(nèi)部編碼、單詞符號自身、行列位置信息。（2）要能處理單行注釋。 三、實驗內(nèi)容及要求單詞種類與識別規(guī)則(1) 標識符：首字符為字母或下劃線，其后由字母、數(shù)字或下劃線組成、長度不超過255個字符；(2) 整數(shù)：由1到8個數(shù)字組成。(3) 小數(shù)：數(shù)字串1 . 數(shù)字串2，其中：數(shù)字串1由1-8個數(shù)字符組成； 數(shù)字串2由0-8個數(shù)字符組成，即：數(shù)字串2可以為空。(4) 字符串：由一對“”括起來的符號串，長度不超過255個字符；(5) 保留字：if、else、while、do、integer、float、string、input、output、and、or、function、end、def、as、begin(6) 數(shù)學(xué)運算符： 、*、/、= (7) 比較運算符： 、=、=(8) 邏輯運算符： and、or(9) 分隔符： 、(、)、；、， 四、實驗環(huán)境操作系統(tǒng)：Win7/其他編譯工具：VC+6.0/CFree /VS2012五、設(shè)計 1設(shè)計大體思路將讀取的文件采用一遍掃描的方法，即從左到右只掃描一次源程序，將讀取的數(shù)據(jù)存放在一個二維數(shù)組里。然后通過掃描函數(shù)scan，再從數(shù)組中一行一行的讀取數(shù)據(jù)，每調(diào)用其依次返回一個單詞的類型，同時單詞本身以及行列號存放在全局變量中。而說詞法分析作為語法分析的一個子程序，故在編寫詞法分析程序時，將會反復(fù)調(diào)用scan函數(shù)來獲取一個個單詞信息。3設(shè)計流程圖4函數(shù)設(shè)計/*詞法分析函數(shù)*/int scan( string s ,int line ) 框架：初始化工作是空格直接跳過，知直到讀取到一個字符if( 是字母 )查表判斷是否為關(guān)鍵字判斷是否為邏輯運算符and或orElse則為標識符else if( 是否為數(shù)字 ) 判斷是整數(shù)Else是小數(shù)Else其余情況判斷是否為運算符，字符串等else if( getchar=/ )if( contentlinei+1=/)/向前看一個,確定是否為行注釋；如果是，則游標指向行末，跳過行注釋if( contentlinei+1=/*)如果向前看一個發(fā)現(xiàn)時塊注釋則一直向前掃描直到出現(xiàn)“*/”停止，略過塊注釋如果都不是則Else判斷為除號，返回運算符類型2對其中部分實現(xiàn)的說明(1)數(shù)字識別while( contentlinei=0 & contentlinei=0 & contentlinei=65 & contentlinei=91 & contentlinei=0 & contentlinei=9 ) /判斷是否為數(shù)字或者字母或者下劃線text += contentlinei;i+;for( j=0; j=13 ; j+ )if( text=keyj )/查表判斷是否為保留字return 5;檢查到讀取的字符為字母時，進行查表判斷，找到即說明為關(guān)鍵字(3) 空格，注釋，行號的處理if( mode=0 )if( icontentk.length() ) i+;/如果為行注釋 直接跳到下一行elseif( mode=-1 )/如果為塊注釋 找回行號k=templine; 六、程序源代碼見源代碼文件。七、實驗數(shù)據(jù)、結(jié)果測試數(shù)據(jù)見文件八、總結(jié)之前的每周作業(yè)曾經(jīng)寫過一個詞法分析程序，所以這次寫詞法分析程序沒什么太多困難。在讀取源文件時，最初的想法是一行一行的讀取，讀一次就存一行，這樣可以節(jié)省空間資源，提高效率。但是仔細一想考慮到塊注釋分布在不同的行中，而且這樣對行列的操作十分麻煩，而且許多地方涉及到要向前看，（比如判斷注釋與/除號運算符時）,最后只好一次全部讀完，存在一個二維數(shù)組中。再用scan函數(shù)來處理。這樣一來行列的處理就自由多了。第二點，在寫scan函數(shù)的時候，最初的想法是每調(diào)用一次，返回一個單詞，然后在語法分析時不斷調(diào)用它。但是僅僅返回單詞是不夠的，于是打算返回一個結(jié)構(gòu)體，把單詞信息行列號什么的全部存進去，這個在后來的語法語義分析中可以看到，這里任然采用的是返回一個單詞類型。單詞本身，和行列號作為全局變量保存。然后只要按照流程圖一步一步判斷，慢慢寫就行了，沒有太多難度，唯一要注意的是單詞位置行列的計算一定要細心。這個是要穿插在整個詞法分析的全部地方的。所有涉及到讀入一個字符的地方都需要考慮到如何修改行列變量。尤其是本程序拓展了塊注釋，要注意行列變化。實 驗 設(shè) 計 二注：由于語義分析和四元式生成都是在語法分析的基礎(chǔ)上拓展得到的，這一章實驗報告囊括了語法，語義和四元式。一、實驗名稱 語 法 語 義 以 及 四 元 式 分 析 程 序二、實驗?zāi)康脑O(shè)計一個語 法 語 義 以 及 生 成 四 元 式 的 分 析 程 序 三、實驗內(nèi)容及要求設(shè)計要求：構(gòu)造相應(yīng)文法的語法分析程序，應(yīng)能指出源程序中出現(xiàn)的錯誤。為語法分析程序中添加類型檢查功能，包括： 變量重復(fù)定義； 變量未定義就使用； 變量未賦值就引用；將語法正確的源程序翻譯成四元式。文法見附錄四、實驗環(huán)境操作系統(tǒng)：Win7/其他編譯工具：VC+6.0/CFree /VS2012五、設(shè)計 1.語法分析設(shè)計（1） 相關(guān)數(shù)據(jù)機構(gòu) struct Tokenstring value;/值int mode;/類型int row;/行int col;/列token;說明：這本應(yīng)是詞法分析時的結(jié)構(gòu)，但是scan函數(shù)返回的是但單一值，于是又設(shè)計了Token函數(shù)，對scan函數(shù)進行擴充，每個單詞的信息均保存一次在結(jié)構(gòu)體中，方便錯誤報告函數(shù)進行處理。（2）各個非終結(jié)符函數(shù)形式/*/*語法語義 各產(chǎn)生式 函數(shù)*/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 guanxibiaodashi();void guanxi();其他函數(shù)：void error();void warning();每個函數(shù)具體作用在代碼中都有注釋說明（3）語法分析整體設(shè)計思路采用遞歸下降的方法，為每個非終結(jié)符設(shè)計一個函數(shù)，在函數(shù)中對此處可能出現(xiàn)的語法錯誤進行處理。處理也語法錯誤的思路主要分兩種：1. 查找關(guān)鍵字由于進行語法分析時檢查到錯誤不可能就此停下，要一次性盡量找到所有的錯誤，而且測試數(shù)據(jù)的語法錯誤形式千奇百怪，這就要求發(fā)現(xiàn)錯誤之后如何找到繼續(xù)進行分析的位置。這里對于一些不常見的錯誤采取查找關(guān)鍵字的方法，一旦出現(xiàn)錯誤在相應(yīng)函數(shù)中查找下一個出現(xiàn)的關(guān)鍵字的位置，然后繼續(xù)分析。2. 跳過錯誤單詞，直接分析下一個單詞由于查找關(guān)鍵字方法會跳過許多代碼，從而有可能造成一些信息不必要的遺漏。尤其是對于漏分號這種錯誤，與是這里采取，直接當(dāng)前錯誤，默認后續(xù)單詞可能就是正確單詞，繼續(xù)分析。但是這個方法在一些地方并不適用，可能會導(dǎo)致一連串的錯誤出現(xiàn)，于是在使用時要考慮好取舍。編譯錯誤處理函數(shù)：void error( Token token,char *msg) /編譯錯誤處理函數(shù)cout 編譯錯誤：; printf( %s,msg); cout endl 錯誤位置：第 token.row 行，第 token.col token.value;cout endl;cout endl;errornum+;每出現(xiàn)錯誤時，通過傳遞錯誤信息參數(shù)以及單詞信息，調(diào)用編譯錯誤處理函數(shù)進行實時報錯。（3）測試數(shù)據(jù)和結(jié)果見后文語義分析部分(4) 語法分析部分的小總結(jié)原本打算試試自底向上歸約方法設(shè)計的，結(jié)果想了想發(fā)現(xiàn)實在麻煩，老師給的文法又挺龐雜的，創(chuàng)建分析表什么的就要好久。后來一想用遞歸下降方法好處很多，做到之后的語義分析和四元式生成的時候在語法分析的基礎(chǔ)上拓展很方便，整體框架非常清晰。在錯誤處理方面考慮的還是挺合理的，對于一些常見錯誤都能有效指出。并且程序只有一個出口，任何代碼輸入都會從那一個出口結(jié)束，不會引起程序崩潰。2、語義分析設(shè)計語義分析主要實現(xiàn)3個功能 變量重復(fù)定義； 變量未定義就使用； 變量未賦值就引用；(1)相關(guān)數(shù)據(jù)結(jié)構(gòu)struct Symtable /符號表結(jié)構(gòu)string name;int type;bool value;S;struct compare: binary_function /仿函數(shù)和綁定器bool operator()( Symtable s, string str) constif (= str)return true;elsereturn false;(2)相關(guān)函數(shù)void push_in_token( Token token ) /進表操作S.name = token.value;S.type = -1;S.value = false;ST.push_back( S );vector : iterator find_token( Token token ) /查表操作it = find_if( ST.begin(), ST.end(), bind2nd( compare(),token.value );return it;（2） 測試數(shù)據(jù)和結(jié)果（4）設(shè)計思路語義部分主要采用符號表結(jié)構(gòu)，符號表中記錄了每個非終結(jié)符的信息。（名稱，類型，是否賦值）。然后再程序中每次調(diào)用Token函數(shù)發(fā)現(xiàn)讀取到標識符時都進行查表操作。根據(jù)查表結(jié)果進行相關(guān)分析。在賦值函數(shù)中，如果查表找到其信息就說明重復(fù)定義。再其余函數(shù)中1.沒有找到說明為聲明就使用。 2.找到發(fā)現(xiàn)未賦值說明未賦值就引用。（5）語義部分小總結(jié)假如只實現(xiàn)以上3個功能語義部分并不難，關(guān)鍵是符號表的構(gòu)建以及進表查表等操作。在這一部分我使用了仿函數(shù)和綁定器進行查表。由于我把相應(yīng)表結(jié)構(gòu)都存在vector內(nèi)，導(dǎo)致查找結(jié)構(gòu)內(nèi)成員信息的不便，但是自己寫一套查找操作代碼估計效率不高，索性使用仿函數(shù)進行查找，泛型操作一般效率較高而且代碼較少也很清晰。假如時間更充足一點其實還可以把數(shù)據(jù)類型匹配這一部分拓展一下，畢竟也是查表比較，但是時間有限只好先完成要求的3個任務(wù)。3、四元式分析設(shè)計（1）相關(guān)數(shù)據(jù)結(jié)構(gòu)struct Quaternary/四元式結(jié)構(gòu)int serial;string op;string v1;string v2;string result;Q;stack operator_stack;/操作數(shù)堆棧stack operand_stack;/操作符堆棧（2）相關(guān)函數(shù)Quaternary Quaternary_generater( int serial, string op, string v1, string v2, string result )/四元式生成函數(shù)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();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; ssQV.back().serial;string s=ss.str(); (*it2).result=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.front().result ) endl;it2 = QV.begin();QV.erase( it2 );（3） 測試數(shù)據(jù)和結(jié)果（4）設(shè)計思路賦值運算部分整體結(jié)構(gòu)流程如下：說明：首先建立操作符棧和運算符棧。每次掃描遇到操作符遍進棧，遇到運算符如果當(dāng)前?？談t進棧，否則和棧頂操作符的優(yōu)先級進行比較，如果小于等于其優(yōu)先級，則pop棧頂符號，進行四元式生成，再將四元式壓入四元式隊列，然后繼續(xù)與棧頂元素比較直至其優(yōu)先級大于其優(yōu)先級或?？談t進棧。If語句部分在對布爾表達式進行判斷時，先讓操作符和運算符進棧，轉(zhuǎn)移序號先賦為null等到掃描到if then之后的部分通過對其四元式生成確定了序號，這時候再查找隊列進行回填序號。函數(shù)具體結(jié)構(gòu)：void biaodashi()xiang();while( token.value=+ | token.value=- )/四元式while( !operator_stack.empty() & operator_stack.top()!= )/此處要注意用while循環(huán)，if會出錯，因為需要不斷判斷直至棧頂?shù)姆杻?yōu)先級小于需要壓棧的符號此處生成四元式，四元式進隊列for( it2=QV.begin(); it2!=QV.end(); it2+ )/找回真出口if( (*it2).result=null )stringstream ss; ssQV.back().serial;string s=ss.str(); (*it2).result=s;break;operator_stack.push( token.value );/如果棧空或者準備進棧的符號的優(yōu)先級大于棧頂?shù)膬?yōu)先級則進棧token = getToken();xiang();（5）四元式的總結(jié)：這部分是我覺得此次試驗最難的一部分。而且也是我花費時間最多的一部分。在寫賦值運算的那部分時，把一個while循環(huán)寫成了if（我一開始以為運算符進棧只需判斷一次）導(dǎo)致測試數(shù)據(jù)結(jié)果出錯找了好久錯誤才找到。If語句那部分的四元式的編寫也十分困難，尤其是找回真假出口讓我考慮了很久。而且測試數(shù)據(jù)整個代碼有許多這種語句，應(yīng)當(dāng)在每個語句結(jié)束時就輸出一次四元式，不然會導(dǎo)致次序的混亂。（一開始我沒發(fā)現(xiàn)，是把所有四元式進隊列到最后程序結(jié)束時一起輸出的），最后調(diào)試了許久，才發(fā)現(xiàn)問題，于是在語句結(jié)果判斷分號時，就調(diào)用四元式輸出函數(shù)進行輸出。六、整體總結(jié) 這次編譯原理大作業(yè)讓真的我受益良多，整個近千行代碼基本都是我一點一點慢慢敲出來的，過程固然辛苦但是學(xué)到了不少。尤其是在做語法分析和四元式生成的部分，代碼量較大，一開始思路也不太清晰，但是還是一點一點硬著頭皮往下寫，結(jié)果在寫的過程中一些思路就出來了，看來有時候還是要多動手，光苦思冥想并不行。對于這次作業(yè)我自己是比較滿意的但是還是有一些不足：語法部分本來想對文法進行拓展把布爾表達式那部分的附加題解決掉，無奈時間有限，實在來不及寫，可能留到暑假自己再完善吧。四元式部分其實做得并不完完善，有些測試數(shù)據(jù)會出現(xiàn)錯誤結(jié)果，主要是還是因為布爾表達式那部分文法沒有拓展，在進行復(fù)雜布爾表達式判斷時會出錯，而且if語句真假口如果遇到復(fù)雜的算數(shù)運算可能會出口回填錯誤?？傮w來說，這次作業(yè)基本任務(wù)還是都完成了，通過這次大作業(yè)也對整個編譯器的設(shè)計有了比以前更深的了解和體會，看來還是實踐才能出真知。附錄文法如下：1. 2. 3. function id ( ) end function 4. begin 語句 語句 end 5. | |6. def id , id as ；7. integer | float | string8. input id , id ；9. output , ；10. id = ；11. if else 12. while do 13. +| 14. *|/ 15. id | con | deci | ( )14. and | or 15. 16. | | = | = | 附錄： 詞法分析完整代碼（復(fù)制可執(zhí)行）/*詞法分析程序BY 謝卓函ON June 20th */#include #include #include #include #include #define MAXLINE 30using namespace std;/標識符1，整數(shù)2，小數(shù)3，字符串4，保留字5，數(shù)學(xué)運算符6，比較運算符7，邏輯運算符8，分隔符9string key14=if,else,while,do,float,string,begin,end,def,integer,input,output,as,function; /保留字string border5= ; , , , ( , ) ; /分隔符 5string arithmetic9=+ , - , * , / , , , = ; /運算符 6string text; /記錄標識符 1string contentMAXLINE; /保存從文件讀取的內(nèi)容int i=0;/i為字符游標int templine = 0;int scan( string s ,int line )int j, flag =0;text = ; /賦空textwhile( contentlinei= )/判斷空格i+;/是空格跳過if( (contentlinei=65 & contentlinei=91 & contentlinei=65 & contentlinei=91 & contentlinei=0 & contentlinei=9 ) /判斷是否為數(shù)字或者字母或者下劃線text += contentlinei;i+;for( j=0; j=0 & contentlinei=0 & contentlinei=9 )/判斷是否為數(shù)字text += contentlinei;i+;return 2; /整數(shù)return 3;/小數(shù)if( contentlinei= ; | contentlinei= | contentlinei= | contentlinei=( | contentlinei=) | contentlinei=, )/判斷是否為分隔符 text = contentlinei;i+; return 9;if( contentlinei= + | contentlinei=- | contentlinei=* | contentlinei= )/判斷是否為運算符 text = contentlinei; i+;return 6;if( contentlinei= )if( contentlinei+1= )text = contentlinei;text += contentlinei+1;i=i+2;return 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;/如果為行注釋那么游標指向行末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,ios:in);if( infile )cout 文件讀取成功! endl;elsecout 文件讀取失敗! endl;int hang, mode,k=1,numline; /k用于定位行數(shù)cout endl;cout 測試數(shù)據(jù)如下： endl;while ( getline(infile,contentk) )cout contentk endl;k+;numline = k-; /numline記錄了文件總行數(shù)cout endl;cout 詞法分析結(jié)果： endl;for( k=1; k=numline; k+ )while( i!=contentk.length() )mode = scan( contentk, k );if( mode!=0 & mode!= -1 )cout 所在行數(shù)： k 所在列數(shù)： i-text.length()+1 單詞類別： mode 單詞為： text endl ;elseif( mode=0 )if( icontentk.length() ) i+;/如果為行注釋 直接跳到下一行elseif( mode=-1 )/如果為塊注釋 找回行號k=templine;i = 0;/一行結(jié)束定位到下一行行頭getchar(); return 0;附錄二 語法語義四元式生成代碼（復(fù)制可執(zhí)行）/*語法+語義+四元式分析程序BY 謝卓函ON June 25th */#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXLINE 30using namespace std;/標識符1，整數(shù)2，小數(shù)3，字符串4，保留字5，數(shù)學(xué)運算符6，比較運算符7，邏輯運算符8，分隔符9string key14=if,else,while,do,float,string,begin,end,def,integer,input,output,as,function; /保留字string border5= ; , , , ( , ) ; /分隔符 5string arithmetic9=+ , - , * , / , , , = ; /運算符 6string text; /記錄標識符 1string contentMAXLINE; /保存從文件讀取的內(nèi)容string resultMAXLINE = t1,t2,t3,t4,t5,t6,t7,t8,t9,t10;/*/*語法語義 各產(chǎn)生式 函數(shù)*/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 guanxibiaodashi();void guanxi();void error();void Quaternary_output();void Quaternary_maker();int i=0,k=1,numline,mode;/i為字符游標,k為行號,numline記錄了文件總行數(shù)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;struct Symtable /符號表結(jié)構(gòu)string name;int type;bool value;S;struct Quaternary/四元式結(jié)構(gòu)int serial;string op;string v1;string v2;string result;Q;Quaternary Quaternary_generater( int serial, string op, string v1, string v2, string result );/函數(shù)聲明vector ST;vector : iterator it;vector QV;vector : iterator it2;stack operator_stack;/操作數(shù)堆棧stack operand_stack;/操作符堆棧struct compare: binary_function /仿函數(shù)和綁定器bool operator()( Symtable s, string str) constif (= str)return true;elsereturn false;void push_in_token( Token token ) /進表操作S.name = token.value;S.type = -1;S.value = false;ST.push_back( S );vector : 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;text = ; /賦空textwhile( contentlinei= )/判斷空格i+;/是空格跳過if( (contentlinei=65 & contentlinei=91 & contentlinei=65 & contentlinei=91 & contentlinei=0 & contentlinei=9 ) /判斷是否為數(shù)字或者字母或者下劃線text += contentlinei;i+;for( j=0; j=0 & contentlinei=0 & contentlinei=9 )/判斷是否為數(shù)字text += contentlinei;i+;return 2; /整數(shù)return 3;/小數(shù)if( contentlinei= ; | contentlinei= | contentlinei= | contentlinei=( | contentlinei=) | contentlinei=, )/判斷是否為分隔符 text = contentlinei;i+; return 9;if( conten