C-Minus词法分析和语法分析设计编译器编译原理课程设计.doc

编译原理课程设计报告课题名称： c- minus词法分析和语法分析设计 提交文档学生姓名： x x x 提交文档学生学号： xxxxxxxxxx 同组 成 员 名 单： x x x 指导 教 师 姓 名： x x 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间：2015年6月10日1. 课程设计目标实验建立c-编译器。只含有扫描程序（scanner）和语法分析（parser）部分。2. 分析与设计c-编译器设计的整体框架，本实验实现扫描处理和语法分析程序（图中粗黑部分）。 2.1 、扫描程序scanner部分2.1.1系统设计思想设计思想：根据dfa图用switch-case结构实现状态转换。 惯用词法：1 语言的关键字：else if int return void while2 专用符号：+ - * / = = != = ; , ( ) /* */3 其他标记是id和num，通过下列正则表达式定义： id = letter letter* num = digit digit* letter = a|.|z|a|.|z digit = 0|.|9大写和小写字母是有区别的4 空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开id、num关键字。5 注释用通常的c语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套说明：当输入的字符使dfa到达接受状态的时候，则可以确定一个单词了。初始状态设置为start，当需要得到下一个token时，取得次token的第一个字符，并且按照dfa与对此字符的类型分析，转换状态。重复此步骤，直到done为止，输出token类型。当字符为“/”时，状态转换为slah再判断下一个字符，如果为“*”则继续转到incomment，最后以“*”时转到endcomment状态，表明是注释，如果其他的则是字符停滞于当前字符，并且输出“/”。2.1.2程序流程图2.1.3 各文件或函数的设计说明扫描程序用到:scanner.h,scanner.cpp scanner.h：声明词法状态，词法分析/dfa中的状态typedef enumstart = 1, innum, inid, indbsym, done dfastate;/定义的token的类型(31种)，分别对应于else、if、int、return、void、while、+、-、*、/、=、=、!=、=、;、,、(、)、/*、*/、num、id、错误、结束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,rbbracket,lcomment,rcomment,num,id,error,endfile tokentype;/定义的token结构体，包括类型、对应的串、所在代码的行号struct tokentokentype tokentype;string tokenstring;int lineno; /每种tokentype对应的串，如tokentypestringelse=elseconst string tokentypestring32 = other, else, if, 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 scanner:定义scanner.cpp中函数 scanner.cpp文件函数说明void scanner : scan()：设置输出结果界面以及设置各种输出状态。if(scansuccess=false)cout词法分析出错！endl;elsecout词法分析成功了！endl;printtoken();/*输出token到文件token.txt中*/正在删除注释void scanner : deletecomments()tokentype scanner : returntokentype(string s)/返回token的类型dfastate scanner : chartype(char c)/返回字符的类型typedef enum endfile,error, if,else,int,return,void,while, /关键字id,num, assign,plus,minus,times,over,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-specifier id(parans) compound-stmt 7.params-params-list|void 8.param-list-param-list,param|param 9.param-type-specifier id|type-specifier id 10.compound-stmt-local-declarations statement-list 11.local-declarations-local-declarations var-declaration|empty 12.statement-list-statement-list statement|empty 13.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-var=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)|var|call|num 27.call-id(args) 28.args-arg-list|empty 29.arg-list-arg-list,expression|expression2.1.2语法分析程序流程图 2.1.3 各文件或函数的设计说明语法分析程序包括：parser.cpp,parser.h parser.cpp： parser : parser()/界面设计 token parser : gettoken()/获取scanner中保存在tokenlist数组中的token，并且每次获取完之后数组下标指向下一个void parser : syntaxerror(string s)/出错处理void parser : match(tokentype ex)/匹配出错treenode * parser : declaration(void)/类型匹配错误treenode * parser : param_list(treenode * k)/k可能是已经被取出来的voidk，但又不是(void)类型的参数列表，所以一直传到param中去，作为其一个子节点 parse.h：对parse.c的函数声明 /19种节点类型，分别表示int、id、void、数值、变量声明、数组声明、函数声明、函数声明参数列表、函数声明参数、复合语句体、if、while、return、赋值、运算、数组元素、函数调用、函数调用参数列表、未知节点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);/输出语法树到文件/treenode定义 包括子节点、兄弟节点、所处行号、节点类型、属性、表达式返回类型typedef struct treenode treenode * newnode(nodekind k);/根据节点类型新建节点treenode * declaration_list(void);treenode * declaration(void);treenode * params(void);treenode * param_list(treenode * k);treenode * param(treenode * k);treenode * compound_stmt(void);treenode * 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 * k);treenode * additive_expression(treenode * k);treenode * term(treenode * k);treenode * factor(treenode * k);treenode * call(treenode * k);treenode * args(void);2.1.4 测试程序说明根据附录a后面的例子，程序输入两个整数，计算并打印出它们的最大公因子，保存为a.txt。/* a program to perform eucilds algorithm to compute gcd. */int gcd (int u, int v) 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. 程序代码实现按文件列出主要程序代码, 添加必要的注释.scanner.cpp:#include #include #include #include #include scanner.h#includeusing namespace std;/*name: 词法分析器copyright: author: xxxdate: 19-05-14 12:00description: 提取出token*/scanner : scanner()scansuccess = true;charindex = 0;str = ;commentflag = true;soursestring = ;linecount = 0;void scanner : scan()cout开始词法分析.endl;bool doublesym = false;getsoursestringfromfile(soursefile.txt);int state = start;linecount = 0;char ch;while(state6)ch = getnextchar();if(0=ch)token t;t.lineno = linecount;t.tokenstring = ;t.tokentype = endfile;tokenlist.push_back(t);break;if(start=state)/初始状态和空格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=state)/letterstate = chartype(ch);if(state!=inid)state = done;elsestr += ch;else if(indbsym=state)/除了=!之外的各种符号if(=ch)str += ch;doublesym = true;elsedoublesym = false;state = done;if(done=state)/接收状态int tp = 0;if(n=ch)tp = 1;token t;t.lineno = linecount-tp;t.tokenstring = str;t.tokentype = returntokentype(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词法分析出错！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(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=ch)/文件结束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)/结束状态，处理commentflag = true;state = 1;if(!commentflag)cout注释错误，没有结束符！endl;scansuccess = false;elsecout注释已经成功删除！endl;tokentype scanner : returntokentype(string s)/返回token的类型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 = 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;else 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)/返回字符的类型if( =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(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)/关键字string tp = ;for(int i = 0; iwidth-t.tokenstring.length(); i+)tp += ;fout_tokenkeyword：headst.tokenstring tptokentypestringt.tokentype=7&t.tokentype=27)/符号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; iwidth-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)/错误string tp = ;for(int i = 0; iwidth-t.tokenstring.length(); i+)tp += ;fout_token error：headst.tokenstring tptokentypestringt.tokentypeendl;else if(t.tokentype=endfile)/结束fout_token linecount: ;fout_tokent.tokenstring tokentypestringt.tokentypeendl;if(linecountt.lineno)break;linecount+;fin.close();fout_token.close();scanner.h:#include#includeusing namespace std;/定义的token的类型(31种)，分别对应于else、if、int、return、void、while、+、-、*、/、=、=、!=、=、;、,、(、)、/*、*/、num、id、错误、结束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,rbbracket,lcomment,rcomment,num,id,error,endfile tokentype;typedef enumstart = 1, innum, inid, indbsym, done dfastate;/定义的token结构体，包括类型、对应的串、所在代码的行号struct tokentokentype tokentype;string tokenstring;int lineno; /每种tokentype对应的串，如tokentypestringelse=elseconst string tokentypestring32 = other, else, if, 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;/词法分析是否成功的标志void getsoursestringfromfile(string s);/通过提供的文件名获取源代码void deletecomments();/删除注释void scan();/词法分析，将分析的token放在tokenlist数组中scanner();token gettokenat(int);/根据下标从tokenlist数组中获取tokenprivate:dfastate chartype(char);/返回字符的类型，如：空格2：数字3：字母等char getnextchar();/获取到下一个字符void backtolastchar();tokentype returntokentype(string s);/根据字符串返回token类型void printtoken();/将词法分析好的token输出到文件token.txt中string soursestring;/获取源代码的字符串int charindex;/配合getnextchar()，指定要取的字符位置string str;/在分析过程中保存token对应的串bool commentflag;/标注注释开始的标志int linecount;/对行号计数，每次获取到/n就自增vector tokenlist;/保存的token序列;parser.cpp:#include scanner.h#include parser.h#include #include using namespace 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开始语法分析.endl;syntaxtree = parse();printtree(syntaxtree);if(error)cout语法分析过程出错！endl;elsecout语法分析成功！endl;token parser : gettoken()/获取scanner中保存在tokenlist数组中的token，并且每次获取完之后数组下标指向下一个lasttoken = currenttoken;currenttoken = scanner.gettokenat(tokenindex+);return currenttoken;void parser : syntaxerror(string s) fout_trees syntax error at line lasttoken.lineno 出错附近token:lasttoken.tokenstring token类型：tokentypestringlasttoken.tokentypeendl; error = true;void parser : match(tokentype ex)if(currenttoken.tokentype=ex) gettoken();else syntaxerror(匹配+tokentypestringex+出错);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_treeparamske