-
第二章习题解答
P36-6
(1)
L
(
G
1
)
< br>是
0~9
组成的数字串
(2)
最左推导
:
N
?
ND
?
< br>NDD
?
NDDD
?
DDDD
?
0
DDD
?
01
DD
?
012
D
?
012
7
N
?
ND
?
DD
?
3
D<
/p>
?
34
N
?
ND
?
NDD
?<
/p>
DDD
?
5
DD
?
56
D
?<
/p>
568
最右推导
:
N
?
ND<
/p>
?
N
7
?
ND
7
?
N
27
?
ND
27
?
N
127
?
D
127
?
0127
N
?
ND
?<
/p>
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
|
N
P36-8
文法：
E
?
T
|
E
?
T
|
E
?
T
T
?<
/p>
F
|
T
*
F
|
T
/
F
F
?
(
E
)|
i
< br>最左推导
:
E
?
E
?
T
?
< br>T
?
T
?
F
?
T
?
i
?
T
?
i
?
T
*
F
?
i
?
F
*
F
?
i
< br>?
i
*
F
?
i
?
i
*
i
E
?
T
?
T
*
F
?
F
*
F
?
i
*
F
< br>?
i
*(
E
)
?
i
*(
E
?
T
)
?
i
*(
T
?<
/p>
T
)
?
i
*(
F
?
T
)
?
i
*(
i
?
T
)
?
i
*(
i
< br>?
F
)
?
i
*(
i
?
i
)
最右推导
:
E
?
E
?
T
?
E
?
T
*
F
?
E
?
T
*
i
?
E
?
F
*
< br>i
?
E
?
i
*
i
?
T
?
i
*
i
?
F
?
i
*
i
?
i
?
i
*
i
< br>E
?
T
?
F
*
T
?
F
*
F
?
F
*(
E
)
?
F
*(
E
?
T
)
?
F
*(
E
?
F
)
?
F
*(
< br>E
?
i
)
?
F
*(
T
?
i
)
?
F<
/p>
*(
F
?
i
)
?
F
*(
i
?
i
)
?
i
*(
i
?
i
)
语法树：
/********************************
E
E
E
T
E
E
+
E
+
T
E
-
T
E
< br>+
T
F
T
T
*
F
-
T
F
T
F
i
F
F
i
T
F
i
F
i
i
i
F
i
< br>i
i+i+i
i-i-i
i
i+i*i
*****************/
P36-9
句子
iiiei
有两个语法树：
S
?
iSeS
?
iSei
?
iiSei
?
iiiei
S
?
iS
?
iiSeS
?
iiSei
?
iiiei<
/p>
P36-10
/**************
S
?
TS
|
T
T
?
(
S
)
|
(
)
***************/
P36-11
/***************
L1:
S
?
AC
A
?
aAb
|
ab
C
?
cC
|
?
L
2:
S
?
AB
A
?
aA
|
?
B
?
bBc
|
bc
L3:
S
?
AB<
/p>
A
?
aAb
|<
/p>
?
B
?
aBb
|
?
L4:
S
?
A
|
B
A
?
0
A
1
|
?
B
?
1
< br>B
0
|
A
***************/
第三章习题参考答案
P64
–
7
(1)
*
1
(
01
|<
/p>
)
101
X
Y
0
1
?
?
1 0
1
1
X
1
2
3
4
5
确定化：
{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}
Y
{2,3,4,Y}
{2,3,4,}
0
1 0
0
2
3
0 0 1 1
0
0 1
1
4
5
6
0
1
1 1
最小化：
{
0
,
1
,<
/p>
2
,
3
,
4
,
5
},{
6
}
{
0
,
1
,
2
,
3
,
4
,
5
}
?
{
1
,
3
,<
/p>
5
}
{
0
,
1
,
2
,
3
,
4
,
5
}
?
{
1
,
< br>2
,
4
,
6
}
0
1
{
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
}
?
{
< br>1
,
3
}
{
0
,
1
,
2
,
3
}
?
{
1<
/p>
,
2
,
4
}
0
1
{
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
)
*
0
1
(2)
(
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
)(
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|<
/p>
8
|
9
)
*
(
0
|
5
)
|
(
0
|
5
)
(3)
0
*
< br>1
(
0
|
10
*
1
)
*
|
1
*
0<
/p>
(
0
|
10
*
1
)
*
P64
–
12
(a)
a
a,b
0
a
确定化：
{0}
{0,1}
{1}
φ
给状态编号：
0
a
1
b
2
1
a
{0,1}
{0,1}
{0}
φ
b
{1}
{1}
φ
φ
1
2
3
1
0
3
2
3
3
a
a
0
1
a b b b
b
2
3
a
最小化：
{
0
,
1
},{
2
,
3
}
{
0
,
1
}<
/p>
?
{
1
}
{
0
,
1
}
?
{
2
}
a
b
{
2
,
3
< br>}
?
{
0
,
3
}
{
2
,
3
}
?
{
3
}<
/p>
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
已经确定化了
,
进行最小化
最小化：
{
{
0
,
1
}
,
{
2
,
3
,
4
,
5
}
}
{
0
,
1
}
a
?
{
1<
/p>
}
{
0
,
1
}
b<
/p>
?
{
2
,
4
}
{
2
,
3
,
4
,
5
}
a
?
{
1
,
3
,
0
,
5<
/p>
}
{
2
,
3
,
4<
/p>
,
5
}
b
?
{
2
,
3
,
4
,
5
}
{
2
,
4
}
a
?
{
1
,
0<
/p>
}
{
2
,
4
}
b
?
{
3
,
5
}
{
3
,
5
}
a
< br>?
{
3
,
5
}
{
3
,
5
}
b
?
{
2
,<
/p>
4
}
{{
0
,
1
},{
2
,
4
},{
3
,
5
}}
{
0
,
1
}
a
?
{
1
}
{
0
,
1
}
b
?
{
2
,
4
}
{
2
,
4
}
a
?<
/p>
{
1
,
0
}
{
2
,
4
}
b
?
{
3
,
5
}
{
3
< br>,
5
}
a
?
{
3
,
5
}
{
3
,
5
}
b<
/p>
?
{
2
,
4
}
b
b a
1
2
0
a b
a
P64
–
14
(1) 0
1
0
0
(2):
X
(
010
|
)
*
1
Y
2
0
1
?
?
1
X
0
确定化：
{X,1,Y}
{1,Y}
{2}
φ
给状态编号：
0
1
2
3
0
1
1
1
3
0
{1,Y}
{1,Y}
{1,Y}
φ
Y
1
{2}
{2}
φ
φ
1
2
2
3
3
0
0
1
0
1 0
1
1
1
2
3
0
最小化：
{
0
,
1
},{
2
,
3
}
{
0
,
1<
/p>
}
0
?
{
1
}
{
0
,
1
}
1
?
{
2
}
{
2
,
< br>3
}
0
?
{
1
,
3
}
{
2
,
3
}
1
?<
/p>
{
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;
其中
:
< br>sym:
是输入串指针
IP
所指
的符号
advance:
是把
IP
调至下一个输入符号
error:
是出错诊察程序
(2)
FIRST(S)={a,^,(}
FIRST(T)={a,^,(}
FIRST(
T
?
)={,,
?
}
FOLLOW(S)={),,,#}
FOLLOW(T)={)}
FOLLOW(
T
?
)={)}
预测分析表
S
T
a
^
(
)
,
#
<
/p>
S
?
(
T
)
T
?
ST
?
T
?
ST
?
T
?
ST
?
< br>
S
?
a
S
?
^
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<
/p>
?
?
*
F
?
|
?
P
?
(
E
)|^|
a
|
b
FIRST(+E)
∩
FIRST(
ε
)={+}
∩
{
ε
}=
φ
FIRST(+E)
∩
FOLLOW(E')={+
}
∩
{#,)}=
φ
< br>
FIRST(T)
∩
FIRS
T(
ε
)={(,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
T'
F
F'
P
+
*
(
E
?<
/p>
TE
'
)
a
b
^
E
?
TE
'
E
?
TE
'
E
?
TE
'
#
E
?
??<
/p>
E
E
?
?
?
E
?
?
?
T
?
F
T
?
F
?
P
F
?
T
?
F
< br>T
?
T
?
F
T
?
T
?
F
T
?
F
?
P
F
?
F
?
P
F
< br>?
F
?
P
F
?
T
?
?
?
T
?
?
T
T
?
?
?
T
?
?
T
< br>T
?
?
T
T
?
?
T
T
?
?
?
F
?
?
?
F
?
?
*
F
< br>?
F
?
?
?
F
?
?
?
F
?
?
?
F
?
?
?
F
?
?
< br>?
F
?
?
?
P
?
(
E
)
P
?
a
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
)
?
(
T
,
S
)
?
(<
/p>
S
,
S
)
?
(
a
,
S
)
?
(
a
,(
T
))
?
(
a
,(
< br>T
,
S
))
?
(
a
,(
S
,
S
))
?
(
a
,(
a
,
S
))
?<
/p>
(
a
,(
a
,
a
))
S
?
(
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
< br>)),
S
)
?
< br>(((
S
,
S
< br>),
S
,
S
),
S
)
?
(((
a
,
S
),
S
,
S
),
S
)
?
(
((
a
,
a
)
,
S
,
S
),
S
)
?
(((
a
,
a
),^
,
S
),
S<
/p>
)
?
(((
a<
/p>
,
a
),^
,(
T
)),
S
)
?
(((
a
,
a
),^
,(
S
)),
S
)
?
(((
a
,
a
),^
,(
a
)),
S
)
?
(((
a
,
a
),^
,(
a
)),
a
)
最右推导
:
S
?
(
T
)
?
(
T
,
S
)
?
(
T
,(
T
))
?
(
T
,(
T
,
S
))
?
(
T
,(
T
,
a
))
?
< br>(
T
,(
S
,
a
))
?
(
T
,(
a
,
a
))
?
(
S
,(
a
,<
/p>
a
))
?
(
a
,(
a
,
a
))
S
?
(
T
,
S
)
?
(
T
< br>,
a
)
?
(
S
,
a
)
?
((
T
),
a
)
?
((<
/p>
T
,
S
),
a
)
?
((
T
,(
T
)),
a
)
?
((
T
,(
S
)),
a
)
?
((
T
,(
a
)),
a
)
?
((
T
,
S
,(
a
)),
a
)
?
((
T
,^
,(
a
)),
a
)
?
((
S
,^
,(
a
)),
a
)
?
(((
T
),^
,(
a<
/p>
)),
a
)
?<
/p>
(((
T
,
S<
/p>
),^
,(
a
)
),
a
)
?
(
((
T
,
a
)
,^
,(
a
)),
a
)
?
(((
S
,
a
),^
,(
a
)),
a
< br>)
?
(((
a
< br>,
a
),^
,(
a
)),
a
)
(2)
(((
a
,a),^,(a)),a)
(((S,a),^,(a)),a)
(((T,
a
),^,(a)),a)
(((
T,S
),^,(a)),a)
((
(T)
,^,(a)),a)
((
S
,^,(a)),a)
((T,^,(a)),a)
((
T,S
,(a)),a)
((T,(
a
)),a)
((T,(
S
)),a)
((T,(
T
)),a)
((
T,S
),a)
(
(T)
,a)
(
S
,a)
(
T,S
)
(T)
S
“移进
< br>-
归约”过程：
步骤
栈
输入串
动作
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
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#(((S
,a),^,(a)),a)#
归
#(((T
,a),^,(a)),a)#
归
#(((T,
a),^,(a)),a)#
进
#(((T,a
),^,(a)),a)#
进
#(((T,S
),^,(a)),a)#
归
#(((T
),^,(a)),a)#
归
#(((T)
,^,(a)),a)#
进
#((S
,^,(a)),a)#
归
#((T
,^,(a)),a)#
归
#((T,
^,(a)),a)#
进
#((T,^
,(a)),a)#
进
#((T,S
,(a)),a)#
归
#((T
,(a)),a)#
归
#((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
<
<
^
<
<
(
<
<
)
>
>
=
>
>
,
>
>
<
>
>