四川大学计算机学院-C-语言编译器-编译原理课程设计报告内附源码-递归下降-c-minus

编译原理课程设计报告 计算机学院 计科x班 xxx xxxx 编译原理课程设计报告课题名称： C-词法扫描器及语法分析器实现 提交文档学生姓名： XXX 提交文档学生学号： XXX 同组 成 员 名 单： 无 指导 教 师 姓 名： 张 兵 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间：2012年 6月 2日目录1 课程设计目标32 分析与设计42.1 程序结构42.2 程序流程53 词法分析63.1 代码结构分析63.2 Token定义73.2.1 Token的定义和类型73.2.2 Token的种别码73.3 DAF分析83.3.1 删除注释DFA83.3.2 词法分析DFA104 语法分析144.1 代码结构分析144.2 节点定义154.2.1 节点定义和类型154.2.2 各类型节点的描述164.3 递归向下语法分析164.3.1 C-文法164.3.2 递归向下分析过程175 测试结果345.1 流程345.2 词法分析结果345.3 词法分析出错385.4 语法分析结果395.5 语法分析出错416 总结426.1 词法分析编写过程426.2 语法分析编写过程436.3 成果和收获437 附录447.1 scanner.h源文件447.2 scanner.cpp源文件457.3 parser.h源文件557.4 parser.cpp源文件56 1 课程设计目标学生在学习编译原理课程过程中，结合各章节的构造编译程序的基本理论，要求用C或C+语言描述及上机调试，实现一个 C-Minus 小编译程序（包括词法分析，语法分析等重要子程序），使学生将理论与实际应用结合起来，受到软件设计等开发过程的全面训练，从而提高学生软件开发的能力。 要求：（1）设计词法分析器设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括：a. 具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；b. 能够拼出语言中的各个单词；c. 返回（种别码， 属性值）。（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类进行语法分析。工程文件总体上是按照两个类的格局分为四个文件，分别是两个类的声明文件和实现文件。四个文件分别为scanner.h和scanner.cpp以及parser.h和parser.cpp，他们分别是Scanner类声明文件、Scanner类实现文件、Parser类声明文件、Parser类实现文件。词法分析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进行语法分析，生成语法树，最后打印语法树。同时，这也是程序的流程。整体程序流程图开始删除注释出错词法分析TF结束语法分析出错出错输出出错信息TFFT从文件获取源代码3 词法分析3.1 代码结构分析词法分析阶段的代码被封装成一个类Scanner，scanner.h中主要是Scanner类的声明代码，scanner.cpp中主要是Scanner类的实现代码。Scanner类对外提供的函数主要有：getSourseStringFromFile(string s)（从文件中获取待分析的源代码）、deleteComments()（过滤注释）、scan()（词法分析主程序）。词法分析的过程主要是：l Scanner调用getSourseStringFromFile(string s)，从文件中获取待分析的源代码l Scanner调用deleteComments()，将注释过滤掉，如果注释出错，则不进行词法分析l Scanner调用scan()，进行词法分析，将分析得到的所有Token保存在Scanner类的成员变量tokenList中，以备语法阶段调用，并将Token输出到文件Token.txt中以上三个函数构成了词法分析的骨架，在Scanner类中还有其他成员变量和函数，主要作为这三个函数处理过程的中间步骤，为这三个函数服务。Scanner类的代码结构和主要的成员变量和函数如下图所示：其他函数和成员变量的作用和含义：l void backToLastChar()：在词法分析过程中，回退一个字符l DFAState charType(char)：返回字符的类型（按状态分），如white space返回START，0-9返回NUMl char getNextChar()：获取到下一个字符l Token getTokenAt(int)：根据下标从tokenList数组中获取词法分析后所保存的Token（供语法分析阶段调用）l void printToken()：将词法分析好的Token输出到文件Token.txt中l TokenType returnTokenType(string s)：根据字符串返回对应的31种Token类型，如字符串int将返回INT， var将返回IDl int charIndex：配合getNextChar()和backToLastChar()使用（分别自增和自减1），用以指示当前待分析的char在源代码中的位置l bool commentFlag：标注注释开始的标志，为true时表示正在注释体内，即源代码进入/*之后且*/之前的状态l int lineCount：对行号计数，表示当前词法分析在源代码的行位置（每次获取到的char为/n就自增1）l bool scanSuccess：词法分析是否成功的标志l string sourseString：获取源代码的字符串l string str：在分析过程中保存Token对应的串l 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、错误、文件结束，TokenType的定义和种别码分别如下所示：/定义的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 删除注释DFA删除注释的DFA描述：删除注释的DFA如下所示，一共分为5个状态，在开始状态1时，如果输入的字符为/,则进入状态2，此时有可能进入注释状态，如果在状态2时，输入的字符为*，则进入注释状态，状态将转到3，如果在状态3时，输入的字符为*，则有可能结束注释状态，此时状态将转到状态4，如果在状态4时输入的字符为/，则注释状态结束，状态转移到结束状态。对应的DFA的代码分析：删除注释的功能通过Scanner 类的成员函数deleteComments()实现，功能是将源代码中的注释过滤掉，将其余代码输出到sourceFile.txt文件中。deleteComments()函数按照上面的DFA编写，在函数中，state变量表示状态，共分为5个状态：l 在状态1时，如果输入的字符为/,则进入状态2，否则仍处在状态1，且输出输入的字符l 在状态2时，（此时可能进入注释状态），如果输入的字符为*，则进入注释状态，状态将转到3，否则跳转到状态1，并输出/和输入的字符l 在状态3时，（此时可能结束注释状态），如果输入的字符为*，此时状态将转到状态4，否则继续在状态3l 在状态4时，如果输入的字符为/，则注释状态结束，状态转移到结束状态相应的DFA代码：代码如下所示：void Scanner : deleteComments()ofstream fout_Sourse(sourseFile.txt);int state = 1;char ch;while(state6)ch = getNextChar();if(0=ch)/文件结束break;if(1=state)/DFA中的状态if(/=ch)state = 2;elsestate = 1;fout_Soursech;else if(2=state)/DFA中的状态if(*=ch)state = 3;commentFlag = false; elsestate = 1;fout_Sourse/ch;else if(3=state)/DFA中的状态if(*=ch)state = 4;elsestate = 3;else if(4=state)/DFA中的状态if(*=ch)state = 4;else if(/=ch)state = 5;elsestate = 3;if(5=state)/结束状态，处理commentFlag = true;state = 1;if(!commentFlag)cout注释错误，没有结束符！endl;scanSuccess = false;3.3.2 词法分析DFA词法分析的DFA描述：词法分析的DFA如下所示，一共分为5个状态：START、INNUM、INID、INDBSYM、DONE。状态START表示开始状态，状态INNUM表示数字类型（NUM）Token的状态，状态INID表示字符串类型Token的状态（如关键字和一般的标示符），状态INDBSYM表示双目运算符型Token的状态（如=、!=、=），状态DONE表示接收状态。l 在开始状态START时 如果输入的字符为空白符，如空格换行等，则仍在START状态 如果输入的字符为digit，则进入状态INNUM，即可能是数字类型（NUM）Token的状态 如果输入的字符为letter，则进入状态INID，即可能是字符串类型Token的状态 如果输入的字符为、!、=，则进入状态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()bool doubleSym = false;getSourseStringFromFile(sourseFile.txt);int state = START;lineCount = 0;char ch;/每一次循环都执行一次DFA，并获取到一个Tokenwhile(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(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;/根据str生成TokenToken t;t.lineNo = lineCount-tp;t.tokenString = str;t.tokenType = returnTokenType(str);tokenList.push_back(t);if(ERROR=t.tokenType)scanSuccess = false;/针对other的情形，回退一个字符int lastState = charType(strstr.length()-1);if(lastState=INNUM | lastState=INID | (lastState=INDBSYM & doubleSym=false)backToLastChar();str = ;state = START;if(doubleSym=true)doubleSym = false; printToken();/输出Token到文件Token.txt中4 语法分析4.1 代码结构分析语法分析阶段的代码被封装成一个类Parser，parser.h中主要是Parser类的声明代码，parser.cpp中主要是Parser类的实现代码。语法分析的过程主要是：在语法分析之前进行词法分析，然后通过递归向下分析法根据C-语言的文法进行语法分析，并生成语法树，最后打印语法树。Parser类在其构造函数中完成语法分析，在构造函数Parser（）中，首先通过Parser类的scanner成员变量进行词法分析（删除注释、词法分析获取Token），然后通过parse()函数开始递归向下分析，并返回语法树的根节点，最后通过printTree()打印语法树，输出到文件tokenTree.txt中。Parser类的代码结构和主要的成员变量和函数如下图所示： 成员函数和变量的作用和含义：l Token getToken()：获取保存在scanner中TokenList数组中的Token，每次获取完之后数组下标指向下一个l void printSpace(int n)：打印n个空格l void syntaxError(string s)：报错的函数，报告出错位置（行号）、出错位置附近的Tokenl void match(TokenType ex)：与目标Token类型ex匹配，如果匹配成功则获取下一个Token（为currentToken赋值），否则报错l void printTree(TreeNode * t)：打印生成的语法树l TreeNode * newNode(Nodekind k)：根据节点类型新建节点l 以下为递归向下分析文法过程中各阶段的分析函数：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);l Scanner scanner：词法分析的Scanner类对象，用于语法分析前进行词法分析处理l Token currentToken：当前获取的Tokenl Token lastToken：前一个Tokenl int tokenIndex：配合getToken使用，每获取一次，tokenIndex自增1l bool Error：语法分析是否出错l int step：用于printTree()函数节点输出时表征节点的先行空格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-文法已通过使用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-文法使用递归向下分析方法分析程序的过程，待分析文法中列出的是将要分析的若干文法，分析函数是程序针对该文法编写的分析函数，用以分析该文法，分析是对该文法的分析过程以及分析函数的编写思想，代码是分析函数用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); = 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);else syntaxError(); else syntaxError();return t;待分析文法paramsparam_list | void分析函数TreeNode * params(void)分析说明函数参数列表要么是void，要么是多个参数组成。params(void)函数先判断第一个是void还是int，如果是int说明是由param_list组成，则调用param_list(TreeNode * k)函数递归向下分析；如果是void说明可能是void型的参