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

河海大学物联网工程学院（常州）课程设计报告题目编译原理课程设计题目编译原理课程设计TOC\o"1-5"\h\z\o"CurrentDocument"一、 课程设计概要 1\o"CurrentDocument"二、 语法分析设计思想 1\o"CurrentDocument"地位及作用 1\o"CurrentDocument"设计思路 1分析方法 1使用文法 1First集合和Follow集合 1\o"CurrentDocument"构造LR(O)项集规范簇 2\o"CurrentDocument"构造SLR(l)分析表 2构造字符串的分析过程 2\o"CurrentDocument"三、 语法分析器设计算法 2\o"CurrentDocument"First集合生成算法 2\o"CurrentDocument"Follow集合生成算法 2\o"CurrentDocument"计算项集I的闭包 2\o"CurrentDocument"状态之间的转换 3构造LR(O)项集规范簇 3构造SLR(l)分析表 3\o"CurrentDocument"句子识别 3\o"CurrentDocument"四、 项目整合 4\o"CurrentDocument"五、 流程图 5构造Follow集合的流程图 5语法分析流程图 6\o"CurrentDocument"六、 主要函数描述 7Follow函数描述 7\o"CurrentDocument"项集I的闭包函数描述 7\o"CurrentDocument"项集生成函数描述 7ActionGoto表生成函数 8\o"CurrentDocument"句子识别函数 8\o"CurrentDocument"七、 运行结果截图 9\o"CurrentDocument"主界面 9Action矩阵和Goto矩阵 9\o"CurrentDocument"语法分析结果 10\o"CurrentDocument"八、 课程设计小结 10一、 课程设计概要课程设计由词法分析、语法分析及语义分析构成。词法分析主要是属性表的生成与展示；语法分析主要是ActionGoto表的生成、驱动程序的编写和ActionGoto表的展示；语义分析组要是四元式的生成与展示。每个部分由一位小组成员单独完成，小组成员经过讨论和协商完成整个课程设计的要求，构成一个完整的系统。作为本次课程设计的组长，我主要负责的是语法分析部分以及如何将以上三部分整合，故在此报告中将着重对语法分析部分和整合部分进行阐述，其他部分将在词法分析、语义分析的报告中得到相应得阐述。二、 语法分析设计思想地位及作用语法分析是根据某种给定的形式文法对由单词序列(如英语单词序列)构成的输入文本进行分析并确定其语法结构的一种过程。它通常用词法分析所产生的属性表序列作为输入，来识其输入的序列是否满足文法的要求。设计思路分析方法语法分析器的任务主要是确定是否可以以及如何从语法的起始符号推导出输入符号串，主要可以通过两种方式完成：自顶向卞分析：根据形式语法规则，在语法分析树的自顶向下展开中搜索输入符号串可能的最左推导。单词按从左到右的顺序依次使用。自底向上分析：语法分析器从现有的输入符号串开始，尝试将其根据给定的形式语法规则进行改写，最终改写为语法的起始符号。我采用的是自底向上的分析技术，主要使用的是SLR(l)分析方法。使用文法SLR(l)分析法的输入是拓广文法G[Z],如下所示：Z::=SS::=i=EE::=E+TE::=TT::=T*FT::=FF::=PP::=(E)P::=iP::=n文法存储stmctRulef1chai左部符号；chai右部符号[MaxRightLenth]:mt右部长度；};〃声明结构体类型文法采用上述的结构体数组进行存储。First集合和Follow集合因为在SLR(l)中我们要用到非终结符的Follow集合，而求Follow集合的我们又需要非终结符的First集合，所以，我们要先求他的First集合。在实现的过程中，我将求First集合和Follow集合都封装在了Experement07这个类中了。在使用的过程中，只要给出非终结符、终结符和所有的文法，就能求出其文法对的First集合和Follow集合了！详细实现见工程中的Expeiement07.cs文件中的源码。构造LR(O)项集规范簇LR(O)项集规范簇和规约式的左侧非终极符的foUow集合可以用来构造SLR(l)分析表。LR(0)项集规范簇的求解包含三部分：项集闭包的求解：由于项集中包含的项是动态增加的，因此，项集采用动态的数组List来存储。转换状态的求解：确定状态之间的转换状态I遇到符号X(XW(VtUVii))转换到的状态定义为：GO(LX)=CLOSURE({AfaX・B|A-a・XBWI},其中A-aX・B称另A-ci.XB的后继项。项集规范簇的构造：从10的项集闭包开始，根据状态的转换，不断增加项集规范簇中的项集个数，直至项集不再增加为止。构造SLR(l)分析表ActionGoto表的构造主要是通过项集之间的跳转关系和文法产生式的规约关系来产生。当一个产生式的识别位置到达最后的时候，那么就根据这个产生式前面的非终结符的Follow集合来规约到到达状态，填入Actum表中。每一个项集状态如果通过其他的非终结符跳转到自己活着别的项集状态，那么我们就对其规约到跳转状态，填入Action表中。如果是通过非终结符，那么我们就将跳转的最终的状态填入Goto表中。构造字符串的分析过程在正确的程序编译过程中，编译时需要根据词法分析器中的SLR(l)分析表来判断所要编译的句子是不是该文法的句子。字符串的分析过程中要求给出字符串的每一步的分析过程，输出每一步所用的文法推导式。测试字符串的输入也是采用外部文件输入方式。三、语法分析器设计算法First集合生成算法扫描所有左部为A的产生式，、若A->£,则将£并入First(A)o、若A->a,则将a并入Fiist(A)。、若A4B.•…,则将Fust(B)Jt入First(A)。、若A->XB.…-或A->Xa•.…，且X->£,则类似于(2)、(3)处理。Follow集合生成算法扫描所有右部包含A的产生式，(1)、若B->xAy,则将Fust(v)中的非£终极符并入Follow(A)。⑵、若B->xA,或者B->xAy且y->E则将Follow(B)并入Follow(A)o(3)、若A是开始符，贝IJ将#弄入Follow(A)。构造SLR(l)分析表计算项集I的闭包CLOSURE(I)=IU{E~・丫|A~a.EBWI,Y^P}。将起始文法并入Io对于I中，若A->a.BP且有产生式B->n,那么将B->.n并入I。对于A->Aa的产生式，判断I中是否已经存在该产生式，如果存在，继续扫描I中的下一条文法。循坏(1)、(2)、(3),直到I不再增大。状态之间的转换GO(LX)=CLOSURE({A—aX・B|AfQ・XBWI},其中A-QX.B称为A-a.XB的后继项。J为GO到的项集。将J置空。对I中每一个形如A->Q・XB的项，将A・>aX・B并入J：调用CLOSURE(J),生成J的闭包。构造LR(O)项集规范簇根据起始符号，构造初始项集10,将10并入项集规范簇C对C中的每个项集I,若GO(I,X)非空且不在C中，那么将GO(I,X)并入C。循坏(2)、⑶直到C不再增大。构造SLR(l)分析表对C中的项集IK如呆满足GO(Ik,A)==Ij且A为非终极符，那么置矩阵GOTO[k][A]=j;对IK中的每项，若A->a.a3且GO(Ik?a)=Ij,那么置ACTION[k][a]=j+1000,襄示移进操作;若A>a•，那么对Follow(A)中的每个终结符a,置ACTION[k][a]=1100+j,表示规约操作：若拓广文法的第一项S->E.,那么置ACTION[k][#]=1200,表示接受句子。循坏IK中的每一项；循坏C中的每一项。句子识别FLAG：=TRUE；WHILEFLAGDOf把状态栈顶元素上托出去并放在s中；IFACTION[S][a]==SjTHEN{把符号a推入符号栈；把状态J推入状态栈；把下一个输入符号读进a：}ELSEIFACTION[S][a]==RjTHEN{从符号栈顶退出构成句柄的相应符号串:从状态栈顶退出与句柄长度相等的若干状态；把规则J的左部非终极符A推入符号栈；把GOTO[top（状态栈）][A]推入状态栈；输出规则式J:}ELSEIFACTION[S][a]=accTHENFLAG:=FALSE；ELSEERROR：}END语法分析总控程序主要利用两个栈作为语法分析的载体，其中一个栈为状态栈，另一个栈为符号栈。算法通过状态栈中栈顶的终结符号与输入符号中当前输入符号来查找ActionGoto表来进行移进和规约，进行一系列的操作。通过ActionGoto表的驱动来使字符串来进行规约到可接受状态，否则出错。四、项目整合Q館块方龛CP，（2个项目），叵CP>AProperties>・•■引用EGV>GlobalVar.es>GV.csGLA5AttributeWordTabie.esAttributeWordTableItem.es>c«ClassTable.es>c«ClassTableItem.es>c«lDTable.esc*LA.CSSA>c«Classl.es>c«Experement01.es>c«Experement07.esExperementl4.esExpcrcmcntl5.cst>c«GotoArtionTable_Key.esl>c«ltemSet.esl>c«Rule.est>c«Ruleltem.esc*Vialtem.es0App.configl>Proqram.es/回MyCompilerAAPropertiest>引角0App.configD圉Main.csl>Program.es工程CP：为实现项目业务逻辑类文件工程工程MyCompiler：为可视化界面工程五、流程图构造Follow集合的流程图语法分析流程图六、主要函数描述Follow函数描述变量名说明函数名generateFollow()该函数在类Experient07中实现，用來求一个文法的所有非终结符的Follow集合的传入参数void由于是类内的函数，在对象构造的时候，所需参数己经通过构造函数传入，所以此函数用到的参数有，文法，终结符，非终结符返回值void项集I的闭包函数描述变量名说明数函名TragerAddltemSet0该函数在类Experient14中实现，用于生成某一个项集中的一个产生式所触发的所有后继项传入参数RuleltemRI项中加入的规则ruleintPosition_ISList这个项的在ISList中的位置返回值void项集生成函数描述变量名说明函数名GetStateTransitionDiagramO该函数在类experientl4中实现，用于生成所有的项集传入参数void由于是类内的函数，在对象构造的时候，所需参数己经通过构造函数传入，所以此函数用到的参数有，文法，终结符，非终结符返回值void返回值己经封装在类的内部，所以此处实际的返回值是ISList（项集的列表）

ActionGoto表生成函数变量名说明函数名GetGotoActionTable()该函数在类Experientl4中实现，用來通过生成的项集來构造ActionGoto表传入参数void由于是类内的函数，在对象构造的时候，所需参数已经通过构造函数传入，所以此函数用到的参数有，文法，终结符，非终结符返回值void返回值己经封装在类的内部，所以此处实际的返回值是GotoActionTable（数据结构是hash表）句子识别函数变量名说明数函名AnalysisSentence()该函数在类Experientl5中实现，用來通过GotoAction表的驱动來识别句子传入参数intStartPlace要分析的句子在属性表的起始位置返回值bool分析成功返回true否则返回false七、运行结果截图主界面菜单“生成”中有：词法分析、ActionGoto表、语法分析、语义分析等菜单项。叫MyCompiler输出文本13progrcm0c;tp输出文本13progrcm0c;tpini0a12.0bL2,0c;L4bagin0a8=0:<20:0b8=naprcgr^n«xpixti夠b,c;bog；壮4=0x20：b=at2O：c二(a+b)心5：endAction矩阵和Goto矩阵说明：由于设计的时候釆用键值对的方式存储，此处给出真正的表结构不是很方便。所以采用了列表的方式展示。意思是：项X经过A或者a（A为非终结符，a未终结符）结果是SX或RX或X（SX为移进X压入栈中，RX为用第X个产生式归约，X为到第X项）。辎入姑progr^e：<pintdbc;辎入姑progr^e：<pintdbc;beg：iaa=Ox20;b=H2D;c二(a+b)*0x5;end输出文本生质ActionGoto羌项1经眇结杲；xcc顶0经过£结1项U经过】结果：SZ项2经过二结果：S3项3经过E结果：Q项3经过T结杲：5顶3经过F结里：6项3经过F结杲：7顶3经过（结舉：S8项3经过】结果：59项3经过"结果：S10顷4经词#结果：R1项4经过十结杲；S11顶5经过#结里：R3项5经过+结杲：R3顶5经过）结果^R3IffiS込河*结黑：£1少语法分析结果对于语义分析，我们