编译原理作业参考答案文档格式.docx
《编译原理作业参考答案文档格式.docx》由会员分享,可在线阅读,更多相关《编译原理作业参考答案文档格式.docx(32页珍藏版)》请在冰点文库上搜索。
诊断编译程序,优化编译程序,交叉编译程序,可变目标编译程序。
第2章高级语言及其语法描述
1(P36)令文法为
NDND
D0129
(1)文法描述的语言L(G)是什么?
(2)给出句子34,568的最左推导和最右推导。
答:
(1)
L(G)={为可带前导0的正整数}
或L(G)={(0129)+}
或L(G)={为数字串}
(2)
最左推导:
NNDDD3D34
NNDNDDDDD5DD56D568
最右推导:
NNDN4D434
NNDN8ND8N68D68568
2*.写出一个文法,使其语言是奇数集,且每个奇数是不以0开头。
SCAB|B(考虑了正负号)
A1|2|3|4|5|6|7|8|9|AA|A0|
B1|3|5|7|9
C+|-|
或:
(未考虑正负号)
SB|AB
B1|3|5|7|9
AAD|N
N2|4|6|8|B
D0|N
SC|ABC
C1|3|5|7|9
A1|2|3|4|5|6|7|8|9
BBA|B0|
2.(P36,8)令文法为
ETE+TE-T
TFT*FT/F
F(E)i
(1)给出该文法的VN、VT和S。
(2)给出i+i*i,i*(i+i)的最左推导和最右推导。
(3)给出i+i+i,i+i*i的语法树。
VN={E,T,F}
VT={+,-,*,/,(,),i}
S=E
最左推导EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*i
ETT*FF*Fi*Fi*(E)i*(E+T)i*(T+T)i*(F+T)i*(i+T)
i*(i+F)i*(i+i)
最右推导EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i
ETT*FT*(E)T*(E+T)T*(E+F)T*(E+i)T*(T+i)T*(F+i)
T*(i+i)F*(i+i)i*(i+i)
构造语法树
E最左推导构造语法树
E+T
E+Ti
Ti
i
3.(P36,9)证明下面的文法是二义的:
SiSeS|iSi
对于句子iiiei有两棵不同的语法树。
因此该文法是二义的。
SiSeSiiSeSiiieSiiiei
SiSiiSeSiiieSiiiei
第3章词法分析
1.设M=({x,y},{a,b},,x,{y})为一个非确定有限自动机NFAM,其中定义如下:
(x,a)={x,y}
(x,b)={y}
(y,a)=
(y,b)={x,y}
试构造其相应的最小化的确定有限自动机DFAM’。
由定义可知(x,a),(y,b)均为多值函数,所以是一个非确定有限自动机。
(1)根据函数值,先构造NFAM
(2)确定化:
①构造DFAM’的转换矩阵:
I
Ia
Ib
{x}①
{x,y}②
{y}③
{y}③
②确定DFAM’的初始状态和终态:
(a)转换矩阵中I列的第一个状态①为DFAM’的初始状态结点。
(b)含有y状态的子集均为DFAM’的终态结点(②、③为终态结点)。
③根据DFAM’的转换矩阵画出对应的状态转换图:
(3)最小化:
①首先将其划分成终态集{2,3}和非终态集{1}
②{2,3}a={2}{2,3},{2,3}b={2}{2,3}
因此{2,3}已是不可再区分的,所以该DFAM’已是最小化的。
2.(P64,7
(1))构造正规式1(01)*101相应的DFAM。
(1)构造NFAM。
1(01)*101
1(01)*101
1101
01
0
1
(2)构造转换矩阵
I0
I1
{X}①
{1,2,3}②
{2,3}③
{2,3,4}④
{2,3}③
{2,3,4}④
{2,3,5}⑤
{2,3,4,Y}⑥
{2,3,4,Y}⑥
(3)由转换矩阵构造DFAM
3.(P64,12(a))将下图所示的NFAM转换为等价的DFAM’,并将该DFA’最小化。
该有限自动机状态0输入同一字符a时到达两个不同的结点,所以是NFA。
(1)构造转换矩阵
{0}①
{0,1}②
{1}③
(2)由转换矩阵构造DFAM
a
b
a
(3)将DFAM最小化
将DFAM的状态划分为非终态集{3}和终态集{1,2}
对每一个子集及每一个a进行考察;
{1,2}a={2}{1,2}
{1,2}b={3}{3}
因此{1,2}是不可区分的,所以最终状态为:
{1,2},{3}
构造最小化的DFAM:
a
b
4.(P64,12(b))将下图所示的NFAM转换为等价的DFAM’,并进行最小化。
从图上可知该图已经是DFAM,先只需将其最小化。
首先划分为两个集合:
{0,1}和{2,3,4,5}
{2,3,4,5}a={1,3,0,5},划分为:
{2,4}和{3,5}
{2,4}a={1,0},{2,4}b={3,5},无需划分
{3,5}a={3,5},{3,5}b={2,4},无需划分
{0,1}a={1},{0,1}b={2,4},无需划分
因此,最终的划分为:
{0,1}、{2,4}和{3,5},化简后的结果:
5.(P65,14)构造一个DFAM,它接受={0,1}上所有满足如下条件的字符串:
每个1都有0直接跟在右边。
(1)根据题意,得到正规式:
(0|10)*
(2)构造对应的NFAM:
(3)将NFAM确定化为DFAM。
相应的DFAM的状态转换矩阵如下:
{X,1,Y}①
{1;
Y}②
{2}③
{1,Y}②
Y}②
{2}③
DFAM转换图:
(4)将DFAM最小化:
①将DFAM的状态划分为非终态集{3}和终态集{1,2}
②对每一个子集进行考察;
{1,2}0={2}{1,2}
{1,2}1={3,3}{3}
因此{0,1}是不可划分的。
因此最终划分结果为:
{1,2}和{3}
最小化后的DFAM:
第4章语法分析-自上而下
1.(P81,1)考虑下面文法G
Sa^(T)
TT,SS
(1)消除文法的左递归。
(2)经改写后的文法是否是LL
(1)的?
给出它的预测分析表。
(1)消除左递归:
Sa^(T)
TST’
T’,ST’|
(2)证明改写后的文法是否是LL
(1)的。
FIRST(S)={a,^,(}FOLLOW(S)={,,),#}
FIRST(T)={a,^,(}FOLLOW(T)={)}
FIRST(T’)={,,}FOLLOW(T’)={)}
证明Sa^(T)各侯选式的FIRST是否两两相交。
FIRST(a)FIRST(^)=
FIRST(a)FIRST(()=
FIRST(^)FIRST(()=
证明T’,ST’的FIRST(T’)和FOLLOW(T’)是否相交。
FIRST(T’)FOLLOW(T’)={,,}{}=
∴该文法是LL
(1)的。
所以,改造后的文法是LL
(1)文法
③预测分析表:
a
^
(
)
,
#
S
Sa
S^
S(T)
T
TST’
TST’
T’
T’
T’,ST’
2.利用P76表4.1的LL
(1)分析表写出表达式(i+i)*i的预测分析过程。
步骤符号栈输入串所用的产生式
0#E(i+i)*i#
1#E’T(i+i)*i#ETE’
2#E’T’F(i+i)*i#TFT’
3#E’T’)E((i+i)*i#F(E)
4#E’T’)Ei+i)*i#
5#E’T’)E`Ti+i)*i#ETE’
6#E’T’)E’T’Fi+i)*i#TFT’
7#E’T’)E’T’ii+i)*i#Fi
8#E’T’)E’T’+i)*i#
9#E’T’)E’+i)*i#T’
10#E’T’)E’T++i)*i#E’+TE’
11#E’T’)E’Ti)*i#
12#E’T’)E’T’Fi)*i#TFT’
13#E’T’)E’T’ii)*i#Fi
14#E’T’)E’T’)*i#
15#E’T’)E’)*i#T’
16#E’T’))*i#E’
18#E’T’*i#
19#E’T’F**i#T’*FT’
20#E’T’Fi#
21#E’T’ii#Fi
22#E’T’#
23#E’#T’
24##E’
3.(P81,2)对下面的文法G
ETE’
E’+E
TFT’
T’T
FPF’
F’*F’
P(E)^ab
(1)计算这个文法的每个非终结符的FIRST和FOLLOW。
(2)证明这个文法是LL
(1)的。
(3)构造它的预测分析表。
(1)计算每个非终结符的FIRST和FOLLOW。
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,^,),#}
(求解过程:
因为E`+E,所以FIRST(E`)={+,}
因为F`*F`,所以FIRST(F`)={*,}
因为P(E)^ab,所以FIRST(P)={(,^,a,b
因为FPF`,所以FIRST(F)=FIRST(P)
因为TFT`,所以FIRST(T)={FIRST(F)
因为ETE`,所以FIRST(E)=FIRST(T)
因为T`T,所以FIRST(T`)=FIRST(T){}
={(,^,a,b,
求非终结符的FOLLOW:
因为ETE`的E是文法的开始符号,FOLLOW(E)={#},又因为P(E),所以FOLLOW(E)={#}FIRST())\{}={#,)}
因为ETE`,所以FOLLOW(E`)=FOLLOW(E)
因为ETE`,并且E`≠,所以FOLLOW(T)=FIRST(E`)\{},又因为E`,所以FOLLOW(T)={+}FOLLOW(E)={+}{#,}}={+,#,}.
因为TFT`,所以FOLLOW(T`)=FOLLOW(T)={+,#,}.
因为TFT`,并且T`≠,所以FOLLOW(F)=FIRST(T`)\{},又因为T`,所以FOLLOW(F)={(,^,a,bFOLLOW(T)={(,^,a,b{+,#,}
={(,^,a,b,+,#,
因为FPF`,所以FOLLOW(F`)=FOLLOW(F)={(,^,a,b,+,#,.
因为FPF`,并且F`≠,所以FOLLOW(P)=FIRST(F`)\{},又因为F`,所以FOLLOW(P)={*FOLLOW(F)={*}{(,^,a,b,+,),#
={*,(,^,a,b,+,,#
(2)证明这个文法是LL
(1)的
该文法没有左递归,只需考察:
E’+E
F’*F’
由于:
E’+E:
FIRST(E’)={+,}∩FOLLOW(E’)={#,}}=Ф
T’T:
FIRST(T’)={(,a,b,^,}∩FOLLOW(T’)={+,),#}=Ф
F’*F’:
FIRST(F’)={*,}∩FOLLOW(F’)={+,(,a,b,^,),#}=Ф
P(E)^ab:
候选式终结符首字符集两两不相交
所以该文法为LL
(1)文法。
(3)LL
(1)分析表
+
*
b
E
ETE’
E’
E’+E
E’
T
TFT’
T’T
F
FPF’
F’
F’*F’
P
P(E)
Pa
Pb
P^
第5章语法分析-自上而下分析
1.(P133,1)令文法G1为:
E→E+T|T
T→T*F|F
F→(E)|i
证明E+T*F是它的一个句型,指出这个句型的所有短语,直接短语和句柄。
因为有:
EE+TE+T*F,所以E+T*F是文法的一个句型。
短语:
E+T*F,T*F直接短语:
T*F句柄:
T*F
2.(P133,3)考虑文法G2
S→a∧|(T)
T→T;
SS
(1)计算文法G2每个非终结符的FIRSTVT和LASTVT。
(2)构造文法G2的优先关系表,该文法是算符优先文法吗?
(3)给出输入串(a;
(a;
a))的算符优先分析过程。
解:
(1)FIRSTVT和LASTVT
FIRSTVT(S)={a,∧,(}
FIRSTVT(T)={;
,a,∧,(}
LASTVT(S)={a,∧,)}
LASTVG(T)={;
,a,∧,)}
(2)优先关系表
∧
;
是算符优先分析文法,因为优先关系表中没有冲突的关系。
(3)(a,(a,a))的分析过程
步骤
栈
余留符号串
栈顶关系
下一步动作
a))#
#<
.(
(进栈
1
#(
A;
a))#
(<
.a
a进栈
2
#(a
a.>
用S→a归约
3
#(S
.;
;
进栈
4
#(S;
<
5
a;
6
(a
7
(S
8
(S;
9
))#
10
S
.>
用T→T;
S归约
11
(T
)进栈
12
(T)
)#
).>
用S→(T)归约
13
14
#(T
15
#(T)
#
16
#S
#
#
结束
3.(P134,5)考虑文法
S→ASb
A→SAa
(1)构造这个文法的LR(0)项目规范族及识别活前缀的DFA。
(2)这个文法是SLR
(1)的吗?
若是,构造出它的SLR分析表。
构造拓广文法:
(0)S’→S
(1)S→AS
(2)S→b(3)A→SA(4)A→a
(2)证明文法是否是SLR
(1)文法?
为了验证这个文法是否是SLR
(1)文法,必须对LR(0)项目集规范族的各个项目集I,验证其是否存在“移进-归约”、“归约-归约”冲突。
该项目规范族中的I1,I5,I7存在“移进-归约”,只需证明存在集合的a,b,FOLLOW(S’),FOLLOW(S),FOLLOW(A)两两不相交。
对此求出FOLLOW(S’)=#,FOLLOW(S)=#,a,b,FOLLOW(A)=a,b。
验证如下:
对状态I1有
FOLLOW(S’)=#;
A→·
S→·
b。
因此FOLLOW(S’)a,b=#a,b=,所以不存在“移进-归约”冲突。
对状态I5有
FOLLOW(A)=a,b;
因此FOLLOW(A)a,b=a,ba,b,所以存在“移进-归约”冲突。
对状态I7也同样存在这种冲突,即:
FOLLOW(S)a,b=#,a,ba,b
因此,该文法不是SLR
(1)文法。
4.(P1357)证明下面文法是SLR
(1)文法,但不是LR(0)文法.
S→A
A→Ab|bBa
B→aAc|a|aAb
证明:
该文法的项目集规范族有:
I0={S→•A,A→•Ab,A→•bBa}
I1=GO(I0,A)={S→A•,A→A•b}
I2=GO(I0,b)={A→b•Ba,B→•aAc,B→•a,B→•aAb}
I3=GO(I1,b)={A→Ab•}
I4=GO(I2,B)={A→bB•a}
I5=GO(I2,a)={B→a•Ac,B→a•,B→a•Ab,A→•Ab,A→•bBa}
I6=GO(I4,a)={A→bBa•}
I7=GO(I5,A)={B→aA•c,B→aA•b,A→A•b}
I8=GO(I5,b)=I2
I9=GO(I7,b)={B→aAb•,A→Ab•}
因为项目集I9中有A→Ab•和B→aAb•,存在“归约-归约”冲突,所以不是LR(0)文法。
又因为FOLLOW(A)={b,c,#},FOLLOW(B)={a}
使得FOLLOW(A)∩FOLLOW(B)=φ,因此构造SLR
(1)分析表时不会出现冲突,所以该文法是SLR
(1)的。
5.有文法:
0.S’→E
1.E→aA
2.E→bB
3.A→cA
4.A→d
5.B→cB
6.B→d
根据下列给出的该文法的LR(0)分析表,写出分析符号串“ac