编译原理课程设计报告语法分析Word下载.docx
- 文档编号:3958625
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:13
- 大小:137.31KB
编译原理课程设计报告语法分析Word下载.docx
《编译原理课程设计报告语法分析Word下载.docx》由会员分享,可在线阅读,更多相关《编译原理课程设计报告语法分析Word下载.docx(13页珍藏版)》请在冰点文库上搜索。
分析方法
语法分析器的任务主要是确定是否可以以及如何从语法的起始符号推导出输入符号串,主要可以通过两种方式完成:
自顶向下分析:
根据形式语法规则,在语法分析树的自顶向下展开中搜索输入符号串可能的最左推导。
单词按从左到右的顺序依次使用。
自底向上分析:
语法分析器从现有的输入符号串开始,尝试将其根据给定的形式语法规则进行改写,最终改写为语法的起始符号。
我采用的是自底向上的分析技术,主要使用的是SLR
(1)分析方法。
使用文法
SLR
(1)分析法的输入是拓广文法G[Z],如下所示:
Z:
:
=SS:
=i=EE:
=E+TE:
=TT:
=T*FT:
=FF:
=PP:
=(E)P:
=iP:
=n
文法存储
structRule
{
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)、若A->
ε,则将ε并入First(A)。
(2)、若A->
a,则将a并入First(A)。
(3)、若A->
B…..,则将First(B)并入First(A)。
(4)、若A->
XB…..或A->
Xa…..,且X->
ε,则类似于
(2)、(3)处理。
Follow集合生成算法
扫描所有右部包含A的产生式,
(1)、若B->
xAy,则将First(y)中的非ε终极符并入Follow(A)。
(2)、若B->
xA,或者B->
xAy且y->
ε则将Follow(B)并入Follow(A)。
(3)、若A是开始符,则将#并入Follow(A)。
计算项集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不再增大。
状态之间的转换
J为GO到的项集。
将J置空。
对I中每一个形如A->
α.Xβ的项,将A->
αX.β并入J;
调用CLOSURE(J),生成J的闭包。
根据起始符号,构造初始项集I0,
将I0并入项集规范簇C
对C中的每个项集I,若GO(I,X)非空且不在C中,那么将GO(I,X)并入C。
循环
(2)、(3)直到C不再增大。
对C中的项集IK如果满足GO(Ik,A)==Ij且A为非终极符,那么置矩阵GOTO[k][A]=j;
对IK中的每项,若A->
α.aβ且GO(Ik,a)==Ij,那么置ACTION[k][a]=j+1000,表示移进操作;
若A->
α.,那么对Follow(A)中的每个终结符a,置ACTION[k][a]=1100+j,表示规约操作’;
若拓广文法的第一项S->
E.,那么置ACTION[k][#]=1200,表示接受句子。
循环IK中的每一项;
循环C中的每一项。
句子识别
FLAG:
=TRUE;
WHILEFLAGDO
把状态栈顶元素上托出去并放在S中;
IFACTION[S][a]==SjTHEN
把符号a推入符号栈;
把状态j推入状态栈;
把下一个输入符号读进a;
}
ELSEIFACTION[S][a]==RjTHEN
从符号栈顶退出构成句柄的相应符号串;
从状态栈顶退出与句柄长度相等的若干状态;
把规则j的左部非终极符A推入符号栈;
把GOTO[top(状态栈)][A]推入状态栈;
输出规则式j;
ELSEIFACTION[S][a]=accTHEN
FLAG:
=FALSE;
ELSEERROR;
END
语法分析总控程序主要利用两个栈作为语法分析的载体,其中一个栈为状态栈,另一个栈为符号栈。
算法通过状态栈中栈顶的终结符号与输入符号中当前输入符号来查找ActionGoto表来进行移进和规约,进行一系列的操作。
通过ActionGoto表的驱动来使字符串来进行规约到可接受状态,否则出错。
四、项目整合
工程CP:
为实现项目业务逻辑类文件工程
工程MyCompiler:
为可视化界面工程
五、流程图
构造Follow集合的流程图
语法分析流程图
六、主要函数描述
Follow函数描述
变量名
说明
函数名
generateFollow()
该函数在类Experient07中实现,用来求一个文法的所有非终结符的Follow集合的
传入参数
void
由于是类内的函数,在对象构造的时候,所需参数已经通过构造函数传入,所以此函数用到的参数有,文法,终结符,非终结符
返回值
项集I的闭包函数描述
TragerAddItemSet()
该函数在类Experient14中实现,用于生成某一个项集中的一个产生式所触发的所有后继项
RuleItemRI
项中加入的规则rule
intPosition_ISList
这个项的在ISList中的位置
项集生成函数描述
GetStateTransitionDiagram()
该函数在类experient14中实现,用于生成所有的项集
返回值已经封装在类的内部,所以此处实际的返回值是ISList(项集的列表)
ActionGoto表生成函数
GetGotoActionTable()
该函数在类Experient14中实现,用来通过生成的项集来构造ActionGoto表
返回值已经封装在类的内部,所以此处实际的返回值是GotoActionTable(数据结构是hash表)
句子识别函数
AnalysisSentence()
该函数在类Experient15中实现,用来通过GotoAction表的驱动来识别句子
intStartPlace
要分析的句子在属性表的起始位置
bool
分析成功返回true否则返回false
七、运行结果截图
主界面
菜单“生成”中有:
词法分析、ActionGoto表、语法分析、语义分析等菜单项。
Action矩阵和Goto矩阵
说明:
由于设计的时候采用键值对的方式存储,此处给出真正的表结构不是很方便。
所以采用了列表的方式展示。
意思是:
项X经过A或者a(A为非终结符,a未终结符)结果是SX或RX或X(SX为移进X压入栈中,RX为用第X个产生式归约,X为到第X项)。
语法分析结果
对于语义分析,我们给给出的输出文本是在语义分析时候所依次使用的产生式。
八、课程设计小结
成员分工
毛凌霄:
词法分析;
王冲:
语法分析;
周潇:
语义分析;
心得体会
在不到一个星期的时间里,我们从查阅资料、互相讨论,到综合想法、征求老师意见,过得十分充实和紧张,虽然课程设计比我们想象的要困难得多,但是我们也拿出耐心和毅力,获得了最终方案。
如今我明白课程设计对我来说的意义,它不仅仅是让我们把所学的理论知识与实践相结合起来,提高自己的实际动手能力和独立思考的能力,也让我学会从各方意见和想法中提取精华,这次设计中的很多地方都是源于和同学的大量讨论获得的,这种讨论对思维的激发和创新让我收获颇多。
这次课程设计使自己学到了不少知识,也经历了不少艰辛,但收获同样巨大。
通过这次课程设计我也发现了自身存在的不足之处,虽然感觉理论上已经掌握,但在运用到实践的过程中仍有意想不到的困惑,经过一番努力才得以解决。
这也激发了我今后努力学习的兴趣,我想这将对我以后的学习产生积极的影响。
通过这次设计,我懂得了学习的重要性,了解到理论知识与实践相结合的重要意义,学会了坚持、耐心和努力,这将为自己今后的学习和工作做出了最好的榜样,更重要的是把自己平时所学的东西应用到实际中。
虽然自己对于这门课懂的并不多,很多基础的东西都还没有很好的掌握,觉得很难,也没有很有效的办法通过自身去理解,但是靠着这一个多礼拜的学习和讨论,有了很大进步。
我认为这个收获应该说是相当大的。
其实课程设计反映的是一个从理论到实际应用的过程,它将对我们今后的工作有着深远的影响,让我们学会主动参与学习,主动了解,
认识自己的不足,将理论活学活用才能提高自己的能力和竞争力,我会谨记这些收获,不断提高和进步!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理课程设计报告 语法分析 编译 原理 课程设计 报告