编译原理课程设计-C-词法扫描器及语法分析器实现

1、编译原理课程设计报告课题名称： C-词法扫描器及语法分析器实现 提交文档学生姓名： 提交文档学生学号： 同组 成 员 名 单： 无 指导 教 师 姓 名： 金军 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间：2014年 6月 xx日目录目录21 课程设计目标22 分析与设计42.1 程序结构43 程序代码实现93.1 代码结构93.2.1 globals.h93.2.2 scan.c113.2.3 parser.c183.4 util.c303.5 test.cpp364 测试结果384.1.给出标准测试程序的词法和语法分析结果：384.1.1 词法分析结果384.1.2 语法

2、分析结果414.2.修改代码后的结果：424.2.1修改425. 本课程设计我的独创工作446.总结44 1 课程设计目标学生在学习编译原理课程过程中，结合各章节的构造编译程序的基本理论，要求用C或C+语言描述及上机调试，实现一个 C-Minus 小编译程序（包括词法分析，语法分析等重要子程序），使学生将理论与实际应用结合起来，受到软件设计等开发过程的全面训练，从而提高学生软件开发的能力。 要求：（1）设计词法分析器设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括：a. 具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要

3、求设计一个供词法分析调用的预处理子程序；b. 能够拼出语言中的各个单词；c. 返回（种别码， 属性值）。（2）语法分析要求用学习过的自底向上或自顶向下的分析方法等，实现对表达式、各种说明语句、控制语句进行语法分析。若语法正确，则用语法制导翻译法进行语义翻译；生成并打印出语法树；若语法错误，要求指出出错性质和出错位置（行号）。2 分析与设计2.1 程序结构本程序采用C+语言以面向对象的思想编写，程序分为两部分：词法分析（Scanner）和语法分析（Parser）。扫描程序执行词法分析，并将字符序列收集到token中，并将每一行的Token打印出来。l 实现方法：Scanner：手工实现Parse

4、r：递归下降l 系统总图:ParserScannersource code Token Syntax Tree 程序流程：在程序中，词法分析获取所有Token，并将获取的Token存储在scanner对象的tokenString中。然后Parser类的语法分析程序就根据tokenString中的Token进行语法分析，生成语法树，最后打印语法树。同时，这也是程序的流程。整体程序流程图开始删除注释出错词法分析TF结束语法分析出错出错输出出错信息TFFT从文件获取源代码l 扫描器：C惯用的词法1、语言的关键字：else if int return void while2、专用符号：+ - * /

5、= = != = ; , ( ) /* */3、其他标记是ID和NUM，通过下列正则表达式定义：ID = letter letter*NUM = digit digit*letter = a|.|z|A|.|Zdigit = 0|.|94、空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字。5. 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套。DFA图如下：初始状态设置为START，当需要得到下一个token时，取得此token的第一个字符，并且按照DFA与对此字符的类

6、型的分析，转换状态。重复此步骤，直到DONE为止，输出token类型。参考课本中所给的TINY扫描程序的DFA，C-的DFA不同之处在于注释以及(= =,! = , =)的处理：1. 注释部分参考了课本中C风格注释的DFA； Other other *54321 / * * / Other other 2. 处理(= =,! = , =)时并没有新建状态，而是在状态INASSIGN中分了4种情况，通过一个变量分别处理。INENDCOMMENTl 语法分析： C-语法与语义：1. program declaration-list 2. declaration-list declaration-l

7、ist 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. pa

8、ram-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 |

9、 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 = expressio

10、n | 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.

11、factor ( expression ) | var | call | NUM 27. call ID ( args ) 28. args arg-list | empty 29. arg-list arg-list , expression | expressionl 代码设计格式：程序结构：语法分析函数parser通过调用词法分析函数getToken实现语法分析。文件和函数的设计说明：文件main.c包含相应头文件，及main函数的实现；文件golbals.h包含符号表和分析数的数据结构及在其它文件中使用的变量；文件util.h 和util.c实现与词法分析和语法分析输出相关的函数pri

12、ntToken和printTree，以及分析树节点初始化相关的函数newStmtNode，newExpNode(Expkind)和copyString；文件scan.h 和scan.c实现词法分析，主要函数为getToken；文件parser.h 和parser.c实现语法分析，函数为与文法规则对应的函数。3 程序代码实现3.1 代码结构3.2.1 globals.h#ifndef _GLOBALS_H_#define _GLOBALS_H_#include #include #include #include #include#include using namespace std;#ifn

13、def FALSE#define FALSE 0#endif#ifndef TRUE#define TRUE 1;#endif/ 保留字的个数#define MAXRESERVED 6typedef enum/book-keeping tokensENDFILE,ERROR,/reserved wordsIF,ELSE,INT,RETURN,VOID,WHILE,/multicharacter tokensID,NUM,/special symbols/LBRACKET/RBRACKET - LBRACE/RBRACE ASSIGN,EQ,LT,RT,PLUS,MINUS,TIMES,OVER

14、,LPAREN,RPAREN,SEMI,LBRACKET,RBRACKET,NEQ,COMMA,LBRACE,RBRACE,LTEQ,RTEQTokenType;extern FILE* source; /源代码文件extern FILE* listing; /listing output text fileextern FILE* code; /extern int lineno; /语法分析树typedef enum NodeKindStmtK, ExpK, DeclarationK,;typedef enum StmtKindIfK, WhileK, AssignK, ReturnK,

15、VoidK,;typedef enum ExpKindOpK, ConstK, IdK, Array_expK,Function_expK,;typedef enum ExpTypeVoid,Integer;typedef enum DeclarationKind FunctionK, VarK, ArrayK, ParaMeterK ;#define MAXCHILDREN 3typedef struct treeNodestruct treeNode *declaration;struct treeNode *childMAXCHILDREN;struct treeNode *siblin

16、g;struct treeNode *params;int lineno;NodeKind nodekind;union kindStmtKind stmt;ExpKind exp;DeclarationKind declaration;kind;struct MyStruct TokenType op;int val;char *name;int size;attr;ExpType type;TreeNode;extern int EchoSource;extern int TraceScan;extern int TraceParse;extern int TraceAnalyze;ext

17、ern int TraceCode;extern int Error;#endif3.2.2 scan.c最主要的过程是GetToken,它消耗输入字符并根据DFA图返回下一个被识别的记号。这个实现利用了双重嵌套情况分析，以及一个有关状态的大型情况列表，在大列表中是基于当前输入字符的单独列表。记号本身被定义成globals.h中的枚举类型。扫描程序的状态也被定义为一个枚举类型，位于扫描程序之中。扫描程序使用了三个全局变量，文件变量source，listing.在globals.h中声明且在main.c中被分配和初始化的整型变量lineno。由getToken过程完成的额外的簿记如下所述：表re

18、served和过程reservedlookup完成位于由getToken的主要循环识别的标识符之后的保留字的查找，currentToken的值也随之改变。标志变量save被用作指示是否将第一个字符增加到tokenString之上；由于需要包括空白格和非消耗的先行，因此这些东西都是必要的。到扫描程序的字符输入由getNextChar函数提供，该函数将一个256字符缓冲区内部的lineBuf中的字符取到扫描程序中，如果已经耗尽了这个缓冲区，且假设每一次都获取了一个新的源代码行，那么getNextChar就利用fget从source文件更新该缓冲区。最后由于从INUM和INID到最终状态的转换是非消

19、耗的。可以通过一个ungetnextChar的过程在输入缓冲区的反填一个字符来完成这一任务。#include globals.h#include util.h#include scan.htypedef enum START, INASSIGN, INCOMMENT,INENDCOMMENT,INNUM, INID, DONE,INLT,INRT ,INNEQStateType;char tokenStringMAXTOKENLEN+1;#define BUFLEN 1024static char lineBufBUFLEN;static int linepos=0;static int bu

20、fsize=0;/getNextChar 从lineBuf获得下一个非空字符，读入新的一行如果lineBuf 耗尽static char getNextCHar(void)if (!(lineposbufsize)lineno+;if (fgets(lineBuf,BUFLEN-1,source)if (EchoSource)fprintf(listing,%4d,%s,lineno,lineBuf);bufsize=strlen(lineBuf);linepos=0;return lineBuflinepos+;else return EOF;else return lineBuflinep

21、os+; / backtracks one character in lineBufstatic void ungetNextChar(void)linepos-;/查找表的保留字static struct char *str;TokenType tok;reservedWordsMAXRESERVED=if,IF,int,INT,else,ELSE,return,RETURN,void,VOID,while,WHILE;/查找一个标识符,看看这是否是一个保留字/使用线性搜索static TokenType reservedLookup(char *s)int i;for(i=0;i)stat

22、e = INRT;else if (c = )state = INLT;else if (c = !)state = INNEQ;elsestate = DONE;switch (c)default:currentToken = ERROR;break;case EOF:save = FALSE;currentToken = ENDFILE;break;case :currentToken = LBRACKET;break;case :currentToken = RBRACKET;break;case ,:currentToken = COMMA;break;case +:currentTo

23、ken = PLUS;break;case -:currentToken = MINUS;break;case *:currentToken = TIMES;break;case :currentToken = LBRACE;break;case :currentToken = RBRACE;break;case (:currentToken = LPAREN;break;case ):currentToken = RPAREN;break;case ;:currentToken = SEMI;break;break;/*=注释改动=*/case INENDCOMMENT:if (c = *&

24、getNextCHar() = /) /token是*且下一个token是/则结束注释save = FALSE;state = START; /注释不作处理，直到注释结束，elsesave = FALSE;state = INENDCOMMENT;break;case INCOMMENT:if (c = *) /“/”后是*则进入注释/ungetNextChar();save = FALSE; state = INENDCOMMENT; /若是注释开头，转入注释结尾处理else if (c = EOF)state = DONE;currentToken = ENDFILE;else / “/”

25、后不是*则为除法ungetNextChar();save = FALSE;currentToken = OVER;state = DONE;break;/*=赋值改动=*/case INASSIGN:state = DONE;if (c = =) /下一个仍是等号就为相等currentToken = EQ;else /否则回退，ungetNextChar();save = FALSE;currentToken = ASSIGN;break;/*=小于等于=*/case INLT:state = DONE;if (c = =)currentToken = LTEQ;elseungetNextCh

26、ar();save = FALSE;currentToken = LT;break;/*=大于等于=*/case INRT:state = DONE;if (c = =)currentToken = RTEQ;elseungetNextChar();save = FALSE;currentToken = RT;break;/*=不等于=*/case INNEQ:state = DONE;if (c = =)currentToken = NEQ;elseungetNextChar();save = FALSE;currentToken = ERROR;break;case INNUM:if (!

27、 isdigit(c)ungetNextChar();save = FALSE;state = DONE;currentToken = NUM;break;case INID:if (!isalpha(c)ungetNextChar();save = FALSE;state = DONE;currentToken = ID;break;case DONE:default:fprintf(listing, Scanner Bug:state=%dn, state);state = DONE;currentToken = ERROR;break;if (save) & (tokenStringIn

28、dex );fprintf(listing, Syntax error at line %d: %s, lineno, message);Error = TRUE;static void match(TokenType expected)if (token = expected)token = getToken();elsesyntaxError(unexpected token-);printToken(token, tokenString);fprintf(listing, );TreeNode * stmt_sequence(void)TreeNode *t = statement();

29、TreeNode *p = t;while (token != ENDFILE) & (token != RBRACE) )TreeNode *q;/match(SEMI);q = statement();if (token != RBRACE)if (q != NULL)if (t = NULL)t = p = q;elsep-sibling = q;p = q;return t;TreeNode * statement(void)TreeNode *t = NULL;switch (token)case IF:t = if_stmt();break;case WHILE:t = while

30、_stmt();break;case ID: /若为ID不直接进行赋值，进入 exp()至factor()，将赋值加入至factor()t = exp();break;case RETURN:t = return_stmt();break;case INT:t = int_stmt();break;case VOID:t = void_stmt();break;case SEMI:match(SEMI);break;default:syntaxError(unexpected token - );printToken(token, tokenString);token = getToken()

31、;break;return t;TreeNode *declaration(void)TreeNode *t = newDeclarationNode(token);if (t != NULL)/名称token = getToken();/ID赋给 = copyString(tokenString);token = getToken();/token是( 则为函数声明if (token = LPAREN)t-kind.declaration = FunctionK;match(LPAREN);TreeNode *paramets = parameter(

32、); /函数参数匹配if (paramets != NULL)t-child0 = paramets;match(RPAREN);match(LBRACE);/匹配函数体TreeNode *body = stmt_sequence();if (body = NULL)syntaxError(error body！ );elset-child1 = body;match(RBRACE);/token后不是（则是变量声明else/普通变量类型t-kind.declaration = VarK;/进入数组类型if (token = LBRACKET)match(LBRACKET);t-kind.de

33、claration = ArrayK;t-attr.size = atoi(tokenString);token = getToken();match(RBRACKET);match(SEMI);return t;TreeNode *parameter(void)TreeNode *t = NULL;if (token = VOID)match(VOID);/结束else if (token = RBRACE)return t;/有参数elset = newDeclarationNode(token);token = getToken(); = copyString(to

34、kenString);token = getToken();/数组if (token = LBRACKET)t-kind.declaration = ArrayK;match(LBRACKET);t-attr.size = 0;match(RBRACKET);/IDelset-kind.declaration = VarK;if (token = COMMA)match(COMMA);t-sibling = parameter();return t;TreeNode *if_stmt(void)TreeNode *t = newStmtNode(IfK);match(IF);if (t !=

35、NULL)match(LPAREN);t-child0 = exp();match(RPAREN);if (t != NULL)/如果带大括号if (token = LBRACE)match(LBRACE);while (token != RBRACE)t-child1 = statement();match(RBRACE);/无括号elset-child1 = statement();if (token = ELSE)match(ELSE);if (t != NULL)/如果带大括号if (token = LBRACE)match(LBRACE);while (token != RBRACE

36、)t-child2 = statement();match(RBRACE);/无括号elset-child2 = statement();return t;TreeNode *while_stmt(void)TreeNode *t = newStmtNode(WhileK);match(WHILE);TreeNode *p = NULL;match(LPAREN);while (token != RPAREN)if (t-child0 = NULL)p = exp();t-child0 = p;elsep = p-child0;p = exp();match(RPAREN);/while函数大

37、括号可有可无/如果有括号if (token = LBRACE)match(LBRACE);while (token!=RBRACE)t-child1 = statement();match(RBRACE);/无elset-child1 = statement();if (token = SEMI)match(SEMI);return t;TreeNode *return_stmt(void)TreeNode *t = newStmtNode(ReturnK); = copyString(tokenString);match(RETURN);if (token != SEM

38、I)t-child0 = exp();match(SEMI);return t;TreeNode *int_stmt(void)TreeNode *t = newDeclarationNode(INT);match(INT); = copyString(tokenString);match(ID);/函数if (token = LPAREN)match(LPAREN);t-kind.declaration = FunctionK;if (token = VOID)match(VOID);else/函数参数匹配inFunction();match(RPAREN);/函数体m

39、atch(LBRACE);while (token != RBRACE)statement();match(RBRACE);/数组else if (token = LBRACKET)t-kind.exp = Array_expK;match(LBRACKET);t-child0 = exp();match(RBRACKET);/变量if (token = SEMI)t-kind.declaration = VarK;match(SEMI);return t;/void 函数TreeNode *void_stmt(void)TreeNode *t = newDeclarationNode(VOID);match(VOID); = copyString(tokenString);match(ID);match(LPAREN);if (token = VOID)match(VOID);elseinFunction();match(RPAREN);match(LBRACE);while (token!=RBRACE)statement();match(RBRACE);return t;/