第12章 自底向上分析 (下)

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 不是空集,则将其添加到状态转移表中,然后不断重复,直到无法生成新的状态,最终的状态转移表的图形如下:

images/lr1_1.png

图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 动作:

a b $ S X
I0 shift I3 shift I4 goto I1 goto I2
I1 ACCEPT
I2 shift I6 shift I7 goto I5
I3 shift I3 shift I4 goto I8
I4 reduce X–>b reduce X–>b
I5 reduce S–>XX
I6 shift I6 shift I7 goto I9
I7 reduce X–>b
I8 reduce X->aX reduce X->aX
I9 reduce X->aX

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

Sym-Stack State-Stack   X   x Remaining-Input   Parse-Action
I0   b   b aab$   M[I0,b] = shift I4
b I0 I4   a   a ab$   M[I4,a] = reduce X->b
I0   X   a ab$   M[I0,X] = goto I2
X I0 I2   a   a ab$   M[I2,a] = shift I6
Xa I0 I2 I6   a   a b$   M[I6,a] = shift I6
Xaa I0 I2 I6 I6   b   b $   M[I6,b] = shift I7
Xaab I0 I2 I6 I6 I7   $   $   M[I7,$] = reduce X->b
Xaa I0 I2 I6 I6   X   $   M[I6,X] = goto I9
XaaX I0 I2 I6 I6 I9   $   $   M[I9,$] = reduce X->aX
Xa I0 I2 I6   X   $   M[I6,X] = goto I9
XaX I0 I2 I6 I9   $   $   M[I9,$] = reduce X->aX
X I0 I2   X   $   M[I2,X] = goto I5
XX I0 I2 I5   $   $   M[I5,$] = reduce S–>XX
I0   S   $   M[I0,$] = goto I1
S I0 I1   $   $   M[I1,$] = ACCEPT

12.2 LR(1) 分析法的要求

和 LR(0) 分析法相比, LR(1) 利用了 lookahead 的信息后,其解析力量和适用范围有了质的飞跃,一个状态中可以同时含有可折叠形态和不可折叠形态(只要可折叠形态的 lookahead 不和不可折叠形态中黑点后面的符号冲突),也可以同时含有多条可折叠形态(只要这些可折叠形态的 lookahead 不相互冲突)。

LR(1) 分析法对语法的要求为:

(1) 起始符号 S 不能位于任何产生式的右边;

(2) 从此语法的起始状态开始生成的所有状态中:

(2.1) 任何一个状态不能同时含有 [ A -> u.aw , c ] 和 [ B -> v. , a ] ;

(2.2) 任何一个状态不能同时含有 [ A -> u. , a ] 和 [ B -> v. , a ] 。

以上的(2.1)将引起 shift/reduce 冲突,(2.2)将引起 reduce/reduce 冲突。一般语言的语法中很少会出现(2.2)的情况,而对于(2.1),在大部分情况下可以通过引入 优先级 来解决(见下一节)。

满足以上要求的语法被称为 LR(1) 语法,判断一个语法是否是 LR(1) 语法的方法就是构造其动作表,若构造过程中没有发现冲突,也就是表中的任何元素 M[I, X] 最多只有一个动作,那么此语法就是 LR(1) 语法。

12.3 利用符号的优先级来解决冲突

大部分情况下, LR(1) 解析过程的 shift/reduce 冲突可以通过引入符号的优先级来解决。具体方法为:

(1) 定义某些符号的优先级以及结合方式;

(2) 当构造 LR(1) 的过程中出现了 shift/reduce 冲突时,即某个状态 I 中同时还有 [ A -> u.aw , c ] 和 [ B -> v. , a ] ,若已定义符号 a 的优先级,且符号串 v 中至少有一个已定义优先级的符号,则可通过以下原则确定 M[I, a] 的动作:

(2.1) 找到 v 中最右边的、已定义优先级的符号(也就是 v 中离 a 最近的一个已定义优先级的符号),假设为 b ;

(2.2) 若 a 的优先级 低于 b 的优先级,则: M[I, a] = reduce B -> v ;

(2.3) 若 a 的优先级 高于 b 的优先级,则: M[I, a] = shift NEXT(I, a) ;

(2.4) 若 a 的优先级 等于 b 的优先级,则根据 a 和 b 的结合方式:

(2.4.1) 若 a 和 b 都为左结合,则 M[I, a] = shift NEXT(I, a) ;

(2.4.2) 若 a 和 b 都为右结合,则 M[I, a] = reduce B -> v 。

来看一个简单的例子,语法为:

0) S -> E
1) E -> E + E
2) E -> E * E
3) E -> id

first(S) = first(E) = id

所有的状态及转移关系见下:

 I0:                              I1:                            I2:
     Configurations:                  Configurations:                Configurations:
         S -> . E     , $                 S -> E .     , $               E -> id .    , +/*/$
         E -> . E + E , +/*/$             E -> E . + E , +/*/$       Actions:
         E -> . E * E , +/*/$             E -> E . * E , +/*/$           +  : reduce E -> id
         E -> . id    , +/*/$         Actions:                           *  : reduce E -> id
     Actions:                             +  : shift  I3                 $  : reduce E -> id
         E  : goto   I1                   *  : shift  I4
         id : shift  I2                   $  : reduce S -> E


 I3:                              I4:
     Configurations:                  Configurations:
         E -> E + . E , +/*/$             E -> E * . E , +/*/$
         E -> . E + E , +/*/$             E -> . E + E , +/*/$
         E -> . E * E , +/*/$             E -> . E * E , +/*/$
         E -> . id    , +/*/$             E -> . id    , +/*/$
     Actions:                         Actions:
         E  : goto   I5                   E  : goto   I6
         id : shift  I2                   id : shift  I2


 I5:                                           I6:
     Configurations:                               Configurations:
         E -> E + E . , +/*/$                          E -> E * E . , +/*/$
         E -> E . + E , +/*/$                          E -> E . + E , +/*/$
         E -> E . * E , +/*/$                          E -> E . * E , +/*/$
     Actions:                                      Actions:
         +  : shift  I3 / reduce E -> E + E            +  : shift  I3 / reduce E -> E * E
         *  : shift  I4 / reduce E -> E + E            *  : shift  I4 / reduce E -> E * E
         $  : reduce E -> E + E                        $  : reduce E -> E * E

注意状态 I5 和 I6 中都出现了两个 shift/reduce 冲突。以 I5 为例,它同时有以下两条形态:

1) E -> E + E . , *
2) E -> E . * E , x

上面第一条形态的 lookahead 和第二条形态中黑点后面的终结符都是 * ,因此当它遇到一个 * 时,可以执行 shift I4 ,也可以执行 reduce E -> E + E 。

现在按前面介绍的方法来确定该执行的动作。首先定义符号 * 和 + 的优先级分别为 0 和 1 (数字越小优先级越高),且定义两个符号都是左结合的。

再来看上面第一条形态,其产生式右边的符号串为 E + E ,这个符号串里最右边的、且定义了优先级的符号就是 + ,其优先级为 1 。而此形态的 lookahead (也就是 * )的优先级为 0 ,高于 + 。因此,选择的动作为 shift 。

再按上面的方法消除其他 shift/reduce 冲突,确定 I5 和 I6 的动作如下(其中方括号内的是被放弃的动作):

 I5:                                                 I6:
     Configurations:                                     Configurations:
         E -> E + E . , +/*/$                                E -> E * E . , +/*/$
         E -> E . + E , +/*/$                                E -> E . + E , +/*/$
         E -> E . * E , +/*/$                                E -> E . * E , +/*/$
     Actions:                                            Actions:
         +  : reduce E -> E + E [shift  I3]                 +  : reduce E -> E * E [shift I3]
         *  : shift  I4         [reduce E -> E + E]         *  : reduce E -> E * E [shift I4]
         $  : reduce E -> E + E                             $  : reduce E -> E * E

LL(1) 分析法的解析过程中,在挑选产生式的时候只利用下一个读入符号(lookahead)的信息,而 LR(1) 分析法不仅仅是利用下一个读入符号的信息,事实上,它几乎利用了前面读入过的所有的符号的信息。 LR(1) 分析法的解析力量和适用范围远大于 LL(1) 分析法,在引入符号优先级解决常见的 shift/reduce 冲突情况后,它可以解析目前几乎所有的程序语言。

到了这里,可以圆满的回答上一章最后的两个问题了:

如何找出可行的折叠? 答案:利用状态和形态,当转移到一个含可折叠形态 [ A -> u. , a ] 的状态、且下一个读入符号是 a 时,就可以执行一次可行的折叠了。

有多个可行的折叠怎么办? 答案: 若采用 LR(1) 分析法,则很少会出现这种情况,且可以比较容易的将语法改写成 LR(1) 语法。

12.4 优化的 LR(1) 分析法: LALR(1)

从前面的内容可以看出, LR(1) 分析法的构造过程十分复杂,且状态和形态的数量都非常之多,即便是本章第一节的仅仅含 4 个产生式的如此简单的例子,也多达 9 个状态和 27 条形态,如下:

images/lr1_1.png

图12.2 状态转移图

上面这个图中, I3 和 I6 几乎是一样的,I4 和 I7 、以及 I8 和 I9 也非常的相似,可以将这样的状态 merge 起来,形成下面这样的状态转移表:

images/lr1_2.png

图12.3 状态转移图

可以看出 merge 后的状态总数少了 3 个,可节省动作表的空间,解析速度也有较大的提高。这种将相似状态 merge 起来的分析法称为 LALR(1) 分析法,这是很多编译器所采用的分析方法。具体的 merge 算法比较复杂,本文档就不介绍了,因为 LALR(1) 分析的基本构造流程和解析流程和 LR(1) 分析法是一样的。

第 12 章完