1、編譯原理實驗指導書編譯原理實驗指導書主編：徐靜 李娜 信息與電氣工程學院2010年3月概 述一、本課程實驗的目的和任務 編譯原理是一門實踐性很強的課程，只有通過實踐，才能真正掌握。實際的編譯程序是十分復雜的，有時由多達十幾萬條指令組成。為此，編譯原理的實踐教學，采用簡化編譯過程的辦法，選擇最關鍵的3個環節詞法分析、語法分析（包括語義處理、產生無優化的目標指令）、連接調試，進行編程和調試訓練。每個環節作為一個實踐課題。先分別編程調試，再連接在一起總調。 二、實驗方法 任何一個實用的高級語言，其語法都比較復雜，如選其作為源語言，很難實踐全過程。故本實驗將定義一個簡化的語言 C語言的一個子集作為源語

2、言，設計調試出它的編譯程序。前后貫穿這一條主線進行實踐。每次都可利用課余時間編程，利用上機時間進行輸入和調試。 三、實驗報告的規范和要求 每個實驗完成后寫出實驗報告。實驗報告的內容包括如下內容：一、 實驗目的二、 程序設計時采用的算法和方法三、 輸入的源程序四、 詞法分析程序清單和輸出結果。 五、 心得體會實驗一 詞法分析一、實驗目的： （1）通過設計編制調試一個具體的詞法分析程序，理解詞法分析在編譯程序中的作用。（2）加深對有窮自動機模型的理解。（3）掌握詞法分析程序的實現方法和技術。（4）用C語言對一個簡單語言的子集編制一個一遍掃描的程序，以加深對編譯原理的理解，掌握編譯程序的實現方法和技

3、術。編制一個讀單詞過程，從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、標識符、常數、運算符、分隔符五大類。并依次輸出各個單詞的內部編碼及單詞符號自身值。（遇到錯誤時可顯示“Error”，然后跳過錯誤部分繼續顯示） 。二、實驗預習提示 1. 詞法分析器的功能和輸出格式詞法分析器的功能是輸入源程序，輸出單詞符號。詞法分析器的單詞符號常常表示成以下的二元式（單詞種別碼，單詞符號的屬性值）。本實驗中，采用的是一類符號一種別碼的方式。2. 單詞的BNF表示 | | | + - =3. “超前搜索”方法詞法分析時，常常會用到超前搜索方法。如當前待分析字符串為“a+”,當前字符為“ ”，此時

4、，分析器到底是將其分析為大于關系運算符還是大于等于關系運算符呢？顯然，只有知道下一個字符是什么才能下結論。于是分析器讀入下一個字符“+”，這時可知應將“ ”解釋為大于運算符。但此時，超前讀了一個字符“+”，所以要回退一個字符，詞法分析器才能正常運行。在分析標識符，無符號整數等時也有類似情況。4. 模塊結構YNYN調用返回輸出緩沖區中是否還有字符取單詞掃描一個字符結束主函數main（）輸入文件名判斷能否打開文件緩沖區掃描一個字符三、實驗過程和指導： （一）準備： 1.閱讀課本有關章節，明確語言的語法，寫出基本保留字、標識符、常數、運算符、分隔符和程序例。2.初步編制好程序。3.準備多組測試數據。

5、（二）上課上機： 將源代碼拷貝到機上調試，發現錯誤，再修改完善。第二次上機調試通過。（三）程序要求：程序輸入/輸出示例：如源程序為C語言。輸入如下一段：main( ) int a,b;a = 10; b = a + 20;要求輸出如下圖。（2，”main”）（5，”（“）（5，”）“）（5，”“）（1，”int”）（2，”a”）（5，”,”）（2，”b”）（5，”;”）（2，”a”）（4，”=”）（3，”10”）（5，”;”）（2，”b”）（4，”=”）（2，”a”）（4，”+”）（3，”20”）（5，”;”）（5，”“）要求：1. 識別保留字：if、int、for、while、do、retu

6、rn、break、continue；單詞種別碼為1。2. 其他的都識別為標識符；單詞種別碼為2。3. 常數為無符號整型數；單詞種別碼為3。4. 運算符包括：+、-、*、/、=、=、=、!= ；單詞種別碼為4。5. 分隔符包括：,、;、(、)； 單詞種別碼為5。以上為參考，具體可自行增刪。（四）程序思路（僅供參考）：這里以開始定義的C語言子集的源程序作為詞法分析程序的輸入數據。在詞法分析中，自文件頭開始掃描源程序字符，一旦發現符合“單詞”定義的源程序字符串時，將它翻譯成固定長度的單詞內部表示，并查填適當的信息表。經過詞法分析后，源程序字符串（源程序的外部表示）被翻譯成具有等長信息的單詞串（源程序

7、的內部表示），并產生兩個表格：常數表和標識符表，它們分別包含了源程序中的所有常數和所有標識符。0. 定義部分：定義常量、變量、數據結構。1. 初始化：從文件將源程序全部輸入到字符緩沖區中。2. 取單詞前：去掉多余空白。3. 取單詞后：去掉多余空白。4. 取單詞：讀出單詞的每一個字符，組成單詞，分析類型。（關鍵是如何判斷取單詞結束？取到的單詞是什么類型的單詞？）5. 顯示結果。（五）練習該實驗的目的和思路：程序開始變得復雜起來，可能是大家目前編過的程序中最復雜的，但相對于以后的程序來說還是簡單的。因此要認真把握這個過渡期的練習。本實驗和以后的實驗相關。通過練習，掌握對字符進行靈活處理的方法。（六

8、）為了能設計好程序，注意以下事情：1. 模塊設計：將程序分成合理的多個模塊（函數），每個模塊做具體的同一事情。2. 寫出（畫出）設計方案：模塊關系簡圖、流程圖、全局變量、函數接口等。3. 編程時注意編程風格：空行的使用、注釋的使用、縮進的使用等。 （七）程序框架：#include#includechar program80,token8; /*數組program存放的為源程序所有字符，數組token為存放的單詞自身字符串*/char ch;int syn,p,m,n,row; /*syn為單詞種別碼*/long int num; /*sum為整型常數*/char *key 8= if,int,

9、for,while,do,return,break,continue; /*保留字*/void main( )p=0;row=1;printf(n please input string:n);do /*從文件將源程序全部輸入到字符緩沖區中*/ ch=getchar(); programp+=ch; while(ch!=#); p=0;do scaner( ); switch(syn) case 3: printf(n(%d, %d),syn,num);break; case -1: printf(nFOUND ERROR IN ROW %d,row);break; case -2: row=

10、row+;break; default: printf(n(%d, %s),syn,token);break; while(syn!=0);getch( );scaner( ) for(n=0;n8;n+) tokenn=NULL; m=0; ch=programp+; while(ch= ) ch=programp+; /*分類判斷1.識別標識符（包括保留字）。建議：關鍵字作為特殊標識符處理，把它們預先安排在一張表格中（保留字表），當掃描程序識別標識符時，查關鍵字，否則為一般標識符。注意：識別保留字：if、int、for、while、do、return、break、continue；單詞種別

11、碼為1。其他的都識別為標識符；單詞種別碼為2。2.識別常數。注意：常數的有效范圍，如果產生溢出則設置syn的值，與主函數的代碼呼應。case 3: printf(n(%d, %d),syn,num);break;case -1: printf(nFOUND ERROR IN ROW %d,row);break;常數為無符號整型數；單詞種別碼為3。3.識別運算符。注意：區分兩個運算符和=。 （switch語句）運算符包括：+、-、*、/、=、=、0 ActionA,a=acc把a和s分別壓入符號棧和狀態棧；使ip前進到下一個字符結束處理是是是否否否三、實驗過程和指導： （一）準備： 1.閱讀課本

12、有關章節，2.考慮好設計方案；3.設計出模塊結構、測試數據，初步編制好程序。（二）上課上機： 將源代碼拷貝到機上調試，發現錯誤，再修改完善。（三）程序要求：程序輸入/輸出示例： 對下列文法，用LR（1）分析法對任意輸入的符號串進行分析： （1）EE+T（2）EET（3）TT*F（4）TT/F（5）F(E)（6）Fi輸出的格式如下：(1) LR（1）分析程序，編制人：姓名，學號，班級(2) 輸入一以#結束的符號串(包括+*/（）i#)：在此位置輸入符號串 (3) 輸出過程如下： 步驟狀態棧符號棧剩余輸入串動作10#i+i*i#移進(4) 輸入符號串為非法符號串(或者為合法符號串)備注：A在“所用

13、產生式”一列中如果對應有推導則寫出所用產生式；如果為匹配終結符則寫明匹配的終結符；如分析異常出錯則寫為“分析出錯”；若成功結束則寫為“分析成功”。B 在此位置輸入符號串為用戶自行輸入的符號串。注意：1. 表達式中允許使用運算符（+-*/）、分割符（括號）、字符i、結束符#； 2. 如果遇到錯誤的表達式，應輸出錯誤提示信息（該信息越詳細越好）；3. 對學有余力的同學，測試用的表達式事先放在文本文件中，一行存放一個表達式，同時以分號分割。同時將預期的輸出結果寫在另一個文本文件中，以便和輸出進行對照；（四）程序思路（僅供參考）：模塊結構：（1）定義部分：定義常量、變量、數據結構。（2）初始化：設立LR(1)分析表、初始化變量空間（包括堆棧、結構體、數組、臨時變量等）；（3）控制部分：從鍵盤輸入一個表達式符號串；（4）利用LR(1)分析算法進行表達式處理：根據LR(1)分析表對表達式符號串進行堆棧（或其他）操作，輸出分析結果，