编译原理课程设计LR0分析法的实现

评语： 课程设计成绩 考 勤 软 件 报 告 答 辩 总 成 绩 教师签名：

《编译原理》课程设计报告

LR(0)分析法的实现

学院（系）： 班 级： 学生姓名： 学号 指导教师：

时间： 从2007 年12月17日 到2007年 12月29日

0

目录

1．课程设计的目的 .........................................................................2 2．课程设计的内容及要求 ..............................................................2 3．实现原理 ....................................................................................2 3.1 LR分析器结构 ...........................................................................2 3.2 LR分析法寻找可归约句柄的依据 .......................................3 3.3 LR分析器的核心 .................................................................3 3.4 LR分析器的总控程序 ..........................................................4 3.5 具体过程分析如下： ...........................................................4 3.6 LR(0)分析表构造基本思想 ...................................................4 3.7 构造LR(0)分析表的方法 .....................................................5 3.7.1生成文法G的LR(0)项目 ............................................5 3.7.2 由项目构成识别文法活前缀的DFA............................5 3.7.3将所得DFA确定化 ......................................................5 3.7.4 LR(0)项目集规范簇的自动构造 ...................................6 3.7.5 LR(0)分析表的构造算法 ..............................................7 4．算法实现流程图 .........................................................................7 5．测试数据 ....................................................................................8 6．结果输出及分析 .........................................................................9 7．软件运行环境及限制................................................................12 8．心得体会 ..................................................................................13 9．参考文献 .................................................................................. 13

1

1．课程设计的目的

通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设计风格。同时通过某种可视化编程语言的应用，具备初步的Windows环境下的编程思想。

2．课程设计的内容及要求

1. 2. 3. 4. 5. 6. 7.

可以使用任何语言来完成，例如：Java、C、C++。 文法采用常用的方式进行描述，例如：S→aA。 以文件方式读取文法。

求出项目集规范族（即所有的状态）。 给出状态间的关系。 给出LR(0)分析表。

给定的任意符号串判定是否是文法中的句子，将分析过程用计算机打印出来。

3．实现原理 3.1 LR分析器结构

LR分析器由三个部分组成：

(1) 总控程序，也可称驱动程序。对所有的LR分析器总控程序都是相同的。 (2) 分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分

析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO） 表两个部分，它们都可用二维数组表示。

(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。

2

3.2 LR分析法寻找可归约句柄的依据

1)规范归约的关键问题是找句柄。

2)问题不在于“历史”与“现实”，而是如何基于“历史”对未来“展望”，“展望”可能存在相当多的可能性。

3)一般只是使用简化了的“展望”信息，以便能构造一个可行的分析算法。

4)一个LR分析器实际上是一个带有下推栈的确定的有限状态自动机。可将一个“历史”与这个“历史”下的展望信息综合为抽象的一个状态

5)下推栈可用于存放由“历史”及相应“展望”信息形成的抽象状态。 6)下推栈内的每个状态都概括了从分析开始到归约阶段的全部“历史”和“展望”信息，因此。栈顶的状态可用于决定当前动作，即，LR分析器的每步动作可由栈顶状态和读头下符号唯一确定。

3.3 LR分析器的核心

1、核心

分析表

2、分析表构成 a)动作表(ACTION)

ACTION[S,a]表示在当前状态S下，面临读头下符号a所应采取的动作。 b)转向表(GOTO)

GOTO[S，X]：若X?VT，表示在当前状态下，读入a应转向什么状态；若X?VN，表示当前栈顶句柄归约成X后，应转向什么状态。 c)栈结构图

d)分析表格式

3

3.4 LR分析器的总控程序

总控程序的动作是根据当前栈顶状态Sm和读头下符号ai查表决定。 1、移进

把(Sm, ai)的下一状态S‘=GOTO[Sm，ai]连同读头下符号推进栈内，栈顶成(S’, ai)，而读头前进一格； 2、归约

指用产生式A??进行归约。若?的长度为?，则弹出栈顶?项，使栈顶状态变为Sm- ?，然后将(Sm- ?,A)的下一状态S’=GOTO[Sm- ?,A]连同非终结符A一起推进栈内，栈顶变为(S’,A)。读头不动，即不改变现行输入符号。 3、接受

宣布分析成功，退出总控程序。 4、报错

报告输入串含有错误，调用相应错误错误处理程序。

3.5 具体过程分析如下：

分析器的动作就是由栈顶状态和当前输入符号所决定。 LR分析器结构：

其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：

(1) 移进：action[i，a]= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。

(2) 归约：action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A->B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。

(3) 接受acc:

当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。

(4) 报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。

3.6 LR(0)分析表构造基本思想

只根据“历史”信息识别呈现于栈顶的句柄，而不考虑“展望”信息的状态。 活前缀 1、定义

4

在规范归约的句型中，不含有句柄以后任何符号的前缀称为活前缀。它有两种情况：归态活前缀和非归态活前缀。 2、归态活前缀

活前缀的尾部正好是句柄之尾，这时可以进行归约。归约之后又会成为另一句型的活前缀。 3、非归态活前缀

句柄尚未形成，需要继续移进若干符号之后才能形成句柄。

3.7 构造LR(0)分析表的方法 3.7.1生成文法G的LR(0)项目

对文法G的每个产生式右部添加一个圆点，称为G的一个LR(0)项目(简称项目)

3.7.2 由项目构成识别文法活前缀的DFA

1)对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀。

2)由于产生式右部的符号串就是句柄，若这些符号串都已进栈，则表示它已处于归态活前缀，若只有部分进栈，则表示它处于非归态活前缀。要想知道活前缀有多大部分进栈了，可以为每个产生式构造一个自动机，由它的状态来记住当前情况，这时，我们把“状态”称为“项目”。这些自动机的全体就是能识别所有活前缀的有限自动机。

3.7.3将所得DFA确定化

（1）文法G的LR(0)项目生成

在文法的每个产生式右部添加一个圆点，就成为G的一个LR(0)项目。 例如，产生式A ? XYZ对应四个项目

A??XYZ 预期要归约的句柄是XYZ，但都未进栈 A?X?YZ 预期要归约的句柄是XYZ，仅X进栈 A?XY?Z 预期要归约的句柄是XYZ，仅XY进栈 A?X YZ? 已处于归态活前缀，XYZ可进行归约，这个项目也称为归约项目。(2)产生式右部符号串的长度为n，则可以分解为n+1个项目。 (3)产生式A??只有一个项目A??。

由项目构成识别文法活前缀的NFA

1、将文法进行拓广，保证文法开始符号不出现在任何产生式右部，即增加产生式S`?S，并令S`? ? S作为初态项目；

2、凡圆点在串的最右边的项目称终态项目或称归约项目，而S`? S ? 称

5

为接受项目；

3、设项目i为X ?X1?Xi-1?Xi?Xn, 项目j为X ?X1? Xi ? Xi＋1 ?Xn ，则从项目i画一弧线射向j，标记为Xi ， Xi是终结符则称为移进， Xi是 非终结符则称为待约；

4、若项目i为X???A?，其中A是非终结符，则从i项目画?弧射向所有A?? ?的项目，??V*

1)构造出的NFA是包含有?串的NFA，可以使用子集法使之确定化，使之成为一个以项目集为状态的DFA，这个DFA就是建立LR分析算法的基础。

2)相应DFA的每个状态是一个项目集，称作LR(0)项目集，整个状态集称为LR(0)项目集规范簇。

3)在DFA的一个状态对应的项目集内，每个项目是“等价”的，即从期待归约的角度看相同。

4)有一个唯一的初态和一个唯一的接受态，但有若干个归约态，表示有若干种活前缀的识别状态。

5)状态反映了识别句柄的情况，即句柄的多大部分已进栈，即知道了历史情况。

6)手工构造文法的项目集规范

3.7.4 LR(0)项目集规范簇的自动构造

1、拓广文法

增加S` ?S 产生式，使文法的开始符号不出现在任何产生式右部，从而保证有唯一的接受项目。 2、定义和构造项目集的闭包

设I是拓广文法G`的一个项目集，如下定义和构造I的闭包CLOSURE(I)： a) I的任何项目都属于CLOSURE(I)；

b) 若A???B?属于CLOSURE(I),B是非终结符，则对任何关于B的产生式B??，项目B???也属于CLOSURE(I);

c) 重复执行步骤b)直到CLOSURE(I)不再扩大为止。 3、定义状态转换函数GO

GO(I,X)定义为CLOSURE(J)，其中I,J都是项目集，X ?( VN? VT),J={任何形如A??X??的项目| A???X??I}。 4、构造LR(0)项目集规范族的算法

PROC ITEMSETS-LR0

{ C:={CLOSURE(S` ??S)} /*初态项目集*/ DO

{ FOR (对C中每个项目集I和G`中每个文法符号X) IF (GO(I,X)非空且不属于C) {把GO(I,X)加入C中} }WHILE C仍然在扩大 }

6

3.7.5 LR(0)分析表的构造算法

设C={I0,I1,?In},以各项目集Ik(k＝0，?,n)的k作为状态序号，并以包含S` ??S的项目集作为初始状态，同时将G`文法的产生式进行编号。然后按下列步骤填写ACTION表和GOTO表：

1、若项目A???a?属于Ik状态且GO(Ik,a)= Ij,a为终结符，则置ACTION[k,a]=Sj; 即：移进a，并转向Ij状态。

2、若项目A??? ?Ik,则对任何终结符a(包括语句结束符＃),置ACTION[k,a]=rj;即根据j号产生式进行归约，其中，j为产生式A?? 的编号。

3、若项目S` ? S?属于Ik, 则置ACTION[k,＃]=accept,简记为acc; 4、若GO(Ik ，A)= Ij,A是非终结符，则置GOTO[k,A]=j;

5、分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标志”。

4．算法实现流程图

7

5．测试数据

[终结符] a b c d

[非终结符] E A B

[开始符] E

[产生式] E->aA E->bB

8

A->cA A->d B->cB B->d

6．结果输出及分析

下面是你输入的文法G：

非终结符号集合为：{ E, A, B } 终结符符号集合为：{ a, b, c, d } G[E]:

(1) E->aA (2) E->bB (3) A->cA (4) A->d (5) B->cB (6) B->d

下面是生成的拓广文法G'：

非终结符号集合为：{ $, E, A, B } 终结符符号集合为：{ a, b, c, d } G'[E]: (0) $->E (1) E->aA (2) E->bB (3) A->cA (4) A->d (5) B->cB (6) B->d

该文法的项目如下： (1) $->.E (2) $->E. (3) E->.aA (4) E->a.A (5) E->aA. (6) E->.bB (7) E->b.B (8) E->bB. (9) A->.cA (10) A->c.A

9

(11) A->cA. (12) A->.d (13) A->d. (14) B->.cB (15) B->c.B (16) B->cB. (17) B->.d (18) B->d.

LR(0)项目规范族如下： I0 = { 1, 3, 6 } I1 = { 2 }

I2 = { 4, 9, 12 } I3 = { 7, 14, 17 } I4 = { 5 }

I5 = { 10, 9, 12 } I6 = { 13 } I7 = { 8 }

I8 = { 15, 14, 17 } I9 = { 18 } I10 = { 11 } I11 = { 16 }

文法的LR(0)分析表 ACTION GOTO 状态 a b c d # E A B 0 S2 S3 1 1 acc 2 S5 S6 4 3 S8 S9 7 4 R1 R1 R1 R1 R1 5 S5 S6 10 6 R4 R4 R4 R4 R4 7 R2 R2 R2 R2 R2 8 S8 S9 11 9 R6 R6 R6 R6 R6 10 R3 R3 R3 R3 R3 11 R5 R5 R5 R5 R5

10

图一:读入文法

图二：分析文法

11

图三：分析句子：ad

图四：生成树

7．软件运行环境及限制

系统平台：Windows XP/2000 软件平台：VC++ 6.0

12

8．心得体会

归约的时候应该从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。

而在当归约到文法符号栈中只剩文法的开始符号E时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。

LR(0)分析器归约是个难点，应该认真分析文法结构。通过实验设计加深了对VC的熟练程度和对编译原理课程的理解。

总的来说，形式语言是编译原理的基础，是建立文法，分析文法的重要知识基础。

9．参考文献

《程序设计语言编译方法》（第三版） 肖军模 大连理工出版社

《编译原理教程习题解析与上机指导》 胡元义 西安电子科技大学出版社 《编译原理学习与应用指导》 张永梅 国防工业出版社 《编译原理》 李建中 机械工业出版社

13

本文来源：https://www.bwwdw.com/article/wor6.html