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

编译原理课程实验报告实验2：语法分析姓名院系软件学院学号任课教师指导教师实验地点实验时间实验课表现出勤、表现得分实验报告得分实验总分操作结果得分一、实验目的本次实验的目的为：巩固对语法分析的基本功能和原理的认识、通过对语法分析表的自动生成加深对语法分析表的认识、理解并处理语法分析中的异常和错误。我是通过自己实现编写一个SLR(1)语法分析器并编写作为其输入的C语言文法规则，在编程的过程中解决问题并加深自己对语法分析器相关知识的理解以实现上述目的的。关于语法分析器的编写，编写语言是C++，编写的是SLR(1)文法分析器以及C语言文法规则，开发环境为QT。二、实验内容一、语法规则描述下面给出本程序的语法规则描述，34~42给出了表达式的定义，28给出了循环语句的定义，27给出了选择语句的定义，03给出了函数的定义，19给出了声明语句的定义，26给出了跳转语句的定义，详细的定义如下：01:<程序>→<外部声明>|<程序><外部声明>02:<外部声明>→<函数定义>|<声明语句>03:<函数定义>→<类型说明符><函数声明符><复合语句>04:<函数声明符>→<指针><直接函数声明符>|<直接函数声明符>05:<直接函数声明符>→id(<参数列表>)|id()06:<参数列表>→<参数>|<参数>,<参数列表>07:<参数>→<类型说明符><标识>08:<语句>→<复合语句>|<单一语句>09:<复合语句>→{}|{<单一语句列表>}10:<单一语句列表>→<单一语句>|<单一语句><单一语句列表>11:<单一语句>→<赋值语句>|<声明语句>|<选择语句>|<循环语句>|<跳转语句>|<表达式语句>|<空语句>|<函数调用语句>12:<函数调用语句>→<函数调用>;13:<函数调用>→id(<形参列表>)|id()14:<形参列表>→<形参>,<形参列表>|<形参>15:<形参>→<E>|<函数调用>16:<赋值语句>→<赋值表达式>;17:<赋值表达式>→<标识><赋值运算符><赋值表达式右部>18:<赋值表达式右部>→<E>|<函数调用>19:<声明语句>→<声明表达>;20:<声明表达>→<类型说明符><声明项列表>21:<声明项列表>→<声明项>|<声明项>,<声明项列表>22:<声明项>→<标识>|<赋值表达式>23:<指针>→*|*<指针>24:<标识>→id|<指针>id25:<表达式语句>→<E>;26:<跳转语句>→break;|continue;|return;|return<E>;27:<选择语句>→if(<E>)<语句>28:<循环语句>→for(<for1>;<for2>;<for3>)<语句>|do<语句>while(<E>);|while(<E>)<语句>29:<for1>→<空>|<赋值表达式>|<声明表达>|<E>30:<for2>→<空>|<赋值表达式>|<E>31:<for3>→<空>|<E>32:<空语句>→;33:<空>→34:<E>→!<G>|<G>35:<G>→<G>&&||<H>|<H>36:<H>→<H><关系运算符><I>|<I>37:<I>→<I>+-<J>|<J>38:<J>→<J>*/%<K>|<K>39:<K>→<L>++--|<L>40:<L>→+-++--<M>|<M>41:<M>→&<N>|<N>42:<N>→(<E>)|<运算单位>43:<运算单位>→<常量>|<标识>44:<常量>→四种常量45:<关系运算符>→关系运算符们46:<赋值运算符>→赋值运算符们47:<类型说明符>→类型说明符们二、语法分析程序的总体结构及实现（1）语法分析器的运行流程语法分析程序以词法分析器作为子程序，词法分析器读取测试文件生成符号表后将符号表交给语法分析器；语法分析器被创建后进行初始化，初始化的流程如下：首先根据第一个输入参数（语法规则程序名），读取文法规则保存到Grammar结构中，然后根据文法生成Frist集保存在FIRST结构中，然后结合FIRST中的内容生成Follow集，保存在FOLLOW结构中；再根据Grammar结构生成LR(0)项目集规范族保存在结构CanonicalCollection中；然后根据CanonicalCollection中的内容生成ACTION表和GOTO表；然后根据两张表中的内容以及FOLLOW集中的内容对词法分析器传入的符号表进行移进规约操作。（2）语法分析器的总体结构关于语法分析器的结构，下面给出分析器的模块划分：1）移进规约模块：负责在ACTION表和GOTO表生成之后进行移进规约，其中涉及到检测的语法错误时的错误处理；2）语法模块：该模块负责将语法规则信息从文件读入到内存；3）项目集规范族生成模块：该模块负责生成Grammar的项目集规范族；4）Follow集生成模块：该模块负责生成Grammar的Follow集；三、语法分析表及其数据结构和查找算法（1）语法分析表的数据结构关于语法分析表（ACTION表和GOTO表）的结构：GOTO表是一个大小为m*n的int型的二维数组，m的大小等于项目集规范族中项目集闭包的数量，即状态数，n的大小等于语法中非终结符的数量；ACTION是一个m*k大小的act型二维数组，k的大小等于终结符的数量加一；加一是因为要考虑符号为空（#）的情况，让ACTION[i][0]（0<i<m）代表从状态i读入空的动作；关于act结构：act由一个char型的act代表要执行的动作，一个int型的index表示如果act代表移进或规约后状态转移的下标或用第几个产生式规约。（2）语法分析表的查找算法关于语法分析表的查找算法：1）维护两个指针bP和cP，初始化为零；2）初始化分析栈，压入状态零和空；3）如果cP小于词法分析器符号表长度，则循环4）到8）；4）读一个终结符word，以word.typeNum查找ACTION表得到动作x；5）如果x.act=SHIFT，则移进该终结符，cP=cP+1；6）如果x.act=REDUCE，则找到对应产生式后在分析栈弹出右部符号数*2的元素，输出；7）如果x.act=ACC，循环结束；8）如果x.act=ERROR，bP=bP+1，cP=bP，打印错误信息，继续进行循环；四、语法分析表的生成算法关于语法分析表的生成算法：读入文法后对文法进行拓广；产生初始的项目集闭包；产生项目集规范族；产生Follow集；初始化ACTION表和GOTO表（分配空间）；项目集规范族中的Ii对应i，I0对应0，0为初始状态；对于从I0到Im的每个状态闭包Ii进行遍历，对于Ii的每一个转移，如果在ACTION表或GOTO表中填入相关信息，对于Ii中每一个可以规约的项目，向后看一个终结符，如果在Follow集中则在ACTION表中填入规约的相关信息，如果已经填入过移进信息则说明出现了错误，该文法并非SLR(1)文法，输出错误信息；如果表项经过上述步骤都没有填入数据则填入ERROR；五、错误处理关于本语法分析程序的错误处理：语法分析器的查表算法部分已经介绍过了，本程序只采用紧急方式恢复的策略，发现当前无法正确匹配后则退回到bP所指向的位置，抛弃一个终结符后继续进行语法分析。三、实验结果针对一测试程序输出其语法分析结果；输出针对此测试程序对应的语法错误报告；四、实验中遇到的问题总结实验过程中遇到的问题如何解决的？问题1：关于action表中需要存储空‘#’以代表在某个状态读入空后所应该进行的动作，如何在action表中安排空这一列？答：以0代表空，所以action表的列数为终结符数量加1，其中第0列表示某状态读入空时应该执行的动作。问题2：关于数据结构，显然，文法中的终结符和非终结符都应该有一个唯一的标号来标识这是哪个文法符号，如何进行存储（文件和内存中）？用什么约束使得处理得到简化？答：我是通过一个short型的整型数标识文法符号的；文法输入文件的约束是，以终极符的数量加一为第一个非终结符的标识值，之后依次加一，必须连续且不重复。对于终结符，从1开始为第1个终结符的标识值（0代表空），以后依次加一，必须连续且不重复；如此设计可以方便后续的action表和goto表的构建和查询操作。问题3：构建项目集规范族或计算first集和follow集的过程中常常需要用到集合操作，如何编写相关代码？答：可以直接使用现有的库或者自己实现一个set数据结构。（二）思考题的思考与分析思考题1：给出在生成语法分析表时所遇到的困难，以及是如何处理的？答：要生成语法分析表（action表和goto表）需要文法非终结符的follow集，要求follow集还需要先求first集，还要求以拓展的产生式的项目闭包为初始状态的项目集规范族cc，在求cc的过程中将各个状态间的转移记录下来；加起来任务很多，但是规定好接口后逐一编写调试的过程还是很顺利的，并没有碰到什么问题。思考题2：思考还可以什么形式来给出语法分析的结果？答：本程序只是简单地直接将规约用到的产生式打印出来，这样结合输入的终结符序列就可以构建出一棵抽象语法树；另外，如果通过进一步处理直接绘制出语法树并注上详细信息会使得结果更加直观。思考题3：如果在语法分析中遇到了语法错误，是应该中断语法分析呢，还是应该进行适当处理后继续语法分析，你是怎么处理的？答：应该进行适当的处理后继续进行语法分析，因为程序的语法错误可能通过简单的紧急方式恢复即可被排除，如果源程序较大，编译时间会很长，因为一点小错误就中断不人性化；另外，如果程序不止一处错误，继续运行有助于帮助用户更快的发现自己程序的各个错误而不是编译一次只能发现一个错误。我是通过最简单的紧