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

1、#include#include#include#includeusingnamespacestd; #definebuflen256#definemaxlen256#definemaxtokenlen40#definemaxchildren4staticintlineno;staticintlinepos=0;/读取的字符在linebuf的位置staticinteof_flag=false;staticintbufsize=0;/linebuf的长度staticcharlinebufbuflen;file*source;chartokenstringmaxtokenlen+1;stringo

2、utput;/输出文件 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;reserverw

3、ords6=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+; tok

4、entypereservedlookup(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)casestar

5、t: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=mi

6、nus;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;defaul

7、t: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=)ungetnextch

8、ar();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)ungetnextcha

9、r();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=erro

10、r;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

11、_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,a

12、rry_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=ope

13、i.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);

14、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*itera

15、tion_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;cha

16、r*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=nul

17、l;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)&

18、(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)

19、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

20、=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; tr

21、eenode*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-param

22、s_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

23、=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);

24、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);

25、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;mat

26、ch(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

27、=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:caselpar

28、en: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;

29、 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!=nu

30、ll)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_e

31、xpression中的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);p-a

32、=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|n

33、eq=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

34、(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=lpa

35、ren&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(tok

36、enstring);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