編譯原理及編譯程序構造部分課后的答案

...wd......wd......wd...第一章練習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[〈標識符〉]的規(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)〈標識符〉=>a(3)〈標識符〉=>〈標識符〉1=>〈標識符〉01=>〈標識符〉c01=>〈標識符〉0c01=>a0c01(4)〈標識符〉=>〈標識符〉a=>〈標識符〉aa=>aaa2．寫一文法，其語言是偶整數(shù)的集合解：G[<偶整數(shù)>]：<偶整數(shù)>::=<符號><偶數(shù)字>|<符號><數(shù)字串><偶數(shù)字><符號>::=+|—|ε<數(shù)字串>::=<數(shù)字串><數(shù)字>|<數(shù)字><數(shù)字>::=<偶數(shù)字>|1|3|5|7|9<偶數(shù)字>::=0|2|4|6|84.設文法G的規(guī)那么是：〈A〉::=b<A>|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,……},其中左右圓括號為終結符?！?〕{〔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．畫出下述文法的狀態(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)?！?〕寫出相應的正那么文法：〔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)對每一產(chǎn)生式的各侯選式，構造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的任何兩條不同規(guī)那么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的兩條規(guī)那么B::=α1|α2，F(xiàn)IRST(α1)∩FIRST(α2)≠∮那么對任意的a∈FIRST(α1)∩FIRST(α2)，有M[B,a]={B::=α1,B::=α2},矛盾假設條件〔矛盾假設條件〔2〕不成立，即存在某非終結符B的兩條規(guī)那么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.考慮具有以下規(guī)那么的文法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)為以下輸入串構造最右推導的逆：(1)i+i*i#(2)i+i↑(i+i)#解：(a)〔1〕句柄為i，所以活前綴集合為：E，E，E＋i〔2〕句柄為i，所以活前綴集合為：E，E+,E+P,E+P↑,E+P↑(,E+P↑(I(b)〔1〕i+i*i#<=F+i*i#<=P+i*i#<=T+i*i#<=E+i*i#<=E+F*i#<=E+P*i#<=E+P*F#<=E+P#<=E+T#<=E#<=S練習4.61.給定具有如下產(chǎn)生式的文法S→E#E→E-T|TT→F|F↑TF→i|(E)試求以下活前綴的有效工程集：(a)F↑(b)E-((c)E-T解：(a)E↑{T→.FT→F↑.TT→.F↑TF→.iF→.(E)}(b)E-({F→(.E),E→.E-T,E→.T,T→.F,T→.F↑T,T→.i,T→.(E)}(c)E-T{E→E-T.}練習4.71.給定以下產(chǎn)生式的文法：S→EE→T|E+TT→P|T*PP→F|F↑PF→i|(E)(1)為該文法構造SLR〔1〕分析表。第五章練習53.如下非分程序構造語言的程序段，畫出編譯該程序段時將生成的有序符號表。BLOCKREALX,Y,Z1,Z2,Z3;INTEGERI,J,K,LASTI;STRINGLIST-OF-NAMES;LOGICALENTRY-ONEXIT-OFF;ARRAYREALVAL(20);ARRAYINTEGERMIN-VAL-IND(20);…ENDOFBLOCK;5.畫出下面的分程序構造的程序段當程序段3和4的編譯即將完成以前的棧式符號表的圖形(包括有效局部和失效局部〕。第六章練習6.22考慮下面的類ALGOL程序，畫出當程序執(zhí)行到①和②時，運行棧內(nèi)容的圖像。第七章練習72.將下面的語句A:=(B+C)↑E+(B+C)*F轉換成三元式