編譯原理課程設(shè)計--C編譯器詞法分析與語法分析的實現(xiàn)

1、編譯原理課程設(shè)計報告課題名稱： C-編譯器詞法分析與語法分析的實現(xiàn) 提交文檔學(xué)生姓名： 黃臻旸 提交文檔學(xué)生學(xué)號： 1043041227 同組 成 員 名 單： 無 指導(dǎo) 教 師 姓 名： 金軍 指導(dǎo)教師評閱成績： 指導(dǎo)教師評閱意見： . . 提交報告時間：2021年 6 月 5 日編譯原理課程設(shè)計報告11、課程設(shè)計目標(biāo)32、分析與設(shè)計32.1、說明所用的方法：32.2、系統(tǒng)總圖：32.2.1、scanner部分：32.2.2、parse部分：52.2.3、代碼設(shè)計說明73、程序代碼實現(xiàn)103.1、獲取輸入部分（在main.c中）：103.2、詞法分析部分（在scan.c中）：103.3、語法

2、分析部分（在parse.c中）：153.4、輸出與結(jié)點的建立（在util.c中）293.5、TokenType、treeNode與結(jié)點類型的聲明（在globals.h中）344、測試結(jié)果365、總結(jié)365.1、收獲365.2、不足361、課程設(shè)計目標(biāo)本次實驗，本C- 編譯器主要設(shè)計并且實現(xiàn)了C- 編譯器的詞法分析功能與語法分析功能。2、分析與設(shè)計2.1、說明所用的方法：各部分的實現(xiàn)方法（scanner：手工實現(xiàn)、Lex；parser：遞歸下降、LL(1)、LR(0)、SLR(1)、LR(1)、LALR(1)、Yacc），所用編程語言實現(xiàn)內(nèi)容所用的實驗方法所用編程語言scanner手工實現(xiàn)C語言

3、parse遞歸下降C語言2.2、系統(tǒng)總圖：2.2.1、scanner部分：、實驗原理：掃描程序的任務(wù)是從源代碼中讀取字符并形成由編譯器的以后部分（通常是分析程序）處理的邏輯單元。由掃描程序生成的邏輯單元稱作記號（token），將字符組合成記號與在一個英語句子中將字母將字母構(gòu)成單詞并確定單次的含義很相像。在此程序中，我將記號分成了以下類型：typedef enum /按照書上附錄B程序布局，放在globals.h中ENDFILE,ERROR,IF,ELSE,INT,RETURN,VOID,WHILE,ID,NUM,ASSIGN,PLUS,MINUS,TIMES,OVER,LT,LE

4、T,BT,BET,EQ,NEQ, / = + - * / < <= > >= = != LPAREN_1,RPAREN_1,SEMI,COM,LPAREN_2,RPAREN_2,LPAREN_3,RPAREN_3,LIN,RIN/ ; , ( ) /* TokenType;其中，關(guān)鍵字有：else、if、int、return、void、while；專用符號有：+、-、*、/、<、<=、>、>=、=、=、=、;、,、(、)、/*、*/其他標(biāo)記是ID、NUM，通過下列正則表達(dá)式定義：ID = letter letter*NUM = digit dig

5、it*letter = a|.|z|A|.|Zdigit = 0|.|9小寫大寫字母是有區(qū)別的?？崭裼煽瞻住Q行符和制表符組成?？崭裢ǔ１缓雎?，除了他必須分開ID、NUM關(guān)鍵字。注釋常用通常的C語言符號/*.*/圍起來。注釋可以放在任何空白出現(xiàn)的位置（即注釋不能放在標(biāo)記內(nèi)）上，且可以超過一行。注釋不能嵌套。、實驗方法：我通過對scanner部分原理的了解，確定了他的NFA，再將NFA轉(zhuǎn)化成DFA，并且將狀態(tài)數(shù)最小化。最后根據(jù)我所得的DFA與課后TINY的示例程序編寫scanner.c。最后所得的DFA：、編程方法：編程采用C語言。初始狀態(tài)設(shè)置為START，當(dāng)需要得到

6、下一個token時，取得此token的第一個字符，并且按照DFA與對此字符的類型的分析，轉(zhuǎn)換狀態(tài)。重復(fù)此步驟，直到DONE為止，輸出token類型。此中難點在于對于注釋的分析，因此我將判斷注釋分成幾個步驟。當(dāng)字符為“/”時，狀態(tài)轉(zhuǎn)換為INASSIGN_1（自創(chuàng)的）再判斷下一個字符，如果為“*”則是注釋，如果是其他的則字符停滯與當(dāng)前字符（ungetNextChar()），并且輸出“/”。在開始時一直未注意停滯與當(dāng)前字符，因此總是讀不出“/v*”中的“v”，在調(diào)試多次后才得以解決。2.2.2、parse部分：、實驗原理：C-語言的各個語法規(guī)則： 1. program declarat

7、ion-list 2. declaration-list declaration-list declaration | declaration 3. declaration var-declaration | fun-declaration 4. var-declaration type-specifier ID ; | type-specifier ID NUM ; 5. type-specifier int | void 6. fun-declaration type-specifier ID ( params ) compound-stmt （在課后解釋中compound-stmt前面沒

8、有“|”符號） 7. params params-list | void 8. param-list param-list , param | param 9. param type-specifier ID | type-specifier ID 10. compound-stmt local-declarations statement-list 11. local-declarations local-declarations var-declaration | empty 12. statement-list statement-list statement | empty 13. s

9、tatement expression-stmt | compound-stmt | selection-stmt | iteration-stmt | return-stmt 14. expression-stmt expression ; | ; 15. selection-stmt if ( expression ) statement | if ( expression ) statement else statement 16. iteration-stmt while(expression) statement 17. return-stmt return ; | return e

10、xpression ; 18. expression var = expression | simple-expression 19. var ID | ID expression 20. simple-expression additive-expression relop additive-expression | additive-expression 21. relop <= | < | > | >= | = | != 22. additive-expression additive-expression addop term | term 23. addop

11、+ | - 24. term term mulop factor | factor 25. mulop * | / 26. factor ( expression ) | var | call | NUM 27. call ID ( args ) 28. args arg-list | empty 29. arg-list arg-list , expression | expression 、實驗方法：本次試驗完成parse方法我采用的是遞歸下降的方法。根據(jù)C- 語言的規(guī)則，我們可以得出C- 語言語法的EBNF。下面是我在代碼中所使用的自己整理出來的語法規(guī)則：注： 為重復(fù) 為選

12、擇，為本來的意思1. program declaration-list 2. declaration-list declaration declaration 3. declaration int|void|empty ID factor;| (params)compound-stmt4. params params-list | void 5. param-list param param 6. param int|void ID empty| 7. compound-stmt local-declarations statement-list 8. local-declarations d

13、eclaration |empty9. statement-list statement |empty 10. statement expression-stmt | compound-stmt | selection-stmt | iteration-stmt | return-stmt 11. expression-stmt expression ; | ; 12. selection-stmt if ( expression ) statement else statement 13. iteration-stmt while(expression) statement 14. retu

14、rn-stmt return ;|expression ; 15. expression simple-expression = expression 16. var ID expression 17. simple-expression additive-expression relop additive-expression 18. relop <= | < | > | >= | = | != 19. additive-expression additive-expression addop term 20. addop + | - 21. term term mu

15、lop factor 22. mulop * | / 23. factor ( expression ) | NUM | ID (args)|expression|empty24. args arg-list | empty 25. arg-list expression expression 其中，3條declaration15條expression和23條factor是重點修改內(nèi)容。、編程方法：編程采用C語言。分析從program開始，逐層向下擴(kuò)展。依靠下一步所得到的token，根據(jù)整理過后的語法規(guī)則來判斷語法樹的結(jié)點生成與走向。并且根據(jù)語法規(guī)則來確定語法樹的末結(jié)點的內(nèi)容。此

16、處的難點在于語法規(guī)則的整理。若是按照書上原來的29條語法規(guī)則來寫，就會發(fā)現(xiàn)在樹的生成方法與邏輯上會很難實現(xiàn)。最開始時我便參照著原29條語法規(guī)則來寫的，雖然全程序都沒有報錯，但是分析程序時一直分析不了。最后停下編程來從筆頭整理了一陣子語法規(guī)則后，語法分析程序可以分析了，只有個別錯誤了。再不斷地在每一個結(jié)點生成時fprintf(listing,”n-its XXXX timen”)一下，逐步排查錯誤，最終才確定了剩下的這25個語法規(guī)則。2.2.3、代碼設(shè)計說明程序globals files包里面分為Source Files文件夾和Header Files文件夾Source Files文件夾中包含：

17、main.c ;parse.c ;scan.c ;util.cHeader Files文件夾中包含：globals.h ;parse.h ;scan.h ;util.h其中：main.c負(fù)責(zé)程序的執(zhí)行方式（cmd命令行下執(zhí)行g(shù)lobals.exe +測試代碼文件名）globals.h負(fù)責(zé)treeNode的聲明，TokenType類型的聲明，與NodeKind等的聲明util.c負(fù)責(zé)新結(jié)點的構(gòu)造，詞法的輸出，語法的輸出，以及輸出顯示的布局void printToken( TokenType token, const char * tokenString) /根據(jù)書上原型做的，但根據(jù)語法規(guī)則所需要

18、的，做過大量修改TreeNode * newStmtNode(StmtKind kind) /根據(jù)書上原型做的，未經(jīng)修改TreeNode * newExpNode(ExpKind kind) /根據(jù)書上原型做的，未經(jīng)修改TreeNode * newParamNode(void) /自己根據(jù)所需建立TreeNode * newDecNode(void) /自己根據(jù)所需建立char * copyString(char * s) /根據(jù)書上原型做的，未經(jīng)修改static void printSpaces(void) /根據(jù)書上原型做的，未經(jīng)修改void printTree( TreeNode * t

19、ree )/根據(jù)書上原型做的，但根據(jù)語法規(guī)則所需要的，做過大量修改util.h負(fù)責(zé)util.c中所用函數(shù)的聲明scan.c負(fù)責(zé)詞法狀態(tài)的聲明，詞法的分析typedef enum START,INASSIGN_1,L_ASSIGN,R_ASSIGN,E_ASSIGN,N_ASSIGN,INASSIGN_2,INCOMMENT,INNUM,INID,DONE StateType;/根據(jù)書上原型做的，但根據(jù)語法規(guī)則所需要的，做過大量修改static int getNextChar(void) /根據(jù)書上原型做的，未經(jīng)修改static void ungetNextChar(void) /根據(jù)書上原型做

20、的，未經(jīng)修改static struct char* str;TokenType tok; reservedWordsMAXRESERVED = "if",IF,"else",ELSE,"int",INT,"return",RETURN,"void",VOID,"while",WHILE;/根據(jù)書上原型做的，但根據(jù)語法規(guī)則所需要的，做過大量修改static TokenType reservedLookup (char * s) /根據(jù)書上原型做的，未經(jīng)修改TokenType g

21、etToken(void) /根據(jù)書上原型做的，但根據(jù)語法規(guī)則所需要的，做過大量修改scan.h負(fù)責(zé)對scan.c中所用函數(shù)的聲明parse.c負(fù)責(zé)語法樹的分析static void syntaxError(char * message) /根據(jù)書上原型做的，未經(jīng)修改static void match(TokenType expected) /根據(jù)書上原型做的，未經(jīng)修改/以下的全部為自己所寫static TreeNode * program(void);static TreeNode * declaration_list(void);static TreeNode * declaration(

22、void);static TreeNode * params(void);static TreeNode * param_list(void);static TreeNode * param(void);static TreeNode * compound_stmt(void);static TreeNode * local_declaration(void);static TreeNode * statement_list(void);static TreeNode * statement(void);static TreeNode * expression_stmt(void);stati

23、c TreeNode * selection_stmt(void);static TreeNode * iteration_stmt(void);static TreeNode * return_stmt(void);static TreeNode * expression(void);static TreeNode * var(void);static TreeNode * simple_expression(void);static TreeNode * additive_expression(void);static TreeNode * term(void);static TreeNo

24、de * factor(void);static TreeNode * args(void);static TreeNode * arg_list(void);parse.h負(fù)責(zé)parse.c中所用函數(shù)的聲明此次所做程序輸入格式為：cmd命令行下執(zhí)行g(shù)lobals.exe +測試代碼文件名輸出地方：cmd命令行輸出內(nèi)容：詞法分析與語法樹3、程序代碼實現(xiàn)3.1、獲取輸入部分（在main.c中）：此處因為并未有所修改，均參照附錄B所寫，所以略去。3.2、詞法分析部分（在scan.c中）：其中部分代碼因為參照附錄B中內(nèi)容而未修改，所以略去。typedef enum /此處便如圖所示，定

25、義11個中間狀態(tài)，其中INASSIGN分成了L_ASSIGN,R_ASSIGN,而在分析注釋結(jié)束時添加了INASSIGN_2狀態(tài)E_ASSIGN,N_ASSIGN,START,INASSIGN_1,L_ASSIGN,R_ASSIGN,E_ASSIGN,N_ASSIGN,INASSIGN_2,INCOMMENT,INNUM,INID,DONE StateType;static struct char* str;TokenType tok; reservedWordsMAXRESERVED = "if",IF,"else",ELSE,"int&qu

26、ot;,INT,"return",RETURN,"void",VOID,"while",WHILE;/此處根據(jù)C- 的保留字做了一定的修改TokenType getToken(void) /獨立完成int tokenStringIndex = 0;TokenType currentToken;StateType state = START;int save;while (state !=DONE) int c = getNextChar();save = TRUE;/fprintf(listing,"nScanner: st

27、ate = %dn",state);/測試每一步狀態(tài)switch (state) case START:if(isdigit(c)state = INNUM;/是數(shù)字else if(isalpha(c)state = INID;/是ID/fprintf(listing,"n-is alphan");/測試是否進(jìn)行到此處else if(c = '/') save = FALSE;state = INASSIGN_1;/判斷注釋/fprintf(listing,"n-is /n");else if(c = ' ')

28、| (c = 't') | (c = 'n')save = FALSE;else if(c = '<') save = FALSE;state = L_ASSIGN;else if(c = '>') save = FALSE;state = R_ASSIGN;else if(c = '=') save = FALSE;state = E_ASSIGN;else if(c = '!') save = FALSE;state = N_ASSIGN;else state = DONE;swit

29、ch(c) case EOF:save = FALSE;currentToken = ENDFILE;break;case ',':currentToken = COM;break;case '=':currentToken = EQ;break;case '+':currentToken = PLUS;break;case '-':currentToken = MINUS;break;case '*':currentToken = TIMES;break;case '(':currentToken

30、 = LPAREN_3;break;case ')':currentToken = RPAREN_3;break;case '':currentToken = LPAREN_2;break;case '':currentToken = RPAREN_2;break;case '':currentToken = LPAREN_1;break;case '':currentToken = RPAREN_1;break;case '':currentToken = SEMI;break;default:c

31、urrentToken = ERROR;break;break;case INCOMMENT:save = FALSE;if (c = EOF) state = DONE;currentToken = ENDFILE;else if (c='*') state = INASSIGN_2;/判斷 出 注釋else state = INCOMMENT;break;case INASSIGN_1:if (c = '*') /fprintf(listing,"n-is zsn");save = FALSE;state = INCOMMENT;/是注釋

32、else state = DONE; ungetNextChar();/char停住，否則會令“/”號后面的char讀不出來currentToken = OVER;break;case INASSIGN_2:if (c = '/') /是 出 注釋 save = FALSE;state = START;else state = INCOMMENT;/不是，返回注釋break;case L_ASSIGN:if(c = '=') currentToken = LET;else currentToken = LT;state = DONE;break;case R_A

33、SSIGN:if(c = '=') currentToken = BET;else currentToken = BT;state = DONE;break;case E_ASSIGN:if(c = '=') currentToken = EQ;else currentToken = ASSIGN;state = DONE;break;case N_ASSIGN:if(c = '=') currentToken = NEQ;else ungetNextChar();state = DONE;break;case INNUM:if (!isdigi

34、t(c) ungetNextChar();save = FALSE;state = DONE;currentToken = NUM;break;case INID:if (!isalpha(c) /fprintf(listing,"n-is ID overn");ungetNextChar();save = FALSE;state = DONE;currentToken = ID;break;case DONE:default:fprintf(listing,"Scanner Bug: state = %dn",state);state = DONE;c

35、urrentToken = ERROR;break;/fprintf(listing,"out switch");/getchar();if (save) && (tokenStringIndex <= MAXTOKENLEN)tokenStringtokenStringIndex+ = (char) c;if (state = DONE) tokenStringtokenStringIndex = '0'if(currentToken = ID)currentToken = reservedLookup(tokenString);if

36、 (TraceScan) fprintf(listing,"n%d: ",lineno);printToken(currentToken,tokenString);return currentToken;3.3、語法分析部分（在parse.c中）：其中部分代碼因為參照附錄B中內(nèi)容而未修改，所以略去。TreeNode * stmt_program(void) /program -> declaration-listTreeNode * t = declaration_list();return t;TreeNode * declaration_list(void) /d

37、eclaration-list -> declaration-list declaration | declaration/ declarationdeclarationTreeNode * t = NULL;TreeNode * p = NULL;TreeNode * q = NULL;/fprintf(listing,"n-its dec_li timen");/fprintf(listing,"n+%s+n",tokenString);/此兩處語句用于程序最初的運(yùn)行測試，基本上每一個函數(shù)里都有，用來測試哪一步有問題if(token!=ENDF

38、ILE&&(token=INT|token=VOID) t = declaration();p = t;while (token!=ENDFILE&&(token=INT|token=VOID) q = declaration();if(q!=NULL) if(t = NULL) t = p = q;else p->sibling = q;p = q;return t;TreeNode * declaration(void) /declaration -> var-declaration | fun-declaration/ (int|void) I

39、D NUM; | (int|void) ID (params) compound-stmt)/ int a; | int a; | void a?;| void main (void) | int gcd (int a,int b) | var-declaration statement(if,while.) /此處曾糾結(jié)過很久，最后發(fā)現(xiàn)附錄A開始陳列29條語法部分和后來詳解29條語法時有不同的地方。compound-stmt前面的“|”沒了。十分無語。而且這里是個難點。我發(fā)現(xiàn)如果真的有var-declaration那些東西又麻煩又累贅，就去掉了幾句語法/&&var-decla

40、ration&&type_specifier&&fun_declarationTreeNode * t = newDecNode();/fprintf(listing,"n-its dec timen");/fprintf(listing,"n+%s+n",tokenString);switch(token) case INT:t -> attr.type = "int"match(INT);break;case VOID:t -> attr.type = "void"m

41、atch(VOID);break;case EOF:return t;default:syntaxError("unexpected token in Type-> ");printToken(token,tokenString);token = getToken();break;/ fprintf(listing,"n+%s+n",tokenString);t -> = copyString(tokenString);match(ID); / fprintf(listing,"n+%s+n",toke

42、nString);switch(token) case LPAREN_2:t -> kind.dec = ArrayK;t -> child0 = factor();match(RPAREN_2);match(SEMI);break;case SEMI:t -> kind.dec = VarK;match(SEMI);break;case LPAREN_3:match(LPAREN_3); /fprintf(listing,"n+%s+n",tokenString);t -> kind.dec = FunK;if(t!=NULL) t->chi

43、ld0 = params();match(RPAREN_3); / fprintf(listing,"n+%s+n",tokenString);if(t!=NULL) t->child1 = compound_stmt();break;default:syntaxError("declaration wrong");token = getToken();break;return t;TreeNode * params(void) TreeNode * t = newParamNode();/fprintf(listing,"n-its p

44、ar timen");/fprintf(listing,"n+%s+n",tokenString);switch(token) case VOID:t ->attr.type = copyString(tokenString);match(VOID);break;default:t -> kind.param = UNull;t ->child0 = param_list();break;return t;TreeNode * param_list(void) TreeNode * t = param();TreeNode * p = t;/fp

45、rintf(listing,"n-its par_l timen");/fprintf(listing,"n+%s+n",tokenString);while ( (token != RPAREN_3) && ( token != ENDFILE ) TreeNode * q;match(COM);q = param();if (q != NULL) if (t = NULL) t = p = q;else p->sibling = q;p = q;return t;TreeNode * param(void) TreeNode *

46、 t = newParamNode();/這是參數(shù)結(jié)點，區(qū)別與聲明結(jié)點/fprintf(listing,"n-its param timen");/fprintf(listing,"n+%s+n",tokenString);switch(token) case VOID:/fprintf(listing,"n+VOID+n");t -> kind.param = Null;match(VOID);break;case INT:t -> attr.type = "int"t -> kind.para

47、m = UNull;/fprintf(listing,"n+INT+n");match(INT);break;default:/fprintf(listing,"n+%s+n",tokenString);syntaxError("param wrong");token = getToken();break;if(t != NULL)&&(token = ID)t -> = copyString(tokenString);match(ID);if( token = LPAREN_2)match(L

48、PAREN_2);t -> kind.param = Array;match(RPAREN_2); else t -> kind.param = Var;return t;TreeNode * compound_stmt(void) TreeNode * t = newStmtNode(CompoundK);/fprintf(listing,"n-its com timen");/fprintf(listing,"n+%s+n",tokenString);match(LPAREN_1);if( (t != NULL) && (

49、token = VOID | token = INT)t->child0 = local_declaration();if( t != NULL) t->child1 = statement_list();match(RPAREN_1);return t;TreeNode * local_declaration(void) TreeNode * t = NULL;TreeNode * q = t;/fprintf(listing,"n-its L_dec timen");/fprintf(listing,"n+%s+n",tokenStrin

50、g);if(token = INT) t = declaration();q = t;while(token = INT) TreeNode * p = declaration();if(p != NULL) if(t = NULL) t = q = p;else q->sibling=p; q=p;return t;TreeNode * statement_list(void) TreeNode * t = NULL;TreeNode * p;/fprintf(listing,"n-its sta_l timen");/fprintf(listing,"n+%s+n",tokenString);if(token!=ENDFILE)&&(token!=RPAREN_1) t = statement();p = t;while (token!=ENDFILE)&&(token!=RPAREN_1) TreeNode * q;q = statement();if (q != NULL) if