3.3 LR分析

LL(k)预测法的弱点是它必须预测下一个将被使用的产生式，并且需要向前查看一个字符、LR(k)是一个更有效的分析法，它可以在看见与整个产生式相关的所有输人记号以后再做出决定(多于k个记号)。

LR(k)分别代表由左自右的分析、最右推导、向前查看k个记号。最右推导的使用看起来有些奇怪，怎样用最右推导进行由左向右的分析呢?

图3.18说明了在文法3.1程序中的LR分析过程，用一个新的产生式 S’→S$ 进行扩充。

a := 7
b := C + (d := 5+6, d)

分析器有一个栈和一个输人，最先输人的个记号为向前查看的记号。根据栈和向前查看的记号，分析器进行如下两项操作：

移进：压人新输人的记号为栈顶状态。

归约：选择文法规则X→ABC；从栈顶弹出C、B、A，将X压入栈。

初始状态时栈为空，分析器指向第一个输入字符。文件终结符号$的移进叫做接收，与此同时分析过程成功结束：

图 3.18 中，栈和输人的操作都表示了出来，同时后面跟有操作的说明。将栈和输人结合起来看，就是一个最右推导。

实际上图 3.18 的演示过程，为输入字符串最右推导的逆过程。

栈中的下标代表 DFA 的状态号，见下图：

3.3.1 LR分析器

LR分析器是怎样知道何时移入、何时归约的呢?

答案在于：LR 分析器使用了确定有限自动机DFA没有用于输人(因为有限自动机不适用于上下文无关文法) 而是用于堆栈。

标有符号(终结符和非终结符) 的DFA箭头可以压人栈：表3.19是文法3.1的转换表。

转换表中的元素有4种类型的动作：

sn 移进状态n

gn 转换到状态n

rn 用规则k归约

a 接收；出错(表中出现空人口)

使用该表进行分析时，可以将移进和转换看做是DFA的箭头并扫描堆栈。

例如，若堆栈为 id:=E，然后DFA分别从状态1转为4， 6， 11。若下一个输人记号是一个分号，状态11的 “;” 列依据规则2进行归约。因为文法的第二个规则是S→id:=E，于是栈顶的3个记号被弹出，同时S人栈.

分析器可以记住到达每个栈时的状态，而不用反复扫描栈中的每个记号。此时，分析算法如下所示：

移进(n)先输人一个记号，将n压人栈。
归约(k)将规则k右侧的符号全部弹出栈；设规则k左边的符号为X；当前处于栈顶状态，查看X得到“转换到n”；将n压人栈。
接收 终止分析， 返回success。
出错 终止分析， 返回failure。

3.3.2 LR(0)分析器生成器

LR(k)分析器通过栈的内容和向前查看k个输人记号来决定选择哪个动作。

表3.19显示了只有一个向前查看符号的情况。k=2时，表的列项应变为两个记号的组合，依次类推。

实际上，k>l时就不适合编译了。虽然部分原因在于担心表过于庞大，但更多的原因是因为大多数编程语言都可以使用LR(I)文法加以描述。

LR(0)文法是一种只需要堆栈就可以进行分析的文法，同时无需向前查看即可决定移进或归约。虽然这类文法应用并不广泛，但它构造LR(0)分析表的算法对于构造LR(1)分析器算法来说是个很好的参照、

下面将通过文法3.20来说明LR(0)分析器生成器。

首先，它将建立一个空栈，输人符是一个以$结尾的、完整的S-句子，因为S’规则也包含在输入中。记为S’→.S$，S前的点号说明了分析器当前所在的位置

文法 3.20

S'→S$
        L→S
S→(L)   L→L，S
S→x

在这种情况下，S为开始符号，这意味着可能从任一个S产生式的右侧开始。

可以用下列符号说明并得到状态1：

状态 1

S'→.S$
S->.x
S->(.L)

一个右部某位置上标有圆点的文法规则称为一个项目(或一个LR(0)项目)。一个状态就是一个项目集。

移进动作

状态1中，考虑移进x后所产生的结果。此时栈顶会变为x，同时在S→x产生式中，将点号移到x后。

规则S→.SS和S→.(L)与该动作无关，这里可以忽略它们。

状态 2

此时得到状态2：

S=>x.

考虑在状态1时移进一个左括号。那么应该将点号移到左括号的右边，第3个产生式变为S’→(.L)。

此时栈顶应为左括号，下一个输人字符应为由L导出的字符串，最后是一个右括号。那么，下–个记号到底应该是什么呢?应该在项目集中的L产生式中查找。在L项目中，存在一个S前有点号的产生式，那么所有S产生式也应包括在内：

状态 3

S→(.L)
L→·.L.S
L→.S
S→.(L)
S→.x

转换动作

在状态1中，考虑移人多个由非终结符S导出的字符。它可能发生在x或左括号移人之后并最终将归约成一个S产生式。

之后所有产生的右侧符号都会弹出，分析器将对状态1中的S执行转换动作。

这一过程可以表示为：将状态1第一项中的点移到S之后，得到状态4：

状态 4

S'→S.$

归约动作在状态2中，点号位于项目的最后。

这说明，此时栈顶部分一定对应于一个完整的产生式(S->x)并准备进行归约。在这种情况下，分析器将进行归约。

对状态所执行的最基本操作包括 closure() 和 goto(I, x)，这里I是一个项目集， x是一个文法符号(非终结符或终结符) 。当有点号在非终结符的左侧时， closure可能为一个项目集添加多个项目，goto 将所有项目中的点号移到符号 x 的后面：

下面是一个构造 LR(0) 分析器的算法，首先用一个附加开始产生式 S’->S$ 对文法加以扩充。设置 T 为状态集，E 为（移进或者转移）箭头的集合。

然后对于符号 $，不计算 goto(I, $) 的值，而是采用 accpet 动作。

对于文法 3.20，如下的图 3.21 已经说明了这一点。

图 3.21

现在可以计算 LR(0) 的规约动作集合 R:

现在可以为该文法(参见表3.22)建一个分析表。对每个箭弧斗 I--x-->J (X为终结符)，在表中(I， X) 的位置记录动作shift J；若X为非终结符，则在表中(I， X) 的位置记录goto I。

对于每个包含项目S’-S.$的状态I，在(I， $) 的位置纪录accept。

最后，对于包含项目A→y.的状态(在尾部有点号的产生式n) ，对于所有记号Y，都在(I， Y) 处纪录 reduce n。

原则上，因为LR(0)不需要向前查看字符，每个状态仅需一个动作：一个状态要么移进，要么归约，不会两者兼有。

实际上，由于还需要知道要移进何种状态，所以还需要以状态号作为行，以文法符号作为列。

表3.22文法3.20的LR(0)分析表

3.3.3 SLR 分析器生成器

下面尝试为文法 3.23 建立一个 LR(0) 的分析表，LR(0) 的状态和分析表如下图 3.24

文法 3.23

在状态3中，对应符号+有一个多重定义人口。分析器必须移进至状态4，同时对产生式2进行归约。这将会产生冲突，说明该文法不是LR(0)——它不能被LR(0)分析器分析、所以还需要一种更为强大的分析算法。

SLR的构造方式要比LR(0) 分析器更好， SLR基于简单的LR。构造SLR分析器与构造LR(0)分析器类似，但只需要依据FOLLOW集来决定表中的归约动作。

下面是确定SLR表中归约动作的算法：

动作(I、X，A→α)表示在状态 I 向前查看符号X时，分析器将通过规则A叫进行、因此，对于文法3.23，虽然使用了与LR(0)相同的状态表(参见图3.24)，但在表中使用了更少的归约动作，参见图3.25.

SLR文法是一种无冲突(多重定义人口) SLR分析表的文法。文法3.23就是这种类型，很多编程语言文法也采用了这种类型。

3.3.4 LR(1) 项目和 LR(1) 分析表

比SLR更加强大的是LR(1) 分析算法。

大多数使用上下文无关文法描述语义的编程语言都有一个LR(1)文法。

构造LR(1)分析表的算法与构造LR(0)分析表相似，但是其项目的概念较LR(0)更完善。一个LR(1)项月由一个文法产生式、一个右侧位置(用点点号表示)和一个向前查看的符号组成、一个项目(A→x.β，x)表示α已位于栈顶，待输人的首部是可以由βx导出的字符串。

LR(1)状态是一个LR(1)项目集，包含与向前查看符号相结合的、LR(1) 的Closure和Goto动作：

开始状态是项目(S’->.S$，?)的闭包，其中向前查看符号 “?” 没有什么意义，因为文件结束符永远不会被移进。

归约动作将通过该算法加以选择：

动作(I，Z，A→a)表示在状态 I、向前查看字符Z时，分析器将通过规则A→α进行归约。

文法3.26不是SLR(参见习题3.9) ，但它属于LR(1) 文法类。

图3.27显示了该文法的LR(1)状态。在图中，一些项目具有相同的产生式，但向前查看的符号不同，如左图所示，将其简化后参见右图：

表3.28(a)是从状态图中导出的LR(1)分析表。

只要点号在产生式尾部(如图3.27中的状态3，点号在产生式E→V的尾部)，那么对于LR(1)表中的相应产生式就有一个归约动作，其相应的行号为状态号，相应列为向前查看符号(这里，向前查看符号为$)。

只要点号在终结符或非终结符的左边，那么在表中相应位置就会产生移进或转换动作，在这里同LR(0)表。

3.3.5 LALR(1) 分析表

LR(1)分析表有时会很大。可以通过合并向前查看符号集中不同的状态来实现表的压缩，得到的分析器叫做LALR(1) 分析器。

例如，考虑文法3.26中的LR(1)分析器(参见图3.27)，若向前查看的符号集可以忽略，那么状态6和状态13的项目是一样的。

同样，状态7和状态12，状态8和状态11，还有状态10和状态14都是如此。将这些状态合并，可以得到如表3.28(b) 所示的LALR(1) 分析表。

对于一些文法， LALR(1) 表包含归约-归约冲突，而在LR(1) 中却没有。但实际上这种区别并不重要。关键的区别是LALR(1) 分析表比LR(1) 表有更少的状态，所以需要更小的内存。

3.3.6 文法类型的层次结构

若一个文法的LALR(1) 分析表无冲突，那么该文法就是LALR(1) 文法。

所有的SLR文法都是LALR文法。

图 3.29 显示了一些文法类型间的关系。

所有合理的编程语言都有一个LALR(1) 文法，同时还有一些对应文法的分析器生成工具。因此， LALR(1) 文法已变成编程语言和自动分析器生成器的标准。

3.3.7 二义性文法的LR分析

一些编程语言包含如下的文法规则：

S→if E then S else S
S→if E then S
S→other

它们接收如下的程序指令：

    if a then if b then Sl elseS 2

该程序段有两种解释方式：

(1) if a then { if b then sl else s2 }
(2) if a then { if b then sl { else s2 

在大多数编程语言中， else 必须与最近的then匹配，所以解释方式(1) 是正确的。

在LR分析表中将会产生冲突：

S→if E then S. else 
S→ff E then S. else S (any)

移进与解释(1)相关，归约与解释(2)相关。

二义性可以通过引人两个非终结符来消除：M(匹配语句)和U(未匹配语句)：

S→M
S→U
M→if E the nM else M
M→other
U→if E the nS
u→if E the nM else U

可以保持文法不变并保留移进-归约冲突。

通过构造分析表，可以使用移进来解决冲突，因为已经选择了解释方式(1)。

二义性文法可能经常使用，应该通过合理的移进或归约来解决移进-归约冲突。

但最好谨慎地使用这些技术，仅在一些熟悉的情况下使用(比如这里描述的 else 匹配问题，以及以后即将描述的算符优先算法)。

几乎所有的移进-归约冲突都不应该使用分析表来解决。

它们都是不正确文法的先兆，应通过消除二义性来解决。

参考资料

《现代编译原理 java》

3.3 LR分析
3.3.1 LR分析器
3.3.2 LR(0)分析器生成器
3.3.3 SLR 分析器生成器
3.3.4 LR(1) 项目和 LR(1) 分析表
3.3.5 LALR(1) 分析表
3.3.6 文法类型的层次结构
3.3.7 二义性文法的LR分析
参考资料

编译原理系列-06-LR