LR分析法

本章介绍上下文无关文法的LR分析方法及分析程序的自动构造。

LR:自左至右扫描，最右推导的逆过程。

基本思想

在规范归约过程中，一方面记住已移进和归约出的整个符号串，另一方面根据所用的产生式推测未来可能碰到的输入符号。

优缺点

优点:与其他技术相比，适应文法范围更广，能力更强，识别效率相当，尤其在自左向右扫描输入串时就能发现其中错误，并能准确指出出错位置。

缺点:

若用手工构造分析程序，工作量太大，且容易出错，所以必须使用自动产生这种分析程序的产生器。

LR分析器

实际上是个有下推栈的确定的有限状态自动机

从逻辑上说，LR分析器包括两部分:

总控程序，或称为语法分析程序
分析表;

注

后面要学习的四种LR分析器的总控程序都相同，仅仅是它们的分析表不同

总控程序

查分析表，根据分析表的内容做若干简单动，如：读头后移，入栈，出栈等。

分析表

四种分析表范围

一个文法的LR分析器常常对应着若干不同分析表所有分析表都恰好识别文法所产生的所有语句。
一共有下列四种分析表

1、LR(0)分析表:

分析能力有限，但这是建立其他LR分析法的基础。

2、SLR分析表:

LR(0)的改进
简单LR分析表构造法，是一种容易实现又有实用价值的方法，但存在一些文法构造不出SLR分析表。

3、规范LR分析表—LR(1)分析表

它能力最强，但实现代价过高，分析表尺寸太大。

4、LALR分析表

LR(1)的改进
向前看LR分析表构造法，也是一种常用方法。

LR分析法找句柄的依据

历史:记录在栈内的符号串移进、归约的历史情况
现实:读头下的符号。
展望:预测句柄之后可能出现的信息;

下推栈

上面提到过LR分析实际是个有下推栈的DFA

下推栈用于存放分析输入串过程中的所有由“历史”及相应“展望”信息形成的抽象状态。
为了便于了解栈顶状态对正规分析过程的作用，我们把栈分为两栏:状态栏和符号栏。
符号栈仅用于记录迄今移进一归约所得到的文法符号，由于它们已经被概括在“状态”里了，所以对语法分析不起作用。
由于每个状态都概括了从分析开始到归约阶段的全部“历史和"展望”信息，所以LR分析器的每步动作可由栈顶状态和读头下符号唯一确定。

下推栈的初始状态

初始时，状态栈放S~0~(初态，符号栈放“#”(栈底符);栈顶S~m~代表符号栈内的符号串X~m~X~m-1~…X~1~及其展望信息。

分析表

分析表-行标是状态-列标是入栈符号

行标是状态-列标是入栈符号
分析表是LR分析器的核心
由动作表和转换表构成

动作表

1)ACTION[S,a]表示:在当前状态S下，面临读头符号a所应采取的动作，该动作有四种可能:移进、归约、出错、接受。

移进

栈顶不形成句柄，把读头符号入栈

归约

栈顶形成句柄，先将栈顶归约

接受

当读头遇到“#”，完成归约

出错

转换表

GOTO[S,X]表示:若X是终结符，表示在当前状态下，读入X应转向什么状态;若X是非终结符，表示当前栈顶句柄归约成X后，应转向什么状态。
对终结符的移进动作和转向动作可以合并在一起填在动作表中，这样，转向表可以压缩，GOTO表只保留非终结符转向部分。

总控程序

根据当前栈顶状态和读头下符号查表决定

移进

归约

像compiler-6里面的一个例子，如果栈内是#if N then N else N ，飘红的部分要归约成N，如果使用总控程序，就可以根据N-> β进行归约，从栈顶弹出了6个元素，并让栈顶状态变成S~m-y~ 再求出下一个状态S’=GOTO(S~m-y~,N)，把N入栈，栈顶变成(S’,N)

接受

接受分析成功，退出总控程序。

出错

报错输入串出错，调用相应出错程序。

分析表含义

0号状态下，读头是i时，动作为：将读头i入栈，并转到5号状态。栈顶变成(5,i)
2号状态下，读头是+时，动作为：按第2号产生式进行归约
4号状态下，遇到非终结符E，将8号状态入栈
1号状态下，遇到#，则分析成功
如果查到空，则表示出错

举例

过程解读

状态栈	符号栈	读头	操作
`0`	#	`i`*i+i#	0号和i=s5，`5入状态栈，i入符号栈`
0 `5`	i	`*`i+i#	5号和=r6，按`6号文法(F->i)`进行归约，产生F*，弹出`1项`
0	#	*i+i#	0号和F=3，`3入状态栈，F入符号栈`
0 `3`	# F	`*`i+i#	3号和=r4，按`4号文法(T->F)`进行归约，产生T*，弹出`1项`
0	#	*i+i#	0号和T=2，`2入状态栈，T入符号栈`
0 `2`	# T	`*`i+i#	2号和=s7，`7号入状态栈，入符号栈`
0 2 `7`	# T *	`i`+i#	7号和i=s5，`5号入状态栈，i入符号栈`
0 2 7 `5`	# T * i	`+`i#	5号和+=r6，按`6号文法(F->i)`进行归约，产生F，弹出`1项`
0 2 7	# T *	+i#	7号和F=10，`10号入状态栈，F入符号栈`
0 2 7 `10`	# T * F	`+`i#	10号和+=r3，按`3号文法(T->TF)`进行归约，产生T*，弹出`3项`
0	#	+i#	0号和T=2，`2号入状态栈，T入符号栈`
0 2	# T	+i#

剩下的

最后，1号和#=acc，识别成功

LR(0)分析表

定义:如果某一文法能够构造一张分析表，使得表中每一元素至多只有一种明确动作，则该文法称为LR文法。

由上面知道，分析表一共有四种，其中最简单的是LR(0)分析表

LR(0)分析表构造

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

只根据历史信息识别呈现于栈顶的句柄。

注:

LR(0)分析表构造的思想和方法是构造其它LR分析表的基础。

构造LR(0)分析表的基本策略:

构造文法G的一个有限自动机，它能识别文法中的所有活前缀。

活前缀

活前缀的概念:

指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。

在普通的产生式后面添加序号，并按最右推导，形成对应式子，再按最左归约进行识别

最左归约时，只要看到一个序号，说明前面的几个符号会形成一个句柄
如ab[2]形成了2号产生式的句柄，根据2号产生式，把b归约成A
aAb[3]形成3号产生式句柄，再根据3号产生式，把Ab归约成A
aAcd[4]形成4号产生式句柄，把d归约成B
aAcBe[1]形成1号产生式句柄，aAcBe归约成S

最左归约

构造活前缀项目

在文法的每个产生式右部添加一个圆点，就成为G的一个LR(0)项目（简称项目）。
注:圆点在产生式中的位置不同则是不同项目。

圆点前面的字符都已经入栈，圆点是栈内栈外的分界线

LR(0)构造方法

首先要拓广文法，即如果文法开头不是一个非终结符到另一个非终结符的产生式则需要加入，如加入 S’->S .

(1)将文法进行拓广，保证文法开始符号不出现在任何产生式右部，即增加产生式S’->S，并令S’→●S作为初态项目;

(2)凡圆点在串的最右边的项目称终态项目或称归约项目，而S→●S称为接受项目;说明所有字符都在栈中

1)构造出的NFA是包含有空串的NFA，可以使用子集法使之确定化，使之成为一个以项目集为状态的DFA,这个DFA就是建立LR分析算法的基础。
2)相应DFA的每个状态是一个项目集，称作LR(O)项目集，整个状态集称为LR(O)项目集规范簇。
3)在DFA的一个状态对应的项目集内，每个项目是“等价”的，即从期待归约的角度看相同。
4)有唯一的初态和唯一的接受态，但有若干个归约态，表示有若干种活前缀的识别状态。
5)状态反映了识别句柄的情况，即句柄的多大部分已进栈，即知道了历史情况。
6)手工构造文法的项目集规范簇很困难。

手写结果

机器构造方法

状态转换函数

LR(0)项目集族图

如果遇到S’-> α●E，则 E->●aA和E->●bB也属于closure(1)
再按closure(1)出现的E,a,b，依次将●后移一位

LR(0)的文法范围小

SLR分析表

消除冲突

以根据读头下符号的不同

1、一个有冲突的项目集，可以根据读头下一个符号的不同来消除冲突。

如果Follow(A)与Follow(B)不相交，则可以根据Follow集来判断

构造SLR分析表算法

注:

1)若文法G按上面算法构造出来的分析表不包含多重定义项，则该文法G是SLR文法。

2)二义文法决不是LR文法。

3)SLR分析法包含的展望信息是体现在利用了Follow(A)信息，可以解决“归约-归约冲突

4)SLR分析法没有包含足够的展望信息，不能完全解决“移进-归约”"冲突，需要改进。

举例

项目簇中

关注其中I1,I2,I9会产生归约-移进冲突

发生冲突原因

I1：S’->E Follow(S)={#}，所以只有遇到#做归约，E->E●+T，遇到+进行移进；有归约-移进冲突
I2：Follow(E)={#,+,)}，遇到#,+,)做归约。因为T->T●*F，遇到*进行移进；有归约-移进冲突
I9：Follow(E)={#,+,)}，遇到#,+,)做归约。因为T->T●*F，遇到*进行移进；有归约-移进冲突

最终可以得到SLR分析表

举例2

下面的文法，无法使用SLR分析

对应项目簇

I2中，因为Follow®={=}，理论上遇到=做归约，但S->L●=R，遇到=移进
这种冲突无法解决
如下图，出现了冲突。需要用规范LR分析表

规范LR(1)分析表

对上面的SLR出现的“移进”-“归约”问题，规范LR可以进行解决

结论

由此看出，并非随符都出现在规范句型中。

对策

给每个LR(0)项目添加展望信息，即:添加句柄之后可能跟的终结符，因为这些终结符确实是规范句型中跟在句柄之后的。这就是LR(1)的方法。

可能引起的问题

故，LR(1)项目是对LR(O)项目的分裂，若文法中终结符的数目为n，则每个LR(O)项目都可以分裂成n个LR(1)项目。这可能会引起分析表的膨胀。

LR(1)项目:形如(A→α●β,a）的二元式称为LR(1)项目。其中， A→α●β是文法的一个产生式，a是终结符，称为搜索符。
(A→α●β)的含义:预期当栈顶句柄αβ形成后，在读头到a。此时，α在栈内，β还未入栈，即它展望了句柄后的一个符号。

有效项目

举例

构造规范LR分析表

举例

可见：当前非终结符的展望符号就是当前非终结符的LastVt
后面的操作就是扩展并求闭包

最终得到规范LR分析表

和上面的SLR分析表对比，可见，2号状态下的冲突解决了

几种LR文法的关系

如果给个文法，来判断是哪个LR文法

方法：

先构造LR(1)文法，至少确定是否为LR文法。
再根据LR(1)文法表，再将每行都按归约填写，如下图
- 2号状态出现了冲突，说明不是LR(0)文法，如果可以用SLR来解决这个冲突，说明是SLR文法
- 如果未发现冲突，说明是LR(0)文法
这种文法好处是，只用构造一张表