编译原理课程设计--LR(1)分析和语义分析.doc
《编译原理课程设计--LR(1)分析和语义分析.doc》由会员分享，可在线阅读，更多相关《编译原理课程设计--LR(1)分析和语义分析.doc（25页珍藏版）》请在冰点文库上搜索。
22
编译原理课程设计
课程设计说明书
课程名称:
＿编译原理课程设计＿＿＿
题目:
＿LR
（1）分析和语义分析＿＿＿
院系：
理学院
专业班级：
信息与计算科学11-2班
学号：
2011304985
2014年6月26日
编译原理课程设计
课程设计（论文）任务书
学号
2011304985
学生姓名
高健
专业（班级）
信计11-2
设计题目
LR
（1）分析和语义分析
设
计
技
术
参
数
·jdk1.6
·开发工具：
Myeclipse10.0
设
计
要
求
对某一文法进行LR
（1）分析和语义分析
工
作
量
文档不少于12页，参考文献不少于10个
工
作
计
划
6月16-17日了解LR分析的原理和过程，选定一个要分析的文法
6月18-19日构造项目集规范族利用项目集规范族和转移函数构造LR
（1）分析表
6月20-21日学习语义分析，并对选定文法赋予语义规则
6月22-23日编写JAVA代码实现对文法的LR
（1）分析和语义分析
6月24-25日完成文档写作包括实现原理，程序流程图和类的说明
6月26日提交课程设计
参
考
资
料
[1]DavidA.Watt.ProgrammingLanguageSyntaxandSemanties[M].prenticeHall,1911.
[2]赵克佳，杨灿群，罗红兵.多语种多平台编译系统剖析[M].工业出版社1997.
[3]陈火旺，钱家骅，孙永强，程序设计语言编译原理[M]，国学工业出版社
[4]李赣生，王华民.编译程序原理和技术[M].清华大学出版社，1997.
[5]金成植，编译程序构造原理和实现技术[M].高等教育出版社，2000.
[6]杜淑敏，王永宁.编译程序设计原理[M].北京大学出版社，1986.
[7]JimHolmes.CompilerConstruction[M].PrenticeHall,1995.
[8]BertrandMeyer.ReusableSoftware[M].PrenticeHall,1994.
[9]AndrewW.Appel.ModernCompilerDesign[M].CambridgeUniversityPress,1998.
[10]陈意云.编译原理和技术[M].中国科学技术大学出版社,1997.
指导教师签字
教研室主任签字
年月日
3
编译原理课程设计
目录
1绪论 1
2概述 1
2.1设计背景 1
2.2设计目的 1
2.3软件定义 2
2.4开发环境 2
3项目设计报告 3
3.1程序流图 3
3.2实现原理 4
3.2.1LR分析概述 4
3.2.2LR
（1）项目集规范族的构造 5
3.2.3LR
（1）分析表的构造 6
3.3类的说明 6
4项目测试报告 6
4.1测试的目的 6
4.2项目集规范族和LR
（1）分析表 7
4.3语义规则 8
4.4运行界面 8
4.5相关代码 10
5心得体会 21
参考文献 22
22
编译原理课程设计
1绪论
《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计思想。
大家通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。
2概述
2.1设计背景
随着科学技术的不断提高，计算机科学日渐成熟，其强大的功能已为人们熟知，它已进入人类社会的各个领域并发挥着越来越重要的作用。
作为计算机应用的一部分，使用计算机对LR
（1）文法判断与预测分析器的构造系统，具有比手工运算、构造所无法比拟的优点。
例如：
查找迅速、查找方便、准确性高等。
这些优点能够极大地提高判定LR
（1）文法的效率，也是我们此次课程设计的目的。
因此，开发这样的一套LR
（1）文法判定与预测分析器的构造软件是很有必要的。
编译原理是大学计算机专业的必修课程，而词法分析作为其中的一部分占据着比较重要的地位。
词法分析是编译原理的第一阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。
通关本次课程设计，我们对编译原理的理解就不止停留在课本上，而是知道怎样把编译原理应用到实际的编译程序设计的实践中。
对我们今后的学习和工作都是至关重要的。
2.2设计目的
因为LR（0）分析过程中不需要向右查看输入符号，因而它可以对文法的限制较大，对绝大多数的高级语言的语法分析器是不能适用的，所以，要分析绝大多数的高级语言编译程序的需要，采用向后查看一个输入符号的方法，即LR
（1）的方法。
2.3软件定义
（1）对任意给定的上下文无关文法Ｇ，构造其LR
（1）项目集规范族，并且在此基础上再利用转移函数进一步构造其LR
（1）分析表。
（2）给定任意字符串判定是否是该文法的句子，并实现语义分析。
2.4开发环境
硬件：
一台IntelPentium4以上的计算机
软件：
Windows操作系统，Myeclipse10.0
编程语言：
Java
3项目设计报告
3.1程序流图
否
否
是
否
是
是
0，#分别入状态栈和符号栈
置ip指向w#的第一个符号
令s是状态栈栈顶，
a是ip所指向的符号
action[s，a]=S’
action[s,a]=reduceA->s
把a和s’分别推入符号栈和状态栈；使ip前进到下一个字符
分别从栈顶弹出|β|个符号，令s’是当前栈顶状态，把a和goto[s’,A]先后推入栈中，输出产生式A->β
Action[A,a]=accept
结束
出错处理
图3-1LR
（1）驱动程序流程图
否
非空受
S’中每个项目I和文法符号X
goto[I,X]
在C中
goto[I,X]加入到项目集
是否还有项目
是
图3-2LR
（1）项目集构造
3.2实现原理
3.2.1LR分析概述
一个LR分析器由3部分组成：
⑴总控程序也称为驱动程序。
对所有的LR分析器总控程序相同。
⑵分析表或分析函数。
它包括“动作”和“状态转换”两部分，都是用二维数组来表示。
ACTION[s，a]规定了当前状态s面临输入a应该采取的动作，GOTO[s，X]规定了状态s面对文法符号X（终结符或非终结符）时下一状态是什么。
GOTO[s，X]定义了一个以文法符号为字母表的DFA。
⑶分析栈。
包括文法符号栈和相应的状态栈，它们均是先进后出栈。
a1a2…………..ai……………an#
LR分析程序
输出
smXm
s1X0
s0#
actiongotogoto
分析表
栈
输入串
图3-3LR分析器工作过程示意图
3.2.2LR
（1）项目集规范族的构造
当LR（0）项目中存在移近-归约冲突和归约-归约冲突时，可用SLR
（1）方法解决动作冲突，但仍然存在多余归约，LR
（1）恰好是解决SLR
（1）方法在某些情况下存在的无效归约问题。
LR
（1）项目形式：
[A→α·β，a1a2…ak]
移进或待归约项目（β≠ε），a1a2…ak不起作用。
归约项目[A→α·，a1a2…ak]，仅当前输入符号串开始的前k个符号是a1a2…ak时，才能用A→α进行归约。
a1a2…ak称向前搜索符号串。
以S′→·S,#属于初始项目集中，把“#”作为向前搜索符，表示活前缀是γ（若γ是有关S产生式的某一右部）要归约为S时必须面临“#”才行。
对初始项目S′→·S,#求闭包后再用转换函数逐步求精求出整个文法的LR
（1）项目集族。
具体构造步骤如下：
⑴LR
（1）项目集的闭包：
设I是G的一个LR
（1）项目集，closure（I）是从I出发用下面三个规则构造的项目集：
①每一个I中的项目都属于closure（I）
②若项目［A→α·Bβ，a]属于closure（I）且B→η∈P，则对任何b∈FIRST（βa），把原来不属于closure（I）中的项目[B→·η，b]加进closure（I）中
③重复执行
（2）直到closure（I）不再增大为止
⑵转移函数GO（I，X）
令I是一个项目集，X是一个文法符号，函数GO（I，X）定义为：
GO（I，X）=CLOSURE（J）
其中：
J={任何形如［A→αX·β，a]的项目|［A→α·Xβ，a]∈I}
S’的LR
（1）项目集族C的构造算法
BEGIN
I0：
C={closure（[S′→·S，#]）}
FORC中的每个项目集I和G´的每个符号XDO
IFGO（I，X）非空且不属于C，THEN把GO（I，X）加入C中
UNTILC不再增大
END
3.2.3LR
（1）分析表的构造
⑴若项目[A→α·aβ，b]属于Ik且GO（Ik，a）=Ij，a为终结符，则置ACTION[k，a]为“把（j，a）移进栈”，记为“sj”
⑵若项目[A→α·，a]属于Ik，置ACTION[k，a]为“用产生式A→α进行归约”，记为“rj”
⑶若项目[S′→S·，#]属于Ik，则置ACTION[k，#]为“接受”，记为“acc”
⑷若GO（Ik，A）＝Ij，则置GOTO[k，A]=j
⑸将空白格均置为“报错标志”
3.3类的说明
本程序共有五个类：
Main.java是主类，只包含主界面的标题栏。
MainView显示主界面内容，提示输入字符串并进行LR
（1）分析，如果输入格式不符合会提示相应信息。
OperateData.java是操作类，对输入的字符串进行LR
（1），提示分析成功或失败信息。
Tools.java是对栈进行处理的类。
AnalyseResult.java是分析字符串显示分析结果的类，对界面进行了布局。
4项目测试报告
4.1测试的目的
在完成了程序的编写工作后，接下来将进行数据测试，这里说的软件，并不单单是指程序本身,还包括其他方面。
测试和开发一样，也是一项技术性很强的工作，有着很多的技巧。
软件测试是软件质量保证的主要活动之一，因此，测试的质量直接影响软件的质量。
依据前面所说的测试对象，我们把测试划分为几个方面来进行测试。
测试目的：
输入字符串进行LR
（1）分析，判断是否为该文法的句子并进行语义分析。
4.2项目集规范族和LR
（1）分析表
扩展文法（0）E’→E
（1）E→E-T
（2）E→T
（3）T→T+F
（4）T→F
（5）F→i
I0:
E→·E,#
E→·E-T,#/-
E→·T,#/-
T→·T+F,#/-/+
T→·F,#/-/+
T→·i,#/-/+
I1:
E’→E·,#
E→E·-T,#/-
I2:
E→T·,#/-
T→T·+F,#/-/+
I3:
T→F·,#/-/+
I4:
F→i·,/-/+
I5:
E→E-·T,#/-
T→·T+F,#/+/-
T→·F,#/+-
F→·i,#/+/-
I7:
E→E-T·,#/-
T→T·+F,#/+/-
I6:
T→T+·F,#/-/+
F→·i,#/-/+
I8:
F→T+F·,#/-/+
－
E
T
+
F
+
i
T
F
i
i
F
图4-1LR
（1）项目集和转换函数
表4-1LR
（1）分析表
状态
ACTION
GOTO
－
+
i
#
E
T
F
0
S4
1
2
3
1
S5
acc
2
r2
S6
r2
3
r4
r4
r4
4
r5
r5
r5
5
S4
7
3
6
S4
8
7
r1
S6
r1
8
r3
r3
r3
4.3语义规则
产生式语义规则
（0）E’→E{printE.VAL}
（1）E→E-T{E.VAL:
=E.VAL-T.VAL}
（2）E→T{E.VAL:
=T.VAL}
（3）T→T+F{T.VAL:
=T.VAL+F.VAL}
（4）T→F{T.VAL:
=F.VAL}
（5）F→i{F.VAL:
=i.LEXVAL}
4.4运行界面
图4-2输入字符串
图4-3分析结果
图4-4输入错误字符串
图4-5显示错误信息
4.5相关代码
（1）OperateData.java
packagelr1.operate;
importjava.util.HashMap;
importjava.util.Map;
importjava.util.Stack;
importjava.util.Vector;
importlr1.tool.TOOL;
publicclassOperateData{
privateMap>wenfa;
privateStringtext;
privateStackstateStack;//状态栈
privateStackyuyiStack;//语义值栈
privateStacksignStack;//符号栈
privateStackinputStack;//输入字符栈
privateStringstate;
privateStringyuyi;
privateStringsign;
privateStringinput;
privateMapwenfaMap;
privateMapamap;
privateMap>analyTable;
privateStringmessage;
publicStringgetMessage（）{
returnmessage;
}
privatevoidsetMessage（Stringstr）{
StringBufferbuffer=newStringBuffer（）;
buffer.append（"结果:
\n"）;
buffer.append（str）;
message=buffer.toString（）;
}
publicOperateData（Stringtext）{//空的构造方法
this.text=text;
stateStack=newStack（）;
stateStack.push（"0"）;
yuyiStack=newStack（）;
yuyiStack.push（""）;
signStack=newStack（）;
signStack.push（"#"）;
inputStack=newStack（）;
text=text.trim（）;
inputStack.push（"#"）;
inputStack.push（text.substring（text.length（）-1））;
for（inti=text.length（）-1;i>=1;i--）{
inputStack.push（text.substring（i-1,i））;
}
wenfa=newHashMap>（）;
analyTable=newHashMap>（）;
MapwMap0=newHashMap（）;
wMap0.put（"0","E'"）;
wMap0.put（"S'","E"）;
MapwMap1=newHashMap（）;
wMap1.put（"1","E"）;
wMap1.put（"E","E+T"）;
MapwMap2=newHashMap（）;
wMap2.put（"2","E"）;
wMap2.put（"E","T"）;
MapwMap3=newHashMap（）;
wMap3.put（"3","T"）;
wMap3.put（"T","T*F"）;
MapwMap4=newHashMap（）;
wMap4.put（"4","T"）;
wMap4.put（"T","F"）;
MapwMap5=newHashMap（）;
wMap5.put（"5","F"）;
wMap5.put（"F","i"）;
wenfa.put（"0",wMap0）;
wenfa.put（"1",wMap1）;
wenfa.put（"2",wMap2）;
wenfa.put（"3",wMap3）;
wenfa.put（"4",wMap4）;
wenfa.put（"5",wMap5）;
Mapamap0=newHashMap（）;
amap0.put（"+",null）;
amap0.put（"*",null）;
amap0.put（"i","S4"）;
amap0.put（"#",null）;
amap0.put（"E","1"）;
amap0.put（"T","2"）;
amap0.put（"F","3"）;
Mapamap1=newHashMap（）;
amap1.put（"+","S5"）;
amap1.put（"*",null）;
amap1.put（"i",null）;
amap1.put（"#","acc"）;
amap1.put（"E",null）;
amap1.put（"T",null）;
amap1.put（"F",null）;
Mapamap2=newHashMap（）;
amap2.put（"+","r2"）;
amap2.put（"*","S6"）;
amap2.put（"i",null）;
amap2.put（"#","r2"）;
amap2.put（"E",null）;
amap2.put（"T",null）;
amap2.put（"F",null）;
Mapamap3=newHashMap（）;
amap3.put（"+","r4"）;
amap3.put（"*","r4"）;
amap3.put（"i",null）;
amap3.put（"#","r4"）;
amap3.put（"E",null）;
amap3.put（"T",null）;
amap3.put（"F",null）;
Mapamap4=newHashMap（）;
amap4.put（"+","r5"）;
amap4.put（"*","r5"）;
amap4.put（"i",null）;
amap4.put（"#","r5"）;
amap4.put（"E",null）;
amap4.put（"T",null）;
amap4.put（"F",null）;
Mapamap5=newHashMap<
升级会员 