编译原理课后答案.doc

第二章 高级语言及其语法描述
4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：
（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。
（2） 优先顺序为↑，+，*，同级优先采用右结合。
解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16
（2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=4

6．令文法G6为 N→D|ND
D→0|1|2|3|4|5|6|7|8|9
（1） G6 的语言L（G6）是什么？
（2） 给出句子0127、34和568的最左推导和最右推导。
解：（1）L（G6）=｛a|a∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝
（2）N ＝＞ND＝＞ NDD＝＞ NDDD＝＞ DDDD＝＞ 0DDD＝＞ 01DD＝＞ 012D＝＞ 0127
N＝＞ ND＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127
N＝＞ ND＝＞ DD＝＞ 3D＝＞ 34
N＝＞ ND＝＞ N4＝＞ D4 ＝＞34
N＝＞ ND＝＞ NDD＝＞ DDD＝＞ 5DD＝＞ 56D＝＞ 568
N＝＞ ND＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 568

7．写一个文法，使其语言是奇数集，且每个奇数不以0开头。
解：A→SN, S→+|-|∑, N→D|MD
D→1|3|5|7|9, M→MB|1|2|3|4|5|6|7|8|9 B→0|1|2|3|4|5|6|7|8|9
8. 文法：

最左推导:

最右推导:

语法树：/********************************

*****************/

9．证明下面的文法是二义的：
S→ iSeS|iS|I
解：因为iiiiei有两种最左推导，所以此文法是二义的。

10．把下面文法改写为无二义的：
S→SS|(S)|()
解：S→ ST|T, T→ (S)|()

11．给出下面语言的相应文法
L1=｛anbnci|n≥1,i≥0｝
L2=｛aibncn|n≥1,i≥0｝
L3=｛anbnambm|n,m≥0｝
L4=｛1n0m1m0n|n,m≥0｝
解：（1）S→ AB|A
A→ aAb|ab
B→ c|cB
(2) S→ AB|B
A→ a|aA
B→ bBc|bc
(3) S→ AB|A|B|∑
A→ aAb|ab
B→ aBb|ab
(4) S→ 1S0|0A1
A→ 0A1|01

第三章 词法分析
7.构造下列正规式的相应的DFA
1(0|1)*101
1(1010*|1(010)*1)*0
0*10*10*10*
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
解答：
（1）1(0|1)*101

I I0 I1
{X} Ф {A,B,C}
{A,B,C} { B,C} { B,C,D}
{B,C} { B,C} { B,C,D}
{B,C,D} { B,C,E} { B,C,D}
{B,C,E} { B,C} {B,C,D,y}
{B,C,D,y} {B,C,E} { B,C,D}

S 0 1
A B
B C D
C C D
D E D
E C F
F E D

(2) 1(1010*|1(010)*1)*0

I I0 I1
{X} Ф {A,B,C}
{A,B,C} {y} {D,H,I,L}
{y} Ф Ф
{D,H,I,L} {E,J} {B,C}
{E,J} Ф {B,C,F,G,K}
{B,C} {y} {D,H,I,L}
{B,C,F,G,K} {B,C,G,I,L,y} {D,H,I,L}
{B,C,G,I,L,y} {B,C,G,J,y} {B,C,D,H,I,L }
{B,C,G,J,y} {B,C,G, y} {D,H,I,L}
{D,H,I,K,L} {E,I,J,L} {B,C}
{E,J,y} Ф {B,C,F,G,K }
{E,I,J,L} {J} {B,C,F,G,K }
{J} Ф {K}
{K} {I,L} Ф
{I,L} {J} {BC}

8.给出下面正规表达式
（1） 以01结尾的二进制数串
（2） 能被5整除的十进制整数
（3） 包含奇数个1或者奇数个0的二进制数串
（4） 英文字母组成的所有符号串，要求符号串中的字母按照字典序排列。
（7）不包含子串abb的由a和b组成的符号串的全体。
解答：
（1） （0|1）*01
（2） (1|2|…|9)(0|1|2|…|9)*(0|5)|0|5
（3） 0*1(0*10*10*)*
（4） A*B*…Z*
(7) b*(a|ab)*
9.对下面的情况给出DFA以及正规表达式。
（1）{0，1}上的含有子串010的所有串。
（2）{0，1}上不含子串010的所有串。
解答：
（1）（0|1）*010（0|1）*
（2）1*(0|1*|1)*1*

12 将图3.8的（a）和(b)分别确定化和最少化。

解：1 确定化
a b
｛0｝ ｛0,1｝ ｛1｝
｛0,1｝ ｛0,1｝ ｛1｝
｛1｝ ｛0｝ __
令A=｛0｝ B=｛0，1｝ C=｛1｝
则状态转换图为：

2 最少化
首先，所有状态可分为 终态集{A B} 非终态集{C}
其次，考察{A B}，由于{A B}由a到{B}由b到{C}，所以不可分，令A={A B}
则最少化后的状态转换图为：

14 构造一个DFA，它接受∑＝｛0,1｝上所有满足下列条件的字符串，每个1都有0直接跟在右边。
解：1 正规式为： （0|10）﹡
2 由正规式转化为NFA：

3 由NFA到DFA：
0 1
{X} {X} {b}
{b} {X} __
令A={X} B={b}
则状态转换图为：

4 最少化
终态集{A} 非终态集{B}
显然不可再划分，则最简的DFA即为：

15 给定右线性文法G：
S→0S|1S|1A|0B
A→1C|1
B→0C|0
C→0C|1C|1|0
求出一个与G等价的左线性文法。

解：1 由右线性文法构造NFA：

2 从NFA中构造左线性文法：
F→A1|B0|C0|C1
A→S1|1
B→S0|0
C→C0|C1|A1|B0
S→S0|S1|1|0
第四章 语法分析－自上而下分析
1. 考虑下面文法 G1:
S→a|∧|(T)
T→T,S|S
(1) 消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。
(2) 经过改写的文法是否是LL（1）的？给出它的预测分析表。
解答：

（1） 消去G1的左递归：S→a|∧|(T)
T→ST’
T’ →,ST’|ε
递归子程序：
PROCEDURE S;
IF sym=’a’ THEN ADVANCE
ELSE IF sym=’ ∧’ THEN ADVANCE
ELSE IF sym=’ (’ THEN
BEGIN
ADVANCE
T;
IF sym=’ )’ THEN ADVANCE
ELSE ERROR
END
ELSE ERROR;

PROCEDURE T;
BEGIN
S;T’
END;

PROCEDURE S;
IF sym=’ ,’ THEN
BEGIN
ADVANCE
S;T’
END;

（2） 是LL（1）文法。
FIRST(S)={ a,∧,( } FIRST(T)={ a,∧,( } FIRST(T’)={ ,,ε }
FOLLOW(S)={ #, , , ε, ) } FOLLOW(T)={ ) } FOLLOW(T’)={ ) }

预测分析表如下：

a
,
∧
(
）
#
S
S→a

S→∧
S→ (T)

T
T→ST’

T→ST’
T→ST’

T’

T’ →,ST’

T’ →ε

2.文法：

(1)
FIRST(E)={(,a,b,^}
FIRST(E')={+,ε}
FIRST(T)={(,a,b,^}
FIRST(T')={(,a,b,^,ε}

FIRST(F)={(,a,b,^}
FIRST(F')={*,ε}
FIRST(P)={(,a,b,^}
FOLLOW(E)={#,)}
FOLLOW(E')={#,)}
FOLLOW(T)={+,),#}
FOLLOW(T')={+,),#}
FOLLOW(F)={(,a,b,^,+,),#}
FOLLOW(F')={(,a,b,^,+,),#}
FOLLOW(P)={*,(,a,b,^,+,),#}
(2)
考虑下列产生式:

FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ
FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ
FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ
FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ
FIRST(*F')∩FIRST(ε)={*}∩{ε}=φ
FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ
FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ
所以,该文法式LL(1)文法.
(3)

+
*
(
)
a
b
^
#
E

E'

T

T'

F

F'

P

(4)
procedure E;
begin
if sym='(' or sym='a' or sym='b' or sym='^'
then begin T; E' end
else error
end
procedure E';
begin
if sym='+'
then begin advance; E end
else if sym<>')' and sym<>'#' then error
end
procedure T;
begin
if sym='(' or sym='a' or sym='b' or sym='^'
then begin F; T' end
else error
end
procedure T';
begin
if sym='(' or sym='a' or sym='b' or sym='^'
then T
else if sym='*' then error
end
procedure F;
begin
if sym='(' or sym='a' or sym='b' or sym='^'
then begin P; F' end
else error
end
procedure F';
begin
if sym='*'
then begin advance; F' end
end
procedure P;
begin
if sym='a' or sym='b' or sym='^'
then advance
else if sym='(' then
begin
advance; E;
if sym=')' then advance
else error
end
else error
end;

3.下面文法那些是LL（1）文法？

（1）S →Abc A →a|ε B→b|ε

没有左递归且FIRST 候选集不冲突且

FIRST(A)∩FOLLOW(A)={ a, ε} ∩ { b }=Ф
FIRST(B)∩FOLLOW(B)={ b, ε} ∩ { c }=Ф
所以该文法为LL（1）文法

（2）S →Ab A →a|B|ε B→b|ε

FIRST(B)＝{ b, ε} ∩ FIRST(ε) ={ε} ≠Ф
所以该文法不是LL（1）文法

（3）S →ABBA A →a |ε B→b|ε

没有左递归且FIRST 候选集不冲突
FIRST(A)∩FOLLOW(A)={ a, ε} ∩{b,#} =Ф
FIRST(B)∩FOLLOW(B)={ b, ε}∩{b,a,#} ≠Ф
所以该文法不是LL（1）文法

(4) S →aSe|B B →bBe |C C→cCe|d

没有左递归且FIRST 候选集不冲突
所以该文法为LL（1）文法

4.Expr→_Expr
Expr→(Expr)| Var ExprTail
ExprTail→_ Expr|ε
Var→id VarTail
VarTail→(Expr)| ε
（1） 构造LL（1）分析表
（2） 给出对句子id_ _id((id)) 的分析过程

解答：（1）FIRST(Expr)={_ , ( , id } FIRST(ExprTail)={_ , ε } FIRST(Var)={id} FIRST(VarTail)={ ( , ε}
FOLLOW(Expr)={# , ) } FOLLOW(ExprTail) ={# , ) }
FOLLOW(Var) {_ , # , ) } FOLLOW(VarTail) ={_ , # , ) }

预测分析表如下：

—
id
(
）
#
Expr
Expr→_Expr
Expr→Var ExprTail

Expr→(Expr)

ExprTail
ExprTail→_ Expr

ExprTail→ε
ExprTail→ε
Var

Var→id VarTail

VarTail
VarTail→ε

VarTail→(Expr)
VarTail→ε

(3) 对句子id_ id)) 的分析过程：

步骤 符号栈 输入串 所用产生式
0 ＃Expr id_ _id((id))＃
1 # ExprTail Var id_ _id((id))＃ Expr→Var ExprTail
2 # ExprTail VarTail id id_ _id((id))＃ Var→id VarTail

3 # ExprTail VarTail _ _id((id))＃

4 # ExprTail _ _id((id))＃ VarTail→ε

5 # Expr_ _ _id((id))＃ ExprTail→_ Expr

6 # Expr _id((id))＃
7 # Expr_ _id((id))＃ Expr→_Expr
8 # Expr id((id))＃
9 # ExprTail Var id((id))＃ Expr→Var ExprTail

10 # ExprTail VarTail id id((id))＃ Var→id VarTail
11 # ExprTail VarTail ((id))＃
12 # ExprTail )Expr( ((id))＃ VarTail→(Expr)
13 ExprTail )Expr (id))＃
14 # ExprTail ) )Expr( (id))＃ Expr→(Expr)
15 # ExprTail ) )Expr id))＃
16 # ExprTail ) )
ExprTail Var id))＃ Expr→Var ExprTail
17 # ExprTail ) )
ExprTail VarTail id id))＃ Var→id VarTail

18 # ExprTail ) )
ExprTail VarTail ))＃
19 # ExprTail ) )
ExprTail ))＃ VarTail→ε
20 # ExprTail ) ) ))＃ ExprTail→ε

21 # ExprTail ) )＃

22 # ExprTail # ExprTail→ε
23 # # 分析成功

第五章

1.
短语: E+T*F, T*F,
直接短语: T*F
句柄: T*F

2 （1）(a, ( a, a ) ) 的最左推导：S => ( T ) =>( T,S ) => ( S,S ) =>(a,S ) =>( a,( T ) ) => ( a,( T,S ) ) > ( a,(S,S ) ) => ( a,( a ,S ) ) => ( a,( a ,a ) )

最右推导：S => ( T ) =>( T,S ) => ( T, (T) ) =>( T, (T, S) ) =>( T, (T, a) ) =>( T, (S, a) ) => ( T,(S, a ) ) => ( T,( a ,a ) ) => (S,( a ,a ) ) => ( a,( a ,a ) )

(((a, a),^,(a)),a) 的最左推导：：S => ( T ) =>( T,S ) => ( S,S ) =>( ( T ) ,S ) => (( T,S )S ) => (( T,S，S ),S ) =>(( S,S，S ),S ) =>(( ( T ),S，S ),S ) =>(( ( T,S ),S，S ),S ) =>(( ( S,S ),S，S ),S ) =>(( ( a, S ),S，S ),S ) =>(( ( a, a ),S，S ),S ) =>(( ( a ,a ),^，S ),S ) =>(( ( a ,a ),^ ，a ),S ) =>(( ( a ,a ),^ ，a ),a )

最右推导：S => ( T ) =>( T,S ) =>( T, a ) =>( S ,a ) =>( (T) , a ) =>( (T S) , a ) =>( (T, ( T )) , a ) =>( (T, ( a )) , a ) =>( (T, S, ( a )) , a ) =>( (T, ^, ( a )) , a ) =>( (S, ^, ( a )) , a ) =>( ((T), ^, ( a )) , a ) =>( ((T,S), ^, ( a )) , a ) =>( ((T ,a), ^, ( a )) , a ) =>( ((S ,a), ^, ( a )) , a ) =>( ((a ,a), ^, ( a )) , a )
(2) (((a, a),^,(a)),a)的规范规约及每一步的句柄为：
(((a, a),^,(a)),a) a
( ((S ,a), ^, ( a )) , a ) S
( ((T ,a), ^, ( a )) , a ) a
( ((T,S), ^, ( a )) , a ) T,S
( ((T), ^, ( a )) , a ) (T)
( (S, ^, ( a )) , a ) S
( (T, ^, ( a )) , a ) ^
( (T, S, ( a )) , a ) T,S
( (T, ( a )) , a ) a
((T,(S)),a) S
( (T, ( T )) , a ) (T)
( (T, S) , a ) T,S
( (T) , a ) (T)
( S ,a ) S
( T, a ) a
( T,S ) T,S
( T ) (T)
S

步骤 符号栈 输入串 动作
0 # (((a, a),^,(a)),a)# 预备
1 #( ((a, a),^,(a)),a)# 进
2 #(( (a, a),^,(a)),a)# 进
3 #((( a, a),^,(a)),a)# 进
4 #(((a , a),^,(a)),a)# 进
5 #(((S , a),^,(a)),a)# 规约 S→a
6 #(((T , a),^,(a)),a)# 规约T→S
7 #(((T, a),^,(a)),a)# 进
8 #(((T, a ),^,(a)),a)# 进
9 #(((T,S ),^,(a)),a)# 规约 S→a
10 #(((T ),^,(a)),a)# 规约T→T,S
11 #(((T) ,^,(a)),a)# 进
12 #((S ,^,(a)),a)# 规约S→(T)
13 #((T ,^,(a)),a)# 规约TS
14 #((T, ^,(a)),a)# 进
15 #((T,^ ,(a)),a)# 进
16 #((T,S ,(a)),a)# 规约S→^
17 #((T ,(a)),a)# 规约T→T,S
18 #((T, (a)),a)# 进
19 #((T,( a)),a)# 进
20 #((T,(a )),a)# 进
21 #((T,(S )),a)# 规约S→a
22 #((T,(T )),a)# 规约T→S
23 #((T,(T) ),a)# 进
24 #((T,S ),a)# 规约S→(T)
25 #((T ),a)# 规约T→T,S
26 #((T) ,a)# 进
27 #(S ,a)# 规约S→(T)
28 #(T a)# 规约T→S
29 #(T, a)# 进
30 #(T, a )# 进
31 #(T, S )# 规约S→a
32 #(T )# 规约T→T,S
33 #(T) # 进
34 #S # 规约S→(T)
35 #S # 接受
语法树：
S 17

( T ) 16

14 T , S 15

S 13 a

( T ) 12

（ T ）

8 T , S 11

6 T , S 7 ( T ) 10

S 5 ^ S 9

( T ) 4 a

2 T , S 3

S a

1 a
其中的编号指示的结点为每一步规约所形成的语法树的根结点。

3（1） FIRSTVT(S)={a,^,(}
FIRSTVT(T)={,,a,^,(}
LASTVT(S)={a,^,)}
LASTVT(T)={,,a,^,)}
(2)

a
^
(
)
,
a

>
>
^

>
>
(
<
<
<
=
<
)

>
>
,
<
<
<
>
>

是算符文法，并且是算符优先文法

(3)优先函数

a
^
(
)
,
f
4
4
2
4
4
g
5
5
5
2
3
也可以最后指定f (#) ,g (#) 的值。

（4）算符优先分析过程。
步骤 符号栈 输入串 动作
0 # (a,(a ,a))# 预备
1 #( a,(a ,a))# 进
2 #(a ,a ,a))# 进
3 #(S ,(a ,a))# 规约S→a
4 #(S, (a ,a))# 进
5 #(S,( a ,a))# 进
6 #(S,(a ,a))# 进
7 #(S,(S ,a))# 规约S→a
8 #(S,(S, a))# 进
9 #(S,(S,a ))# 进
10 #(S,(S,S ))# 规约S→a
11 #(S,(T ))# 规约T→T,S
12 #(S,(T) )# 进
13 #(S,S )# 规约S→(T)
14 #(T )# 规约T→T,S
15 #(T) # 进
16 #S # 规约S→(T)
17 #S # 接受

5.拓广的文法为：S’→S , S→AS, S→b ,A→SA, A→a,
(1) 所有的 LR(0)项目：
0. 1. 2. 3.
4. 5. 6. 7.
8. 9. 10. 11.
（2）LR(0)项目集规范族：

I0 S’→·S , S→·AS , S→·b , A→·SA , A→·a

I0 S I 1 S’→S· , S→A·S , S→b· , A→S·A, A→a· , A→·SA
A I 2 S→A·S, , S→·AS , S→·b , A→·SA , A→·a
a I 3 A→a·
b I 4 S→b·

I 1 S I 5 A→S·A, A→·SA , A→·a , S→·AS , S→·b
A I 6 A→SA· , S→A·S , S→·AS , S→·b , A→·SA , A→·a,
a (I 3)
b (I 4)

I 2 S I 7 S→AS· , A→S·A, A→·SA , A→·a, S→·AS, S→·b,
A( I 2 )
a (I 3 )
b (I 4 )
I 5 S (I 5) A (I 6) a (I 3) b (I 4)
I 6 S (I 7) A (I 2 ) a (I 3) b (I 4)

I 7 S (I 5) A (I 6) a (I 3) b (I 4)

(3) I 1 中存在移进规约冲突S’→S· ， A→·a ， S→·b 但是FOLLOW(S’)＝{#}
所以该冲突可以消除
I 6中存在移进规约冲突：A→SA· ，S→·b ，A→·a 但是FOLLOW(A)＝{b, a }
所以该冲突不可以消除。
I 7中存在移进规约冲突：S→AS· ，A→·a ，S→·b但是FOLLOW(S)＝{a , b ,# }
所以该冲突不可以消除。 所以该文法不是SLR文法。

（4）
I0 [S’→·S , # ] , [S→·AS , # ] ,[ S→·b , # ], [ A→·SA ,a/b ] ,[ A→·a ,a/b]

I0 S I 1 [ S’→S·,# ] , [S→A·S,a/b] , [S→b·,a/b ] , [A→S·A, a /b ],
[A→a· , a/b] , [ A→·SA, a/b]
A I 2 [S→A·S, #] , [S→·AS , #], [ S→·b , #], [A→·SA ,a/b ],[ A→·a, a/b ]

a I 3 : [ A→a·,a/b],
b I 4 [ S→b·,#]

I 1 S I 5 [A→S·A, a/b ], [A→·SA , a/b ],[ A→·a , a/b ],[ S→·AS , a/b ],
[ S→·b, a/b ]
A I 6 [A→SA·,a/b ], [ S→A·S , a/b ], [ S→·AS , a/b ], [S→·b , a/b ], [A→·SA , a/b ], [A→·a, a/b ]
a (I 3)
b I7 [S→b·, a/b ]

I 2 S I 8 [ S→AS·,#] , [A→S·A, a/b ], [A→·SA ,a/b] , [A→·a, a/b] , [S→·AS, a/b], [ S→·b, a/b]
A I 9 [ S→A·S , #/a/b ], [ S→·AS , #/a/b ] , [S→·b ,#/ a/b ], [A→·SA , a/b ], [A→·a, a/b ]
a (I 3 )
b I 10 [S→b·, #/a/b ]

I 5 S (I 5) A (I 6) a (I 3) b (I 7)

I 6 S I 11 : [ S→AS·, a/b] , [A→S·A, a/b ], [A→·SA , a/b ], [A→·a, a/b ] ,
A I 12 : [ S→A·S , a/b ], [ S→·AS , a/b ], [ S→·b, a/b], [A→·SA , a/b ],
[A→·a, a/b ]
a (I 3)
b (I 7)

I 8 S( I 5 ) A( I 6 ) a( I 3) b( I 7)
I 9 S I 13 : [ S→AS·, #/a/b] , [A→S·A, a/b ], [A→·SA , a/b ], [A→·a, a/b ] ,
[ S→·AS ,a/b ] , [S→·b , a/b ]
A (I 9 )
a (I 3 )
b (I 10 )
I 11 S( I 5 ) A( I 6 ) a( I 3) b( I 7)

I 12 S( I 11 ) A( I 12 ) a( I 3) b( I 7)

I 13 S( I 5 ) A( I 6 ) a( I 3) b( I 7)

I 6, I 11, I 13 中存在移进规约冲突，所以该文法不是LR(1)的和LALR的。

(附上网络版的答案)
(2)
1

9
8
7
S A
S

11
10
0
a