編譯原理課程設計報告C語言詞法與語法分析器的實現(xiàn)

1、編譯原理課程設計報告課題名稱： 編譯原理課程設計 c-語言詞法與語法分析器的實現(xiàn) c-詞法與語法分析器的實現(xiàn)1.課程設計目標（1）題目實用性c-語言擁有一個完整語言的基本屬性，通過編寫c-語言的詞法分析和語法分析，對于理解編譯原理的相關理論和知識有很大的作用。通過編寫c-語言詞法和語法分析程序，能夠對編譯原理的相關知識：正則表達式、有限自動機、語法分析等有一個比較清晰的了解和掌握。（2）c-語言的詞法說明 語言的關鍵字：else if int return void while 所有的關鍵字都是保留字，并且必須是小寫。專用符號：+ - * / = = != = ; , ( ) /* */其他標

2、記是id和num，通過下列正則表達式定義：id = letter letter*num = digit digit*letter = a|.|z|a|.|zdigit = 0|.|9 注：id表示標識符，num表示數(shù)字，letter表示一個字母，digit表示一個數(shù)字。 小寫和大寫字母是有區(qū)別的。 空格由空白、換行符和制表符組成。空格通常被忽略。 注釋用通常的c語言符號/ * . . . * /圍起來。注釋可以放在任何空白出現(xiàn)的位置(即注釋不能放在標記內)上，且可以超過一行。注釋不能嵌套。（3）程序設計目標能夠對一個程序正確的進行詞法及語法分析。2.分析與設計（1）設計思想a. 詞法分析詞法分

3、析的實現(xiàn)主要利用有窮自動機理論。有窮自動機可用作描述在輸入串中識別模式的過程，因此也能用作構造掃描程序。通過有窮自動機理論能夠容易的設計出詞法分析器。b. 語法分析語法分析采用遞歸下降分析。遞歸下降法是語法分析中最易懂的一種方法。它的主要原理是，對每個非終結符按其產(chǎn)生式結構構造相應語法分析子程序，其中終結符產(chǎn)生匹配命令，而非終結符則產(chǎn)生過程調用命令。因為文法遞歸相應子程序也遞歸，所以稱這種方法為遞歸子程序下降法或遞歸下降法。其中子程序的結構與產(chǎn)生式結構幾乎是一致的。（2）程序流程圖程序主流程圖： 詞法分析: 語法分析： 讀取程序讀取程序進行遞歸下降分析匹配或建立樹對輸入的字符進行匹配判斷對應輸

4、出各行代碼的詞法分析結果輸出程序對應的語法樹詞法分析子流程圖：start否是num是否為dight是否為num否否是id是否為alpha是否為id否是是否為=是否為, );fprintf(listing,syntax error at line %d: %s,lineno,message);error = true;/*判斷讀取的字符*/static void match(tokentype expected)if(token=expected)token=gettoken( );elsesyntaxerror(unexpected token - );printtoken(token,tok

5、enstring);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 * de

6、claration(void) treenode * t = null;switch (token)case void : case int : t = newstmtnode(deck);if(token = int)t-type =integer;elset-type = void;match(token);switch (token)case id: = copystring(tokenstring);t-kind.stmt = vardk;match(id);switch (token)case lzkh:t-kind.stmt = vardk;t-type =

7、intarray;match(lzkh);match(num);match(rzkh);match(semi);break;case lparen:t-kind.stmt = fundk;match(lparen);t-child0 = params();match(rparen);t-child1 = compound_stmt();break;default: match(semi);break;break;default:syntaxerror(unexpected token - );printtoken(token,tokenstring);token = gettoken();br

8、eak;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-child0 = newstmtnode(paramk); t-child0-type = void;else if(token =

9、 rparen)t=null;elset = param_list();return t;treenode * param_list(void)treenode * t = newstmtnode(paramlist);int i = 1;t-child0 = param();while(token != rparen) match(dot);t-childi = param();i+;return t;treenode * param(void)treenode * t = null;match(int);t= newstmtnode(paramk);t-type=integer;t-att

10、=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-child0 = local_declarations();t-child1 = statement_list();match(rdkh);return t;treenode * local_declarations(void)tre

11、enode * t = newstmtnode(localdeck);int i=0;while(token = int | token = void)t-childi = declaration();i+;return t;treenode * statement_list(void)treenode * t = newstmtnode(stmtlist);int i=0;while(token != rdkh)t-childi =statement();i+;return t;treenode * statement(void)treenode * t ;switch (token) ca

12、se 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

13、*/return t;treenode * expression_stmt(void) treenode * t = newstmtnode(expstmtk);if(token = semi)match(semi);elset = expression();match(semi);return t;treenode * if_stmt(void)treenode * t = newstmtnode(ifk);if(t!=null)match(if);match(lparen);t-child0 = expression();match(rparen);t-child1 = statement

14、();if (token=else)match(else); if (t!=null) t-child2 = newstmtnode(elsek); t-child2-child0 = statement();return t;treenode * while_stmt(void) treenode * t = newstmtnode(whilek);match(while);match(lparen);if (t!=null) t-child0 = expression();match(rparen);if (t!=null) t-child1 = statement();return t;

15、treenode * return_stmt(void)treenode * t = newstmtnode(retk);if(token = return)match(return);if(token = semi)match(semi);elset-child0 = expression();match(semi);return t;treenode * expression(void)treenode * t = simple_exp();return t;treenode* var(void)treenode* t = newexpnode(idk);if (t!=null) & (t

16、oken=id) = copystring(tokenstring);match(id);if(token = lzkh)match(token);t-type = arrayunit;t-child0 = expression();match(rzkh);return t;treenode * simple_exp(void)treenode * t = additive_expression();if(t!=null)if (token = lt | token = le| token = mt | token = me|token =eq|token =neq)tr

17、eenode * p = newexpnode(opk);if(p!=null)p-attr.op = token;p-child0 = t;match(token);p-child1 = 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-child0 = t;match(token);p-c

18、hild1 = term();t = p;return t;treenode * term(void) treenode * t = factor();while (token=times)|(token=over) treenode * p = newexpnode(opk);if (p!=null) p-child0 = t;p-attr.op = token;match(token);p-child1 = factor();t = p;return t;treenode * factor(void) treenode * t = null;switch (token) case num

19、: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); = ;match(token);p-child0 = expression();t = p;if (token = lparen )treenode * p = newstmtnode(callk);p-attr

20、.name = ;t=p;match(token);p-child0 = args();match(rparen);break;case lparen :match(lparen);t = expression();match(rparen);break;default:syntaxerror(unexpected token - );printtoken(token,tokenstring);token = gettoken();break;return t;treenode * args(void)treenode * t = newstmtnode(arglist)

21、;if(token != rparen)t-child0 = arg_list();return t;elsereturn null;treenode * arg_list(void)treenode * t = newstmtnode(argk);int i = 1;if(token != rparen)t-child0 = expression();while(token!=rparen)match(dot);t-childi = expression();i+;return t;treenode * parse(void) treenode * t;token = gettoken();

22、t =declaration_list();if (token!=endfile)syntaxerror(code ends before filen);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

23、 currenttoken; /* current state - always begins at start */ statetype state = start; /* 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 =

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

25、: 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=lzkh; break

26、; 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 = st

27、art; elseungetnextchar(); 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; case innum: if (!isdigit(c

28、) /* 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 in

29、put */ ungetnextchar(); currenttoken = lt; break; case inme: state = done; if(c= =)currenttoken = me; else /* backup in the input */ ungetnextchar(); currenttoken = mt; break; case done: default: /* should never happen */ fprintf(listing,scanner bug: state= %dn,state); state = done; currenttoken = e

30、rror; break; if (save) & (tokenstringindex = maxtokenlen) tokenstringtokenstringindex+ = (char) c; if (state = done) tokenstringtokenstringindex = 0; if (currenttoken = id) currenttoken = reservedlookup(tokenstring); if (tracescan) fprintf(listing,t%d: ,lineno); printtoken(currenttoken,tokenstring);

31、 return currenttoken; /* end gettoken */util.cpp#include globals.h#include util.hvoid printtoken(tokentype token, const char* tokenstring)/*根據(jù)對應的判斷輸出判斷結果*/switch(token) case else:case if:case int:case return:case void:case while:fprintf(listing, reserved word: %sn, tokenstring);break;case lt:fprintf

32、(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);bre

33、ak;case rzs:fprintf(listing,*/n);break;case me:fprintf(listing,=n);break;case le:fprintf(listing,=n);break;case num:fprintf(listing,num,val= %sn,tokenstring);break;case id:fprintf(listing,id, name= %sn,tokenstring);break;case error:fprintf(listing,error: %sn,tokenstring);break;default:fprintf(listin

34、g,unknown token: %dn,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 %dn,lineno);elsefor(i=0;ichildi=null;t-sibling=null;t-nodekind=stmt

35、k;t-kind.stmt=kind;t-lineno=lineno;return t;/* function newexpnode creates a new expression node 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 %dn,lineno);elsefor(i=0;ic

36、hildi=null;t-sibling=null;t-nodekind=expk;t-kind.exp=kind;t-lineno=lineno;t-type=void;return t;char * copystring(char * s)int n;char * t;if(s=null)return null;n=strlen(s)+1;t=(char *)malloc(n);/*其作用是在內存的動態(tài)存儲區(qū)中分配一個長度為n的連續(xù)空間.保存tokenstring*/if(t=null)fprintf(listing, out of memory error at line %dn,lin

37、eno);elsestrcpy(t,s);/*該函數(shù)是字符串拷貝函數(shù)，用來將一個字符串復制到一個字符數(shù)組中。*/*例如：strcpy (str1,china)； 作用是將”china這個字符串拷貝到str1數(shù)組中*/return t;static int indentno =0;#define indent indentno+=2#define unindent indentno-=2static void printspaces(void)int i;for(i=0;inodekind=stmtk)switch(tree-kind.stmt)case ifk:fprintf(listing,ifn);break;case whilek:fprintf(listing,whilen);break;case elsek:fprintf(listing,elsen);break;case expstmtk:fprint