CMinus詞法分析和語(yǔ)法分析設(shè)計(jì)編譯器編譯原理課程設(shè)計(jì)精

1、編譯原理課程設(shè)計(jì)報(bào)告課題名稱(chēng)： c- minus詞法分析和語(yǔ)法分析設(shè)計(jì) 提交文檔學(xué)生姓名： x x x 提交文檔學(xué)生學(xué)號(hào)： xxxxxxxxxx 同組 成 員 名 單： x x x 指導(dǎo) 教 師 姓 名： x x 指導(dǎo)教師評(píng)閱成績(jī)： 指導(dǎo)教師評(píng)閱意見(jiàn)： . . 提交報(bào)告時(shí)間：2015年6月10日1. 課程設(shè)計(jì)目標(biāo)實(shí)驗(yàn)建立c-編譯器。只含有掃描程序（scanner）和語(yǔ)法分析（parser）部分。2. 分析與設(shè)計(jì)c-編譯器設(shè)計(jì)的整體框架，本實(shí)驗(yàn)實(shí)現(xiàn)掃描處理和語(yǔ)法分析程序（圖中粗黑部分）。 2.1 、掃描程序scanner部分2.1.1系統(tǒng)設(shè)計(jì)思想設(shè)計(jì)思想：根據(jù)dfa圖用switch-case結(jié)構(gòu)

2、實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換。 慣用詞法：1 語(yǔ)言的關(guān)鍵字：else if int return void while2 專(zhuān)用符號(hào)：+ - * / = = != = ; , ( ) /* */3 其他標(biāo)記是id和num，通過(guò)下列正則表達(dá)式定義： id = letter letter* num = digit digit* letter = a|.|z|a|.|z digit = 0|.|9大寫(xiě)和小寫(xiě)字母是有區(qū)別的4 空格由空白、換行符和制表符組成?？崭裢ǔ１缓雎裕怂仨毞珠_(kāi)id、num關(guān)鍵字。5 注釋用通常的c語(yǔ)言符號(hào)/ * . . . * /圍起來(lái)。注釋可以放在任何空白出現(xiàn)的位置(即注釋不能放在標(biāo)記內(nèi))

3、上，且可以超過(guò)一行。注釋不能嵌套說(shuō)明：當(dāng)輸入的字符使dfa到達(dá)接受狀態(tài)的時(shí)候，則可以確定一個(gè)單詞了。初始狀態(tài)設(shè)置為start，當(dāng)需要得到下一個(gè)token時(shí)，取得次token的第一個(gè)字符，并且按照dfa與對(duì)此字符的類(lèi)型分析，轉(zhuǎn)換狀態(tài)。重復(fù)此步驟，直到done為止，輸出token類(lèi)型。當(dāng)字符為“/”時(shí)，狀態(tài)轉(zhuǎn)換為slah再判斷下一個(gè)字符，如果為“*”則繼續(xù)轉(zhuǎn)到incomment，最后以“*”時(shí)轉(zhuǎn)到endcomment狀態(tài)，表明是注釋?zhuān)绻渌膭t是字符停滯于當(dāng)前字符，并且輸出“/”。2.1.2程序流程圖2.1.3 各文件或函數(shù)的設(shè)計(jì)說(shuō)明掃描程序用到:scanner.h,scanner.cpp sc

4、anner.h：聲明詞法狀態(tài)，詞法分析/dfa中的狀態(tài)typedef enumstart = 1, innum, inid, indbsym, done dfastate;/定義的token的類(lèi)型(31種)，分別對(duì)應(yīng)于else、if、int、return、void、while、+、-、*、/、=、=、!=、=、;、,、(、)、/*、*/、num、id、錯(cuò)誤、結(jié)束typedef enumelse = 1,if,int,return,void,while,plus,minus,times,over,lt,leq,gt,geq,eq,neq,assign,semi,comma,lparen,rpar

5、en,lmbracket,rmbracket,lbbracket,rbbracket,lcomment,rcomment,num,id,error,endfile tokentype;/定義的token結(jié)構(gòu)體，包括類(lèi)型、對(duì)應(yīng)的串、所在代碼的行號(hào)struct tokentokentype tokentype;string tokenstring;int lineno; /每種tokentype對(duì)應(yīng)的串，如tokentypestringelse=elseconst string tokentypestring32 = other, else, if, int, return, void, whil

6、e, plus, minus, times, over, lt, leq, gt, geq, eq, neq, assign, semi, comma, lparen, rparen, lmbracket, rmbracket, lbbracket, rbbracket, lcomment, rcomment, num, id, error, endfile;class scanner:定義scanner.cpp中函數(shù) scanner.cpp文件函數(shù)說(shuō)明void scanner : scan()：設(shè)置輸出結(jié)果界面以及設(shè)置各種輸出狀態(tài)。if(scansuccess=false)cout詞法分析出

7、錯(cuò)！endl;elsecout詞法分析成功了！endl;printtoken();/*輸出token到文件token.txt中*/正在刪除注釋void scanner : deletecomments()tokentype scanner : returntokentype(string s)/返回token的類(lèi)型dfastate scanner : chartype(char c)/返回字符的類(lèi)型typedef enum endfile,error, if,else,int,return,void,while, /關(guān)鍵字id,num, assign,plus,minus,times,over

8、,eq,ueq,lt,lparen,rparen,semi,bt,lq,bq, dou,lzgh,rzgh,ldgh,rdgh,/特殊字符：= + - * / = != declaration-list 2.declaration-list-declaration-list declaration | declaration 3.declaration-var-declaration|fun-declaration 4.var-declaration-type-specifier id;|type-specfier idnum 5.type-specifier-int|void 6.fun-s

9、pecifier id(parans) compound-stmt 7.params-params-list|void 8.param-list-param-list,param|param 9.param-type-specifier id|type-specifier id pound-stmt-local-declarations statement-list 11.local-declarations-local-declarations var-declaration|empty 12.statement-list-statement-list statement|empty 13.

10、statement-expression-stmt|compound-stmt|selection-stmt|iteration-stmt|return-stmt 14.expression-stmt-expression;|; 15.selection-stmt-if(expression)statement|if(expression)statement else statement 16.iteration-stmt-while(expression)statement 17.return-stmt-return ;|return expression; 18.expression-va

11、r=expression|simple-expression 19.var-id|idexpression 20.simple-expression-additive-expression relop additive-expression|additive-expression 21.relop-=|=|=|!= 22.additive-expression-additive-expression addop term|term 23.addop-+|- 24.term-term mulop factor|factor 25.mulop-*|/ 26.factor-(expression)|

12、var|call|num 27.call-id(args) 28.args-arg-list|empty 29.arg-list-arg-list,expression|expression2.1.2語(yǔ)法分析程序流程圖 2.1.3 各文件或函數(shù)的設(shè)計(jì)說(shuō)明語(yǔ)法分析程序包括：parser.cpp,parser.h parser.cpp： parser : parser()/界面設(shè)計(jì) token parser : gettoken()/獲取scanner中保存在tokenlist數(shù)組中的token，并且每次獲取完之后數(shù)組下標(biāo)指向下一個(gè)void parser : syntaxerror(string

13、s)/出錯(cuò)處理void parser : match(tokentype ex)/匹配出錯(cuò)treenode * parser : declaration(void)/類(lèi)型匹配錯(cuò)誤treenode * parser : param_list(treenode * k)/k可能是已經(jīng)被取出來(lái)的voidk，但又不是(void)類(lèi)型的參數(shù)列表，所以一直傳到param中去，作為其一個(gè)子節(jié)點(diǎn) parse.h：對(duì)parse.c的函數(shù)聲明 /19種節(jié)點(diǎn)類(lèi)型，分別表示int、id、void、數(shù)值、變量聲明、數(shù)組聲明、函數(shù)聲明、函數(shù)聲明參數(shù)列表、函數(shù)聲明參數(shù)、復(fù)合語(yǔ)句體、if、while、return、賦值、運(yùn)算

14、、數(shù)組元素、函數(shù)調(diào)用、函數(shù)調(diào)用參數(shù)列表、未知節(jié)點(diǎn)typedef enum intk, idk, voidk, constk, var_declk, arry_declk, funk, paramsk, paramk, compk, selection_stmtk, iteration_stmtk, return_stmtk, assignk, opk, arry_elemk, callk, argsk, unkownk nodekind;typedef enum void,integer exptype;ofstream fout_tree(tokentree.txt);/輸出語(yǔ)法樹(shù)到文件/t

15、reenode定義 包括子節(jié)點(diǎn)、兄弟節(jié)點(diǎn)、所處行號(hào)、節(jié)點(diǎn)類(lèi)型、屬性、表達(dá)式返回類(lèi)型typedef struct treenode treenode * newnode(nodekind k);/根據(jù)節(jié)點(diǎn)類(lèi)型新建節(jié)點(diǎn)treenode * declaration_list(void);treenode * declaration(void);treenode * params(void);treenode * param_list(treenode * k);treenode * param(treenode * k);treenode * compound_stmt(void);treenode

16、 * 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 * expression(void);treenode * var(void);treenode * simple_expression(treenode *

17、 k);treenode * additive_expression(treenode * k);treenode * term(treenode * k);treenode * factor(treenode * k);treenode * call(treenode * k);treenode * args(void);2.1.4 測(cè)試程序說(shuō)明根據(jù)附錄a后面的例子，程序輸入兩個(gè)整數(shù)，計(jì)算并打印出它們的最大公因子，保存為a.txt。/* a program to perform eucilds algorithm to compute gcd. */int gcd (int u, int v

18、) if (v=0) return u; else return gcd(v,u-u/v*v); /* u-u/v*v= u mod v */void main(void) int x; int y; x=input(); y=input(); output(gcd(x,y);3. 程序代碼實(shí)現(xiàn)按文件列出主要程序代碼, 添加必要的注釋.scanner.cpp:#include #include #include #include #include scanner.h#includeusing namespace std;/*name: 詞法分析器copyright: author: xxxda

19、te: 19-05-14 12:00description: 提取出token*/scanner : scanner()scansuccess = true;charindex = 0;str = ;commentflag = true;soursestring = ;linecount = 0;void scanner : scan()cout開(kāi)始詞法分析.endl;bool doublesym = false;getsoursestringfromfile(soursefile.txt);int state = start;linecount = 0;char ch;while(state

20、6)ch = getnextchar();if(0=ch)token t;t.lineno = linecount;t.tokenstring = ;t.tokentype = endfile;tokenlist.push_back(t);break;if(start=state)/初始狀態(tài)和空格state = chartype(ch);if(state!=start)str += ch;else if(innum=state)/digitstate = chartype(ch);if(state!=innum)state = done;elsestr += ch;else if(inid=s

21、tate)/letterstate = chartype(ch);if(state!=inid)state = done;elsestr += ch;else if(indbsym=state)/除了=!之外的各種符號(hào)if(=ch)str += ch;doublesym = true;elsedoublesym = false;state = done;if(done=state)/接收狀態(tài)int tp = 0;if(n=ch)tp = 1;token t;t.lineno = linecount-tp;t.tokenstring = str;t.tokentype = returntoken

22、type(str);tokenlist.push_back(t);if(error=t.tokentype)scansuccess = false;int laststate = chartype(strstr.length()-1);if(laststate=innum | laststate=inid | (laststate=indbsym & doublesym=false)backtolastchar();str = ;state = start;if(doublesym=true)doublesym = false; if(scansuccess=false)cout詞法分析出錯(cuò)！

23、endl;elsecout詞法分析成功了！endl;printtoken();/輸出token到文件token.txt中token scanner : gettokenat(int tokenindex)token token;token.lineno = linecount;token.tokenstring = ;token.tokentype = endfile;if(tokenindextokenlist.size()token = tokenlist.at(tokenindex+);return token;void scanner : getsoursestringfromfile

24、(string path)ifstream fin(path.c_str();string temp; soursestring = ;while(getline(fin,temp)soursestring += temp;soursestring += n; fin.close();charindex = 0;void scanner : deletecomments()cout正在刪除注釋.endl;ofstream fout_sourse(soursefile.txt);int state = 1;char ch;while(state6)ch = getnextchar();if(0=

25、ch)/文件結(jié)束break;if(1=state)if(/=ch)state = 2;elsestate = 1;fout_soursech;else if(2=state)if(*=ch)state = 3;commentflag = false; elsestate = 1;fout_sourse/ch;else if(3=state)if(*=ch)state = 4;elsestate = 3;else if(4=state)if(*=ch)state = 4;else if(/=ch)state = 5;elsestate = 3;if(5=state)/結(jié)束狀態(tài)，處理comment

26、flag = true;state = 1;if(!commentflag)cout注釋錯(cuò)誤，沒(méi)有結(jié)束符！endl;scansuccess = false;elsecout注釋已經(jīng)成功刪除！endl;tokentype scanner : returntokentype(string s)/返回token的類(lèi)型tokentype t;if(s=else)t = else;else if(s=if)t = if;else if(s=int)t = int;else if(s=return)t = return;else if(s=void)t = void;else if(s=while)t =

27、 while;else if(s=+)t = plus;else if(s=-)t = minus;else if(s=*)t = times;else if(s=/)t = over;else if(s=)t = lt;else if(s=)t = gt;else if(s=)t = geq;else if(s=)t = eq;else if(s=!=)t = neq;else if(s=)t = assign;else if(s=;)t = semi;else if(s=,)t = comma;else if(s=()t = lparen;else if(s=)t = rparen;els

28、e if(s=)t = lmbracket;else if(s=)t = rmbracket;else if(s=)t = lbbracket;else if(s=)t = rbbracket;else if(s=/*)t = lcomment;else if(s=*/)t = rcomment;else if(2=chartype(ss.length()-1)t = num;else if(3=chartype(ss.length()-1)t = id;elset = error;return t;dfastate scanner : chartype(char c)/返回字符的類(lèi)型if(

29、=c | n=c | t=c |r=c)return start; else if(c=0&c=a&c=a&c=z)return inid;else if(c= | c= | c=!)return indbsym; elsereturn done;char scanner : getnextchar()if(charindex0)char ch = soursestringcharindex-1;charindex-;if(n=ch)linecount-;void scanner : printtoken()ofstream fout_token(token.txt);ifstream fin

30、(soursefile.txt);string temp; int linecount = 0;int index = 0;while(getline(fin,temp)fout_tokenlinecount: ;fout_tokentempendl;while(indextokenlist.size()token t = tokenlist.at(index);if(linecount=t.lineno)fout_token linecount=1&t.tokentype=6)/關(guān)鍵字string tp = ;for(int i = 0; iwidth-t.tokenstring.lengt

31、h(); i+)tp += ;fout_tokenkeyword：headst.tokenstring tptokentypestringt.tokentype=7&t.tokentype=27)/符號(hào)string tp = ;for(int i = 0; iwidth-t.tokenstring.length(); i+)tp += ;fout_tokensymbols：headst.tokenstring tptokentypestringt.tokentypeendl;else if(t.tokentype=28)/numstring tp = ;for(int i = 0; iwidt

32、h-t.tokenstring.length(); i+)tp += ;fout_token num：headst.tokenstring tptokentypestringt.tokentypeendl;else if(t.tokentype=29)/idstring tp = ;for(int i = 0; iwidth-t.tokenstring.length(); i+)tp += ;fout_token id：headst.tokenstring tptokentypestringt.tokentypeendl;else if(t.tokentype=30)/錯(cuò)誤string tp

33、= ;for(int i = 0; iwidth-t.tokenstring.length(); i+)tp += ;fout_token error：headst.tokenstring tptokentypestringt.tokentypeendl;else if(t.tokentype=endfile)/結(jié)束fout_token linecount: ;fout_tokent.tokenstring tokentypestringt.tokentypeendl;if(linecountt.lineno)break;linecount+;fin.close();fout_token.cl

34、ose();scanner.h:#include#includeusing namespace std;/定義的token的類(lèi)型(31種)，分別對(duì)應(yīng)于else、if、int、return、void、while、+、-、*、/、=、=、!=、=、;、,、(、)、/*、*/、num、id、錯(cuò)誤、結(jié)束typedef enumelse = 1,if,int,return,void,while,plus,minus,times,over,lt,leq,gt,geq,eq,neq,assign,semi,comma,lparen,rparen,lmbracket,rmbracket,lbbracket,r

35、bbracket,lcomment,rcomment,num,id,error,endfile tokentype;typedef enumstart = 1, innum, inid, indbsym, done dfastate;/定義的token結(jié)構(gòu)體，包括類(lèi)型、對(duì)應(yīng)的串、所在代碼的行號(hào)struct tokentokentype tokentype;string tokenstring;int lineno; /每種tokentype對(duì)應(yīng)的串，如tokentypestringelse=elseconst string tokentypestring32 = other, else, if

36、, int, return, void, while, plus, minus, times, over, lt, leq, gt, geq, eq, neq, assign, semi, comma, lparen, rparen, lmbracket, rmbracket, lbbracket, rbbracket, lcomment, rcomment, num, id, error, endfile;class scannerpublic:bool scansuccess;/詞法分析是否成功的標(biāo)志void getsoursestringfromfile(string s);/通過(guò)提供的

37、文件名獲取源代碼void deletecomments();/刪除注釋void scan();/詞法分析，將分析的token放在tokenlist數(shù)組中scanner();token gettokenat(int);/根據(jù)下標(biāo)從tokenlist數(shù)組中獲取tokenprivate:dfastate chartype(char);/返回字符的類(lèi)型，如：空格2：數(shù)字3：字母等char getnextchar();/獲取到下一個(gè)字符void backtolastchar();tokentype returntokentype(string s);/根據(jù)字符串返回token類(lèi)型void printto

38、ken();/將詞法分析好的token輸出到文件token.txt中string soursestring;/獲取源代碼的字符串int charindex;/配合getnextchar()，指定要取的字符位置string str;/在分析過(guò)程中保存token對(duì)應(yīng)的串bool commentflag;/標(biāo)注注釋開(kāi)始的標(biāo)志int linecount;/對(duì)行號(hào)計(jì)數(shù)，每次獲取到/n就自增vector tokenlist;/保存的token序列;parser.cpp:#include scanner.h#include parser.h#include #include using namespace

39、std;parser : parser()step = 0;tokenindex = 0;error = false;string path = a.txt;coutpath;scanner.getsoursestringfromfile(path);scanner.deletecomments();if(scanner.scansuccess)scanner.scan();if(scanner.scansuccess)cout開(kāi)始語(yǔ)法分析.endl;syntaxtree = parse();printtree(syntaxtree);if(error)cout語(yǔ)法分析過(guò)程出錯(cuò)！endl;el

40、secout語(yǔ)法分析成功！endl;token parser : gettoken()/獲取scanner中保存在tokenlist數(shù)組中的token，并且每次獲取完之后數(shù)組下標(biāo)指向下一個(gè)lasttoken = currenttoken;currenttoken = scanner.gettokenat(tokenindex+);return currenttoken;void parser : syntaxerror(string s) fout_trees syntax error at line lasttoken.lineno 出錯(cuò)附近token:lasttoken.tokenstri

41、ng token類(lèi)型：tokentypestringlasttoken.tokentypeendl; error = true;void parser : match(tokentype ex)if(currenttoken.tokentype=ex) gettoken();else syntaxerror(匹配+tokentypestringex+出錯(cuò));void parser : printspace(int n)for(int i = 0; in; i+)fout_treenodekind)case voidk:fout_treevoidkendl;break;case intk:fout_treeintkendl;break;case idk:fout_treeidk: endl;break;case constk:fout_treeconstk: attr.valendl;break;case var_declk:fout_treevar_declkendl;break;case arry_declk:fout_treearry_declkendl;break;case funk:fout_treefunckendl;break;case paramsk:fout_treeparamsken