川大编译原理课程设计报告.doc
编译原理课程设计报告 计算机学院 xxxxxxxxxx 编译原理课程设计报告课题名称 C-Minus词法扫描器及语法分析器实现 提交文档学生姓名 提交文档学生学号 同组 成 员 名 单 无 指导 教 师 姓 名 指导教师评阅成绩 指导教师评阅意见 . . 提交报告时间2014年 6月 20日目录1 课程设计目标32 分析与设计32.1 程序结构32.2 程序流程4 3 词法分析43.1 代码结构分析53.2 Token定义63.2.1 Token的定义和类型63.2.2 Token的种别码63.3 DAF分析73.3.1 删除注释DFA73.3.2 词法分析DFA94 语法分析134.1 代码结构分析134.2 分析树节点定义144.2.1 树节点定义和类型144.2.2 各类型节点的描述154.3 递归向下语法分析164.3.1 C-Minus文法164.3.2 递归向下分析过程165 测试结果335.1 流程335.2 词法分析结果345.3 词法分析出错395.4 语法分析结果415.5 语法分析出错446 创新与总结456.1 程序创新点456.1.1程序报错处理456.1.2语法分析程序优化处理456.1.3函数中数组参数改进476.2 总结507 附录507.1 scanner.h源文件507.2 scanner.cpp源文件527.3 parser.h源文件617.4 parser.cpp源文件62 1 课程设计目标结合各章节的构造编译程序的基本理论,用C或C语言,实现一个 C-Minus 小编译程序(包括词法分析,语法分析等重要子程序)。本编译器包括以下两个模块(1) 设计词法分析器利用手工实现方法实现,设计各类别单词的状态转换图,并为不同类别的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括l 将不翻译的注释等符号先滤掉,转换成一个没有注释的程序 l 能够分离并收集程序中字符串的各个单词,并保存与单词记号相关的信息;(2)语法分析利用学习过递归向下的分析方法等,实现对表达式、各种说明语句、控制语句进行语法分析。若语法正确,则用语法制导翻译法进行语义翻译;生成并打印出语法树;若语法错误,要求指出出错性质和出错位置(行号)。2 分析与设计2.1 程序结构本节主要分析程序的代码结构和代码工程文件的划分。(程序由两个类组成 Scanner类和Parser类,分别为词法分析和语法分析类。工程分为四个文件scanner.h、scanner.cpp、parser.h、parser.cpp,分别对应Scanner类和Parser类的声明和实现文件)。本程序采用C语言以面向对象的思想编写,程序分为两部分词法分析(Scanner)和语法分析(Parser),分别将两个处理阶段封装成Scanner类和Parser类,两个类各司其职,分别完成词法分析和语法分析的任务。Scanner类主要的工作是过滤注释、词法分析获取Token。Parser类的主要工作是根据Scanner类词法分析之后的Token进行语法分析,生成语法树,最后并输出语法树。在处理过程中,Scanner类的对象作为Parser类的一个成员变量,供Parser调用。本程序myCompiler包含四个文件,其具体功能如下词法分析scanner.h与词法分析相关的类(Scanner类)的声明scanner.cpp词法分析阶段类(Scanner类)的实现语法分析parser.h与语法分析相关的类(Parser类)的声明parser.cpp语法分析阶段类(Parser类)的实现2.2 程序流程在程序中,Scanner类的对象scanner作为Parser类中的一个成员变量,配合Parser类进行语法分析。它们的关系是这样的Parser类的一个成员变量scanner首先对源程序删除注释,然后进行词法分析获取所有Token,并将获取的Token存储在scanner对象的tokenList(vector类型)中。然后Parser类的语法分析程序就根据tokenList中的Token进行语法分析,生成语法树,最后打印语法树。在这流程之间如果出现分析错误,怎输出相应的错误信息。本程序的流程图如下图 3 词法分析3.1 代码结构分析词法分析阶段的代码被封装成一个类Scanner,scanner.h中主要是Scanner类的声明代码,scanner.cpp中主要是Scanner类的实现代码。Scanner类的代码结构和主要的成员变量和函数如下 图所示 l Scanner调用getSourseStringFromFilestring s,从文件中获取待分析的源代码l Scanner调用deleteComments,将注释过滤掉,如果注释出错,则不进行词法分析l Scanner调用scan,进行词法分析,将分析得到的所有Token保存在Scanner类的成员变量tokenList中,以备语法阶段调用,并将Token输出到文件Token.txt中l Scanner调用getTokenAtint 根据下标从tokenList数组中获取Token以上为Scanner类对外提供的公共函数getSourseStringFromFilestring s(从文件中获取待分析的源代码)、deleteComments(过滤注释)、scan(词法分析主程序)、getTokenAtint(获取数组中Token)。这四个函数构成了词法分析的骨架,在Scanner类中还有其他成员变量和函数,主要作为这四个函数处理过程的中间步骤,为这四个函数服务。此外,其他函数和成员变量的作用和含义如下publicbool scanSuccess;//词法分析是否成功的标志string sourseString;//获取源代码的字符串Scanner;privatestring printSpaceconst int i;DFAState charTypechar;//根据字母返回字符的DFA状态类型void backToLastChar;//回到上一个字符char getNextChar;//获取到下一个字符TokenType getTokenTypestring s;//根据字符串返回Token类型void printToken;//将词法分析好的Token输出到文件Token.txt中int charIndex; //配合getNextChar,指定要取的字符位置string str;//在分析过程中保存Token对应的串bool commentStartFlag;//标注注释开始的标志int lineCount;//对行号计数,每次获取到/n就自增vectorToken tokenList;//保存的Token序列3.2 Token定义3.2.1 Token的定义和类型Token定义//定义的Token结构体,包括类型、对应的串、所在代码的行号struct TokenTokenType tokenType;string tokenString;int lineNo;;Token类型(TokenType)程序中,将Token的类型分为31种,分别对应于else、if、int、return、void、while、、-、*、/、、、、、、、、;、,、、、、、、、/*、*/、num、id、错误、文件结束//定义的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;3.2.2 Token的种别码TokenType的种别码如下表所示,共31种单词符号种别码Value单词符号种别码ValueelseELSE1ASSIGN17ifIF2;SEMI18intINT3,COMMA19returnRETURN4LPAREN20voidVOID5RPAREN21whileWHILE6LMBRACKET22PLUS7RMBRACKET23-MINUS8LBBRACKET24*TIMES9RBBRACKET25/OVER10/*LCOMMENT26LT11*/RCOMMENT27LEQ12numNUM28GT13idID29GEQ14错误ERROR30EQ15结束ENDFILE31NEQ163.3 DAF分析由于词法分析程序分为两个步骤处理删除注释和词法分析获取Token。所以对应有两个DFA,程序分别根据这两个DFA进行编写,现根据DFA分析两程序deleteComments和scan如下3.3.1 删除注释DFADFA描述删除注释的DFA如下所示,一共分为5个状态,在开始状态1时,如果输入的字符为/,则进入状态2,此时有可能进入注释状态,如果在状态2时,输入的字符为*,则进入注释状态,状态将转到3,如果在状态3时,输入的字符为*,则有可能结束注释状态,此时状态将转到状态4,如果在状态4时输入的字符为/,则注释状态结束,状态转移到结束状态。对应的DFA的代码分析删除注释的功能通过Scanner 类的成员函数deleteComments实现,功能是将源代码中的注释过滤掉,将其余代码输出到pureCodeFile.txt文件中。deleteComments函数按照上面的DFA编写,在函数中,state变量表示状态,共分为5个状态l 在状态1时,如果输入的字符为/,则进入状态2,否则仍处在状态1,且输出输入的字符l 在状态2时,(此时可能进入注释状态),如果输入的字符为*,则进入注释状态,状态将转到3,否则跳转到状态1,并输出/和输入的字符l 在状态3时,(此时可能结束注释状态),如果输入的字符为*,此时状态将转到状态4,否则继续在状态3l 在状态4时,如果输入的字符为/,则注释状态结束,状态转移到结束状态相应的DFA代码代码如下所示void ScannerdeleteCommentscout 开始删除注释... endl;ofstream fout_SoursepureCodeFile.txt;int state 1;char ch;while state6ch getNextChar;if 0 ch//文件结束break;if 1 stateif / chstate 2;elsestate 1;fout_Sourse ch;else if 2 stateif * chstate 3;commentStartFlag true;//进入注释elsestate 1;fout_Sourse / ch;//输出前面的/else if 3 stateif * chstate 4;elsestate 3;else if 4 stateif * chstate 4;else if / chstate 5;elsestate 3;if 5 state//结束状态,处理commentStartFlag false;//注释结束state 1;if commentStartFlag //报错cout 注释错误,没有结束符 endl;scanSuccess false;elsecout 成功删除注释 endl;3.3.2 词法分析DFADFA描述词法分析的DFA如下所示,一共分为5个状态START、INNUM、INID、INDBSYM、DONE。状态START表示开始状态,状态INNUM表示数字类型(NUM)Token的状态,状态INID表示字符串类型Token的状态(如关键字和一般的标示符),状态INDBSYM表示双目运算符型Token的状态(如、、、),状态DONE表示接收状态。对应的DFA的代码分析词法分析的功能通过Scanner 类的成员函数scan实现,功能是根据过滤掉注释的源代码获取Token并保存,获取到的Token通过printToken函数输出到Token.txt文件中。scan函数按照上面的DFA编写,在函数中,doubleSym变量表示双目运算符标志,当doubleSym为true时表示INDBSYM状态接收到的字符为,str变量是在词法分析过程中用来存储分析的Token的字符串,如INT型Token在分析过程中得到 int的字符串,变量ch为当前输入的字符。分析到最后,在状态DONE中,根据分析过程中获取的str确定Token的类型,并生成和保存相应的Token。程序一共分为5个状态START、INNUM、INID、INDBSYM、DONE。函数在各状态下的处理分析如下l 在开始状态START时 如果输入的字符为空白符,如空格换行等,则仍在START状态 如果输入的字符为digit,则进入状态INNUM,即可能是数字类型(NUM)Token的状态,同时将ch添加到str中去(str ch) 如果输入的字符为letter,则进入状态INID,即可能是字符串类型Token的状态,同时将ch添加到str中去(str ch) 如果输入的字符为、、、,则进入状态INDBSYM,即可能是双目运算符型Token的状态,同时将ch添加到str中去(str ch) 如果输入的字符为是除以上之外的,则进入状态DONE,同时将ch添加到str中去(str ch),这次输入的字符可能是单目运算符、错误等l 在状态INNUM时 如果输入的字符为digit,则仍停留在INNUM状态,同时将ch添加到str中去(str ch) 如果输入的为其他的字符,则转到DONE状态l 在状态INID时 如果输入的字符为letter,则仍停留在INID状态,同时将ch添加到str中去(str ch) 如果输入的为其他的字符,则转到DONE状态l 在状态INDBSYM时 如果输入的字符为,将双目运算标志赋值为true后转到DONE状态,同时将ch添加到str中去(str ch),并将doubleSym 赋值为true(doubleSym true),表示ch为 如果输入的为其他的字符,则直接转到DONE状态l 在状态DONE时接受状态,根据分析过程中获取的字符串确定Token的类型,并生成和保存相应的Token,同时将str设为空,(以便分析下一个Token)。在DFA中,other表示ch没有被添加到str中后的转移,所以当状态是通过条件other跳转到DONE状态的情况时,则需将分析的字符回退回去(backToLastChar)。相应的DFA代码代码如下void Scannerscancout 开始词法分析... endl;bool doubleSym false;getSourseStringFromFilepureCodeFile.txt;int state START;lineCount 0;char ch;while state6ch getNextChar;if 0 ch//如果遇到文件结束则添加ENDFILE类型tokenToken t;t.lineNo lineCount;t.tokenString ;t.tokenType ENDFILE;tokenList.push_backt;break;if START state//初始状态和空格state charTypech;if state STARTstr ch;else if INNUM state//digitstate charTypech;if state INNUMstate DONE;elsestr ch;else if INID state//letterstate charTypech;if state INIDstate DONE;elsestr ch;else if INDBSYM state//除了之外的各种符号if chstr ch;doubleSym true;elsedoubleSym false;state DONE;if DONE state//接收状态int tp 0;if n ch//遇到换行符行数会自动加1tp 1;Token t;t.lineNo lineCount - tp;//恢复原来行数t.tokenString str;t.tokenType getTokenTypestr;tokenList.push_backt;if ERROR t.tokenTypescanSuccess false;int lastState charTypestrstr.length - 1;if lastState INNUM || lastState INID || lastState INDBSYM str ;state START;if doubleSym truedoubleSym false;if scanSuccess falsecout 词法分析出错 endl;elsecout 词法分析成功 endl;printToken;//输出Token到文件Token.txt中4 语法分析4.1 代码结构分析语法分析阶段的代码被封装成一个类Parser,parser.h中主要是Parser类的声明代码,parser.cpp中主要是Parser类的实现代码。语法分析的过程主要是在语法分析之前进行词法分析,然后通过递归向下分析法根据C-语言的文法进行语法分析,并生成语法树,最后打印语法树。Parser类在其构造函数中完成语法分析,在构造函数Parser()中,首先通过Parser类的scanner成员变量进行词法分析(删除注释、词法分析获取Token),然后通过parse函数开始递归向下分析,并返回语法树的根节点,最后通过printTree打印语法树,输出到文件SyntaxTree.txt中。Parser类的代码结构和主要的成员变量和函数如下图所示 成员函数和变量的作用和含义publicParser;TreeNode * parsevoid;TreeNode * syntaxTree;//语法树根节点privateScanner scanner;Token currentToken;//当前获取的TokenToken lastToken;//前一个Tokenint tokenIndex;//配合getToken使用,每获取一次,tokenIndex自增bool Error;//语法分析是否出错int step;//用于节点输出时表征节点的先行空格Token getToken;//获取保存在scanner中TokenList数组中的Token,每次获取完之后数组下标指向下一个void printSpaceint n;//打印n个空格void syntaxErrorstring message;//报错的函数,报告出错位置(行号)、出错位置附近的Tokenvoid matchTokenType ex;//与目标Token类型ex匹配,如果匹配成功则获取下一个Token(为currentToken赋值),否则报错void printSyntaxTreeTreeNode * t;//打印生成的语法树TreeNode * newNodeNodekind k;//根据节点类型新建节点TreeNode * declaration_listvoid;TreeNode * declarationvoid;TreeNode * paramsvoid;TreeNode * param_listTreeNode * k;TreeNode * paramTreeNode * k;TreeNode * compound_stmtvoid;TreeNode * local_declarationvoid;TreeNode * statement_listvoid;TreeNode * statementvoid;TreeNode * expression_stmtvoid;TreeNode * selection_stmtvoid;TreeNode * iteration_stmtvoid;TreeNode * return_stmtvoid;TreeNode * expressionvoid;TreeNode * varvoid;TreeNode * simple_expressionTreeNode * k;TreeNode * additive_expressionTreeNode * k;TreeNode * termTreeNode * k;TreeNode * factorTreeNode * k;TreeNode * callTreeNode * k;TreeNode * argsvoid;4.2 分析树节点定义4.2.1 树节点定义和类型节点定义//treeNode定义 包括子节点、兄弟节点、所处行号、节点类型、属性、表达式返回类型typedef struct treeNodestruct treeNode * childMAXCHILDREN;struct treeNode * sibling;int lineno; Nodekind nodekind;union TokenType op; int val; const char * name; attr; ExpType type; TreeNode;节点类型在程序处理过程中,主要对语法树定义了19种节点,分别为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,分别表示int、id、void、数值、变量声明、数组声明、函数声明、函数声明参数列表、函数声明参数、复合语句体、if、while、return、赋值、运算、数组元素、函数调用、函数调用参数列表、未知节点。//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;4.2.2 各类型节点的描述节点类型描述子节点组成IntK变量或返回值类型(int)无VoidK变量或返回值类型(void)无IdK标示符(id)无ConstK数值无Var_DeclK变量声明变量类型变量名Var_DeclK数组声明数组名数组大小FunK函数声明返回类型函数名参数列表函数体ParamsKFunK的参数列表参数(如果有多个参数,则之间为兄弟节点)ParamKFunK的参数参数类型参数名CompK复合语句体变量声明列表语句列表Selection_StmtKif条件表达式IF体ELSE体Iteration_StmtKwhile条件表达式循环体Return_StmtKreturn表达式AssignK赋值被赋值变量赋值变量OpK运算运算符左值运算符右值Arry_ElemK数组元素数组名下标CallK函数调用函数名参数列表ArgsKCallK的参数列表表达式(如果有多个表达式,则之间为兄弟节点)UnkownK未知节点无4.3 递归向下语法分析4.3.1 C-Minus文法已通过使用EBNF的方式消除左递归programdeclaration-listdeclaration_list declaration declaration declarationvar-declaration|fun-declarationvar_declaration type-specifier ID; | type-specifier ID NUM;type - specifier int | voidfun-declatationtype-specifier ID params | compound-stmtparamsparam_list | voidparam_listparam, paramparam type-specifier ID compound-stmt local-declaration statement-listlocal-declarations empty var- declarationstatement-liststatementstatementexpression-stmt | compound-stmt | selection-stmt | iteration-stmt | return-stmtexpression-stmt expression;selection-stmtif expression statement else statementiteration-stmtwhile expressionstatementreturn-stmtreturn expression;expression var expression | simple-expressionrelop | | | | | varID | ID expressionsimple-expressionadditive-expression relop additive-expression additive-expressiontermaddop term addop | -termfactormulop factor mulop * | /factorexpression | var | call | NUMcallID args argsarg-list | emptyarg-list expression, expression4.3.2 递归向下分析过程以下表格列出了根据上文中的C-Minus-文法使用递归向下分析方法分析程序的过程,待分析文法中列出的是将要分析的若干文法,分析函数是程序针对该文法编写的分析函数,用以分析该文法,分析是对该文法的分析过程以及分析函数的编写思想,代码是分析函数用C语言的实现,各文法分析过程如下待分析文法programdeclaration-list分析函数TreeNode * parsevoid分析说明C-语言编写的程序由一组声名序列组成。parsevoid函数使用递归向下分析方法直接调用declaration_list函数,并返回树节点代码TreeNode * Parser parsevoidTreeNode * t;currentToken getToken;lastToken currentToken;t declaration_list;ifcurrentToken.tokenTypeENDFILE syntaxError结束错误;return t;待分析文法declaration_list declaration declaration 分析函数TreeNode * declaration_listvoid分析说明C-语言编写的程序由一组声名序列组成。declaration_listvoid函数使用递归向下分析方法直接调用declaration函数,并返回树节点代码TreeNode * Parser declaration_list TreeNode * t declaration;TreeNode * p t;//在开始语法分析出错的情况下找到int和void型,过滤掉int和void之前的所有Token,防止在开始时出错后面一错百错whilecurrentToken.tokenTypeINTcurrentToken.tokenTypeVOIDcurrentToken.t