編譯方法實(shí)驗(yàn)指導(dǎo)書(8學(xué)時(shí)

1、E-TG-FSG-iSG-i/FSG-i/iSG-i/iG-i/i-TG-i/i-FSG-i/i-iSG-i/i-iG-i/i-i編譯原理實(shí)驗(yàn)課程教學(xué)大綱1實(shí)驗(yàn)課程名稱：編譯原理實(shí)驗(yàn)2實(shí)驗(yàn)課程名稱（英文）： Compiling Method3課程代碼：4實(shí)驗(yàn)課程性質(zhì)：非獨(dú)立設(shè)課5學(xué) 時(shí)：86學(xué) 分：37適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 8先修或同修課程：離散數(shù)學(xué),數(shù)據(jù)結(jié)構(gòu),高級(jí)語言程序設(shè)計(jì)等9開課單位：信息與計(jì)算機(jī)工程學(xué)院10制定實(shí)驗(yàn)教學(xué)大綱的依據(jù)：東北林業(yè)大學(xué)編譯方法教學(xué)大綱。11本實(shí)驗(yàn)課在培養(yǎng)實(shí)驗(yàn)?zāi)芰χ械牡匚患白饔猛ㄟ^本實(shí)驗(yàn)課程培養(yǎng)學(xué)生以下幾方面的能力：加深學(xué)生對(duì)編譯方法所涉及的概念、算法、理論

2、的理解；體驗(yàn)編譯方法所涉及的抽象思維的具體實(shí)現(xiàn)； 激勵(lì)學(xué)生在編譯方法設(shè)計(jì)方面的創(chuàng)新精神；培養(yǎng)正規(guī)系統(tǒng)程序設(shè)計(jì)的能力；12應(yīng)達(dá)到的實(shí)驗(yàn)?zāi)芰?biāo)準(zhǔn)本課程的實(shí)驗(yàn)主要培養(yǎng)學(xué)生的抽象思維能力和正規(guī)的程序設(shè)計(jì)能力，加強(qiáng)對(duì)編譯方法基本原理、基本概念的理解，使學(xué)生初步具備將算法或理論轉(zhuǎn)化為正確程序的能力。13實(shí)驗(yàn)內(nèi)容(1) 實(shí)驗(yàn)一詞法分析實(shí)驗(yàn)?zāi)康模?編制一個(gè)類c語言的詞法分析程序。 實(shí)驗(yàn)要求：畫好類c語言的有窮狀態(tài)自動(dòng)機(jī)。在進(jìn)行本實(shí)驗(yàn)之前，應(yīng)熟練課程內(nèi)容，在上機(jī)之前做好實(shí)驗(yàn)計(jì)劃，編寫好相應(yīng)的代碼實(shí)驗(yàn)內(nèi)容：根據(jù)有窮狀態(tài)自動(dòng)機(jī)編制一個(gè)類c語言的掃描程序。 (2)實(shí)驗(yàn)二 語法分析 實(shí)驗(yàn)?zāi)康模壕帉懸粋€(gè)類c語言的語法分析

3、程序?qū)嶒?yàn)要求：閱讀課本有關(guān)章節(jié)，花一周時(shí)間確定語法部分的文法，設(shè)計(jì)出LL(1)分析表；考慮好設(shè)計(jì)方案；設(shè)計(jì)出模塊結(jié)構(gòu)、測(cè)試數(shù)據(jù)，初步編制好程序。實(shí)驗(yàn)內(nèi)容：根據(jù)LL(1)分析表和文法編制類c語言的語法分析程序?qū)嶒?yàn)指導(dǎo)書(1) 實(shí)驗(yàn)一詞法分析實(shí)驗(yàn)?zāi)康模壕幹埔粋€(gè)類c語言的詞法分析程序。 一、 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)?zāi)康模航⒁粋€(gè)詞法分析器，其功能是輸入一段源程序，經(jīng)過處理后，按程序順序并以二元式輸出單詞符號(hào)（即程序語言的語法單位），并且，如果該單詞是關(guān)鍵字或符號(hào)（包括界符和運(yùn)算符），則在相應(yīng)的關(guān)鍵字表或符號(hào)表中找出其位置；如果該單詞是關(guān)鍵字或常數(shù)，則直接輸出。 二、 程序設(shè)計(jì)原理與方法程序設(shè)計(jì)原理： 根據(jù)各個(gè)

4、單詞的狀態(tài)轉(zhuǎn)換圖，可以進(jìn)行合成，給出能夠識(shí)別Simple-C語言中各類單詞的DFA，如圖2-8所示。三、 示例程序 #include stdio.h#include string.h/狀態(tài)名表typedef enum S_state, A_state, B_state, C_state, D_state, E_state, F_state, G_state, H_state, I_state, J_state, K_state, L_state, M_state, N_state, O_state, P_state, Q_state, R_state, T_state, U_state, V_

5、state, W_state, X_state, Y_state, Z_state, END_state STATE;/單詞類別標(biāo)識(shí)typedef enum KEY_WORD = 0, IDENTIFIER, UNSINED_INT, REAL_CONST, SINGLE_DELIMITER, COMMENT, DIVISION_SIGN, ADDSELF_OPERATOR, ADD_OPERATOR, SUBTRACTIONSELF_OPERATOR, SUBTRACTION_OPERATOR, DOUBLERELATIONAL_OPERATOR, SINGLERELATIONAL_OPER

6、ATOR, ERROR, CHAR_CONST, STRING_CONST , NONE WORDTYPE;/單詞類別名稱char WordTypeExplanation30 = 關(guān)鍵字, 標(biāo)識(shí)符, 無符號(hào)整數(shù) ,實(shí)型常量 ,單界限符, 注釋, 除號(hào), 自增運(yùn)算符 , 加法運(yùn)算符, 自減運(yùn)算符, 減法運(yùn)算符或取負(fù)運(yùn)算符, 雙界限關(guān)系運(yùn)算符 ,單界限關(guān)系運(yùn)算符, 出錯(cuò), 字符常量, 字符串常量 , 無可處理字符 ;#define KEYWORD_COUNT 18#define KEYWORD_MAXLENGTH 20 /關(guān)鍵字表 編號(hào)由位置隱含char KeyWordTableKEYWORD_C

7、OUNTKEYWORD_MAXLENGTH = break, case, char ,continue ,default, do, double, else , float, for , if, int, return, struct , switch ,unsigned ,void, while ;/* GetWordType判斷是關(guān)鍵字還是自定義標(biāo)識(shí)符 參數(shù)：char* str 待判斷標(biāo)識(shí)符 返回值：KEY_WORD 關(guān)鍵字 IDENTIFIER 自定義標(biāo)識(shí)符*/WORDTYPE GetWordType(char* str) int i=0; for(i = 0;i KEYWORD_COU

8、NT ; i+) if(strcmp(str, KeyWordTablei) =0 ) break; /*查找關(guān)鍵字表,此處可用折半查找提高效率*/ if(i = A & ch= a & ch= 0 & ch) return 17; else if(ch = = strlength ) state = Z_state; break; ch_type = GetCharactorType(straddrcur_pos); /*取得當(dāng)前字符類別*/ switch(ch_type) case 1: /*字母*/case 3: /*下劃線*/case 4: /*字母e或E*/ state = A_st

9、ate;tmpstrcur_pos- *pcurpos = straddrcur_pos; /*記錄當(dāng)前字符,用以在B狀態(tài)判斷是標(biāo)識(shí)符還是關(guān)鍵字*/ break;case 2: /*數(shù)字*/ state = C_state;break;case 6:/*星號(hào)*/case 7:/*百分號(hào)*/ case 9:/*分號(hào)*/case 10:/*左方括號(hào)*/case 11:/*右方括號(hào)*/case 12:/*逗號(hào)*/case 13:/*空格*/case 22:/*左括號(hào)*/case 23:/*右括號(hào)*/ case 24: /*左大括號(hào)*/case 25: /*右大括號(hào)*/ state = L_state

10、; break; case 8: /*斜線*/ state = M_state; break; case 14: /*加號(hào)*/ state = Q_state; break;case 15: /*減號(hào)*/ state = R_state; break;case 16: /*等號(hào)*/case 17: /*大于號(hào)*/case 18: /*小于號(hào)*/ state = T_state; break;case 19: /*嘆號(hào)*/ state = U_state; break; case 20: /*單引號(hào)*/ state = V_state; break;case 21: /*雙引號(hào)*/ state

11、= X_state; break; default: /* 其它字符 */ state = Z_state; break; cur_pos +; break; case A_state: if(cur_pos = strlength ) state = B_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 1 | ch_type = 2 | ch_type = 3 | ch_type = 4) state = A_state; tmpstrcur_pos- *pcurpos = straddrcur_p

12、os; /*記錄當(dāng)前字符,用以在B狀態(tài)判斷是標(biāo)識(shí)符還是關(guān)鍵字*/ cur_pos +; else state = B_state; break; case B_state: wordtype = GetWordType(tmpstr); /*判斷是關(guān)鍵字還是標(biāo)識(shí)符*/ state = END_state; break; /*A_state - B_state 處理關(guān)鍵字和標(biāo)識(shí)符 */ case C_state: if(cur_pos = strlength ) state = D_state; break; ch_type = GetCharactorType(straddrcur_pos);

13、 if(ch_type = 2) /*數(shù)字*/ cur_pos +; state = C_state; else if(ch_type = 4) /* e或E */ cur_pos +; state = H_state; else state = D_state; break; break; case D_state: if(cur_pos = strlength ) /*所有字符處理完畢*/ wordtype = UNSINED_INT; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos);/*此句可以省略

14、*/ if(ch_type = 5)/*小數(shù)點(diǎn)*/ cur_pos +; state = F_state; else /*其它字符*/ wordtype = UNSINED_INT; state = END_state; break; case F_state: if(cur_pos = strlength ) /*所有字符處理完畢*/ wordtype = ERROR; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 2)/*數(shù)字*/ cur_pos +; state = G

15、_state; else /*其它字符*/ wordtype = ERROR; state = END_state; break; case G_state: if(cur_pos = strlength ) /*所有字符處理完畢*/ wordtype = REAL_CONST ; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 2 ) /*數(shù)字*/ cur_pos +; state = G_state; else if(ch_type = 4) /*E 或 e*/ cur_p

16、os +; state = H_state; else wordtype = REAL_CONST ; state = END_state; break; case H_state: /*處理科學(xué)記數(shù)法表示的實(shí)數(shù)中 e或E后面的部分 */ if(cur_pos = strlength ) /*所有字符處理完畢, e后面沒有字符*/ wordtype = ERROR; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 2 ) /*數(shù)字*/ cur_pos +; state = J_

17、state; else if(ch_type = 14 | ch_type = 15 ) /* + 或 - */ cur_pos +; state = I_state; else /* 3.4e 或 3e 后面不是數(shù)字也不是正負(fù)號(hào) */ wordtype = ERROR; state = END_state; break; case I_state: if(cur_pos = strlength ) /*所有字符處理完畢, e+-后面沒有字符*/ wordtype = ERROR; state = END_state; break; ch_type = GetCharactorType(str

18、addrcur_pos); if(ch_type = 2 ) /*數(shù)字*/ cur_pos +; state = J_state; else /* e+-后面不是數(shù)字*/ wordtype = ERROR; state = END_state; break; case J_state: if(cur_pos = strlength ) /*所有字符處理完畢,是實(shí)常數(shù)*/ wordtype = REAL_CONST; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 2 ) /*數(shù)

19、字*/ cur_pos +; state = J_state; else /* 是實(shí)常數(shù)*/ wordtype = REAL_CONST; state = END_state; break; /*C_state - J_state 數(shù)字（包括 正整數(shù) 實(shí)數(shù) 科學(xué)記數(shù)的實(shí)數(shù)）*/ case L_state: wordtype = SINGLE_DELIMITER; state = END_state; break; case M_state: if(cur_pos = strlength ) /*所有字符處理完畢,是除號(hào)*/ wordtype = DIVISION_SIGN; state = E

20、ND_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 6 ) /*星號(hào)*/ cur_pos +; state = N_state; else /*是除號(hào) */ wordtype = DIVISION_SIGN; state = END_state; break; case N_state: if(cur_pos = strlength ) /*所有字符處理完畢, ,注釋不完整*/ wordtype = ERROR; state = END_state; break; ch_type = GetChar

21、actorType(straddrcur_pos); if(ch_type != 6 ) /*不是星號(hào)*/ cur_pos +; state = N_state; else /*是星號(hào) */ cur_pos +; state =O_state; break; case O_state: if(cur_pos = strlength ) /*所有字符處理完畢,注釋不完整*/ wordtype = ERROR; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type != 8 ) /*不是斜線

22、*/ cur_pos +; state = N_state; else /*是斜線 */ cur_pos +; wordtype = COMMENT; state = END_state; break; /* 注釋和除號(hào)處理完畢*/ case Q_state: if(cur_pos = strlength ) /*所有字符處理完畢，是加號(hào) */ wordtype = ADD_OPERATOR; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 14 ) /* 自增+ */ cur

23、_pos +; wordtype = ADDSELF_OPERATOR; state = END_state; else /*是加號(hào) */ wordtype = ADD_OPERATOR; state = END_state; break; /*加號(hào)和自增處理完畢*/ case R_state: if(cur_pos = strlength ) /*所有字符處理完畢，是減號(hào) */ wordtype = SUBTRACTION_OPERATOR; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch

24、_type = 15 ) /* 自減- */ cur_pos +; wordtype = SUBTRACTIONSELF_OPERATOR; state = END_state; else /*是減號(hào) */ wordtype = SUBTRACTION_OPERATOR; state = END_state; break; /*減號(hào)和自減處理完畢*/ case T_state: if(cur_pos = strlength ) /*所有字符處理完畢，是 關(guān)系單界運(yùn)算符 */ wordtype = SINGLERELATIONAL_OPERATOR; state = END_state; bre

25、ak; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 16 ) /* 關(guān)系雙界運(yùn)算符 = = = strlength ) /*所有字符處理完畢，出錯(cuò) */ wordtype = ERROR; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 16 ) /* 關(guān)系雙界運(yùn)算符 ！= */ cur_pos +; wordtype = DOUBLERELATIONAL_OPERATOR ; state = END_sta

26、te; else /* 出錯(cuò) */ wordtype = ERROR; state = END_state; break; /* 關(guān)系 單雙 界運(yùn)算符處理完畢*/ case V_state: if(cur_pos = strlength ) /*所有字符處理完畢，字符常量缺少右邊的單引號(hào) */ wordtype = ERROR; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 20 ) /* 兩個(gè)單引號(hào)中間沒有字符，出錯(cuò) */ cur_pos +; wordtype = ERR

27、OR; state = END_state; else /* 其它字符 */ cur_pos +; state = W_state; break; case W_state: if(cur_pos = strlength ) /*所有字符處理完畢，字符常量缺少右邊的單引號(hào) */ wordtype = ERROR; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 20 ) /* 字符型常量 */ cur_pos +; wordtype = CHAR_CONST; state =

28、END_state; else /* 出錯(cuò)，字符型常量中只能有一個(gè)字符 */ wordtype = ERROR; state = END_state; break; /* 字符型常量 處理完畢*/ case X_state: if(cur_pos = strlength ) /*所有字符處理完畢，字符串常量缺少右邊的雙引號(hào) */ wordtype = ERROR; state = END_state; break; ch_type = GetCharactorType(straddrcur_pos); if(ch_type = 21 ) /* 字符串型常量 */ cur_pos +; word

29、type = STRING_CONST; state = END_state; else /* 其它字符 */ cur_pos +; state = X_state; break; /* 字符串型常量 處理完畢*/ case Z_state: default: wordtype = ERROR; state = END_state; break; *pcurpos = cur_pos ; /* 修改當(dāng)前行待處理位置游標(biāo)變量的值 */ return wordtype; int main() char teststr80 = 0; char outstr256 = 0; int i=0; int

30、curpos = 0 , start = 0; WORDTYPE wordtype; int strlength = 0; puts(Input a program line to test please: ); gets(teststr); strlength = (int)strlen(teststr); while(curpos strlength) start = curpos; memset(outstr, 0 , sizeof(char)*256); wordtype = RecogniteWordByDFA(teststr ,strlength , &curpos ); for(

31、i = start;icurpos; i+)outstri-start = teststri; printf(%s: %s)n, outstr , WordTypeExplanationwordtype); getchar(); return 0;四、總結(jié)在上述程序中，主要是實(shí)現(xiàn)了把源文件的關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、符號(hào)分離開的功能。并附帶了簡(jiǎn)單的錯(cuò)誤處理過程。 (2) 實(shí)驗(yàn)二 語法分析1、實(shí)驗(yàn)?zāi)康模簩?duì)Simple-C語言進(jìn)行LL(1)分析的實(shí)現(xiàn)過程及方法。 2、實(shí)驗(yàn)內(nèi)容：編能夠根據(jù)文法及LL(1)分析表生成語法分析程序。1）文法：Program：=ProgramHead FunctionDecl

32、are VarDifine FunctionGroup （2） | FunctionDeclare VarDifine FunctionGroup（3） | ProgramHead VarDifine FunctionGroup（4） | ProgramHead FunctionDeclare FunctionGroup（5） | ProgramHead FunctionGroup（6） | FunctionDeclare FunctionGroup（7） | VarDifine FunctionGroup（8） | FunctionGroup程序頭：（9）ProgramHead ：= # i

33、ncludeLibFileName.h ProgramHead（10）LibFileName ：=stdio（11） |math（12） |string（13） |ctype函數(shù)聲明與全局變量定義：（14）FunctionDeclare ：= BaseType FunctionName(ForParList) FunctionDeclareMore（15） | struct StrTypeName FunctionName(ForParList) FunctionDeclareMore（16） | void StrTypeName FunctionName(ForParList) Functi

34、onDeclareMore（17）FunctionDeclareMore ：=; FunctionDeclare（18） |（19）VarDifine ：= ExpSentence（20）FunctionName ：= Id函數(shù)組： （21）FunctionGroup ：= UnMainFunction MainFunction UnMainFunction（22）UnMainFunction ：=FunctionHead FunctionBody（23） |（24）FunctionHead ：= BaseType FunctionName(ForParList)（25） | void Fun

35、ctionName(ForParList)（26） | struct StrTypeName FunctionName(ForParList)（27）FunctionBody ：=ExpSentence ExecSentence（28）MainFunction ：= MainFunctionHead FunctionBody（29）MainFunctionHead ：= void main()類型：（30）BaseType ：=int（31） |char（32） |float(33) |double（34）OneArrayType ：= BaseType ArrayNameDimlong （35）TwoArrayType ：= BaseType ArrayNameDimlong Dimlong（36）ArrayName ：=Id（37）Dimlong ：=Intc（38）StructureType ：=struct StrTypeName StructureBody（39）StrTypeName ：= Id（40）StructureBody ：= MembersList （41）MembersList ：=BaseType IdList; MembersListMore（42） |OneArrayType; MembersListMo