河海大学物联网工程学院（常州）

课程设计报告

题    目   编译原理课程设计

授课班号              

专    业   计算机科学与技术  

学生姓名                

学    号      \    

指导教师             

目  录

一、课程设计概要... 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)分析方法。

使用文法

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表中。

构造字符串的分析过程

在正确的程序编译过程中，编译时需要根据词法分析器中的SLR(1)分析表来判断所要编译的句子是不是该文法的句子。字符串的分析过程中要求给出字符串的每一步的分析过程，输出每一步所用的文法推导式。测试字符串的输入也是采用外部文件输入方式。

三、语法分析器设计算法

First集合生成算法

扫描所有左部为A的产生式，

(1)、若Ａ->ε ，则将ε并入First(A)。

(2)、若Ａ->a ，则将a并入First(A)。

(3)、若Ａ->B…..，则将First(B)并入First(A)。

(4)、若Ａ->XB…..或Ａ->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→α.Bβ∈I，B→γ∈P}。

将起始文法并入I。

对于I中，若A->α.Bβ且有产生式B->η，那么将B->.η并入I。

对于A->Aα的产生式，判断I中是否已经存在该产生式，如果存在，继续扫描I中的下一条文法。

循环(1)、(2)、(3),直到I不再增大。

状态之间的转换

GO(I，X)=CLOSURE({A→αX.β| A→α.Xβ∈I}，其中A→αX.β称为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为非终极符，那么置矩阵GOTO[k][A]=j;  

对IK中的每项，若A->α.aβ且GO(Ik ,a)==I j，那么置ACTION[k][a]=j+1000，表示移进操作;若A->α.,那么对Follow(A)中的每个终结符a, 置ACTION[k][a]=1100+j，表示规约操作’;若拓广文法的第一项S->E.，那么置ACTION[k][#]=1200，表示接受句子。

循环IK中的每一项；

循环C中的每一项。

句子识别

FLAG：=TRUE；

WHILE FLAG DO

{

把状态栈顶元素上托出去并放在S中；

 IF ACTION[S][a]==Sj THEN

{

把符号a推入符号栈；

把状态j推入状态栈；

把下一个输入符号读进a；

}

ELSE IF ACTION[S][a]==Rj THEN

{

从符号栈顶退出构成句柄的相应符号串；

从状态栈顶退出与句柄长度相等的若干状态；

把规则j的左部非终极符A 推入符号栈；

把GOTO[top(状态栈)][A] 推入状态栈；

输出规则式j；

}

ELSE IF ACTION[S][a]=acc THEN

FLAG:=FALSE；

ELSE ERROR；

}

END

语法分析总控程序主要利用两个栈作为语法分析的载体，其中一个栈为状态栈，另一个栈为符号栈。算法通过状态栈中栈顶的终结符号与输入符号中当前输入符号来查找ActionGoto表来进行移进和规约，进行一系列的操作。通过ActionGoto表的驱动来使字符串来进行规约到可接受状态，否则出错。

四、项目整合

工程CP：为实现项目业务逻辑类文件 工程

工程MyCompiler：为可视化界面 工程

五、流程图

构造Follow集合的流程图

语法分析流程图

六、主要函数描述

Follow函数描述

项集I的闭包函数描述

项集生成函数描述

ActionGoto表生成函数

句子识别函数

七、运行结果截图

主界面

菜单“生成”中有：词法分析、ActionGoto表、语法分析、语义分析等菜单项。

Action矩阵和Goto矩阵

说明：由于设计的时候采用键值对的方式存储，此处给出真正的表结构不是很方便。所以采用了列表的方式展示。意思是：项X经过A或者a（A为非终结符，a未终结符）结果是SX或RX或X（SX为移进X压入栈中，RX为用第X个产生式归约，X为到第X项）。

语法分析结果

对于语义分析，我们给给出的输出文本是在语义分析时候所依次使用的产生式。

八、课程设计小结

成员分工

       毛凌霄：词法分析；

       王冲：语法分析；

       周潇：语义分析；

心得体会

在不到一个星期的时间里，我们从查阅资料、互相讨论，到综合想法、征求老师意见，过得十分充实和紧张，虽然课程设计比我们想象的要困难得多，但是我们也拿出耐心和毅力，获得了最终方案。如今我明白课程设计对我来说的意义，它不仅仅是让我们把所学的理论知识与实践相结合起来，提高自己的实际动手能力和独立思考的能力，也让我学会从各方意见和想法中提取精华，这次设计中的很多地方都是源于和同学的大量讨论获得的，这种讨论对思维的激发和创新让我收获颇多。 

这次课程设计使自己学到了不少知识，也经历了不少艰辛，但收获同样巨大。通过这次课程设计我也发现了自身存在的不足之处，虽然感觉理论上已经掌握，但在运用到实践的过程中仍有意想不到的困惑，经过一番努力才得以解决。这也激发了我今后努力学习的兴趣，我想这将对我以后的学习产生积极的影响。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样，更重要的是把自己平时所学的东西应用到实际中。虽然自己对于这门课懂的并不多，很多基础的东西都还没有很好的掌握，觉得很难，也没有很有效的办法通过自身去理解，但是靠着这一个多礼拜的学习和讨论，有了很大进步。我认为这个收获应该说是相当大的。其实课程设计反映的是一个从理论到实际应用的过程，它将对我们今后的工作有着深远的影响，让我们学会主动参与学习，主动了解， 认识自己的不足，将理论活学活用才能提高自己的能力和竞争力，我会谨记这些收获，不断提高和进步！