LR语法分析实验报告.docx

目 录

引言 1

第一章 概述 2

设计题目及内容 2

设计环境 2

第二章 设计的基本原理 3

LR分析器的基本理 3

LR分析器工作过程算法 3

第三章 程序设计 5

总体方案设计 5

各模块设计 5

第四章 程序测试和结论以及心得 7

参考文献 7

附录 程序清单 8

—概述

设计题目及内容

设计题目：根据LR分析表构造LR分析器

内容：

已知文法G：

E→E+T

E→T

T→T*F

T→F

(5)F→(E)

(6)F→I

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

S11

9

R1

S7

R1

R1

10

R3

R3

R3

R3

11

R5

R5

R5

R5

注：sj 表示把下一状态j和现行输入符号a移进栈

rj 表示按第j个产生式进行规约

acc 表示接受

空格表示 出错标志，报错

根据以上文法和LR分析表，构造LR分析器，并要求输出LR工作过程。

设计环境：

硬件设备：一台PC机

软件设备：Windows2000/XPOS，VC++6.0实现语言：C语言

二 设计的基本原理

基本原理：

LR方法的基本思想：

在规范规约的过程中，一方面记住已移进和规约出的整个符号串，即记

住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据记载的“历史”和“展望”以及“现实”的输入符号等三个方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。

LR分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。

LR分析器的每一步工作是由栈顶状态和现行输入符号所唯一决定的。

为清晰说明LR分析器实现原理和模型：

LR分析器的核心部分是一张分析表。这张分析表包括两个部分，一是“动作”（ACTION）表，另一是“状态转换”（GOTO）表。他们都是二维数组。

ACTION(s,a)规定了当状态s面临输入符号a时应采取什么动作。GOTO（s，X）规定了状态s面对文法符号X（终结符或非终结符）时下一状态是什么。显然，GOTO(s，X)定义了一个以文法符号为字母表的DFA。

每一项ACTION(s，a)所规定的动作不外是下述四种可能之一：

移进 把（s，a）的下一个转态s’=GOTO(s，X)和输入符号a推进栈，下一输入符号变成现行输入符号。

规约指用某一产生式A→β进行规约。假若β的长度为r，规约的动作是A，去除栈顶的r个项，使状态Sm-r变成栈顶状态，然后把（Sm-r，A）的下一状态s’=GOTO(Sm-r,A)和文法符号A推进栈。规约动作不改变现行输入符号。执行规约动作意味着β（=Xm-r+1…Xm）已呈现于栈顶而且是一个相对于A的句柄。

接受 宣布分析成功，停止分析器的工作。

报错 发现源程序含有错误，调用出错处理程序。

LR分析器工作过程算法描述：

一个LR分析器的工作过程可看成是栈里的状态序列，已规约串和输入串所

构成的三元式的变化过程。分析开始时的初始三元式为

(s0, #, a1a2……an#)

其中，s0为分析器的初态；＃为句子的左括号；a1a2……an为输入串；其后的

＃为结束符（句子右括号）。分析过程每步的结果可表示为

（s0s1……sm，#X1X2……Xmai,ai+1……an#）

分析器的下一步动作是由栈顶状态sm和现行输入符号ai所唯一决定的。即，执行ACTION（sm，ai）所规定的动作。经执行每种可能的动作之后，三元式的变化情形是：

若ACTION（sm，ai）为移进，且s=GOTO（sm，ai），则三元式变成：

（s0s1……sms，#X1X2……Xmai,ai+1……an#）

若ACTION（sm，ai）= {A→β},则按照产生式A→β进行规约。此时三元式变为

（s0s1……sms，#X1X2……XmA,aiai+1……an#）此处s=GOTO（Sm-r，A），r为β的长度，β=Xm-r+1……Xm。

若ACTION（sm，ai）为“接受”，则三元式不再变化，变化过程终止，宣布分析成功。

若ACTION（sm，ai）为“报错”，则三元式的变化过程终止，报告错误。

一个LR分析器的工作过程就是一步一步的