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

1、.编译原理课程实验报告实验2：语法分析院系软件学院学号任课教师指导教师实验地点软件学院三楼机房实验时间2016/10/30/星期日实验课表现出勤、表现得分实验报告得分实验总分操作结果得分一、需求分析得分要求：采用至少一种句法分析技术（LL(1)、SLR(1)、LR(1)或LALR(1)）对类高级语言中的基本语句进行句法分析。阐述句法分析系统所要完成的功能。 本语法分析器是在词法分析器的基础上实现对类高级语言中的基本语句进行句法分析，基本功能如下：（1）能识别以下几类语句：Ø 声明语句（包括变量声明、数组声明、记录声明和过程声明）Ø 表达式及赋值语句（包括数组元素的引用和赋值

2、）Ø 分支语句：if_then_else Ø 循环语句：do_while Ø 过程调用语句（2）本语法分析器采用自顶向下的分析技术，能根据导入的文法，自动计算first集和follow集，能够生成每个产生式的select集，并自动生成预测分析表。（3）本语法分析器具备语法错误处理能力，可以进行错误检测，如果检测到在出错时，采用恐慌模式，能够给出错误提示信息，格式：错误项 错误原因 行号a)忽略输入中的一些符号，直到输入中出现选定的同步词法单元集合中的某个词法单元，同步集合的选取是非终结符的follow集；b)如果终结符在栈顶而不能匹配，弹出此终结符。c)输入栈中缺

3、少某些应有的符号，比如只有右括号没有左括号等，会给出相应的提示。（4）系统的输入形式多样：可以通过文件导入文法和测试用例，可以通过用户界面显示并编辑测试用例。测试用例涵盖了第（1）条中列出的各种类型的语句，并设置了一些语法错误。（5）系统的输出分为两部分：一部分是打印输出语法分析器的FIRST集、FOLLOW集、select集和LL(1)分析表。另一部分是打印输出语法分析结果。 （6）本系统还实现了输出语法分析树的功能，让语法分析的过程更清晰。二、文法设计得分要求：给出如下语言成分的文法描述。Ø 声明语句（包括变量声明、数组声明、记录声明和过程声明）Ø 表达式及赋值语句（包

4、括数组元素的引用和赋值）Ø 分支语句：if_then_else Ø 循环语句：do_while Ø 过程调用语句 本语法分析器主要针对C语言进行文法设计，下面给出各语言成分的文法描述。 程序入口：Program->P P->D P /支持连续声明 P ->S P P->1） 声明语句：D ® proc id ; D S|T id; /支持过程声明和变量声明T X C | recordD/支持结构体声明X short|int | long|float|double|char|string/支持多种基本类型的声明C numC | /支

5、持数组的声明2)表达式及赋值语句:S® id = E ;| L = E ; E ® E + E | E * E | -E | (E) | id | digit | LL ® idE | LE/支持数组元素的引用和赋值3) 控制流语句:S ®if B then S1 else S2| while B do S1B B | B /或语句| B && B /且语句| ! B /非语句| (B) /使用括号| E relop E /关系语句| true /bool型| false/bool型relop < | <= | = | !=

6、| > | >=/关系符号4）过程调用语句S ®callid (Elist)Elist ® Elist, EElist ® E 下面给出整个程序的无二义性，无左递归的LL（1）文法：Program->PP->D P|S P|emptyD->proc T id ( M ) P |T id A ;|record id P M->X id M'M'->, X id M'|emptyA->= F|empty|, id AF->digit|id|char| G |stringG->H G&#

7、39;G'->, H G'|emptyH->digit|charT->X CX->short|int|long|float|double|char|void|string|booleanC-> digit C|emptyS->L = E ;|if B then S else S|while B do S|call id ( Elist ) ;|return E ;E->- E E'|( E ) E'|digit E'|L E'|string EE'->+ E E'|* E E'

8、;|emptyL->id L'L'-> digit L'|emptyB->! B B'|( B ) B'|E relop E B'|true B'|false B'B'->or B B'|and B B'|emptyrelop-><|<=|=|!=|>|>=Elist->E Elist'Elist'->, E Elist'|empty 注：此处用empty代表空三、系统设计得分要求：分为系统概要设计和系统详细设计。（1

9、） 系统概要设计：给出必要的系统宏观层面设计图，如系统框架图、数据流图、功能模块结构图等以及相应的文字说明。1）系统的数据流图：说明说明：本语法分析器是基于上一个实验词法分析器的基础上，通过在界面写或者是导入源程序，词法分析器将源程序识别的词法单元传递给语法分析器，语法分析器验证这个词法单元组成的串是否可以由源语言的文法生成，能够输出语法分析的结果，文法的first集、follow集和预测分析表，当然也可以以易于理解的方式报告语法错误。2） 系统框架图本系统框架主要是三部分，一部分是词法分析，负责识别源程序的词法单元识别，并将其存储，以供语法分析时读取；第二部分是文法分析部分，负责将导入的文法

10、进行分析，得出文法的first集和follow集，以及自动构造出预测分析表，在语法分析时进行查询；第三部分是用户界面，提供源程序输入功能，以及语法分析结果的显示，显示语法分析树，还有first集、follow集和预测分析表的展示。（2）系统详细设计：对如下工作进行展开描述ü 核心数据结构的设计核心数据结构主要有两种:1) Tuple三元组为了存储预测分析表，我使用Tuple<string,string,string>三元组的数据结构，分别存储产生式的头部，产生式体，输入符号。2) Stack栈为了能够在语法分析时根据预测分析表来进行分析，我写了一个CStack的类用来实现

11、栈的数据结构，在进行语法分析时，一个栈用来存储文法符号，一个栈用来存储输入符号，然后根据预测分析表进行语法分析。ü 主要功能函数说明主要功能函数:1) IDContent类：功能：充当符号表的角色，主要是用来保存关键字，运算符，界符，转义字符等各类单词。主要函数：bool isConstCh(string str)/判断是否转义字符bool isLetter_(char c)/判断是否字母或下划线bool isDigit(char c)/判断是否数字bool isBlank(char c)/ 判断是否是空格、制表符、换行、回车bool isKeyWord(string str)/判断

12、是否关键字bool isBoundary(char c)/判断是否是边界符号bool isOperator(string ch)/判断是否运算符2）Identifier类功能：识别单词的核心类主要函数：string isID(string str, refint i)/是否是标识符string isSixteen(string str, refint i,outbool right)/是否16进制数string isEight(string str,refint i,outbool right)/是否8进制数string isNumber(string str, refint i, outbo

13、ol right)/是否是常数string isOperator(string str, refint i, outbool right)/是否是运算符string isNote(string str, refint i, outbool right)/是否注释string isBoundary(string str, refint i,outbool right)/是否界符string isChar(string str, refint i, outbool right)/是否字符常数3） FirstAndFollow类功能：得到first集、follow集、select集、预测分析表pub

14、licvoid getFirstCollection()/得到first集合publicvoid getFollowCollection()/得到follow集合publicvoid getSelectCollection()/得到预测分析表publicvoid getAnalysisTable(string str1, string str2, string str3)/得到预测分析表publicvoid errorHandle()/加入同步词法单元4） CStack类功能：栈结构publicbool isEmpty()/判断栈是否为空publicvoid push(object item)

15、/往栈中加入一个元素publicobject pop()/从栈中弹出一个元素publicobject peek()/返回栈顶对象5） Form类publicvoid analysis(string str)/词法单元识别publicvoid parse()/语法单元识别privatevoid导入文法ToolStripMenuItem_Click(object sender, EventArgs e)/导入文法privatevoid显示语法分析树ToolStripMenuItem_Click(object sender, EventArgs e)/输出语法分析树privatevoid addLi

16、stview1Item()/输出first集和follow集privatevoid addListview3Item()/输出预测分析表ü 程序核心部分的程序流程图语法分析核心部分流程图：四、系统实现及结果分析得分要求：对如下内容展开描述。（1） 系统实现过程中遇到的问题；实现过程中主要遇到的问题有：1) 如何修改文法使其时LL（1）文法通过对文法的修改，主要是对文法消除左递归，消除二义性，以及提取公因式等，最终对于相同左部的产生式他们的select集不相交，得到了LL（1）文法。 2）如何得到文法符号的first集 对于终结符，其first集就是本身，但是对非终结符，在遍历的时候依

17、赖于其他的非终结符，于是我采用循环遍历的方法，如果当前某个非终结符的first集依赖于其他非终结符，且其他非终结符的first集还没有求出来，则跳过当前的非终结符求下一个非终结符的first集，直到其依赖的非终结符的first集求出来后再求解。直到所有的非终结符的first集求出来后，循环结束，就得到了所有文法符号的first集合。 3）如何得到非终结符的follow集 为了使思路清晰，我采用两遍遍历的方式来求非终结符的follow集。 第一遍之后，所有非终结符都将得到一个暂时的follow集（不是最终的follow集），第二遍的目标就是发现其中是否有非终结符的follow集发生了改变，如果改

18、变，则继续遍历整个文法，直到没有新的符号加入follow集中。 求follow集的具体思想就是：不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW集合中为止Ø 将$放入FOLLOW( S )中，其中S是开始符号，$是输入右端的结束标记Ø 如果存在一个产生式AB，那么FIRST ( )中除之外的所有符号都在FOLLOW( B )中Ø 如果存在一个产生式AB，或存在产生式AB且FIRST ( ) 包含，那么FOLLOW( A )中的所有符号都在FOLLOW( B )中 4）如何根据预测分析表进行语法分析 这里主要依赖于栈的结构，将经过词法分析得到的词法单

19、元压入输入栈，将文法起始符号压入文法栈，然后根据预测分析表得到各个产生式进行语法分析。（2） 输出该句法分析器的分析表；因为预测分析表实在是过于庞大，因此本处分段截取预测分析表，下面的表是接在上面表的右侧。（3） 针对一测试程序输出其句法分析结果；测试程序：语法分析结果：语法分析树：（4） 输出针对此测试程序对应的语法错误报告；带错误的测试程序：语法错误报告：（5） 对实验结果进行分析。总结：本语法分析器具有强大的语法分析功能l 允许变量的连续声明，比如inta,b,c；l 允许声明的同时赋值，比如string c = “你好”；l 允许对数组的声明和引用，同时进行赋值，比如char4 a = a,b,c,d;a0 = m；l 支持多种类型的声明和赋值，比如int，s