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

1、#include<fstream>#include<iostream>#include<string>#include<strstream>using namespace std; #define BUFLEN 256#define MAXLEN 256#define MAXTOKENLEN 40#define MAXCHILDREN 4static int lineno;static int linepos

2、 = 0;/读取的字符在lineBuf的位置static int EOF_FLAG = false;static int bufsize = 0;/lineBuf的长度static char lineBufBUFLEN;FILE * source;char tokenStringMAXTOKENLEN+1;string output;/输出文件 enum TokenTypeENDFILE,ERROR,IF,ELSE,INT,R

3、ETURN,VOID,WHILE,ID,NUM,ASSIGN,EQ,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI,LBRACKET,RBRACKET,LBRACE,RBRACE,COMMA,GT,GEQ,NEQ,LEQ; enum StateTypeSTART,INASSIGN,INCOMMENT,INNUM,INID,DONE,PRECOMMENT,AFTERCOMMENT; structchar* str;TokenType tok;ReserverWords6=  "if",I

4、F,"else",ELSE,"int",INT,"return",RETURN,"void",VOID,"while",WHILE  void UnGetNextChar()if (!EOF_FLAG)linepos-; int GetNextChar()if(!(linepos<bufsize)lineno+;if(fgets(lineBuf,BUFLEN-1,source)bufsize=strlen(lineBuf);linepos=0;ret

5、urn lineBuflinepos+;elseEOF_FLAG=true;return EOF;elsereturn lineBuflinepos+; TokenType ReservedLookUp(char * s)int i;for (i = 0; i < 6; i+)if(!strcmp(s,ReserverWordsi.str)return ReserverWordsi.tok;return ID; TokenType

6、 GetToken()StateType state = START;/初始状态为startbool save;TokenType CurrentToken;int tokenStringIndex=0;string assign=""while(state!=DONE)int c=GetNextChar();save = true;switch (state)case START:if (isdigit(c)state =&

7、#160;INNUM;else if (isalpha(c)state = INID;else if (c = '<')|(c='>')|(c='=')|(c='!')state = INASSIGN;assign+=char(c);else if (c = ' ') | (c = 't') 

8、;| (c = 'n')save = false;else if (c = '/')save = false;state = PRECOMMENT;elsestate = DONE;switch (c)case EOF:save = false;CurrentToken = ENDFILE;break;case '+':Curre

9、ntToken = PLUS;break;case '-':CurrentToken = MINUS;break;case '*':CurrentToken = TIMES;break;case '(':CurrentToken = LPAREN;break;case ')':CurrentToken = RPAREN;break;case '':CurrentTok

10、en = SEMI;break;case '':CurrentToken = LBRACKET;break;case '':CurrentToken = RBRACKET;break;case '':CurrentToken = LBRACE;break;case '':CurrentToken = RBRACE;break;case ',':CurrentToken

11、 = COMMA;break;default:CurrentToken = ERROR;break;    break;case INCOMMENT:save = false;if (c = EOF)state = DONE;CurrentToken = ENDFILE;else if (c = '*')state = AFTERCOMMEN

12、T;elsestate=INCOMMENT;break;case INASSIGN:if (c = '=')CurrentToken = EQ;state=DONE;else if(assign="!")UnGetNextChar();save = false;CurrentToken = ERROR;state=DONE;else if(assign="=")UnGetNextChar();save =

13、60;false;CurrentToken =ASSIGN state=DONE;else if(assign="<")UnGetNextChar();save = false;CurrentToken =LT state=DONE;elseUnGetNextChar();save = false;CurrentToken =GT state=DONE;break;case INNUM:if (!isdigit(c)UnGetNextCha

14、r();save = false;state = DONE;CurrentToken = NUM;break;case INID:if (!isalpha(c)UnGetNextChar();save = false;state = DONE;CurrentToken = ID;break;case PRECOMMENT:if(c='*')state=INCOMMENT;save=false;elseUnGetNextChar()

15、;CurrentToken=OVER;state=DONE;break;case AFTERCOMMENT:save=false;if(c='/')state=START;else if(c='*')state=AFTERCOMMENT;elsestate=INCOMMENT;break;case DONE:default:state = DONE;CurrentToken = ERROR;break;if(save)&&(tokenStringIndex<=MAXTOK

16、ENLEN)tokenStringtokenStringIndex+=(char)c;if(state=DONE)tokenStringtokenStringIndex='0'if(CurrentToken=ID)CurrentToken=ReservedLookUp(tokenString);return CurrentToken; enum NodeKind/节点类型FuncK,IntK,IdK,ParamsK,ParamK,CompK,ConstK,CallK,ArgsK,VoidK,Var_DeclK,Arry_DeclK,Arry_ElemK,As

17、signK/*,WhileK*/,OpK,Selection_StmtK,Iteration_StmtK,Return_StmtK; struct/节点类型和字符串关系string str;NodeKind nk;nodekind18=  "Funck",FuncK,"IntK",IntK,"IdK",IdK,"ParamsK",ParamsK,"ParamK",ParamK,"CompK",CompK,"Const

18、K",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",Selecti

19、on_StmtK,"Iteration_StmtK",Iteration_StmtK,"Return_StmtK",Return_StmtK; struct/符号与字符串关系string str;TokenType tk;Ope11=  "=",ASSIGN,"=",EQ,"<",LT,"+",PLUS,"-",MINUS,"*",TIMES,"/",OVER,"

20、;>",GT,">=",GEQ,"!=",NEQ,"<=",LEQ; string OpeLookUp(TokenType tk)/操作符转换为字符串int i;for(i=0;i<11;i+)if(tk=Opei.tk)return Opei.str; string Change(NodeKind nk)/节点类型转换为字符串int i;for(i=0;i<19;i+)if(nk=nodekindi.nk)return

21、60;nodekindi.str;break; TokenType token;struct TreeNodestruct TreeNode *  child4;struct TreeNode *  sibling;int lineno;    NodeKind nodekind;union  TokenType op; int val; const char

22、0;* 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&

23、#160;* 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 *

24、0;expression(void);TreeNode * var(void);TreeNode * simple_expression(TreeNode * p);TreeNode * additive_expression(TreeNode * p);TreeNode * term(TreeNode * p);TreeNode * factor(TreeNode * p);TreeNode * 

25、;call(TreeNode * p);TreeNode * args(void); char * copyString(char *s)int n;char * t;if (s=NULL)return NULL;n=strlen(s)+1;t=(char*)malloc(n);if (t=NULL)elsestrcpy(t,s);return t; void match(TokenType expected)if(token=expe

26、cted)token=GetToken();elsecout<<"unexpected token"<<endl; TreeNode * newNode(NodeKind kind) TreeNode * t = (TreeNode *) malloc(sizeof(TreeNode);int i;if (t=NULL);else for (i=0;i<4;i+) t->child

27、i = NULL;    t->sibling = NULL;    t->nodekind = kind;        t->lineno = lineno;if (kind=OpK|kind=IntK|kind=IdK)if(kind=IdK)t-> = ""i

28、f(kind=ConstK)t->attr.val = 0;return t; TreeNode * declaration_list(void)/declaration_list->declaration_list declaration | declarationTreeNode * t = declaration();TreeNode * p =t; while(token!=INT)&&(token!

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

30、t; 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=V

31、OID)p=newNode(VoidK);match(VOID); if(p!=NULL&&token=ID)q = newNode(IdK);q-> = copyString(tokenString); match(ID);if (token=LPAREN)t = newNode(FuncK);t->child0 = p;   /p是t子节点t->child1 = q;match(LPAREN

32、);t->child2 = params();match(RPAREN);t->child3 = compound_stmt();else if (token=LBRACKET)t = newNode(Var_DeclK);a = newNode(Arry_DeclK);t->child0 = p;   /p是t子节点t->child1 = a;match(LBRACKET);s = 

33、;newNode(ConstK);s->attr.val = atoi(tokenString);match(NUM);a->child0=q;a->child1=s;match(RBRACKET);match(SEMI);else if (token=SEMI)t = newNode(Var_DeclK);t->child0 = p;t->child1 = q;match(SEMI);else;else;return t; TreeNode *

34、 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/参数列表为(void id,) t-&

35、gt;child0 = param_list(p);else/(token=INT)t->child0 = param_list(p);return t; TreeNode * param_list(TreeNode * k)/params_list->params_list,param | paramTreeNode * t = param(k);TreeNode * p = t; 

36、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;return t; TreeNode * param(TreeNode * k)T

37、reeNode * t = newNode(ParamK);TreeNode * p = NULL;TreeNode * q = NULL;if(k=NULL&&token=VOID)p = newNode(VoidK);match(VOID);else if(k=NULL&&token=INT)p = newNode(IntK);match(INT);else if (k!

38、=NULL)p = k;if(p!=NULL)t->child0 = p;if (token=ID)q = newNode(IdK);q-> = copyString(tokenString);t->child1 = q;match(ID);if (token=LBRACKET&&(t->child1!=NULL)/match(LBRACKET);t->child2 = newNode(IdK

39、);match(RBRACKET);else   return t; else return t; TreeNode * compound_stmt(void)  TreeNode * t = newNode(CompK);match(LBRACE);t->child0 = local_declaration();t->child1 = statement_list(); match(

40、RBRACE);return t; 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&#

41、160;* q1 = newNode(IntK);p->child0 = q1;match(INT);else if(token=VOID)TreeNode * q1 = newNode(VoidK);p->child0 = q1;match(INT);if(p!=NULL)&&(token=ID) TreeNode * q2 = newNode(IdK);   

42、60; q2-> = copyString(tokenString);p->child1 = q2;match(ID);if(token=LBRACKET) TreeNode * q3 = newNode(Var_DeclK);p->child3 = q3;match(LBRACKET);match(RBRACKET);match(SEMI);else if(token=SEMI)match(SEMI);elsematch(SEM

43、I);  if(p!=NULL)if(t=NULL)t = q = p;elseq->sibling = p;q = p;return t; TreeNode * statement_list(void)  TreeNode * t = statement();   TreeNode * p = t;while (IF=token&

44、#160;| 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 = 

45、;q;else  p->sibling = q;p = q;return t; TreeNode * statement(void)  TreeNode * t = NULL;switch(token)case IF:t = selection_stmt(); break;case WHILE:t = iteration_stmt(); break;case&#

46、160;RETURN:t = return_stmt(); break;case LBRACE:t = compound_stmt(); break;case ID: case SEMI: case LPAREN: case NUM: t = expression_stmt(); break;default:token = GetToken();break;return t; TreeN

47、ode * 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->c

48、hild2 = statement();return t; 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 

49、;= statement();return t; TreeNode * return_stmt(void)  TreeNode * t = newNode(Return_StmtK);match(RETURN);if (token=SEMI)  match(SEMI);return t;else if(t!=NULL)  t->child0 = expression(); match(SEM

50、I);return t; TreeNode * expression_stmt(void)  TreeNode * t = NULL;if(token=SEMI)   match(SEMI);return t;else t = expression();match(SEMI);return t; TreeNode * expression(void)  TreeNode *&#

51、160;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);

52、p->child0 = t;p->child1 = expression();return p;else /simple_expression中的var和call类型的情况 t = simple_expression(t);   return t; TreeNode * var(void)  TreeNode * t = NULL;TreeNode * p

53、 = NULL;TreeNode * q = NULL;if(token=ID)p = newNode(IdK);p-> = copyString(tokenString); match(ID);if(token=LBRACKET)  match(LBRACKET);q = expression();match(RBRACKET); t = newNode(Arry_ElemK);t->child

54、0 = p;t->child1 = q;elset = p;return t; TreeNode * simple_expression(TreeNode * k)   TreeNode * t = additive_expression(k);k = NULL;if(EQ=token | GT=token | GEQ=token |

55、0;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); return t;return t; TreeNode

56、 * 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

57、->child1 = term(k);t = q;return t; TreeNode * term(TreeNode * k)  TreeNode * t = factor(k);k = NULL;while(token=TIMES)|(token=OVER) TreeNode * q = newNode(OpK);q->attr.op = t

58、oken; q->child0 = t; t = q;match(token);q->child1 = factor(k);return t; TreeNode * factor(TreeNode * k)  TreeNode * t = NULL;if(k!=NULL)/k为上面传下来的已经解析出来的以ID开头的var,可能为call或varif(token=LPAREN &

59、& k->nodekind!=Arry_ElemK) /call t = call(k);else  t = k; else/没有从上面传下来的var switch(token)case LPAREN:match(LPAREN);t = expression();match(RPAREN);break;case ID:k = var();if(LPAREN=token && k

60、->nodekind!=Arry_ElemK)  t = call(k);else/如果是连续计算，进入这一步t=k;break;case NUM:t = newNode(ConstK);if(t!=NULL)&&(token=NUM) t->attr.val = atoi(tokenString); match(NUM);break;default:token = GetToken();break; return t

61、; TreeNode * call(TreeNode * k)  TreeNode * t = newNode(CallK);if(k!=NULL)t->child0 = k;match(LPAREN);if(token=RPAREN)    match(RPAREN);return t;else if(k!=NULL) t->child1 = args();match(RP

62、AREN);return t; TreeNode * args(void)  TreeNode * t = newNode(ArgsK);TreeNode * s = NULL;TreeNode * p = NULL;if(token!=RPAREN)s = expression();p = s;while(token=COMMA)   TreeNode&#

63、160;* q;match(COMMA);q = expression();if(q!=NULL)if(s=NULL)   s = p = q;else  p->sibling = q;p = q;if(s!=NULL)t->child0 = s;return t; int blank_number=0;void PreOrder(TreeNode* t)strin

64、g blank="  "int i;for(i=0;i<blank_number;i+)blank+=" "if(t!=NULL)if(t->nodekind=OpK)cout<<blank<<"Op: "<<OpeLookUp(t->attr.op)<<endl;output+=blank+"Op: "+OpeLookUp(t->attr.op)+"n"else if(t->nodekind=IdK)cout<<blank<<Change(t->nodekind)<<": "<<t-><<endl;output+=blank+Change(t->nodekind)+": "+t->+"n"else if(t->nodekin