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

编译原理课程设计报告课题名称： 编译原理课程设计 C-语言词法与语法分析器的实现 提交文档学生姓名： 提交文档学生学号： 同组 成 员 名 单： 指导 教 师 姓 名： 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间： 年 月 日C-词法与语法分析器的实现1.课程设计目标（1）题目实用性C-语言拥有一个完整语言的基本属性，通过编写C-语言的词法分析和语法分析，对于理解编译原理的相关理论和知识有很大的作用。通过编写C-语言词法和语法分析程序，能够对编译原理的相关知识：正则表达式、有限自动机、语法分析等有一个比较清晰的了解和掌握。（2）C-语言的词法说明 语言的关键字：else if int return void while 所有的关键字都是保留字，并且必须是小写。专用符号：+ - * / = = != = ; , ( ) /* */其他标记是ID和NUM，通过下列正则表达式定义：ID = letter letter*NUM = digit digit*letter = a|.|z|A|.|Zdigit = 0|.|9 注：ID表示标识符，NUM表示数字，letter表示一个字母，digit表示一个数字。 小写和大写字母是有区别的。 空格由空白、换行符和制表符组成。空格通常被忽略。 注释用通常的c语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套。（3）程序设计目标能够对一个程序正确的进行词法及语法分析。2.分析与设计（1）设计思想a. 词法分析词法分析的实现主要利用有穷自动机理论。有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。通过有穷自动机理论能够容易的设计出词法分析器。b. 语法分析语法分析采用递归下降分析。递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。（2）程序流程图程序主流程图： 词法分析: 语法分析： 读取程序读取程序进行递归下降分析匹配或建立树对输入的字符进行匹配判断对应输出各行代码的词法分析结果输出程序对应的语法树词法分析子流程图：Start否是Num是否为dight是否为num否否是ID是否为alpha是否为id否是是否为=是否为, );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 * declaration_list(void)TreeNode * t= declaration();TreeNode * p= t;while (token=INT) | (token=VOID) ) TreeNode *q = declaration();if (q!=NULL) if (t=NULL) t = p = q;else /* now p cannot be NULL either */p-sibling = q;p = q;return t;TreeNode * declaration(void) TreeNode * t = NULL;switch (token)case VOID : case INT : t = newStmtNode(DecK);if(token = INT)t-type =Integer;elset-type = Void;match(token);switch (token)case ID: = copyString(tokenString);t-kind.stmt = VarDK;match(ID);switch (token)case LZKH:t-kind.stmt = VarDK;t-type = IntArray;match(LZKH);match(NUM);match(RZKH);match(SEMI);break;case LPAREN:t-kind.stmt = FunDK;match(LPAREN);t-child0 = params();match(RPAREN);t-child1 = compound_stmt();break;default: match(SEMI);break;break;default:syntaxError(unexpected token - );printToken(token,tokenString);token = getToken();break;break;default : syntaxError(unexpected token - );printToken(token,tokenString);token = getToken();break; /* end case */return t;TreeNode * params(void)TreeNode * t = NULL;if(token = VOID)match(token);t = newStmtNode(ParamList); t-child0 = newStmtNode(ParamK); t-child0-type = Void;else if(token = RPAREN)t=NULL;elset = param_list();return t;TreeNode * param_list(void)TreeNode * t = newStmtNode(ParamList);int i = 1;t-child0 = param();while(token != RPAREN) match(DOT);t-childi = param();i+;return t;TreeNode * param(void)TreeNode * t = NULL;match(INT);t= newStmtNode(ParamK);t-type=Integer;=copyString(tokenString);match(ID);if(token = LZKH)t-type=IntArray;match(LZKH);match(RZKH);return t;TreeNode * compound_stmt(void)TreeNode * t = newStmtNode(ComK);match(LDKH);t-child0 = local_declarations();t-child1 = statement_list();match(RDKH);return t;TreeNode * local_declarations(void)TreeNode * t = newStmtNode(LocalDecK);int i=0;while(token = INT | token = VOID)t-childi = declaration();i+;return t;TreeNode * statement_list(void)TreeNode * t = newStmtNode(StmtList);int i=0;while(token != RDKH)t-childi =statement();i+;return t;TreeNode * statement(void)TreeNode * t ;switch (token) case IF : t = if_stmt(); break;case WHILE : t = while_stmt(); break;case ID :case SEMI:t = expression_stmt(); break;case RETURN : t = return_stmt(); break;case LDKH : t=compound_stmt();break;default : syntaxError(unexpected token - );printToken(token,tokenString);token = getToken();break; /* end case */return t;TreeNode * expression_stmt(void) TreeNode * t = newStmtNode(ExpstmtK);if(token = SEMI)match(SEMI);elset = expression();match(SEMI);return t;TreeNode * if_stmt(void)TreeNode * t = newStmtNode(IfK);if(t!=NULL)match(IF);match(LPAREN);t-child0 = expression();match(RPAREN);t-child1 = statement();if (token=ELSE)match(ELSE); if (t!=NULL) t-child2 = newStmtNode(ElseK); t-child2-child0 = statement();return t;TreeNode * while_stmt(void) TreeNode * t = newStmtNode(WhileK);match(WHILE);match(LPAREN);if (t!=NULL) t-child0 = expression();match(RPAREN);if (t!=NULL) t-child1 = statement();return t;TreeNode * return_stmt(void)TreeNode * t = newStmtNode(RetK);if(token = RETURN)match(RETURN);if(token = SEMI)match(SEMI);elset-child0 = expression();match(SEMI);return t;TreeNode * expression(void)TreeNode * t = simple_exp();return t;TreeNode* var(void)TreeNode* t = newExpNode(IdK);if (t!=NULL) & (token=ID) = copyString(tokenString);match(ID);if(token = LZKH)match(token);t-type = ArrayUnit;t-child0 = expression();match(RZKH);return t;TreeNode * simple_exp(void)TreeNode * t = additive_expression();if(t!=NULL)if (token = LT | token = LE| token = MT | token = ME|token =EQ|token =NEQ)TreeNode * p = newExpNode(OpK);if(p!=NULL)p-attr.op = token;p-child0 = t;match(token);p-child1 = additive_expression();t=p;return t;TreeNode* additive_expression(void)TreeNode * t = term();while(token = PLUS | token = MINUS)TreeNode * p = newExpNode(OpK);p-attr.op = token;p-child0 = t;match(token);p-child1 = term();t = p;return t;TreeNode * term(void) TreeNode * t = factor();while (token=TIMES)|(token=OVER) TreeNode * p = newExpNode(OpK);if (p!=NULL) p-child0 = t;p-attr.op = token;match(token);p-child1 = factor();t = p;return t;TreeNode * factor(void) TreeNode * t = NULL;switch (token) case NUM :t = newExpNode(ConstK);if (t!=NULL) & (token=NUM)t-attr.val = atoi(tokenString);match(NUM);break;case ID :t = var();if (token = ASSIGN)TreeNode* p = newStmtNode(AssignK); = ;match(token);p-child0 = expression();t = p;if (token = LPAREN )TreeNode * p = newStmtNode(CallK); = ;t=p;match(token);p-child0 = args();match(RPAREN);break;case LPAREN :match(LPAREN);t = expression();match(RPAREN);break;default:syntaxError(unexpected token - );printToken(token,tokenString);token = getToken();break;return t;TreeNode * args(void)TreeNode * t = newStmtNode(ArgList);if(token != RPAREN)t-child0 = arg_list();return t;elsereturn NULL;TreeNode * arg_list(void)TreeNode * t = newStmtNode(ArgK);int i = 1;if(token != RPAREN)t-child0 = expression();while(token!=RPAREN)match(DOT);t-childi = expression();i+;return t;TreeNode * parse(void) TreeNode * t;token = getToken();t =declaration_list();if (token!=ENDFILE)syntaxError(Code ends before filen);return t;scan.cpp#include globals.h#include util.h#include scan.h/*对扫描的字符进行匹配判断*/TokenType getToken(void) /* index for storing into tokenString */ int tokenStringIndex = 0; /* holds current token to be returned */ TokenType currentToken; /* current state - always begins at START */ StateType state = START; /* flag to indicate save to tokenString */ int save; while (state != DONE) int c = getNextChar(); save = TRUE; switch (state) case START: if (isdigit(c) state = INNUM; else if (isalpha(c) state = INID; else if (c = =) state = INEQUAL; else if (c = ) state = INME; else if (c = ) | (c = t) | (c = n) save = FALSE; else if (c= !) state = INNEQ; else if (c = /) if(getNextChar()!=*) ungetNextChar(); state = DONE; currentToken = OVER; break; else save = FALSE; state = INCOMMENT; else state = DONE; switch (c) case EOF: save = FALSE; currentToken = ENDFILE; break; case +: currentToken = PLUS; break; case -: currentToken = MINUS; break; case *: currentToken = TIMES; break; case (: currentToken = LPAREN; break; case ): currentToken = RPAREN; break; case ;: currentToken = SEMI; break; case : currentToken=LZKH; break; case : currentToken=RZKH; break; case : currentToken=LDKH; break; case : currentToken=RDKH; break;case ,: currentToken=DOT; break; default: currentToken = ERROR; break; break; case INCOMMENT: save = FALSE; if (c = EOF) state = DONE; currentToken = ERROR; else if(c=*) if(getNextChar()=/) state = START; elseungetNextChar(); break; case INNEQ: state=DONE;if(c=)currentToken=NEQ;else ungetNextChar();save=FALSE;currentToken=ERROR; break; case INEQUAL: state = DONE; if (c = =) currentToken = EQ; else /* backup in the input */ ungetNextChar(); currentToken = ASSIGN; break; case INNUM: if (!isdigit(c) /* backup in the input */ ungetNextChar(); save = FALSE; state = DONE; currentToken = NUM; break; case INID: if (!isalpha(c) /* backup in the input */ ungetNextChar(); save = FALSE; state = DONE; currentToken = ID; break; case INLE: state = DONE; if(c= =)currentToken = LE; else /* backup in the input */ ungetNextChar(); currentToken = LT; break; case INME: state = DONE; if(c= =)currentToken = ME; else /* backup in the input */ ungetNextChar(); currentToken = MT; break; case DONE: default: /* should never happen */ fprintf(listing,Scanner Bug: state= %dn,state); state = DONE; currentToken = ERROR; break; if (save) & (tokenStringIndex = MAXTOKENLEN) tokenStringtokenStringIndex+ = (char) c; if (state = DONE) tokenStringtokenStringIndex = 0; if (currentToken = ID) currentToken = reservedLookup(tokenString); if (TraceScan) fprintf(listing,t%d: ,lineno); printToken(currentToken,tokenString); return currentToken; /* end getToken */Util.cpp#include globals.h#include util.hvoid printToken(TokenType token, const char* tokenString)/*根据对应的判断输出判断结果*/switch(token) case ELSE:case IF:case INT:case RETURN:case VOID:case WHILE:fprintf(listing, reserved word: %sn, tokenString);break;case LT:fprintf(listing,n);break;case NEQ:fprintf(listing,!=n);break;case ASSIGN:fprintf(listing,=n);break;case DOT:fprintf(listing,n);break;case LZKH:fprintf(listing,n);break; case RZKH:fprintf(listing,n);break;case LDKH:fprintf(listing,n);break;case RDKH:fprintf(listing,n);break;case LZS:fprintf(listing,/*n);break;case RZS:fprintf(listing,*/n);break;case ME:fprintf(listing,=n);break;case LE:fprintf(listing,=n);break;case NUM:fprintf(listing,NUM,val= %sn,tokenString);break;case ID:fprintf(listing,ID, name= %sn,tokenString);break;case ERROR:fprintf(listing,ERROR: %sn,tokenString);break;default:fprintf(listing,Unknown token: %dn,token);/*this function is used to establish the new stmt node*/TreeNode * newStmtNode(StmtKind kind)TreeNode * t = (TreeNode *)malloc(sizeof(TreeNode);int i;if(t=NULL)fprintf(listing, Out of memory error at line %dn,lineno);elsefor(i=0;ichildi=NULL;t-sibling=NULL;t-nodekind=StmtK;t-kind.stmt=kind;t-lineno=lineno;return t;/* Function newExpNode creates a new expression node for syntax tree construction*/TreeNode * newExpNode(ExpKind kind)TreeNode * t = (TreeNode *)malloc(sizeof(TreeNode);int i;if(t=NULL)fprintf(listing, Out of memory error at line %dn,lineno);elsefor(i=0;ichildi=NULL;t-sibling=NULL;t-nodekind=ExpK;t-kind.exp=kind;t-lineno=lineno;t-type=Void;return t;char * copyString(char * s)int n;char * t;if(s=NULL)return NULL;n=strlen(s)+1;t=(char *)malloc(n);/*其作用是在内存的动态存储区中分配一个长度为n的连续空间.保存tokenstring*/if(t=NULL)fprintf(listing, Out of memory error at line %dn,lineno);elsestrcpy(t,s);/*该函数是字符串拷贝函数，用来将一个字符串复制到一个字符数组中。*/*例如：strcpy (str1,china)； 作用是将”China这个字符串拷贝到str1数组中*/return t;static int indentno =0;#define INDENT