川大编译原理课程设计报告

编译原理课程设计报告 计算机学院 计科8班 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调用getSourseStringFromFile(string s)，从文件中获取待分析的源代码l Scanner调用deleteComments()，将注释过滤掉，如果注释出错，则不进行词法分析l Scanner调用scan()，进行词法分析，将分析得到的所有Token保存在Scanner类的成员变量tokenList中，以备语法阶段调用，并将Token输出到文件Token.txt中l Scanner调用getTokenAt(int) 根据下标从tokenList数组中获取Token以上为Scanner类对外提供的公共函数：getSourseStringFromFile(string s)（从文件中获取待分析的源代码）、deleteComments()（过滤注释）、scan()（词法分析主程序）、getTokenAt(int)（获取数组中Token）。这四个函数构成了词法分析的骨架，在Scanner类中还有其他成员变量和函数，主要作为这四个函数处理过程的中间步骤，为这四个函数服务。此外，其他函数和成员变量的作用和含义如下：public:bool scanSuccess;/词法分析是否成功的标志string sourseString;/获取源代码的字符串Scanner();private:string printSpace(const int i);DFAState charType(char);/根据字母返回字符的DFA状态类型void backToLastChar();/回到上一个字符char getNextChar();/获取到下一个字符TokenType getTokenType(string s);/根据字符串返回Token类型void printToken();/将词法分析好的Token输出到文件Token.txt中int charIndex; /配合getNextChar()，指定要取的字符位置string str;/在分析过程中保存Token对应的串bool commentStartFlag;/标注注释开始的标志int lineCount;/对行号计数，每次获取到/n就自增vector 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单词符号种别码ValueelseELSE1=ASSIGN17ifIF2;SEMI18intINT3,COMMA19returnRETURN4(LPAREN20voidVOID5)RPAREN21whileWHILE6LMBRACKET22+PLUS7RMBRACKET23-MINUS8LBBRACKET24*TIMES9RBBRACKET25/OVER10/*LCOMMENT26LT11*/RCOMMENT27GT13idID29=GEQ14错误ERROR30=EQ15结束ENDFILE31!=NEQ163.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 Scanner:deleteComments()cout 开始删除注释. endl;ofstream fout_Sourse(pureCodeFile.txt);int state = 1;char ch;while (state6)ch = getNextChar();if (0 = ch)/文件结束break;if (1 = state)if (/ = ch)state = 2;elsestate = 1;fout_Sourse ch;else if (2 = state)if (* = ch)state = 3;commentStartFlag = true;/进入注释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)/结束状态，处理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 Scanner:scan()cout 开始词法分析. endl;bool doubleSym = false;getSourseStringFromFile(pureCodeFile.txt);int state = START;lineCount = 0;char ch;while (state6)ch = getNextChar();if (0 = ch)/如果遇到文件结束则添加ENDFILE类型tokenToken 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)/遇到换行符行数会自动加1tp = 1;Token t;t.lineNo = lineCount - tp;/恢复原来行数t.tokenString = str;t.tokenType = getTokenType(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)/以other结束需回退一个字符backToLastChar();str = ;state = START;if (doubleSym = true)doubleSym = false;if (scanSuccess = false)cout 词法分析出错！ 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类的代码结构和主要的成员变量和函数如下图所示： 成员函数和变量的作用和含义：public:Parser();TreeNode * parse(void);TreeNode * syntaxTree;/语法树根节点private:Scanner scanner;Token currentToken;/当前获取的TokenToken lastToken;/前一个Tokenint tokenIndex;/配合getToken使用，每获取一次，tokenIndex自增bool Error;/语法分析是否出错int step;/用于节点输出时表征节点的先行空格Token getToken();/获取保存在scanner中TokenList数组中的Token，每次获取完之后数组下标指向下一个void printSpace(int n);/打印n个空格void syntaxError(string message);/报错的函数，报告出错位置（行号）、出错位置附近的Tokenvoid match(TokenType ex);/与目标Token类型ex匹配，如果匹配成功则获取下一个Token（为currentToken赋值），否则报错void printSyntaxTree(TreeNode * t);/打印生成的语法树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);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 (expression)statementreturn-stmtreturn expression;expression var = expression | simple-expressionrelop = | | = | = = | ! =varID | ID expressionsimple-expressionadditive-expression relop additive-expression additive-expressiontermaddop term addop + | -termfactormulop factor mulop * | /factor(expression) | var | call | NUMcallID( args )argsarg-list | emptyarg-list expression, expression4.3.2 递归向下分析过程以下表格列出了根据上文中的C-Minus-文法使用递归向下分析方法分析程序的过程，待分析文法中列出的是将要分析的若干文法，分析函数是程序针对该文法编写的分析函数，用以分析该文法，分析是对该文法的分析过程以及分析函数的编写思想，代码是分析函数用C+语言的实现，各文法分析过程如下：待分析文法programdeclaration-list分析函数TreeNode * parse(void)分析说明C-语言编写的程序由一组声名序列组成。parse(void)函数使用递归向下分析方法直接调用declaration_list()函数，并返回树节点代码TreeNode * Parser : parse(void)TreeNode * t;currentToken = getToken();lastToken = currentToken;t = declaration_list();if(currentToken.tokenType!=ENDFILE) syntaxError(结束错误);return t;待分析文法declaration_list declaration declaration 分析函数TreeNode * declaration_list(void)分析说明C-语言编写的程序由一组声名序列组成。declaration_list(void)函数使用递归向下分析方法直接调用declaration()函数，并返回树节点代码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(currentToken.tokenType=ENDFILE)break;/寻找语法分析的入口，即找到int和voidwhile(currentToken.tokenType=INT)|(currentToken.tokenType=VOID) TreeNode * q;q = declaration();if(q!=NULL)if(t=NULL) t = p = q;else p-sibling = q;p = q;match(ENDFILE);return t;待分析文法declarationvar-declaration|fun-declarationvar_declaration type-specifier ID; | type-specifier ID NUM;fun-declatationtype-specifier ID (params) | compound-stmttype - specifier int | void分析函数TreeNode * declaration(void)分析说明C-语言的声明分为变量声明和函数声明。declaration(void)函数并不是直接调用var-declaration或fun-declaration文法所对应的函数，令其返回节点，实际上程序并没有为var-declaration和fun-declaration文法定义函数，而是在declaration(void)函数中，通过求First集合的方式先确定是变量定义还是函数定义，然后分别根据探测的结果生成变量声明节点（Var_DeclK）或函数声明节点（FunK）。所以var-declaration和fun-declaration文法在declarationvar-declaration|fun-declaration文法中就都已经分析了代码TreeNode * Parser:declaration(void)TreeNode * t = NULL;TreeNode * p = NULL;TreeNode * q = NULL;TreeNode * s = NULL;if (currentToken.tokenType = INT)p = newNode(IntK);match(INT);else if (currentToken.tokenType = VOID)p = newNode(VoidK);match(VOID);elsesyntaxError(类型匹配错误);if (p != NULL) & (currentToken.tokenType = ID)q = newNode(IdK); = new charcurrentToken.tokenString.length();strcpy(,currentToken.tokenString.c_str();match(ID);if (currentToken.tokenType = LPAREN)/(：函数情况t = newNode(FunK);t-child0 = p;t-child1 = q;match(LPAREN);t-child2 = params();match(RPAREN);t-child3 = compound_stmt();else if (currentToken.tokenType = LMBRACKET)/：数组声明t = newNode(Var_DeclK);TreeNode * m = newNode(Arry_DeclK);match(LMBRACKET);match(NUM);s = newNode(ConstK);s-attr.val = atoi(lastToken.tokenString.c_str();m-child0 = q;m-child1 = s;t-child0 = p;t-child1 = m;match(RMBRACKET);match(SEMI);else if (currentToken.tokenType = SEMI)/;结尾：普通变量声明t = newNode(Var_DeclK);t-child0 = p;t-child1 = q;match(SEMI);elsesyntaxError();elsesyntaxError();return t;待分析文法paramsparam_list | void分析函数TreeNode * params(void)分析说明函数参数列表要么是void，要么是多个参数组成。params(void)函数先判断第一个是void还是int，如果是int说明是由param_list组成，则调用param_list(TreeNode * k)函数递归向下分析；如果是void说明可能是void型的参数，也可能参数就是void，所以再求其Follow集合，如果集合求出来是右括号，则说明参数就是void，于是新建一个VoidK节点就行；如果集合求出来不是右括号则说明是void型的参数，然后再调用param_list(TreeNode * k)函数递归向下分析，并将已经取出VoidK节点传递给param_list(TreeNode * k)函数代码TreeNode * Parser:params(void)TreeNode * t = newNode(ParamsK);TreeNode * p = NULL;if