編譯原理復習題及答案(共20頁)

1、編譯(biny)原理復習(fx)題及答案(d n)選擇題一個正規(guī)語言只能對應(B)A 一個正規(guī)文法B 一個最小有限狀態(tài)自動機文法GA：A AaB BAb Ba是(A)A 正規(guī)文法B 二型文法下面說法正確的是(A)A 一個SLR（1）文法一定也是LALR（1）文法B 一個LR（1）文法一定也是LALR（1）文法一個上下文無關(guān)文法消除了左遞歸，提取了左公共因子后是滿足LL（1）文法的(A)A 必要條件B 充分必要條件下面說法正確的是(B)A 一個正規(guī)式只能對應一個確定的有限狀態(tài)自動機B 一個正規(guī)語言可能對應多個正規(guī)文法算符優(yōu)先分析與規(guī)范歸約相比的優(yōu)點是(A)A 歸約速度快B 對文法限制少一個LR（

2、1）文法合并同心集后若不是LALR（1）文法(B)A 則可能存在移進/歸約沖突B 則可能存在歸約/歸約沖突C 則可能存在移進/歸約沖突和歸約/歸約沖突下面說法正確的是(A)A Lex是一個詞法分析器的生成器B Yacc是一個語法分析器下面說法正確的是(A)A 一個正規(guī)文法也一定是二型文法B 一個二型文法也一定能有一個等價的正規(guī)文法編譯原理是對(C)。A、機器語言的執(zhí)行B、匯編語言的翻譯C、高級語言的翻譯D、高級語言程序的解釋執(zhí)行(A)是一種典型的解釋型語言。ABASICBCCFORTRANDPASCAL把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由(B)完成的。A. 編譯器B. 匯編器C.

3、 解釋器D. 預處理器用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫(B)A源程序B目標程序C連接程序D解釋程序(C)不是編譯程序的組成部分。A.詞法分析程序B.代碼生成程序C.設(shè)備管理程序D.語法分析程序通常一個編譯程序中，不僅包含詞法分析，語法分析，語義分析，中間代碼生成，代碼優(yōu)化，目標代碼生成等六個部分，還應包括(C)。A模擬(mn)執(zhí)行器B解釋器C表格處理(chl)和出錯處理 D符號執(zhí)行器編譯程序(bin y chn x)絕大多數(shù)時間花在(D)上。A出錯處理B詞法分析C目標代碼生成D表格管理源程序是句子的集合，(B)可以較好地反映句子的結(jié)構(gòu)。A. 線性表B. 樹C. 完全圖D. 堆棧詞法分析

4、器的輸出結(jié)果是(D)。A、單詞自身值B、單詞在符號表中的位置C、單詞的種別編碼D、單詞的種別編碼和自身值詞法分析器不能(D)A. 識別出數(shù)值常量B. 過濾源程序中的注釋C. 掃描源程序并識別記號D. 發(fā)現(xiàn)括號不匹配文法：G：SxSx | y所識別的語言是(D)。A、xyxB、(xyx)*C、x*yx*D、xnyxn (n0)如果文法G是無二義的，則它的任何句子(A)A最左推導和最右推導對應的語法樹必定相同B最左推導和最右推導對應的語法樹可能不同C最左推導和最右推導必定相同D可能存在兩個不同的最左推導，但它們對應的語法樹相同正則文法(A)二義性的。A. 可以是B. 一定不是C. 一定是(B)這樣

5、一些語言，它們能被確定的有窮自動機識別，但不能用正則表達式表示。A. 存在B. 不存在C. 無法判定是否存在給定文法AbA | ca，為該文法句子的是(C)A. bbaB. cabC. bcaD. cba設(shè)有文法GS：SS1|S0|Sa|Sc|a|b|c，下列符號串中是該文法的句子有(D)A. ab0B. a0c01C. a0b0aD. bc10文法G產(chǎn)生的(D)的全體是該文法描述的語言。A句型B. 終結(jié)符集C. 非終結(jié)符集D.句子若文法G定義的語言是無限集，則文法必然是(A)A遞歸的B. 上下文無關(guān)的C. 二義性的D. 無二義性的描述一個語言的文法是(B)A唯一的B. 不唯一的C. 可能唯一

6、一個(y )文法所描述的語言是(A)A唯一(wi y)的B. 不唯一(wi y)的C. 可能唯一采用自上而下分析，必須(A)。A、消除回溯B、消除左遞歸C、消除右遞歸D、提取公共左因子編譯過程中，語法分析器的任務是(A)分析單詞的構(gòu)成分析單詞串如何構(gòu)成語句分析語句是如何構(gòu)成程序分析程序的結(jié)構(gòu)A. B. C. D. 詞法分析器的輸入是( A)。A符號串 B源程序 C語法單位 D目標程序兩個有窮自動機等價是指它們的(C)。A狀態(tài)數(shù)相等 B有向弧數(shù)相等C所識別的語言相等D狀態(tài)數(shù)和有向弧數(shù)相等若狀態(tài)k含有項目“A ”，且僅當輸入符號aFOLLOW(A)時，才用規(guī)則“A ”歸約的語法分析方法是(D)。A

7、LALR分析法BLR(0)分析法CLR(1)分析法 DSLR(1)分析法若a為終結(jié)符，則A a為(B)項目。A歸約B移進C接受D待約在使用高級語言編程時,首先可通過編譯程序發(fā)現(xiàn)源程序的全部和部分(A)錯誤。A. 語法B. 語義C. 語用D. 運行喬姆斯基(Chomsky)把文法分為四種類型，即0型、1型、2型、3型。其中3型文法是(B)A. 非限制文法B. 正則文法C. 上下文有關(guān)文法D. 上下文無關(guān)文法一個句型中的(A)稱為該句型的句柄。A. 最左直接短語B. 最右直接短語C. 終結(jié)符D. 非終結(jié)符在自底向上的語法分析方法中，分析的關(guān)鍵是(D)A. 尋找句柄B. 尋找句型C. 消除遞歸D.

8、選擇候選式在自頂向下的語法分析方法中，分析的關(guān)鍵是(C)A. 尋找句柄B. 尋找句型C. 消除遞歸D. 選擇候選式在LR分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型(C)的DFA狀態(tài)。A.句柄B. 前綴C. 活前綴D. LR(0)項目一個(y )上下文無關(guān)文法G包括四個組成部分，它們是一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組(B)A. 句子B. 產(chǎn)生(chnshng)式C. 單詞D. 句型詞法(cf)分析器用于識別(C)A. 句子B. 產(chǎn)生式C. 單詞D. 句型編譯程序是一種(B)A. 匯編程序B. 翻譯程序C. 解釋程序D. 目標程序按邏輯上劃分，編譯程序第三步工作是(A)A. 語

9、義分析B. 詞法分析C. 語法分析D. 代碼生成在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合均是(B)A. 非終結(jié)符集B.終結(jié)符集C. 字母表D. 狀態(tài)集編譯程序中語法分析器接收以(A)為單位的輸入。A. 單詞B. 表達式C. 產(chǎn)生式D. 句子編譯過程中，語法分析器的任務就是(B)A. 分析單詞是怎樣構(gòu)成的B. 分析單詞串是如何構(gòu)成語句和說明的C. 分析語句和說明是如何構(gòu)成程序的D. 分析程序的結(jié)構(gòu)若一個文法是遞歸的，則它所產(chǎn)生的語言的句子(A)。A.是無窮多個B.是有窮多個C.是可枚舉的D.個數(shù)是常量識別上下文無關(guān)語言的自動機是(C)A. 下推自動機B. NFAC. DFAD. 圖靈機

10、編譯原理各階段工作都涉及(B)A.詞法分析B.表格管理C.語法分析D.語義分析正則表達式R1和R2等價是指(C)A. R1和R2都是定義在一個字母表上的正則表達式B. R1和R2中使用的運算符相同C. R1和R2代表同一正則集D. R1和R2代表不同正則集已知文法GS:SA1， AA1|S0|0。與G 等價的正規(guī)式是(C)A. 0(0|1)*B. 1*|0*1C. 0(1|10)*1D. 1(10|01)*0與(a|b)*(a|b)等價的正規(guī)式是(C)。A.a*| b*B.(ab)*(a|b)C. (a|b)(a|b)*D.(a|b)*(D)文法不是LL(1)的。A. 遞歸B. 右遞歸C. 2

11、型D.含有(hn yu)公共左因子的給定(i dn)文法AbA|cc，則符號串cc bcbc bcbcc bccbcc bbbcc中，是該文法(wnf)句子的是(D)A. B. C. D. LR(1)文法都是()A. 無二義性且無左遞歸B. 可能有二義性但無左遞歸C. 無二義性但可能是左遞歸D. 可以既有二義性又有左遞歸文法EE+E|E*E|i的句子i*i+i*i有(C)棵不同的語法樹。A. 1B. 3C. 5D.7文法 SaaS|abc 定義的語言是(C)。A.a2kbc|k0B.akbc|k0C.a2k-1bc|k0D.akakbc|k0若B為非終結(jié)符，則 A.B 為(D)。A.移進項目B

12、.歸約項目C.接受項目D.待約項目同心集合并可能會產(chǎn)生新的(D)沖突。A.二義B.移進/移進C.移進/歸約D.歸約/歸約就文法的描述能力來說，有(C)ASLR(1) LR(0)BLR(1) LR(0)CSLR(1) LR(1)D無二義文法 LR(1)如圖所示自動機M，請問下列哪個字符串不是M所能識別的(D)。A. bbaaB. abbaC. ababD. aabb有限狀態(tài)自動機能識別(C)A.上下文無關(guān)語言B.上下文有關(guān)語言C.正規(guī)語言D.0型文法定義的語言已知文法G是無二義的，則對G的任意句型(A)A.最左推導和最右推導對應的語法樹必定相同B.最左推導和最右推導對應的語法樹可能相同C.最左推

13、導和最右推導必定相同D.可能存在兩個不同的最左推導，但他們對應的語法樹相同(B)不是(b shi)DFA的成分A.有窮字母表B.多個(du )初始狀態(tài)的集合C.多個終態(tài)的集合D.轉(zhuǎn)換函數(shù)與逆波蘭(b ln)式(后綴表達式)ab+c*d+對應的中綴表達式是(B)A. a+b+c*dB. (a+b)* c+dC. (a+b)* (c+d)D. a+b*c+d后綴式abc+d+可用表達式(B)來表示。A( (a+b)c)+d B(a+(bc)+d C (a(b+c)+d D(a(b+c)+d表達式A*(B-C*(C/D)的后綴式為(B)。AABC-CD/* BABCCD/*-* CABC-*CD/*

14、 D以上都不對(D)不是NFA的成分。A. 有窮字母表B. 初始狀態(tài)集合C. 終止狀態(tài)集合D. 有限狀態(tài)集合問答題將文法GS 改寫為等價的GS，使GS不含左遞歸和左公共因子。GS： SbSAe | bA AAb | d答：文法GS 改寫為等價的不含左遞歸和左公共因子的GS為：SbB BSAe | AAd A A bA | 將文法GS 改寫為等價的GS，使GS不含左遞歸和左公共因子。GS： SSAe|Ae AdAbA|dA|d答：文法GS 改寫為等價的不含左遞歸和左公共因子的GS為： S AeSS AeS| A dA A AB| B bA | 將文法GS 改寫為等價的GS，使GS不含左遞歸和左公

15、共因子。GS： SA AB|AS BaB|a答：文法GS 改寫為等價的不含左遞歸和左公共因子的GS為：S AA BAASA|B aBBB|判斷下面文法是否為LL(1)文法，若是,請構(gòu)造相應(xingyng)的LL(1)分析表。SaHHaMd | dMAb | AaM | e答：首先(shuxin)計算文法的 FIRST集和FOLLOW集如下表。文法的 FIRST集和FOLLOW集 非終結(jié)符FIRST集FOLLOW集Sa.# .Ha ，d.# .Ma ，e ，d ，bAa ，e.b.由于(yuy)predict（HaMd）predict（Hd）=ad = predict（MAb）predict（

16、M）=a ，ed ，b = predict（AaM）predict（Ae）= a e = 所以該文法是LL(1)文法，LL(1)分析表如下表。adbe#SaH.HaMdd.MAb.AbAaM.e.判斷下面文法是否為LL(1)文法，若是，請構(gòu)造相應的LL(1)分析表。SaDDSTe|TbH|HHd|答：首先計算文法的 FIRST集和FOLLOW集如下表。 非終結(jié)符FIRST集FOLLOW集Sa#，b，d，e.Da，#，b，d，e Tb，d，eHd，e由于predict（DSTe）predict（D）=a# ，b ，d ，e =predict（TbH）predict（TH）=be =predict

17、（Hd）predict（H）= d e =所以該文法是LL(1)文法，LL(1)分析表如下表：aebd#SaD.DSTeTH.bHH.Hd.判斷下面(xi mian)文法是否為LL(1)文法，若是，請構(gòu)造相應的LL(1)分析表。SaDDSTe|TbMMbHHM|答：文法(wnf)的 FIRST集和FOLLOW集非終結(jié)符FIRST集FOLLOW集Sa.# ，bDa ，# ，bTb.e.Mb.e.Hb ，e.由于(yuy)predict（DSTe）predict（D）=a# ，b=predict（HM）predict（H）= b e =所以該文法是LL(1)文法，LL(1)分析表如下表：aeb#S

18、aD.DSTeTbMMbHHM.某語言的拓廣文法G為：(0) SS(1) S Db|B(2) D d|(3) B Ba|證明G不是LR(0)文法而是SLR(1)文法，請給出SLR(1)分析表。答：拓廣文法G，增加產(chǎn)生式SS在項目集I0中：有移進項目D d 歸約項目D 和B 存在移進-歸約和歸約-歸約沖突，所以G不是LR(0)文法。若產(chǎn)生式排序為：(0) SS(1) S Db(2) S B(3) D d(4) D (5) B Ba(6) B G的LR(0)項目集族及識別活前綴(qinzhu)的DFA如下圖：由產(chǎn)生(chnshng)式知Follow(S)=# Follow(D)= bFollow(

19、B)= a ,#在I0中:Follow(D) d= b d=Follow(B) d= a ,# d=Follow(D) Follow(B)= ba ,# =在I3中:Follow(S) a=#a=所以(suy)在I0，I3中的移進-歸約和歸約-歸約沖突可以由Follow集解決,所以G是SLR(1)文法, 構(gòu)造的SLR(1)分析表如下表：狀態(tài)ACTIONGOTObda#SDB0r4S4r6r61231acc2S53S6r24r35r16r5r5給出與正規(guī)式R（ab）*（a|b*）ba等價的NFA。答：與正規(guī)式R等價的NFA如下圖給出與正規(guī)(zhnggu)式R（(ab)*|b）*（a|(ba)*）

20、a 等價(dngji)的NFA。答：與正規(guī)式R等價(dngji)的NFA如下圖給出與正規(guī)式 R（aba）*（(ba)*|b）b等價的NFA。答：與正規(guī)式R等價的NFA如下圖將下圖的NFA確定化為DFA。答：用子集法確定化如下表IIaIb狀態(tài)X,1,21,2.1,2,31,2,Y1,2.1,2.1,2,Y1,2.1,2,31,2,31,2,31,2,3X123確定化后如下圖：將下圖的NFA確定化為DFA。答：用子集(z j)法確定化如下表IIaIb狀態(tài)X,0,1,30,1,3.2,3,Y.1,3.2,Y.Y.0,1,30,1,31,3.1,3.2,3,Y2,3,YY.2,Y.Y.X1234Y確定

21、(qudng)化后如下圖某語言(yyn)的拓廣文法G為：(0) ST (1) T aBd|(2) B Tb| 證明G不是LR(0)文法而是SLR(1)文法，請給出SLR(1)分析表。答：拓廣文法G，增加產(chǎn)生式ST 在項目集I0中：有移進項目T aBd和歸約項目T 存在移進-歸約沖突，所以G不是LR(0)文法。 若產(chǎn)生式排序為： (0) ST(1) T aBd(2) T (3) B Tb(4) B G的LR(0)項目集族及識別活前綴的DFA如下圖所示：識別G活前綴的DFA由產(chǎn)生(chnshng)式知：Follow(T)=#,b Follow(B)= d在I0中： Follow(T) a=# ，b

22、 a=在I2中：Follow(B) a= d a=Follow(T) a=# ，b a=Follow(B) Follow(T) = d# ，b=所以(suy)在I0，I2，中的移進-歸約和歸約-歸約沖突可以(ky)由Follow集解決，所以G是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下表。SLR(1)分析表nameACTIONGOTOabd#TB0S2r2r211acc2S2r2r4r2433S54S65r1r16r3某語言的文法G為： E aTd| T Eb|a證明G不是LR(0)文法而是SLR(1)文法，請給出該文法的SLR(1)分析表。答：拓廣文法G，增加產(chǎn)生式SE在項目集I0中：

23、 有移進項目E aTd和歸約項目E 存在移進-歸約沖突，所以G不是LR(0)文法。 .若產(chǎn)生(chnshng)式排序為：(0) SE (1) E aTd (2) E (3) T Eb (4) T aG的LR(0)項目集族及識別(shbi)活前綴的DFA如下圖：由產(chǎn)生(chnshng)式知：Follow(E)=# ，b Follow(T)= d在I0 ，I2中:Follow(E) a=# ，b a=在I5 中:Follow(E) a=# ，b a=Follow(T) a= d a=Follow(T) Follow(E) = d # ，b=所以在I0 ， I2 ， I5中的移進-歸約和歸約-歸約沖

24、突可以由Follow集解決,所以G是SLR(1)文法。構(gòu)造的SLR(1)分析表如下表：nameACTIONGOTOabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r2436r1r17r3給出文法GS的LR(1)項目(xingm)集規(guī)范族中I0項目(xingm)集的全體項目。GS為： S BD|D B aD|b D BI0:答：I0：給出文法GS的LR(1)項目(xingm)集規(guī)范族中I0項目集的全體項目。GS為： S D;D|D D DB|B B a|bI0:答：I0:給出文法GS的LR(1)項目集規(guī)范族中I0項目集的全體項目。GS為： S S;V|V V Va

25、A|A A b(S)| I0:答：I0:文法GM及其LR分析(fnx)表如下，請給出對串dbba#的分析過程。GM: 1) M VbA2) V d3) V 4) A a5) A Aba6) A nameACTIONGOTObda#MAV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：對串dbba#的分析(fnx)過程如下表步驟狀態(tài)棧文法符號棧剩余輸入符號動作12345678900302024024602467024678024601#d#V#Vb#VbA#VbAb#VbAba#VbA#Mdbba#bba#bba#ba#ba#a#移進用V d歸約移進用

26、A 歸約移進移進用A Aba 歸約用M VbA 歸約接受文法(wnf)GS及其LR分析表如下，請給出對輸入串da;aoa#的分析過程。GS: 0) SS1) SdSoS2) S dS3) S S;S 4) S a nameACTIONGOTOda;a#S0S2S3S311S4acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1S4r1答：輸入(shr)串da;aoa#的分析過程(guchng)如下表：步驟狀態(tài)棧文法符號棧剩余輸入符號動作123456789101112 002023025025402543025460250257025730257801#d#

27、da#dS#dS;#dS;a#dS;S#dS#dSo#dSoa#dSoS#Sda;aoa#a;aoa#;aoa#;aoa#aoa#oa #oa #oa #a #移進移進用S a 歸約移進移進用S a 歸約用S S;S 歸約移進移進用S a 歸約用SdSoS 歸約接受文法GM及其LR分析表如下，請給出對串dada#的分析過程。GM: 1) S VdB2) V e3) V 4) B a 5) B Bda6) B 狀態(tài)ACTIONGOTOdea#SBV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：對串dada#的分析(fnx)過程如下表步驟狀態(tài)棧文法符號

28、棧剩余輸入符號動作1234567890020240245024602467024678024601#V#Vd#Vda#VdB#VdBd#VdBda#VdB#Sdada#dada#ada#da#da#a#用V 歸約移進移進用B a歸約移進移進用B Bda 歸約用S VdB 歸約接受文法(wnf)GE為： EE+T|T TT*F|F F(E)|i試給出句型(j xn)(E+F)*i的短語，簡單(直接)短語,句柄和最左素短語。答：短語有: (E+F)*i ，(E+F) ，E+F ，F(xiàn) ，i 簡單(直接)短語有：F ，i 句柄是：F最左素短語是：E+F文法GS為：SV VT | ViT TF| T+F

29、F)V* |( 試給出句型ViFi( 的短語，簡單(直接)短語,句柄和最左素短語。答：短語有: ViFi( ，ViF ， F ，(簡單(直接)短語有: F ，( 句柄是: F 最左素短語是: ViF文法GS為：SSdT | TTTG | GG(S) | a試給出句型(SdG)a的短語、簡單(直接)短語、句柄和最左素短語。答：句型(SdG)a的短語：(SdG)0 用正規(guī)(zhnggu)文法。(2) L2= a0n1n bdm | n0，m0 用二型文法。 答：(1) 描述(mio sh)L1語言的正規(guī)文法如下： S aS|AA bA|bB B c(2) 描述L2語言的二型文法如下：S AB A

30、aT T 0T1|01 B bD D dD|d 下列語言或文法確切屬于按喬姆斯基（Chomsky）分類的哪種類型,請?zhí)钤冢?）內(nèi)。（1） L1= a0n1nbdm | n0，m 0 ( ) （2） L2= anbncnbm | n0,m0 ( ) （3） L3= anbmc| n0,m0 ( ) （4） GA:AaB| BAb|a ( )（5） GE:EE+E|E*E|(E)|i ( )答：（1） L1= a0n1nbdm | n0，m 0 ( 2 型 ) （2） L2= anbncnbm | n0,m0 ( 1型 ) （3） L3= anbmc| n0,m0 ( 3型 ) （4） GA:AaB| BAb|a ( 2型 ) （5） GE:EE+E|E*E|(E)|i ( 2型 )按指定類型給出下列語言的文法。(1) L1= candbm| n0,m0 用正規(guī)文法。(2) L2= 0na