CMinus词法分析和语法分析设计编译器编译原理课程设计精

《CMinus词法分析和语法分析设计编译器编译原理课程设计精》由会员分享，可在线阅读，更多相关《CMinus词法分析和语法分析设计编译器编译原理课程设计精（55页珍藏版）》请在装配图网上搜索。

1、编译原理课程设计报告课题名称： 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结构

2、实现状态转换。 惯用词法： 语言的关键字：else if int return void while 专用符号：+ - * / = = != = ; , ( ) /* */ 其他标记是ID和NUM，通过下列正则表达式定义： ID = letter letter* NUM = digit digit* letter = a|.|z|A|.|Z digit = 0|.|9大写和小写字母是有区别的 空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字。 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以

3、超过一行。注释不能嵌套说明：当输入的字符使DFA到达接受状态的时候，则可以确定一个单词了。初始状态设置为START，当需要得到下一个token时，取得次token的第一个字符，并且按照DFA与对此字符的类型分析，转换状态。重复此步骤，直到DONE为止，输出token类型。当字符为“/”时，状态转换为SLAH再判断下一个字符，如果为“*”则继续转到INCOMMENT，最后以“*”时转到ENDCOMMENT状态，表明是注释，如果其他的则是字符停滞于当前字符，并且输出“/”。2.1.2程序流程图2.1.3 各文件或函数的设计说明扫描程序用到:scanner.h,scanner.cpp scanner

4、.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,LM

5、BRACKET,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, PL

6、US, 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词法分析出错！end

7、l;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,U

8、EQ,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-specif

9、ier 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.state

10、ment-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=exp

11、ression|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|c

12、all|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)/出错

13、处理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、赋值、运算、数组元素

14、、函数调用、函数调用参数列表、未知节点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);/输出语法树到文件/treeNo

15、de定义 包括子节点、兄弟节点、所处行号、节点类型、属性、表达式返回类型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 * lo

16、cal_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);T

17、reeNode * 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

18、(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: 1

19、9-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

20、= 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)

21、/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(

22、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;

23、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(stri

24、ng 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)/文

25、件结束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

26、= 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 = WHIL

27、E;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(

28、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 |

29、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(sour

30、seFile.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();

31、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.t

32、okenString.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 = ;fo

33、r(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()

34、;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,RBBRAC

35、KET,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

36、, 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);/通过提供的文件名获取

37、源代码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()

38、;/将词法分析好的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;P

39、arser : 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;elsecou

40、t语法分析成功！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 To

41、ken类型：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_Tre

42、eIntKendl;break;case IdK:fout_TreeIdK: attr.nameendl;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_TreeParamsKendl;break;case ParamK:fout_TreeParamKe

43、ndl;break;case CompK:fout_TreeCompKendl;break;case Selection_StmtK:fout_TreeIfendl;break;case Iteration_StmtK:fout_TreeWhileendl;break;case Return_StmtK:fout_TreeReturnendl;break;case AssignK:fout_TreeAssignendl;break;case OpK:fout_TreeOp:;fout_Treeattr.opendl;break;case Arry_ElemK:fout_TreeArry_Ele

44、mKendl;break;case CallK:fout_TreeCallKendl;break;case ArgsK:fout_TreeArgsKendl;break;default:fout_TreeUnknownK：Unknown exp kindendl;break;step+;/进入子节点多输出空格for(i = 0;ichildi!=NULL)printTree(t-childi);step-;/进入兄弟节点时，由于进入子节点时n+了，所以要n-回来，从而输出一样的空格空格t = t-sibling;TreeNode * Parser : newNode(Nodekind kind

45、)TreeNode * p = (TreeNode *)malloc(sizeof(TreeNode);int k;if(p=NULL)cout内存分配出错！endl;elsefor(k = 0;kchildk = NULL; p-sibling = NULL;p-nodekind = kind;p-lineno = currentToken.lineNo;if(kind=OpK | kind=IntK | kind=IdK)p-type = Integer;if(kind=IdK)p-attr.name = ;if(kind=ConstK)p-attr.val = 0;return p;Tr

46、eeNode * Parser : parse(void)TreeNode * t;currentToken = getToken();lastToken = currentToken;t = declaration_list();if(currentToken.tokenType!=ENDFILE) syntaxError(结束错误);return t;TreeNode * Parser : declaration_list() TreeNode * t = declaration();TreeNode * p = t;/在开始语法分析出错的情况下找到int和void型，过滤掉int和void之前的所有Token，防止在开始时出错后面一错百错while(currentToken.tokenType!=INT)&(currentToken.tokenType!=VOID)&(currentToken.tokenType!=ENDFILE) syntaxError();getToken();if(curre