编译原理第三版课后习题答案文档格式.doc
- 文档编号:1455296
- 上传时间:2023-04-30
- 格式:DOC
- 页数:28
- 大小:893.50KB
编译原理第三版课后习题答案文档格式.doc
《编译原理第三版课后习题答案文档格式.doc》由会员分享,可在线阅读,更多相关《编译原理第三版课后习题答案文档格式.doc(28页珍藏版)》请在冰点文库上搜索。
P36-10
/**************
***************/
P36-11
/***************
L1:
L2:
L3:
L4:
第三章习题参考答案
P64–7
X
Y
1
2
3
4
5
0
1101
1
确定化:
{X}
φ
{1,2,3}
{2,3}
{2,3,4}
{2,3,5}
{2,3,4,Y}
{2,3,4,}
0
10
00110
6
01
0
1
11
最小化:
1
0010
11
P64–8
(1)
(3)
P64–12
(a)
a
a,b
a
a
b
{0}
{0,1}
{1}
给状态编号:
a
abbb
b
a
aa
bb
a
b
(b)
bba
ab
ab
ba
aa
已经确定化了,进行最小化
P64–14
(1)0
1
0
(2):
0
1
0
{X,1,Y}
{1,Y}
{2}
0
0
10
11
1
0
111
0
第四章
P81–1
(1)按照T,S的顺序消除左递归
递归子程序:
procedureS;
begin
ifsym='
a'
orsym='
^'
thenabvance
elseifsym='
('
thenbegin
advance;
T;
ifsym='
)'
thenadvance;
elseerror;
end
elseerror
end;
procedureT;
S;
procedure;
'
thenbegin
advance;
S;
end
其中:
sym:
是输入串指针IP所指的符号
advance:
是把IP调至下一个输入符号
error:
是出错诊察程序
FIRST(S)={a,^,(}
FIRST(T)={a,^,(}
FIRST()={,,}
FOLLOW(S)={),,,#}
FOLLOW(T)={)}
FOLLOW()={)}
预测分析表
^
(
)
#
S
T
是LL
(1)文法
P81–2
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,^,+,),#}
考虑下列产生式:
FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ
FIRST(+E)∩FOLLOW(E'
)={+}∩{#,)}=φ
FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ
FIRST(T)∩FOLLOW(T'
)={(,a,b,^}∩{+,),#}=φ
FIRST(*F'
)∩FIRST(ε)={*}∩{ε}=φ
)∩FOLLOW(F'
)={*}∩{(,a,b,^,+,),#}=φ
FIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ
所以,该文法式LL
(1)文法.
+
*
E
E'
T'
F
F'
P
(4)
procedureE;
b'
thenbeginT;
E'
end
elseerror
end
procedureE'
;
+'
thenbeginadvance;
Eend
elseifsym<
>
'
andsym<
#'
thenerror
thenbeginF;
T'
end
procedureT'
thenT
elseifsym='
*'
procedureF;
thenbeginP;
F'
procedureF'
procedureP;
thenadvance
then
begin
E;
ifsym='
thenadvance
elseerror
elseerror
P81–3
(1)是,满足三个条件。
(2)不是,对于A不满足条件3。
(3)不是,A、B均不满足条件3。
(4)是,满足三个条件。
第五章
P133–1
短语:
E+T*F,T*F,
直接短语:
T*F
句柄:
P133–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)
“移进-归约”过程:
步骤 栈 输入串 动作
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
FIRSTVT(S)={a,^,(}
FIRSTVT(T)={,,a,^,(}
LASTVT(S)={a,^,)}
LASTVT(T)={,,a,^,)}
<
=
是算符文法,并且是算符优先文法
(3)优先函数
f
g
栈 输入字符串 动作
# (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
0. 1. 2. 3.
4. 5. 6. 7.
8. 9. 10. 11.
9
8
7
SA
S
11
10
a
AS
d5
A
{0,2,5,7,10}
{1,2,5,7,8,10}
{2,3,5,7,10}
{11}
{6}
{2,5,7,8,10}
{2,3,5,7,9,10}
{2,4,5,7,8,10}
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(,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文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 第三 课后 习题 答案