编译原理实验报告-语法分析

编译原理课程实验报告实验2：语法分析姓名赵璐媛院系软件学院学号1143710516任课教师陈鄞指导教师陈鄞实验地点软件学院三楼机房实验时间10月30日78节实验课表现出勤、表现得分实验报告得分实验总分操作结果得分一、需求分析得分要求：采用至少一种句法分析技术（LL(1)、SLR(1)、LR(1)或LALR(1)）对类高级语言中的基本语句进行句法分析。阐述句法分析系统所要完成的功能。语法分析器使用LL(1)进行语法分析（1）能识别以下几类语句：声明语句（包括变量声明、数组声明、记录声明和过程声明）表达式及赋值语句（包括数组元素的引用和赋值）分支语句：if_then_else循环语句：do_while过程调用语句（2）自动计算FIRST集和FOLLOW集，并自动生成预测分析表。（3）具备语法错误处理能力，能准确给出错误所在位置，并采用可行的错误恢复策略。输出的错误提示信息格式如下：ErroratLine[行号]：[说明文字]（4）系统的输入形式：要求可以通过文件导入文法和测试用例，可以通过用户界面显示并编辑测试用例。（5）系统的输出分为两部分：一部分是打印输出语法分析器的FIRST集、FOLLOW集和LL(1)分析表。另一部分是打印输出语法分析结果。二、文法设计得分要求：给出如下语言成分的文法描述。声明语句（包括变量声明、数组声明、记录声明和过程声明）表达式及赋值语句（包括数组元素的引用和赋值）分支语句：if_then_else循环语句：do_while过程调用语句P®D //参见教材p229P®S //参见教材p241 S®SS //参见教材p241/*声明*/D®DD|procid;DS|Tid; //参见讲义第7章 T→XC|recordD //参见教材p227 X→int|real //参见教材p227C→[E]C|ε //参见教材p227/*赋值语句*/S®id=E;|L=E; //参见教材p234E®E+E|E*E|-E|(E)|id|digit|L //参见教材p234L®id[E]|L[E] //参见教材p234/*控制流语句*/S®ifBthenS1 //参见教材p241|ifBthenS1elseS2 //参见教材p241 |doS1whileB //参见教材p241B→BorB //参见教材p243 |BandB //参见教材p243 |notB //参见教材p243 |(B) //参见教材p243 |EopE //参见教材p243 |true //参见教材p243 |false //参见教材p243op→<|<=|==|!=|>|>= //参见教材p240/*过程调用*/S®callid(Elist) //参见讲义第6章Elist®Elist,E //参见讲义第6章Elist®E //参见讲义第6章消除左递归和二义性后文法如下：P->S'|D/*声明*/D->Tid;D'|procid;DS'D'D'->DD'|εT->XC|recordDX->int|realC->[E]C|ε/*控制流语句*/S->L=E;|callid(Elist);|ifBthenSEL|doS'whileBEL->ε|elseSS'->SS'|εB->notBB'|(B)B'|EOPEB'|trueB'|falseB'B'->orBB'|andBB'|εOP-><|<=|==|!=|>|>=/*过程调用*/Elist->EElist'Elist'->,EElist'|ε/*赋值语句*/E->FE'E'->+FE'|εF->GF'F'->*GF'|εG->-G|(E)|digit|LL->idL'L'->[E]L'|ε三、系统设计得分要求：分为系统概要设计和系统详细设计。（1）系统概要设计：给出必要的系统宏观层面设计图，如系统框架图、数据流图、功能模块结构图等以及相应的文字说明。（2）系统详细设计：对如下工作进行展开描述核心数据结构的设计主要功能函数说明程序核心部分的程序流程图系统概要设计系统的设计类图如下：（建议放大查看）在选择了DFA文件、语法文件和代码文件后，点击分析按钮，1）由DFAView生成DFA实例，由SyntaxView生成LL实例并打印fist集、follow集、预测分析表；2）调用DFA实例的doDFA方法对CodeView中的代码进行分析；3）调用LL实例的getTree方法对2）产生的结果进行分析，得到语法树和错误信息；4）调用语法树的printTree方法得到字符串表示，调用OutputView的setTextLabel方法打印语法树和错误信息。系统详细设计系统的核心类是LL类，LL类中实现了first集、follow集、预测分析表的生成过程，以及使用预测分析表对语法进行分析的过程。first集数据结构是Map<String,Set<String>>，map的key是终结符或语法变量，value是一个set，即first(key)。生成过程见LL.getFirst()。follow集数据结构是Map<String,Set<String>>，map的key是终结符或语法变量，value是一个set，即follow(key)。生成过程见LL.getFollow()。预测分析表数据结构是Map<String,Map<String,String[]>>，举例说明，若table(X,a)为X->Y1Y2，则table.get(X).get(a)为String[]类型，记做temp，则temp[0]=Y1temp[1]=Y2。生成过程见LL.getTable()。分析过程分析过程见下图，其中P是语法树根，同时也是栈中最初的元素。四、系统实现及结果分析得分要求：对如下内容展开描述。系统实现过程中遇到的问题；输出该句法分析器的分析表；针对一测试程序输出其句法分析结果；输出针对此测试程序对应的语法错误报告；对实验结果进行分析。注：其中的测试样例需先用已编写的词法分析程序进行处理。遇到问题：指导书中给出的文法有二义性和左递归，直接使用预测分析法进行分析会导致程序无限循环或不能正确分析。解决方法：改写文法，消除其中的二义性和左递归。程序打印预测分析表如下：为方便查看，导入到excel中如下所示：（建议放大查看）测试程序：分析结果：错误报告：结果分析：源程序第1-4行是不同种类的声明语句，从分析结果图一可看到最终都规约为语法变量D。源程序第5-7行是不同种类的赋值语句，从图二可