編譯技術(shù)--實驗指導書

1、編譯技術(shù)實驗指導書湘潭大學信息工程學院計算機工程系 何春梅2015-09-01實驗課時說明編譯技術(shù)課總課時為32/8學時，其中實驗課時為8學時，課時分配為：前三個實驗是必做實驗：其中DFA的模擬程序2學時、DFA的化簡2學時、LL(1)文法判斷程序4學時。后面3個實驗為學生根據(jù)自己安排選做實驗。目 錄實驗1 DFA模擬程序 1實驗2 DFA化簡 2實驗3 LL(1)文法判斷程序 4實驗4 基于預測分析表法的語法分析程序(1) 5實驗5 基于預測分析表法的語法分析程序(2) 6實驗6 中間代碼生成：逆波蘭式的產(chǎn)生與計算 8 實驗1 詞法程序設(shè)計DFA模擬程序一、實驗?zāi)康?通過實驗教學，加深學生對

2、所學的關(guān)于編譯的理論知識的理解，增強學生對所學知識的綜合應(yīng)用能力，并通過實踐達到對所學的知識進行驗證。通過對DFA模擬程序?qū)嶒?，使學生掌握詞法分析的實現(xiàn)技術(shù)，及具體實現(xiàn)方法。通過本實驗加深對詞法分析程序的功能及實現(xiàn)方法的理解 。二、實驗環(huán)境 供Windows系統(tǒng)的PC機，可用C+/C#/Java等編程工具編寫三、實驗內(nèi)容 1、定義一個右線性正規(guī)文法，示例如(僅供參考) GS：SaU|bV UbV|aQ VaU|bQ QaQ|bQ|e實驗前要考慮清楚用哪種數(shù)據(jù)結(jié)構(gòu)存儲上述文法。2、構(gòu)造其有窮確定自動機，如3、利用有窮確定自動機M=(K,f, S,Z）行為模擬程序算法，來對于任意給定的串，若屬于該

3、語言時，該過程經(jīng)有限次計算后就會停止并回答“是”，若不屬于，要么能停止并回答“不是”。K:=S；c:=getchar;while c<>eof do K:=f(K,c); c:=getchar; ;if K is in Z then return (yes)else return (no)四、實驗方式與要求1、每位同學定義的語言或文法不同，上機編程實現(xiàn)2、實驗報告格式要求書寫要點：概要設(shè)計（總體設(shè)計思想）；詳細設(shè)計（程序主流程、自動機的存儲格式、關(guān)鍵函數(shù)的流程圖）；結(jié)果分析（輸入與輸出結(jié)果、存在問題及有待改進善的地方、實驗心得）。實驗2 DFA（確定的有窮自動機）的化簡一、 實驗?zāi)?/p>

4、的與要求通過設(shè)計、編寫和調(diào)試將確定的有窮自動機的狀態(tài)數(shù)變?yōu)樽钌俚腃程序，使得學生掌握化簡為有窮自動機的過程中的相關(guān)概念和方法。DFA的表現(xiàn)形式可以為表格或圖形。二、 問題描述每一個正規(guī)集都可以由一個狀態(tài)數(shù)最少的DFA所識別，這個DFA是唯一的（不考慮同構(gòu)的情況）。任意給定的一個DFA，根據(jù)以下算法設(shè)計一個C程序，將該DFA 化簡為與之等價的最簡DFA。三、 算法（1）構(gòu)造具有兩個組的狀態(tài)集合的初始劃分I：接受狀態(tài)組 F 和非接受狀態(tài)組 Non-F。（2）對I采用下面所述的過程來構(gòu)造新的劃分I-new. For I 中每個組G do Begin 當且僅當對任意輸入符號a,狀態(tài)s和讀入a后轉(zhuǎn)換到I

5、的同一組中； /*最壞情況下，一個狀態(tài)就可能成為一個組*/ 用所有新形成的小組集代替I-new中的G; end（3）如果I-new=I，令I(lǐng)-final=I,再執(zhí)行第（4）步，否則令I(lǐng)=I=new,重復步驟（2）。（4）在劃分I-final的每個狀態(tài)組中選一個狀態(tài)作為該組的代表。這些代表構(gòu)成了化簡后的DFAM狀態(tài)。令s是一個代表狀態(tài)，而且假設(shè)：在DFA M中，輸入為a時有從s到t轉(zhuǎn)換。令t所在組的代表是r,那么在M中有一個從s到r的轉(zhuǎn)換，標記為a。令包含s0的狀態(tài)組的代表是M的開始狀態(tài)，并令M的接受狀態(tài)是那些屬于F的狀態(tài)所在組的代表。注意,I-final的每個組或者僅含F(xiàn)中的狀態(tài)，或者不含F(xiàn)中

6、的狀態(tài)。（5）如果M含有死狀態(tài)（即一個對所有輸入符號都有刀自身的轉(zhuǎn)換的非接受狀態(tài)d）,則從M中去掉它；刪除從開始狀態(tài)不可到達的狀態(tài)；取消從任何其他狀態(tài)到死狀態(tài)的轉(zhuǎn)換。四、基本要求1、輸入一個DFA M,輸出一個與之等價的最小化的DFA M，上機編程實現(xiàn)。2、實驗報告格式要求書寫要點：概要設(shè)計（總體設(shè)計思想）；詳細設(shè)計：程序主流程、DFA的存儲格式（即數(shù)據(jù)結(jié)構(gòu)）、關(guān)鍵函數(shù)的流程圖；結(jié)果分析（輸入與輸出結(jié)果、存在問題及有待改進善的地方、實驗心得）五、測試數(shù)據(jù)輸入下圖的DFA M,得到其最簡的DFA M。 DFA M六、 實現(xiàn)提示：（1） 可將輸入的DFA存放在外部文本文件中，也可以直接從NFA轉(zhuǎn)換

7、得到。對DFA的最小化分兩部分進行化簡，即分別對狀態(tài)（結(jié)點）和路徑（?。┻M行最小化，最后輸出最小化的DFA。（2） 實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)：用鏈表實現(xiàn)DFA的構(gòu)造：由結(jié)點鏈表和轉(zhuǎn)換弧鏈表組成： struct node /結(jié)點的定義int pos;/結(jié)點在哪個組中 int num；/結(jié)點的序號 int accept; /結(jié)點是否為接受狀態(tài) struct node *next; NODE; struct arc/弧的定義 int start; /開始的頂點位置 char input; /弧上所接受的輸入字符 int end; /結(jié)束的頂點位置 struct arc *next;ARC; Struct gr

8、oups /分組后各結(jié)點所在組的位置 int n; /屬于哪個組 int i;/在組中的位置GROUPs;（3） 實現(xiàn)方法：根據(jù)accept的值為0還是1進行初次劃分I，將accept為0的所有結(jié)點構(gòu)建成一個鏈表，將accept為1的所有結(jié)點構(gòu)建一個鏈表。然后執(zhí)行最小化函數(shù)，對每一個輸入字符遍歷以上個鏈表，對每個結(jié)點.num=弧.start的情況，查看該弧.end的組號是否相等，相等則不劃分；若不相等，則需進一步劃分，構(gòu)建新的鏈表等。劃分完成后選頭結(jié)點為代表，刪除結(jié)點鏈表上其他結(jié)點，并將弧線鏈表上需被刪的弧.start或弧.end該為頭結(jié)點。實驗3 LL(1)文法判斷程序一、實驗?zāi)康?首先能讓

9、用戶輸入一個文法，然后讓計算機自動判斷是否是一個LL(1)文法，通過實驗教學，加深學生對所學的關(guān)于編譯的理論知識的理解，增強學生對所學知識的綜合應(yīng)用能力，并通過實踐達到對所學的知識進行驗證。二、實驗環(huán)境 供Windows系統(tǒng)的PC機，可用C+/C#/Java等編程工具編寫三、實驗步驟 1、讓計算機接受一個文法，示例如(僅供參考)：GS 為:SAB SbCA AbB BaDCAD CbDaS Dc1. 2、編程實現(xiàn)對上述文法是否是LL(1)文法的判斷，是則給出肯定回答，否則給出否定回答。2. 判別是否是LL(1)文法以鏈表或數(shù)組等數(shù)據(jù)結(jié)構(gòu)保存文法.求出能推出的非終結(jié)符.計算FIRST集,FOLL

10、OW集和SELECT集SELECT(A)SELECT(A)=?輸出肯定回答是輸出否定回答否實驗流程圖如下：實驗4-5基于預測分析表法的語法分析程序一、實驗?zāi)康?通過對基于LL(1)文法的預測分析表法實現(xiàn)DFA模擬程序?qū)嶒?，使學生掌握確定的自上而下的語法分析的實現(xiàn)技術(shù)，及具體實現(xiàn)方法。通過本實驗加深對語詞法分析程序的功能及實現(xiàn)方法的理解。二、實驗環(huán)境 供Windows系統(tǒng)的PC機，可用C+/C#/Java等編程工具編寫三、實驗步驟 1、定義一個LL(1)文法，示例如(僅供參考) GE：E TE' E'+TE'|T FT' T' *FT'| F i|

11、(E)2、構(gòu)造其預測分析表，如3、LL(1)文法的預測分析表的模型示意圖4、預測分析控制程序的算法流程 5、運行結(jié)果，示例如下四、實驗方式與要求1、每位同學定義的文法不同，上機編程實現(xiàn);2、實驗報告格式要求書寫要點：概要設(shè)計（總體設(shè)計思想）；詳細設(shè)計（程序主流程、自動機的存儲格式、關(guān)鍵函數(shù)的流程圖）；結(jié)果分析（輸入與輸出結(jié)果、存在問題及有待改進善的地方、實驗心得）.實驗6 逆波蘭式的產(chǎn)生及計算一、實驗?zāi)康模?將非后綴式用來表示的算術(shù)表達式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達式，并計算用逆波蘭式來表示的算術(shù)表達式的值。 二、實驗內(nèi)容:  1.定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。 2.初始化

12、：設(shè)立算符優(yōu)先分析表、初始化變量空間（包括堆棧、結(jié)構(gòu)體、數(shù)組、臨時變量等）； 3.控制部分：從鍵盤輸入一個表達式符號串； 4.利用算符優(yōu)先分析算法進行表達式處理：根據(jù)算符優(yōu)先分析表對表達式符號串進行堆棧（或其他）操作，輸出分析結(jié)果，如果遇到錯誤則顯示錯誤信息。 5.對生成的逆波蘭式進行計算。 三、實驗預習提示: 1、逆波蘭式定義 將運算對象寫在前面，而把運算符號寫在后面。用這種表示法表示的表達式也稱做后綴式。逆波蘭式的特點在于運算對象順序不變，運算符號位置反映運算順序。采用逆波蘭式可以很好的表示簡單算術(shù)表達式，其優(yōu)點在于易于計算機處理表達式。 2、產(chǎn)生逆波蘭式的前提 中綴算術(shù)表達式 3、逆波蘭

13、式生成的實驗設(shè)計思想及算法  (1)首先構(gòu)造一個運算符棧，此運算符在棧內(nèi)遵循越往棧頂優(yōu)先級越高的原則。 (2)讀入一個用中綴表示的簡單算術(shù)表達式，為方便起見,設(shè)該簡單算術(shù)表達式的右端多加上了優(yōu)先級最低的特殊符號“#”。 (3)從左至右掃描該算術(shù)表達式，從第一個字符開始判斷，如果該字符是數(shù)字，則分析到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。 (4)如果不是數(shù)字，該字符則是運算符，此時需比較優(yōu)先關(guān)系。 做法如下：將該字符與運算符棧頂?shù)倪\算符的優(yōu)先關(guān)系相比較。如果，該字符優(yōu)先關(guān)系高于此運算符棧頂?shù)倪\算符，則將該運算符入棧。倘若不是的話，則將此運算符棧頂?shù)倪\算符從棧中彈出，將該字符入棧。 (5)

14、重復上述操作(1)-(2)直至掃描完整個簡單算術(shù)表達式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡單算術(shù)表達式轉(zhuǎn)化為逆波蘭表示的簡單算術(shù)表達式。 四、逆波蘭式計算的實驗設(shè)計思想及算法  (1)構(gòu)造一個棧，存放運算對象。 (2)讀入一個用逆波蘭式表示的簡單算術(shù)表達式。 (3)自左至右掃描該簡單算術(shù)表達式并判斷該字符，如果該字符是運算對象，則將該字符入棧。若是運算符，如果此運算符是二目運算符，則將對棧頂部的兩個運算對象進行該運算，將運算結(jié)果入棧，并且將執(zhí)行該運算的兩個運算對象從棧頂彈出。如果該字符是一目運算符，則對棧頂部的元素實施該運算，將該棧頂部的元素彈出，將運算結(jié)果入棧。

15、 (4)重復上述操作直至掃描完整個簡單算術(shù)表達式的逆波蘭式，確定所有字符都得到正確處理，我們便可以求出該簡單算術(shù)表達式的值。 五、實驗步驟： （一）準備：  1.閱讀課本有關(guān)章節(jié)， 2.考慮好設(shè)計方案； 3.設(shè)計出模塊結(jié)構(gòu)、測試數(shù)據(jù)，初步編制好程序。 （二）上課上機：  將源代碼拷貝到機上調(diào)試，發(fā)現(xiàn)錯誤，再修改完善。第二次上機調(diào)試通過。 （三）程序要求： 程序輸入/輸出示例：  輸出的格式如下： (1)逆波蘭式的生成及計算程序，編制人：姓名，學號，班級 (2)輸入一以#結(jié)束的中綴表達式(包括+*/（）數(shù)字#)：在此位置輸入符號串如(28+68)*2#  (3)逆波蘭式為：28&68+2*  (4)逆波蘭式28&68+2*計算結(jié)果為192 備注