12.1 构造 LR(1) 分析器

LR(0) 分析法要求语法的状态中不能有多条可折叠形态、且不能同时有可折叠形态和不可折叠形态，这是为了避免 reduce/reduce 冲突和 shift/reduce 冲突，此限制条件相当强，导致 LR(0) 的适用范围非常小。

事实上，只要对 LR(0) 法做一个很小的改进，就可以将这个限制条件去掉非常大的一部分。

这个可改进的地方就在于： LR(0) 法在执行 reduce 动作的时候没有利用下一个读入的符号的信息。

即便一个状态中含有多条可折叠形态，如： I = { “A -> u.” ; “B -> v.” } ，那么只要 Follow(A) 和 Follow(B) 不相交，就可以利用下一个符号 a 来选择折叠时需应用的产生式，如果 a 属于 Follow(A) ，那就 reduce “A -> u” ，如果 a 属于 Follow(B) 那就 reduce “B -> v” 。

shift/reduce 冲突同样可能避免，若一个状态中含有可折叠形态，也含有不可折叠形态，如： I = { “A -> u.” ; “B -> v.w” } ，那么只要 Follow(A) 和 First(w) 不相交，那也可以利用下一个符号 a 来选择需要执行的动作，如果 a 属于 Follow(A) ，那就 reduce ，如果 a 属于 First(w) 那就 shift 。

按以上思路，可以对 LR(0) 法进行一个小小的改进。但是还可以更进一步的，在形态中就绑定需要的下一个符号的信息，将上一章中的形态的格式改进一下，改进成下面这样的格式：

A –> X1 … Xi • Xi+1 … Xn , a

上面这个形态代表着这样的解析状态：目前栈上的符号为 X1 … Xi ，期待遇到 Xi+1 … Xn 这一系列的符号，并且只有 Xn 后读入的终结符是 a 的时候才执行 reduce 动作。这个 a 被称为 预测先行（lookahead） 。

使用这种格式的形态的 LR 解析法称为 LR(1) 分析法，括号中的 1 表示需要 1 个 lookahead ，也就是只利用下一个读入符号的信息。LR(1) 的构造过程和 LR(0) 的构造过程几乎一样，以下仅介绍二者不同的地方。

新格式形态的后继形态、延伸形态：

后继形态（successor configuration） ：形态：

C = [ A -> X•YZ, a ]

遇到符号 Y 的后转移到形态：

C’ = [ A -> XY•Z, a ]

C’ 称为形态 C 遇到符号 Y 的后继形态，记为 NEXT(C, Y)。

延伸形态（extended configuration） ： 若一个形态 C 的黑点后面是非终结符 B ，即：

C = [ A -> u.Bv, a ]

且有： B -> w ， b ∈ First(va) 。则形态：

C’ = [ B -> .w, b ]

是形态 C 的延伸形态。也就是说， C’ 中的产生式左边的非终结符就是 C 中黑点后面的非终结符，且 C’ 中的 lookahead 是 First(va) 中的一个符号（其中 v 是形态 C 中 B 后面的符号串， a 是形态 C 的lookahead）。

例如：

若 C = [ A -> b.BDd, a ] ，且 B 和 D 的产生式为： B -> c ，D -> e | f ，则 First(Dda) = {e, f} ，因此形态：

[ B -> .c, e ] 和 [ B -> .c, f ]

都是 C 的延伸形态。

为什么 C’ 中的 lookahead 是 First(va) 中的符号呢？我们再观察一下形态 C ：

C = [ A -> u.Bv, a ]

这个形态表明目前栈上的符号串是 u ，期待遇到符号 B ，再遇到符号串 v ，最后遇到 a 时才能折叠。因此，要折叠形态 C’ 得到符号 B ，遇到的终结符 b 必须得是 C 中的 B 后面的终结符，也就是 First(v) ，但如果 First(v) 中含有 ε 呢，这时就一定得遇到符号 a 才能折叠。因此： b 必须得是 First(va) 中的符号。

进一步，若 C’’ 是 C’ 的延伸形态，则 C’’ 也是 C 的延伸形态。这里再次强调一下：延伸的方向是单向的。

新格式形态的相关操作和上一章的几乎是一模一样的：

形态集合的闭合（closure of a configurating set） ：闭合操作步骤（设集合名为 I）：

（1） 遍历 I ，对 I 中的每一条黑点后是非终结符的形态 [ A -> u.Bv , a ] ，对 B 的每一个产生式 B -> w 、以及 First(va) 中的每一个符号 b ，将形态 [ B -> .w, b ] 添加进 I 。

（2） 重复（1），直到不再出现新的形态。

闭合操作的得到的新集合 I’ 仍然称为原集合 I 的 闭包集合 ，记为 CLOSURE(I) 。

上下文无关语法的起始状态（start state of a CFG） ： 若一个 CFG 的起始符号 S 的所有产生式为 S -> u1 | u2 | … | un ，且 S 不位于任何产生式的右边，则其起始状态（记为 I0 ）是以下形态的集合的闭包集合，即：

I0 = CLOSURE( { [S->.u1, $], [S->.u2, $] , … [S->.un, $] } )

后继状态（succesor state） ： 当状态 I 遇到符号 X 时，可能转移到另一个状态，称此状态为状态 I 遇到符号 X 的后继状态，记为 NEXT(I, X) ，按下式计算：

NEXT(I, X) = CLOSURE( { NEXT(C, X) | C ∈ I } )

NEXT(I, X) 的计算步骤为：

（1） 置 I’ 为空集。

（2） 遍历 I ，对 I 中每一条形态 C ，若 NEXT(C, X) 存在，则将 NEXT(C, X) 加入 I’ 。

（3） 对 I’ 进行闭合操作。

注意，NEXT(I, X) 可能为空集。

来看一个简单的例子吧：

0) S' –> S
1) S –> XX
2) X –> aX
3) X –> b

首先算出所有符号的 first set ： First(S) = First(S’) = First(X) = {a, b} 。

起始状态 I0 = CLOSURE( { “S’ -> .S , $” } ) ：

I0:
    S' –> .S  , $
    S  –> .XX , $
    X  –> .aX , a/b
    X  –> .b  , a/b

上面的 “X –> .aX , a/b” 是两条形态 “X –> .aX , a” 和 “X –> .aX , b” 的简写。

还是按上一章的步骤，对语法中的所有符号 X （S’, S, X, a, b） ，求出 I0 遇到 X 的后继状态 I1 = NEXT(I0, X) ，若 I1 不是空集，则将其添加到状态转移表中，然后不断重复，直到无法生成新的状态，最终的状态转移表的图形如下：图12.1 状态转移图

构造动作表 M 的步骤也和上一章的大致一样， M 中的 M[I, X] 表示栈顶状态为 I ，下一个符号为 X 时所应采取的动作，按以下情况确定：

（1） NEXT(I, X) 存在（设为 I’）、 X 为终结符： M[I, X] = shift I’ ；

（2） NEXT(I, X) 存在（设为 I’）、 X 为非终结符： M[I, X] = goto I’ ；

（3） I 中含有形态 [ A -> X1 X2 … Xn • , X] ，有以下两种情况：

（3.1） A != S 或 X != $ ： M[I, X] = reduce A -> X1 X2 … Xn ；

（3.2） A == S 且 X == $ ： M[I, X] = accept ；

（4） 其他所有情况： M[I, X] = deny 。

按以上步骤以及图12.1，构造出的动作表 M 如下，其中 M[I, X] 为空白的表示 deny 动作：

构造出动作表后，LR(1) 解析流程和 LR(0) 是一样的，详见上一章，下面对句子 “baab” 进行解析，全过程如下：