编译原理课程设计报告(语法分析)

1、河海大学物联网工程学院（常州）课程设计报告题 目 编译原理课程设计 授课班号 专 业 计算机科学与技术 学生姓名 学 号 指导教师 目 录一、课程设计概要1二、语法分析设计思想1地位及作用1设计思路1分析方法1使用文法1First集合和Follow集合1构造LR(0)项集规范簇2构造SLR(1)分析表2构造字符串的分析过程2三、语法分析器设计算法2First集合生成算法2Follow集合生成算法2计算项集I的闭包2状态之间的转换3构造LR(0)项集规范簇3构造SLR(1)分析表3句子识别3四、项目整合4五、流程图5构造Follow集合的流程图5语法分析流程图6六、主要函数描述7Follow函数

2、描述7项集I的闭包函数描述7项集生成函数描述7ActionGoto表生成函数8句子识别函数8七、运行结果截图9主界面9Action矩阵和Goto矩阵9语法分析结果10八、课程设计小结10一、课程设计概要课程设计由词法分析、语法分析及语义分析构成。词法分析主要是属性表的生成与展示；语法分析主要是ActionGoto表的生成、驱动程序的编写和ActionGoto表的展示；语义分析组要是四元式的生成与展示。每个部分由一位小组成员单独完成，小组成员经过讨论和协商完成整个课程设计的要求，构成一个完整的系统。作为本次课程设计的组长，我主要负责的是语法分析部分以及如何将以上三部分整合，故在此报告中将着重对语

3、法分析部分和整合部分进行阐述，其他部分将在词法分析、语义分析的报告中得到相应得阐述。二、语法分析设计思想地位及作用语法分析是根据某种给定的形式文法对由单词序列（如英语单词序列）构成的输入文本进行分析并确定其语法结构的一种过程。它通常用词法分析所产生的属性表序列作为输入，来识其输入的序列是否满足文法的要求。设计思路分析方法语法分析器的任务主要是确定是否可以以及如何从语法的起始符号推导出输入符号串，主要可以通过两种方式完成：自顶向下分析：根据形式语法规则，在语法分析树的自顶向下展开中搜索输入符号串可能的最左推导。单词按从左到右的顺序依次使用。自底向上分析：语法分析器从现有的输入符号串开始，尝试将其

4、根据给定的形式语法规则进行改写，最终改写为语法的起始符号。我采用的是自底向上的分析技术，主要使用的是SLR(1)分析方法。使用文法SLR(1)分析法的输入是拓广文法GZ，如下所示：Z:=S S:=i=E E:=E+T E:=T T:=T*F T:=F F:=P P:=(E) P:=i P:=n文法存储struct Rule char 左部符号； char 右部符号MaxRightLenth； int右部长度；; /声明结构体类型文法采用上述的结构体数组进行存储。First集合和Follow集合因为在SLR(1)中我们要用到非终结符的Follow集合，而求Follow集合的我们又需要非终结符的F

5、irst集合，所以，我们要先求他的First集合。在实现的过程中，我将求First集合和Follow集合都封装在了Experement07这个类中了。在使用的过程中，只要给出非终结符、终结符和所有的文法，就能求出其文法对的First集合和Follow集合了！详细实现见工程中的Experement07.cs文件中的源码。构造LR(0)项集规范簇LR(0)项集规范簇和规约式的左侧非终极符的follow集合可以用来构造SLR(1)分析表。LR(0)项集规范簇的求解包含三部分：项集闭包的求解：由于项集中包含的项是动态增加的，因此，项集采用动态的数组List来存储。转换状态的求解：确定状态之间的转换状态

6、I遇到符号X(X(VtVn)转换到的状态定义为：GO(I，X)=CLOSURE(AX.| A.XI，其中AX.称为A.X的后继项。项集规范簇的构造：从 I0的项集闭包开始，根据状态的转换，不断增加项集规范簇中的项集个数，直至项集不再增加为止。构造SLR(1)分析表ActionGoto表的构造主要是通过项集之间的跳转关系和文法产生式的规约关系来产生。当一个产生式的识别位置到达最后的时候，那么就根据这个产生式前面的非终结符的Follow集合来规约到到达状态，填入Action表中。每一个项集状态如果通过其他的非终结符跳转到自己活着别的项集状态，那么我们就对其规约到跳转状态，填入Action表中。如果

7、是通过非终结符，那么我们就将跳转的最终的状态填入Goto表中。构造字符串的分析过程在正确的程序编译过程中，编译时需要根据词法分析器中的SLR(1)分析表来判断所要编译的句子是不是该文法的句子。字符串的分析过程中要求给出字符串的每一步的分析过程，输出每一步所用的文法推导式。测试字符串的输入也是采用外部文件输入方式。三、语法分析器设计算法First集合生成算法扫描所有左部为A的产生式， (1)、若-> ，则将并入First(A)。 (2)、若->a ，则将a并入First(A)。 (3)、若->B.，则将First(B)并入First(A)。 (4)、若->XB.或->

8、;Xa.，且X->，则类似于(2)、(3)处理。Follow集合生成算法扫描所有右部包含A的产生式， (1)、若B->xAy ，则将First(y)中的非终极符并入Follow(A)。 (2)、若B->xA，或者B->xAy且y->则将Follow(B)并入Follow(A)。 (3)、若是开始符，则将#并入Follow(A)。构造SLR(1)分析表计算项集I的闭包CLOSURE(I)=I B.| A.BI，BP。将起始文法并入I。对于I中，若A->.B且有产生式B->，那么将B->.并入I。对于A->A的产生式，判断I中是否已经存在该产生

9、式，如果存在，继续扫描I中的下一条文法。循环(1)、(2)、(3),直到I不再增大。状态之间的转换GO(I，X)=CLOSURE(AX.| A.XI，其中AX.称为A.X的后继项。J为GO到的项集。将J置空。对I中每一个形如A->.X的项，将A->X .并入J；调用CLOSURE(J)，生成J的闭包。构造LR(0)项集规范簇根据起始符号，构造初始项集I0,将I0并入项集规范簇C对C中的每个项集I，若GO(I，X)非空且不在C中，那么将GO(I，X)并入C。循环(2)、(3)直到C不再增大。构造SLR(1)分析表对C中的项集IK如果满足GO(Ik ,A )= Ij 且A为非终极符，那

10、么置矩阵GOTOkA=j; 对IK中的每项，若A->.a且GO(Ik ,a)=I j，那么置ACTIONka=j+1000，表示移进操作;若A->.,那么对Follow(A)中的每个终结符a, 置ACTIONka=1100+j，表示规约操作;若拓广文法的第一项S->E.，那么置ACTIONk#=1200，表示接受句子。循环IK中的每一项；循环C中的每一项。句子识别FLAG：=TRUE； WHILE FLAG DO 把状态栈顶元素上托出去并放在S中； IF ACTIONSa=Sj THEN 把符号a推入符号栈； 把状态j推入状态栈； 把下一个输入符号读进a； ELSE IF A

11、CTIONSa=Rj THEN 从符号栈顶退出构成句柄的相应符号串； 从状态栈顶退出与句柄长度相等的若干状态； 把规则j的左部非终极符A 推入符号栈； 10把GOTOtop(状态栈)A 推入状态栈； 输出规则式j； ELSE IF ACTIONSa=acc THEN FLAG:=FALSE； ELSE ERROR； END语法分析总控程序主要利用两个栈作为语法分析的载体，其中一个栈为状态栈，另一个栈为符号栈。算法通过状态栈中栈顶的终结符号与输入符号中当前输入符号来查找ActionGoto表来进行移进和规约，进行一系列的操作。通过ActionGoto表的驱动来使字符串来进行规约到可接受状态，否则

12、出错。四、项目整合工程CP：为实现项目业务逻辑类文件 工程工程MyCompiler：为可视化界面 工程五、流程图构造Follow集合的流程图语法分析流程图六、主要函数描述Follow函数描述变量名说明函数名generateFollow()该函数在类Experient07中实现，用来求一个文法的所有非终结符的Follow集合的传入参数void由于是类内的函数，在对象构造的时候，所需参数已经通过构造函数传入，所以此函数用到的参数有，文法，终结符，非终结符返回值void项集I的闭包函数描述变量名说明函数名TragerAddItemSet()该函数在类Experient14中实现，用于生成某一个项集中

13、的一个产生式所触发的所有后继项传入参数RuleItem RI项中加入的规则ruleint Position_ISList这个项的在ISList中的位置返回值void项集生成函数描述变量名说明函数名GetStateTransitionDiagram()该函数在类experient14中实现，用于生成所有的项集传入参数void由于是类内的函数，在对象构造的时候，所需参数已经通过构造函数传入，所以此函数用到的参数有，文法，终结符，非终结符返回值void返回值已经封装在类的内部，所以此处实际的返回值是ISList（项集的列表）ActionGoto表生成函数变量名说明函数名GetGotoActionTa

14、ble()该函数在类Experient14中实现，用来通过生成的项集来构造ActionGoto表传入参数void由于是类内的函数，在对象构造的时候，所需参数已经通过构造函数传入，所以此函数用到的参数有，文法，终结符，非终结符返回值void返回值已经封装在类的内部，所以此处实际的返回值是GotoActionTable（数据结构是hash表）句子识别函数变量名说明函数名AnalysisSentence()该函数在类Experient15中实现，用来通过GotoAction表的驱动来识别句子传入参数int StartPlace要分析的句子在属性表的起始位置返回值bool分析成功返回true否则返回f

15、alse七、运行结果截图主界面菜单“生成”中有：词法分析、ActionGoto表、语法分析、语义分析等菜单项。Action矩阵和Goto矩阵说明：由于设计的时候采用键值对的方式存储，此处给出真正的表结构不是很方便。所以采用了列表的方式展示。意思是：项X经过A或者a（A为非终结符，a未终结符）结果是SX或RX或X（SX为移进X压入栈中，RX为用第X个产生式归约，X为到第X项）。语法分析结果对于语义分析，我们给给出的输出文本是在语义分析时候所依次使用的产生式。八、课程设计小结成员分工毛凌霄：词法分析；王冲：语法分析；周潇：语义分析；心得体会在不到一个星期的时间里，我们从查阅资料、互相讨论，到综合想

16、法、征求老师意见，过得十分充实和紧张，虽然课程设计比我们想象的要困难得多，但是我们也拿出耐心和毅力，获得了最终方案。如今我明白课程设计对我来说的意义，它不仅仅是让我们把所学的理论知识与实践相结合起来，提高自己的实际动手能力和独立思考的能力，也让我学会从各方意见和想法中提取精华，这次设计中的很多地方都是源于和同学的大量讨论获得的，这种讨论对思维的激发和创新让我收获颇多。 这次课程设计使自己学到了不少知识，也经历了不少艰辛，但收获同样巨大。通过这次课程设计我也发现了自身存在的不足之处，虽然感觉理论上已经掌握，但在运用到实践的过程中仍有意想不到的困惑，经过一番努力才得以解决。这也激发了我今后努力学习的兴趣，我想这将对我以后的学习产生积极的影响。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持