編譯原理練習(xí)及答案

第一章練習(xí)題（緒論）一、選擇題編譯程序是一種常用的 B—軟件。A）應(yīng)用 B）系統(tǒng) C）實(shí)時(shí)系統(tǒng)D）分布式系統(tǒng)編譯程序生成的目標(biāo)代碼程序 B 是可執(zhí)行程序。A）—定 B）不一定編譯程序的大多數(shù)時(shí)間是花在D—上。A）詞法分析B）語法分析 C）出錯(cuò)處理D）表格管理將編譯程序分成若干“遍”將 B。A） 提咼編譯程序的執(zhí)行效率；B） 使編譯程序的結(jié)構(gòu)更加清晰，提高目標(biāo)程序質(zhì)量；C） 充分利用內(nèi)存空間，提咼機(jī)器的執(zhí)行效率。編譯程序各個(gè)階段都涉及到的工作有D。A）詞法分析B）語法分析 C）語義分析D）表格管理詞法分析的主要功能是 。A）識(shí)別字符串B）識(shí)別語句C）識(shí)別單詞 D）識(shí)別標(biāo)識(shí)符若某程序設(shè)計(jì)語言允許標(biāo)識(shí)符先使用后說明，則其編譯程序就必須A 。A）多遍掃描 B）一遍掃描編譯方式與解釋方式的根本區(qū)別在于B。A）執(zhí)行速度的快慢 B）是否生成目標(biāo)代碼C）是否語義分析多遍編譯與一遍編譯的主要區(qū)別在于D 。A） 多遍編譯是編譯的五大部分重復(fù)多遍執(zhí)行，而一遍編譯是五大部分只執(zhí)行一遍；B） 一遍編譯是對(duì)源程序分析一遍就立即執(zhí)行，而多遍編譯是對(duì)源程序重復(fù)多遍分析再執(zhí)行；C） 多遍編譯要生成目標(biāo)代碼才執(zhí)行，而一遍編譯不生成目標(biāo)代碼直接分析執(zhí)行；D） 多遍編譯是五大部分依次獨(dú)立完成，一遍編譯是五大部分交叉調(diào)用執(zhí)行完成。編譯程序分成“前端”和“后端”的好處是DA） 便于移植B） 便于功能的擴(kuò)充C） 便于減少工作量D） 以上均正確第二章練習(xí)題（文法與語言）1、直接推導(dǎo)、＋推導(dǎo)、＊推導(dǎo)2、句型和句子，文法定義（搞清楚）G=（VT,VN,S,P）3、語言的形式定義： L（G[S]）={xIS->x且xGVT*}若L是無窮的，則G一定是遞歸的4、 最左推導(dǎo)、最右推導(dǎo)（規(guī)范推導(dǎo)）5、 歸約、規(guī)范歸約6、 遞歸：規(guī)則遞歸、文法遞歸（1） A->BAe->CA,???（2） A->B,B->CA,???文法的等價(jià)性：G1=G2（1）每棵子樹的葉子組成一個(gè)短語；（2） 每棵簡(jiǎn)單子樹的葉子組成一個(gè)直接短語；簡(jiǎn)單子樹：只有單層分支的子樹（3） 最左邊簡(jiǎn)單子樹的葉子是句柄一個(gè)句型不一定只對(duì)應(yīng)一棵唯一的語法樹。如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)二棵不同的語法樹或者二個(gè)不同的最左（右）推導(dǎo)，則這個(gè)文法是二義性的歸約是推導(dǎo)的逆過程。即：將句型中的某一子串用一串非終結(jié)符代替的過程。若有A->a則XAY->XaY,于是XaY->XAY。稱規(guī)范（最右）推導(dǎo)的逆過程為規(guī)范歸約（先歸約最左那一串（不是一個(gè)）符號(hào)）。規(guī)范歸約：先歸約最左那一串（不是一個(gè)）符號(hào)。1）文法的開始符一定寫在文法的前面（第一條規(guī)則式中）；2） e是表示空符號(hào)串，不是終結(jié)符；3） L是語言，不要用作非終結(jié)符；4） 文法的完整表示是G=（VT,VN,S,P）一、選擇題文法G產(chǎn)生的D 的全體是該文法描述的語言。A.句型B.終結(jié)符集C.非終結(jié)符集D.句子若文法G定義的語言是無限集，則文法必然是AA遞歸的B上下文無關(guān)的C二義性的D無二義性的Chomsky定義的四種形式語言文法中，0型文法又稱為A文法;1型文法又稱為C文法；2型語言可由G_識(shí)別。A短語結(jié)構(gòu)文法B上下文無關(guān)文法C上下文有關(guān)文法D正規(guī)文法E圖靈機(jī)F有限自動(dòng)機(jī)G下推自動(dòng)機(jī)一個(gè)文法所描述的語言是A；描述一個(gè)語言的文法是BA唯一的B不唯一的C可能唯一，也可能不唯一二、構(gòu)造文法以生成下列語言：{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是不含兩個(gè)相鄰1的0、1串}解：G=({S,A},{0,1},S,P),其中P={S-0|1|OS|1A,A—OS|0}5．能被5整除的整數(shù)集合。解：G[S]:S->FNCF->+I-IEC->0|5N->AMIE M->0IAIEA->1I2I3I4I5I6I7I8I9Ex1:設(shè)E={a,b},試設(shè)計(jì)一個(gè)文法G,定義語言L={a2n,b2nIn>1}解：G[A]：A->BIDB->aaIaBaD->bbIbDbEx3：設(shè)計(jì)一個(gè)表示所有標(biāo)識(shí)符I的文法。解：G[I]：I->LIILDL->a|b|c z|A|B|C |ZED->1|2|3 |9|E&設(shè)G[E]：E->E+EIE*E|(E)|i,試證明符號(hào)串(i*i+i)是文法G[E]的一個(gè)句子證明：從E出發(fā)，只要證明符號(hào)串x=(i*i+i)對(duì)于文法G[E]存在一個(gè)推導(dǎo)。E->(E)->(E+E)->(E＊E+E)->(i*E+E)->(i*i+E)->(i*i+i)以上從文法的開始符E->(i*i+i)，所以符號(hào)串(i*i+i)是G[E]的一個(gè)句子。Ex:已知:S->ABA->AaIbBB->aISb,給出句子babaab的最左、最右推導(dǎo)解：最左：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。解：因?yàn)閤={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） 濟(jì)明文法是.[義性的；2） 語百L=?3） 找?個(gè)等價(jià)的無一義性的文法。解：1)找一個(gè)句子，使它能夠?qū)?yīng)兩棵不同的語法樹，如102)L是所有偶數(shù)的集合；|NotE：某一語言可能對(duì)應(yīng)兩個(gè)文法，一個(gè)無二義，一個(gè)有二|義，所以同一語言其對(duì)應(yīng)的文法不唯一口E&已知G[S]:ST(AS)I(b)求符號(hào)串(a))和(AUSaAMh)))的短語、也接燦語和旬解：因?yàn)椤?AS) ((a)S) (a))所以，符號(hào)串(a))不是句型，它沒有短語、直接短語和句又因?yàn)镾=(A)=(AAS：)=(A(A(b)))^(AUSaAHb)))所以，符號(hào)$(Aa&iAHb)))是文法G的句型.以第一個(gè)S以第一個(gè)S為根:以第二個(gè)S為根:以第三個(gè)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}+第四章練習(xí)題(詞法分析)1?第四章練習(xí)題(詞法分析)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ī)式的等價(jià)性若L(R1)=L(R2)，則R1與R2等價(jià)，記為：R1=R2利用等價(jià)公式化簡(jiǎn)(A|B)*=(A*|B*)*=(A*B*)A*=A*(BA*)*(A*)*=A*A*=AA*|AA*=A*AAA*=A+如果它們的最小化的DFA是相同的，則兩正規(guī)式等價(jià)例題：證明：(alb)*=((ela)b*)*DFA與NFA的區(qū)別初態(tài)可不唯一f 一t映射函數(shù)JNFAN=(S,X，S0N,嚴(yán)F)DFAM=(S,S0D,尸，F(xiàn))正規(guī)式R->NFA，按如下規(guī)則分裂，直到保證一個(gè)唯一的初態(tài)結(jié)和唯一的終態(tài)結(jié)。注意：一定要一步一步來分裂，不可以跳過每一步?。。。。。。?！

ABABAABA*A分裂為分裂為分裂為例ABABAABA*A分裂為分裂為分裂為例例題：Ex2:R=0(1*)*I01,求NFAo答案：先化簡(jiǎn)R,因?yàn)?A*)*=A*AIA*=A*所以0(1*)*I01=01*I01=0(1*I1)=01*設(shè)I設(shè)I是NFA的狀態(tài)子集，定義E-closure(I)：若S^I,貝US丘E-closure(I)；若SEI,則從I出發(fā)經(jīng)任意條E弧能到達(dá)的任意狀態(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)。根據(jù)狀態(tài)轉(zhuǎn)換矩陣畫DFA,如卜所小。廠ab廠abABCBBDcBCDBEBCBl^a(D>^a‘)bb6.DFA的化簡(jiǎn)(最小化DFA)采用分化法步驟：(1)將DFA的狀態(tài)分成兩個(gè)子集：終態(tài)集和非終態(tài)集。形成初始分劃n。(2)由分劃算法構(gòu)造新的分劃直到n中每一狀態(tài)子集不能再分為止。接上題：第一步：形成初始分劃：n=({AR,CR},{E})第二步：由分劃算法構(gòu)造新的分劃：1)對(duì){A,B,C,D}a輸入a得{B}對(duì){A,B,C}b輸入b得{C,D}，而D輸入b得到E,所以將D劃分出來所以ni=({A,B,C},{D},{E})

2） 對(duì){A,B,C}a輸入{B}對(duì){A,C}b輸入b得到{C},而B輸入b得到D,所以劃分出B所以n2=（{A,C},{B},{D},{E}）3） 對(duì){A,C}a={B}對(duì){A,C}b={C}不能再分劃，說明A、C等價(jià)?？蓜h除其中一個(gè)，如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}） =對(duì)丄2}円2}{1,2}廣{2},說明1、2等價(jià)。刪除狀態(tài)2得如下愎小化DFAo解：正規(guī)集L（R）={anbmcl|n,m,l>=1}正規(guī)文法，P：S->aS|aA， A->bA|bB，B->cB|c一、設(shè)語言L是由奇數(shù)個(gè)a和偶數(shù)（可以是0）個(gè)b組成的符號(hào)串之集。課后答案p;花-6⑴￡(即是咖訕的數(shù)亍出TrND-WD=>NDDD=>DDDDnODDDrUIDDc。12心二UI27 ?N=■NDnDD=3打=■34NnNDnNDD=DDD=5DD=56D=56S最卅推導(dǎo):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最左推導(dǎo)：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權(quán)右推導(dǎ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:是輸入串指針叩所指的符號(hào)advance:是把丁調(diào)金卜'-?個(gè)輸入符弓error：S錯(cuò)診察程序(2)FIRST(S)=feT\(]FIRST(T)={a/,()FIRST(D={!T￡}FOLLOW⑸二■!)—#}FOLLOW(T)-D)FOLLOW(廠)打)}預(yù)測(cè)分析表第二題：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/,+,),#}⑵?考慮下列產(chǎn)生式：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'