川大编译原理课程设计报告.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