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

河海大学物联网工程学院（常州） 课程设计报告 题 目 编译原理课程设计 授课班号 专 业 计算机科学与技术 学生姓名 学 号 \ 指导教师 目 录 一、课程设计概要 1 二、语法分析设计思想 1 地位及作用 1 设计思路 1 分析方法 1 使用文法 1 First集合和Follow集合 1 构造LR(0)项集规范簇 2 构造SLR(1)分析表 2 构造字符串的分析过程 2 三、语法分析器设计算法 2 First集合生成算法 2 Follow集合生成算法 2 计算项集I的闭包 2 状态之间的转换 3 构造LR(0)项集规范簇 3 构造SLR(1)分析表 3 句子识别 3 四、项目整合 4 五、流程图 5 构造Follow集合的流程图 5 语法分析流程图 6 六、主要函数描述 7 Follow函数描述 7 项集I的闭包函数描述 7 项集生成函数描述 7 ActionGoto表生成函数 8 句子识别函数 8 七、运行结果截图 9 主界面 9 Action矩阵和Goto矩阵 9 语法分析结果 10 八、课程设计小结 10  一、课程设计概要 课程设计由词法分析、语法分析及语义分析构成。词法分析主要是属性表的生成与展示；语法分析主要是ActionGoto表的生成、驱动程序的编写和ActionGoto表的展示；语义分析组要是四元式的生成与展示。每个部分由一位小组成员单独完成，小组成员经过讨论和协商完成整个课程设计的要求，构成一个完整的系统。 作为本次课程设计的组长，我主要负责的是语法分析部分以及如何将以上三部分整合，故在此报告中将着重对语法分析部分和整合部分进行阐述，其他部分将在词法分析、语义分析的报告中得到相应得阐述。 二、语法分析设计思想 地位及作用 语法分析是根据某种给定的形式文法对由单词序列（如英语单词序列）构成的输入文本进行分析并确定其语法结构的一种过程 设计思路 分析方法 语法分析器的任务主要是确定是否可以以及如何从语法的起始符号推导出输入符号串，主要可以通过两种方式完成： 自顶向下分析：根据形式语法规则，在语法分析树的自顶向下展开中搜索输入符号串可能的最左推导。单词按从左到右的顺序依次使用。 自底向上分析：语法分析器从现有的输入符号串开始，尝试将其根据给定的形式语法规则进行改写，最终改写为语法的起始符号。 使用文法 SLR(1)分析法的输入是拓广文法G[Z]，如下所示： 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集合的我们又需要非终结符的First集合，所以，我们要先求他的First集合。 在实现的过程中，我将求First集合和Follow集合都封装在了Experement07这个类中了。 在使用的过程中，只要给出非终结符、终结符和所有的文法，就能求出其文法对的First集合和Follow集合了！详细实现见工程中的Experement07.cs文件中的源码。 构造LR(0)项集规范簇 LR(0)项集规范簇和规约式的左侧非终极符的follow集合可以用来构造SLR(1)分析表。 LR(0)项集规范簇的求解包含三部分： 项集闭包的求解：由于项集中包含的项是动态增加的，因此，项集采用动态的数组List来存储。 转换状态的求解：确定状态之间的转换状态I遇到符号X(X∈(Vt∪Vn))转换到的状态定义为：GO(I，X)=CLOSURE({A→αX.β| A→α.Xβ∈I}，其中A→αX.β称为A→α.Xβ的后继项。 项集规范簇的构造：从 I0的项集闭包开始，根据状态的转换，不断增加项集规范簇中的项集个数，直至项集不再增加为止。 构造SLR(1)分析表 ActionGoto表的构造主要是通过项集之间的跳转关系和文法产生式的规约关系来产生。当一个产生式的识别位置到达最后的时候，那么就根据这个产生式前面的非终结符的Follow集合来规约到到达状态，填入Action表中。每一个项集状态如果通过其他的非终结符跳转到自己活着别的项集状态，那么我们就对其规约到跳转状态，填入Action表中。如果是通过非终结符，那么我们就将跳转的最终的状态填入Goto表中。 构造字符串的分析过程 在正确的程序编译过程中，编译时需要