編譯程序?qū)嶒炛笇?dǎo)書

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*

2、lettera|z|A|Zdigit0|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 < 36for 6 ( 26 >= 37while 7 ) 27 <= 38ID 10 28 = 39MUN 20 29 != 40 30 0 1000 31 ERROR

3、 -11.2.3 詞法分析程序的功能輸入：所給文法的源程序字符串。輸出：二元組（syn,token或sum）構(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

4、,-) (20,1) (34,;) (31,)1.3 詞法分析程序的主要算法思想算法的基本任務(wù)是從字符串表示的源程序中識別出具有獨立意義的單詞符號，其基本思想是根據(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

5、*KEY_WORDS8=“main”,”int”,”char”,”if”,”else”,”for”,”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 詞法分析

6、程序流程2語法分析2.1 實驗?zāi)康木幹埔粋€遞歸下降分析程序， 實現(xiàn)對詞法分析程序所提供的單詞序列進行語法檢查和結(jié)構(gòu)分析。2.2 實驗要求利用C語言編制遞歸下降分析程序，并對C語言的簡單子集進行分析。2.2.1 待分析的C語言子集的語法用擴充的BNF表示如下：(1) <程序>=main( )<語句塊>(2) <語句塊>=<語句串>(3) <語句串>=<語句><語句>(4) <語句>=<賦值語句>|<條件語句>|<循環(huán)語句>(5) <賦值語句>=ID=&l

7、t;表達式>(6) <條件語句>=if(<條件>)<語句塊>(7) <循環(huán)語句>=while<條件><語句塊>(8) <條件>=<表達式><關(guān)系運算符><表達式>(9) <表達式>=<項>+<項>|-<項>(10)<項>=<因子>*<因子>|/<因子>(11)<因子>=ID|NUM|(<表達式>)(12)<關(guān)系運算符>=<|<=

8、|>|>=|=|!=2.3 語法分析程序的算法思想(1) 主程序示意圖如圖3所示。置初值調(diào)用scaner讀下一個單詞符號調(diào)用lrparser結(jié)束圖3 語法分析主程序示意圖(2) 遞歸下降分析程序示意圖如圖4所示。lrparser否否是否單詞串main()是調(diào)用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)用statem

9、ent函數(shù)出錯處理圖6語句串分析示意圖(5) statement (語句) 函數(shù)流程如圖7所示；(6) expression（表達式）分析過程如圖8所示；(7) term（項）分析過程如圖9所示；(8) condition（條件）分析過程如圖10所示；(9) factor（因子）分析過程如圖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)用

10、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)用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)翻譯原理的理解，掌握將語法分析所識別的語法

11、成分變換為中間代碼的語義翻譯方法。3.2 實驗要求采用遞歸下降語法制導(dǎo)翻譯法對算術(shù)表達式、賦值語句、條件語句、循環(huán)語句進行語義分析生成四元式序列。3.2.1 實驗的輸入和輸出輸入是語法分析提供的正確的單詞串，輸出是四元式序列。例如，對于語句串i=2*3+4;if (i>10) j=3;while j>10 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

12、) (=,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ù)回送一個新的臨時變量名，臨時變量名產(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)用lrpars

13、er打印四元式列表結(jié)束圖12 語義分析主程序示意圖3. 函數(shù)lrparser在原來語法分析的基礎(chǔ)上插入相應(yīng)的語義動作將輸入串翻譯成四元式序列。在實驗中我們只對表達式、if語句和while語句進行翻譯，其具體翻譯程序見實驗實例。4實驗實例/*/*文件：globals.h */*定義分析器需要的一些數(shù)據(jù)結(jié)構(gòu)、宏等 */*本頭文件必須在其他文件前引用 */*/# ifndef _GLOBALS_H# define _GLOBALS_H# include <stdio.h># include <stdlib.h># include <string.h>/*單詞種別碼

14、*/# 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ù)的單詞種別碼*/# define _SYN_ASSIGN21/* = */# define _SYN_PLUS22/* + */# define _SYN_MINUS23/* - */# defi

15、ne _SYN_TIMES24/* * */# define _SYN_DIVIDE25/* / */# define _SYN_LPAREN26/* ( */# define _SYN_RPAREN27/* ) */# define _SYN_LEFTBRACKET128/* */# define _SYN_RIGHTBRACKET129/* */# define _SYN_LEFTBRACKET230/* */# define _SYN_RIGHTBRACKET231/* */# define _SYN_COMMA32/* , */# define _SYN_COLON33/* : */#

16、 define _SYN_SEMICOLON34/* ; */# define _SYN_LG35/* > */# define _SYN_LT36/* < */# define _SYN_ME37/* >= */# define _SYN_LE38/* <= */# define _SYN_EQ39/* = */# define _SYN_NE40/* != */# define _SYN_END1000/* 源程序結(jié)束標(biāo)志 */# define _SYN_ERROR-1/* error */# define MAXLENGTH255/* 一行允許的字符個數(shù) */un

17、ion WORDCONTENT /*存放單詞內(nèi)容的聯(lián)合*/char T1MAXLENGTH;int T2;char T3;typedef struct WORD /*單詞二元組*/int syn;union WORDCONTENT value; WORD;# endif/*/*文件：scan.h */*定義詞法分析器的接口 */*/# ifndef _SCAN_H# define _SCAN_H/* 一個TAB占用的空格數(shù) */# define _TAB_LENGTH4/* 關(guān)鍵字結(jié)束標(biāo)記 */# define _KEY_WORD_END"waiting for your expan

18、ding"/* 函數(shù) Scaner 得到源程序里的下一個單詞符號 */void Scaner(void);# endif/*/*文件：scan.c */*分析器的詞法掃描部分 */*/# include "globals.h"# Include "scan.h"void Do_Tag(char *strSource);/* 識別標(biāo)識符的中間狀態(tài) */void Do_Digit(char *strSource);/* 識別數(shù)字的中間狀態(tài) */void Do_EndOfTag(char *strSource);/* 識別標(biāo)識符最后的一個狀態(tài) */v

19、oid Do_EndOfDigit(char *strSource);/* 識別數(shù)字最后的一個狀態(tài) */void Do_EndOfEqual(char *strSource);/* =,= */void Do_EndOfPlus(char *strSource);/* + */void Do_EndOfSubtraction(char *strSource);/* - */void Do_EndOfMultiply(char *strSource);/* * */void Do_EndOfDivide(char *strSource);/* / */void Do_EndOfLParen(ch

20、ar *strSource);/* ( */void Do_EndOfRParen(char *strSource);/* ) */void Do_EndOfLeftBracket1(char *strSource);/* */void Do_EndOfRightBracket1(char *strSource);/* */void Do_EndOfLeftBracket2(char *strSource);/* */void Do_EndOfRightBracket2(char *strSource);/* */void Do_EndOfColon(char *strSource);/* :

21、 */void Do_EndOfComma(char *strSource);/* , */void Do_EndOfSemicolon(char *strSource);/* ; */void Do_EndOfMore(char *strSource);/* >,>= */void Do_EndOfLess(char *strSource);/* <,<= */void Do_EndOfEnd(char *strSource);/* 用' 0 ' 作為源程序結(jié)束 */void PrintError(int nColumn,int nRow,char c

22、hInput);/* 詞法分析錯誤輸出 */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",&qu

23、ot;if","else","for","while","void",_KEY_WORD_END;int IsDigit(char chInput)/* 判斷掃描的字符是否數(shù)字 */ if (chInput<='9' && chInput>='0') return 1; else return 0;int IsChar(char chInput)/* 判斷掃描的字符是否字母 */ if (chInput<='z' &

24、& chInput>='a') | (chInput<='Z' && chInput>='A') return 1; else return 0;void Do_Start(char *strSource)/* 開始識別最先一個單詞 */ gnLocateStart=gnLocate; switch (strSourcegnLocate)/* 根據(jù)第一個字符判斷 */ case '+': Do_EndOfPlus(strSource);break; case '-': Do

25、_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_EndOfLeftBracket1(strSource);break; ca

26、se '': 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_EndOfSemicol

27、on(strSource);break; case '>': Do_EndOfMore(strSource);break; case '<': Do_EndOfLess(strSource);break; case '=': Do_EndOfEqual(strSource);break; case '0': Do_EndOfEnd(strSource);break; default:if (IsChar(strSourcegnLocate) /* 是標(biāo)識符或關(guān)鍵字 */ Do_Tag(strSource);else i

28、f (IsDigit(strSourcegnLocate) /* 可能是整數(shù) */ uWord.value.T2=strSourcegnLocate-'0' Do_Digit(strSource);else /* 其他符號 */ if (strSourcegnLocate!=' ' && strSourcegnLocate!='t' && strSourcegnLocate!=' n' && strSourcegnLocate!='r' PrintError(gnCo

29、lumn,gnRow,strSourcegnLocate); if (strSourcegnLocate='n ' | strSourcegnLocate='r') gnColumn+;gnRow=1; else if (strSourcegnLocate='t') gnColumn+=_TAB_LENGTH; else gnRow+; gnLocate+;Do_Start(strSouce);break; return;void Do_Tag(char *strSource)/* 識別標(biāo)識符的中間狀態(tài) */ gnLocate+; gnRow+;

30、if (IsChar(strSourcegnLocate) | IsDigit(strSourcegnLocate) /* 是數(shù)字或者字母 */Do_Tag(strSource); else Do_EndOfTag(strSource); return;void Do_Digit(char *strSource)/* 識別整數(shù)的中間狀態(tài) */ gnLocate+; gnRow+; if (IsDigit(strSourcegnLocate) /* 是數(shù)字 */uWord.value.T2=uWord.value.T2*10+strSourcegnLocate-'0'/* 累加識

31、別的數(shù)字 */Do_Digit(strSource); else Do_EndOfDigit(strSource); return;void Do_EndOfTag(char *strSource)/* 標(biāo)識符的最后狀態(tài) */int nLoop; uWord.syn=_SYN_ID;/* 單詞種別碼缺省為標(biāo)識符 */* 記錄標(biāo)識符 */ strncpy(uWord.value.T1,strSource+gnLocateStart,gnLocate-gnLocateStart); uWord.value.T1gnLocate-gnLocateStart='0' nLoop=0;

32、while (strcmp(KEY_WORDSnLoop,_KEY_WORD_END) /* 查關(guān)鍵字表，是否關(guān)鍵字 */ if (! strcmp(KEY_WORDSnLoop,uWord.value.T1) /* 比較和某關(guān)鍵字相符 */ uWord.syn=nLoop+1;/* 設(shè)置正確的 syn */ break;nLoop+; return;void Do_EndOfDigit(char *strSource)/* 識別數(shù)字的最后狀態(tài) */ uWord.syn=_SYN_NUM; return;void Do_EndOfEqual(char *strSource)/* =,= */

33、if (strSourcegnLocate+1!='=') /* = */ uWord.syn=_SYN_ASSIGN; uWord.value.T3=strSourcegnLocate; else /* = */gnLocate+;gnRow+;uWord.syn=_SYN_EQ;strcpy(uWord.value.T1,"="); gnLocate+; gnRow+; return;void Do_EndOfPlus(char *strSource)/* + */ uWord.syn=_SYN_PLUS; uWord.value.T3=strSourc

34、egnLocate; gnLocate+; gnRow+; return;void Do_EndOfSubtraction(char *strSource)/* - */ uWord.syn=_SYN_MINUS; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void Do_EndOfMultply(char *strSource)/* * */ uWord.syn=_SYN_ TIMES; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void

35、 Do_EndOfDivide(char *strSource)/* / */ uWord.syn=_SYN_DIVIDE; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void Do_EndOfLParen(char *strSource)/* ( */ uWord.syn=_SYN_LPAREN; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void Do_EndOfRParen(char *strSource)/* ( */ uWord.

36、syn=_SYN_RPAREN; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void Do_EndOfLeftBracket1(char *strSource)/* */ uWord.syn=_SYN_LEFTBRACKET1; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void Do_EndOfRightBracket1(char *strSource)/* */ uWord.syn=_SYN_RIGHTBRACKET1; uWord.v

37、alue.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void Do_EndOfLeftBracket2(char *strSource)/* */ uWord.syn=_SYN_LEFTBRACKET2; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void Do_EndOfRightBracket2(char *strSource)/* */ uWord.syn=_SYN_RIGHTBRACKET2; uWord.value.T3=strSourcegnLocat

38、e; gnLocate+; gnRow+; return;void Do_EndOfColon(char *strSource)/* : */ uWord.syn=_SYN_COLON; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void Do_EndOfComma(char *strSource)/* , */ uWord.syn=_SYN_COMMA; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void Do_EndOfSemicolo

39、n(char *strSource)/* ; */ uWord.syn=_SYN_SEMICOLON; uWord.value.T3=strSourcegnLocate; gnLocate+; gnRow+; return;void Do_EndOfMore(char *strSource)/* >,>= */ if (strSourcegnLocate+1!='=') /* > */ uWord.syn=_SYN_LG; uWord.value.T3=strSourcegnLocate; else /*>= */gnLocate+;gnRow+;uWo

40、rd.syn=_SYN_ME;strcpy(uWord.value.T1,">="); gnLocate+; gnRow+; return;void Do_EndOfLess(char *strSource)/* <,<= */ if (strSourcegnLocate+1!='=') /* < */ uWord.syn=_SYN_LT; uWord.value.T3=strSourcegnLocate; else /*<= */gnLocate+;gnRow+;uWord.syn=_SYN_LE;strcpy(uWord.v

41、alue.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 uWord)/* 打印二元組 */ if (uWord.syn<=_SYN_ID /* 關(guān)鍵字、標(biāo)識符或者有錯誤 */ | uWord.syn=_SYN_ME/* &g

42、t;= */ | uWord.syn=_SYN_LE/* <= */ | uWord.syn=_SYN_EQ) /* = */ fprintf(fw,"n(%d,t%s)",uWord.syn,uWord.value.T1); else if (uWord.syn=_SYN_NUM) /* 數(shù)字 */ fprintf(fw,"n(%d,t%d)",uWord.syn,uWord.value.T2); else /* 其他符號 */ fprintf(fw,"n(%d,t%c)",uWord.syn,uWord.value.T3);

43、 return;void ApartWord(char *strSource)/* 根據(jù)輸入的源程序識別所有的單詞 */ gnColumn=gnRow=1; gnLocate=gnLocateStart=0; while (strSourcegnLocate) Scaner( ); return;void Scaner(void)/* 詞法掃描函數(shù) */ Do_Start(strSource);/* 識別出一個單詞 */ printWord(uWord);/* 打印二元組 */ return;void PrintError(int nColumn,int nRow,char chInput)/

44、* 打印詞法掃描發(fā)現(xiàn)的錯誤 */ fprintf(fw,"n 無法識別的單詞 ->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

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

46、xtern Word uWord;/* 掃描得到的單詞 */extern 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);void error(char *strError)/* 輸出掃描發(fā)現(xiàn)的錯誤 */ LocateError(gnColumn,gnRow); fprintf(fw,"%s",strError); return;void Match(int syn,char *strError)/*