080100190編譯方法實(shí)驗(yàn)指導(dǎo)書

1、編譯方法實(shí)驗(yàn)指導(dǎo)書東北大學(xué)軟件學(xué)院二零零九年九月目 錄前 言2實(shí)驗(yàn)要求3實(shí)驗(yàn)1掃描器設(shè)計(jì)（4學(xué)時(shí)）41.實(shí)驗(yàn)?zāi)康?2.實(shí)驗(yàn)類型43.實(shí)驗(yàn)基本要求44.預(yù)習(xí)內(nèi)容45.實(shí)驗(yàn)基本步驟46.實(shí)驗(yàn)思考題13實(shí)驗(yàn)2中間代碼生成器設(shè)計(jì)（4學(xué)時(shí)）141.實(shí)驗(yàn)?zāi)康?42.實(shí)驗(yàn)類型143.實(shí)驗(yàn)基本要求144.預(yù)習(xí)內(nèi)容145.實(shí)驗(yàn)基本步驟146.實(shí)驗(yàn)思考題16參考資料17前 言編譯方法課程的理論知識(shí)較抽象，但同時(shí)又是一門實(shí)踐性很強(qiáng)的專業(yè)必修課。故本課程的教學(xué)注重理論教學(xué)與實(shí)踐教學(xué)的緊密結(jié)合，讓學(xué)生從上機(jī)實(shí)踐中深入領(lǐng)會(huì)抽象的理論知識(shí)。上機(jī)實(shí)驗(yàn)的目的是：(1) 加深對(duì)講授內(nèi)容的理解，了解編譯程序的基本結(jié)構(gòu)，學(xué)習(xí)并掌握編

2、譯程序的相關(guān)實(shí)現(xiàn)技術(shù)：如設(shè)計(jì)掃描器的自動(dòng)機(jī)、設(shè)計(jì)翻譯及生成Token的算法；設(shè)計(jì)中間代碼生成器，熟悉算術(shù)表達(dá)式的語(yǔ)法分析與中間代碼生成原理。(2) 練習(xí)上機(jī)調(diào)試程序，加強(qiáng)學(xué)生發(fā)現(xiàn)及解決問(wèn)題的能力。實(shí)驗(yàn)要求1實(shí)驗(yàn)時(shí)，按照編譯方法實(shí)驗(yàn)指導(dǎo)書的內(nèi)容完成兩個(gè)必做題目。實(shí)驗(yàn)后，應(yīng)整理出實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告應(yīng)包括以下內(nèi)容：(1) 實(shí)驗(yàn)?zāi)康?2) 實(shí)驗(yàn)內(nèi)容(3) 實(shí)驗(yàn)原理及基本步驟：實(shí)驗(yàn)使用的自動(dòng)機(jī)的設(shè)計(jì)，實(shí)驗(yàn)使用哪種語(yǔ)法分析方法等(4) 數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計(jì)(5) 關(guān)鍵代碼分析（帶注釋）及運(yùn)行結(jié)果(6) 總結(jié)與分析：對(duì)運(yùn)行情況所作的分析，以及本次調(diào)試程序所取得的經(jīng)驗(yàn)。如果程序未能通過(guò)，則應(yīng)分析其原因(7) 實(shí)

3、驗(yàn)思考題2實(shí)驗(yàn)考核標(biāo)準(zhǔn)：(1) 原理分析正確； 10。(2) 數(shù)據(jù)結(jié)構(gòu)及程序總體設(shè)計(jì)正確，并有一定的創(chuàng)新性；30。(3) 程序運(yùn)行結(jié)果正確；20。(4) 上機(jī)報(bào)告書寫認(rèn)真，內(nèi)容完整，有相應(yīng)的實(shí)驗(yàn)分析；20。(5) 實(shí)驗(yàn)過(guò)程中，具有嚴(yán)謹(jǐn)?shù)膶W(xué)習(xí)態(tài)度，認(rèn)真、踏實(shí)、一絲不茍的科學(xué)作風(fēng)；20。實(shí)驗(yàn)1掃描器的設(shè)計(jì)（4學(xué)時(shí)）1.實(shí)驗(yàn)?zāi)康氖煜げ?shí)現(xiàn)一個(gè)掃描器（詞法分析程序）。2.實(shí)驗(yàn)類型設(shè)計(jì)性。3.實(shí)驗(yàn)基本要求(1) 設(shè)計(jì)掃描器的有限自動(dòng)機(jī)（識(shí)別器）；(2) 設(shè)計(jì)翻譯、生成Token的算法（翻譯器）；(3) 編寫代碼并上機(jī)調(diào)試運(yùn)行通過(guò)。·輸入源程序文件或源程序字符串；·輸出相應(yīng)的Token

4、序列；關(guān)鍵字表和界符表；符號(hào)表和常數(shù)表；4.預(yù)習(xí)內(nèi)容(1) 有限自動(dòng)機(jī)原理(2) 詞法分析器原理5.實(shí)驗(yàn)基本步驟掃描器 單詞 Token(1) 有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖 e d d d +|- -1/+/-11+ d . d e d d - -1/+/- l/d -1/+/-12 -1l -13 -1 b b - 14 -1 - 15 -1 -其中：d為數(shù)字，l為字母，b為界符，-1代表其它符號(hào)（如在狀態(tài)8處遇到了非字母或數(shù)字的其它符號(hào)，會(huì)變換到狀態(tài)12）。狀態(tài)轉(zhuǎn)換矩陣：d · E|e +|- l b -1 2 8 9 15 2 3 5 11 11 4 4 5 11 11 7 6 7

5、7 11 11 8 8 12 10 14 131 2 3 4 5 6 7 8 9 10 11 12 13 14 15(2) 關(guān)鍵字表和界符表 Program ; Begin : End ( Var ) While , Do := Repeat + Until - For * To / If > Then >= Else = < <=(3) 數(shù)據(jù)設(shè)計(jì)：狀態(tài)轉(zhuǎn)換矩陣：int aut107= 2, 0, 0, 0, 8, 9, 15, 2, 3, 5,11, 0, 0, 11, 4, 0, 0, 0, 0, 0, 0, 4, 0, 5,11, 0, 0, 11, 7, 0,

6、0, 6, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 7, 0, 0,11, 0, 0, 11, 8, 0, 0, 0, 8, 0, 12, 0, 0, 0, 0, 0, 10, 14,0, 0, 0, 0, 0, 0, 13;關(guān)鍵字表：char keywords3012=“program”,”begin”,”end”,”var”,”while”,”do”, ”repeat”,”until”,”for”,”to”,”if”,”then”,”else”, “;”, ”:”, ”(“, ”)”, ”,”, ”:=”, ”+”, ”-“, ”*”, ”/”,”>”, ”>

7、;=”, ”=”, “<”, “<=”;符號(hào)表：char ID5012; /表中存有源程序中的標(biāo)識(shí)符常數(shù)表：float C20;其它變量： struct token int code; int value; /Token結(jié)構(gòu) struct token tok100; /Token數(shù)組 int s; /當(dāng)前狀態(tài) int n,p,m,e,t; /尾數(shù)值，指數(shù)值，小數(shù)位數(shù)，指數(shù)符號(hào)，類型 float num; /常數(shù)值char w50; /源程序緩沖區(qū)int i; /源程序指針,當(dāng)前字符為wichar strTOKEN12; /當(dāng)前已經(jīng)識(shí)別出的單詞(4) 語(yǔ)義動(dòng)作： ·q1：n

8、=m=p=t=0; e=1; num=0; 其它變量初始化； ·q2：n=10*n+(wi); ·q3：t=1; ·q4：n=10*n+( wi); m+; ·q5：t=1; ·q6：if - then e=-1; ·q7：p=10*p+(wi); ·q8：將wi中的符號(hào)拼接到strTOKEN的尾部； ·q9：將wi中的符號(hào)拼接到strTOKEN的尾部； ·q10：將wi中的符號(hào)拼接到strTOKEN的尾部； /標(biāo)識(shí)符的編碼為1，值為其在常數(shù)表中的位置；常數(shù)的編碼為2，值為其在符號(hào)表中的位置；關(guān)鍵字和界符

9、的編碼為其在關(guān)鍵字表中的位置，值為0。 ·q11：num=n*10e*p-m; /計(jì)算常數(shù)值ti.code=2; ti.value=InsertConst(num); /生成常數(shù)Token ·q12：code=Reserve(strTOKEN); /查關(guān)鍵字表 if code then ti.code=code; ti.value=0; /生成關(guān)鍵字Tokenelse ti.code=1; ti.value=InsertID(strTOKEN); /生成標(biāo)識(shí)符Token ·q13：code=Reserve(strTOKEN); /查界符表 if code then

10、 ti.code=code; ti.value=0; /生成界符Tokenelse strTOKENstrlen(strTOKEN)-1=0; /單界符源程序緩沖區(qū)指針減1； code=Reserve(strTOKEN); /查界符表 ti.code=code; ti.value=0; /生成界符Token ·q14：code=Reserve(strTOKEN); /查界符表 ti.code=code; ti.value=0; /生成界符Token ·q15：stop.(5) 查狀態(tài)變換表int find(int s,char ch) /s是當(dāng)前狀態(tài)，ch是當(dāng)前字符，返回值

11、是轉(zhuǎn)換后狀態(tài)查狀態(tài)轉(zhuǎn)換矩陣aut107；返回新狀態(tài)；(6) 主程序流程：初始化；打開用戶源程序文件； while （文件未結(jié)束） 讀入一行到wi，i=0;do /處理一行，每次處理一個(gè)單詞 濾空格，直到第一個(gè)非空的wi；i-；s=1; /處理一個(gè)單詞開始while （s!=0） /拼單詞并生成相應(yīng)Token act(s); /執(zhí)行qs if （s>=11 && s<=14） /一個(gè)單詞處理結(jié)束 break; i+; /getchar() s=find(s, wi);if （s=0） 詞法錯(cuò)誤； while （wi!=換行符）；關(guān)閉用戶源程序文件；生成Token文件；

12、輸出關(guān)鍵字表；輸出Token序列；輸出符號(hào)表；輸出常數(shù)表；(6) 參考程序/ scan.cpp : Defines the entry point for the console application.#include "string.h"#include "math.h"char keywords3012="program","begin","end","var","while","do","repeat",&q

13、uot;until","for","to","if","then","else","", ":", "(", ")", ",", ":=", "+", "-", "*", "/", ">", ">=", "=", &q

14、uot;<", "<="int num_key=28;int aut118= 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 8, 9,15, 0, 2, 3, 5,11, 0, 0,11, 0, 4, 0, 0, 0, 0, 0, 0, 0, 4, 0, 5,11, 0, 0,11, 0, 7, 0, 0, 6, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0,11, 0, 0,11, 0, 8, 0, 0, 0, 8, 0,12, 0, 0, 0, 0, 0, 0,10,14,

15、0, 0, 0, 0, 0, 0, 0,13;char ID5012;int C20;int num_ID=0,num_C=0;struct token int code; int value; /Token結(jié)構(gòu)struct token tok100; /Token數(shù)組int i_token=0,num_token=0; /Token計(jì)數(shù)器和Token個(gè)數(shù)char strTOKEN15; /當(dāng)前單詞int i_str; /當(dāng)前單詞指針int n,p,m,e,t; /尾數(shù)值，指數(shù)值，小數(shù)位數(shù)，指數(shù)符號(hào)，類型double num; /常數(shù)值char w50; /源程序緩沖區(qū)int i; /源程序緩

16、沖區(qū)指針,當(dāng)前字符為wistruct map /當(dāng)前字符到狀態(tài)轉(zhuǎn)換矩陣列標(biāo)記的映射char str50;int col;struct map col14="0123456789",1,".",2,"Ee",3,"+-",4; /數(shù)字struct map col22="abcdefghijklmnopqrstuvwxyz",5,"0123456789",1; /關(guān)鍵字或標(biāo)識(shí)符struct map col31=":(),+-*/=><",6; /界

17、符struct map *ptr;int num_map;void act(int s);int find(int s,char ch);int InsertConst(double num);int Reserve(char *str);int InsertID(char *str);int main(int argc, char* argv) FILE *fp; int s; /當(dāng)前狀態(tài)fp=fopen("exa.txt","r"); while (!feof(fp) fgets(w,50,fp); i=0;dowhile (wi=' 

18、9;) /濾空格i+;if (wi>='a' && wi<='z') /判定單詞類別ptr=col2; num_map=2;else if (wi>='0' && wi<='9')ptr=col1; num_map=4;else if (strchr(col30.str,wi)=NULL)printf("非法字符%cn",wi);i+;continue;elseptr=col3; num_map=1;i-;s=1; /開始處理一個(gè)單詞while (s!=0

19、) act(s); if (s>=11 && s<=14)break; i+; /getchar() s=find(s,wi);if (s=0)strTOKENi_str='0'printf("詞法錯(cuò)誤：%sn",strTOKEN); while (wi!=10); printf("關(guān)鍵字表："); /輸出結(jié)果for (i=0;i<30;i+)printf("%s ",keywordsi);printf("n"); printf("Token序列：&quo

20、t;);for (i=0;i<num_token;i+)printf("(%d,%d)",toki.code,toki.value);printf("n");printf("符號(hào)表：");for (i=0;i<num_ID;i+)printf("%s ",IDi);printf("n");printf("常數(shù)表：");for (i=0;i<num_C;i+)printf("%d ",Ci);printf("n");fc

21、lose(fp);printf("Hello World!n");return 0;void act(int s)int code;switch (s)case 1:n=0;m=0;p=0;t=0;e=1;num=0;i_str=0; strTOKENi_str='0' /其它變量初始化 break; case 2:n=10*n+wi-48; break; case 3:t=1; break; case 4:n=10*n+wi-48; m+; break; case 5:t=1; break; case 6:if (wi='-') e=-1;

22、 break; case 7:p=10*p+wi-48; break; case 8:strTOKENi_str+=wi; /將ch中的符號(hào)拼接到strTOKEN的尾部； break; case 9:strTOKENi_str+=wi; /將ch中的符號(hào)拼接到strTOKEN的尾部； break;case 10:strTOKENi_str+=wi; /將ch中的符號(hào)拼接到strTOKEN的尾部； break; case 11:num=n*pow(10,e*p-m); /計(jì)算常數(shù)值 toki_token.code=2; toki_token+.value=InsertConst(num); /生

23、成常數(shù)Token num_token+;break;case 12:strTOKENi_str='0' code=Reserve(strTOKEN); /查關(guān)鍵字表 if (code) toki_token.code=code; toki_token+.value=0; /生成關(guān)鍵字Tokenelse toki_token.code=1; toki_token+.value=InsertID(strTOKEN); /生成標(biāo)識(shí)符Token num_token+;break; case 13:strTOKENi_str='0' code=Reserve(strTOK

24、EN); /查界符表 if (code) toki_token.code=code; toki_token+.value=0; /生成界符Token else strTOKENstrlen(strTOKEN)-1='0' /單界符 i-; code=Reserve(strTOKEN); /查界符表 toki_token.code=code; toki_token+.value=0; /生成界符Tokennum_token+;break; case 14:strTOKENi_str='0' code=Reserve(strTOKEN); /查界符表 toki_to

25、ken.code=code; toki_token+.value=0; /生成界符Tokennum_token+;break;int find(int s,char ch)int i,col=7; struct map *p;p=ptr;for (i=0;i<num_map;i+)if (strchr(p+i)->str,ch)col=(p+i)->col;break;return autscol;int InsertConst(double num)int i;for (i=0;i<num_C;i+)if (num=Ci)return i;Ci=num;num_C+;

26、return i;int Reserve(char *str)int i;for (i=0;i<num_key;i+)if (!strcmp(keywordsi,str)return (i+3);return 0;int InsertID(char *str)int i; for (i=0;i<num_ID;i+)if (!strcmp(IDi,str)return i;strcpy(IDi,str);num_ID+;return i;6.實(shí)驗(yàn)思考題(1) 掃描器的任務(wù)是什么？(2) 掃描器、識(shí)別器、翻譯器三者之間的關(guān)系是怎樣的？(3) 為什么說(shuō)有限自動(dòng)機(jī)是詞法分析的基礎(chǔ)？實(shí)驗(yàn)2中

27、間代碼生成器的設(shè)計(jì)（4學(xué)時(shí)）1.實(shí)驗(yàn)?zāi)康氖煜に阈g(shù)表達(dá)式的語(yǔ)法分析與中間代碼生成原理。2.實(shí)驗(yàn)類型綜合性。3.實(shí)驗(yàn)基本要求(1) 設(shè)計(jì)語(yǔ)法制導(dǎo)翻譯生成表達(dá)式的四元式的算法；(2) 編寫代碼并上機(jī)調(diào)試運(yùn)行通過(guò)。·輸入算術(shù)表達(dá)式·輸出語(yǔ)法分析結(jié)果相應(yīng)的四元式序列(3) 本實(shí)驗(yàn)已給出遞歸子程序法的四元式屬性翻譯文法的設(shè)計(jì)，鼓勵(lì)學(xué)生在此基礎(chǔ)上進(jìn)行創(chuàng)新，即設(shè)計(jì)LL(1)分析法或LR(0)分析法的屬性翻譯文法，并根據(jù)這些屬性翻譯文法，使用擴(kuò)展的語(yǔ)法分析器實(shí)現(xiàn)語(yǔ)法制導(dǎo)翻譯。4.預(yù)習(xí)內(nèi)容(1) 形式語(yǔ)言基礎(chǔ)及其文法運(yùn)算 (2) 語(yǔ)法分析原理以及3種常用的語(yǔ)法分析方法(3) 語(yǔ)義分析原理5.實(shí)驗(yàn)基本步驟(1) 算術(shù)表達(dá)式文法 G(E)： E à E 0 T | T T à T 1 F | FF à i | (E)(2) 文法變換G(E) E