編譯原理實(shí)驗(yàn)指導(dǎo)

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

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

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

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

5、（二）上課上機(jī)： 將源代碼拷貝到機(jī)上調(diào)試，發(fā)現(xiàn)錯(cuò)誤，再修改完善。第二次上機(jī)調(diào)試通過。（三）程序要求：程序輸入/輸出示例：如源程序?yàn)镃語言。輸入如下一段：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. 識(shí)別保留字：if、int、for、while、do、retu

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

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

8、）為了能設(shè)計(jì)好程序，注意以下事情：1. 模塊設(shè)計(jì)：將程序分成合理的多個(gè)模塊（函數(shù)），每個(gè)模塊做具體的同一事情。2. 寫出（畫出）設(shè)計(jì)方案：模塊關(guān)系簡(jiǎn)圖、流程圖、全局變量、函數(shù)接口等。3. 編程時(shí)注意編程風(fēng)格：空行的使用、注釋的使用、縮進(jìn)的使用等。 （七）程序框架：#include#includechar program80,token8; /*數(shù)組program存放的為源程序所有字符，數(shù)組token為存放的單詞自身字符串*/char ch;int syn,p,m,n,row; /*syn為單詞種別碼*/long int num; /*sum為整型常數(shù)*/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 /*從文件將源程序全部輸入到字符緩沖區(qū)中*/ 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.識(shí)別標(biāo)識(shí)符（包括保留字）。建議：關(guān)鍵字作為特殊標(biāo)識(shí)符處理，把它們預(yù)先安排在一張表格中（保留字表），當(dāng)掃描程序識(shí)別標(biāo)識(shí)符時(shí)，查關(guān)鍵字，否則為一般標(biāo)識(shí)符。注意：識(shí)別保留字：if、int、for、while、do、return、break、continue；單詞種別

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

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

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