文档介绍：学号:E10914106
专业:计算机科学与技术二班姓名：杨雨露
实验日期:2012/5/25教师签字:
成绩:
《编译原理》
课程实验报告
Word上实验四:LR分析
弓丨言 1
第一章概述 2
1设计题目及内容 2
2设计环境 2
第二章设计的基本原理 3
1 LR分析器的基本理 3
2 LR分析器工作过程算法 3
第三章程序设计 5
1总体方案设计 5
2各模块设计 5
第四章程序测试和结论以及心得 7
参考文献 7
附录程序清单 8
第一章概述
1. 1设计题目及内容
设计题目：根据LR分析表构造LR分析器内容：
已知文法G： (1)E-E+T
E—T
T—T*F
T—F
F- (E)
F-1
LR分析表:
状态
ACTION （动作）
GOTO（转换）
I
+
*
（
）
#
E
T
F
0
S5
S4
1
2
3
1
S6
Acc
2
R2
S7
R2
R2
3
R4
R4
R4
R4
4
S5
S4
8
2
3
5
R6
R6
R6
R6
6
S5
S4
9
3
7
S5
S4
10
8
S6
SU
9
R1
S7
R1
R1
10
R3
R3
R3
R3
11
R5
R5
R5
R5
注：
S j表示把下一状态j和现行输入符号a移进栈
rj表示按第j个产生式进行规约
acc表示接受
空格表示出错标志，报错
根据以上文法和LR分析表，构造LR分析器，并要求输出LR工作过程。
1. 2设计环境
硬件设备：一台PC机
软件设备：Windows 2000/XP OS , VC++6. 0
实现语言：C语言
第二章设计的基本原理
2. 1基本原理
LR方法的基本思想：
在规范规约的过程中，一方面记住已移进和规约出的整个符号串，即记住 “历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据记载的“历史”和“展望”以及“现实”的输入符号等三个方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。
LR分析器实质上是一个带先进后出存储器(栈)的确定有限状态自动机。
LR分析器的每一步工作是由栈顶状态和现行输入符号所唯一决定的。
为清晰说明LR分析器实现原理和模型：
LR分析器的核心部分是一张分析表。这张分析表包括两个部分，一是"动作(ACTION)表，另一是“状态转换”(GOTO)表。他们都是二维数组□ ACTION(s, a) 规定了当状态s面临输入符号a吋应采取什么动作。GOTO (s, X)规定了状态s
面对文法符号X (终结符或非终结符)吋下一状态是什么。显然，GOTO(s, X)定义了一个以文法符号为字母表的DFAo
每一项ACTION(s, a)所规定的动作不外是下述四种可能之一：
移进把(s, a)的下一个转态s，= G0T0(s, X)和输入符号a 推进栈，下一输入符号变成现行输入符号。
规约指用某一产生式A-B进行规约。假若B的长度为r,规约
的动作是A,去除栈顶的r个项，使状态Sm-r变成栈顶状态，然后把(Sm-r, A) 的下一状态s，= GOTO(Sm-r, A)和文法符号A推进栈。规约动作不改变现行输入符号。执行规约动作意味着B (=Xm-r+l...Xm)已呈现于栈顶而且是一个相对于A的句柄。
接受宣布分析成功，停止分析器的工作。
报错发现源程序含有错误，调用出错处理程序。
2. 2 LR分析器工作过程算法描述
一个LR分析器的工作过程可看成是栈里的状态序列，已规约串和输入串所构成的三元式的变化过程。分析开始时的初始三元式为
(sO, #, ala2 an#)
其中，sO为分析器的初态；#为句子的左括号；ala2 an为输入串；其后的
#为结束符(句子右括号)。分析过程每步的结果可表示为
(sOsl sm, #X1X2 Xm ai, ai+1 an#)
分析器的下一步动作是由栈顶状态sm和现行输入符号ai所唯一决定的。即，执行ACTION (sm, ai )所规定的动作。经执行每种可能的