山東交通學(xué)院成人本科學(xué)歷《編譯原理》復(fù)習(xí)導(dǎo)學(xué)資料

《編譯原理》（A）復(fù)習(xí)題一、填空題（每小題5分，共計(jì)45分）1．如果編譯程序生成的目標(biāo)程序是機(jī)器代碼程序，則源程序的執(zhí)行分為兩大階段：編譯，和運(yùn)行。2．對(duì)編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是目標(biāo)代碼。3．一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分，依次為：一組非終結(jié)符，一組終結(jié)符，一個(gè)開始符，以及一組產(chǎn)生式。4．喬姆斯基（Chomsky）把文法分為四種類型，即0型、1型、2型、3型。其中3型文法又稱為正規(guī)文法。5．算符優(yōu)先分析法每次都是對(duì)最左素短語(yǔ)進(jìn)行規(guī)約。6.不同的編譯程序，有不同的存儲(chǔ)組織方式與分配方案。在大部分的現(xiàn)有編譯程序中采用的方案主要有以下兩種：靜態(tài)存儲(chǔ)方案和動(dòng)態(tài)存儲(chǔ)方案。二、選擇題（每個(gè)選項(xiàng)2分，共計(jì)20分）題號(hào)12345678答案BCCADC(1)B(2)A(3)CD1．一個(gè)語(yǔ)言的文法是B。A．惟一的B．不惟一的C．個(gè)數(shù)有限的2．如果一個(gè)正規(guī)表達(dá)式所代表的集合是無(wú)窮的，則它必含有的運(yùn)算是C。A．連接運(yùn)算“?”B．或運(yùn)算“|”C．閉包運(yùn)算“*”D．括號(hào)“（”和“）”3．一個(gè)句型中的最左C稱為該句型的句柄。A．短語(yǔ)B．素短語(yǔ)C．簡(jiǎn)單短語(yǔ)D．終結(jié)符號(hào)4．在遞歸子程序方法中，如果文法存在左公因子，則會(huì)使分析過(guò)程產(chǎn)生A。A．回溯B．非法調(diào)用C．有限次調(diào)用D．無(wú)限循環(huán)5．表達(dá)式-a+b*(-c+d)的逆波蘭式是D。A．a(chǎn)b+-cd+-*B．a(chǎn)-b+c-d+*C．a(chǎn)-b+c-d+*D．a(chǎn)-bc-d+*+6．動(dòng)態(tài)存儲(chǔ)分配時(shí)，可以采用的分配方法有C。（1）以過(guò)程為單位的棧式動(dòng)態(tài)存儲(chǔ)分配（2）堆存儲(chǔ)分配（3）最佳分配方法A．（1）B．（2）C．（1）（2）D．（1）（2）（3）7．對(duì)于下面的程序：procedurep(x,y,z);beginy:=y+2;z:=z+xend;begina:=4;b:=5;p(a+b,a,a);printaend;若參數(shù)傳遞的辦法分別為：（1）傳名，（2）傳地址，（3）傳值，那么程序執(zhí)行時(shí)所輸出的a分別是（1）B（2）A（3）C。A．15B．17C．4D．138．優(yōu)化的目的是生成D的目標(biāo)代碼。A．運(yùn)行速度較快B．運(yùn)行速度快但占用內(nèi)存空間大C．占用存儲(chǔ)空間較少D．運(yùn)行速度快且占用存儲(chǔ)空間少三、（7分）現(xiàn)有文法G(E)：EET＋|TTTF*|FFF↑|a其中E是文法的開始符號(hào)。求出句型FF↑↑*的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。解答：短語(yǔ)有：F,F↑,F↑↑,FF↑↑*簡(jiǎn)單短語(yǔ)有：F,F↑句柄為F四、（7分）有文法G(A)=（{a,d,e},{A,B},A,P），其中P：AaABe|BaBdB|ε試計(jì)算文法的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，并判斷該文法是否是LL(1)文法。解答：FIRST(A)={a,d}FIRST(B)={d,ε}FOLLOW(A)={$,d}FOLLOW(B)={a,e}因?yàn)镕IRST(aABe)∩FIRST(Ba)=φFIRST(dB)∩FIRST(ε)=φFIRST(dB)∩FOLLOW(B)=φ符合LL(1)文法條件，所以該文法是LL(1)文法。五、（7分）將下面的NFA確定化后畫出狀態(tài)轉(zhuǎn)換圖。解答：由子集法構(gòu)造DFA如表所示：IIaIb{S,3,1}{3,1,5}{3,1,6}{3,1,5}{3,5,2,1,4,Z}{3,1,6}{3,1,6}{3,1,5}{3,6,2,1,4,Z}{3,5,2,1,4,Z}{3,5,2,1,4,Z}{3,6,4,1,Z}{3,6,2,1,4,Z}{3,5,4,1,Z}{3,6,2,1,4,Z}{3,6,4,1,Z}{3,5,4,1,Z}{3,6,2,1,4,Z}{3,5,4,1,Z}{3,5,2,1,4,Z}{3,6,4,1,Z}換名后DFA的映像：IIaIb012132214335464564635所構(gòu)造的DFA相應(yīng)的狀態(tài)圖如下：六、（7分）設(shè)有文法G(S)：SS（S）Sε（1）構(gòu)造識(shí)別文法規(guī)范句型可歸前綴的DFA。（2）這個(gè)文法是LR（0）的嗎？請(qǐng)說(shuō)明理由。解答：（1）先構(gòu)造增廣文法：S’S0SS(S)1Sε2文法的識(shí)別規(guī)范句型可歸前綴的DFA如圖（2）該文法是LR(0)文法。這是因?yàn)?，在識(shí)別可歸前綴DFA的狀態(tài)中，只有一個(gè)狀態(tài)I1有移進(jìn)－歸約“沖突”，但是此狀態(tài)中的歸約項(xiàng)目實(shí)際上是接受項(xiàng)目，在構(gòu)造分析表時(shí)不會(huì)產(chǎn)生沖突。所以，該文法是LR(0)項(xiàng)目。（7分）寫出語(yǔ)句

ifx+1>ytheny:=x+1elsewhilex<y+1dox:=x+1的四元式序列。解答：100（+,x,1,t1）101(j>,t1,y,103)102(j,_,_,106)103(+,x,1,t2)104(:=,t2,_,y)105(j,_,_,112)106(+,y,1,t3)107(j<,x,t3,109)108(j,_,_,112)109(+,x,1,t4)110(:=,t4,_,106)111(j,_,_,106)112《編譯原理》（B）復(fù)習(xí)題一、填空題（每小題2分，共計(jì)20分）1．若源程序是用高級(jí)語(yǔ)言編寫的，目標(biāo)程序是機(jī)器語(yǔ)言程序或匯編程序，則其翻譯程序稱為編譯程序。2．文法G產(chǎn)生的句子的全體是該文法描述的語(yǔ)言。3．編譯過(guò)程中詞法分析所完成的任務(wù)是從源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的單詞。4．基本塊內(nèi)可以進(jìn)行的優(yōu)化是合并已知量，找出公共表達(dá)式和去除無(wú)用賦值。5．一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱為該句型的句柄。二、選擇題（每小題3分，共24分）題號(hào)12345678答案ACACCBCB1．編譯程序必須完成的工作有A。（1）詞法分析（2）語(yǔ)法分析（3）語(yǔ)義分析（4）代碼生成（5）中間代碼生成（6）代碼優(yōu)化A．(1)(2)(3)(4)B．(1)(2)(3)(4)(5)C．(1)(2)(3)(4)(5)(6)D．(1)(2)(3)(4)(6)2．LL（1）文法的條件是C。A．對(duì)形如Ux1|x2|……|xn的規(guī)則，要求FIRST(xi)∩FIRST(xj)≠φ(i≠j)B．對(duì)形如Ux1|x2|……|xn的規(guī)則，若xiε，則要求FIRST(xj)∩FOLLOW(U)=φC．a(chǎn)和bD．都不是3．若a為終結(jié)符，則Aα·aβ為A項(xiàng)目。A．移入B．待約C．規(guī)約D．接受4．動(dòng)態(tài)存儲(chǔ)分配時(shí)，可以采用的分配方法有C。（1）以過(guò)程為單位的棧式動(dòng)態(tài)存儲(chǔ)分配（2）堆存儲(chǔ)分配（3）最佳分配方法A．（1）B．（2）C．（1）（2）D．（1）（2）（3）5．運(yùn)行階段的存儲(chǔ)組織與管理的目的是C。（1）提高編譯程序的運(yùn)行速度（2）提高目標(biāo)程序的運(yùn)行速度（3）為運(yùn)行階段的存儲(chǔ)分配作準(zhǔn)備A．（1）（2）B．（1）（3）C．（2）（3）D．（1）（2）（3）三、（14分）對(duì)文法G=(VT,VN,S,P)：VT＝{a,b}，VN＝{S,A,B}，開始符號(hào)為SP：SaB|bAAaS|bAA|aBbS|aBB|b給出串a(chǎn)aabbabbba的（1）最左推導(dǎo)；（2）最右推導(dǎo)；（3）推導(dǎo)樹。解答：（1）最左推導(dǎo)為：S==>aB=>aaBB=>aaaBBB=>aaabSBB=>aaabbABB=>aaabbaBB=>aaabbabB=>aaabbabbS=>aaabbabbbA=>aaabbabbba（2）最右推導(dǎo)為：S==>aB=>aaBB=>aaBbS=>aaBbbA=>aaBbba=>aaaBBbba=>aaaBbbba=>aaabSbbba=>aaabbAbbba=>aaabbabbba（3）推導(dǎo)樹為：四、（14分）給出文法G（S）={（a,b,c），（S,P,Q），S，P}，P：SaSb|PPbPc|bQcQQa|a文法消除左遞歸、提取公因子后是不是LL（1）文法？請(qǐng)證實(shí)之。解答：文法消除左遞歸、提取公因子后變?yōu)镾aSb|PPbRRPc|QcQaQ’Q’aQ’|ε因?yàn)閷?duì)規(guī)則SaSb|P，有FIRST(aSb)∩FIRST(P)=φ對(duì)規(guī)則RPc|Qc，有FIRST(Pc)∩FIRST(Qc)=φ對(duì)規(guī)則Q’aQ’|ε，有FIRST(aQ’)∩FOLLOW(Q)=φ所以文法消除左遞歸、提取公因子后是LL（1）文法。五、（14分）設(shè)有文法G(S)：SAAaAbAaAdAε（1）構(gòu)造識(shí)別文法規(guī)范句型可歸前綴的DFA。（2）說(shuō)明文法G是否為SLR（1）文法，為什么？解答：（1）先構(gòu)造增廣文法：S’S0SA1SaAb2SaAd3Aε4文法的識(shí)別規(guī)范句型可歸前綴的DFA如圖：（2）該文法是SLR(1)文法。這是因?yàn)榧炔淮嬖凇耙七M(jìn)-規(guī)約”沖突，也不存在“規(guī)約-規(guī)約”沖突。六、（14分）把下面語(yǔ)句翻譯成四元式序列。if(x>0)and(y>1)thenz:=x+yelsebeginx:=x+2;y:=y+3;end;解答：100(j>,x,0,102)101(j,_,_,107)102(