编译原理第三版课后习题答案.doc
- 文档编号:1224373
- 上传时间:2023-04-30
- 格式:DOC
- 页数:28
- 大小:893.50KB
编译原理第三版课后习题答案.doc
《编译原理第三版课后习题答案.doc》由会员分享,可在线阅读,更多相关《编译原理第三版课后习题答案.doc(28页珍藏版)》请在冰点文库上搜索。
目录
P36-6 1
P36-7 1
P36-8 1
P36-9 2
P36-10 2
P36-11 2
P64–7 3
P64–8 4
P64–12 4
P64–14 6
P81–1 7
P81–2 8
P81–3 11
P133–1 11
P133–2 11
P133–3 13
P134–5 14
P164–5 18
P164–7 18
P217–1 18
P217–3 19
P218–4 19
P218–5 20
P218–6 21
P218–7 21
P219–12 21
P270–9 23
P36-6
(1)
是0~9组成的数字串
(2)
最左推导:
最右推导:
P36-7
G(S)
P36-8
文法:
最左推导:
最右推导:
语法树:
/********************************
*****************/
P36-9
句子iiiei有两个语法树:
P36-10
/**************
***************/
P36-11
/***************
L1:
L2:
L3:
L4:
***************/
第三章习题参考答案
P64–7
(1)
X
Y
X
1
2
3
4
Y
5
0
1101
1
确定化:
0
1
{X}
φ
{1,2,3}
φ
φ
φ
{1,2,3}
{2,3}
{2,3,4}
{2,3}
{2,3}
{2,3,4}
{2,3,4}
{2,3,5}
{2,3,4}
{2,3,5}
{2,3}
{2,3,4,Y}
{2,3,4,Y}
{2,3,5}
{2,3,4,}
0
3
2
0
10
1
00110
6
5
4
01
0
1
11
最小化:
0
0
2
1
1
0010
5
4
3
01
0
1
11
P64–8
(1)
(2)
(3)
P64–12
(a)
a
1
0
a,b
a
确定化:
a
b
{0}
{0,1}
{1}
{0,1}
{0,1}
{1}
{1}
{0}
φ
φ
φ
φ
给状态编号:
a
b
0
1
2
1
1
2
2
0
3
3
3
3
a
1
0
a
abbb
3
2
b
a
最小化:
aa
2
1
0
bb
a
b
(b)
0
3
2
bba
ab
a
ab
5
4
1
ba
aa
已经确定化了,进行最小化
最小化:
0
2
1
bba
ab
a
P64–14
(1)0
1
0
1
0
(2):
Y
X
2
0
1
Y
1
X
0
确定化:
0
1
{X,1,Y}
{1,Y}
{2}
{1,Y}
{1,Y}
{2}
{2}
{1,Y}
φ
φ
φ
φ
给状态编号:
0
1
0
1
2
1
1
2
2
1
3
3
3
3
0
1
0
0
10
3
2
11
1
0
最小化:
0
3
1
0
111
0
0
第四章
P81–1
(1)按照T,S的顺序消除左递归
递归子程序:
procedureS;
begin
ifsym='a'orsym='^'
thenabvance
elseifsym='('
thenbegin
advance;T;
ifsym=')'thenadvance;
elseerror;
end
elseerror
end;
procedureT;
begin
S;
end;
procedure;
begin
ifsym=','
thenbegin
advance;
S;
end
end;
其中:
sym:
是输入串指针IP所指的符号
advance:
是把IP调至下一个输入符号
error:
是出错诊察程序
(2)
FIRST(S)={a,^,(}
FIRST(T)={a,^,(}
FIRST()={,,}
FOLLOW(S)={),,,#}
FOLLOW(T)={)}
FOLLOW()={)}
预测分析表
a
^
(
)
#
S
T
是LL
(1)文法
P81–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)
procedureE;
begin
ifsym='('orsym='a'orsym='b'orsym='^'
thenbeginT;E'end
elseerror
end
procedureE';
begin
ifsym='+'
thenbeginadvance;Eend
elseifsym<>')'andsym<>'#'thenerror
end
procedureT;
begin
ifsym='('orsym='a'orsym='b'orsym='^'
thenbeginF;T'end
elseerror
end
procedureT';
begin
ifsym='('orsym='a'orsym='b'orsym='^'
thenT
elseifsym='*'thenerror
end
procedureF;
begin
ifsym='('orsym='a'orsym='b'orsym='^'
thenbeginP;F'end
elseerror
end
procedureF';
begin
ifsym='*'
thenbeginadvance;F'end
end
procedureP;
begin
ifsym='a'orsym='b'orsym='^'
thenadvance
elseifsym='('then
begin
advance;E;
ifsym=')'thenadvance
elseerror
end
elseerror
end;
P81–3
/***************
(1)是,满足三个条件。
(2)不是,对于A不满足条件3。
(3)不是,A、B均不满足条件3。
(4)是,满足三个条件。
***************/
第五章
P133–1
短语:
E+T*F,T*F,
直接短语:
T*F
句柄:
T*F
P133–2
文法:
(1)
最左推导:
最右推导:
(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
“移进-归约”过程:
步骤 栈 输入串 动作
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
>
>
^
>
>
(
<
<
<
=
<
)
>
>
<
<
<
>
>
是算符文法,并且是算符优先文法
(3)优先函数
a
^
(
)
f
4
4
2
4
4
g
5
5
5
2
3
(4)
栈 输入字符串 动作
# (a,(a,a))# 预备
#( a,(a,a))# 进
#(a ,(a,a))# 进
#(t ,(a,a))# 归
#(t, (a,a))# 进
#(t,( a,a))# 进
#(t,(a ,a))# 进
#(t,(t ,a))# 归
#(t,(t, a))# 进
#(t,(t,a ))# 进
#(t,(t,s ))# 归
#(t,(t ))# 归
#(t,(t) )# 进
#(t,s )# 归
#(t )# 归
#(t ) # 进
#s # 归
success
P134–5
(1)
0. 1. 2. 3.
4. 5. 6. 7.
8. 9. 10. 11.
(2)
1
9
8
7
SA
S
11
10
0
a
4
3
2
AS
d5
6
确定化:
S
A
a
b
{0,2,5,7,10}
{1,2,5,7,8,10}
{2,3,5,7,10}
{11}
{6}
{1,2,5,7,8,10}
{2,5,7,8,10}
{2,3,5,7,9,10}
{11}
{6}
{2,3,5,7,10}
{2,4,5,7,8,10}
{2,3,5,7,10}
{11}
{6}
{2,5,7,8,10}
{2,5,7,8,10}
{2,3,5,7,9,10}
{11}
{6}
{2,3,5,7,9,10}
{2,4,5,7,8,10}
{2,3,5,7,10}
{11}
{6}
{2,4,5,7,8,10}
{2,5,7,8,10}
{2,3,5,7,9,10}
{11}
{6}
{11}
φ
φ
φ
φ
{6}
φ
φ
φ
φ
AS
3:
5:
6:
SAa
b
SaASbSAb
aA
4:
0:
7:
AS
b
aabba
2:
1:
DFA
构造LR(0)项目集规范族也可以用GO函数来计算得到。
所得到的项目集规范族与上图中的项目集一样:
={,,,,}
GO(,a)={}=
GO(,b)={}=
GO(,S)={,,,,,}=
GO(,A)={,,,,}=
GO(,a)={}=
GO(,b)={}=
GO(,S)={,,,,}=
GO(,A)={,,,,,}=
GO(,a)={}=
GO(,b)={}=
GO(,S)={,,,,,}=
GO(,A)={,,,,}=
GO(,a)={}=
GO(,b)={}=
GO(,S)={,,,,}=
GO(,A)={,,,,,}=
GO(,a)={}=
GO(,b)={}=
GO(,S)={,,,,,}=
GO(,A)={,,,,}=
GO(,a)={}=
GO(,b)={}=
GO(,S)={,,,,}=
GO(,A)={,,,,,}=
项目集规范族为C={,,,,,,}
(3)不是SLR文法
状态3,6,7有移进归约冲突
状态3:
FOLLOW(S’)={#}不包含a,b
状态6:
FOLLOW(S)={#,a,b}包含a,b,;移进归约冲突无法消解
状态7:
FOLLOW(A)={a,b}包含a,b;移进归约冲突消解
所以不是SLR文
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 第三 课后 习题 答案
![提示](https://static.bingdoc.com/images/bang_tan.gif)