作业解答第5章.docx
《作业解答第5章.docx》由会员分享，可在线阅读，更多相关《作业解答第5章.docx（16页珍藏版）》请在冰点文库上搜索。
作业解答第5章
5.1考虑以下的文法:
StS;T|T
TTa
（1）
为这个文法构造
LR（0）的项目集规范族。
（2）
这个文法是不是
LR（0）文法？
如果是，则构造LR（0）分析表。
（3）
对输入串“a;a”
进行分析。
解：
（1）拓广文法G[S']:
0:
S'ts
1:
StS;T
2:
StT
3:
TTa
构造LR（O）项目集规范族
状态
项目集
转换函数
0
S't・s
St.S;T
St・T
TT・a
GO[0,S]=1
GO[0,S]=1
GO[0,T]=2
GO[0,a]=3
1
S'ts-
Sts•;T
ACCEPT
GO[1,;]=4
2
StT•
R2
3
Tta•
R3
4
StS;•T
TT・a
GO[4,T]=5
GO[4,a]=3
5
StS;T•
R1
（2）该文法不存在“归约—归约”和“归约—移进”冲突，因此是LR（0）文法。
LR（0）分析
表如下：
状态
ACTION
GOTO
;
a
#
s
T
0
S3
1
2
1
S4
ACCEPT
2
R2
R2
R2
3
R3
R3
R3
4
S3
5
5
R1
R1
R1
（3）对输入串“a;a”进行分析如下:
步骤
状态栈
符号栈
输入符号栈
ACTION
GOTO
0
0
#
a;a#
S3
1
03
#a
;a#
R3
2
3
02
#T
;a#
R2
1
4
01
#S
;a#
S4
5
014
#S;
a#
S3
6
0143
#S;a
#
R3
5
7
0145
#S;T
#
R1
1
8
01
#S
#
ACCEPT
5.2证明下面文法是SLR
（1）文法，但不是LR（O）文法。
SF
LAb|bBa
BtaAc|a|aAb
解：
文法G[S]:
0:
StA
1:
AtAb
2：
AtbBa
3:
BtaAc
4:
BTa
5:
BtaAb
构造LR（0）项目集规范族:
状态
项目集
转换函数
0
St・A
At・Ab
At・bBa
GO[0,A]=1
GO[0,A]=1
GO[O,b]=2
1
StA-
Ata-b
ACCEPT
GO[1,b]=3
2
Atb•Ba
Bt・aAc
Bt・a
Bt・aAb
GO[2,B]=4
GO[2,a]=5
GO[2,a]=5
GO[2,a]=5
3
AtAb•
R1
4
AtbB-a
GO[4,a]=6
5
Bta•Ac
Bta•
Bta•AbAt・Ab
At・bBa
GO[5,A]=7
R4
GO[5,A]=7
GO[5,A]=7
GO[5,b]=2
6
AtbBa•
R2
7
BtaA-c
BtaA-b
Ata-b
GO[7,c]=8
GO[7,b]=9
GO[7,b]=9
8
BtaAc•
R3
9
BtaAb•
AtAb•
R5
R1
LR（0）
状态5存在“归约-移进”冲突，状态9存在“归约-归约”冲突，因此该文法不是
文法。
状态5:
FOLLOW（B#{a},因此，FOLLOWED{b①
状态9:
FOLLOW（B#{a},FOLLOW（A）={#,b,c}，因此FOLLOWEDFOLLOW（A）=①
状态5和状态9的冲突均可用SLR
（1）方法解决，构造SLR
（1）分析表如下：
状态
ACTION
GOTO
a
b
c
#
A
B
0
S2
1
1
S3
ACCEPT
2
S5
4
3
R1
R1
R1
4
S6
5
R4
S2
7
6
R2
R2
R2
7
S9
S8
8
R3
9
R5
R1
R1
R1
该SLR
（1）分析表无重定义，因此该文法是SLR
（1）文法，不是LR（0）文法。
5.3证明下面文法是LR
（1）文法，但不是SLR
（1）文法。
SfAaAb|BbBa
A^£
Bf£
解：
拓广文法G[S']:
0:
S'fS
1:
SfAaAb
2：
SfBbBa3:
Af£
4:
Bf£
构造LR（0）项目集规范族:
状态
项目集
转换函数
0
S'f・SSf・AaAbSf・BbBaAf.
Bf・
GO[O,S]=1
GO[O,A]=2
GO[O,B]=3
R3
R4
1
S'fS-
ACCEPT
2
SfA-aAb
GO[2,a]=4
3
SfB•bBa
GO[3,b]=5
4
SfAa-Ab
GO[4,A]=6
R3
5
SfBb•Ba
Bf・
GO[5,B]=7
R4
6
SfAaA-b
GO[6,b]=8
7
SfBbB*a
GO[7,a]=9
8
SfAaAb-
R1
9
SfBbBa*
R2
状态0存在“归约—归约”冲突，且FOLLOW（A）={a,b},FOLLOW（B）={a,b},即FOLLOW（A）nFOLLOW（B）={a,b}工①，所以该文法不是SLR⑴文法。
构造LR
（1）项目集规范族:
状态
项目集
转换函数
0
S'f・S,#
Sf・AaAb,#
Sf・BbBa#
Af・,a
Bf・,b
GO[0,S]=1
GO[0,A]=2
GO[0,B]=3
R3
R4
1
S'fS•,#
ACCEPT
2
SfA-aAb,#
GO[2,a]=4
3
SfB-bBa,#
GO[3,b]=5
4
SfAa-Ab,#
Af・,b
GO[4,A]=6
R3
5
SfBb-Ba,#
Bf・,a
GO[5,B]=7
R4
6
SfAaA-b,#
GO[6,b]=8
7
SfBbB-a,#
GO[7,a]=9
8
SfAaAb-,#
R1
9
SfBbBa-,#
R2
LR
（1）分析表:
状态
ACTION
GOTO
a
b
#
S
A
B
0
R3
R4
1
2
3
1
ACCEPT
2
S4
3
S5
4
R3
6
5
R4
7
6
S8
7
S9
8
R1
9
R2
5.4考虑以下的文法：
iEE+
iEE*
ia
（1）为这个文法构造LR
（1）项目集规范族。
（2）构造LR
（1）分析表。
（3）为这个文法构造LALR
（1）项目集规范族。
（4）构造LALR
（1）分析表。
（5）对输入符号串“aa*a+”进行LR
（1）和LALR
（1）分析。
解：
（1）拓广文法G[S]:
0:
StE
1:
Etee+
2:
EtEE*
3:
Eta
构造LR
（1）项目集规范族：
状态
项目集
转换函数
0
St.E,#
GO[0,E]=1
Et・EE+,a:
#
GO[0,E]=1
Et・EE*,a:
#
GO[O,E]=1
Et・a,a:
#
GO[O,a]=2
1
StE•,#
ACCEPT
EtE•E+,a:
#
GO[1,E]=3
EtE•E*,a:
#
GO[1,E]=3
Et・EE+,*:
+
GO[1,E]=3
Et・EE*,*:
+
GO[1,E]=3
Et・a,*:
+
GO[1,a]=4
2
Eta•,a:
#
R3
3
EtEE-+,a:
#
GO[3,+]=5
EtEE-*,a:
#
GO[3,*]=6
Ete•E+,*:
+
GO[3,E]=7
Ete•E*,*:
+
GO[3,E]=7
Et.EE+,*:
+
GO[3,E]=7
Et・EE*,*:
+
GO[3,E]=7
Et・a,*:
+
GO[3,a]=4
4
Eta•,*:
+
R3
5
EtEE+・,a:
#
R1
6
EtEE*•,a:
#
R2
7
EtEE-+,*:
+
GO[7,+]=8
EtEE-*,*:
+
GO[7,*]=9
EtE•E+,*:
+
GO[7,E]=7
EtE•E*,*:
+
GO[7,E]=7
Et.EE+,*:
+
GO[7,E]=7
Et・EE*,*:
+
GO[7,E]=7
a,*:
+
G0[7,a]=4
8
EE+・,*:
+
R1
9
E~ee*•,*:
+
R2
（2）构造LR
（1）分析表
状态
ACTION
GOTO
+
*
a
#
E
0
S2
1
1
S4
ACCEPT
3
2
R3
R3
3
S5
S6
S4
7
4
R3
R3
5
R1
R1
6
R2
R2
7
S8
S9
S4
7
8
R1
R1
9
R2
R2
（3）构造LALR⑴项目集规范族
状态
项目集
转换函数
0
S»E,#
E»EE+,a:
#
E»EE*,a:
#
a,a:
#
GO[0,E]=1
GO[0,E]=1
GO[0,E]=1
GO[0,a]=2
1
StE•,#
E~E-E+,a:
#Ete-E*,a:
#Et-ee+,*:
+Et-EE*,*:
+Et-a,*:
+
ACCEPT
GO[1,E]=3
GO[1,E]=3
GO[1,E]=3
GO[1,E]=3
GO[1,a]=2
2
Eta-,a:
#:
*:
+
R3
3
EtEE-+,a:
#:
*:
+
EtEE-*,a:
#:
*:
+Ete-E+,*:
+
EtE-E*,*:
+
Et-EE+,*:
+Et-ee*,*:
+
Et-a,*:
+
GO[3,+]=4
GO[3,*]=5
GO[3,E]=3
GO[3,E]=3
GO[3,E]=3
GO[3,E]=3
GO[3,a]=2
4
EtEE+-,a:
#:
*:
+
R1
5
Etee*-,a:
#:
*:
+
R2
（4）构造LALR
（1）分析表。
状态
ACTION
GOTO
+
*
a
#
E
0
S2
1
1
S2
ACCEPT
3
2
R3
R3
R3
R3
3
S4
S5
S2
3
4
R1
R1
R1
R1
5
R2
R2
R2
R2
（5）对输入符号串“aa*a+”进行LR
（1）分析:
步骤
状态栈
符号栈
输入串
ACTION
GOTO
1
0
#
aa*a+#
S2
2
02
#a
a*a+#
R3
1
3
01
#E
a*a+#
S4
4
014
#Ea
*a+#
R3
3
5
013
#EE
*a+#
S6
6
0136
#EE*
a+#
R2
1
7
01
#E
a+#
S4
8
014
#Ea
+#
R3
3
9
013
#EE
+#
S5
10
0135
#EE+
#
R1
1
11
01
#E
#
ACCEP
对输入符号串“aa*a+”进行LALR
（1）分析:
步骤
状态栈
符号栈
输入串
ACTION
GOTO
1
0
#
aa*a+#
S2
2
02
#a
a*a+#
R3
1
3
01
#E
a*a+#
S2
4
012
#Ea
*a+#
R3
3
5
013
#EE
*a+#
S5
6
0135
#EE*
a+#
R2
1
7
01
#E
a+#
S2
8
012
#Ea
+#
R3
3
9
013
#EE
+#
S4
10
0134
#EE+
#
R1
1
11
01
#E
#
ACCEP'
5.5说明以下的文法是LR
（1）文法，但不是LALR
（1）文法。
StaAd|bBd|aBe|bAe
c
Btc
解：
拓广文法：
0:
S'ts
1:
StaAd2：
StbBd3:
StaBe4:
StbAe
5:
Atc
6:
Btc
4
S10
5
S11
6
R5
R6
7
S12
8
S13
9
R6
R5
10
R1
11
R3
12
R2
13
R4
同核项目集合并，构造LALR
（1）项目集规范族:
状态
项目集
转换函数
0
S'fS,#aAd,#S»bBd,#aBe,#S»bAe,#
GO[0,S]=1
GO[0,a]=2
GO[0,b]=3
GO[0,a]=2
GO[0,b]=3
1
S'tS-,#
ACCEPT
2
Sta•Ad,#
S^a•Be，#c,dc,e
GO[2,A]=4
GO[2,B]=5
GO[2,c]=6
GO[2,c]=6
3
Stb•Bd,#Stb•Ae,#At・c,eBt・c,d
GO[3,B]=7
GO[3,A]=8
GO[3,c]=6
GO[3,c]=6
4
StaA-d,#
GO[4,d]=9
5
StaB•e,#
GO[5,e]=10
6
Atc•,d:
e
Btc•,d:
e
R5
R6
7
StbB•d,#
GO[7,d]=11
8
StbA-e,#
GO[8,e]=12
9
StaAd-,#
R1
10
StaBe•,#
R3
11
StbBd-,#
R2
12
StbAe-,#
R4
构造LALR⑴分析表:
状态
ACTION
GOTO
a
b
c
d
e
#
S
A
B
0
S2
S3
1
1
ACCEPT
2
S6
4
5
3
S9
8
7
4
S10
5
S11
6
R5/R6
R5/R6
7
S12
8
S13
9
R1
10
R3
11
R2
12
R4
从LR
（1）分析表可以看出，分析表无重定义，因此该文法是LR
（1）文法。
从LALR⑴分析表可以看出，分析表ACTI0N[6,d]和ACTI0N[6,e]存在重定义，因此该文法不是LALR⑴文法。
升级会员 