毕业设计编译原理设计报告c语言词法与语法分析器的实现

编译原理课程设计报告课题名称：编译原理课程设计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是否为dightNum是否为id是否为alphaID是否为>,<.,!,=是否为=单符号双符号是否为+,-,*等专用符号专用符号是否为/是否为*是否为*是否为/错误结果over是 否否是否否是是否是否否是是是是否否否3.程序代码实现整个词法以及语法的程序设计在一个工程里面，一共包含了8个文件，分别为main.cpp、parse.cpp、scan.cpp、util.cpp、scan.h、util.h、globals.h、parse.h,其中scan.cpp和scan.h为词法分析程序。

以下仅列出各个文件中的核心代码：Main.cpp#include "globals.h"#define NO_P ARSE FALSE#include "util.h"#if NO_PARSE#include "scan.h"#else#include "parse.h"#endifint lineno=0;FILE * source;FILE * listing;FILE * code;int EchoSource = TRUE;int TraceScan=TRUE;int TraceParse=TRUE;int Error = FALSE;int main(int argc,char * argv[]){TreeNode * syntaxTree;char pgm[120];scanf("%s",pgm);source=fopen(pgm,"r");if(source==NULL){fprintf(stderr,"File %s not found\n",pgm);exit(1);}listing = stdout;fprintf(listing,"\nC COMPILA TION: %s\n",pgm); #if NO_PARSEwhile(getToken()!=ENDFILE);#elsesyntaxTree = parse();if(TraceParse){fprintf(listing,"\nSyntaxtree:\n");printTree(syntaxTree);}#endiffclose(source);return 0;}Parse.cpp#include "globals.h"#include "util.h"#include "scan.h"#include "parse.h"static TokenType token; /* holds current token *//* function prototypes for recursive calls */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_declarations(void);static TreeNode * statement_list(void);static TreeNode * statement(void);static TreeNode * expression_stmt(void);static TreeNode * if_stmt(void);static TreeNode * while_stmt(void);static TreeNode * return_stmt(void);static TreeNode * expression(void);static TreeNode * var(void);static TreeNode * simple_exp(void);static TreeNode * additive_expression(void);static TreeNode * term(void);static TreeNode * factor(void);static TreeNode * args(void);static TreeNode * arg_list(void);static void syntaxError(char * message){ fprintf(listing,"\n>>> ");fprintf(listing,"Syntax error at line %d: %s",lineno,message); Error = TRUE;}/*判断读取的字符*/static void match(TokenType expected){if(token==expected){token=getToken( );}else{syntaxError("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 = V oid;match(token);switch (token){case ID:t-> = copyString(tokenString);t->kind.stmt = V arDK;match(ID);switch (token){case LZKH:t->kind.stmt = V arDK;t->type = IntArray;match(LZKH);match(NUM);match(RZKH);match(SEMI);break;case LPAREN:t->kind.stmt = FunDK;match(LPAREN);t->child[0] = params();match(RP AREN);t->child[1] = 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->child[0] = newStmtNode(ParamK);t->child[0]->type = V oid;}else if(token == RP AREN)t=NULL;else{t = param_list();}return t;}TreeNode * param_list(void){TreeNode * t = newStmtNode(ParamList);int i = 1;t->child[0] = param();while(token != RP AREN){match(DOT);t->child[i] = param();i++;}return t;}TreeNode * param(void){TreeNode * t = NULL;match(INT);t= newStmtNode(ParamK);t->type=Integer;t->=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->child[0] = local_declarations();t->child[1] = statement_list();match(RDKH);return t;}TreeNode * local_declarations(void){TreeNode * t = newStmtNode(LocalDecK);int i=0;while(token == INT || token == VOID){t->child[i] = declaration();i++;}return t;}TreeNode * statement_list(void){TreeNode * t = newStmtNode(StmtList);int i=0;while(token != RDKH){t->child[i] =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);else{t = expression();match(SEMI);}return t;}TreeNode * if_stmt(void){TreeNode * t = newStmtNode(IfK);if(t!=NULL){match(IF);match(LPAREN);t->child[0] = expression();match(RP AREN);t->child[1] = statement();if (token==ELSE){match(ELSE);if (t!=NULL) t->child[2] = newStmtNode(ElseK);t->child[2]->child[0] = statement();} }return t;}TreeNode * while_stmt(void){TreeNode * t = newStmtNode(WhileK);match(WHILE);match(LPAREN);if (t!=NULL) t->child[0] = expression();match(RP AREN);if (t!=NULL) t->child[1] = statement();return t;}TreeNode * return_stmt(void){TreeNode * t = newStmtNode(RetK);if(token == RETURN)match(RETURN);if(token == SEMI)match(SEMI);else{t->child[0] = 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))t-> = copyString(tokenString);match(ID);if(token == LZKH){match(token);t->type = ArrayUnit;t->child[0] = expression();match(RZKH);}return t;}TreeNode * simple_exp(void){TreeNode * t = additive_expression();if(t!=NULL){if (token == L T || token == LE|| token == MT || token == ME||token ==EQ||token ==NEQ) {TreeNode * p = newExpNode(OpK);if(p!=NULL){p->attr.op = token;p->child[0] = t;match(token);p->child[1] = 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->child[0] = t;match(token);p->child[1] = term();t = p;}return t;}TreeNode * term(void){TreeNode * t = factor();while ((token==TIMES)||(token==OVER)){TreeNode * p = newExpNode(OpK);if (p!=NULL) {p->child[0] = t;p->attr.op = token;match(token);p->child[1] = 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);p-> = t->;match(token);p->child[0] = expression();t = p;}if (token == LP AREN ){TreeNode * p = newStmtNode(CallK);p-> = t->;t=p;match(token);p->child[0] = args();match(RP AREN);}break;case LPAREN :match(LPAREN);t = expression();match(RP AREN);break;default:syntaxError("unexpected token -> ");printToken(token,tokenString);token = getToken();break;}return t;}TreeNode * args(void){TreeNode * t = newStmtNode(ArgList);if(token != RPAREN){t->child[0] = arg_list();return t;}elsereturn NULL;}TreeNode * arg_list(void){TreeNode * t = newStmtNode(ArgK);int i = 1;if(token != RPAREN)t->child[0] = expression();while(token!=RP AREN){match(DOT);t->child[i] = expression();i++;}return t;}TreeNode * parse(void){ TreeNode * t;token = getToken();t =declaration_list();if (token!=ENDFILE)syntaxError("Code ends before file\n");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 = ST ART;/* 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 = INLE;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 = LP AREN;break;case ')':currentToken = RP AREN;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;}else{ungetNextChar();}}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;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 = L T;}break;case INME:state = DONE;if(c== '=')currentToken = ME; else{ /* backup in the input */ungetNextChar();currentToken = MT;}break;default: /* should never happen */fprintf(listing,"Scanner Bug: state= %d\n",state);state = DONE;currentToken = ERROR;break;}if ((save) && (tokenStringIndex <= MAXTOKENLEN))tokenString[tokenStringIndex++] = (char) c;if (state == DONE){ tokenString[tokenStringIndex] = '\0';if (currentToken == ID)currentToken = reservedLookup(tokenString);}}if (TraceScan) {fprintf(listing,"\t%d: ",lineno);printToken(currentToken,tokenString);}return currentToken;} /* end getT oken */Util.cpp#include "globals.h"#include "util.h"void printToken(TokenType token, const char* tokenString) {/*根据对应的判断输出判断结果*/switch(token){case ELSE:case IF:case INT:case RETURN:case VOID:case WHILE:fprintf(listing, "reserved word: %s\n", tokenString);break;case L T:fprintf(listing,"<\n");break;case EQ:fprintf(listing,"==\n");break;case LPAREN:fprintf(listing,"(\n");break;case RPAREN:fprintf(listing,")\n");break;case SEMI:fprintf(listing,";\n");break;case PLUS:fprintf(listing,"+\n");break;case MINUS:fprintf(listing,"-\n");break;case TIMES:fprintf(listing,"*\n");break;case OVER:fprintf(listing,"/\n");break;case ENDFILE:fprintf(listing,"EOF\n");break;case MT: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= %s\n",tokenString);break;case ID:fprintf(listing,"ID, name= %s\n",tokenString);break;case ERROR:fprintf(listing,"ERROR: %s\n",tokenString);break;default:fprintf(listing,"Unknown token: %d\n",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 %d\n",lineno);}else{for(i=0;i<MAXCHILDREN;i++){t->child[i]=NULL;}t->sibling=NULL;t->nodekind=StmtK;t->kind.stmt=kind;t->lineno=lineno;}return t;}/* Function newExpNode creates a new expressionnode 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 %d\n",lineno);}else{for(i=0;i<MAXCHILDREN;i++){t->child[i]=NULL;}t->sibling=NULL;t->nodekind=ExpK;t->kind.exp=kind;t->lineno=lineno;t->type=V oid;}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 %d\n",lineno);}else{strcpy(t,s);/*该函数是字符串拷贝函数，用来将一个字符串复制到一个字符数组中。