编译原理第六章到第十一章课后习题答案.pdf
编译原理第六章到第十一章课后习题答案
p116/1.已知文法G[S]为:
S→a|∧|(T)
T→T,S|S
(1)计算FIRSTVT--LASTVT表
(2)构造算符优先关系表(OPERATERPRIORITYRELATION
TABLE),说明是否为算符优先文法。=:#=#,(=)=:#=#,(=)
:LASTVT(S)#,LASTVT(T)),LASTVT(T),
表中无多重人口所以是算符优先(OPG)文法。
(3)计算G[S]的优先函数。
收敛
(4)对输入串(a,a)#的算符优先分析过程为
Success!
3.有文法G(S):
s-V
v-T/ViT
T-F/T+F
F-)V*|(
(1)(+(i(的规范推导
S=V
=ViT
=ViF
=Vi(
=Ti(
=T+Fi(
=T+(i(
=F+(i(
=(+(i(
(2)F+Fi(的短语、句柄、素短语。
短语
S:F+Fi(
T1:F+F(素短语)
T2:F(句柄)
F:((素短语)
(3)G(S)是否为OPG?若是,给出(1)中句子的分析过程!
S’-#S#S-VV-T/ViTT-F/T+FF-)V*|(
算符优先关系表(OPERATERPRIORITYRELATIONTABLE)
对输入串(+(I(的算符优先分析过程为:
p152/2
文法:
S→L.L|L
L→LB|B
B→0|1
拓广文法为G′,增加产生式S′→S
I3
若产生式排序为:
0S→S
1S→L.L
2S→L
3L→LB
4L→B
5B→0
6B→1
由产生式知:
First(S)={0,1}
First(S)={0,1}
First(L)={0,1}
First(B)={0,1}
Follow(S)={#}
Follow(S)={#}
Follow(L)={.,0,1,#}
Follow(B)={.,0,1,#}
G′的LR(0)项目集族及识别活前缀的DFA如下图所示:
I5
B→.0和B→.1为移进项目,S→L.为归约项目,存在移进-归约
冲突,因此所给文法不是LR(0)文法。
在I
2、I
8
中:
Follow(s)∩{0,1}={#}∩{0,1}=
所以在I
2、I
8
中的移进-归约冲突可以由Follow集解决,所以G是SLR(1)文法。
构造的SLR(1)分析表如下:
分析成功,说明输入串101.110是题目2文法的句子。
0)S’-S
1)S-a
2)S-^
3)S-(T)
4)T-T,S
5)T-S
LR(0)分析表
[8。1]写出下列各式的逆波兰表示
(1)-a-((b*c)/(c-d)+(-b)*a)
(2)-A+B*C↑(D/E)/F
栈顶运算符与当前运算符比较:
栈顶运算符当前运算符:进栈
栈顶运算符当前运算符:进行运算
解8.1:
(1)a@bc*cd-/b@a*+-
(2)A@BCDE/↑*F/+
[8。2]写出表达式
A+B*(C-D)-E/F↑G
逆波兰表示,三元组表示,四元组表示。解8.2:逆波兰表示:
ABCD-*+EFG↑/-
①(-,C,D)
②(*,B,①)
③(+,A,②)
④(↑,F,G)
⑤(/,E,④)
⑥(-,③,⑤)
四元式组:
1)(