編譯原理與編譯程序構(gòu)造部分課后答案解析（張莉楊海燕編著）

編譯原理與編譯程序構(gòu)造部分課后答案解析（張莉楊海燕編著）第?章練習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+因ft：A+=AA*=A*A練習2.31.設(shè)G[〈標識符〉]的規(guī)則是：〈標識符〉::=a|b|c|〈標識符〉a|〈標識符〉c|〈標識符〉0|〈標識符〉1試寫出VT和VN，并對下列符號串a(chǎn),ab0,a0c01,0a,11,aaa給出可能的?些推導。解：VT={a,b,c,0,1}，VN={〈標識符〉}(1)不能推導出ab0,11,0a(2)〈標識符〉=>a1=>〈標識符〉01=>〈標識符〉c01=>〈標識符〉0c01=>a0c01a=>〈標識符〉aa=>aaa解：G[<偶整數(shù)>]：<偶整數(shù)>::=<符號><偶數(shù)字>|<符號><數(shù)字串><偶數(shù)字>>+|—|<數(shù)字串>::=<數(shù)字串><數(shù)字>|<數(shù)字><數(shù)字>::=<偶數(shù)字>|1|3|5|7|9<偶數(shù)字>::=0|2|4|6|84.設(shè)?法G的規(guī)則是：〈A〉::=b|cc試證明：cc,bcc,bbcc,bbbcc∈L[G]證：（1）〈A〉=>ccA〉〈A〉=>bccA〉〈A〉〈A〉=>bbccA〉〈A〉〈A〉=>bbb〈A〉=>bbbcc?∵cc,bcc,bbcc,bbbcc∈Vt*bccbbcc5試對如下語?構(gòu)造相應?法：a(bn)a|其中左右圓括號為終結(jié)符。（2）{（an）（bn）|n=1,2,3,……}解：（1）?法[G〈S〉]：S::=a(B)aB::=bB|ε2〈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↑+，8.證明下?的?法G是?義的：S::=iSeS|iS|i證：由?法可知iiiei是該?法的句?，iiiei有兩棵不同的語法樹。所以該?法是?義性?法。第三章練習3.11．畫出下述?法的狀態(tài)圖〈Z〉::=〈B〉e〈B〉::=〈A〉f〈A〉::=e|〈A〉e使?該狀態(tài)圖檢查下列句?是否是該?法的合法句?f，eeff，eefe2、有下列狀態(tài)圖，其中S為初態(tài)，Z為終態(tài)。（1）寫出相應的正則?法：V，Vn和Vt；A→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.2A，B，C是任意正則表達式，證明以下關(guān)系成?：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*)*DFA（1）1（0|1）*|0（2）1（1010*|1（010）*1）*04.5.構(gòu)造?DFA，它接受Σ={0,1}上所有滿?如下條件的字符串：每個1都有0直接跟在右邊。第四章練習4.2G[A]:A::=(B)|dBeB::=c|Bc試設(shè)計?頂向下的語法分析程序。解：消除左遞歸：A::=(B)|dBeB::=c{c}procedureB;ifCLASS='c'thenbeginnextsym;whileCLASS='c'donextsym;end;elseerror;programG;beginnextsym;A;end;procedureA;ifCLASS='('thenbeginnextsym;B;ifCLASS=')'thenelseerrorend；elseifCLASS='d'thenbeginnextsym;B;ifCLASS='e'thennextsym;elseerror;end;elseerror;G[Z]Z::AcB|BdA::=AaB|cB::=aA|a試求各選擇（候選式）FIRST集合；該?法的?頂向下的語法分析程序是否要編成遞歸?程序？為什么？試?遞歸下降分析法設(shè)計其語法分析程序。解:(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}要編成遞歸?程序，因為?法具有遞歸性Z::=AcB|BdA::=c{aB}B::a[A]練習4.31G[E]ETE‘E'→+ET→FT'T'→TF→PF'F'→*F'|εP→(E)|a|b|∧FIRST和集合的解：(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,),+}FIRST(F')={FOLLOW(F')={(,a,),+}FIRST(P)={(,a,b,∧}FOLLOW(P)={*,(,a,),+}(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(∧)=∮所以ft?法是LL(1)?法2aABbcd|εA|εB→SAh|C|εC→Sf|Cg|D→aBD|ε（1)對每?個?終結(jié)符號，構(gòu)造FOLLOW集；（2)對每?產(chǎn)?式的各侯選式，構(gòu)造FIRST集；（3)指出ft?法是否為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}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(ε)=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的每?個?終結(jié)符A的任何兩條不同規(guī)則A::=α|β,有：FIRST(α)∩FIRST(β)=∮則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）?盾。必要性：?法是）?盾。?法，即分析表中不含多重??若條件(1)不成?，即存在某?終結(jié)符B的兩條規(guī)則B::=α1|α2，F(xiàn)IRST(α1)∩FIRST(α2)≠∮則對任意的a∈FIRST(α1)∩