9 or I10： ropi I2：B→i rop·i I3：B→i ropi· I：B→i·i1 B→i ·rop i′ I0：S →·B B→·ii B→·i rop i B→·(B)( I4：B→(·B) B→·not B I12：B→(B)· B→·i B→·AB I11：B→(B·)and B→·OBB B→·i rop i A→B·and I9： B→·(B) A→·B and O→B·or( O→·B or B→·not BO I10： B→·AB O B→·OBOA A→·B and Anot O→·B or (not I5：B→not·B B→·inot B→·i rop i O B→·(B) B→·not Bi B→·ABA B→·OB B→·B and B→·B or Band I9：A→B and· I6：B→not B· A→B·and O C→B·or I10：O→B or· O I7：B→A·B B→·iandB I14：B→AB· B→·i rop i A→B·and B→·(B) O→B·or B→·not B not B→·AB B→·OB A( A→·B and O→·B or i OA I8：B→O·Bnot B→·i ( B→·i rop i B→·(B)i B→·not B B→·ABandO I9： I15：B →OB· B→·OBB A→B·and A→·B andor O→B·or I10： O→·B or
图3-19 习题3.31中文法G[S′]的DFA 下面，对文法G[S′]中形如“A→α·”的项目： I13 ： S′→B· I12 ： B→(B)· I14 ： B→AB· I1 ： B→i· I6 ： B→not B· I10 ： O→B or· I3 ： B→i rop i· I9 ： A→B and· I15 ： B→OB· 求FOLLOW集。根据FOLLOW集构造方法，构造文法G[S′]中非终结符的FOLLOW集如下：
① 对文法开始符S′，#∈FOLLOW(S′)，即FOLLOW(S′)={#}。 ② 由B→…B)得FIRST(′) ′)\\{ε}?FOLLOW(B)，即FOLLOW(B)={ )}； 由B→B and得FIRST(′and′)\\{ε}?FOLLOW(B)，即FOLLOW(B)={ )，and};
B I13：S →B· A→B·and O→B·orand I： 由O→B or得FIRST(′or′)\\{ε}?FOLLOW(B)，即FOLLOW(B)={)，and,or}; 由B→AB得FIRST(B)\\{ε}?FOLLOW(A)，即FOLLOW(A)={ i，(,not) (注：FIRST(B)={ i，(,not)}；
由B→OB得FIRST(B)\\{ε}?FOLLOW(O)，即FOLLOW(O)={ i，(,not)。 ③ 由S′→B得FOLLOW(S′)?FOLLOW(B)，即FOLLOW(B)={ )，and，or,#}，由此得到FOLLOW(B)={ )，and，or,#}，FOLLOW(A)=FOLLOW(O)={ i，(,not)。 分析图3-19，可知I1、I6、I14、I15存在矛盾。I1的“移进”/“归约”矛盾可以在SLR(1)下得到解决，因为FOLLOW(B)={ )，and，or,#}，而移进仅是在字符“rop”下进行的，即有FOLLOW(B)∩{ rop }=Φ，故移进与归约不发生矛盾(归约是在字符“)”、“and”、“or”或“#”下进行的)。 而I6、I14和I15的“移进”/“归约”矛盾无法得到解决(在字符“and”和“or”下既要“移进”又要“归约”)，故文法G[S′]是一个二义文法。经分析，当B遇到后面的“and”或“or”时应移进，故服从右结合规则。由此得到布尔表达式的SLR(1)分析表见表3-17。
表3-17 习题3.31的布尔表达式的SLR(1)分析表 状ACTION GOTO 态 i rop ( ) not and or # B A O 0 s1 s4 s5 13 7 8
1 s2 r1 r1 r1 r1
2 s3
3 r2 r2 r2 r2
4 s1 s4 s5 11 7 8
5 s1 s4 s5 6 7 8
6 r4 s9 s10 r4
7 s1 s4 s5 14 7 8 8 s1 s4 s5 15 7 8 9 r5 r5 r5 10 r7 r7 r7 11 s12 s9 s10
12 r3 r3 r3 r3
13 s9 s10 acc
14 r6 s9 s10 r6
15 r8 s9 s10 r8 3.32 给出文法G[S]: S→SaS∣SbS∣cSd∣eS∣f。 (1) 请证实这是一个二义文法； (2) 给出什么样的约束条件可构造无冲突的LR分析表？请证实你的论点。 【解答】 (1) 对于语句fafbf，该文法存在两棵不同的语法树，如图3-20所示。
SS
SaSSbS
fSbSSaSf图3-20 语句fafbf的两棵不同语法树
ffff 因此，G[S]是二义文法。 (2) 首先将文法G[S]拓广为G[S′]：(0) S′→S (1) S→SaS (2) S→SbS (3) S→cSd (4) S→eS (5) S→f 该文法G[S′]的DFA如图3-21所示。 ef ′ I1：S →S·′ I5：S→Sa·SSa I0：S →·S S→S·aS S→·SaS S→·SaS S→S·bS S→·SbS S→·SbS S→·cSdb S→·cSdc S→·eS S→·eSc I2：S→c·Sde S→·f S→·f S→·SaS S→·SbSf S→·cSd f S→·eSc I：S→f· I6：S→Sb·S4 S→·fS S→·SaS ecc S→·SbS S→·cSde S→·eSf S→·fSa I9：S→SaS· S→S·aS S→S·bSbaSb I10：S→SbS· S→S·aS S→S·bS I3：S→e·Sf S→·SaS S→·SbS S→·cSd S→·eSe S→·fSb I7：S→cS·dd S→S·aS S→S·bSaa I8：S→eS· S→S·aSb S→S·bS I11：S→cSd·图3-21 习题3.32中G[S′]的DFA
状态I1、I8、I9和I10存在“移进”/“归约”冲突。计算G[S′]中所有非终结符的 FOLLOW集： FOLLOW(S′)={#} FOLLOW(S)={a,b,d,#} ① 对于I1：S′→S· S→S·aS S→S·bS 可以采用SLR(1)解决冲突，即当LR分析器处于状态1时，如果下一个输入符号是“#”，则按S′→S·执行归约；如果下一个输入符号是“a”或“b”，则执行移进。 ② 对于I8：S→eS· S→S·aS S→S·bS 该冲突无法采用SLR(1)解决，我们给出约束条件：让e的优先级比a和b高，则
当LR分析器处于状态8时，若下一输入符号是FOLLOW(S)中的符号，就按S→eS·执行归约。 ③ 对于I9：S→SaS· S→S·aS S→S·bS 该冲突无法采用SLR(1)解决，我们给出约束条件：让a的优先级比a和b高，即实行左结合，则当LR分析器处于状态9时，若下一输入符号是FOLLOW(S)中的符号，就按S→SaS·执行归约。 ④ 对于I10：S→SbS· S→S·aS S→S·bS 此时也给出约束条件：让b的优先级比a和b高，即实行左结合，则当LR分析器处于状态10时，若下一输入符号是FOLLOW(S)中的符号，就按S→SbS·执行归约。
综上所述，统一给出构造无冲突的LR分析表的约束条件是：左边终结符的优先级比右边终结符高，即实行左结合。另外，我们也看到，消除左递归有助于解决LR分析表中的冲突。 3.33 根据下面所给文法G[S′]和表3-18分析ia;iaea# 的语义加工过程。 G[S′]：(0) S′→S (1) S→iSeS (2) S→iS (3) S→S;S (4) S→a
【解答】 ia;iaea# 的语义加工过程见表3-19。 表3-18 习题3.33的SLR(1)分析表 ACTION GOTO 状态 i e ; a # S 0 s2 s3 1 1 s4 acc
2 s2 s3 5
3 r4 r4 r4
4 s2 s3 6
5 s7 r2 r2
6 r3 r3 r3
7 s2 s3 8
8 r1 r1 r1
表3-19 ia;iaea# 的语义加工过程
步 骤 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 状 态 栈 0 02 023 025 01 014 0142 01423 01425 014257 0142573 0142578 0146 01 acc 符 号 栈 # # i # ia # iS # S # S; # S;i # S;ia # S;iS # S;iSe # S;iSea # S;SeS #S;S # S 输 入 串 ia;iaea# a;iaea# ;iaea# ;iaea# ;iaea# iaea# aea# ea# ea# a# # # # #