编译原理课程设计实验报告-(川大张兵)

编译原理课程设计指导老师：张兵学生：刘佳玉编译原理课程设计报告课题名称： C-词法扫描器及语法分析器实现 提交文档学生姓名： 刘佳玉 提交文档学生学号： 34 同组 成 员 名 单： 无 指导 教 师 姓 名： 张兵 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间： 2015 年 6 月 10 日目录编译原理课程设计报告11、课程设计目标22、分析与设计22.1程序结构22.2程序流程32.3词法分析32.3.1代码结构分析32.3.2token定义和类型42.3.3DNF分析42.4语法分析52.4.1代码结构分析52.4.2节点定义和类型52.4.3递归下降语法分析63、测试结果113.1流程113.2出错情况154、总结154.1收获154.2特色154.3不足165、程序代码实现165.1递归下降源代码165.2C-文法201、课程设计目标学生在学习编译原理课程过程中，结合各章节的构造编译程序的基本理论，要求用C或C+语言描述及上机调试，实现一个 C-Minus 小编译程序（包括词法分析，语法分析等重要子程序），使学生将理论与实际应用结合起来，受到软件设计等开发过程的全面训练，从而提高学生软件开发的能力。要求：实现scanner和parser功能2、分析与设计2.1程序结构语法分析采用递归下降方法的程序结构：本程序采用面向对象的思想编写，使用C语言实现，程序分为两部分：词法分析（scan）和语法分析（parse），分别将两个处理阶段写在两个函数中，分别是scan()和parse()，两个函数分别完成词法分析和语法分析的任务。scan()函数主要的工作是检查注释是否合法、词法分析获取token。parse()函数的主要工作是根据scan()词法分析之后的token进行语法分析，生成语法树，最后并输出语法树。2.2程序流程递归下降方法的程序流程图2.3词法分析2.3.1代码结构分析词法分析阶段的代码写在一个函数中scan()。main函数读取程序数据，将其存储在一个二维数组中，调用函数zhushierror()，确定程序是否存在注释错误，注释的错误主要是注释的符号不匹配。如果不存在注释错误，则调用scan()函数进行词法分析，否则报错。词法分析是对输入的数据一个字符一个字符的分析，将所分析出来的token存储在一个vector数组中，方便后面语法分析时调用。词法分析没有什么错误限制，基本不会报错。所以在分析的同时，就会将所分析出的token输出 2.3.2token定义和类型token结构体定义如下：struct token/token结构体 Tokentype tokentype;/token类型 char tokenstring1100;/token串 int lineno;/token行号;token类型：/定义的Token的类型(29种)，分别对应于else、if、int、return、void、while、/+、-、*、/、=、=、/!=、=、;、,、(、)、num、id、错误、结束typedef enum elsee=1,iff,intt,returnn,voidd,whilee,xiaoyudengyu,dayudengyu,dengyudengyu,budengyu,/10 jia,jian,cheng,chu,dayu,xiaoyu,dengyu,fenhao,douhao,zuokuohao,youkuohao,zuozhongkuohao,/22 youzhongkuohao,zuohuakuohao,youhuakuohao,num,id,error,end/29Tokentype;2.3.3DNF分析词法分析的DFA描述：词法分析的DFA如下所示，一共分为5个状态：START、INNUM、INID、INDBSYM、DONE。状态START表示开始状态，状态INNUM表示数字类型（NUM）Token的状态，状态INID表示字符串类型Token的状态（如关键字和一般的标示符），状态INDBSYM表示双目运算符型Token的状态（如=、!=、=），状态DONE表示接收状态。2.4语法分析2.4.1代码结构分析语法分析阶段的代码中，每一条文法都有相对应的函数，通过函数之间的递归调用来达到语法分析的目的。语法分析的过程主要是：在语法分析之前进行词法分析，然后通过递归向下分析法根据C-语言的文法进行语法分析，并生成语法树，最后打印语法树。下面是语法分析所用到的全局变量和函数的声明：token currenttoken;/当前tokentoken lasttoken;/上一个tokenint tokenxb=0;/token下标int blank=0;/先行空格void gettoken();/得到tokenvoid parseerror();/输出错误void match(Tokentype tt);/匹配treenode * compound_stmt();/函数声明void printspace(int n);/打印空格void printtree(treenode * t);/打印语法分析树treenode * newnode(Nodekind kind);/创建新节点treenode * args();treenode * call(treenode * k);/函数调用treenode * factor(treenode * k);treenode * term(treenode * k);treenode * additive_expression(treenode * k);/加成的表达式treenode * simple_expression(treenode * k);/简单表达式treenode * varr();treenode * expression();treenode * expression_stmt();/表达式声明treenode * return_stmt();/返回式声明treenode * iteration_stmt();/while声明treenode * selection_stmt();/if声明treenode * statement();/复合语句后者种类treenode * statement_list();/复合语句体后者treenode * local_declaration();/复合语句体前者treenode * param(treenode * k);/函参treenode * param_list(treenode * k);/函参列表treenode * compound_stmt();/函数内容，复合语句treenode * params();/函数参数treenode * declaration();/函数声明treenode * declaration_list();/多个函数列表treenode * parse();/语法分析2.4.2节点定义和类型节点定义：struct treenode/树节点结构体 treenode * child;/子节点 treenode * brother;/兄弟节点 int lineno;/所在行 Nodekind nodekind;/节点类型 char nodestring1100;/节点类型所代表的字符串，用于语法树打印;节点类型：/19种节点类型，分别表示int、id、void、数值、变量声明、数组声明、函数声明、/函数声明参数列表、函数声明参数、复合语句体、if、while、return、赋值、运算、/数组元素、函数调用、函数调用参数列表、未知节点typedef enum ints,ids,voids,nums,var,shuzu,hanshu,hancanlist,hancan,fuheyuju,ifs,whiles,returns, fuzhi,yunsuan,shuzuyuansu,hanshudiaoyong,hanshudiaoyongcanlist,unknownNodekind;/节点种类2.4.3递归下降语法分析2.4.3.1C-语法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, expression2.4.3.2递归下降语法分析过程以下表格列出了根据上文中的C-文法使用递归向下分析方法分析程序的过程，在代码部分只列出了函数名，具体函数见源代码。待分析文法programdeclaration-list分析函数treeNode * parse()分析说明C-语言编写的程序由一组声名序列组成。parse(void)函数使用递归向下分析方法直接调用declaration_list()函数，并返回树节点代码treenode * parse()待分析文法declaration_list declaration declaration 分析函数treenode * declaration_list()分析说明C-语言编写的程序由一组声名序列组成。declaration_list(void)函数使用递归向下分析方法直接调用declaration()函数，并返回树节点代码treenode * declaration_list()待分析文法declarationvar-declaration|fun-declarationvar_declaration type-specifier ID; | type-specifier ID NUM;fun-declatationtype-specifier ID (params) | compound-stmttype - specifier int | void分析函数treenode * declaration()分析说明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 * declaration()待分析文法paramsparam_list | void分析函数treenode * params()分析说明函数参数列表要么是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 * params()待分析文法param_listparam, param分析函数treenode * param_list(treenode * k)分析说明参数列表由param序列组成，并由逗号隔开。param_list(TreeNode * k)函数使用递归向下分析方法直接调用param(TreeNode * k)函数，并返回树节点代码treenode * param_list(treenode * k)待分析文法param type-specifier ID 分析函数treenode * param(treenode * k)分析说明参数由int或void、标示符组成，最后可能有中括号表示数组。param(TreeNode * k)函数根据探测先行Token是int还是void而新建IntK或VoidK节点作为其第一个子节点，然后新建IdK节点作为其第二个子节点，最后探测Follow集合，是否是中括号，而确定是否再新建第三个子节点表示数组类型代码treenode * param(treenode * k)待分析文法compound-stmt local-declaration statement-list分析函数treenode * compound_stmt()分析说明复合语句由用花括号围起来的一组声明和语句组成。compound_stmt(void) 函数使用递归向下分析方法直接调用local_declaration()函数和statement_list()函数，并根据返回的树节点作为其第一个子节点和第二个子节点代码treenode * compound_stmt()待分析文法local-declarations empty var- declaration分析函数treenode * local_declaration()分析说明局部变量声明要么是空，要么由许多变量声明序列组成。local_declaration(void)函数通过判断先行的Token是否是int或void便可知道局部变量声明是否为空，如果不为空，则新建一个变量定义节点（Var_DeclK）代码treenode * local_declaration()待分析文法statement-liststatement分析函数treenode * statement_list()分析说明由语句列表由0到多个statement组成。statement_list(void)函数通过判断先行Token类型是否为statement的First集合确定后面是否是一个statement，如果是，则使用递归向下分析方法直接调用statement()函数代码treenode * statement_list()待分析文法statementexpression-stmt | compound-stmt | selection-stmt | iteration-stmt | return-stmt分析函数treenode * statement()分析说明statement由表达式或复合语句或if语句或while语句或return语句构成。statement(void)函数通过判断先行Token类型确定到底是哪一种类型。如果是IF则是if语句类型，如果是WHILE，则是while语句类型，如果是RETURN，则是return语句类型，如果是左大括号，则是复合语句类型，如果是ID、SEMI、LPAREN、NUM，则是表达式语句类型代码treenode * statement()待分析文法expression-stmt expression;分析函数treenode * expression_stmt()分析说明表达式语句有一个可选的且后面跟着分号的表达式。expression_stmt(void)函数通过判断先行Token类型是否为分号，如果不是则直接调用函数expression()代码treenode * expression_stmt()待分析文法selection-stmtif (expression) statement else statement分析函数treenode * selection_stmt()分析selection_stmt(void)函数直接调用expression()函数和statement()函数分别得到其第一个和第二个子节点，然后通过判断先行Token类型是否为ELSE，如果是则直接调用statement()函数得到其第三个子节点代码treenode * selection_stmt()待分析文法iteration-stmtwhile (expression)statement分析函数treenode * iteration_stmt()分析iteration_stmt(void)函数直接调用expression()函数和statement()函数分别得到其第一个和第二个子节点代码treenode * iteration_stmt()待分析文法return-stmtreturn expression;分析函数treenode * return_stmt()分析return_stmt(void)函数通过判断先行Token类型是否为分号，如果不是则直接调用函数expression()得到其子节点代码treenode * return_stmt()待分析文法expression var = expression | simple-expression分析函数treenode * expression()分析expression(void)函数通过判断先行Token类型是否为ID，如果不是说明只能是simple_expression情况，则调用simple_expression(TreeNode * k)函数递归向下分析；如果是ID说明可能是赋值语句，或simple_expression中的var和call类型的情况，所以再求其Follow集合，如果集合求出来是赋值类型的Token，则说明是赋值语句，于是新建一个AssignK节点就行；如果集合求出来不是赋值类型的Token则说明是simple_expression中的var和call类型的情况，然后再调用simple_expression(TreeNode * k)函数递归向下分析，并将已经取出IdK节点传递给simple_expression(TreeNode * k)函数代码treenode * expression()待分析文法varID | ID expression分析函数treenode * varr()分析varr(void)函数先新建一个IdK节点，再通过判断先行Token类型是否为左中括号，如果是则新建一个数组节点Arry_ElemK，将IdK作为Arry_ElemK节点的第一个子节点，再直接调用函数expression()得到Arry_ElemK的第二个子节点，最后返回的节点时Arry_ElemK；如果先行Token类型不是左中括号，则将之前的IdK返回代码treenode * varr()待分析文法simple-expressionadditive-expression relop additive-expression relop = | | = | = = | ! =分析函数treenode * simple_expression(treenode * k)分析simple_expression(TreeNode * k)函数先调用additive_expression(TreeNode * k)函数返回一个节点，然后再一直判断后面的Token是否为=、=、=、!=，如果是则新建OpK节点，然后令之前的节点为其第一个子节点，然后继续调用additive_expression(TreeNode * k)函数返回一个节点，作为OpK节点的第二个节点代码treenode * simple_expression(treenode * k)待分析文法additive-expressiontermaddop term addop + | -分析函数treenode * additive_expression(treenode * k)分析additive_expression(TreeNode * k)函数先调用term(TreeNode * k)函数返回一个节点，然后再一直判断后面的Token是否为+或-，如果是则新建OpK节点，然后令之前的节点为其第一个子节点，然后继续调用term(TreeNode * k)函数返回一个节点，作为OpK节点的第二个节点代码treenode * additive_expression(treenode * k)待分析文法termfactormulop factor mulop * | /分析函数treenode * term(treenode * k)分析term(TreeNode * k)函数先调用factor(TreeNode * k)函数返回一个节点，然后再一直判断后面的Token是否为*或/，如果是则新建OpK节点，然后令之前的节点为其第一个子节点，然后继续调用actor(TreeNode * k)函数返回一个节点，作为OpK节点的第二个节点代码treenode * term(treenode * k)待分析文法factor(expression) | var | call | NUM分析函数treenode * factor(treenode * k)分析factor(TreeNode * k)函数首先判断k是否为空，如果不为空，则k为上面传下来的已经解析出来的以ID开头的var，此时可能为call或var的情况，然后判断后面的Token是否为左括号，如果是则说明是call的情形，如果不是则为var的情形。如果k为空，再根据先行的Token类型判断是4中推导中的哪一种，然后直接调用相关的函数返回一个节点代码treenode * factor(treenode * k)待分析文法callID( args )分析函数treenode * call(treenode * k)分析call(TreeNode * k)函数新建一个call语句的节点CallK，如果k不为空，则将k设为CallK的第一个子节点，然后通过调用args(void)函数获得其第二个节点，最后返回CallK节点代码treenode * call(treenode * k)待分析文法argsarg-list | empty arg-list expression, expression分析函数treenode * args()分析factor(TreeNode * k)函数首先判断后面的Token是否为右括号，如果是则说明是empty的情形，如果不是则为至少有一个expression的情形，然后调用expression()函数返回节点，然后一直判断后面的Token是否为逗号，如果是则说明后面还有一个expression，则再调用expression()函数，使各expression返回的节点为兄弟节点，然后再将第一个expression返回的节点作为函数调用语句参数节点ArgsK的子节点代码treenode * args()3、测试结果3.1流程测试数据：测试结果：词法分析：语法分析：3.2出错情况若注释没有结束符号：则提示删除注释出错若含有未知Token：比如char则语法分析出错4、总结4.1收获在本次课程设计中增加了自己的动手能力，锻炼了构造一个项目的框架方法，能够很好的给出系统的框架，并且能够按照程序流程进行程序的编写。能够灵活运用递归下降的方法进行分析问题，在词法分析中掌握了状态机的转变，同时能够熟练运用状态机进行字符的匹配。在语法分析中，学习到了怎么样通过文法构建代码，以及根据文法编写代码带来的相关问题，如左递归，节点的定义等。特别是在写语法分析器的时候，已经对编译器的语法分析的内容有了一定的了解，所以直接进行了理论的学习。首先自己对递归向下分析法进行了学习，将书上的几个递归向下分析的伪代码看过之后，自己对递归向下的分析方法的原理有了初步的认识，大概知道了根据文法怎么分析。但是由于C-语言给出的文法有左递归存在，于是自己将存在左递归的文法改写成EBNF的形式，并据此进行代码编写。整个过程可以说是痛并快乐着，一方面自己在编写代码的时候遇到了很多问题，这也是自己动手能力不足的一个表现。 4.2特色在词法分析方面，使用全局变量zs来判断当前字符是否是注释，并且通过zs的值判断注释是否合法。整体来说，代码简介明了，没有复杂的类的关系，树节点只有孩子和兄弟两个子节点，没有复杂的节点之间的关系。 4.3不足由于各函数之间逻辑关系比较复杂，代码还存在一些错误，需要通过测试来修复bug5、程序代码实现5.1递归下降源代码#include#include#include#include#include#include#includeusing namespace std;char s10051005;/文本char p10051005;char t1005;/当前token串char linshi1100;/临时数组int k;/文本行数int zs;/注释标记,1表示是注释，0表示不是注释void zhushierror()/注释错误 int i,j,len; zs=0; for(i=0;ik-1;i+) len=strlen(si); for(j=0;jlen-1;j+) if(sij=/&sij+1=*) if(zs=0) zs=1; else return; if(sij=*&sij+1=/) if(zs=1) zs=0; else zs=1; return; /定义的Token的类型(29种)，分别对应于else、if、int、return、void、while、/+、-、*、/、=、=、/!=、=、;、,、(、)、num、id、错误、结束typedef enum elsee=1,iff,intt,returnn,voidd,whilee,xiaoyudengyu,dayudengyu,dengyudengyu,budengyu,/10 jia,jian,cheng,chu,dayu,xiaoyu,dengyu,fenhao,douhao,zuokuohao,youkuohao,zuozhongkuohao,/22 youzhongkuohao,zuohuakuohao,youhuakuohao,num,id,error,end/29Tokentype;struct token/token结构体 Tokentype tokentype;/token类型 char tokenstring1100;/token串 int lineno;/token行号;Tokentype gettokentype(char c) Tokentype to; if(!strcmp(c,else) to=elsee; else if(!strcmp(c,if) to=iff; else if(!strcmp(c,return) to=returnn; else if(!strcmp(c,int) to=intt; else if(!strcmp(c,void) to=voidd; else if(!strcmp(c,while) to=whilee; else if(!strcmp(c,+) to=jia; else if(!strcmp(c,-) to=jian; else if(!strcmp(c,*) to=cheng; else if(!strcmp(c,/) to=chu; else if(!strcmp(c,) to=xiaoyu; else if(!strcmp(c,) to=dayu; else if(!strcmp(c,=) to=dayudengyu; else if(!strcmp(c,=) to=dengyudengyu; else if(!strcmp(c,!=) to=budengyu; else if(!strcmp(c,=) to=dengyu; else if(!strcmp(c,;) to=fenhao; else if(!strcmp(c,) to=douhao; else if(!strcmp(c,() to=zuokuohao; else if(!strcmp(c,) to=youkuohao; else if(!strcmp(c,) to=zuozhongkuohao; else if(!strcmp(c,) to=youzhongkuohao; else if(!strcmp(c,) to=zuohuakuohao; else if(!strcmp(c,) to=youhuakuohao;