-
第二章
P36-
6
(1)
L
(
G
1
)
是
0~
9
组成的数字串
(2)
最左推导
:
N
?
ND
?
NDD
?
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<
/p>
7
?
ND
7
?
N
27
?
ND
27
?
N
127
?
D
127<
/p>
?
0127
N
?
ND
?
N
4<
/p>
?
D
4
?
34
N
?
ND
?
N
8
?
ND
8
?
N
68
?
D
68
?
568
P36-
7
G(S)
O
?
1
|
3
|
5
|
7
|
9
N
?
2
|
4
|
6
|
8
|
O
D
< br>?
0
|
N
S
?
O
|
A
O
A
?
AD
|
N
P36-
8
文法：
E
?
T
|
E
?
T
|
E
?
T
T
?
F
|
T
*
F
< br>|
T
/
F
F
?
(
E
)|
i
最左推导
:
E
?
E
?
T
?
T
?<
/p>
T
?
F
?
T
?
i
?
T
?
i
?
T
*
F
?
i
?
F
*
F
?
i
?
i<
/p>
*
F
?
i
?
i
*
i
E
?
T
?
T
*
F
?
F
*
F
?
i
*
F
?
i<
/p>
*(
E
)
?
i
*(
E
?
T
)
?
i
*(
T
?
T
)
?
i
*(
F
?
T
)
?
i
*(
i
?
T
)
?
i
*(
i
?
F<
/p>
)
?
i
*(
i
?
i
)
最右推导
:
E
?
E
?
T
?
E
?
T
*
F
?
E
< br>?
T
*
i
?
E
?
F
*
i
?
E
?
i
*
i
?
T
?
i
*
i
?
F
?
< br>i
*
i
?
i
?
i
*
i
E
?
T
?
F
*
T
?
F
*
F
?
F
*(
E
)
?
F
*(
E
< br>?
T
)
?
F
*(
E
?
F
)
?
F
*(
E
?
i
)
?
F
*(
T
?
i
)
?
F
*(
F
?
i
)
?
F
< br>*(
i
?
i
)
?
i
*(
i
?
i
)
语
法树：
/********************************
E
E
+
T
E
+
T
F
T
F
i
F
i
i
< br>i+i+i
*****************/
P36-
9
句子
iiiei
有两个语法树：
S
S
?
?
iSeS
iS
?
?
iiSeS
iSei
?
?
iiSei
iiSei
?
?
iiiei
iiiei
P36-
10
/**************
S
?
TS
|
T
T
?
(
S
)
|
(
)
***************/
P36-
11
/***************
L1:
S
?
AC
A
< br>?
aAb
|
ab
C
?
cC
< br>|
?
L2:
S
?
AB
A
?
< br>aA
|
?
B
?
bBc
|
bc
L3:
E
E
+
T
T
T
*
F
F
F
i
i
i
i-
i-i
E
E
-
T
E
-
T<
/p>
F
T
F
i
F
i
i
i+i*i<
/p>
S
?
AB
A
?
aAb
|
?
B
?
aBb
|
?
L4:
S
?
A
|
B
A
?
0
A
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}
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
,
2
,
3
,
4
,
5
},{
6
}
{
0
,
1
,
< br>2
,
3
,
4
,
5
}
0
?
{
1
,
3
,
5
}
{
0
,
1
,
2
,
3
,
4
,
5
}
1
?
{
1
,
2
,
4
,
6
}<
/p>
{
0
,
1
,
2
,
3
,
4
},{
5
},{
6
}
{
0
,
1
,
2
,
3
,
4
}
?
{
1
,
3
,
5<
/p>
}
0
{
0
,
1
,
2
,
3
},{
4
},{
5
},{
6
}
{
0
,
1
,
2
,
3
}
0
?
{
1
,
3
}
{
0
,
1
,
2
,
3
}
1
?
{
1
,
2
,
4
}
{
0
,
1
< br>},{
2
,
3
< br>}{
4
},{
5
},{
6
}
{
0
,
1
}
?
{
1
}
{
0
,
1
}
?
{
1
,
2
}
0
1
{
2
,
< br>3
}
0
?
{
3
}
{
2
,
3
}
1
?
{
4<
/p>
}
{
0
},{<
/p>
1
},{
2
,<
/p>
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}
1
a
{0,1}
{0,1}
{0}
b
{1}
{1}
φ
φ
给状态编号：
0
1
2
3
a
1
1
0
3
b
2
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
,
< br>3
}
?
{
0
,
3
}
{
2
,
3
}
?
{
3
}
a
b
{
0
,
1
< br>},{
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
}<
/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):
X
(
010
|
)
*
1
Y
2
0
1
?
?
1
X
0
确定化：
{X,1,Y}
0
{1,Y}
Y
1
{2}
{1,Y}
{2}
φ
给状态编号：
0
1
2
3
0
1
1
1
3
1
2
2
3
3
{1,Y}
{1,Y}
φ
{2}
φ
φ
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
,
3
< br>}
0
?
{
1
,
3
}
{
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;
其中
:
< 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
< br>?
T
?
?
T
|
?
F
?
P
F
?
F
?
?
*
F
?
|
?
P
?
(
E
)
< br>|
a
|
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
T'
+
*
(
E
?<
/p>
TE
'
)
a
b
^
E
?
TE
'
E
?
TE
'
E
?
TE
'
#
E
?
??<
/p>
E
E
?
?
?
E
?
?
?
T
?
F
T
?
T
?
F
< br>T
?
T
?
F
T
?
T
?
F
T
?
T
?
?
?
T
?
?
T
< br>T
?
?
?
T
?
?
T
T
?
?
T
T
?
?
T
T
?
?
?
F
F'
P
F<
/p>
?
P
F
?
F
?
P
F
?
F
?
P
F
?
F
?
P
F
?
<
/p>
F
?
?
?
F
?
?
*
F
?
F
?
?
?
F
?
?
?
F
?
?<
/p>
?
F
?
?
?
F
?
?
?
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
end;
begin
advance; E;
if
sym=')' then advance
else error
end
else error
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
#(((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
#((T,
(a)),a)#
进
19
#((T,(
a)),a)#
进
20
#((T,(a
)),a)#
进
21
#((T,(S
)),a)#
归
22
#((T,(T
)),a)#
归
23
#((T,(T)
),a)#
进
24
#((T,S
),a)#
归
25
#((T
),a)#
归
26
#((T)
,a)#
进
27
#(S
,a)#
归
28
#(T
,a)#
归
29
#(T,
a)#
进
30
#(T,a
)#
进
31
#(T,S
)#
归
32
#(T
)#
归
33
#(T)
#
进
34
#S
#
归
P133
–
3
(1)
FIRSTVT(S)={a,^,(}
FIRSTVT(T)={,,a,^,(}
LASTVT(S)={a,^,)}
LASTVT(T)={,,a,^,)}
(2)
a
^
(
)
,
a
>
>
^
>
>
(
<
<
<
=
<
)
>
>
,
<
<
<
>
>
G
6
是算符文法，并且是算符优先文法
(3)
优先函数
a
^
(
)
,
f
4
4
2
4
4
g
5
5
5
2
3
f
a
f
^
f
(
f
)
f
,
g
a
g
^
g
(
g
)
g
,
（
4
）
栈
输入字符串
#
（
a,(
a,a)
）
#
#(
a, (a,a))#
#(a
, (a,a))#
#(t
, (a,a))#
动作
预备
进
进
归