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

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、实现状态转换. 惯用词法：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语言符号/ * . . . * /围起来.注释可以放在任何空白出现地位置(即注释不能放在标记内)

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

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

5、EN,LMBRACKET,RMBRACKET,LBBRACKET,RBBRACKET,LCOMMENT,RCOMMENT,NUM,ID,ERROR,ENDFILE TokenType。/定义地Token结构体，包括类型、对应地串、所在代码地行号struct TokenTokenType tokenType。string tokenS lineNo。 /每种TokenType对应地串，如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中函数 scanner.cpp文件函数说明void Scanner : scan()：设置输出结果界面以及设置各种输出状态.if(scanSuccess=false)cout词法分析出

7、错！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

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 10.compound-stmt-local-declarations statement-list 11.local-declarations-local-declarations var-declaration|empty 12.statement-list-statement-list statement|emp

10、ty 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.express

11、ion-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-(expres

12、sion)|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(s

13、tring 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

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)。/输出语法

15、树到文件/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)。Tr

16、eeNode * 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(Tree

17、Node * 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,

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

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

20、(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(

21、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 = retur

22、nTokenType(str)。tokenList.push_back(t)。if(ERROR=t.tokenType)scanSuccess = 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词

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 : getSourseStringFr

24、omFile(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()

25、。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)/结束状态，处理c

26、ommentFlag = 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=whi

27、le)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 = RPAR

28、EN。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)/返回字符地

29、类型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)。ifstre

30、am 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

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

32、 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)/错误stri

33、ng 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_To

34、ken.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,LBBRA

35、CKET,RBBRACKET,LCOMMENT,RCOMMENT,NUM,ID,ERROR,ENDFILE TokenType。typedef enumSTART = 1, INNUM, INID, INDBSYM, DONE DFAState。/定义地Token结构体，包括类型、对应地串、所在代码地行号struct TokenTokenType tokenType。string tokenS lineNo。 /每种TokenType对应地串，如tokenTypeStringELSE=ELSEconst string tokenTypeString32 = OTHER, EL

36、SE, 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)。

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 p

38、rintToken()。/将词法分析好地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 name

39、space 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语法分析过程出错！e

40、ndl。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.tok

41、enString 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 In

42、tK: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_TreeParamsKendl。break。case ParamK:fout_TreeParamKendl。break。case CompK:fout_TreeCompKendl。break。case Selection_StmtK:fout_