编译原理 第5章 习题与答案2.doc

第五章 习题
5-1 设有文法G[S]：
S→A/ A→aA∣AS∣/
(1) 找出部分符号序偶间的简单优先关系。
(2) 验证G[S]不是简单优先文法。

5-2 对于算符文法G[S]：
S→E E→E-T∣T T→T*F∣F F→-P∣P P→(E)∣i
(1) 找出部分终结符号序偶间的算符优先关系。
(2) 验证G[S]不是算符优先文法。

5-3 设有文法G′[E]：
E→E1 E1→E1+T1|T1 T1→T T→T*F|F F→(E)|i
其相应的简单优先矩阵如题图5-3所示，试给出对符号串（i+i）进行简单优先分析的过程。

题图5-3 文法G′[E]的简单优先矩阵

5-4 设有文法G[E]：
E→E+T|T
T→T*F|F
F→(E)|i
其相应的算符优先矩阵如题图5-4所示。试给出对符号串（i+i）进行算符优先分析的过程。

(
i
*
+
)
#
(

i

*

+

)

#

题图5-4 文法G[E]的算符优先矩阵

5-5 对于下列的文法，试分别构造识别其全部可归前缀的DFA和LR(0)分析表，并判断哪些是LR(0)文法。
(1) S→aSb∣aSc∣ab
(2) S→aSSb∣aSSS∣c
(3) S→A A→Ab∣a

5-6 下列文法是否是SLR(1)文法？若是，构造相应的SLR(1)分析表，若不是，则阐明其理由。
(1) S→Sab∣bR R→S∣a
(2) S→aSAB∣BA A→aA∣B B→b
(3) S→aA∣bB A→cAd∣ε B→cBdd∣ε

5-7 对如下的文法分别构造LR(0)及SLR(1)分析表，并比较两者的异同。
S→cAd∣b A→ASc∣a

5-8 对于文法G[S]:
S→A A→BA∣ε B→aB∣b
(1) 构造LR(1)分析表；
(2) 给出用LR(1)分析表对输入符号串abab的分析过程。

5-9 对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法。
(1) S→A A→AB∣ε B→aB∣b
(2) S→aSa∣a

第5章 习题答案2
5-1 解：
(1) 由文法的产生式和如答案图5-1(a)所示的句型A／／a／的语法树，可得G中的部分优先关系如答案图5-1(b)所示。

(2) 由答案图5-1(b)可知，在符号A和/之间，即存在等于关系，又存在低于关系，故文法G[S]不是简单优先文法。

5-2 解：
(1) 由文法G[S]的产生式可直接看出：
（ ）
此外，再考察句型－P－－(E)和i*(T*F)的语法树 (见答案图5-2(a)及(b))。
由答案图5-2(a)可得：
－ － , － － , － (
由答案图5-2(b)可得：
i * , * ( , ( * , * ）
(2) 由答案图5-2(a)可知，在终结符号－和－之间，存在两种算符优先关系：
－ － , － －
故文法G[S]不是算符优先文法。

5-3 解：对符号串(i+i)进行简单优先分析的过程如答案表5-3所示。
因为分析成功，所以符号串(i+i)是文法G′[E]的合法句子。

答案表5-3 符号串(i+i)的简单优先分析过程
步骤
分析栈
关系
当前
符号
余留
输入串
句柄
所用
产生式
0
#
低于
（
i+i)#

1
#(
低于
i
+i)#

2
#(i
优于
+
i)#
i
F→i
3
#(F
优于
+
i)#
F
T→F
4
#(T
优于
+
i)#
T
T1→T
5
#(T1
优于
+
i)#
T1
E1→T1
6
#(E1
等于
+
i)#

7
#(E1+
低于
i
)#

8
#(E1+i
优于
)
#
i
F→i
9
#(E1+F
优于
)
#
F
T→F
10
#(E1+T
优于
)
#
T
T1→T
11
#(E1+T1
优于
)
#
E1+T1
E1→E1+T1
12
#(E1
优于
)
#
E1
E→E1
13
#(E
等于
)
#

14
#(E)
优于
#

(E)
F→(E)
15
#F
优于
#

F
T→F
16
#T
优于
#

T
T1→T
17
#T1
优于
#

T1
E1→T1
18
#E1
优于
#

E1
E→E1
19
#E
优于
#

分析
成功

5-4 解：对符号串(i+i)进行算符优先分析的过程如答案表5-4所示。
因为分析成功，所以符号串(i+i)是文法G[E]的合法句子。
句子(i+i)及其分析过程中所得句型的语法树如答案图5-4所示。

答案表5-4 符号串（i+i)的算符优先分析过程
步骤
分析栈
当前栈顶
终结符号
优先
关系
当前输
入符号
余留
输入串
最左
素短语
0
#
#

（
i+i)#

1
#(
（

i
+i)#

2
#(i
i

+
i)#
i
3
#(F
(

+
i)#

4
#(F+
+

i
)#

5
#(F+i
i

)
#
i
6
#(F+F
+

)
#
F+F
7
#(E
(

)
#

8
#(E)
)

#

(E)
9
#F
#

#

分析
成功

5-5 解：
(1) 在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：
0.S′→S 2.S→aSc
1.S→aSb 3.S→ab
识别文法G[S]全部可归前缀的DFA如答案图5-5-(1)所示。

因为文法G[S]的每个LR(0)项目集中都不含冲突项目，所以文法G[S]是LR(0)文法，故可构造出不含冲突动作的LR(0)分析表如答案表5-5-(1)所示。

答案表5-5-(1) 文法G[S]的LR(0)分析表
状态
ACTION
GOTO
a
b
c
#
S
0
1
2
3
4
5
6
s2

s2

r3
r1
r2

s4
s5
r3
r1
r2

s6
r3
r1
r2

acc

r3
r1
r2
1

3

(2) 在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：
0.S′→S 2.S→aSSS
1.S→aSSb 3.S→c
识别文法G[S]全部可归前缀的DFA如答案图5-5-(2)所示。

因为文法G[S]的每个LR(0)项目集中都不含冲突项目，所以文法G[S]是LR(0)文法，故可构造出不含冲突动作的LR(0)分析表如答案表5-5-(2)所示。

答案表5-5-(2) 文法G[S]的LR(0)分析表
状态
ACTION
GOTO
a
b
c
#
S
0
1
2
3
4
5
6
7
s2

s2
r3
s2
s2
r1
r2

r3

r1
r2
s3

s3
r3
s3
s3
r1
r2

acc

r3

r1
r2
1

4

5
7

(3) 在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：
0.S′→S 2.A→Ab
1.S→A 3.A→a
识别文法G[S]全部可归前缀的DFA如答案图5-5-(3)所示。

因为在LR(0)项目集I2中含有移进-归约冲突项目，所以文法G[S]不是LR(0)文法，故构造出的LR(0)分析表中含有冲突动作。文法G[S]的LR(0)分析表如答案表5-5-(3)所示。

答案表5-5-(3) 文法G[S]的LR(0)分析表
状态
ACTION
GOTO
a
b
#
S
A
0
1
2
3
4
s3

r1
r3
r2

s4 ,r1
r3
r2

acc
r1
r3
r2
1

2

5-6 解：
(1) 在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：
0.S′→S 3.R→S
1.S→Sab 4.R→a
2. S→bR
识别文法G[S]全部可归前缀的DFA如答案图5-6-(1)所示。

由答案图5-6-(1)可知，在项目集I1 和I4中都存在“移进-归约”冲突。在项目集I4 ={ R→S·, S→S·ab }中, 由于FOLLOR(R)={a}，FOLLOR(R)∩{a}={a}≠Æ，所以其项目集的“移进-归约”冲突不可能通过SLR(1)规则得到解决，从而该文法不是SLR(1)文法。

(2) 在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：
0.S′→S 3.A→aA
1.S→aSAB 4.A→B
2.S→BA 5.B→b
识别文法G[S]全部可归前缀的DFA如答案图5-6-(2)所示。

答案图5-6-(2) 识别G[S]全部可归前缀的DFA

因为文法G[S]的每个LR(0)项目集中都不含冲突项目，所以文法G[S]是LR(0)文法，故也是SLR(1)文法。
因为FOLLOW(S)={a,b,#}, FOLLOW(A)={a,b,#}, FOLLOW(B)={a,b,#}, 所以文法G[S]的SLR(1)分析表如答案表5-6-(2)所示。

答案表5-6-(2) 文法G[S]的SLR(1)分析表
状态
ACTION
GOTO
a
b
#
S
A
B
0
1
2
3
4
5
6
7
8
9
10
11
s2

s2
s7
r5
s7
r2
s7
r4

r1
r3
s4

s4
s4
r5
s4
r2
s4
r4
s4
r1
r3

acc

r5

r2

r4

r1
r3
1

5

6

9

11

3

3
8

8

8

10

(3) 在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：
0.S′→S 4.A→ε
1.S→aA 5.B→cBdd
2.S→bB 6.B→ε
3. A→cAd
识别文法G[S]全部可归前缀的DFA如答案图5-6-(3)所示。

由答案图5-6-(3)可知，在项目集I2 ,I3 ,I5 和I9中都存在“移进-归约”冲突。
因为在项目集I2 和I5中, 由于FOLLOR(A)={d,#}，FOLLOR(A)∩{c}=Æ，所以其项目集的“移进-归约”冲突能通过SLR(1)规则得到解决；
又因为在项目集I3 和I9中, 由于FOLLOR(B)={d,#}，FOLLOR(B)∩{c}=Æ，所以其项目集的“移进-归约”冲突也能通过SLR(1)规则得到解决；所以文法G[S]是SLR(1)文法。
因为FOLLOR(S)={#}，FOLLOR(A)={d,#}，FOLLOR(B)={d,#}，所以文法G[S]的SLR(1)分析表如答案表5-6-(3)所示。

答案表5-6-(3) 文法G[S]的SLR(1)分析表
状态
ACTION
GOTO
a
b
c
d
#
S
A
B
0
1
2
3
4
5
6
7
8
9
10
11
12
s2

s3

s5
s9

s5

s9

r4
r6

r4
s7
r3

r6
s11
s12
r5

acc
r4
r6
r1
r4

r3
r2
r6

r5
1

4

6

8

10

5-7 解：在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：
0.S′→S 3.A→ASc
1.S→cAd 4.A→a
2.S→b
识别文法G[S]全部可归前缀的DFA如答案图5-7所示。

因为文法G[S]的每个LR(0)项目集中都不含冲突项目，所以文法G[S]是LR(0)文法。
文法G[S]的LR(0)分析表如答案表5-7-(a)所示。

答案表5-7-(a) 文法G[S]的LR(0)分析表
状态
ACTION
GOTO
a
b
c
d
#
S
A
0
1
2
3
4
5
6
7
8

s4
r2
r4

r1

r3
s3

r2
r4
s3
r1

r3
s2

r2
r4
s2
r1
s8
r3

r2
r4
s6
r1

r3

acc

r2
r4

r1

r3
1

7

5

因为FOLLOR(S)={#,c}，FOLLOR(A)={b,c,d}，所以文法G[S]的SLR(1)分析表如答案表5-7-(b)所示。

答案表5-7-(b) 文法G[S]的SLR(1)分析表
状态
ACTION
GOTO
a
b
c
d
#
S
A
0
1
2
3
4
5
6
7
8

s4

s3

r4
s3

r3
s2

r2
r4
s2
r1
s8
r3

r4
s6

r3

acc

r2

r1

1

7

5

两个表的相同之处为：
(1) 两个表的GOTO表部分完全相同。
(2) 在两个表的ACTION表中，不含归约项目的项目集对应的行的元素完全相同，即第0,2,5,7行完全相同。
两个表的不同之处为：
在两个表的ACTION表中，含有归约项目的项目集对应的行的元素不同，即第3,4,6,8行的元素不同。以第3行为例，答案表5-7-(a)中的所有元素都为r2 ；而在答案表5-7-(b)中 , 因为FOLLOR(S)={#,c}，故仅在“#”和“c”列对应的元素为r2 。

5-8 解：
(1) 在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：
0.S′→S 3.A→ε
1.S→A 4.B→aB
2.A→BA 5.B→b
文法G[S]的LR(1)项目集及DFA如答案图5-8所示。

文法G[S]的LR(1)分析表如答案表5-8-(1)所示。

答案表5-8-(1) 文法G[S]的LR(1)分析表
状态
ACTION
GOTO
a
b
#
S
A
B
0
1
2
3
4
5
6
7
s4

s4
s4
r5

r4
s5

s5
s5
r5

r4
r3
acc
r1
r3

r5
r2
r4
1

2

6

3

3
7

(2) 用LR(1)分析表对输入符号串abab的分析过程如答案表5-8-(2)所示。因为分析成功，所以符号串abab是文法G[S]的合法句子。

答案表5-8-(2) 符号串abab的LR分析过程
步骤
状态栈
符号栈
余留输入串
分析动作
下一状态
1
I0
#
abab#
s4
4
2
I0I4
#a
bab#
s5
5
3
I0I4I5
#ab
ab#
r5
GOTO[I4 ,B]=7
4
I0I4I7
#aB
ab#
r4
GOTO[I0 ,B]=3
5
I0I3
#B
ab#
s4
4
6
I0I3I4
#Ba
b#
s5
5
7
I0I3I4I5
#Bab
#
r5
GOTO[I4 ,B]=7
8
I0I3I4I7
#BaB
#
r4
GOTO[I3 ,B]=3
9
I0I3I3
#BB
#
r3
GOTO[I3 ,A]=6
10
I0I3I3I6
#BBA
#
r2
GOTO[I3 ,A]=6
11
I0I3I6
#BA
#
r2
GOTO[I0 ,A]=2
12
I0I2
#A
#
r1
GOTO[I0 ,S]=1
13
I0I1
#S
#
acc

5-9 解：
(1) 在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：
0.S′→S 3.A→ε
1.S→A 4.B→aB
2.A→AB 5.B→b
文法G[S]的LR(1)项目集及DFA如答案图5-9-(1)所示。

文法G[S]的LR(1)分析表如答案表5-9-(1)所示。因为分析表中不含多重定义的元素，所以文法G[S]是LR(1)文法。

答案表5-9-(1) 文法G[S]的LR(1)分析表
状态
ACTION
GOTO
a
b
#
S
A
B
0
1
2
3
4
5
6
r3

s5
r2
r5
s5
r4
r3

s4
r2
r5
s4
r4
r3
acc
r1
r2
r5

r4
1

2

3

6

(2) 在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：
0.S′→S
1.S→aSa
2.S→a
文法G[S]的LR(1)项目集及DFA如答案图5-9-(2)所示。

文法G[S]的LR(1)分析表如答案表5-9-(2)所示。因为分析表中含有多重定义的元素ACTION[I5 ,a]= r2 ,s5 ，所以文法G[S]不是LR(1)文法。

答案表5-9-(2) 文法G[S]的LR(1)分析表
状态
ACTION
GOTO
a
#
S
0
1
2
3
4
5
6
7
s2

s5
s4

r2 ,s5
s7
r1

acc
r2

r1

1

3

6