注意，如果将条件改为“，”的优先级高且满足左结合，则将无法构造分析表。这是因为“，”在遇见其后的“，”时要求归约；而“；”在遇见其后的“，”时则要求移进；这时ACTION[8,“，”]栏就无法确定是放“r1”还是放“s5”了。 3.24 文法G[T]及其SLR(1)分析表(见表3-12)如下，给出串bibi的分析过程。 G[T]:(1) T→EbH (2) E→d (3) E→ε (4) H→i
(5) H→Hbi (6) H→ε
表3-12 习题3.24的SLR(1)分析表 ACTION GOTO 状态 b d i # T E H
0 r3 s3 1 2
1 acc
2 s4
3 r2
4 r6 s6 r6 5
5 s7 r1 6 r4 r4 7 s8 8 r5 r5 【解答】 对句子bibi，先构造它的语法树，如图3-15所示。 T
EbH
?Hbi i图3-15 句子bibi的语法树
bibi的分析过程参考该语法树进行，见表3-13。 表3-13 bibi的分析过程
输入串 状态 归约产生式 符号
0 r3 # bibi# 02 #E bibi# 024 #Eb ibi# 0246 r4 #Ebi bi# 0245 #EbH bi# 02457 #EbHb i# 024578 r5 #EbHbi # 0245 r1 #EbH #
01 #T #
acc
3.25 给出文法G[S]及图3-16所示的LR(1)项目集规范族中的0、1、2、3、4。 G[S]: S→S;B | B B→BaA | A
A→b(S) 01 S →·S, #′2
3
4
图3-16 习题3.25的部分项目集
【解答】 首先求出G[S]中所有非终结符的FOLLOW集。 已知FOLLOW(S′)={#}；则： 由S′→S得FOLLOW(S′) ?FOLLOW(S)，即FOLLOW(S)={#}； 由S→S;…得FOLLOW(S)={#,;}； 由A→…S)得FOLLOW(S)={#,;,)}； 由B→Ba…得FOLLOW(B)={a}；
由S→B得FOLLOW(S) ?FOLLOW(B)，即FOLLOW(B)={#,;,),a}； 由B→A得FOLLOW(B) ?FOLLOW(A)，即FOLLOW(A)={#,;,),a}。 LR(1)的闭包CLOSURE(I)可按如下方法构造： (1) I的任何项目都属于CLOSURE(I)。 (2) 若项目[A→α·Bβ,a]属于CLOSURE(I)，B→γ是一个产生式，对FIRST(βa)中的每个终结符b，如果[B→·γ,b]原来不在CLOSURE(I)中，则把它加进去。 (3) 重复执行步骤(2)，直至CLOSURE(I)不再增大为止。 注意，b可能是从β推出的第一个符号，若β推出ε，则b就是a。 我们先构造LR(1)项目集族的I0。 由FOLLOW(S)={#}可知[S′→·S,#]∈CLOSURE(I0)。此时β=ε，故b=a=“#”，即有： [S→·S;B,#]∈CLOSURE(I0) [S→·B,#]∈CLOSURE(I0) 此时对B→·γ而言，因β=ε，即b=a=“#”。 对[S→·S;B,#]，由于β≠ε，而FIRST(β)=FIRST(′;B′)={;}；则有： [S→·S;B,#/;]∈CLOSURE(I0) [S→·B,#/;]∈CLOSURE(I0) 同时有： [B→·BaA,#/;]∈CLOSURE(I0) [B→·A,#/;]∈CLOSURE(I0) 此时对A→·γ而言，因β=ε，即b=a=“#/;”。 对[B→·BaA,#]，由于β≠ε，而FIRST(β)=FIRST(′aA′)={a}；则有： [B→·BaA,#/;/a]∈CLOSURE(I0) [B→·A,#/;/a]∈CLOSURE(I0) 同时有：[A→·b(S),#/;/a]∈CLOSURE(I0)
S1 S →S·,#′′ S →·S,#0 S→S·;B,#/; S→·S;B,#/; B2 S→B·,#/; S→·B,#/; B→B·aA,#/;/a B→·BaA,#/;/a
A3 B→A·,#/;/a B→·A,#/;/ab4
A→b·(S),#/;/a A→·b(S),#/;/a
图3-17 习题3.25的LR(1)部分项目集
3.26 一个非LR(1)的文法如下： L→MLb | a M→ε 请给出所有“移进”/“归约”冲突的LR(1)项目集，以说明该文法确实不是LR(1)的。 【解答】 先将文法G[L]拓广为G[L′]：(0) L′→L 1) L→MLb (2) L→a (3) M→ε 如果按LR(1)方法构造分析表时出现“移进”/“归约”冲突，则项目集规范族中一定包含如下形式的项目： [A→α·bβ,a] 和 [A→α·,b] 即移进符号与向前搜索符号相同。 在构造LR(1)项目集族之前，我们先求出G[L′]中所有非终结符的FIRST集和 FOLLOW集：
FIRST(L′)=FIRST(L)={a, ε} FIRST(M)={ ε} 由FOLLOW集构造方法知FOLLOW(L′)={#}； 由L→…Lb 得FIRST(′b′) ? FOLLOW(L)，即FOLLOW(L)={b}； 由L→ML… 得FIRST(L)\\{ ε}? FOLLOW(M)，即FOLLOW(M)={a}； 由L′→L得FOLLOW(L′) ? FOLLOW(L)，即FOLLOW(L)={#,b}。 LR(1)闭包CLOSURE(I)构造方法如下： (1) I的任何项目都属于CLOSURE(I)。 (2) 若项目[A→α·Bβ,a]属于CLOSURE(I)，B→γ是一个产生式，对FIRST(βa)中的每个终结符b，如果[B→·γ,b]原来不在CLOSURE(I)中，则把它加进去。 (3) 重复执行步骤(2)，直至CLOSURE(I)不再增大为止。 注意，b可能是从β推出的第一个符号，若β推出ε，则b就是a。 令[L′→·L,#]∈CLOSURE(I0)，求得项目集如下： I0：L′→·L,# I2：L→M·Lb,# I4：L→M·Lb,b L→·MLb,# L→·MLb,b L→·MLb,b L→·a,# L→·a,b L→·a,b M→·, a M→·, a M→·, a I1：L′→L·,# I3：L→ML·b,# I5：L→MLb·,# 如果一个项目中含有m个移进项目： A1→α·a1β1, A2→α·a2β2, …,Am→α·amβm
同时I中含有n个归约项目： B1→α·, B2→α·, …, Bn→α· 如果集合{a1, …,am}，FOLLOW(B1), …,FOLLOW(Bn)两两相交，则必然存在“移进”/“归约”冲突。 由I0中L→·a, #和M→·,a 可知{a}∩FOLLOW(M)={a}∩{a}≠Φ(在此α=ε)； 由I2中L→·a,b和M→·,a 可知{a}∩FOLLOW(M)≠Φ； 由I4中L→·a,b和M→·,a 可知{a}∩FOLLOW(M)≠Φ； 也即，I0 、I2 、I4三个项目集存在“移进”/“归约”冲突。 3.27 试证明任何一个SLR(1)文法一定是一个LALR(1)文法。 【解答】 我们知道，在求闭包ε_CLOSURE(I)时，构造有效的LR(1)项目集与构造LR(0)项目集是有区别的。如果A→α·Bβ属于CLOSURE(I)，且关于B的产生式是B→γ，则对LR(0)来说，项目B→·γ也属于CLOSURE(I)；而对LR(1)(假定A→α·Bβ的后续一个字符为a)，则要求对FIRST(βa)中的每个终结符b，有项目[B→·γ,b]属于CLOSURE(I)。 LR(1)、LR(0)以及SLR(1)方法的区别也仅在上述构造分析表的算法上。也即若项目 A→α·属于Ik，则当“用产生式A→α归约”时，LR(0)是无论面临什么输入符号都进行归约；SLR(1)则是仅当面临的输入符号a∈FOLLOW(A)时才进行归约，而并不判断符号栈里的符号串所构成的活前缀βα是否把α归约为A的规范句型前缀βAa；而LR(1)则明确指出只有当α后跟终结符a(即存在规范句型其前缀为βAa)时，才允许把α归约为A。 因此，LR(1)比SLR(1)更精确，解决的冲突也多于SLR(1)，但LR(1)的要求(即限制)也比SLR(1)严格。但是对LR(1)来说，其中的一些状态(项目集)除了向前搜索符不同外，其核心部分都是相同的，也即LR(1)比SLR(1)和LR(0)存在更多的状态，但是每个LR(0)文法、SLR(1)文法都是LR(1)文法。
如果两个LR(1)项目集除去搜索符之后是相同的，则称这两个LR(1)项目集具有相同的心。当把所有同心的LR(1)项目集合并为一时，则会看到一个心就是LR(0)项目集(同时也是SLR(1)项目集)，这种LR分析法称为LALR方法。 假定有一个LR(1)文法，它的LR(1)项目集不存在动作冲突，如果我们把同心集合并为一，就可能导致冲突存在。但是这种冲突不会是“移进”/“归约”间的冲突。因为若存在这种冲突，则意味着面对当前的输入符号a，有一个项目[A→α·,a]要求采取归约动作；同时又有另一项目[B→β·aγ,b]要求把a移进。
这两个项目既然同处在合并之后的一个集合中，就意味着在合并之前必然有某个c使得[A→α·,a]和[B→β·aγ,c]同处于(合并之前的)某一集合中，然而这又意味着原来的LR(1)项目集已经存在着“移进”/“归约”冲突了，同时也意味着SLR(1)项目集也已经存在着“移进”/“归约”冲突(因为SLR(1)与合并后的LALR项目集相同。) 但是，同心集的合并有可能产生新的“归约”/“归约”冲突。假定有对活前缀ac有效的项目集为{[A→c·,d], [B→c·,e]}，对bc有效的项目集为{[A→c·,e], [B→c·,d]}，这两个集合都不含冲突，它们是同心的，但合并后就变成{[A→c·,d/e], [B→c·,d/e]}，显然这是一个含有“归约”/“归约”冲突的集合。由于SLR(1)与LALR同心(项目集相同),故在SLR(1)文法中必然存在“归约”/“归约”冲突。由此可知,任何一个SLR(1)文法一定是一个LALR(1)文法。 注意，LALR项目集族总是与同一文法的SLR(1)项目集的心相同，并且实现LALR分析对文法的要求比LR(1)严但比SLR(1)宽，而开销比SLR(1)大却远小于LR(1)。 3.28 已知文法G[S]: S→aAd | ;Bd | aB↑| ;A↑ A→a B→a
(1) 试判断G[S]是否为LALR(1)文法。 (2) 当一个文法是LR(1)而不是LALR(1)时，那么LR(1)项目集的同心集合并后会出现哪几种冲突，请说明理由。
【解答】 (1) 将文法G[S]拓广为文法G[S′]：(0) S′→S (1) S→aAd (2) S→;Bd (3) S→aB↑ (4) S→;A↑ (5) A→a (6) B→a
判断G[S]是否为LALR(1)文法的方法是：首先构造LR(1)项目集族，如果它不存在冲突，就把同心集合并在一起；若合并后的集族不存在“归约”/“归约”冲突(即不存在同一个项目集中有两个像A→c·和B→c·这样具有相同搜索符的产生式)，则表明G[S]是LALR(1)文法。 在构造LR(1)项目集族之前，先求出G[S′]中所有非终结符的FIRST集和FOLLOW集如下： FIRST(S′)= FIRST(S)={a,;} FIRST(A)={a} FIRST(B)={a} 由FOLLOW集构造方法知FOLLOW(S′)={#}； 由S′→S得FOLLOW(S′) ?FOLLOW(S)，即FOLLOW(S)={#}； 由S→…Ad和S→…A↑得FOLLOW(A)={d,↑}； 由S→…Bd和S→…B↑得FOLLOW(B)={d,↑}。 LR(1)的闭包CLOSURE(I)可按如下方法构造： ① I的任何项目都属于CLOSURE(I)； ② 若项目[A→α·Bβ,a]属于CLOSURE(I)，B→γ是一个产生式，对FIRST(βa)中的每一个终结符b，如果[B→·γ,b]原来不在CLOSURE(I)中，则把它加进去。 ③ 重复执行步骤②，直至CLOSURE(I)不再增大为止。 注意，b可能是从β推出的第一个符号，若β推出ε，则b就是a。 LR(1)项目集族构造如下： 由FOLLOW(S)={#}知S的向前搜索字符为“#”，即[S′→·S,#]。令[S′→·S,#] ∈CLOSURE(I0)，我们来求出属于I0的所有项目。已知[S′→·S,#]∈CLOSURE(I0)，由LR(1)闭包CLOSURE(I)步骤①知β=ε，也即对产生式S→aAd、S→;Bd、S→aB↑、S→;A↑都有b=a=“#”。由此得到项目集I0如下： I0：S′→·S,#
S→·aAd,# S→·;Bd,# S→·aB↑,# S→·;A↑,# 同理求得其他项目： I1: S′→S·,# I4: S→aA·d,# I10: S→aAd·,# I2: S→a·Ad,# I5: S→aB·↑,# I11: S→aB↑·,# S→a·B↑,# I6: A→a·,d I12: S→;Bd·,# A→·a,d B→a·,↑ I13: S→;A↑·,# B→·a,↑ I7: S→;B·d,# I3: S→;·Bd,# I8: S→;A·↑,#