编译原理课程设计--C-编译器词法分析与语法分析的实现.doc

编译原理课程设计报告课题名称： 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、语法分析部分（在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语言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,LET,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 digit*letter = a|.|z|A|.|Zdigit = 0|.|9小写大写字母是有区别的。空格由空白、换行符和制表符组成。空格通常被忽略，除了他必须分开ID、NUM关键字。注释常用通常的C语言符号/*.*/围起来。注释可以放在任何空白出现的位置（即注释不能放在标记内）上，且可以超过一行。注释不能嵌套。、实验方法：我通过对scanner部分原理的了解，确定了他的NFA，再将NFA转化成DFA，并且将状态数最小化。最后根据我所得的DFA与课后TINY的示例程序编写scanner.c。最后所得的DFA：、编程方法：编程采用C语言。初始状态设置为START，当需要得到下一个token时，取得此token的第一个字符，并且按照DFA与对此字符的类型的分析，转换状态。重复此步骤，直到DONE为止，输出token类型。此中难点在于对于注释的分析，因此我将判断注释分成几个步骤。当字符为“/”时，状态转换为INASSIGN_1（自创的）再判断下一个字符，如果为“*”则是注释，如果是其他的则字符停滞与当前字符（ungetNextChar()），并且输出“/”。在开始时一直未注意停滞与当前字符，因此总是读不出“/v*”中的“v”，在调试多次后才得以解决。2.2.2、parse部分：、实验原理：C-语言的各个语法规则： 1. program declaration-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前面没有“|”符号） 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. statement 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 expression ; 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 + | - 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。下面是我在代码中所使用的自己整理出来的语法规则：注： 为重复 为选择，为本来的意思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 declaration |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. return-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 mulop 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，根据整理过后的语法规则来判断语法树的结点生成与走向。并且根据语法规则来确定语法树的末结点的内容。此处的难点在于语法规则的整理。若是按照书上原来的29条语法规则来写，就会发现在树的生成方法与逻辑上会很难实现。最开始时我便参照着原29条语法规则来写的，虽然全程序都没有报错，但是分析程序时一直分析不了。最后停下编程来从笔头整理了一阵子语法规则后，语法分析程序可以分析了，只有个别错误了。再不断地在每一个结点生成时fprintf(listing,”n-its XXXX timen”)一下，逐步排查错误，最终才确定了剩下的这25个语法规则。2.2.3、代码设计说明程序globals files包里面分为Source Files文件夹和Header Files文件夹Source Files文件夹中包含：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) /根据书上原型做的，但根据语法规则所需要的，做过大量修改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 * tree )/根据书上原型做的，但根据语法规则所需要的，做过大量修改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) /根据书上原型做的，未经修改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 getToken(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(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);static 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 TreeNode * 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 /此处便如图所示，定义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,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: state = %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 = ) | (c = t) | (c = n)save = FALSE;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;switch(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 = 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:currentToken = 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;/是注释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_ASSIGN: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 (!isdigit(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;currentToken = ERROR;break;/fprintf(listing,out switch);/getchar();if (save) & (tokenStringIndex declaration-listTreeNode * t = declaration_list();return t;TreeNode * declaration_list(void) /declaration-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!=ENDFILE&(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) ID 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-declaration&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;match(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,tokenString);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-child0 = 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 par 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;/fprintf(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 * 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.param = 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(LPAREN_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) & (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,tokenString);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();i