LR(0)分析法的实现编译原理课程设计.doc

评语：
课程设计成绩
考 勤

软 件

报 告

答 辩

总 成 绩

教师签名：

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

LR(0)分析法的实现

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

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

目录
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．软件运行环境及限制 13
8．心得体会 14
9．参考文献 14
1．课程设计的目的
通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设计风格。同时通过某种可视化编程语言的应用，具备初步的Windows环境下的编程思想。
2．课程设计的内容及要求
1. 可以使用任何语言来完成，例如：Java、C、C++。
2. 文法采用常用的方式进行描述，例如：S→aA。
3. 以文件方式读取文法。
4. 求出项目集规范族（即所有的状态）。
5. 给出状态间的关系。
6. 给出LR(0)分析表。
7. 给定的任意符号串判定是否是文法中的句子，将分析过程用计算机打印出来。
3．实现原理
3.1 LR分析器结构
LR分析器由三个部分组成：
(1) 总控程序，也可称驱动程序。对所有的LR分析器总控程序都是相同的。
(2) 分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO） 表两个部分，它们都可用二维数组表示。
(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。

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.4 LR分析器的总控程序
总控程序的动作是根据当前栈顶状态Sm和读头下符号ai查表决定。
1、移进
把(Sm, ai)的下一状态S‘=GOTO[Sm，ai]连同读头下符号推进栈内，栈顶成(S’, ai)，而读头前进一格；
2、归约
指用产生式Aa®进行归约。若a的长度为g，则弹出栈顶g项，使栈顶状态变为Sm- g，然后将(Sm- g,A)的下一状态S’=GOTO[Sm- g,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、定义
在规范归约的句型中，不含有句柄以后任何符号的前缀称为活前缀。它有两种情况：归态活前缀和非归态活前缀。
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)产生式Ae®只有一个项目A®•。

由项目构成识别文法活前缀的NFA
1、将文法进行拓广，保证文法开始符号不出现在任何产生式右部，即增加产生式S`®S，并令S`® • S作为初态项目；
2、凡圆点在串的最右边的项目称终态项目或称归约项目，而S`® S • 称为接受项目；
3、设项目i为X ®X1…Xi-1•Xi…Xn, 项目j为X ®X1… Xi • Xi＋1 …Xn ，则从项目i画一弧线射向j，标记为Xi ， Xi是终结符则称为移进， Xi是 非终结符则称为待约；
4、若项目i为Xa®•Ab，其中A是非终结符，则从i项目画e弧射向所有A®• g的项目，ÎgV*
1)构造出的NFA是包含有e串的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) 若Aa®•Bb属于CLOSURE(I),B是非终结符，则对任何关于B的产生式Bg®，项目B®•g也属于CLOSURE(I);
c) 重复执行步骤b)直到CLOSURE(I)不再扩大为止。
3、定义状态转换函数GO
GO(I,X)定义为CLOSURE(J)，其中I,J都是项目集，X Î( VNÈ VT),J={任何形如Aa®X•b的项目| Aa®•XÎbI}。
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仍然在扩大
}
3.7.5 LR(0)分析表的构造算法
设C={I0,I1,…In},以各项目集Ik(k＝0，…,n)的k作为状态序号，并以包含S` ®•S的项目集作为初始状态，同时将G`文法的产生式进行编号。然后按下列步骤填写ACTION表和GOTO表：
1、若项目Aa®•ab属于Ik状态且GO(Ik,a)= Ij,a为终结符，则置ACTION[k,a]=Sj; 即：移进a，并转向Ij状态。
2、若项目Aa®• ÎIk,则对任何终结符a(包括语句结束符＃),置ACTION[k,a]=rj;即根据j号产生式进行归约，其中，j为产生式Aa® 的编号。
3、若项目S` ® S•属于Ik, 则置ACTION[k,＃]=accept,简记为acc;
4、若GO(Ik ，A)= Ij,A是非终结符，则置GOTO[k,A]=j;
5、分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标志”。
4．算法实现流程图

5．测试数据
[终结符]
a
b
c
d

[非终结符]
E
A
B

[开始符]
E

[产生式]
E->aA
E->bB
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

2

图一:读入文法

图二：分析文法

图三：分析句子：ad

图四：生成树
7．软件运行环境及限制
系统平台：Windows XP/2000
软件平台：VC++ 6.0
8．心得体会
归约的时候应该从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。
而在当归约到文法符号栈中只剩文法的开始符号E时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。

LR(0)分析器归约是个难点，应该认真分析文法结构。通过实验设计加深了对VC的熟练程度和对编译原理课程的理解。
总的来说，形式语言是编译原理的基础，是建立文法，分析文法的重要知识基础。

9．参考文献
《程序设计语言编译方法》（第三版） 肖军模 大连理工出版社
《编译原理教程习题解析与上机指导》 胡元义 西安电子科技大学出版社
《编译原理学习与应用指导》 张永梅 国防工业出版社
《编译原理》 李建中 机械工业出版社