编译原理及编译程序构造-部分课后答案(张莉--杨海燕编著)

第一章练习12、典型的编译程序可划分为哪几个主要的逻辑部分？各部分的主要功能是什么？典型的编译程序具有7个逻辑部分：第二章练习2.24.试证明：A+=AA*=A*A证：∵A*=A0∪A+，A+=A1∪A2∪…∪An∪…得：A*=A0∪A1∪A2∪…∪An∪…∴AA*=A（A0∪A1∪A2∪…∪An∪…）=AA0∪AA1∪AA2∪…∪AAn∪…=A∪A2∪A3∪An+1∪…=A+同理可得：A*A=(A0∪A1∪A2∪…∪An∪…)A=A0A∪A1A∪A2A∪…∪AnA∪…=A∪A2∪A3∪An+1∪…=A+因此：A+=AA*=A*A练习2.31.设G[〈标识符〉]的规则是：〈标识符〉::=a|b|c|〈标识符〉a|〈标识符〉c|〈标识符〉0|〈标识符〉1试写出VT和VN，并对下列符号串a,ab0,a0c01,0a,11,aaa给出可能的一些推导。解：VT={a,b,c,0,1}，VN={〈标识符〉}(1)不能推导出ab0,11,0a(2)〈标识符〉=a(3)〈标识符〉=〈标识符〉1=〈标识符〉01=〈标识符〉c01=〈标识符〉0c01=a0c01(4)〈标识符〉=〈标识符〉a=〈标识符〉aa=aaa2．写一文法，其语言是偶整数的集合解：G[偶整数]：偶整数::=符号偶数字|符号数字串偶数字符号::=+|—|ε数字串::=数字串数字|数字数字::=偶数字|1|3|5|7|9偶数字::=0|2|4|6|84.设文法G的规则是：〈A〉::=bA|cc试证明：cc,bcc,bbcc,bbbcc∈L[G]证：（1）〈A〉=cc（2）〈A〉=b〈A〉=bcc（3）〈A〉=b〈A〉=bb〈A〉=bbcc（4）〈A〉=b〈A〉=bb〈A〉=bbb〈A〉=bbbcc又∵cc,bcc,bbcc,bbbcc∈Vt*∴由语言定义，cc,bcc,bbcc,bbbcc∈L[G]5试对如下语言构造相应文法：（1）{a(bn)a|n=0,1,2,3,……},其中左右圆括号为终结符。（2）{（an）（bn）|n=1,2,3,……}解：（1）文法[G〈S〉]：S::=a(B)aB::=bB|ε(2)文法[G〈S〉]：--错了，两个n不等S::=(A)(B)A::=aA|aB::=bB|b7.对文法G3[〈表达式〉]〈表达式〉::=〈项〉|〈表达式〉+〈项〉|〈表达式〉-〈项〉〈项〉::=〈因子〉|〈项〉*〈因子〉|〈项〉/〈因子〉〈因子〉::=（〈表达式〉）|i列出句型〈表达式〉+〈项〉*〈因子〉的所有短语和简单短语。表达式=表达式+项=表达式+项*因子短语有：〈表达式〉+〈项〉*〈因子〉和〈项〉*〈因子〉简单短语是：〈项〉*〈因子〉8文法V::=aaV|bc的语言是什么？•解：L（G[V]）={a2nbc|n=0,1,2,……}V⇒aaV⇒aaaaV⇒....⇒a2nbc(n≥1)V⇒bc(n=0)练习2.45.已知文法G[E]：E::=ET+|TT::=TF*|FF::=FP↑|PP::=（E）|i有句型TF*PP↑+，问此句型的短语，简单短语，和句柄是什么？解：此句型的短语有：TF*PP↑+，TF*，PP↑，P简单短语有：TF*，P句柄是：TF*8.证明下面的文法G是二义的：S::=iSeS|iS|i证：由文法可知iiiei是该文法的句子，又由文法可知iiiei有两棵不同的语法树。所以该文法是二义性文法。第三章练习3.11．画出下述文法的状态图〈Z〉::=〈B〉e〈B〉::=〈A〉f〈A〉::=e|〈A〉e使用该状态图检查下列句子是否是该文法的合法句子f，eeff，eefe2、有下列状态图，其中S为初态，Z为终态。（1）写出相应的正则文法：（2）写出该文法的V，Vn和Vt；（3）该文法确定的语言是什么？解：（1）Z→A1|0A→A0|0（2）V={A,Z,0,1}Vn={A,Z}Vt={0,1}（3）L(G[S])={0或0n1,n≥1}L(G[S])={0|00*1}练习3.21．令A，B，C是任意正则表达式，证明以下关系成立：A|A=A（A*）*=A*A*=ε|AA*（AB）*A=A（BA）*（A|B）*=（A*B*）*=（A*|B*）证明：⑴A∣A＝｛x∣x∈L(A)或x∈L(A)｝＝｛x∣x∈L(A)｝＝A⑵（A*）*＝（A*）0∪（A*）1∪（A*）2∪…∪（A*）n＝ε∪(A0∪A1∪A2∪…∪An)∪(A1…)＝ε∪A0∪A1∪A2∪…∪An＝A*⑶ε︱AA*所表示的语言是:{ε}∪LA·LA*＝LA0∪LA（LA0∪LA1∪LA2∪…）＝LA0∪LA1∪LA2∪…＝LA*故ε︱AA*＝A*⑷(LALB)*LA=({ε}∪L(A)LB∪LALBLALB∪LALBLALBLALB∪…)LA=LA∪LALBLA∪LALBLALBLA∪LALBLALBLALB∪LA…=LA∪({ε}∪LBLA∪LBLALBLA∪…)=LA(LBLA)∴(AB)*A=A(BA)*⑸三个表达式所描述的语言都是LALB中任意组合∴（A|B）*=(A*B*)=(A*|B*)*2.构造下列正则表达式相应的DFA（1）1（0|1）*|0（2）1（1010*|1（010）*1）*04.5.构造一DFA，它接受Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。第四章练习4.22.有文法G[A]:A::=(B)|dBeB::=c|Bc试设计自顶向下的语法分析程序。解：消除左递归：A::=(B)|dBeB::=c{c}procedureB;ifCLASS='c'thenbeginnextsym;whileCLASS='c'donextsym;end;elseerror;programG;beginnextsym;A;end;procedureA;ifCLASS='('thenbeginnextsym;B;ifCLASS=')'thennextsym；elseerrorend；elseifCLASS='d'thenbeginnextsym;B;ifCLASS='e'thennextsym;elseerror;end;elseerror;3.有文法G[Z]:Z::=AcB|BdA::=AaB|cB::=aA|a(1)试求各选择（候选式）的FIRST集合；(2)该文法的自顶向下的语法分析程序是否要编成递归子程序？为什么？(3)试用递归下降分析法设计其语法分析程序。解:(1)FIRST(B)={a}FIRST(A)={c}FIRST(Z)={a,c}FIRST(AcB)={c}FIRST(Bd)={a}FIRST(AaB)={c}FIRST(c)={c}FIRST(aA)={a}FIRST(a)={a}(2)要编成递归子程序，因为文法具有递归性(3)改写文法：Z::=AcB|BdA::=c{aB}B::=a[A]练习4.31.对下面的文法G[E]:E→TE‘E'→+E|εT→FT'T'→T|εF→PF'F'→*F'|εP→(E)|a|b|∧(1)计算这个文法的每个非终结符号的FIRST和FOLLOW集合(2)证明这个文法是LL(1)的(3)构造它的预测分析表解：(1)FIRST(E)={(,a,b,∧}FOLLOW(E)={#,)}FIRST(E')={+,ε}FOLLOW(E')={#,)}FIRST(T)={(,a,b,∧}FOLLOW(T)={#,),+}FIRST(T')={(,a,b,∧,ε}FOLLOW(T')={#,),+}FIRST(F)={(,a,b,∧}FOLLOW(F)={(,a,b,∧,#,),+}FIRST(F')={*,ε}FOLLOW(F')={(,a,b,∧,#,),+}FIRST(P)={(,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)文法2.对于文法G[S]：S→aABbcd|εA→ASd|εB→SAh|eC|εC→Sf|Cg|εD→aBD|ε（1)对每一个非终结符号，构造FOLLOW集；（2)对每一产生式的各侯选式，构造FIRST集；（3)指出此文法是否为LL（1）文法。解：（1）FIRST(S)={a,ε}FIRST(A)={a,d,ε}FIRST(B)={a,d,h,e,ε}FIRST(C)={a,f,g,ε}FIRST(D)={a,ε}FOLLOW(S)={d,a,f,h#}FOLLOW(A)={a,h,e,b,d}FOLLOW(B)={b,a}FOLLOW(C)={g,b,a}(2)FIRST(aABbcd)={a}FIRST(ε)={ε}FIRST(ASd)={a,d}FIRST(ε)={ε}FIRST(SAh)={a,d,h}FIRST(eC)={e}FIRST(ε)={ε}FIRST(Sf)={a,f}FIRST(Cg)={a,f,g}FIRST(ε)={ε}(3)不是LL(1)文法，因FIRST(Sf)∩FIRST(Cg)={a,f}∩{a,f,g}≠∮或FOLLOW(S)∩FIRST(aABbcd)＝{d,a,f,h#}∩{a}≠∮或FOLLOW(A)∩FIRST(ASd)＝{a,h,e,b,d}∩{a,d}≠∮或FOLLOW(B)∩FIRST(SAh)＝{a,b}∩{a,d,h}≠∮或FOLLOW(C)∩FIRST(Sf)＝{g,a,b}∩{a,f}≠∮或FOLLOW(C)∩FIRST(Cg)＝{g,a,b}∩{a,f,g}≠∮6.一个文法G是LL(1)的必要与充分条件是什么？试证明之。充要条件是：对于G的每一个非终结符A的任何两条不同规则A::=α|β,有：(1)FIRST(α)∩FIRST(β)=∮(2)假若β=*=ε,则FIRST(α)∩FOLLOW(A)=∮证明：充分性：条件（证明：充分性：条件（1）（2）成立反证：若分析表中存在多重入口，即）成立反证：若分析表中存在多重入口，即M[B,a]={B::=α1,B::=α2},表明FIRST(α1)∩FIRST(α2)≠∮或M[B,a]={B::=α1,B::=α2}，其中α2=ε或α2=+=ε表明FIRST(α1)∩FOLLOW(B)≠∮与条件（1）（2）矛盾。必要性：文法是）矛盾。必要性：文法是LL(1)文法，即分析表中不含多重入口若条件文法，即分析表中不含多重入口若条件(1)不成立，即存在某非终结符B的两条规则B::=α1|α2，FIRST(α1)∩FIRST(α2)≠∮则对任意的a∈FIRST(α1)∩FIRST(α2)，有M[B,a]={B::=α1,B::=α2},矛盾若条件（矛盾若条件（2）不成立，即存在某非终结符B的两条规则B::=α1|α2，α2=*=ε有FIRST(α1)∩FOLLOW(B)≠∮则对任意的a∈FIRST(α1)∩FOLLOW(B)，有M[B,a]={B::=α1,B::=α2},矛盾练习4.44.有文法G[E]:E::=E+T|TT::=T*F|FF::=(E)|i列出下述句型的短语和素短语：E、T、i、T*F、F*F、i*F、F*i、F+F+F练习4.51.考虑具有下列规则的文法S→E#E→T|E+TT→P|P↑TP→F|P*FF→i|(E)(a)下列句型的最右推导步骤中，其活前缀的集合是什么？(1)E+i*i#(2)E+P↑(i＋i)＃(b)