編譯程序?qū)嶒炛笇?dǎo)書講解[共25頁]

1、編譯程序?qū)嶒炛笇?dǎo)書實驗?zāi)康模河肅語言對一個C語言的子集編制一個一遍掃描的編譯程序，以加深對編譯原理的理解，掌握編譯程序的實現(xiàn)方法和技術(shù)。1詞法分析1.1 實驗?zāi)康脑O(shè)計、編制并測試一個詞法分析程序，加深對詞法分析原理的理解。1.2 實驗要求1.2.1 待分析的C語言子集的詞法1. 關(guān)鍵字main if else int char for while 所有的關(guān)鍵字都是小寫。2專用符號= + - * / = = != ; : , ( )3其他標(biāo)記ID和NUM通過以下正規(guī)式定義其他標(biāo)記：IDletter(letter|digit)*NUMdigit digit*lettera|z|A|Zdigit0|

2、94空格由空白、制表符和換行符組成空格一般用來分隔ID、NUM、專用符號和關(guān)鍵字，詞法分析階段通常被忽略。1.2.2 各種單詞符號對應(yīng)的種別碼表1 各種單詞符號的種別碼單詞符號 種別碼 單詞符號 種別碼 單詞符號 種別碼main 1 = 21 , 32int 2 + 22 : 33char 3 - 23 ; 34if 4 * 24 35else 5 / 25 = 37while 7 ) 27 = 38ID 10 28 = 39MUN 20 29 != 40 30 0 1000 31 ERROR -11.2.3 詞法分析程序的功能輸入：所給文法的源程序字符串。輸出：二元組（syn,token或s

3、um）構(gòu)成的序列。其中，. syn為單詞種別碼。. Token為存放的單詞自身字符串。. Sum為整型常量。具體實現(xiàn)時，可以將單詞的二元組用結(jié)構(gòu)進行處理。例如，對源程序main()int i=10;while(i) i=i-1;的源文件，經(jīng)詞法分析后輸出如下序列：(1,main) (26,() (27,) (30, (2,int) (10,i) (21,=) (20,10) (34,;) (7,while)(26,() (10,i) (27,) (10,i) (21,=) (10,i) (23,-) (20,1) (34,;) (31,)1.3 詞法分析程序的主要算法思想算法的基本任務(wù)是從字符

4、串表示的源程序中識別出具有獨立意義的單詞符號，其基本思想是根據(jù)掃描到的單詞符號的第一個字符的種類，拼出相應(yīng)的單詞符號。1. 主程序示意圖 主程序示意圖如圖1所示。 置初值調(diào)用掃描子程序輸出單詞二元組輸入串結(jié)束結(jié)束否是圖1 詞法分析主程序示意圖其中初值包括如下兩方面：(1) 關(guān)鍵字表初值關(guān)鍵字作為特殊標(biāo)識符處理,把它們預(yù)先安排在一張表格中(稱為關(guān)鍵字表),當(dāng)掃描程序識別出標(biāo)識符時,查關(guān)鍵字表。如能查到匹配的單詞，則該單詞為關(guān)鍵字，否則為一般標(biāo)識符。關(guān)鍵字表為一個字符串?dāng)?shù)組，其描述如下：char *KEY_WORDS8=“main”,”int”,”char”,”if”,”else”,”for”,”

5、while”；為分析方便，這里把main作關(guān)鍵字處理。(2) 程序中需要用到的主要變量：syn,token和sum。2. 掃描子程序的算法思想首先設(shè)置三個變量：token用來存放構(gòu)成單詞符號的字符串；sum用來存放整型單詞；syn用來存放單詞符號的種別編碼。掃描子程序主要部分流程如圖2所示。變量初始化 忽略空格是是否文件結(jié)束 返回否其他符號運算符,界符等符號字母數(shù)字否對不同符號給出相應(yīng)的syn值是否關(guān)鍵字是Syn為對應(yīng)關(guān)鍵字的單詞種別碼返回報錯拼數(shù)拼字符串Syn=10Syn=11圖2 詞法分析程序流程2語法分析2.1 實驗?zāi)康木幹埔粋€遞歸下降分析程序， 實現(xiàn)對詞法分析程序所提供的單詞序列進行語

6、法檢查和結(jié)構(gòu)分析。2.2 實驗要求利用C語言編制遞歸下降分析程序，并對C語言的簡單子集進行分析。2.2.1 待分析的C語言子集的語法用擴充的BNF表示如下：(1) =main( )(2) =(3) =;(4) =|(5) =ID=(6) =if()(7) =while(8) =(9) =+|-(10)=*|/(11)=ID|NUM|()(12)=|=|=|!=2.3 語法分析程序的算法思想(1) 主程序示意圖如圖3所示。置初值調(diào)用scaner讀下一個單詞符號調(diào)用lrparser結(jié)束圖3 語法分析主程序示意圖(2) 遞歸下降分析程序示意圖如圖4所示。lrparser否否是否單詞串main()是調(diào)

7、用scaner出錯處理調(diào)用語句塊分析函數(shù)否源程序是否結(jié)束是打印分析成功圖4遞歸下降分析程序示意圖(3) 語句塊分析過程示意圖如圖5所示。否是否是調(diào)用scaner出錯處理調(diào)用語句串分析過程否是否是出口圖5語句塊分析示意圖(4) 語句串分析過程示意圖如圖6所示。調(diào)用statement函數(shù) 否否是否；是調(diào)用scaner調(diào)用statement函數(shù)出錯處理圖6語句串分析示意圖(5) statement (語句) 函數(shù)流程如圖7所示；(6) expression（表達式）分析過程如圖8所示；(7) term（項）分析過程如圖9所示；(8) condition（條件）分析過程如圖10所示；(9) facto

8、r（因子）分析過程如圖11所示。否是調(diào)用scaner是調(diào)用expression是否標(biāo)識符否是否ifififfifififif標(biāo)識符否是否while是是調(diào)用scaner調(diào)用scaner是否=否調(diào)用condition調(diào)用condition調(diào)用語句塊調(diào)用語句塊調(diào)用scaner出錯處理圖7 statement函數(shù)流程調(diào)用factor調(diào)用ffactor調(diào)用term出錯處理調(diào)用factor調(diào)用scaner是否*、/是否否是否+、-是出錯處理調(diào)用scaner調(diào)用term圖8 expression分析過程示意圖 圖9 term分析過程示意圖調(diào)用scaner調(diào)用expression否是否邏輯運算符是出錯處理調(diào)用

9、expression圖10 condition分析過程示意圖是是否標(biāo)識符否是是否數(shù)字否是否（否是調(diào)用expression調(diào)用scaner是否）否調(diào)用scaner是出錯處理調(diào)用scaner圖11 factor分析過程示意圖 3語義分析產(chǎn)生中間代碼3.1 實驗?zāi)康耐ㄟ^上機實驗，加深對語法制導(dǎo)翻譯原理的理解，掌握將語法分析所識別的語法成分變換為中間代碼的語義翻譯方法。3.2 實驗要求采用遞歸下降語法制導(dǎo)翻譯法對算術(shù)表達式、賦值語句、條件語句、循環(huán)語句進行語義分析生成四元式序列。3.2.1 實驗的輸入和輸出輸入是語法分析提供的正確的單詞串，輸出是四元式序列。例如，對于語句串i=2*3+4;if (i1

10、0) j=3;while j10 k=1;輸出的四元式序列如下：(1) (*,2,3,T1)(2) (+,2,T1,T2)(3) (=,T2, ,i)(4) (j,i,10,6)(5) (j, , ,7)(6) (=,3, ,j)(7) (j,j,10,9)(8) (j, , ,11)(9) (=,1, ,k)(10) (j, , ,7)(11) .3.2.2 算法思想1. 設(shè)置語義過程(1). int gen(op,arg1,arg2,result)該函數(shù)是將四元式(op,arg1,arg2,result)送到四元式表中。(2). char *newtemp( )該函數(shù)回送一個新的臨時變量名

11、，臨時變量名產(chǎn)生的順序為T1,T2,.(3). int merg(p1,p2)該函數(shù)將以p1和p2為頭指針的兩條鏈合并為一，合并后的鏈首為返回值。(4). int bp(p,t)該函數(shù)的功能是把p所鏈接的每個四元式的第四區(qū)段都填為t。2. 主程序示意圖置初值調(diào)用scaner調(diào)用lrparser打印四元式列表結(jié)束圖12 語義分析主程序示意圖3. 函數(shù)lrparser在原來語法分析的基礎(chǔ)上插入相應(yīng)的語義動作將輸入串翻譯成四元式序列。在實驗中我們只對表達式、if語句和while語句進行翻譯，其具體翻譯程序見實驗實例。4實驗實例/*/*文件：globals.h */*定義分析器需要的一些數(shù)據(jù)結(jié)構(gòu)、宏等

12、 */*本頭文件必須在其他文件前引用 */*/# ifndef _GLOBALS_H# define _GLOBALS_H# include # include # include /*單詞種別碼*/# define _SYN_MAIN1# define _SYN_INT2# define _SYN_CHAR3# define _SYN_IF4# define _SYN_ELSE5# define _SYN_FOR6# define _SYN_WHILE7/*以上為關(guān)鍵字的單詞種別碼*/# define _SYN_ID10/*標(biāo)識符的單詞種別碼*/# define _SYN_NUM20/*整數(shù)

13、的單詞種別碼*/# define _SYN_ASSIGN21/* = */# define _SYN_PLUS22/* + */# define _SYN_MINUS23/* - */# define _SYN_TIMES24/* * */# define _SYN_DIVIDE25/* / */# define _SYN_LPAREN26/* ( */# define _SYN_RPAREN27/* ) */# define _SYN_LEFTBRACKET128/* */# define _SYN_RIGHTBRACKET129/* */# define _SYN_LEFTBRACKET2

14、30/* */# define _SYN_RIGHTBRACKET231/* */# define _SYN_COMMA32/* , */# define _SYN_COLON33/* : */# define _SYN_SEMICOLON34/* ; */# define _SYN_LG35/* */# define _SYN_LT36/* = */# define _SYN_LE38/* ,= */void Do_EndOfLess(char *strSource);/* ,= */void Do_EndOfEnd(char *strSource);/* 用 0 作為源程序結(jié)束 */voi

15、d PrintError(int nColumn,int nRow,char chInput);/* 詞法分析錯誤輸出 */void Scaner(void)；/* 詞法掃描函數(shù) */extern char *strSource;/* 待分析的源程序 */extern FILE *fw;/* 結(jié)果輸出文件 */int gnColumn,gnRow,/* 行列號 */ gnLocate,/* 下一個字符腳標(biāo) */ gnLocateStart;/* 下一個單詞開始位置 */Word uWord;/* 掃描出的單詞 */* 關(guān)鍵字表 */char *KEY_WORDS20=main,int,char

16、,if,else,for,while,void,_KEY_WORD_END;int IsDigit(char chInput)/* 判斷掃描的字符是否數(shù)字 */ if (chInput=0) return 1; else return 0;int IsChar(char chInput)/* 判斷掃描的字符是否字母 */ if (chInput=a) | (chInput=A) return 1; else return 0;void Do_Start(char *strSource)/* 開始識別最先一個單詞 */ gnLocateStart=gnLocate; switch (strSou

17、rcegnLocate)/* 根據(jù)第一個字符判斷 */ case +: Do_EndOfPlus(strSource);break; case -: Do_EndOfSubtraction(strSource);break; case *: Do_EndOfMultiply(strSource);break; case /: Do_EndOfDivide(strSource);break; case (: Do_EndOfLParen(strSource);break; case ): Do_EndOfRParen(strSource);break; case : Do_EndOfLeftBr

18、acket1(strSource);break; case : Do_EndOfRightBracket1(strSource);break; case : Do_EndOfLeftBracket2(strSource);break; case : Do_EndOfRightBracket2(strSource);break; case : Do_EndOfColon(strSource);break; case ,: Do_EndOfComma(strSource);break; case ;: Do_EndOfSemicolon(strSource);break; case : Do_En

19、dOfMore(strSource);break; case ,= */ if (strSourcegnLocate+1!=) /* */ uWord.syn=_SYN_LG; uWord.value.T3=strSourcegnLocate; else /*= */gnLocate+;gnRow+;uWord.syn=_SYN_ME;strcpy(uWord.value.T1,=); gnLocate+; gnRow+; return;void Do_EndOfLess(char *strSource)/* ,= */ if (strSourcegnLocate+1!=) /* */ uWo

20、rd.syn=_SYN_LT; uWord.value.T3=strSourcegnLocate; else /*= */gnLocate+;gnRow+;uWord.syn=_SYN_LE;strcpy(uWord.value.T1,=); gnLocate+; gnRow+; return;void Do_EndOfEnd(char *strSource)/* 讀到0,源程序結(jié)束 */ uWord.syn=_SYN_END; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void PrintWord(Word uWo

21、rd)/* 打印二元組 */ if (uWord.syn= */ | uWord.syn=_SYN_LE/* Col:%dtRow:%dtChar:%c,nColumn,nRow,chInput); return;/*/*文件：semanteme.h */*定義語法（語義）分析器的接口 */*/# ifndef _SEMANTEME_H# define _SEMANTEME_H/* 四元組的結(jié)構(gòu) */typedef struct QUAD char opMAXLENGTH;/* 操作符 */ char argv1MAXLENGTH;/* 第一個操作數(shù) */ char argv2MAXLENGT

22、H;/* 第二個操作數(shù) */ char resultMAXLENGTH;/* 運算結(jié)果 */QUATERNION;void lrparse(void);/* 語法語義分析主函數(shù) */# endif/*/*文件：semanteme.c */*分析器的語法語義掃描部分 */*/# include globals.h# include scan.h# include semanteme.hQUATERNION *pQuad;/* 存放四元組的元組 */int nSuffix,nNXQ,/* 臨時變量的編號 */ntc,nfc;extern Word uWord;/* 掃描得到的單詞 */extern

23、 int gnColumn,gnRow;/* 行列號 */FILE *fw;/* 打印結(jié)果的文件指針 */char *strFileName;/* 打印結(jié)果的文件名 */char *strSource;/* 源程序 */char *Expression(void);char *Term(void);char *Factor(void);void Statement_Block(int *nChain);void LocateError(int nColumn,int nRow)/* 定位語法錯誤 */ fprintf(fw,nCol:%dtRow:%d-,nColumn+1,nRow);voi

24、d error(char *strError)/* 輸出掃描發(fā)現(xiàn)的錯誤 */ LocateError(gnColumn,gnRow); fprintf(fw,%s,strError); return;void Match(int syn,char *strError)/* 判斷當(dāng)前識別出的單詞是否需要的單詞， 如果不是則報錯，否則掃描下一個單詞 */ if (syn=uWod.syn) Scaner( ); else error(strError); return;void gen(char *op,char *argv1,char *argv2,char *result)/* 生成一個四元式

25、 */ sprintf(pQuadnNXQ.op,op); sprintf(pQuadnNXQ.argv1,argv1); sprintf(pQuadnNXQ.argv2,argv2); sprintf(pQuadnNXQ.result,result); nNXQ+; return;void PrintQuaternion(void)/* 打印一個四元式 */ int nLoop; for (nLoop=1;nLoopnNXQ;nLoop+) fprintf(fw,n%d:%s,t%s,t%s, nLoop,pQuadnLoop.op,pQuadnLoop.argv1, pQuadnLoop.argv2,pQuadnLoop.result); char *Newtemp(void)/* 產(chǎn)生一個臨時變量 */ char *strTempID=(char *) malloc(MAXLENGTH); sprintf(strTempID,T%d,+nSuffix); return strTempID;int merg(i