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

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

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分，共計20分）1．若源程序是用高級語言編寫的，目標(biāo)程序是機器語言程序或匯編程序，則其翻譯程序稱為編譯程序。2．文法G產(chǎn)生的句子的全體是該文法描述的語言。3．編譯過程中詞法分析所完成的任務(wù)是從源程序中識別出一個個具有獨立意義的單詞。4．基本塊內(nèi)可以進行的優(yōu)化是合并已知量，找出公共表達(dá)式和去除無用賦值。5．一個句型中的最左簡單短語稱為該句型的句柄。二、選擇題（每小題3分，共24分）題號12345678答案ACACCBCB1．編譯程序必須完成的工作有A。（1）詞法分析（2）語法分析（3）語義分析（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．對形如Ux1|x2|……|xn的規(guī)則，要求FIRST(xi)∩FIRST(xj)≠φ(i≠j)B．對形如Ux1|x2|……|xn的規(guī)則，若xiε，則要求FIRST(xj)∩FOLLOW(U)=φC．a(chǎn)和bD．都不是3．若a為終結(jié)符，則Aα·aβ為A項目。A．移入B．待約C．規(guī)約D．接受4．動態(tài)存儲分配時，可以采用的分配方法有C。（1）以過程為單位的棧式動態(tài)存儲分配（2）堆存儲分配（3）最佳分配方法A．（1）B．（2）C．（1）（2）D．（1）（2）（3）5．運行階段的存儲組織與管理的目的是C。（1）提高編譯程序的運行速度（2）提高目標(biāo)程序的運行速度（3）為運行階段的存儲分配作準(zhǔn)備A．（1）（2）B．（1）（3）C．（2）（3）D．（1）（2）（3）三、（14分）對文法G=(VT,VN,S,P)：VT＝{a,b}，VN＝{S,A,B}，開始符號為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）文法？請證實之。解答：文法消除左遞歸、提取公因子后變?yōu)镾aSb|PPbRRPc|QcQaQ’Q’aQ’|ε因為對規(guī)則SaSb|P，有FIRST(aSb)∩FIRST(P)=φ對規(guī)則RPc|Qc，有FIRST(Pc)∩FIRST(Qc)=φ對規(guī)則Q’aQ’|ε，有FIRST(aQ’)∩FOLLOW(Q)=φ所以文法消除左遞歸、提取公因子后是LL（1）文法。五、（14分）設(shè)有文法G(S)：SAAaAbAaAdAε（1）構(gòu)造識別文法規(guī)范句型可歸前綴的DFA。（2）說明文法G是否為SLR（1）文法，為什么？解答：（1）先構(gòu)造增廣文法：S’S0SA1SaAb2SaAd3Aε4文法的識別規(guī)范句型可歸前綴的DFA如圖：（2）該文法是SLR(1)文法。這是因為既不存在“移進-規(guī)約”沖突，也不存在“規(guī)約-規(guī)約”沖突。六、（14分）把下面語句翻譯成四元式序列。if(x>0)and(y>1)thenz:=x+yelsebeginx:=x+2;y:=y+3;end;解答：100(j>,x,0,102)101(j,_,_,107)102(