編譯原理練習及答案

第一章練習題（緒論）一、選擇題編譯程序是一種常用的 B—軟件。A）應用 B）系統 C）實時系統D）分布式系統編譯程序生成的目標代碼程序 B 是可執(zhí)行程序。A）—定 B）不一定編譯程序的大多數時間是花在D—上。A）詞法分析B）語法分析 C）出錯處理D）表格管理將編譯程序分成若干“遍”將 B。A） 提咼編譯程序的執(zhí)行效率；B） 使編譯程序的結構更加清晰，提高目標程序質量；C） 充分利用內存空間，提咼機器的執(zhí)行效率。編譯程序各個階段都涉及到的工作有D。A）詞法分析B）語法分析 C）語義分析D）表格管理詞法分析的主要功能是 。A）識別字符串B）識別語句C）識別單詞 D）識別標識符若某程序設計語言允許標識符先使用后說明，則其編譯程序就必須A 。A）多遍掃描 B）一遍掃描編譯方式與解釋方式的根本區(qū)別在于B。A）執(zhí)行速度的快慢 B）是否生成目標代碼C）是否語義分析多遍編譯與一遍編譯的主要區(qū)別在于D 。A） 多遍編譯是編譯的五大部分重復多遍執(zhí)行，而一遍編譯是五大部分只執(zhí)行一遍；B） 一遍編譯是對源程序分析一遍就立即執(zhí)行，而多遍編譯是對源程序重復多遍分析再執(zhí)行；C） 多遍編譯要生成目標代碼才執(zhí)行，而一遍編譯不生成目標代碼直接分析執(zhí)行；D） 多遍編譯是五大部分依次獨立完成，一遍編譯是五大部分交叉調用執(zhí)行完成。編譯程序分成“前端”和“后端”的好處是DA） 便于移植B） 便于功能的擴充C） 便于減少工作量D） 以上均正確第二章練習題（文法與語言）1、直接推導、＋推導、＊推導2、句型和句子，文法定義（搞清楚）G=（VT,VN,S,P）3、語言的形式定義： L（G[S]）={xIS->x且xGVT*}若L是無窮的，則G一定是遞歸的4、 最左推導、最右推導（規(guī)范推導）5、 歸約、規(guī)范歸約6、 遞歸：規(guī)則遞歸、文法遞歸（1） A->BAe->CA,???（2） A->B,B->CA,???文法的等價性：G1=G2（1）每棵子樹的葉子組成一個短語；（2） 每棵簡單子樹的葉子組成一個直接短語；簡單子樹：只有單層分支的子樹（3） 最左邊簡單子樹的葉子是句柄一個句型不一定只對應一棵唯一的語法樹。如果一個文法存在某個句子對應二棵不同的語法樹或者二個不同的最左（右）推導，則這個文法是二義性的歸約是推導的逆過程。即：將句型中的某一子串用一串非終結符代替的過程。若有A->a則XAY->XaY,于是XaY->XAY。稱規(guī)范（最右）推導的逆過程為規(guī)范歸約（先歸約最左那一串（不是一個）符號）。規(guī)范歸約：先歸約最左那一串（不是一個）符號。1）文法的開始符一定寫在文法的前面（第一條規(guī)則式中）；2） e是表示空符號串，不是終結符；3） L是語言，不要用作非終結符；4） 文法的完整表示是G=（VT,VN,S,P）一、選擇題文法G產生的D 的全體是該文法描述的語言。A.句型B.終結符集C.非終結符集D.句子若文法G定義的語言是無限集，則文法必然是AA遞歸的B上下文無關的C二義性的D無二義性的Chomsky定義的四種形式語言文法中，0型文法又稱為A文法;1型文法又稱為C文法；2型語言可由G_識別。A短語結構文法B上下文無關文法C上下文有關文法D正規(guī)文法E圖靈機F有限自動機G下推自動機一個文法所描述的語言是A；描述一個語言的文法是BA唯一的B不唯一的C可能唯一，也可能不唯一二、構造文法以生成下列語言：{anbnInMO}解：G=（{S},{a,b},S,P）,其中P={S-e|aSb}{anbmIn，mM1}解：G=（{S，A，B}，{a，b}，S，P），其中P={S—AB,A—aIaA,B—bIbB}{an,bmIn，mM1}解：G=（{S，A，B}，{a，b}，S，P），其中P={S—A|B,A—aIaA,B—bIbB}

4.L={wIw是不含兩個相鄰1的0、1串}解：G=({S,A},{0,1},S,P),其中P={S-0|1|OS|1A,A—OS|0}5．能被5整除的整數集合。解：G[S]:S->FNCF->+I-IEC->0|5N->AMIE M->0IAIEA->1I2I3I4I5I6I7I8I9Ex1:設E={a,b},試設計一個文法G,定義語言L={a2n,b2nIn>1}解：G[A]：A->BIDB->aaIaBaD->bbIbDbEx3：設計一個表示所有標識符I的文法。解：G[I]：I->LIILDL->a|b|c z|A|B|C |ZED->1|2|3 |9|E&設G[E]：E->E+EIE*E|(E)|i,試證明符號串(i*i+i)是文法G[E]的一個句子證明：從E出發(fā)，只要證明符號串x=(i*i+i)對于文法G[E]存在一個推導。E->(E)->(E+E)->(E＊E+E)->(i*E+E)->(i*i+E)->(i*i+i)以上從文法的開始符E->(i*i+i)，所以符號串(i*i+i)是G[E]的一個句子。Ex:已知:S->ABA->AaIbBB->aISb,給出句子babaab的最左、最右推導解：最左：S=>AB=>bBB=>baB=>baSb=>baABb=>babBBb=>babaBb=>babaabS=>AB=>ASb=>AABb=>AAabbabaab=>bBbaab=>Abaabi,j,k>=0S=>AB=>ASb=>AABb=>AAabbabaab=>bBbaab=>Abaabi,j,k>=0}D->aDIE, C->bCcIE=>AbBab=>Abaab=>bBbaab=>babaab歸約：=>AbBab=>AAab=>AABb=>Asb=>AB=>S已知L={aibjckIi=j或j=k,求：文法G解：S->ABIDC,A->aAbIE,B->cBIE11?已知L={xx-1Ix^{a,b}+}，若x=ab,Mx-1=ba,求文法G。解：因為x={a9b}+={a,b,ab,ba9aa,bb, }則L={aa,bb,abba,baab,aaaa,bbbb,^4*所以：A->aaIbbIaAaIbAbEx3:P：S->A|B A->aAb|0 B->aBbb|1求L?解.L（G）={amOb^,amlb2m|m>0}例題：Ex:已知G[N]:N^SEIES^SDIDETOI2I4I6I8I10DTOI1I2I3|……I8I91） 濟明文法是.[義性的；2） 語百L=?3） 找?個等價的無一義性的文法。解：1)找一個句子，使它能夠對應兩棵不同的語法樹，如102)L是所有偶數的集合；|NotE：某一語言可能對應兩個文法，一個無二義，一個有二|義，所以同一語言其對應的文法不唯一口E&已知G[S]:ST(AS)I(b)求符號串(a))和(AUSaAMh)))的短語、也接燦語和旬解：因為—(AS) ((a)S) (a))所以，符號串(a))不是句型，它沒有短語、直接短語和句又因為S=(A)=(AAS：)=(A(A(b)))^(AUSaAHb)))所以，符號$(Aa&iAHb)))是文法G的句型.以第一個S以第一個S為根:以第二個S為根:以第三個s為根:以A為根：3+L(a*)-{s，*…}4+(ab)L(ab)=L(a)uL(b)={a,b}5+(ab)(ab)L(a|b)L(a|b)—{ }6+a?bL(a-b)=L(a)L(b)={ab}7+(ab)*(L(a|b))*={a?b}+第四章練習題(詞法分析)1?第四章練習題(詞法分析)1?正規(guī)式與正規(guī)集止規(guī)式￡*申、A,BA|BABA*止規(guī)集{小{町{縱衣L(A).L(B)L(A|B)=L(A)uL(B)L(AB)=L(A)L(B)L(A*)=(L(A))*2.正規(guī)式的等價性若L(R1)=L(R2)，則R1與R2等價，記為：R1=R2利用等價公式化簡(A|B)*=(A*|B*)*=(A*B*)A*=A*(BA*)*(A*)*=A*A*=AA*|AA*=A*AAA*=A+如果它們的最小化的DFA是相同的，則兩正規(guī)式等價例題：證明：(alb)*=((ela)b*)*DFA與NFA的區(qū)別初態(tài)可不唯一f 一t映射函數JNFAN=(S,X，S0N,嚴F)DFAM=(S,S0D,尸，F)正規(guī)式R->NFA，按如下規(guī)則分裂，直到保證一個唯一的初態(tài)結和唯一的終態(tài)結。注意：一定要一步一步來分裂，不可以跳過每一步?。。。。。。?！

ABABAABA*A分裂為分裂為分裂為例ABABAABA*A分裂為分裂為分裂為例例題：Ex2:R=0(1*)*I01,求NFAo答案：先化簡R,因為(A*)*=A*AIA*=A*所以0(1*)*I01=01*I01=0(1*I1)=01*設I設I是NFA的狀態(tài)子集，定義E-closure(I)：若S^I,貝US丘E-closure(I)；若SEI,則從I出發(fā)經任意條E弧能到達的任意狀態(tài)S',有S'eI；B.確定化NFAN為DFAM已知NFAN=(S,,S0,f,F),令①唯一的初態(tài)x=S0，②唯一的終態(tài)y=F；

例題：解:1)令初始集D為空集，求DFA例題：解:陣。{0,2,1}{0,1}{0,3,1}{0,2,1} B{0,2,1} B{0,2,1} B(0,2,1) B{0,1} 陣。{0,2,1}{0,1}{0,3,1}{0,2,1} B{0,2,1} B{0,2,1} B(0,2,1) B{0,1} c{0,3,1} D{0,1} C{0,y,1} e確定初始狀態(tài)與終態(tài):只要有x即為初態(tài),只要含y的即為終態(tài)。所以A為初態(tài)，E為終態(tài)。根據狀態(tài)轉換矩陣畫DFA,如卜所小。廠ab廠abABCBBDcBCDBEBCBl^a(D>^a‘)bb6.DFA的化簡(最小化DFA)采用分化法步驟：(1)將DFA的狀態(tài)分成兩個子集：終態(tài)集和非終態(tài)集。形成初始分劃n。(2)由分劃算法構造新的分劃直到n中每一狀態(tài)子集不能再分為止。接上題：第一步：形成初始分劃：n=({AR,CR},{E})第二步：由分劃算法構造新的分劃：1)對{A,B,C,D}a輸入a得{B}對{A,B,C}b輸入b得{C,D}，而D輸入b得到E,所以將D劃分出來所以ni=({A,B,C},{D},{E})

2） 對{A,B,C}a輸入{B}對{A,C}b輸入b得到{C},而B輸入b得到D,所以劃分出B所以n2=（{A,C},{B},{D},{E}）3） 對{A,C}a={B}對{A,C}b={C}不能再分劃，說明A、C等價?？蓜h除其中一個，如C,可得如下最小化的DFAExl:B知止規(guī)式R=“Z⑹篤求最小化的DFA。解:算「步，解:算「步，R^NFA（分裂法）。第一〔步，NFA^DFA（了集法）17Id0 {X}17Id0 {X}{12y}1◎l{12y}{2,y} 2{2,y}2'2{2,y}1{2,y} 2 12y}2'=^@第二步，DFAAi小化（分劃法）

第二步，DFAAi小化（分劃法）

n=（{1},丄2}） =對丄2}円2}{1,2}廣{2},說明1、2等價。刪除狀態(tài)2得如下愎小化DFAo解：正規(guī)集L（R）={anbmcl|n,m,l>=1}正規(guī)文法，P：S->aS|aA， A->bA|bB，B->cB|c一、設語言L是由奇數個a和偶數（可以是0）個b組成的符號串之集。課后答案p;花-6⑴￡(即是咖訕的數亍出TrND-WD=>NDDD=>DDDDnODDDrUIDDc。12心二UI27 ?N=■NDnDD=3打=■34NnNDnNDD=DDD=5DD=56D=56S最卅推導:NnND二■N7二A/D7=>NUn,VD27=>Afl：?nD127^i.)：27MrNDrN4rD4r34N=NDnn\D8=A/68=/>68=568P36-7 1G(S)OT113151719TV^21416181(9DtOIJV20AOAADINP36-8文法：E^T\E+T\E-TTfF\T^F\T/FFT(E)lf最左推導：E、E+T->T+T、F+T->i+丁亠i+T*F\i+F*Fui+i姑F=i+i*iEnT=T*FnF*F"*Fni%E)=>i氣E卜T)^i^(T+T)^i^(F+T)ni?r)^i*(i+F)=>i*G+O權右推導：EdE+T=E+F^FdE—T*idE+F*i=E—iBdF+iBdF+i*i=i—i喙E= F*T->LF」F*(E)」F*(E+T)iF^(E+F)F^(E+i)=F*(T十」)二>F*(F十f)二> 十i)二淪(f+)STABSTABAtaAbI￡R―>ciBbIELI:SA\BA^OAllrB^\BO\AP36-11Jj^p?rnLL:StACATuAbIabC.—>■c(2I￡\：1-STABATMIFBtbBcIbe1.3：64頁第六題也要看!確定化:01{1,2,3}巾申M2,3}⑵3}{2t3,4}^3}{2,3}⑵3,4}23,4}{2,3,5}⑵3,1}憶3,5}{2,3}憶3,4,Y}{2.3,4,￥}{2,3,5}23,4,}(j0023000(j51最0023000(j51最小化:0,1,2,3,4,5,{6}0,1,2,3,4,5}。={1,3,5} {0,1,2,3,4,5}]={1,2,4,6}{0,1,2,3,4,{5},{6}{0,1,2,3,4°二{1,3,5}0,1,2,3},{4},5},{6}0,12,3}。={,3} {0,1,2,3}]={1,2,4}0,1,{2,3}{4},{5},{6}{0,1}0={1} {0,1}廣{1,2}{2,3}°={3} {2,3}廣{4}{0},{1},{2,3},{4},{5},{6}P64-8⑴(110)*01(2)(1I2I3I4I5I6I7I819)(01112131415I6171819)*(015)I(015)⑶0*1(0110ftl)'11*0(0110*1/P81-1(1)按照Tj的順序消除左遞歸G\5)￡T胡W)「fS廠2遞歸子程序：pffK'eciureS;begin1lic-ri!)rgl：irl(lVcl\f.C;T;iTsym1)htln\iadvance1

elseerror;en(i(i1.Sf'v'：'：■o'：-pfid:prufeGurc1';h(?gins；r(rid；pro<(?duti'Tf;beginj丨synr,il)eginadvixnce:S;Fendend;其中；叩i:是輸入串指針叩所指的符號advance:是把丁調金卜'-?個輸入符弓error：S錯診察程序(2)FIRST(S)=feT\(]FIRST(T)={a/,()FIRST(D={!T￡}FOLLOW⑸二■!)—#}FOLLOW(T)-D)FOLLOW(廠)打)}預測分析表第二題：E^TEfEJ+EIeT7FT廠tFIfFtPF"FJ*『上P^{E)\a\h\^⑴1rST(E)={(,a,b/}FIRST(ET)={+he}FIRST(T)={(tatb/jFIRSTS)-(C ￡}FIRST(F)={(,a,b,IFTRST(r)=(*,e}FIRST(P)={Gatb/}FOLLOW(E)=(pJ}FOLLOW(EJ)={#,)}FOLLOW(T)={4,),#}FOLLOW(T‘)={+,),#}FOLLOW(F)二{(,a,b/,+,),#}FOLLOttr(F,)={(,d,b,",+,),#}FOLLOW(P)={*,(,a,b/,+,),#}⑵?考慮下列產生式：EJ+El￡r^T\ePT(E)SlalbFIRST(+E)DFIRST(e)={+)D{?}=4>FIRST(+E)QFOLLOW(E')={+}n{#,)}“FIRST(T)PFIRST(€)={(,a,b/}n{e}=4>FIRST(T)AFOLLOW(D={(,a,b/}0{+,),#}=4)FIRST(*F,)AFIRST(e)={*}n{e}=4>FIRST(*F‘)nFOLLOW(F')={*}門{(衛(wèi),b,；+,)，#}=FIRST((E))nFIRST(a)nFIRST(b)nFIRST(*)=<!>所以，該文法式LL(1)文法.⑶+*()abEEtTE'EtTE'EtTE'EfTE、E，E't+EE，T￡E，T￡TT—FTTlFTTtFT'TlFTVT，T￡TJT廠T￡T，tTTJTTJTT，T￡IFFtPF'FtPF'FtPF'FIPF'