編譯原理實驗指導.doc

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

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

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

4、字符串為“a+”, 當前字符為“ ”，此時，分析器到底是將其分析為大于關(guān)系運算符還是大于等于關(guān)系運算符呢？顯然，只有知道下一個字符是什么才能下結(jié)論。于是分析器讀入下一個字符“+”，這時可知應將 “ ”解釋為大于運算符。 但此時，超前讀了一個字符 “+”，所以要回退一個字符，詞法分析器才能正常運行。在分析標識符，無符號整數(shù)等時也有類似情況。4. 模塊結(jié)構(gòu)3編譯原理實驗指導書主函數(shù) main（）輸入文件名判斷能否打開文件YN緩沖區(qū)掃描一個字符緩沖區(qū)中是否還有字符N結(jié)束Y調(diào)用取單詞掃描一個字符返回輸出三、實驗過程和指導：（一）準備：1. 閱讀課本有關(guān)章節(jié)，明確語言的語法，寫出基本保留字、標識符、常數(shù)

5、、運算符、分隔符和程序例。2. 初步編制好程序。3. 準備多組測試數(shù)據(jù)。（二）上課上機：將源代碼拷貝到機上調(diào)試，發(fā)現(xiàn)錯誤，再修改完善。第二次上機調(diào)試通過。（三）程序要求：程序輸入 / 輸出示例：4編譯原理實驗指導書如源程序為 C語言。輸入如下一段：main( )int a,b;a = 10;b = a + 20;要求輸出如下圖。（2，” main”）（4，” =”）（5，”（“）（ 3，” 10”）（5，”）“）（5，”; ”）（5，” “）（2，” b”）（ 1，” int ”）（4，” =”）（2，” a”）（2，” a”）（5，”, ”）（4，” +”）（2，” b”）（ 3，” 20”

6、）（5，”; ”）（5，”; ”）（2，” a”）（5，” “）要求：1. 識別保留字： if 、int 、for 、while 、 do、return 、break 、continue ；單詞種別碼為 1。5編譯原理實驗指導書2.其他的都識別為標識符；單詞種別碼為2。3. 常數(shù)為無符號整型數(shù)；單詞種別碼為 3。4. 運算符包括： +、- 、* 、/ 、=、 、 =、=、!= ；單詞種別碼為 4。5. 分隔符包括： , 、; 、 、 、( 、) ； 單詞種別碼為 5。以上為參考，具體可自行增刪。（四）程序思路（僅供參考）：這里以開始定義的 C語言子集的源程序作為詞法分析程序的輸入數(shù)據(jù)。在詞法分

7、析中，自文件頭開始掃描源程序字符，一旦發(fā)現(xiàn)符合“單詞”定義的源程序字符串時，將它翻譯成固定長度的單詞內(nèi)部表示，并查填適當?shù)男畔⒈?。?jīng)過詞法分析后，源程序字符串（源程序的外部表示）被翻譯成具有等長信息的單詞串（源程序的內(nèi)部表示），并產(chǎn)生兩個表格：常數(shù)表和標識符表，它們分別包含了源程序中的所有常數(shù)和所有標識符。0. 定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。1. 初始化：從文件將源程序全部輸入到字符緩沖區(qū)中。2. 取單詞前：去掉多余空白。3. 取單詞后：去掉多余空白。4. 取單詞：讀出單詞的每一個字符，組成單詞，分析類型。（關(guān)鍵是如何判斷取單詞結(jié)束？取到的單詞是什么類型的單詞？）5. 顯示結(jié)果。（五）練

8、習該實驗的目的和思路：程序開始變得復雜起來，可能是大家目前編過的程序中最復雜的，但相對于以后的程序來說還是簡單的。因此要認真把握這個過渡期的練習。6編譯原理實驗指導書本實驗和以后的實驗相關(guān)。通過練習，掌握對字符進行靈活處理的方法。（六）為了能設計好程序，注意以下事情：1. 模塊設計：將程序分成合理的多個模塊（函數(shù)），每個模塊做具體的同一事情。2. 寫出（畫出）設計方案：模塊關(guān)系簡圖、流程圖、全局變量、函數(shù)接口等。3. 編程時注意編程風格：空行的使用、注釋的使用、縮進的使用等。（七）程序框架：#include#includechar program80,token8; /*數(shù)組 program

9、存放的為源程序所有字符，數(shù)組token 為存放的單詞自身字符串*/char ch;int syn,p,m,n,row; /*syn為單詞種別碼 */long int num; /*sum為整型常數(shù) */7編譯原理實驗指導書char *key8= if,int,for,while,do,return,break,continue; /*保留字 */void main( )p=0;row=1;printf(n please input string:n);do/*從文件將源程序全部輸入到字符緩沖區(qū)中*/ch=getchar();programp+=ch;while(ch!=#);p=0;dosca

10、ner( );switch(syn)8編譯原理實驗指導書case 3: printf(n(%d, %d),syn,num);break;case -1: printf(nFOUND ERROR IN ROW %d,row);break;case -2: row=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+;9編譯原理實驗指導書/*分類判斷

11、1.識別標識符（包括保留字） 。建議：關(guān)鍵字作為特殊標識符處理，把它們預先安排在一張表格中（保留字表），當掃描程序識別標識符時，查關(guān)鍵字，否則為一般標識符。注意：識別保留字： if 、int、 for、while 、 do、return、 break、continue；單詞種別碼為 1。其他的都識別為標識符；單詞種別碼為2。2.識別常數(shù)。注意：常數(shù)的有效范圍，如果產(chǎn)生溢出則設置 syn 的值，與主函數(shù)的代碼呼應。 case 3: printf(n(%d, %d),syn,num);break;case -1: printf(nFOUND ERROR IN ROW %d,row);break;常

12、數(shù)為無符號整型數(shù)；單詞種別碼為3。3.識別運算符。注意：區(qū)分兩個運算符 和= 。（switch 語句）運算符包括： +、-、*、/、=、 、=、0ActionA,a=acc是否結(jié)束處理23編譯原理實驗指導書三、實驗過程和指導：（一）準備：1. 閱讀課本有關(guān)章節(jié)，2. 考慮好設計方案；3. 設計出模塊結(jié)構(gòu)、測試數(shù)據(jù)，初步編制好程序。（二）上課上機：將源代碼拷貝到機上調(diào)試，發(fā)現(xiàn)錯誤，再修改完善。（三）程序要求：程序輸入 / 輸出示例：對下列文法，用 LR（1）分析法對任意輸入的符號串進行分析：（ 1）E E+T（ 2）E ET（ 3）T T*F（ 4）T T/F（ 5）F (E)（ 6）F i輸出

13、的格式如下：(1) LR （1）分析程序，編制人：姓名，學號，班級(2) 輸入一以 #結(jié)束的符號串 ( 包括 +*/ （） i#) ：在此位置輸入符號串(3) 輸出過程如下：步驟狀態(tài)棧符號棧剩余輸入串動作10#i+i*i#移進(4) 輸入符號串為非法符號串 ( 或者為合法符號串 )備注：A在“ 所用產(chǎn)生式 ”一列中如果對應有推導則寫出所用產(chǎn)生式；如果為匹配終結(jié)符則寫明匹配的終結(jié)符； 如分析異常出錯則寫為“分析出錯”；若成功結(jié)束則寫為 “分析成功”。B 在此位置輸入符號串為用戶自行輸入的符號串。24編譯原理實驗指導書注意：1. 表達式中允許使用運算符（ +-*/ ）、分割符（括號）、字符 i 、結(jié)束符 #；2. 如果遇到錯誤的表達式，應輸出錯誤提示信息（該信息越詳細越好）；3. 對學有余力的同學， 測試用的表達式事先放在文本文件中， 一行存放一個表達式，同時以分號分割。同時將預期的輸出結(jié)果寫在另一個文本文件中，以便和輸出進行對照；（四）程序思路（僅供參考）：模塊結(jié)構(gòu)：（ 1）定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。（ 2）初始化：設立 LR(1) 分析表、初始化變量空間（包括堆棧、結(jié)構(gòu)體、數(shù)組、臨時變量等）；（ 3）控制部分：從鍵盤輸入一個表達式符號串；（ 4）利用 LR(1) 分析算法進行表達式處理：根據(jù) LR(1) 分析表對表達式符號串進行堆棧（或其他）