最新四川大學(xué)-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 = 0;/ 讀取的字符在 lineBuf 的位置static int EOF_FLAG = false ;static i

2、nt bufsize = 0; /lineBuf 的長度static char lineBufBUFLEN;FILE * source;char tokenStringMAXTOKENLEN+1; string output; / 輸出文件enum TokenType ENDFILE,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;enum

3、 StateType START,INASSIGN,INCOMMENT,INNUM,INID,DONE,PRECOMMENT,AFTERCOMMENT ;struct char * str; TokenType tok;ReserverWords6= "if" ,IF, "else" ,ELSE, "int" ,INT, "return" ,RETURN, "void" ,VOID, "w hile" ,WHILE ;void UnGetNextChar() if (!EOF

4、_FLAG) linepos-;int GetNextChar()if (!(linepos<bufsize)lineno+;if (fgets(lineBuf,BUFLEN-1,source) bufsize=strlen(lineBuf);linepos=0;return lineBuflinepos+; else EOF_FLAG=true ; return EOF;else return lineBuflinepos+;TokenType ReservedLookUp( char * s)int i;for (i = 0; i < 6; i+)if (!strcmp(s,R

5、eserverWordsi.str)return ReserverWordsi.tok;return ID;TokenType GetToken() 精品文檔StateType state = START;/初始狀態(tài)為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 =

6、INNUM; else if (isalpha(c) state = INID;else if (c ='<' )|(c='>' )|(c='=' )|(c='!')state = INASSIGN; assign+= char (c);else if (c =' ' ) | (c ='t') | (c ='n')save = false ;else if (c ='/')save = false ;state = PRECOMMENT; else sta

7、te = DONE; switch (c) case EOF:save = false ;CurrentToken = ENDFILE; break ;case '+':CurrentToken = PLUS; break ; case '-'casecase('case')casebreak ;INCOMMENT:casecasecasecasecasecasedefaultsave = falseif(c = EOF)''''''''elseifCurrentToken =MIN

8、US;break ;CurrentToken =break ;CurrentToken =break ;CurrentToken =break ;CurrentToken =break ;CurrentToken =break ;CurrentToken =break ;CurrentToken =break ;CurrentToken =break ;CurrentToken =break ;CurrentToken =break ;state = DONE;CurrentToken = ENDFILE;(c =state = AFTERCOMMENT;TIMES;LPAREN;RPAREN

9、;SEMI;LBRACKET;RBRACKET;LBRACE;RBRACE;COMMA;ERROR;else state=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 = false ;

10、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)UnGetNextChar();save = false ; state = DONE; CurrentToken = NUM; break

11、;case INID: if (!isalpha(c) UnGetNextChar(); save = false ; state = DONE;CurrentToken = ID; break ;case PRECOMMENT: if (c= '*') state=INCOMMENT; save= false ; else UnGetNextChar();CurrentToken=OVER; state=DONE; break ;case AFTERCOMMENT: save= false ; if (c= '/') state=START; else if

12、(c= '*') state=AFTERCOMMENT; else state=INCOMMENT; break ;case DONE:default :state = DONE; CurrentToken = ERROR; break ; if (save)&&(tokenStringIndex<=MAXTOKENLEN) tokenStringtokenStringIndex+=(char )c;if (state=DONE) tokenStringtokenStringIndex='0'if (CurrentToken=ID) Cur

13、rentToken=ReservedLookUp(tokenString); return CurrentToken; enum NodeKind / 節(jié)點類型 FuncK,IntK,IdK,ParamsK,ParamK,CompK,ConstK,CallK,ArgsK,VoidK,Var_De clK,Arry_DeclK,Arry_ElemK,AssignK/*,WhileK*/ ,OpK,Selection_StmtK,Iteration_StmtK,Return_StmtK ; struct /節(jié)點類型和字符串關(guān)系 string str;"ParamK",Arry_

14、"IteNodeKind nk; nodekind18 = "Funck" ,FuncK, "IntK" ,IntK, "IdK" ,IdK, "ParamsK" ,ParamsK, ,ParamK, "CompK" ,CompK, "ConstK" ,ConstK, "CallK" ,CallK, "ArgsK" ,ArgsK, "VoidK" ,VoidK, "Var_DeclK"

15、,Var_DeclK, "Arry_DeclK" DeclK, "Arry_ElemK" ,Arry_ElemK, "AssignK" ,AssignK, /*"WhileK",WhileK,*/ "OpK" ,OpK, "Selection_StmtK" ,Selection_StmtK, ration_StmtK" ,Iteration_StmtK, "Return_StmtK" ,Return_StmtK;struct /符號與字符串關(guān)系

16、string str; TokenType tk;Ope11"/"= "=" ,ASSIGN, "=" ,EQ, "<" ,LT,"+" ,PLUS, "-" ,MINUS, "*" ,TIMES,OVER, ">" ,GT, ">=" ,GEQ, "!=" ,NEQ, "<=" ,LEQ;string OpeLookUp(TokenType tk) /

17、 操作符轉(zhuǎn)換為字符串 int i;for (i=0;i<11;i+) if (tk=Opei.tk) return Opei.str;string Change(NodeKind nk) /節(jié)點類型轉(zhuǎn)換為字符串int i;for (i=0;i<19;i+) if (nk=nodekindi.nk)return nodekindi.str; break ;TokenType token;struct TreeNodestructTreeNode * child4;structTreeNode * sibling;int lineno;NodeKind nodekind;union T

18、okenType op; int val; const char * 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(

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

20、ode * p);TreeNode * term(TreeNode * p);TreeNode * factor(TreeNode * p);TreeNode * 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) else strcpy(t,s); return t;void match(TokenType expected)if

21、(token=expected) 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->childi = NULL; t->sibling = NULL;t->nodekind = kind;t->line

22、no = lineno; if (kind=OpK|kind=IntK|kind=IdK) if (kind=IdK) t-> ="" if (kind=ConstK) t->attr.val = 0; return t; TreeNode * declaration_list(void )/declaration_list->declaration_list declaration | declaration TreeNode * t = declaration。；TreeNode * p =t;while (token!=INT)&a

23、mp;&(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； else p->sibling=q; p=q;match(ENDFILE);return t;TreeNode * declaration( void )TreeNode * t = NULL;TreeNode * p

24、 = 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);q-> = copyString(tokenString); match(ID);if (token=LPAREN)t = newNode(FuncK);t->

25、child0 = p;/p 是 t 子節(jié)點t->child1 = q;match(LPAREN);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 子節(jié)點t->child1 = a;match(LBRACKET);s = newNode(ConstK);s->attr.val = atoi(tok

26、enString);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 * params( void )/params_list | voidTreeNode * t = newNode(ParamsK);TreeNode * p = NULL; if (to

27、ken=VOID) p = newNode(VoidK);match(VOID);if (token=RPAREN) if (t!=NULL) t->child0 = p; else / 參數(shù)列表為(void id,)t->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);

28、TreeNode * p = t;k = NULL; /沒有要傳給 param 的VoidK ,所以將 k設(shè)為NULL while (token=COMMA)TreeNode * q = NULL;match(COMMA);q = param(k); if (q!=NULL) if (t=NULL) t=p=q; else p->sibling = q; p = q; return t;TreeNode * param(TreeNode * k) TreeNode * t = newNode(ParamK);TreeNode * p = NULL;TreeNode * q = NULL;

29、if (k=NULL&&token=VOID) p = newNode(VoidK); match(VOID);else if (k=NULL&&token=INT) p = newNode(IntK); match(INT); else if (k!=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=L

30、BRACKET&&(t->child1!=NULL) match(LBRACKET);t->child2 = newNode(IdK); 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(RBRACE);return t;T

31、reeNode * 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); else if (token=VOID)TreeNode * q1 = newNode(VoidK); p->child0 = q1;match(I

32、NT);if (p!=NULL)&&(token=ID)TreeNode * q2 = newNode(IdK);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); else mat

33、ch(SEMI);if (p!=NULL) if (t=NULL) t = q = p;else q->sibling = p; q = p; return t;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。

34、；if (q!=NULL)if (t=NULL) t = p = 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 RETURN:t = return_stmt();break ;case LBRACE:t = compound_stmt();break ;case ID: cas

35、e SEMI: case LPAREN: case NUM: t = expression_stmt();break ;default :token = GetToken();break ; return t;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)ma

36、tch(ELSE);if (t!=NULL) t->child2 = 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 = statement。； return t;TreeNode * return_stmt( void )TreeNode

37、* t = newNode(Return_StmtK);match(RETURN);if (token=SEMI)match(SEMI);return t; else if (t!=NULL)t->child0 = expression。； match(SEMI); return t;TreeNode * expression_stmt( void )TreeNode * t = NULL; if (token=SEMI) match(SEMI); return t; else t = expression。； match(SEMI); return t;TreeNode * expre

38、ssion( 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。； return p;

39、else /simple_expression 中的 var 和 call 類型的情況 t = simple_expression(t);return t;TreeNode * var( void )TreeNode * t = NULL;TreeNode * p = NULL;TreeNode * q = NULL;if (token=ID)p = newNode(IdK);p-> = copyString(tokenString);match(ID);if (token=LBRACKET) match(LBRACKET);q = expression。； match

40、(RBRACKET);t = newNode(Arry_ElemK);t->child0 = 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 | LT=token | LEQ=token | NEQ=token)TreeNode * q = newNode(OpK);q->attr.op = token;q-

41、>child0 = t;t = q；match(token);t->child1 = additive_expression(k);return t;return t;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)

42、;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 = token;q->child0 = t;t = q;match(token);q->child1 = factor(k);return t;TreeNode * factor(TreeNode * k) TreeNode * t = NULL;if (k!=NULL) /k 為

43、上面?zhèn)飨聛淼囊呀?jīng)解析出來的以ID開頭的var,可能為call或var if (token=LPAREN && k->nodekind!=Arry_ElemK)/callt = call(k); else t = k; else /沒有從上面?zhèn)飨聛淼膙ar switch (token) case LPAREN:match(LPAREN); t = expression。； match(RPAREN); break ; case ID:k = var();if (LPAREN=token && k->nodekind!=Arry_ElemK) t = c

44、all(k); else /如果是連續(xù)計算，進入這一步 t=k; break ; case NUM:t = newNode(ConstK);if (t!=NULL)&&(token=NUM) t->attr.val = atoi(tokenString); match(NUM);break ; defaulttoken = GetToken(); break ; return t;TreeNode * call(TreeNode * k) TreeNode * t = newNode(CallK); if (k!=NULL)t->child0 = k; match(

45、LPAREN);if (token=RPAREN) match(RPAREN); return t; else if (k!=NULL) t->child1 = args(); match(RPAREN); 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 * q; match(COMMA);

46、q = expression。； if (q!=NULL)if (s=NULL) (s = p = q;) else ( p->sibling = q; p = q;)if (s!=NULL)( t->childO = s;) return t;)int blank_number=O;void PreOrder(TreeNode* t) (string blank= "" ;int i;for (i=O;i<blank_number;i+) (blank+="")if (t!=NULL) (if (t->nodekind=OpK)

47、 (cout«blank« "Op:" «OpeLookUp(t->attr.op)«endl;output+=blank+ "Op:" +OpeLookUp(t->attr.op)+ "n" ) else if (t->nodekind=ldK) (cout«blank«Change(t->nodekind)<<" «t->«endl;output+=blank+Change(t->nodekind)+" +t->attr,name+ "n")else if (t->nodekind=ConstK)cout«blank«Change(t->nodekind)<< ":" «t->attr.val«endl; int n=t->att