編譯技術課程設計報告

編譯技術課程設計班 級 計算機0802 學 號 姓 名 龔 科 指導老師 朱 玉 全 二零一一年 七 月一、目的是理論與實踐并重的課程，而其實驗課要綜合運用一、二年級所學的多門課程的內容，用來完成一個小型編譯程序。從而鞏固和加強對詞法分析、語法分析、語義分析、代碼生成和報錯處理等理論的認識和理解；培養(yǎng)學生對完整系統(tǒng)的獨立分析和設計的能力，進一步培養(yǎng)學生的獨立編程能力。二、任務及要求基本要求：1 詞法分析器 產生下述小語言的單詞序列這個小語言的所有的單詞符號，以及它們的種別編碼和內部值如下表： 單詞符號種別編碼助記符內碼值DIMIFDOSTOPEND標識符常數(shù)（整）=+*，（）1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR-內部字符串標準二進形式-對于這個小語言，有幾點重要的限制：首先，所有的關鍵字（如IFWHILE等）都是“保留字”。所謂的保留字的意思是，用戶不得使用它們作為自己定義的標示符。例如，下面的寫法是絕對禁止的： IF（5）=x 其次，由于把關鍵字作為保留字，故可以把關鍵字作為一類特殊標示符來處理。也就是說，對于關鍵字不專設對應的轉換圖。但把它們（及其種別編碼）預先安排在一張表格中（此表叫作保留字表）。當轉換圖識別出一個標識符時，就去查對這張表，確定它是否為一個關鍵字。再次，如果關鍵字、標識符和常數(shù)之間沒有確定的運算符或界符作間隔，則必須至少用一個空白符作間隔（此時，空白符不再是完全沒有意義的了）。例如，一個條件語句應寫為 IF i0 i= 1;而絕對不要寫成 IFi0 i=1;因為對于后者，我們的分析器將無條件地將IFI看成一個標識符。這個小語言的單詞符號的狀態(tài)轉換圖，如下圖： 2 語法分析器 能識別由加+ 減- 乘* 除/ 乘方 括號（）操作數(shù)所組成的算術表達式，其文法如下：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i 使用的算法可以是：預測分析法；遞歸下降分析法；算符優(yōu)先分析法；LR分析法等。3 中間代碼生成器 產生上述算術表達式的中間代碼（四元式序列）較高要求：1 擴充上述小語言的單詞；2 增加語法分析器的功能，能識別條件語句和循環(huán)語句等；3 增加中間代碼生成器的功能，能產生條件語句和循環(huán)語句等的中間代碼（四元式序列）4 增加報錯功能；5 將中間代碼翻譯成匯編語言。三、實現(xiàn)過程說明數(shù)據(jù)定義清單：#define ACC -2/*種別編碼*/#define sy_if 0#define sy_then 1#define sy_else 2#define sy_while 3#define sy_begin 4#define sy_do 5#define sy_end 6#define a 7#define semicolon 8#define e 9#define jinghao 10#define S 11#define L 12#define tempsy 15#define EA 18 /*E and*/#define E0 19 /*E or*/#define plus 34#define times 36#define becomes 38#define op_and 39#define op_or 40#define op_not 41#define rop 42#define lparent 48#define rparent 49#define ident 56#define intconst 57#define minus 58#define div 59#define chengfang 60/*/char ch=0;/*從字符緩沖區(qū)讀取當前字符*/int count=0;/*詞法分析結果緩沖區(qū)計數(shù)器*/static char spelling10=;/*存放識別的字*/static char line81=;/*一行字符緩沖區(qū)，最多80個字符*/char *pline;/*字符緩沖區(qū)指針*/static char ntab110010;/*變量名表，共100項，每項長度10*/struct ntabint tc;/*真值*/int fc;/*假值*/ntab2200;/*在布爾表達式E中保存有關布爾變量的真、假值*/int label=0;/*指向ntab2的指針*/struct rwords/*存放臨時變量的表的定義*/char sp10;int sy;/*（保留字表）匹配表的結構，用來與輸入緩沖區(qū)中的單詞進行匹配*/*匹配表初始化，大小為10*/struct rwords reswords10=if,sy_if, do,sy_do,else,sy_else,while,sy_while,then,sy_then,begin,sy_begin,end,sy_end,and,op_and,or,op_or,not,op_not;struct aaint sy1;/*存放名字*/int pos;/*存放名字所對應的地址*/buf1000,/*詞法分析結果緩沖區(qū)*/n,/*讀取二元式的當前字符*/n1,/*當前表達式中的字符*/E,/*非終結符*/sstack100,/*算術或布爾表達式加工處理使用的符號棧*/ibuf100, /*算術或布爾表達式使用的緩沖區(qū)*/stack1000;/*語法分析加工處理使用的符號棧*/struct aa oth;/*四元式中空白位置*/struct fourexpchar op10;struct aa arg1;struct aa arg2;int result;fexp200;/*四元式的結構定義*/int ssp=0;/*指向sstack棧指針*/struct aa *pbuf=buf;/*指向詞法分析緩沖區(qū)的指針*/int nlength=0;/*詞法分析中記錄單詞的長度*/int lnum=0;/*源程序行數(shù)記數(shù)，源程序長度*/int tt1=0;/*變量名表指針*/FILE *cfile;/*源程序文件，為結束符*/int newt=0;/*臨時變量計數(shù)器*/int nxq=100;/*nxq指向下一個形成的四元式的地址*/ /*每次執(zhí)行gen（）時，地址自動增1*/int lr; /*掃描LR分析表1過程中保存的當前狀態(tài)值*/int lr1; /*掃描LR分析表2或表3所保存的當前狀態(tài)值*/int sp=0; /*查找LR分析表時狀態(tài)棧的棧頂指針*/int stack1100;/*狀態(tài)棧1的定義*/int sp1=0;/*狀態(tài)棧1的棧頂指針*/int num=0;/*算術或布爾表達式緩沖區(qū)指針*/struct llint nxq1;/*記錄下一條四元式的地址*/int tc1; /*真值鏈*/int fc1; /*假值鏈*/labelmark10; /*記錄語句嵌套層次的數(shù)組，*/ /*即記錄嵌套中每層的布爾表達式E的首地址*/int labeltemp10;/*記錄語句嵌套層次的數(shù)組，*/ /*即記錄每層else之前的四元式地址*/int pointmark=-1,/*labelmark數(shù)組指針*/pointtemp=-1;/*labeltemp數(shù)組指針*/int sign=0; /*sign=1，為賦值語句；sign=2，為布爾表達式。*/*程序語句LR分析表*/static int action1913=/*0*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,-1,-1,/*1*/-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,ACC,-1,-1,/*2*/-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,/*3*/-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1,/*4*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,8,/*5*/-1,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1,/*6*/-1,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*7*/-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1,/*8*/-1,-1,-1,-1,-1,-1,12,-1,-1,-1,-1,-1,-1,/*9*/-1,-1,-1,-1,-1,-1,105,-1,13,-1,-1,-1,-1,/*10*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,14,-1,/*11*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,15,-1,/*12*/-1,-1,103,-1,-1,-1,103,-1,103,-1,103,-1,-1,/*13*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,16,/*14*/-1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*15*/-1,-1,102,-1,-1,-1,102,-1,102,-1,102,-1,-1,/*16*/-1,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1,/*17*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1,/*18*/-1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1;/*算術表示式的LR分析表*/static int action11610=/*0*/12,-1,-1,-1,-1,-1,14,-1,-1,1,/*1*/-1,2,3,4,5,6,-1,-1,ACC,-1,/*2*/12,-1,-1,-1,-1,-1,13,-1,-1,7,/*3*/12,-1,-1,-1,-1,-1,13,-1,-1,8,/*4*/12,-1,-1,-1,-1,-1,13,-1,-1,9,/*5*/12,-1,-1,-1,-1,-1,13,-1,-1,10,/*6*/12,-1,-1,-1,-1,-1,13,-1,-1,11,/*7*/-1,101,101,4,5,6,-1,101,101,-1,/*8*/-1,102,102,4,5,6,-1,102,102,-1,/*9*/-1,103,103,103,103,6,-1,103,103,-1,/*10*/ -1,104,104,104,104,6,-1,104,104,-1,/*11*/ -1,105,105,105,105,105,-1,105,105,-1,/*12*/ -1,107,107,107,107,107,-1,107,107,-1,/*13*/ 12,-1,-1,-1,-1,-1,13,-1,-1,-14,/*14*/ -1,2,3,4,5,6,-1,15,-1,-1,/*15*/ -1,106,106,106,106,106,-1,106,106,-1;/*布爾表示式的LR分析表*/static int action21611=/*0*/1,-1,4,-1,5,-1,-1,-1,13,7,8,/*1*/-1,2,-1,101,-1,101,101,101,-1,-1,-1,/*2*/3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*3*/-1,-1,-1,102,-1,102,102,102,-1,-1,-1,/*4*/1,-1,4,-1,5,-1,-1,-1,11,7,8,/*5*/1,-1,4,-1,5,-1,-1,-1,6,7,8,/*6*/-1,-1,-1,104,-1,9,10,104,-1,-1,-1,/*7*/1,-1,4,-1,5,-1,-1,-1,14,7,8,/*8*/1,-1,4,-1,5,-1,-1,-1,15,7,8,/*9*/105,-1,105,-1,105,-1,-1,-1,-1,-1,-1,/*10*/107,-1,107,-1,107,-1,-1,-1,-1,-1,-1,/*11*/-1,-1,-1,12,-1,9,10,-1,-1,-1,-1,/*12*/-1,-1,-1,103,-1,103,103,103,-1,-1,-1,/*13*/-1,-1,-1,-1,-1,9,10,ACC,-1,-1,-1,/*14*/-1,-1,-1,106,-1,9,10,106,-1,-1,-1,/*15*/-1,-1,-1,108,-1,9,10,108,-1,-1,-1;函數(shù)清單：void main(); /*主程序*/void readline(); /* 從文件讀一行到緩沖區(qū) */void readch(); /* 從緩沖區(qū)讀取一個字符 */int find(char spel); /* 標識符和關鍵字的識別 */void identifier(); /* 字符串的識別 */void number(); /* 數(shù)字的識別 */void scan(); /* 掃描主函數(shù) */void readnu(); /* 讀取二元式的一個字符 */int newtemp(); /* 中間變量的生成 */int gen(char op1,struct aa arg11,struct aa arg22,int result1); /* 生成四元式 */int merg(int p1,int p2); /* 布爾表示式的匹配 */void lrparse1(int num); /* 賦值語句的分析 */int lrparse2(int num); /* 布爾表達式的分析 */int test(int value); /* 測試字符是否為表達式中的值（不包括;） */int lrparse();/* 程序語句處理 */void disp1(); /* 顯示詞法分析結果 */void disp2(); /* 四元式分析結果 */void disp3(); /* 變量名表顯示 */主要函數(shù)流程圖：主函數(shù)：結束四元式的分析，顯示結果語法分析lrparse()從二元式讀一個字符初始化狀態(tài)棧顯示詞法分析結果掃描主函數(shù)scan從緩沖區(qū)讀取一個字符readch打開文件pas.dat開始詞法分析掃描函數(shù)scan：結束讀取下一符號分情況識別(帶不帶=)數(shù)字的識別number()字符串識別identifier()ch為其它符號？ch為數(shù)字？ch為字母？ch= ch=掃描程序scan Y N詞法分析標識符及關鍵字識別函數(shù)identifier：若ss1=1,返回ii-1,否則返回1順序查看數(shù)組ntab。若ss1=1,則為關鍵字，若不為1，則ii+ss1=0; ii=0;標識符和關鍵字的識別賦值語句的語法分析函數(shù)lrparse1結束A-i:=Elr=ACC)&stack1sp1=1?規(guī)約后為非終結符E-(E)E-iE-E+Elr=107?lr=106?lr=101?lr=100?堆棧管理,并遞歸進行管理lr1=108?lr1=0?出錯lr1=-1?讀SLR(1)表,得lr1賦值語句的分析lrparse1:對應文法：S-E;E-E+E;E-E-E;E-E*E;E-E/E;E-EE;E-(E); YE-i； N Y N N Y. Y Y Y Y N Y布爾表達式的語法分析函數(shù)lrparse2：結束return 1lr=ACC?規(guī)約后為非終結符EO-E(1)orE-EO E(2)E-ilr=108?lr=107?lr=101?lr=100?堆棧管理,并遞歸進行管理lr1=109?lr1=0?出錯lr1=-1?讀SLR(1)表,得lr1布爾表達式的分析lrparse2對應文法：S-E;E-i;E-i rop i;E-(E);B-not E;E-E and;E-E or;E-EE; Y Y N Y N N Y. Y Y Y Y N Y注：老師給出的賦值語句文法為：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i我將此文法給些為：(0)S-E;(1)E-E+E;(2)E-E-E;(3)E-E*E;(4)E-E/E;(5)E-EE;(6)E-(E);(7)E-i；并計算其SLR分析表:狀態(tài) ACTIONGOTO i + - * / ( ) #E0S12s141 1S2S3S4S5S6Acc 2S12S137 3S12S138 4S12S139 5S12S1310 6S12S1311 7R1R1S4S5S6R1R1 8R2R2S4S5S6R2R2 9R3R3R3R3S6R3R310R4R4R4R4S6R4R411R5R5R5R5R5R5R512R7R7R7R7R7R7R713S12S1314S2S3S4S5S6S1515R6R6R6R6R6R6R6四、源程序清單/ ht.cpp : 定義控制臺應用程序的入口點。/小型編譯程序：高級語言到四元式的編譯#include stdio.h/*如果使用TC的話，需要配置頭文件路徑*/#include string.h#define ACC -2/*/#define sy_if 0#define sy_then 1#define sy_else 2#define sy_while 3#define sy_begin 4#define sy_do 5#define sy_end 6#define a 7#define semicolon 8#define e 9#define jinghao 10#define S 11#define L 12#define tempsy 15#define EA 18 /*E and*/#define E0 19 /*E or*/#define plus 34#define times 36#define becomes 38#define op_and 39#define op_or 40#define op_not 41#define rop 42#define lparent 48#define rparent 49#define ident 56#define intconst 57#define minus 58#define div 59#define chengfang 60/*/char ch=0;/*從字符緩沖區(qū)讀取當前字符*/int count=0;/*詞法分析結果緩沖區(qū)計數(shù)器*/static char spelling10=;/*存放識別的字*/static char line81=;/*一行字符緩沖區(qū)，最多80個字符*/char *pline;/*字符緩沖區(qū)指針*/static char ntab110010;/*變量名表，共100項，每項長度10*/struct ntabint tc;/*真值*/int fc;/*假值*/ntab2200;/*在布爾表達式E中保存有關布爾變量的真、假值*/int label=0;/*指向ntab2的指針*/struct rwords/*存放臨時變量的表的定義*/char sp10;int sy;/*（保留字表）匹配表的結構，用來與輸入緩沖區(qū)中的單詞進行匹配*/*匹配表初始化，大小為10*/struct rwords reswords10=if,sy_if, do,sy_do,else,sy_else,while,sy_while,then,sy_then,begin,sy_begin,end,sy_end,and,op_and,or,op_or,not,op_not;struct aaint sy1;/*存放名字*/int pos;/*存放名字所對應的地址*/buf1000,/*詞法分析結果緩沖區(qū)*/n,/*讀取二元式的當前字符*/n1,/*當前表達式中的字符*/E,/*非終結符*/sstack100,/*算術或布爾表達式加工處理使用的符號棧*/ibuf100, /*算術或布爾表達式使用的緩沖區(qū)*/stack1000;/*語法分析加工處理使用的符號棧*/struct aa oth;/*四元式中空白位置*/struct fourexpchar op10;struct aa arg1;struct aa arg2;int result;fexp200;/*四元式的結構定義*/int ssp=0;/*指向sstack棧指針*/struct aa *pbuf=buf;/*指向詞法分析緩沖區(qū)的指針*/int nlength=0;/*詞法分析中記錄單詞的長度*/int lnum=0;/*源程序行數(shù)記數(shù)，源程序長度*/int tt1=0;/*變量名表指針*/FILE *cfile;/*源程序文件，為結束符*/*FILE *mfile;*/int newt=0;/*臨時變量計數(shù)器*/int nxq=100;/*nxq指向下一個形成的四元式的地址*/ /*每次執(zhí)行gen（）時，地址自動增1*/int lr;/*掃描LR分析表1過程中保存的當前狀態(tài)值*/int lr1;/*掃描LR分析表2或表3所保存的當前狀態(tài)值*/int sp=0;/*查找LR分析表時狀態(tài)棧的棧頂指針*/int stack1100;/*狀態(tài)棧1的定義*/int sp1=0;/*狀態(tài)棧1的棧頂指針*/int num=0;/*算術或布爾表達式緩沖區(qū)指針*/struct llint nxq1;/*記錄下一條四元式的地址*/int tc1;/*真值鏈*/int fc1;/*假值鏈*/labelmark10;/*記錄語句嵌套層次的數(shù)組，*/ /*即記錄嵌套中每層的布爾表達式E的首地址*/int labeltemp10;/*記錄語句嵌套層次的數(shù)組，*/ /*即記錄每層else之前的四元式地址*/int pointmark=-1,/*labelmark數(shù)組指針*/ pointtemp=-1;/*labeltemp數(shù)組指針*/int sign=0;/*sign=1，為賦值語句；sign=2，為布爾表達式。*/*程序語句LR分析表*/static int action1913=/*0*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,-1,-1,/*1*/-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,ACC,-1,-1,/*2*/-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,/*3*/-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1,/*4*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,8,/*5*/-1,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1,/*6*/-1,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*7*/-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1,/*8*/-1,-1,-1,-1,-1,-1,12,-1,-1,-1,-1,-1,-1,/*9*/-1,-1,-1,-1,-1,-1,105,-1,13,-1,-1,-1,-1,/*10*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,14,-1,/*11*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,15,-1,/*12*/-1,-1,103,-1,-1,-1,103,-1,103,-1,103,-1,-1,/*13*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,16,/*14*/-1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*15*/-1,-1,102,-1,-1,-1,102,-1,102,-1,102,-1,-1,/*16*/-1,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1,/*17*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1,/*18*/-1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1;/*算術表示式的LR分析表*/static int action11610=/*0*/12,-1,-1,-1,-1,-1,14,-1,-1,1,/*1*/-1,2,3,4,5,6,-1,-1,ACC,-1,/*2*/12,-1,-1,-1,-1,-1,13,-1,-1,7,/*3*/12,-1,-1,-1,-1,-1,13,-1,-1,8,/*4*/12,-1,-1,-1,-1,-1,13,-1,-1,9,/*5*/12,-1,-1,-1,-1,-1,13,-1,-1,10,/*6*/12,-1,-1,-1,-1,-1,13,-1,-1,11,/*7*/-1,101,101,4,5,6,-1,101,101,-1,/*8*/-1,102,102,4,5,6,-1,102,102,-1,/*9*/-1,103,103,103,103,6,-1,103,103,-1,/*10*/ -1,104,104,104,104,6,-1,104,104,-1,/*11*/ -1,105,105,105,105,105,-1,105,105,-1,/*12*/ -1,107,107,107,107,107,-1,107,107,-1,/*13*/ 12,-1,-1,-1,-1,-1,13,-1,-1,-1,/*14*/ -1,2,3,4,5,6,-1,15,-1,-1,/*15*/ -1,106,106,106,106,106,-1,106,106,-1;/*布爾表示式的LR分析表*/static int action21611=/*0*/1,-1,4,-1,5,-1,-1,-1,13,7,8,/*1*/-1,2,-1,101,-1,101,101,101,-1,-1,-1,/*2*/3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*3*/-1,-1,-1,102,-1,102,102,102,-1,-1,-1,/*4*/1,-1,4,-1,5,-1,-1,-1,11,7,8,/*5*/1,-1,4,-1,5,-1,-1,-1,6,7,8,/*6*/-1,-1,-1,104,-1,9,10,104,-1,-1,-1,/*7*/1,-1,4,-1,5,-1,-1,-1,14,7,8,/*8*/1,-1,4,-1,5,-1,-1,-1,15,7,8,/*9*/105,-1,105,-1,105,-1,-1,-1,-1,-1,-1,/*10*/107,-1,107,-1,107,-1,-1,-1,-1,-1,-1,/*11*/-1,-1,-1,12,-1,9,10,-1,-1,-1,-1,/*12*/-1,-1,-1,103,-1,103,103,103,-1,-1,-1,/*13*/-1,-1,-1,-1,-1,9,10,ACC,-1,-1,-1,/*14*/-1,-1,-1,106,-1,9,10,106,-1,-1,-1,/*15*/-1,-1,-1,108,-1,9,10,108,-1,-1,-1;/*從文件讀一行到緩沖區(qū)*/void readline()char ch1;pline=line;ch1=fgetc(cfile); while(ch1!=n)*pline=ch1;pline+;ch1=fgetc(cfile); *pline=0;pline=line;/*從緩沖區(qū)讀取一個字符*/void readch()if(ch=0)readline();lnum+;ch=*pline;pline+;/*標識符和關鍵字的識別*/int find(char spel)int ss1=0;int ii=0;while(ss1=0)&(ii=a)&(ch=0)&(ch=9);pline-;spellingk=0;while(ss=0)&(iii10)if(!strcmp(spelling,reswordsiii.sp) ss=1;iii+;/*關鍵字匹配*/if(ss=1)bufcount.sy1=reswordsiii-1.sy;elsebufcount.sy1=ident;j=find(spelling);if(j=-1)bufcount.pos=tt1;strcpy(ntab1tt1,spelling);tt1+;nlength+;else bufcount.pos=j;count+;for(k=0;k=0)&(ch=9);bufcount.sy1=