編譯原理實驗報告

1、僅供參考編譯原理實驗報告合肥工業(yè)大學(xué)計算機與信息學(xué)院專業(yè)： 信息安全11-1 學(xué)生姓名： 周偉康 指導(dǎo)教師： 李宏芒 完成時間：2013年6月1日第 27 頁 共 24 頁實驗一 詞法分析設(shè)計一、實驗?zāi)康耐ㄟ^本實驗的編程實踐，使學(xué)生了解詞法分析的任務(wù)，掌握詞法分析程序設(shè)計的原理和構(gòu)造方法，使學(xué)生對編譯的基本概念、原理和方法有完整的和清楚的理解，并能正確地、熟練地運用。二、實驗內(nèi)容用VC+/VB/JAVA語言實現(xiàn)對C+語言子集的源程序進行詞法分析。通過輸入源程序從左到右對字符串進行掃描和分解，依次輸出各個單詞的內(nèi)部編碼及單詞符號自身值；若遇到錯誤則顯示“Error”，然后跳過錯誤部分繼續(xù)顯示 ；

2、同時進行標識符登記符號表的管理。以下是實現(xiàn)詞法分析設(shè)計的主要工作：（1）從源程序文件中讀入字符。（2）統(tǒng)計行數(shù)和列數(shù)用于錯誤單詞的定位。（3）刪除空格類字符，包括回車、制表符空格。（4）按拼寫單詞，并用（內(nèi)碼，屬性）二元式表示。（5）如果發(fā)現(xiàn)錯誤則報告出錯。（6）根據(jù)需要是否填寫標識符表供以后各階段使用。三、實驗要求1、編程時注意編程風(fēng)格：空行的使用、注釋的使用、縮進的使用等。2、將標識符填寫的相應(yīng)符號表須提供給編譯程序的以后各階段使用。3、根據(jù)測試數(shù)據(jù)進行測試。測試實例應(yīng)包括以下三個部分:u 全部合法的輸入。u 各種組合的非法輸入。u 由記號組成的句子。4、詞法分析程序設(shè)計要求輸出形式:例：

3、輸入C+語言的實例程序：For i=0 then n+;a= 3b %);輸出形式為：單詞二元序列（種別，屬性）類型位置（行，列）for(1,for)關(guān)鍵字（1，1）i(6,i)標識符（1，2）=(4，=)關(guān)系運算符（1，3）0(5，0)常數(shù)（1，4）thenErrorError（1，5）n(6,n)標識符（1，6）+ErrorError（1，7）；(2,;)分界符（1，8）a(6,a)標識符（2，1）=(4,<=)關(guān)系運算符（2，2）3bErrorError（2，4）%ErrorError（2，4）)(2,)分界符（2，5）；(2,;)分界符（2，6）四、詞法分析實驗設(shè)計思想及算法 u

4、 程序的說明部分為各種表格和變量安排空間：Type 1: key數(shù)組 c+關(guān)鍵字表（事先構(gòu)造好關(guān)鍵字表）；Type 2: separatrix 數(shù)組 存放分界符表（可事先構(gòu)造好分界符表）；Type 3: arithmetic operator （算術(shù)運算符表）；Type 4: relation operator (關(guān)系運算符表)；Type 5: constant integer （常整數(shù)表）；Type 6: constant real （常實數(shù)表）；Type 7: constant string （常字符串）；Type 8: identifier （標識符）；Type -1 :Error （不

5、可識別符號）；Input/output 輸入/輸出文件流；Class buffer: 輸入緩沖區(qū)類；Buf 緩沖區(qū)對象實例；u 初始化過程：顯示必要的說明（為兼容控制臺，用英文顯示），引導(dǎo)確定有效輸入文件。直接回車默認源文件為當前目錄下src.cpp;u 主程序設(shè)計考慮：主程序關(guān)聯(lián)輸出文件，調(diào)用初始化過程和詞法分析過程（lexical）；在大多數(shù)實際編譯的詞法分析階段，其結(jié)果內(nèi)部存儲直接傳遞給語法分析器，或僅輸出為中間文件。故此詞法分析程序并不供用戶指定文件輸出，而將分析結(jié)果保存在當前目錄下“l(fā)ex.txt”文件中以便查看。u 詞法分析過程考慮：功能：從緩沖區(qū)中辨析出單詞，產(chǎn)生類號和在各類表中

6、指針（type，pointer）；輸出此單詞信息：（單詞，（類號，指針）二元組， 類別標識， 源文件中位置）以便查看。算法：Lexical每次從buf中取一待處理串token，跳過空白字符，以首字分大致類別：字母->關(guān)鍵字或標識符，數(shù)字->常數(shù)，其他->符號；連續(xù)取出本類字符，注意標識符可含_，數(shù)字可含不多于一個.，符號處理時若找到一個”則可將直到下個”之前的內(nèi)容作為字符串常量，若找不到下個”則返回匹配出錯，在下一個可能單詞開始處（最近一個界符之后）繼續(xù)分析。c+的雙字符運算符單詞的第一個字符也必為一個有效符號單詞，故可在識別出一個單字運算符之后超前再搜一個字符判斷是否為雙字

7、運算符。對于標識符，常數(shù)常串，需分別與標識符表和常數(shù)表中已登記的元素相比較，如表中已有該元素，則記錄其在表中的位置，如未出現(xiàn)過，將標識符按順序填入五、程序結(jié)構(gòu)，函數(shù)功能；本程序用C+實現(xiàn)。運用STL簡化代碼量。Class Buffer; 緩沖區(qū)類，ln，col 字段為行列，其它成員函數(shù)顧名思義見源碼。Int classify（char &c）分辨字母數(shù)字，引用型參數(shù)用于統(tǒng)一小寫（即規(guī)定大小寫不敏感，僅為方便處理，與實際c+不符）Int reserve（string s）關(guān)鍵字表（有序）中二分查找s，56個關(guān)鍵字最多6次查找。void getreal(string s, double &

8、amp;t) 串s內(nèi)容轉(zhuǎn)實數(shù)存t中。（詞法分析保證s可轉(zhuǎn)）void getint(string s, int &t) 串s內(nèi)容轉(zhuǎn)整數(shù)存t中。（詞法分析保證s可轉(zhuǎn)）string what(int x) 返回type=x所對應(yīng)的單詞類別標識，方便輸出查看。void print_info(string s,int a, int b) 打印單詞s，類號a，指針b；或出錯信息void lexical() 詞法分析過程；六、用例測試即運行結(jié)果源文件內(nèi)容：運行程序：分析結(jié)果：Code：e1.cpp七、實驗總結(jié)不足：lexcal 代碼繁雜，未能分模塊。影響整個程序的擴充和移植。STL運用不熟練。異常給

9、出不細化。收獲：深入了解詞法分析過程。復(fù)習(xí)鞏固了c/c+語言。尤其c語言中輸出格式控制。附：單詞分類表表一：keywords（type = 1）asmautoboolbreakcasecatchcharclassconstcontinue12345678910defaultdeletedodoubleelseenumexplicitexportExternfalse11121314151617181920floatforFriendgotoifinlineintlongnamespacenew21222324252627282930operatorprivateprotectedpublicr

10、egisterreturnshortsignedsizeofstatic31323334353637383940structswitchtemplatethisthrowtruetrytypedeftypenameunion41424344454647484950unsignedusingVirtualvoidvolatilewhile515253545556表二：separatrix（type = 2）;,()123456789表三：arithmetic operator （type = 3）*%+-<=>&|+123456789101112-<<>&g

11、t;+=-=*=/=%=&=|=1314151617181920212223表四：relation operator （type = 4）!=<=>=!=&&|12345678實驗二 LL(1)分析法一、實驗?zāi)康?通過完成預(yù)測分析法的語法分析程序，了解預(yù)測分析法和遞歸子程序法的區(qū)別和聯(lián)系。使學(xué)生了解語法分析的功能，掌握語法分析程序設(shè)計的原理和構(gòu)造方法，訓(xùn)練學(xué)生掌握開發(fā)應(yīng)用程序的基本方法。有利于提高學(xué)生的專業(yè)素質(zhì)，為培養(yǎng)適應(yīng)社會多方面需要的能力。二、實驗內(nèi)容u 根據(jù)某一文法編制調(diào)試 LL （ 1 ）分析程序，以便對任意輸入的符號串進行分析。u 構(gòu)造預(yù)測分析表，

12、并利用分析表和一個棧來實現(xiàn)對上述程序設(shè)計語言的分析程序。u 分析法的功能是利用LL（1）控制程序根據(jù)顯示棧棧頂內(nèi)容、向前看符號以及LL（1）分析表，對輸入符號串自上而下的分析過程。 三、實驗要求1、編程時注意編程風(fēng)格：空行的使用、注釋的使用、縮進的使用等。2、如果遇到錯誤的表達式，應(yīng)輸出錯誤提示信息。 3、對下列文法，用LL（1）分析法對任意輸入的符號串進行分析： （1）E->TG（2）G->+TG|TG（3）G->（4）T->FS（5）S->*FS|/FS（6）S->（7）F->(E)（8）F->i輸出的格式如下：四、 LL（1）分析法實驗設(shè)計

13、思想及算法u 文法分析：FIRST和FOLLOW集：FIRST (F) = i , ( FIRST (S) = * , , FIRST (G) = + , - , FIRST (T) = i , ( FIRST (E) = i , ( FOLLOW (F) = * , / , + , - , ) , # FOLLOW (S) = + , - , ) , # FOLLOW (G) = ) , # FOLLOW (T) = + , - , ) , # FOLLOW (E) = ) , # 構(gòu)造LL（1）分析表：i+-*/()#EE->TGE->TGTT->FST->FSGG

14、->+TGG->-TGG->G->FF->iF->(E)SS->S->S->*FSS->/FSS->S->u 模塊結(jié)構(gòu)：（1）定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。Vt：終結(jié)符下標映射集。Vn：非終結(jié)符下標映射集。T ：LL（1）分析表。Sym：符號棧，it為其棧頂，為方便輸出用vector模擬。In ：輸出串。St ：規(guī)約時所用產(chǎn)生式。（2）初始化：設(shè)立LL(1)分析表。（3）分析過程：從鍵盤輸入一個表達式符號串input；把#和文法開始符號入sym棧；把input第一個符號給a；While （1） X = Sym.pop

15、();If x in Vt thenIf x = a then 把下個輸入符號給aElse ERRORElse if x = #then If x = a then break else ERRORElse if Tx, a = Pi then 產(chǎn)生式Pi右側(cè)依次反向入sym棧Else ERROR分析成功；五、程序結(jié)構(gòu)，函數(shù)功能；本程序用C+實現(xiàn)。運用STL簡化代碼量。void prepare()；初始化LL（1）表。void analysis()；預(yù)測分析總控過程。int main()； 主函數(shù)，順序調(diào)用上兩過程。六、用例測試即運行結(jié)果Code：e2.cpp七、實驗總結(jié)不足：程序功能單一，未

16、能實現(xiàn)對任意文法的LL（1）判斷、預(yù)測分析表構(gòu)建、句子分析的統(tǒng)一。 異常給出不細化。收獲：熟練first，follow集的求法，LL（1）預(yù)測分析表的構(gòu)建。復(fù)習(xí)鞏固了c/c+語言。尤其c+語言中輸出格式控制和STL簡單運用，為下次實驗打好基礎(chǔ)。實驗三 LR(1)分析法一、實驗?zāi)康?構(gòu)造LR(1)分析程序，利用它進行語法分析，判斷給出的符號串是否為該文法識別的句子，了解LR（K）分析方法是嚴格的從左向右掃描，和自底向上的語法分析方法。二、實驗內(nèi)容對下列文法，用LR（1）分析法對任意輸入的符號串進行分析： （1）EE+T（2）EET（3）TT*F（4）TT*F（5）TT/F（6）TT*F（7）F(

17、E)（8）Fi三、實驗要求1、編程時注意編程風(fēng)格：空行的使用、注釋的使用、縮進的使用等。2、如果遇到錯誤的表達式，應(yīng)輸出錯誤提示信息。 3、從文件輸入文法，構(gòu)建項目其LR（1）項目集規(guī)范族，及每個項目集的轉(zhuǎn)換函數(shù)GO。4、構(gòu)建LR（1）規(guī)范分析表。5、以分析表對輸入句子進行移進規(guī)約。四、LR（1）分析法實驗設(shè)計思想及算法 (1)總控程序，也可以稱為驅(qū)動程序。對所有的LR分析器總控程序都是相同的。(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將不同，分析表又可以分為動作表（ACTION）和狀態(tài)轉(zhuǎn)換（GOTO）表兩個部分，它們都可用二維數(shù)組表示。(3)分析

18、棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進后出棧。分析器的動作就是由棧頂狀態(tài)和當前輸入符號所決定。u LR分析器由三個部分組成：u 其中:SP為棧指針，Si為狀態(tài)棧，Xi為文法符號棧。狀態(tài)轉(zhuǎn)換表用GOTOi，X=j表示，規(guī)定當棧頂狀態(tài)為i，遇到當前文法符號為X時應(yīng)轉(zhuǎn)向狀態(tài)j，X為終結(jié)符或非終結(jié)符。u ACTIONi，a規(guī)定了棧頂狀態(tài)為i時遇到輸入符號a應(yīng)執(zhí)行。動作有四種可能：(1)移進： actioni，a= Sj：狀態(tài)j移入到狀態(tài)棧，把a移入到文法符號棧，其中i,j表示狀態(tài)號。(2)歸約： actioni，a=rk：當在棧頂形成句柄時，則歸約為相應(yīng)的非終結(jié)符A，即文法中有A- B的產(chǎn)生式

19、，若B的長度為R(即|B|=R)，則從狀態(tài)棧和文法符號棧中自頂向下去掉R個符號，即棧指針SP減去R，并把A移入文法符號棧內(nèi)，j=GOTOi,A移進狀態(tài)棧，其中i為修改指針后的棧頂狀態(tài)。(3)接受acc: 當歸約到文法符號棧中只剩文法的開始符號S時，并且輸入符號串已結(jié)束即當前輸入符是'#'，則為分析成功。(4)報錯:當遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入端不是該文法能接受的符號串。五、程序結(jié)構(gòu)，函數(shù)功能；程序要求與功能：1.在同目錄下“grammar.txt”中輸入文法，格式如下：開始符號必須在第一個產(chǎn)生式左側(cè)每行一個產(chǎn)生式，“->”用空格代替

20、，除此之外，空格無意義。非終結(jié)符用單個大寫字母表示，其他為終結(jié)符空字用$表示。2.LR（1）項目集規(guī)范族及其GO函數(shù)存入“states.txt" LR（1）分析表存入“LR(1) parsing table.txt" 文法，first集，分析表，同時在控制臺顯示 輸入句子及“移進規(guī)約”過程也在控制臺完成本程序用C+實現(xiàn)。運用STL簡化代碼量。全局變量說明：first非終結(jié)符對其FIRST集的映射；G文法，即產(chǎn)生式集合；Vt、Vn 終結(jié)符、非終結(jié)符集；States利用GO函數(shù)廣度優(yōu)先建立識別活前綴DFA時存放狀態(tài)的隊列；Actionsaction表Gotosgoto表V文法符

21、號對下標的映射，方便確定其在action，goto表中的位置。類和各函數(shù)說明：Class Item LR（1）項目類。包括一個帶點的產(chǎn)生式，和一個展望字符集。Class Item_set LR(1)項目集（狀態(tài)）類。包含一組LR（1）項目類實例I，和若干二元組集合，每個二元組表示本狀態(tài)Go函數(shù)的文法符號和下一狀態(tài)標號。void Item_set:closure() 對項目集求閉包void Item_set:output(ofstream &f) 輸出狀態(tài)（包括展望字符集）void inputG(const string& G_file) 從輸入文件中讀入文法，調(diào)用dot_G()

22、；void dot_G() 對每個產(chǎn)生式右第一個位置加；void getfirst(char e, set<char> & f) 對非終結(jié)符e求其FIRST集，存入f。void findV() 從文法G中分類符號到Vt，Vn調(diào)用getfirst();vector<string> production(char c) 返回一組字符c在左的帶產(chǎn)生式；set<char> findfirst(string& str, set<char>& X) AB，a對(a)求FIRSTItem_set GO(Item_set& Ix,

23、 char x) 求GO（Ix，x）bool isdifferent(Item_set& Ix) 判斷Go出的狀態(tài)是否已在states隊列中出現(xiàn)void DFA() 廣度優(yōu)先擴展DFA，以GO作為擴展條件void creat_goto() 建goto表；void creat_action() 建action表；void print_parsing_table() 打印LR（1）分析表；void print_states() 打印狀態(tài)信息；void print_production_num() 打印產(chǎn)生式及其編號，方便查看分析表；void print_first() 打印非終結(jié)符FIRS

24、T集；void parse() 輸入句子，LR（1）分析過程；int main() 調(diào)用上述子過程；詳細注釋見源碼六、用例測試即運行結(jié)果例1、文法文件：運行程序：查看狀態(tài)文件內(nèi)容：輸入句子：例2：文法文件：運行程序：查看狀態(tài)文件內(nèi)容：Sum to 30 states.I0: .E# E .E+T# + - E .E-T# + - E .T # + - T .T*F# * + - / T .T/F# * + - / T .F # * + - / F .(E)# * + - / F .i # * + - / GO(I0,() = I4GO(I0,E) = I1GO(I0,F) = I3GO(I0,

25、T)=I2GO(I0,i)=I5I1: E. # E E.+T# + - E E.-T# + - GO(I1,+)=I6GO(I1,-)=I7I2:E T. # + - T T.*F# * + - / T T./F# * + - / GO(I2,*)=I8GO(I2,/)=I9I3:T F. # * + - / I4:F (.E)# * + - / E .E+T) + - E .E-T) + - E .T ) + - T .T*F) * + - / T .T/F) * + - / T .F ) * + - / F .(E) * + - / F .i ) * + - / GO(I4,()=I13

26、GO(I4,E)=I10GO(I4,F)=I12GO(I4,T)=I11GO(I4,i)= I14I5:F i. # * + - / I6:E E+.T# + - T .T*F# * + - / T .T/F# * + - / T .F # * + - / F .(E)# * + - / F .i# * + - / GO(I6,()=I4GO(I6,F)=I3GO(I6,T)=I15GO(I6,i)= I5I7:E E-.T# + - T .T*F# * + - / T .T/F# * + - / T .F # * + - / F .(E)# * + - / F .i # * + - / GO

27、(I7,()=I4GO(I7,F)=I3GO(I7,T)=I16GO(I7,i)= I5I8:T T*.F# * + - / F .(E)# * + - / F .i # * + - / GO(I8,()=I4GO(I8,F)=I17GO(I8,i)= I5I9:T T/.F# * + - / F .(E)# * + - / F .i # * + - / GO(I9,()=I4GO(I9,F)=I18GO(I9,i)= I5I10:F (E.)# * + - / E E.+T) + - E E.-T) + - GO(I10,)=I19GO(I10,+)=I20GO(I10,-)= I21I11

28、:E T. ) + - T T.*F) * + - / T T./F) * + - / GO(I11,*)=I22GO(I11,/)= I23I12:T F. ) * + - / I13:F (.E) * + - / E .E+T) + - E .E-T) + - E .T ) + - T .T*F) * + - / T .T/F) * + - / T .F ) * + - / F .(E) * + - / F .i ) * + - / GO(I13,()=I13GO(I13,E)=I24GO(I13,F)=I12GO(I13,T)=I11GO(I13,i)= I14I14:F i. ) *

29、+ - / I15:E E+T.# + - T T.*F# * + - / T T./F# * + - / GO(I15,*)=I8GO(I15,/)= I9I16:E E-T.# + - T T.*F# * + - / T T./F# * + - / GO(I16,*)=I8GO(I16,/)=I9I17:T T*F.# * + - / I18:T T/F.# * + - / I19:F (E).# * + - / I20:E E+.T) + - T .T*F) * + - / T .T/F) * + - / T .F ) * + - / F .(E) * + - / F .i ) * +

30、- / GO(I20,()=I13GO(I20,F)=I12GO(I20,T)=I25GO(I20,i)= I14I21:E E-.T) + - T .T*F) * + - / T .T/F) * + - / T .F ) * + - / F .(E) * + - / F .i ) * + - / GO(I21,()=I13GO(I21,F)=I12GO(I21,T)=I26GO(I21,i)= I14I22:T T*.F) * + - / F .(E) * + - / F .i ) * + - / GO(I22,()=I13GO(I22,F)=I27GO(I22,i)= I14I23:T T

31、/.F) * + - / F .(E) * + - / F .i ) * + - / GO(I23,()=I13GO(I23,F)=I28GO(I23,i)=I14I24:F (E.) * + - / E E.+T) + - E E.-T) + - GO(I24,)=I29GO(I24,+)=I20GO(I24,-)= I21I25:E E+T.) + - T T.*F) * + - / T T./F) * + - / GO(I25,*)=I22GO(I25,/)=I23I26:E E-T.) + - T T.*F) * + - / T T./F) * + - / GO(I26,*)=I22G

32、O(I26,/)=I23I27:T T*F.) * + - / I28:T T/F.) * + - / I29:F (E).) * + - / 輸入句子：七、實驗總結(jié)不足：此次實驗時間有限，輸出不直觀且受控制臺限制，之后可考慮利用MFC或Java編寫圖形化界面，包括DFA圖也可設(shè)法畫出。 異常給出不細化。收獲：雖是LR（1）分析試驗，但在實現(xiàn)過程中也加深了LR（0），SLR，LALR的理解，充分認識Go函數(shù)和求MFA再確定為DFA的等價性。對c+容器的運用也略微熟練了。 Code：e3.cpp附：算術(shù)表達式文法的LR分析表狀態(tài)ACTIONGOTO#（）*+-/iEFT0s4s51231s6s7

33、acc2r3r3s8s9r33r6r6r6r6r64s13s141011125r8r8r8r8r86s4s51537s4s51638s4s5179s4s51810s20s21s1911r3r3s22s23r312r6r6r6r6r613s13s1424111214r8r8r8r8r815r1r1s8s9r116r2r2s8s9r217r4r4r4r4r418r5r5r5r5r519r7r7r7r7r720s13s14251221s13s14261222s13s142723s13s142824s20s21s2925r1r1s22s23r126r2r2s22s23r227r4r4r4r4r428r

34、5r5r5r5r529r7r7r7r7r7實驗四 逆波蘭表達式的產(chǎn)生及計算一、實驗?zāi)康?非后綴式用來表示的算術(shù)表達式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達式，并計算用逆波蘭式來表示的算術(shù)表達式的值。二、實驗內(nèi)容將非后綴式用來表示的算術(shù)表達式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達式，并計算用逆波蘭式來表示的算術(shù)表達式的值。擴展：基于后綴表達式的計算器。三、逆波蘭表達式的產(chǎn)生及計算實驗設(shè)計思想及算法1.程序流程：a）程序歡迎界面b）關(guān)聯(lián)輸入文件，不存在轉(zhuǎn) step mc）從輸入文件獲得一行中綴表達式midd）mid是以分號開頭的字串或讀取到輸入文件尾，轉(zhuǎn)step 0e) 標準化mid（若干空格的情況）f）輸出mid到文件g）若mid不合法,給出錯誤信息后轉(zhuǎn)step ch）將中綴mid轉(zhuǎn)成后綴表達式suffixi）若suffix不合法,給出錯誤信息后轉(zhuǎn)step cj）suffix存在錯誤運算，給出錯誤信息后轉(zhuǎn)step ck）輸出suffix到文件l）計算suffix結(jié)果，輸出到文件后轉(zhuǎn)step cm）建議用戶重建輸入文件，用戶拒絕，轉(zhuǎn) step 0n）等待用戶重建完成后轉(zhuǎn) step c0）給出任務(wù)完成狀態(tài)，程序結(jié)束2.主要算法1）中綴表達式mid轉(zhuǎn)后綴表達式suffix： i ）定義一個運算符棧S，把一個最小的符號0壓棧，當它出棧時轉(zhuǎn)化完成。 ii）將