四川大学-C-minus语法分析器-纯代码

#include#include#include#includeusingnamespacestd; #defineBUFLEN256#defineMAXLEN256#defineMAXTOKENLEN40#defineMAXCHILDREN4staticintlineno;staticintlinepos=0;/读取的字符在lineBuf的位置staticintEOF_FLAG=false;staticintbufsize=0;/lineBuf的长度staticcharlineBufBUFLEN;FILE*source;chartokenStringMAXTOKENLEN+1;stringoutput;/输出文件 enumTokenTypeENDFILE,ERROR,IF,ELSE,INT,RETURN,VOID,WHILE,ID,NUM,ASSIGN,EQ,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI,LBRACKET,RBRACKET,LBRACE,RBRACE,COMMA,GT,GEQ,NEQ,LEQ; enumStateTypeSTART,INASSIGN,INCOMMENT,INNUM,INID,DONE,PRECOMMENT,AFTERCOMMENT; structchar*str;TokenTypetok;ReserverWords6=if,IF,else,ELSE,int,INT,return,RETURN,void,VOID,while,WHILE; voidUnGetNextChar()if(!EOF_FLAG)linepos-; intGetNextChar()if(!(lineposbufsize)lineno+;if(fgets(lineBuf,BUFLEN-1,source)bufsize=strlen(lineBuf);linepos=0;returnlineBuflinepos+;elseEOF_FLAG=true;returnEOF;elsereturnlineBuflinepos+; TokenTypeReservedLookUp(char*s)inti;for(i=0;i6;i+)if(!strcmp(s,ReserverWordsi.str)returnReserverWordsi.tok;returnID; TokenTypeGetToken()StateTypestate=START;/初始状态为startboolsave;TokenTypeCurrentToken;inttokenStringIndex=0;stringassign=;while(state!=DONE)intc=GetNextChar();save=true;switch(state)caseSTART:if(isdigit(c)state=INNUM;elseif(isalpha(c)state=INID;elseif(c=)|(c=)|(c=!)state=INASSIGN;assign+=char(c);elseif(c=)|(c=t)|(c=n)save=false;elseif(c=/)save=false;state=PRECOMMENT;elsestate=DONE;switch(c)caseEOF: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=LBRACKET;break;case:CurrentToken=RBRACKET;break;case:CurrentToken=LBRACE;break;case:CurrentToken=RBRACE;break;case,:CurrentToken=COMMA;break;default:CurrentToken=ERROR;break;break;caseINCOMMENT:save=false;if(c=EOF)state=DONE;CurrentToken=ENDFILE;elseif(c=*)state=AFTERCOMMENT;elsestate=INCOMMENT;break;caseINASSIGN:if(c=)CurrentToken=EQ;state=DONE;elseif(assign=!)UnGetNextChar();save=false;CurrentToken=ERROR;state=DONE;elseif(assign=)UnGetNextChar();save=false;CurrentToken=ASSIGN;state=DONE;elseif(assign=)UnGetNextChar();save=false;CurrentToken=LT;state=DONE;elseUnGetNextChar();save=false;CurrentToken=GT;state=DONE;break;caseINNUM:if(!isdigit(c)UnGetNextChar();save=false;state=DONE;CurrentToken=NUM;break;caseINID:if(!isalpha(c)UnGetNextChar();save=false;state=DONE;CurrentToken=ID;break;casePRECOMMENT:if(c=*)state=INCOMMENT;save=false;elseUnGetNextChar();CurrentToken=OVER;state=DONE;break;caseAFTERCOMMENT:save=false;if(c=/)state=START;elseif(c=*)state=AFTERCOMMENT;elsestate=INCOMMENT;break;caseDONE:default:state=DONE;CurrentToken=ERROR;break;if(save)&(tokenStringIndex=MAXTOKENLEN)tokenStringtokenStringIndex+=(char)c;if(state=DONE)tokenStringtokenStringIndex=0;if(CurrentToken=ID)CurrentToken=ReservedLookUp(tokenString);returnCurrentToken; enumNodeKind/节点类型FuncK,IntK,IdK,ParamsK,ParamK,CompK,ConstK,CallK,ArgsK,VoidK,Var_DeclK,Arry_DeclK,Arry_ElemK,AssignK/*,WhileK*/,OpK,Selection_StmtK,Iteration_StmtK,Return_StmtK;struct/节点类型和字符串关系stringstr;NodeKindnk;nodekind18=Funck,FuncK,IntK,IntK,IdK,IdK,ParamsK,ParamsK,ParamK,ParamK,CompK,CompK,ConstK,ConstK,CallK,CallK,ArgsK,ArgsK,VoidK,VoidK,Var_DeclK,Var_DeclK,Arry_DeclK,Arry_DeclK,Arry_ElemK,Arry_ElemK,AssignK,AssignK,/*WhileK,WhileK,*/OpK,OpK,Selection_StmtK,Selection_StmtK,Iteration_StmtK,Iteration_StmtK,Return_StmtK,Return_StmtK; struct/符号与字符串关系stringstr;TokenTypetk;Ope11=,ASSIGN,=,EQ,GT,=,GEQ,!=,NEQ,=,LEQ; stringOpeLookUp(TokenTypetk)/操作符转换为字符串inti;for(i=0;i11;i+)if(tk=Opei.tk)returnOpei.str; stringChange(NodeKindnk)/节点类型转换为字符串inti;for(i=0;i19;i+)if(nk=nodekindi.nk)returnnodekindi.str;break; TokenTypetoken;structTreeNodestructTreeNode*child4;structTreeNode*sibling;intlineno;NodeKindnodekind;unionTokenTypeop;intval;constchar*name;attr; TreeNode*declaration_list(void);TreeNode*declaration(void);TreeNode*params(void);TreeNode*param_list(TreeNode*p);TreeNode*param(TreeNode*p);TreeNode*compound_stmt(void);TreeNode*local_declaration(void);TreeNode*statement_list(void);TreeNode*statement(void);TreeNode*expression_stmt(void);TreeNode*selection_stmt(void);TreeNode*iteration_stmt(void);TreeNode*return_stmt(void);TreeNode*expression(void);TreeNode*var(void);TreeNode*simple_expression(TreeNode*p);TreeNode*additive_expression(TreeNode*p);TreeNode*term(TreeNode*p);TreeNode*factor(TreeNode*p);TreeNode*call(TreeNode*p);TreeNode*args(void); char*copyString(char*s)intn;char*t;if(s=NULL)returnNULL;n=strlen(s)+1;t=(char*)malloc(n);if(t=NULL)elsestrcpy(t,s);returnt; voidmatch(TokenTypeexpected)if(token=expected)token=GetToken();elsecoutunexpectedtokenendl; TreeNode*newNode(NodeKindkind)TreeNode*t=(TreeNode*)malloc(sizeof(TreeNode);inti;if(t=NULL);elsefor(i=0;ichildi=NULL;t-sibling=NULL;t-nodekind=kind;t-lineno=lineno;if(kind=OpK|kind=IntK|kind=IdK)if(kind=IdK)=;if(kind=ConstK)t-attr.val=0;returnt; TreeNode*declaration_list(void)/declaration_list-declaration_listdeclaration|declarationTreeNode*t=declaration();TreeNode*p=t;while(token!=INT)&(token!=VOID)&(token!=ENDFILE)token=GetToken();if(token=ENDFILE)break;while(token=INT|token=VOID)TreeNode*q;q=declaration();if(q!=NULL)if(t=NULL)t=p=q;elsep-sibling=q;p=q;match(ENDFILE);returnt; TreeNode*declaration(void)TreeNode*t=NULL;TreeNode*p=NULL;TreeNode*q=NULL;TreeNode*s=NULL;TreeNode*a=NULL;if(token=INT)p=newNode(IntK);match(INT);else/(token=VOID)p=newNode(VoidK);match(VOID); if(p!=NULL&token=ID)q=newNode(IdK);=copyString(tokenString);match(ID);if(token=LPAREN)t=newNode(FuncK);t-child0=p;/p是t子节点t-child1=q;match(LPAREN);t-child2=params();match(RPAREN);t-child3=compound_stmt();elseif(token=LBRACKET)t=newNode(Var_DeclK);a=newNode(Arry_DeclK);t-child0=p;/p是t子节点t-child1=a;match(LBRACKET);s=newNode(ConstK);s-attr.val=atoi(tokenString);match(NUM);a-child0=q;a-child1=s;match(RBRACKET);match(SEMI);elseif(token=SEMI)t=newNode(Var_DeclK);t-child0=p;t-child1=q;match(SEMI);else;else;returnt; TreeNode*params(void)/params_list|voidTreeNode*t=newNode(ParamsK);TreeNode*p=NULL;if(token=VOID)p=newNode(VoidK);match(VOID);if(token=RPAREN)if(t!=NULL)t-child0=p;else/参数列表为(voidid,)t-child0=param_list(p);else/(token=INT)t-child0=param_list(p);returnt; TreeNode*param_list(TreeNode*k)/params_list-params_list,param|paramTreeNode*t=param(k);TreeNode*p=t;k=NULL;/没有要传给param的VoidK，所以将k设为NULLwhile(token=COMMA)TreeNode*q=NULL;match(COMMA);q=param(k);if(q!=NULL)if(t=NULL)t=p=q;elsep-sibling=q;p=q;returnt; TreeNode*param(TreeNode*k)TreeNode*t=newNode(ParamK);TreeNode*p=NULL;TreeNode*q=NULL;if(k=NULL&token=VOID)p=newNode(VoidK);match(VOID);elseif(k=NULL&token=INT)p=newNode(IntK);match(INT);elseif(k!=NULL)p=k;if(p!=NULL)t-child0=p;if(token=ID)q=newNode(IdK);=copyString(tokenString);t-child1=q;match(ID);if(token=LBRACKET&(t-child1!=NULL)/match(LBRACKET);t-child2=newNode(IdK);match(RBRACKET);elsereturnt;else;returnt; TreeNode*compound_stmt(void)TreeNode*t=newNode(CompK);match(LBRACE);t-child0=local_declaration();t-child1=statement_list();match(RBRACE);returnt; TreeNode*local_declaration(void)TreeNode*t=NULL;TreeNode*q=NULL;TreeNode*p=NULL;while(token=INT|token=VOID)p=newNode(Var_DeclK);if(token=INT)TreeNode*q1=newNode(IntK);p-child0=q1;match(INT);elseif(token=VOID)TreeNode*q1=newNode(VoidK);p-child0=q1;match(INT);if(p!=NULL)&(token=ID)TreeNode*q2=newNode(IdK);=copyString(tokenString);p-child1=q2;match(ID);if(token=LBRACKET)TreeNode*q3=newNode(Var_DeclK);p-child3=q3;match(LBRACKET);match(RBRACKET);match(SEMI);elseif(token=SEMI)match(SEMI);elsematch(SEMI); if(p!=NULL)if(t=NULL)t=q=p;elseq-sibling=p;q=p;returnt; TreeNode*statement_list(void)TreeNode*t=statement();TreeNode*p=t;while(IF=token|LBRACKET=token|ID=token|WHILE=token|RETURN=token|SEMI=token|LPAREN=token|NUM=token)TreeNode*q;q=statement();if(q!=NULL)if(t=NULL)t=p=q;elsep-sibling=q;p=q;returnt; TreeNode*statement(void)TreeNode*t=NULL;switch(token)caseIF:t=selection_stmt();break;caseWHILE:t=iteration_stmt();break;caseRETURN:t=return_stmt();break;caseLBRACE:t=compound_stmt();break;caseID:caseSEMI:caseLPAREN:caseNUM:t=expression_stmt();break;default:token=GetToken();break;returnt; TreeNode*selection_stmt(void)TreeNode*t=newNode(Selection_StmtK);match(IF);match(LPAREN);if(t!=NULL)t-child0=expression();match(RPAREN);t-child1=statement();if(token=ELSE)match(ELSE);if(t!=NULL)t-child2=statement();returnt; TreeNode*iteration_stmt(void)TreeNode*t=newNode(Iteration_StmtK);match(WHILE);match(LPAREN);if(t!=NULL)t-child0=expression();match(RPAREN);if(t!=NULL)t-child1=statement();returnt; TreeNode*return_stmt(void)TreeNode*t=newNode(Return_StmtK);match(RETURN);if(token=SEMI)match(SEMI);returnt;elseif(t!=NULL)t-child0=expression();match(SEMI);returnt; TreeNode*expression_stmt(void)TreeNode*t=NULL;if(token=SEMI)match(SEMI);returnt;elset=expression();match(SEMI);returnt; TreeNode*expression(void)TreeNode*t=var();if(t=NULL)/不是以ID开头，只能是simple_expression情况t=simple_expression(t);else/以ID开头，可能是赋值语句，或simple_expression中的var和call类型的情况TreeNode*p=NULL;if(token=ASSIGN)/赋值语句p=newNode(AssignK);match(ASSIGN);p-child0=t;p-child1=expression();returnp;else/simple_expression中的var和call类型的情况t=simple_expression(t);returnt; TreeNode*var(void)TreeNode*t=NULL;TreeNode*p=NULL;TreeNode*q=NULL;if(token=ID)p=newNode(IdK);=copyString(tokenString);match(ID);if(token=LBRACKET)match(LBRACKET);q=expression();match(RBRACKET); t=newNode(Arry_ElemK);t-child0=p;t-child1=q;elset=p;returnt; TreeNode*simple_expression(TreeNode*k)TreeNode*t=additive_expression(k);k=NULL;if(EQ=token|GT=token|GEQ=token|LT=token|LEQ=token|NEQ=token)TreeNode*q=newNode(OpK);q-attr.op=token;q-child0=t;t=q;match(token);t-child1=additive_expression(k);returnt;returnt; TreeNode*additive_expression(TreeNode*k)TreeNode*t=term(k);k=NULL;while(token=PLUS)|(token=MINUS)TreeNode*q=newNode(OpK);q-attr.op=token;q-child0=t;match(token);q-child1=term(k);t=q;returnt; TreeNode*term(TreeNode*k)TreeNode*t=factor(k);k=NULL;while(token=TIMES)|(token=OVER)TreeNode*q=newNode(OpK);q-attr.op=token;q-child0=t;t=q;match(token);q-child1=factor(k);returnt; TreeNode*factor(TreeNode*k)TreeNode*t=NULL;if(k!=NULL)/k为上面传下来的已经解析出来的以ID开头的var,可能为call或varif(token=LPAREN&k-nodekind!=Arry_ElemK)/callt=call(k);elset=k;else/没有从上面传下来的varswitch(token)caseLPAREN:match(LPAREN);t=expression();match(RPAREN);break;caseID:k=var();if(LPAREN=token&k-nodekind!=Arry_ElemK)t=call(k);else/如果是连续计算，进入这一步t=k;break;caseNUM:t=newNode(ConstK);if(t!=NULL)&(token=NUM)t-attr.val=atoi(tokenString);match(NUM);break;default:token=GetToken();break;returnt; TreeNode*call(TreeNode*k)TreeNode*t=newNode(CallK);if(k!=NULL)t-child0=k;match(LPAREN);if(token=RPAREN)match(RPAREN);returnt;elseif(k!=NULL)t-child1=args();match(RPAREN);returnt; TreeNode*args(void)TreeNode*t=newNode(ArgsK);TreeNode*s=NULL;TreeNode*p=NULL;if(token!=RPAREN)s=e