-
编译
原理
课后题答案
第二章
P36-6
(1)
L
(
G
1
)
是
0~9
组成的数字串
(2)
最左推导
:
N
?
ND
?
N
DD
?
NDDD
?
DDDD
?
0
DDD
?
01
DD
?
012
D
?
0127
N
?
ND
?
DD
?
3
D
?
34
N
?
ND
?
NDD
?
DDD
?
5
DD
?
56
D
?
568
最右推导
:
N
?
ND
?
N
7
?
ND
7<
/p>
?
N
27
?
ND
27
?
N
127
?
D
127
?
0127
N
?
ND
?
N
4
?
D
4
?
34
N
?
ND
?
N
8
?
ND
8
?
N
68
?
D
68
?
568
P36-7
G(S)
O
?
1
|
3
|<
/p>
5
|
7
|
9
N
?
2
|
4
|
6
|
8
|
O
D
?
0
|
N
S
?
O
|<
/p>
AO
A
?
AD<
/p>
|
N
P36-8
文法：
E
?
T
|
E
?
T
|
E
?
T
T
?
F
|
T
*
F
< br>|
T
/
F
F
?
(
E
)|
i
最左推导
:
E
?
E
?
T
?
T
?
T
?
F
?
T
?
i
?
T
?
i
< br>?
T
*
F
?
i
?
F
*
F
?
i
?
i
*
F
?
i
?
i
*
i
E
?
T
< br>?
T
*
F
?
F
*
F
?
i
*
F
?
i
*(
E
)
?
i
*(
E
?
T
)
?
i
*(
T
?
T
)
?
i
*(
F
?
T
)
?
i
*(
i
?
T
)
?<
/p>
i
*(
i
?
F
)
?
i
*(
i
?
i
)
最右推导
:
E
?
E
?
T
?
E
?
T
*
F
?
E
?
T
< br>*
i
?
E
?
F
*
i
?
E
?
i
*
i
?
T
?
i
*
i
?
F
?
i
*
< br>i
?
i
?
i
*
i
E
?
T
?
F
*
T
?
F
*
F
?
F
*(
E
)
?
F
*(
E
?
T
< br>)
?
F
*(
E
?
F
)
?
F
*(
E
?
i
)
?
F
*(
T
?
i
)
?
F
*(
F
?
i
)
?
F
*(
i
?
i
)
?
i
*(
i
?
i
)
语法树：
/*********
***********************
E
E
+
T
E
+
T
F
T
F
i
F
i
i
i+i+i
********
*********/
P36-9
句子
iiiei
有两个语法树：
S
S
?
?
iSeS
iS
?
?
iiSeS
iSei
?
?
iiSei
iiSei
?
?
iiiei
iii
ei
P36-10
/**************
S
?
TS
|
T<
/p>
T
?
(
S
)
|
(
)
***************/
P36-11
/***************
L1:
S
?
AC
A
?
aA
b
|
ab
C
?
cC
|
?<
/p>
L2:
E
E<
/p>
+
T
T
T
*
F
F
F
i
i
i
i-i-i
E
E
-
E
-
T
T
F
F
i
i
i+i*i
T
F
i
S
?
AB
A
< br>?
aA
|
?
B
?
bBc
|
bc
L3:
< br>S
?
AB
A
?
aAb
|
?
B
?
aBb
|
?
L4:
S
?
A
|
B
A
?
0
A<
/p>
1
|
?
B
?
1
B
0
|
A
********
*******/
第三章习题参考答案
P64
–
7
(1)
1
(
01
|<
/p>
)
*
101
X
Y
0
1
?
?
1 0
1
X
1
2
3
4
5
1
确定化：
{X}
φ
{1,2,3}
{2,3}
{2,3,4}
{2,3,5}
{2,3,4,Y}
0
φ
φ
{2,3}
{2,3}
{2,3,5}
{2,3}
{2,3,5}
1
{1,2,3}
φ
{2,3,4}
{2,3,4}
{2,3,4}
{2,3,4,Y}
{2,3,4,}
Y
0
1
0
0
2
3
0 0
1 1 0
1
0 1
4
5
6
0
1
1
1
最小化：
{
0
,
1
,
2
,
3
,
4
,
5
},{
6
}
{
0
,
1
,
2
,
3
,
4
< br>,
5
}
0
?
{
1
,
3
,
5
}
{
0
,
1
,
2
,
3
,
4
,
5
}
1
?
{
< br>1
,
2
,
4
,
6
}
{
0
,
1
,
2
,
3
,
4
},{
5
},{
6
}
{
0
,
1
,
2
,
3
,
4
< br>}
?
{
1
,
3
,
5
}
0
{
0
,
1
,
2
,
3
},{
4
},{
5
},{
6
}
{
0
,
1
,
2
,
3
}
0
?
< br>{
1
,
3
}
{
0
,
1
,
2
,
3
}
1
?<
/p>
{
1
,
2
,
4
}
{
0
,
1
},{
2
,
3
}{
4
},{
5
},{
6
}
{
0
,
1
}
?
< br>{
1
}
{
0
,
1
}
?
{
1
,
2
}
0
1<
/p>
{
2
,
3
}
0
?
{
3
}
{
2
,
3
}
1
?
{
4
< br>}
{
0
},{
< br>1
},{
2
,
< br>3
},{
4
},{
5
},{
6
}
0
1
2
0
0 0 1 0
0 1
1
3
4
5
0
1
1
1
P64
–
8
(1)
(
1
|
0
)
*<
/p>
01
(2)
(
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
< br>|
9
)(
0
|
1
|
2
|
3
|
4
|<
/p>
5
|
6
|
7
|
8
|
9
)
*
(
0
|
5
)
|
(
0
|
5
)
(3)
0
*
1
(
0
|
10
*
1
)
*
|
1
*
0
(
0
|
10
*
< br>1
)
*
P64
–
12
(a)
a
a,b
0
a
1
确定化：
{0}
{0,1}
{1}
φ
给状态编号：
0
1
2
3
a
1
1
0
3
b
2
2
3
3
a
{0,1}
{0,1}
{0}
φ
b
{1}
{1}
φ
φ
a
a
0
1
a b b b
b
2
3
a
最小化：
{
0
,
1
},{
2
,
3
}
{<
/p>
0
,
1
}
?
{
1
}
{
0
,
1
}
?
{
2
}
a
b
< br>{
2
,
3
}
?
{
0
,
3
}
{
2
,
3
}<
/p>
?
{
3
}
a
b
{
0
,
1
},{
2
},{
3
}
a
a
b b
1
2
0
a
b
(b)
b b a
2
3
0
a b
a
a
b
b
a
4
5
1
a
a
已经确定化了
< br>,
进行最小化
最小化：
{
{
0
,
1
}<
/p>
,
{
2
,
3
,
4
,
5
}
}
{
0
,
1
}
< br>a
?
{
1
}
{
0
< br>,
1
}
b
?
{
2
,
4
}
{
2
,
3
,
4
,
5
}
a
?
{
1
,
3
< br>,
0
,
5
}
{
2
< br>,
3
,
4
,
5
}
b
?
{
2
,
3
,
4
,
5
}
{
2
,
4
}
a
?
< br>{
1
,
0
}
{
2
,
4
}
b
?
{
3
,
5<
/p>
}
{
3
,
5
}
a
?
{
3
,
5
}
{
3
,
5
}
b
< br>?
{
2
,
4
}
{{
0
,
1
},{
2
,
4
},{
3
,
5
}}
{
0
,
1
}
a
?
{
1
}
{
0
,
1
}
b
?
{
2
,
4
}
{
2
,
< br>4
}
a
?
{
1
,
0
}
{
2
,
4
}
b
?<
/p>
{
3
,
5
}
{
3
,
5
}
a
?
{
3
,
5
}
{
3
< br>,
5
}
b
?
{
2
,
4
}
b b a
1
2
0
a b
a
P64
–
14
(1) 0
1
0
0
(2):
(
010
|
)
X
*
1
Y
2
0
1
?
?
1
X
Y
0
确定化：
{X,1,Y}
{1,Y}
{2}
φ
给状态编号：
0
1
2
3
0
1
1
1
3
1
2
2
3
3
0
{1,Y}
{1,Y}
{1,Y}
φ
1
{2}
{2}
φ
φ
0
0
1
0
1 0
1
1
1
2
3
0
最小化：
{
0
,
1
}
,{
2
,
3
}
{
0
,
1
}
0
?
{
1
}
{
0
,
1
}
1
?
{
2
}
{
2
,
3
}
0
?
{
1
,
3
}<
/p>
{
2
,
3
}
1
?
{
3
}
{
0
,
1
},{
2
},{
3
}
0
1
1 1
1
3
0
0
0
第四章
P81
–
1
(1)
按照
T,S
< br>的顺序消除左递归
G
?
(
S
)
S
?
a
|^
|
(
T
)
< br>T
?
S
T
?
T
?
?
,
S
T
?
|
?
递归子程序：
procedure S;
begin
if sym='a' or sym='^'
then
abvance
else if sym='('
then
begin
advance;T;
if
sym=')' then advance;
else error;
end
else error
end;
procedure
T;
begin
S;
T
?
end;
procedure
T
?
;
begin
if sym=','
then begin
advance;
S;
T
?
end
end;
其中
:
sy
m:
是输入串指针
IP
所指的符号
advance:
是把
IP
调至下一个输入符号
error:
是出错诊察程序
(2)
FIRST(S)={a,^,(}
FIRST(T)={a,^,(}
FIRST(
T
?
)={,,
?
}
FOLLOW(S)={),,,#}
FOLLOW(T)={)}
FOL
LOW(
T
?
)={)}
预测分析表
S
T
a
^
(
)
,
#
S
?
(
T
)
S
?
a
S
?
^
T
?
ST
?
T
?
ST
?
T
?
ST
?
T
?
是
LL(1)
文法
T
?
?
?
T
?
?
,
ST
?
P81
–
2
文法：
E
?
T
E
?
E
?
?
?
E
|
?
T
?
F
T
?
T
< br>?
?
T
|
?
F
?
P
F
?
F
?
?
*
F
?
|
?
P
?
(
E
)
|
a
< br>|
b
|^
(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)
考虑下列产生式
:
E
?
?
?
E
|
?
T
?
?
T
|
?
F
?
< br>?
*
F
?
|
?
P
?
(
E
)|^|
a
|
b
FIRST(+E)
∩
FIRST(
ε
)={
+}
∩
{
ε
}
=
φ
FIRST(+E)
∩
FOLLOW(E')={+}
∩
{#,)}=
φ
FIRS
T(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)
E
E'
T
+
*
(
)
a
b
^
#
E
?
??
E
E
?
TE
'
E
?
TE
'
E
?
TE
'
E
?
TE
'
E
?
?
?
E
?
?
?
T
?
F
T
?
T
?
F
T
?
T
?
F
T
< br>?
T
?
F
T
?
T'
F
F'
P
T
?
?
?
T
?
?
T
< br>
T
?
?
?
T
?
?
T
T
?
?
T
T
?
?
T
T
?
?
?
< br>
F
?
P
F
?
F
?
P
F
?
F
?
P
F
?
F
?
P
F
?
< br>F
?
?
?
F
?
?
*
F
?
F
?
?
?
F
?
?
?
F
?
?
< br>?
F
?
?
?
F
?
?
?
F
?
?
?
P
?
(
E
)
P
?
a
< br>
P
?
b
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;
P81
–
3
/***************
(1)
是，满足三个条件。
(2)
不是，对于
< br>A
不满足条件
3
。
(3)
不是，
A
、
B
均不满足条件<
/p>
3
。
(4)
是，满足三个条件。
***************/
第五章
P133
–
1
E
?
E
?
T
?
E
?
T
*
F
短语
: E+T*F, T*F,
直接短语
: T*F
句柄
: T*F
P133
–
2
文法：
S
?
a
|^|(
T
)
T
?
T
,<
/p>
S
|
S
(1)
最左推导
:
S
?
(
T
)<
/p>
?
(
T
,
S
)
?
(
S
,
S
)
?
(
a
,
S
)
?
(
a
,(
T
))
?
(
a
,(
T
,
S
))
?<
/p>
(
a
,(
S
,
S
))
?
(
a
,(
a
,
S
))
?
(
a
,(
a
,
a
))
S
?
(
T
,
S
)
?
(
S
,
S
)
?<
/p>
((
T
),
S<
/p>
)
?
((
T
,
S
),
S
)
?
((
T
,
S
,
S
),
S
)
?
((
S
,
S
< br>,
S
),
S
)
?
(((
T
),
S
,
S
),
S
)
?
(((
T
,
S
),
S
,
S
)
),
S
)
?
(
((
S
,
S
)
,
S
,
S
),
S
)
?
(((
a
,
S
),<
/p>
S
,
S
),
S
)
?
(((
a
,
a
),
S
,
S
),
S
)
?
(((
a
,
a
),^
,
S
),
S
)
?
(((
a
,
a
),^
,(
T
)),
S
)
?
(((
a
,
a
),^
,(
S
)),
S
)
?
(((
a
,
a
),^
,(
a
)),
S
)
?
(((
a
,
a
),^
,(
a
)),
a
)
最右推导
:
S
?
(
T
)<
/p>
?
(
T
,
S
)
?
(
T
,(
T
))
?
(
T
,(
T
,
S
))
?
(
T
,(
< br>T
,
a
))
?
(
T
,(
S
,
a
))
?
(
T
,(
a
,
a
))
?<
/p>
(
S
,(
a
,
a
))
?
(
a
,(
a
,
a
))
S
?
(
T
,
S
)
?
(
T
,
a
)
?
(
S
,
a<
/p>
)
?
((
T
),
a
)
?
((
T
,
S
),
a
)
?
((
T
,(
T
)),
a
)
?
((
T
,(
S
)),
a
)
?
((
T
,(
a
)),
a
)
?
((
T
,
S
,(
a
)),
a
)
?
((
T
,^
,(
a
)),
a
)
?
((
S
,^
,(
a
)),
a
)
?
(((
T
),^
,(
a
)),
a
)
?
(((
T
,
S
),^
,(
a<
/p>
)),
a
)
?<
/p>
(((
T
,
a<
/p>
),^
,(
a
)
),
a
)
?
(
((
S
,
a
)
,^
,(
a
)),
a
)
?
(((
a
,
a
),^
,(
a
)),
a
< br>)
(2)
< br>(((
a
,a),^,(a)),a)
< br>
(((S,a),^,(a)),a)
(((T,
a
),^,(a)),a)
(((
T,S
),^,(
a)),a)
((
(T)
,^,(a)),a)
((
S
,^,(a)),a)
((T,^,(a)),a)
((<
/p>
T,S
,(a)),a)
((T,(
a
)),a)
((T,(
S
)),a)
((T,(
T
)),a)
((
T,S
),a)
(
(T)
< br>,a)
(
S
,a)
(
T,S
)
(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)#
归
6
#(((T
,a),^,(a)),a)#
归
7
#(((T,
a),^,(a)),a)#
进
8
#(((T,a
),^,(a)),a)#
进
9
#(((T,S
),^,(a)),a)#
归
10
#(((T
),^,(a)),a)#
归
11
#(((T)
,^,(a)),a)#
进
12
#((S
,^,(a)),a)#
归
13
#((T
,^,(a)),a)#
归
14
#((T,
^,(a)),a)#
进
15
#((T,^
,(a)),a)#
进
16
#((T,S
,(a)),a)#
归
17
#((T
,(a)),a)#
归
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#((T,
(a)),a)#
#((T,(
a)),a)#
#((T,(a
)),a)#
#((T,(S
)),a)#
#((T,(T
)),a)#
#((T,(T)
),a)#
#((T,S
),a)#
#((T
),a)#
#((T)
,a)#
#(S
,a)#
归
#(T
,a)#
归
#(T,
a)#
进
#(T,a
)#
进
#(T,S
)#
归
#(T
)#
归
#(T)
#
进
#S
#
归
进
进
进
归
归
进
归
归
进
P133
–
3
(1)
FIRSTVT(S)={a,^,(}
FIRSTVT(T)={,,a,^,(}
LASTVT(S)={a,^,)}
LASTVT(T)={,,a,^,)}
(2)
a
^
(
)
,
a
<
<
^
<
<
(
<
<
)
>
>
=
>
>
,
>
>
<
>
>
G
6
是算符文法，并且是算符优先文法
(3)
优先函数
f
g
f
a
f
^
f
(
f
f
)
,
a
4
5
^
4
5
(
2
5
)
4
2
,
4
3