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

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

3、parse遞歸下降C語言2.2、系統總圖：2.2.1、scanner部分：、實驗原理：掃描程序的任務是從源代碼中讀取字符并形成由編譯器的以后部分（通常是分析程序）處理的邏輯單元。由掃描程序生成的邏輯單元稱作記號（token），將字符組合成記號與在一個英語句子中將字母將字母構成單詞并確定單次的含義很相像。在此程序中，我將記號分成了以下類型：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;其中，關鍵字有：else、if、int、return、void、while；專用符號有：+、-、*、/、<、<=、>、>=、=、=、=、;、,、(、)、/*、*/其他標記是ID、NUM，通過下列正則表達式定義：ID = letter letter*NUM = digit dig

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

6、下一個token時，取得此token的第一個字符，并且按照DFA與對此字符的類型的分析，轉換狀態。重復此步驟，直到DONE為止，輸出token類型。此中難點在于對于注釋的分析，因此我將判斷注釋分成幾個步驟。當字符為“/”時，狀態轉換為INASSIGN_1（自創的）再判斷下一個字符，如果為“*”則是注釋，如果是其他的則字符停滯與當前字符（ungetNextChar()），并且輸出“/”。在開始時一直未注意停滯與當前字符，因此總是讀不出“/v*”中的“v”，在調試多次后才得以解決。2.2.2、parse部分：、實驗原理：C-語言的各個語法規則： 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方法我采用的是遞歸下降的方法。根據C- 語言的規則，我們可以得出C- 語言語法的EBNF。下面是我在代碼中所使用的自己整理出來的語法規則：注： 為重復 為選

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是重點修改內容。、編程方法：編程采用C語言。分析從program開始，逐層向下擴展。依靠下一步所得到的token，根據整理過后的語法規則來判斷語法樹的結點生成與走向。并且根據語法規則來確定語法樹的末結點的內容。此

16、處的難點在于語法規則的整理。若是按照書上原來的29條語法規則來寫，就會發現在樹的生成方法與邏輯上會很難實現。最開始時我便參照著原29條語法規則來寫的，雖然全程序都沒有報錯，但是分析程序時一直分析不了。最后停下編程來從筆頭整理了一陣子語法規則后，語法分析程序可以分析了，只有個別錯誤了。再不斷地在每一個結點生成時fprintf(listing,”n-its XXXX timen”)一下，逐步排查錯誤，最終才確定了剩下的這25個語法規則。2.2.3、代碼設計說明程序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負責程序的執行方式（cmd命令行下執行globals.exe +測試代碼文件名）globals.h負責treeNode的聲明，TokenType類型的聲明，與NodeKind等的聲明util.c負責新結點的構造，詞法的輸出，語法的輸出，以及輸出顯示的布局void printToken( TokenType token, const char * tokenString) /根據書上原型做的，但根據語法規則所需要

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

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

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

21、etToken(void) /根據書上原型做的，但根據語法規則所需要的，做過大量修改scan.h負責對scan.c中所用函數的聲明parse.c負責語法樹的分析static void syntaxError(char * message) /根據書上原型做的，未經修改static void match(TokenType expected) /根據書上原型做的，未經修改/以下的全部為自己所寫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負責parse.c中所用函數的聲明此次所做程序輸入格式為：cmd命令行下執行globals.exe +測試代碼文件名輸出地方：cmd命令行輸出內容：詞法分析與語法樹3、程序代碼實現3.1、獲取輸入部分（在main.c中）：此處因為并未有所修改，均參照附錄B所寫，所以略去。3.2、詞法分析部分（在scan.c中）：其中部分代碼因為參照附錄B中內容而未修改，所以略去。typedef enum /此處便如圖所示，定

25、義11個中間狀態，其中INASSIGN分成了L_ASSIGN,R_ASSIGN,而在分析注釋結束時添加了INASSIGN_2狀態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;/此處根據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);/測試每一步狀態switch (state) case START:if(isdigit(c)state = INNUM;/是數字else if(isalpha(c)state = INID;/是ID/fprintf(listing,"n-is alphan");/測試是否進行到此處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中內容而未修改，所以略去。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);/此兩處語句用于程序最初的運行測試，基本上每一個函數里都有，用來測試哪一步有問題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.) /此處曾糾結過很久，最后發現附錄A開始陳列29條語法部分和后來詳解29條語法時有不同的地方。compound-stmt前面的“|”沒了。十分無語。而且這里是個難點。我發現如果真的有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();/這是參數結點，區別與聲明結點/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