編譯程序實驗指導書

1、編譯程序實驗指導書實驗目的：用C語言對一個C語言的子集編制一個一遍掃描的編譯程序，以加深對編譯原理的理解，掌握編譯程序的實現(xiàn)方法和技術。1詞法分析1.1 實驗目的設計、編制并測試一個詞法分析程序，加深對詞法分析原理的理解。1.2 實驗要求待分析的C語言子集的詞法1. 關鍵字main if else int char for while 所有的關鍵字都是小寫。2專用符號= + - * / < <= > >= = != ; : , ( )3其他標記ID和NUM通過以下正規(guī)式定義其他標記：IDletter(letter|digit)*NUMdigit digit*letter

2、a|z|A|Zdigit0|94空格由空白、制表符和換行符組成空格一般用來分隔ID、NUM、專用符號和關鍵字，詞法分析階段通常被忽略。各種單詞符號對應的種別碼表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 -11.2.3 詞法分

3、析程序的功能輸入：所給文法的源程序字符串。輸出：二元組（syn,token或sum）構成的序列。其中，. syn為單詞種別碼。. Token為存放的單詞自身字符串。. Sum為整型常量。具體實現(xiàn)時，可以將單詞的二元組用結構進行處理。例如，對源程序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) (

4、34,;) (31,)1.3 詞法分析程序的主要算法思想算法的基本任務是從字符串表示的源程序中識別出具有獨立意義的單詞符號，其基本思想是根據(jù)掃描到的單詞符號的第一個字符的種類，拼出相應的單詞符號。1. 主程序示意圖 主程序示意圖如圖1所示。 置初值調用掃描子程序輸出單詞二元組輸入串結束結束否是圖1 詞法分析主程序示意圖其中初值包括如下兩方面：(1) 關鍵字表初值關鍵字作為特殊標識符處理,把它們預先安排在一張表格中(稱為關鍵字表),當掃描程序識別出標識符時,查關鍵字表。如能查到匹配的單詞，則該單詞為關鍵字，否則為一般標識符。關鍵字表為一個字符串數(shù)組，其描述如下：char *KEY_WORDS8=

5、“main”,”int”,”char”,”if”,”else”,”for”,”while”；為分析方便，這里把main作關鍵字處理。(2) 程序中需要用到的主要變量：syn,token和sum。2. 掃描子程序的算法思想首先設置三個變量：token用來存放構成單詞符號的字符串；sum用來存放整型單詞；syn用來存放單詞符號的種別編碼。掃描子程序主要部分流程如圖2所示。變量初始化 忽略空格是是否文件結束 返回否其他符號運算符,界符等符號字母數(shù)字否對不同符號給出相應的syn值是否關鍵字是Syn為對應關鍵字的單詞種別碼返回報錯拼數(shù)拼字符串Syn=10Syn=11圖2 詞法分析程序流程2語法分析2.1

6、 實驗目的編制一個遞歸下降分析程序， 實現(xiàn)對詞法分析程序所提供的單詞序列進行語法檢查和結構分析。2.2 實驗要求利用C語言編制遞歸下降分析程序，并對C語言的簡單子集進行分析。待分析的C語言子集的語法用擴充的BNF表示如下：(1) <程序>=main( )<語句塊>(2) <語句塊>=<語句串>(3) <語句串>=<語句><語句>(4) <語句>=<賦值語句>|<條件語句>|<循環(huán)語句>(5) <賦值語句>=ID=<表達式>(6) <條

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

8、3 語法分析程序的算法思想(1) 主程序示意圖如圖3所示。置初值調用scaner讀下一個單詞符號調用lrparser結束圖3 語法分析主程序示意圖(2) 遞歸下降分析程序示意圖如圖4所示。lrparser否否是否單詞串main()是調用scaner出錯處理調用語句塊分析函數(shù)否源程序是否結束是打印分析成功圖4遞歸下降分析程序示意圖(3) 語句塊分析過程示意圖如圖5所示。否是否是調用scaner出錯處理調用語句串分析過程否是否是出口圖5語句塊分析示意圖(4) 語句串分析過程示意圖如圖6所示。調用statement函數(shù) 否否是否；是調用scaner調用statement函數(shù)出錯處理圖6語句串分析示意

9、圖(5) statement (語句) 函數(shù)流程如圖7所示；(6) expression（表達式）分析過程如圖8所示；(7) term（項）分析過程如圖9所示；(8) condition（條件）分析過程如圖10所示；(9) factor（因子）分析過程如圖11所示。否是調用scaner是調用expression是否標識符否是否ifififfifififif標識符否是否while是是調用scaner調用scaner是否=否調用condition調用condition調用語句塊調用語句塊調用scaner出錯處理圖7 statement函數(shù)流程調用factor調用ffactor調用term出錯處理調

10、用factor調用scaner是否*、/是否否是否+、-是出錯處理調用scaner調用term圖8 expression分析過程示意圖 圖9 term分析過程示意圖調用scaner調用expression否是否邏輯運算符是出錯處理調用expression圖10 condition分析過程示意圖是是否標識符否是是否數(shù)字否是否（否是調用expression調用scaner是否）否調用scaner是出錯處理調用scaner圖11 factor分析過程示意圖 3語義分析產生中間代碼3.1 實驗目的通過上機實驗，加深對語法制導翻譯原理的理解，掌握將語法分析所識別的語法成分變換為中間代碼的語義翻譯方法。3

11、.2 實驗要求采用遞歸下降語法制導翻譯法對算術表達式、賦值語句、條件語句、循環(huán)語句進行語義分析生成四元式序列。輸入是語法分析提供的正確的單詞串，輸出是四元式序列。例如，對于語句串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) (=,1, ,k)(10) (j, , ,7)(11) .3

12、.2.2 算法思想1. 設置語義過程(1). int gen(op,arg1,arg2,result)該函數(shù)是將四元式(op,arg1,arg2,result)送到四元式表中。(2). char *newtemp( )該函數(shù)回送一個新的臨時變量名，臨時變量名產生的順序為T1,T2,.(3). int merg(p1,p2)該函數(shù)將以p1和p2為頭指針的兩條鏈合并為一，合并后的鏈首為返回值。(4). int bp(p,t)該函數(shù)的功能是把p所鏈接的每個四元式的第四區(qū)段都填為t。2. 主程序示意圖置初值調用scaner調用lrparser打印四元式列表結束圖12 語義分析主程序示意圖3. 函數(shù)lr

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

14、YN_INT2# define _SYN_CHAR3# define _SYN_IF4# define _SYN_ELSE5# define _SYN_FOR6# define _SYN_WHILE7/*以上為關鍵字的單詞種別碼*/# define _SYN_ID10/*標識符的單詞種別碼*/# define _SYN_NUM20/*整數(shù)的單詞種別碼*/# define _SYN_ASSIGN21/* = */# define _SYN_PLUS22/* + */# define _SYN_MINUS23/* - */# define _SYN_TIMES24/* * */# define _

15、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/* : */# define _SYN_SEMICOLON34/* ; */#

16、 define _SYN_LG35/* > */# define _SYN_LT36/* < */# define _SYN_ME37/* >= */# define _SYN_LE38/* <= */# define _SYN_EQ39/* = */# define _SYN_NE40/* != */# define _SYN_END1000/* 源程序結束標志 */# define _SYN_ERROR-1/* error */# define MAXLENGTH255/* 一行允許的字符個數(shù) */union WORDCONTENT /*存放單詞內容的聯(lián)合*/cha

17、r 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/* 關鍵字結束標記 */# define _KEY_WORD_END"waiting for your expanding"/* 函數(shù) Scaner 得到源程序里的下一

18、個單詞符號 */void Scaner(void);# endif/*/*文件：scan.c */*分析器的詞法掃描部分 */*/# include "globals.h"# Include "scan.h"void Do_Tag(char *strSource);/* 識別標識符的中間狀態(tài) */void Do_Digit(char *strSource);/* 識別數(shù)字的中間狀態(tài) */void Do_EndOfTag(char *strSource);/* 識別標識符最后的一個狀態(tài) */void Do_EndOfDigit(char *strSourc

19、e);/* 識別數(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(char *strSource);/* ( */void Do_En

20、dOfRParen(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);/* : */void Do_EndOfComma(char *strS

21、ource);/* , */void Do_EndOfSemicolon(char *strSource);/* ; */void Do_EndOfMore(char *strSource);/* >,>= */void Do_EndOfLess(char *strSource);/* <,<= */void Do_EndOfEnd(char *strSource);/* 用' 0 ' 作為源程序結束 */void PrintError(int nColumn,int nRow,char chInput);/* 詞法分析錯誤輸出 */void Scane

22、r(void)；/* 詞法掃描函數(shù) */extern char *strSource;/* 待分析的源程序 */extern FILE *fw;/* 結果輸出文件 */int gnColumn,gnRow,/* 行列號 */ gnLocate,/* 下一個字符腳標 */ gnLocateStart;/* 下一個單詞開始位置 */Word uWord;/* 掃描出的單詞 */* 關鍵字表 */char *KEY_WORDS20="main","int","char","if","else",&qu

23、ot;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' && chInput>='a') |

24、 (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_EndOfSubtraction(strSource);bre

25、ak; 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; case '': Do_EndOfRightBrac

26、ket1(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 '&

27、gt;': Do_EndOfMore(strSource);break; case '<': Do_EndOfLess(strSource);break; case '=': Do_EndOfEqual(strSource);break; case '0': Do_EndOfEnd(strSource);break; default:if (IsChar(strSourcegnLocate) /* 是標識符或關鍵字 */ Do_Tag(strSource);else if (IsDigit(strSourcegnLocate) /*

28、 可能是整數(shù) */ Do_Digit(strSource);else /* 其他符號 */ if (strSourcegnLocate!=' ' && strSourcegnLocate!='t' && strSourcegnLocate!=' n' && strSourcegnLocate!='r' PrintError(gnColumn,gnRow,strSourcegnLocate); if (strSourcegnLocate='n ' | strSource

29、gnLocate='r') gnColumn+;gnRow=1; else if (strSourcegnLocate='t') gnColumn+=_TAB_LENGTH; else gnRow+; gnLocate+;Do_Start(strSouce);break; return;void Do_Tag(char *strSource)/* 識別標識符的中間狀態(tài) */ gnLocate+; gnRow+;if (IsChar(strSourcegnLocate) | IsDigit(strSourcegnLocate) /* 是數(shù)字或者字母 */Do_Ta

30、g(strSource); else Do_EndOfTag(strSource); return;void Do_Digit(char *strSource)/* 識別整數(shù)的中間狀態(tài) */ gnLocate+; gnRow+; if (IsDigit(strSourcegnLocate) /* 是數(shù)字 */+strSourcegnLocate-'0'/* 累加識別的數(shù)字 */Do_Digit(strSource); else Do_EndOfDigit(strSource); return;void Do_EndOfTag(char *strSource)/* 標識符的最后狀

31、態(tài) */int nLoop; uWord.syn=_SYN_ID;/* 單詞種別碼缺省為標識符 */* 記錄標識符 */ nLoop=0; while (strcmp(KEY_WORDSnLoop,_KEY_WORD_END) /* 查關鍵字表，是否關鍵字 */* 比較和某關鍵字相符 */ uWord.syn=nLoop+1;/* 設置正確的 syn */ break;nLoop+; return;void Do_EndOfDigit(char *strSource)/* 識別數(shù)字的最后狀態(tài) */ uWord.syn=_SYN_NUM; return;void Do_EndOfEqual(ch

32、ar *strSource)/* =,= */ if (strSourcegnLocate+1!='=') /* = */ uWord.syn=_SYN_ASSIGN; else /* = */gnLocate+;gnRow+;uWord.syn=_SYN_EQ; gnLocate+; gnRow+; return;void Do_EndOfPlus(char *strSource)/* + */ uWord.syn=_SYN_PLUS; gnLocate+; gnRow+; return;void Do_EndOfSubtraction(char *strSource)/*

33、- */ uWord.syn=_SYN_MINUS; gnLocate+; gnRow+; return;void Do_EndOfMultply(char *strSource)/* * */ uWord.syn=_SYN_ TIMES; gnLocate+; gnRow+; return;void Do_EndOfDivide(char *strSource)/* / */ uWord.syn=_SYN_DIVIDE; gnLocate+; gnRow+; return;void Do_EndOfLParen(char *strSource)/* ( */ uWord.syn=_SYN_L

34、PAREN; gnLocate+; gnRow+; return;void Do_EndOfRParen(char *strSource)/* ( */ uWord.syn=_SYN_RPAREN; gnLocate+; gnRow+; return;void Do_EndOfLeftBracket1(char *strSource)/* */ uWord.syn=_SYN_LEFTBRACKET1; gnLocate+; gnRow+; return;void Do_EndOfRightBracket1(char *strSource)/* */ uWord.syn=_SYN_RIGHTBR

35、ACKET1; gnLocate+; gnRow+; return;void Do_EndOfLeftBracket2(char *strSource)/* */ uWord.syn=_SYN_LEFTBRACKET2; gnLocate+; gnRow+; return;void Do_EndOfRightBracket2(char *strSource)/* */ uWord.syn=_SYN_RIGHTBRACKET2; gnLocate+; gnRow+; return;void Do_EndOfColon(char *strSource)/* : */ uWord.syn=_SYN_

36、COLON; gnLocate+; gnRow+; return;void Do_EndOfComma(char *strSource)/* , */ uWord.syn=_SYN_COMMA; gnLocate+; gnRow+; return;void Do_EndOfSemicolon(char *strSource)/* ; */ uWord.syn=_SYN_SEMICOLON; gnLocate+; gnRow+; return;void Do_EndOfMore(char *strSource)/* >,>= */ if (strSourcegnLocate+1!=&

37、#39;=') /* > */ uWord.syn=_SYN_LG; else /*>= */gnLocate+;gnRow+;uWord.syn=_SYN_ME; gnLocate+; gnRow+; return;void Do_EndOfLess(char *strSource)/* <,<= */ if (strSourcegnLocate+1!='=') /* < */ uWord.syn=_SYN_LT; else /*<= */gnLocate+;gnRow+;uWord.syn=_SYN_LE; gnLocate+;

38、gnRow+; return;void Do_EndOfEnd(char *strSource)/* 讀到'0',源程序結束 */ uWord.syn=_SYN_END; gnLocate+; gnRow+; return;void PrintWord(Word uWord)/* 打印二元組 */ if (uWord.syn<=_SYN_ID /* 關鍵字、標識符或者有錯誤 */ | uWord.syn=_SYN_ME/* >= */ | uWord.syn=_SYN_LE/* <= */ | uWord.syn=_SYN_EQ) /* = */ else i

39、f (uWord.syn=_SYN_NUM) /* 數(shù)字 */ else /* 其他符號 */ 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

40、 PrintError(int nColumn,int nRow,char chInput)/* 打印詞法掃描發(fā)現(xiàn)的錯誤 */ fprintf(fw,"n 無法識別的單詞 ->Col:%dtRow:%dtChar:%c",nColumn,nRow,chInput); return;/*/*文件：semanteme.h */*定義語法（語義）分析器的接口 */*/# ifndef _SEMANTEME_H# define _SEMANTEME_H/* 四元組的結構 */typedef struct QUAD char opMAXLENGTH;/* 操作符 */ char

41、 argv1MAXLENGTH;/* 第一個操作數(shù) */ char argv2MAXLENGTH;/* 第二個操作數(shù) */ char resultMAXLENGTH;/* 運算結果 */QUATERNION;void lrparse(void);/* 語法語義分析主函數(shù) */# endif/*/*文件：semanteme.c */*分析器的語法語義掃描部分 */*/# include "globals.h"# include "scan.h"# include "semanteme.h"QUATERNION *pQuad;/* 存放四

42、元組的元組 */int nSuffix,nNXQ,/* 臨時變量的編號 */ntc,nfc;extern Word uWord;/* 掃描得到的單詞 */extern int gnColumn,gnRow;/* 行列號 */FILE *fw;/* 打印結果的文件指針 */char *strFileName;/* 打印結果的文件名 */char *strSource;/* 源程序 */char *Expression(void);char *Term(void);char *Factor(void);void Statement_Block(int *nChain);void LocateErr

43、or(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)/* 判斷當前識別出的單詞是否需要的單詞， 如果不是則報錯，否則掃描下一個單詞 */ if (syn=uWod

44、.syn) Scaner( ); else error(strError); return;void gen(char *op,char *argv1,char *argv2,char *result)/* 生成一個四元式 */ sprintf(pQuadnNXQ.op,op); sprintf(pQuadnNXQ.argv1,argv1); sprintf(pQuadnNXQ.argv2,argv2); sprintf(pQuadnNXQ.result,result); nNXQ+; return;void PrintQuaternion(void)/* 打印一個四元式 */ int nLo

45、op; for (nLoop=1;nLoop<nNXQ;nLoop+) fprintf(fw,"n%d:%s,t%s,t%s", nLoop,pQuadnLoop.op,pQuadnLoop.argv1, pQuadnLoop.argv2,pQuadnLoop.result); char *Newtemp(void)/* 產生一個臨時變量 */ char *strTempID=(char *) malloc(MAXLENGTH); sprintf(strTempID,"T%d",+nSuffix); return strTempID;int mer

46、g(int p1,int p2)/* 合并p1和p2 */ int p,nResult; if (p2=0) nResult=p1; else nResult=p=p2; while (atoi(pQuadp.result) p=atoi(pQuadp.result);sprintf(pQuadp.result,"%d",p1); return nResult;void bp(int p,int t)/* 將t回填到以p為首的四元式鏈中 */ int w,q=p; while (q) w=atoi(pQuadq.result); sprintf(pQuadq.result,"%d",t); q=w;