編譯原理課程設(shè)計(jì)報(bào)告C語(yǔ)言詞法與語(yǔ)法分析器的實(shí)現(xiàn)

1、編譯原理課程設(shè)計(jì)報(bào)告課題名稱(chēng)： 編譯原理課程設(shè)計(jì) c-語(yǔ)言詞法與語(yǔ)法分析器的實(shí)現(xiàn) c-詞法與語(yǔ)法分析器的實(shí)現(xiàn)1.課程設(shè)計(jì)目標(biāo)（1）題目實(shí)用性c-語(yǔ)言擁有一個(gè)完整語(yǔ)言的基本屬性，通過(guò)編寫(xiě)c-語(yǔ)言的詞法分析和語(yǔ)法分析，對(duì)于理解編譯原理的相關(guān)理論和知識(shí)有很大的作用。通過(guò)編寫(xiě)c-語(yǔ)言詞法和語(yǔ)法分析程序，能夠?qū)幾g原理的相關(guān)知識(shí)：正則表達(dá)式、有限自動(dòng)機(jī)、語(yǔ)法分析等有一個(gè)比較清晰的了解和掌握。（2）c-語(yǔ)言的詞法說(shuō)明 語(yǔ)言的關(guān)鍵字：else if int return void while 所有的關(guān)鍵字都是保留字，并且必須是小寫(xiě)。專(zhuān)用符號(hào)：+ - * / = = != = ; , ( ) /* */其他標(biāo)

2、記是id和num，通過(guò)下列正則表達(dá)式定義：id = letter letter*num = digit digit*letter = a|.|z|a|.|zdigit = 0|.|9 注：id表示標(biāo)識(shí)符，num表示數(shù)字，letter表示一個(gè)字母，digit表示一個(gè)數(shù)字。 小寫(xiě)和大寫(xiě)字母是有區(qū)別的。 空格由空白、換行符和制表符組成?？崭裢ǔ１缓雎?。 注釋用通常的c語(yǔ)言符號(hào)/ * . . . * /圍起來(lái)。注釋可以放在任何空白出現(xiàn)的位置(即注釋不能放在標(biāo)記內(nèi))上，且可以超過(guò)一行。注釋不能嵌套。（3）程序設(shè)計(jì)目標(biāo)能夠?qū)σ粋€(gè)程序正確的進(jìn)行詞法及語(yǔ)法分析。2.分析與設(shè)計(jì)（1）設(shè)計(jì)思想a. 詞法分析詞法分

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

4、出各行代碼的詞法分析結(jié)果輸出程序?qū)?yīng)的語(yǔ)法樹(shù)詞法分析子流程圖：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, );/*進(jìn)行語(yǔ)法分析，構(gòu)建語(yǔ)法樹(shù)*/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/*對(duì)掃描的字符進(jìn)行匹配判斷*/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ù)對(duì)應(yīng)的判斷輸出判斷結(jié)果*/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);/*其作用是在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一個(gè)長(zhǎng)度為n的連續(xù)空間.保存tokenstring*/if(t=null)fprintf(listing, out of memory error at line %dn,lin

37、eno);elsestrcpy(t,s);/*該函數(shù)是字符串拷貝函數(shù)，用來(lái)將一個(gè)字符串復(fù)制到一個(gè)字符數(shù)組中。*/*例如：strcpy (str1,china)； 作用是將”china這個(gè)字符串拷貝到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