admin 管理员组文章数量: 1086019
2024年12月31日发(作者：霹雳兵烽决之碧血玄黄西瓜)
表中没有多从定义的元素，所以文法是LR(1)文法。
（2）LR(1)分析法：
状态
项目集
经过的符号
到达的状态
I0
E’ →·E#
E→·E+T#/+
E→·T#/+
T→·a#/+
E
T
(
T→·(E)#/+
R2
R2
R2
4
R5
R5
R5
5
S5
S4
6
6
R4
R4
R4
a
I1
I1
I5
I4
I1
E’ →E·#
E→E·+T#/+
+
I2
I2
E→E+·T#/+
T→·(E)#/+
T→·a#/+
T
(
a
I3
I5
I4
I3
T→a·#/+
I5
T→(·E)#/+
E→·E+T+/)
E→E+T·#/T
I4
E→·T)/+
T→·(E)+/)
T→·a+/)
E
C
T
a
I7
I8
I9
I12
I6
E→T·#/+
I7
T→(E·)#/+
E→E·+T+/)
)
+
I10
I11
I8
E→·E+T+/)
E→·T)/+
T→·(E)+/)
T→(·E))/+
T→·a+/)
(
a
E
T
I8
I12
I14
I9
I9
E→T·+/)
I10
T→(E) ·#/+
I11
E→E+·T+/)
T→·(E)+/)
T→·a+/)
(
T
a
I8
I13
I12
I12
T→a·+/)
I13
E→E+T·)/+
I14
T→(E·)+/)
E→E·+T+/)
+
)
I11
I15
I15
T→(E) ·+/)
LALR(1)分析：（合并同心集）
状态
项目集
经过的符号
到达的状态
I0
E’ →·E#
E→·E+T#/+
E→·T#/+
T→·(E)#/+
T→·a#/+
E
T
a
I1
I6/I9
I4/I12
I1
E’ →E·#
E→E·+T#/+
+
I2/I11
I2/I11
E→E+·T#/+/）
T→·(E)#/+/）
T→·a#/+/）
T
(
a
I3/I13
I5/I8
I4/I12
I3/I13
E→E+T·)/+/#
I4/I12
T→a·+/)/#
I5/I8
T→(·E)#/+/）
E→·E+T+/)
E→·T)/+
T→·(E)+/)
T→·a+/)
T
(
E
a
I6/I9
I5/I8
I7/I14
I4/I12
I6/I9
E→T·+/)/#
I7/I14
T→(E·)+/)/#
E→E·+T+/)
+
)
I2/I11
I10/I15
I10/I15
T→(E) ·+/)/#
LR(1)
ACTION
GOTO
+
(
)
a
#
E
T
0
S5
S4
1
6
1
S2
ACC
2
S5
S4
3
3
R1
R1
4
R4
R4
5
S8
S12
7
9
6
R2
R2
7
S11
S10
8
S8
S12
14
9
9
R2
R2
10
可以看出，表中无冲突项，所以是LR(1)文法；LALR（1）分析表：
LR(1)
ACTION
GOTO
+
(
)
a
#
E
T
0
S5/S8
S4/S12
1
6/9
R3
R3
11
S8
S12
13
12
R4
R4
13
R1
R1
14
S11
S15
15
R3
R3
1
S2/S11
ACC
2/11
S5/S8
S4/S12
3/13
3/13
R1
R1
R1
4/12
R4
R4
R4
5/8
S5/S8
S4/S12
7/14
6/9
6/9
R2
R2
R2
10/15
R3
R3
R3
7/14
S2/S11
S10/S15
解：
（1）求LR(1)项目集和状态转换图：
E’ →·E#
E→·E+E#,+,*
E→·E*E#,+,*
E→·i#,+,*
E
i
I1
I2
I1
E’ →E·#
E→E·+E#,+,*
E→E·*E#,+,*
+
*
I3
I4
I2
E→i·#,+,*
I3
E→E+·E#,+,*
E→·E+E#,+,*
E→·E*E#,+,*
E→·i#,+,*
状态
项目集
经过的符号
到达的状态
I0
E
i
I5
I2
I4
E→E*·E#,+,*
E→·E+E#,+,*
E→·E*E#,+,*
E→·i#,+,*
E
i
I6
I2
I5
E→E+E·#,+,*
E→E·+E#,+,*
E→E·*E#,+,*
+
*
I3
I4
I6
E→E·+E#,+,*
E→E·*E#,+,*
+
*
E→E*E·#,+,*
I3
I4
状态
ACTION
GOTO
i
+
*
#
E
0
s2
1
1
s3
s4
acc
2
r3
r3
r3
3
s2
5
4
s2
6
依据以上图求出该文法的LR(1)分析表知道由于项目I5,I6导致了有多重定义的元素，所以
不是LR(1)文法。事实上，从文法本身可以看出它是二义性的，因此不可能是LR（1）文
法。等价的LR(1)文法为：E→E+T|TF→T*F|FF→i。另外，对原文法的冲突项来说，若考
虑算术运算符的运算优先级别，以及结合方式，上述冲突是可解决的。例如，假设表达式
运算满足左结合律（即a+b+c=(a+b)+c而不是右结合律：a+b+c=a+(b+c)）,及*运算和优化
优先级高于+运算，上述文法相应的LR（1）分析表为
（2）解：LR(1)：
状态
项目集
经过的符号
到达的状态
I0
S’ →·S#
S→·aSa#
S→·bSb#
S→·a#
S→·b#
S
a
b
I1
I2
I3
I1
S’ →S·#
I2
S→a·Sa#
5
r1
s4
r1
6
r2
r2
r2
S→a·#
S→·aSaa
S→·bSba
S→·aa
S→·ba
S
a
b
I4
I7
I6
I3
S→b·Sb#
S→b·#
S→·aSab
S→·ab
S→·bSbb
S→·bb
S
a
b
I11
I14
I13
I4
S→aS·a#
a
I5
I5
S→aSa·#
I6
S→b·Sba
S→b·a
S→·aSab
S→·bSbb
S→·ab
S→·bb
S
a
b
I10
I14
I13
I7
S→a·Saa
S→a·a
S→·bSba
S→·aa
S→·ba
S
S→·aSaa
a
b
I8
I7
I6
I8
S→aS·aa
a
I9
I9
S→aSa·a
I10
S→bS·ba
b
I15
I11
S→bS·b#
b
I12
I12
S→bSb·#
I13
S→b·Sbb
S→b·b
S→·bSbb
S→·ab
S→·bb
S
S→·aSab
a
b
I16
I14
I13
I14
S→a·Sab
S→a·b
S→·aSaa
S→·bSba
S→·aa
S→·ba
S
a
b
I18
I7
I6
I15
S→bSb·a
I16
S→bS·bb
b
I17
I17
S→bSb·b
I18
S→aS·ab
a
I19
I19
S→aSa·b
有移进——归约冲突，不是LR(1)文法。
（3）求LR(1)项目集和状态转换图：
状态
项目集
经过的符号
到达的状态
I0
S’ →·S#
S→·V:=E#
S→·LS#
L→·I:I
V→·I:
S
V
L
I
I1
I2
I3
I4
I1
S’ →S·#
I2
S→V·:=E#
:
I5
I3
S→L·S#
S→·V:=E#
S→·LS#
V→·I:
L→·I:I
S
L
I
I6
I3
I4
I4
L→I·:I
V→I·:
:
I7
I5
S→V: ·=E#
=
I8
I6
S→LS·#
I7
L→I: ·I
I8
S→V:= ·E#
E
I9
I9
S→V:=E·#
=”移进”总是伴随着填写GOTO(Sm,ai)=Sm+1，所以这种情况下结论成立。
先访问ACTION(Sm,ai)=rj，其中ai是一个终结符,rj意指按文法的第j个产生式A→Xm-
r+1Xm-r+2···Xm进行归约，再访问GOTO(Sm-r,A)=Sl, 其中A是一个非终结符。查看
构造LR分析表的算法的条目（1），可以知道当ai是一个非终结符时，填写GOTO(Sm,ai)
=Sm+1，即只有归约出了ai时，再状态转换到Sm+1,和总控程序情况一致，所以这种情况
下结论成立。
综上所述，结论成立。
46．证明：在文法G[S]中，只有非终结符S有两个候选式，AaAb及BbBa，而两个候选的
FIRST集分别为{a}和{b}，它们不相交，所以，文法G[S]满足LL（1）文法的条件，是
LL（1）文法。在SLR（1）方法识别活前缀的DFA中，项目I0={S'→· S, S→ ·AaAb,
S→· BbBa, A→e· , B→e· }中出现归约-归约冲突，而follow(A)=follow(B)={a,b}，用
SLR（1）方法不能解决冲突。
证：根据第3章“词法分析及词法分析程序”，我们知道任一正规集可以由某一正规式r表
示，而对于任一正规式r，都可以构造一个DFA,并且两者在表述语言的意义下等价。根据
这个DFA，我们可以很容易地构造一个分析表。方法是对于DFA中的每一个子图，如果
从状态Ii，经过了终结符号a,到达状态Ij,则在分析表中有ACTION(Ii,a)=Sj，如果Sj是一
个终结状态，则置ACTION(Ii,a)=ACC。
解： SLR(1)分析表比LR(0)分析表在采用一定形式存储时（如稀疏矩阵），会少一些存储
空间。另外，在分析进行到归约动作时，LR（0）无论下一符号是什么（即使是错误的输
入），都将先进行归约，然后才判断下一输入符是否正确；而SLR（1）在进行归约时还要
先看看下一符号是否正确，否则将报错。从而可知，对于有错误的输入串，SLR（1）分析
效率要高一些。
证：考察LR分析器的总控程序，可以知道访问GOTO分析表元素的可能只有两种，下面
分情况讨论：
先访问ACTION(Sm,ai)=”移进”，再访问GOTO(Sm,ai)=Sm+1,其中ai是一个终结符。查看
构造LR分析表的算法的条目（1），可以知道当ai是一个终结符时，填写ACTION(Sm,ai)
（4）略。
依据以上图求出该文法的LR(1)分析表知道由于项目I4导致了有多重定义的元素，所以不
是LR(1)文法。
48．略。
47．略。
版权声明：本文标题：(完整版)编译原理课后答案(第三版蒋立源康慕宁编) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1735745698a1687795.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论