2013編譯原理復(fù)習(xí)題及答案

1、編譯原理復(fù)習(xí)題及答案、選擇題B一個最小有限狀態(tài)自動機(jī)是(A)B一個最小有限狀態(tài)自動機(jī)是(A)B二型文法A一個正規(guī)文法文法GA：AAAA正規(guī)文法下面說法正確的是(A)A一個SLR(1)文法一定也是LALR(1)文法B一個LR(1)文法一定也是LALR(1)文法一個上下文無關(guān)文法消除了左遞歸，提取了左公共因子后是滿足LL(1)文法的(A)A必要條件B充分必要條件下面說法正確的是(B)A一個正規(guī)式只能對應(yīng)一個確定的有限狀態(tài)自動機(jī)B一個正規(guī)語言可能對應(yīng)多個正規(guī)文法算符優(yōu)先分析與規(guī)范歸約相比的優(yōu)點(diǎn)是(A)A歸約速度快B對文法限制少一個LR(1)文法合并同心集后若不是LALR(1)文法(B)A則可能存在移

2、進(jìn)/歸約沖突B則可能存在歸約/歸約沖突C則可能存在移進(jìn)/歸約沖突和歸約/歸約沖突下面說法正確的是(A)ALex是一個詞法分析器的生成器BYacc是一個語法分析器下面說法正確的是(A)A一個正規(guī)文法也一定是二型文法B一個二型文法也一定能有一個等價的正規(guī)文法10.10.編譯原理是對(C)。A、機(jī)器語言的執(zhí)行C、高級語言的翻譯B、匯編語言的翻譯D、高級語言程序的解釋執(zhí)行.用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫(B)A.A.源程序B.目標(biāo)程序C.連接程序D.解釋程序.(C)不是編譯程序的組成部分。A.詞法分析程序B.代碼生成程序C.設(shè)備管理程序D.語法分析程序.通常一個編譯程序中，不僅包含詞法分析，

3、語法分析，語義分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等六個部分，還應(yīng)包括(C)。A.模擬執(zhí)行器B.解釋器C.表格處理和出錯處理D.符號執(zhí)行器A.線性表B.樹.詞法分析器的輸出結(jié)果是A.線性表B.樹.詞法分析器的輸出結(jié)果是(D)。A、單詞自身值C、單詞的種別編碼.詞法分析器不能(D)A.識別出數(shù)值常量C.掃描源程序并識別記號完全圖D.堆棧B、單詞在符號表中的位置D、單詞的種別編碼和自身值B.過濾源程序中的注釋發(fā)現(xiàn)括號不匹配.文法：G：SfxSxIy所識別的語言是(D)。A、xyxB、(xyx)*C、x*yx*D、xnyxn(nN0).如果文法G是無二義的，則它的任何句子a(A)A.最左推導(dǎo)和

4、最右推導(dǎo)對應(yīng)的語法樹必定相同B.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C.最左推導(dǎo)和最右推導(dǎo)必定相同D.可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同.正則文法(A)二義性的。A.可以是B.一定不是C.一定是.(B)這樣一些語言，它們能被確定的有窮自動機(jī)識別，但不能用正則表達(dá)式表示A.存在B.不存在C.無法判定是否存在.給定文法A-bAIca,為該文法句子的是(C)C.bcaD.cba下列符號串中是該文法的句子有C.bcaD.cba下列符號串中是該文法的句子有(D)C.a0b0aD.bc10C.可能唯一C.可能唯一.設(shè)有文法GS：SaS1|S0|Sa|Sc|a|b|c,A.ab0B.a0c

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

6、“Aa歸約的語法分析方法是(D)。A.LALR分析法B.LR(0)分析法C.LR(1)分析法D.SLR(1)分析法.若a為終結(jié)符，則Aa為田)項目。A.歸約B.移進(jìn)C.接受D.待約.在使用高級語言編程時，首先可通過編譯程序發(fā)現(xiàn)源程序的全部和部分(A)錯誤。A.語法B.語義C.語用D.運(yùn)行.喬姆斯基(Chomsky)把文法分為四種類型，即0型、1型、2型、3型。其中3型文法是(B)A.非限制文法B.正則文法C.上下文有關(guān)文法D.上下文無關(guān)文法.一個上下文無關(guān)文法G包括四個組成部分，它們是一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組(B)A.句子B.產(chǎn)生式C.單詞D.句型34.詞法分析器用

7、于識別(C)A.句子B.產(chǎn)生式C.單詞D.句型35.編譯程序是一種(B)A.匯編程序B.翻譯程序C.解釋程序D.目標(biāo)程序36.按邏輯上劃分，編譯程序第三步工作是(A)A.語義分析B.詞法分析C.語法分析D.代碼生成.在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合均是(B)A.非終結(jié)符集B.終結(jié)符集C.字母表D.狀態(tài)集.編譯程序中語法分析器接收以(A)為單位的輸入。A.單詞B.表達(dá)式C.產(chǎn)生式D.句子39.編譯過程中，語法分析器的任務(wù)就是39.編譯過程中，語法分析器的任務(wù)就是(B)A.分析單詞是怎樣構(gòu)成的C.分析語句和說明是如何構(gòu)成程序的B.分析單詞串是如何構(gòu)成語句和說明的D.分析程序的結(jié)構(gòu)

8、.若一個文法是遞歸的，則它所產(chǎn)生的語言的句子(A)。A.是無窮多個A.是無窮多個B.是有窮多個C.是可枚舉的D.個數(shù)是常量D.圖靈機(jī)D.語義分析D.圖靈機(jī)D.語義分析A.下推自動機(jī)B.NFAC.DFA.編譯原理各階段工作都涉及(B)A.詞法分析B.表格管理C.語法分析.正則表達(dá)式R1和R2等價是指(C)R1和R2都是定義在一個字母表上的正則表達(dá)式R1和R2中使用的運(yùn)算符相同R1和R2代表同一正則集R1和R2代表不同正則集.已知文法GS:SfA1,AfA1|S0|0。與G等價的正規(guī)式是(C)A.0(0|1)*B.1*|0*1A.0(0|1)*B.1*|0*1C.0(1|10)*1D.1(10|0

9、1)*0與(a|b)*(a|b)等價的正規(guī)式是(C)。A.a*|b*與(a|b)*(a|b)等價的正規(guī)式是(C)。A.a*|b*B.(ab)*(a|b)C.(a|b)(a|b)*(D)文法不是LL的。A.遞歸B.右遞歸C.2型D.(a|b)*D.含有公共左因子的給定文法AfbA|cc,則符號串ccbcbcbcbccbccbccbbbcc中，是該文法句子的是(D)A.B.LR(1)文法都是()無二義性且無左遞歸無二義性但可能是左遞歸C.D.B.可能有二義性但無左遞歸可以既有二義性又有左遞歸文法EfE+E|E*E|i的句子i*i+i*i有(C)棵不同的語法樹。A.1B.A.1B.3C.5D.750

10、.文法SfaaS|abc定義的語言是(C)。C.C.終止?fàn)顟B(tài)集合D.有限狀態(tài)集合51.52.53.54.55.56.57.58.59.60.61.A.a2kbclk0B.akbclk0C.a2k-lbclk0若B為非終結(jié)符A.移進(jìn)項目則A-.B為(D)。B.歸約項目C.接受項目同心集合并可能會產(chǎn)生新的(D)沖突。A.二義B.移進(jìn)/移進(jìn)C.移進(jìn)/歸約就文法的描述能力來說，有(C)A.SLR(1)uLR(0)B.LR(1)uLR(0)C.SLR(1)uLR(1)如圖所示自動機(jī)M,請問下列哪個字符串不是M所能識別的(D)。A.bbaaB.abbaD.akakbclk0D.待約項目D.歸約/歸約D.無

11、二義文法uLR(1)D.aabbC.abab有限狀態(tài)自動機(jī)能識別(C)A.上下文無關(guān)語言B.上下文有關(guān)語言C.正規(guī)語言已知文法G是無二義的，則對G的任意句型&仆)A.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能相同C.最左推導(dǎo)和最右推導(dǎo)必定相同D.可能存在兩個不同的最左推導(dǎo)，但他們對應(yīng)的語法樹相同(B)不是DFA的成分A.有窮字母表B.多個初始狀態(tài)的集合C.多個終態(tài)的集合與逆波蘭式(后綴表達(dá)式)ab+c*d+對應(yīng)的中綴表達(dá)式是(B)A.a+b+c*dB.(a+b)*c+dC.(a+b)*(c+d)后綴式abc+d+可用表達(dá)式(B)來表示。A.(a+b)c)+dB

12、.-(a+(bc)+dC.-(a(b+c)+d表達(dá)式A*(B-C*(C/D)的后綴式為(B)。A.ABC-CD/*B.ABCCD/*-*C.ABC-*CD/*D.0型文法定義的語言D.轉(zhuǎn)換函數(shù)D.a+b*c+dD.(a(b+c)+dD.以上都不對(D)不是NFA的成分。A.有窮字母表B.初始狀態(tài)集合二、問答題將文法GS改寫為等價的GS,使GS不含左遞歸和左公共因子。GS：SS答：文法GS改寫為等價的不含左遞歸和左公共因子的GS為：SS將文法GS改寫為等價的GS,使GS不含左遞歸和左公共因子。GS：SS答：文法GS改寫為等價的不含左遞歸和左公共因子的GS為：SSSS將文法GS改寫為等價的GS,使

13、GS不含左遞歸和左公共因子。GS：SS答：文法GS改寫為等價的不含左遞歸和左公共因子的GS為：判斷下面文法是否為LL(1)文法，若是,請構(gòu)造相應(yīng)的LL(1)分析表。答:首先計算文法的FIRST集和FOLLOW集如下表。文法的FIRST集和FOLLOW集非終結(jié)符FIRST集FOLLOW集Sa#.Ha，d.#.Ma,e,d，bAa，e.b.由于predict(HaMd)predict(Hd)=ad二0predict(MAb)predict(M)=a,ed,b=0predict(AaM)predict(Ae)=ae=0所以該文法是LL(1)文法，LL(1)分析表如下表。adbe#SaH.HaMdd.

14、MAb.AbAaM.e.判斷下面文法是否為LL(1)文法，若是，請構(gòu)造相應(yīng)的LL(1)分析表。答:首先計算文法的FIRST集和FOLLOW集如下表。非終結(jié)符FIRST集FOLLOW集Sa#,b,d,e.Da，#,b,d,eTb,d,eHd，e由于predict(DSTe)predict(D)=a#,b,d,e=5predict(TbH)predict(TH)=be二0predict(Hd)predict(H)=de二0所以該文法是LL(1)文法，LL(1)分析表如下表:aebd#SaD.DSTeTH.bHH.Hd.6.判斷下面文法是否為LL(1)文法，若是，請構(gòu)造相應(yīng)的LL(1)分析表。文法的

15、FIRST集和FOLLOW集非終結(jié)符FIRST集FOLLOW集Sa.#，bDa，#，bTb.e.Mb.e.Hb，e.由于predict(DSTe)predict(D)=a#,b=0predict(HM)predict(H)=be=0所以該文法是LL(1)文法，LL(1)分析表如下表：aeb#SaD.DSTeTbMMbHHM.7.某語言的拓廣文法為:(0(證明G不是LR(0)文法而是SLR(1)文法，請給出SLR(1)分析表。Follow(D)=bFollow(D)=bIo：SfIo：SfS*Db5fBDfdDfBfBaBfG的1區(qū)(0)項目集族及識別活前綴的DFA如下圖:由產(chǎn)生式知拓廣文法G，

16、增加產(chǎn)生式早S在項目集I。中：有移進(jìn)項目D歸約項目D和存在移進(jìn)-歸約和歸約-歸約沖突，所以G不是LR(O)文法。若產(chǎn)生式排序為：Follow(S)=#Follow(B)=a,#在I。中：Follow(D)d=bd二0Follow(B)d=a,#d二0Follow(D)Follow(B)=ba,#=0在匕中：Follow(S)a=#a二0所以在I0,I3中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow集解決，所以G是SLR(1)文法,構(gòu)造的SLR分析表如下表：狀態(tài)ACTIONGOTObda#SDB0r4S4r6r61231acc2S53S6r24r35r16r5r58.給出與正規(guī)式R=(ab)*

17、(alb*)ba等價的NFA。答：與正規(guī)式R等價的NFA如下圖給出與正規(guī)式R=(ab)*lb)*(al(ba)*)a等價的NFA。答：與正規(guī)式R等價的NFA如下圖給出與正規(guī)式R=(aba)*(ba)*lb)b等價的NFA。答：與正規(guī)式R等價的NFA如下圖11.將下圖的NFA確定化為DFA。a答：用子集法確定化如下表IlaIb狀態(tài)X,1,21,2.1,2,3X1,2.1,2.1,2,311,2,31,2,Y1,2,321,2,Y1,2.1,2,33確定化后如下圖：12.將下圖的NFA確定化為DFAoba用子集法確定化如下表IIaIb狀態(tài)X,0,1,30,1,32,3,YX0,1,3.0,1,32

18、,3,Y12,3,Y.1,3.Y.21,3.0.2,Y.32,Y.1,3.Y.4Y0.Y確定化后如下圖aa13.某語言的拓廣文法G為:證明G不是LR(0)文法而是SLR(1)文法，請給出SLR(1)13.某語言的拓廣文法G為:證明G不是LR(0)文法而是SLR(1)文法，請給出SLR(1)分析表。答：拓廣文法G，增加產(chǎn)生式S叮在項目集10中:有移進(jìn)項目T-aBd和歸約項目T存在移進(jìn)-歸約沖突，所以G不是LR(0)文法。若產(chǎn)生式排序為：G的1區(qū)(0)項目集族及識別活前綴的DFA如下圖所示:識別G活前綴的DFA由產(chǎn)生式知：Follow(T)=#,bFollow(B)=d在I。中：Follow(T)

19、a=#,ba=0在匕中：Follow(B)a=da=0Follow(T)a=#,ba二0Follow(B)Follow(T)=db,b=0所以在I0,I2,中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow集解決，所以G是SLR(1)文法。構(gòu)造的SLR(1)分析表如下表。SLR(1)分析表nameACTIONGOTOabd#TB0S2r2r211acc2S2r2r4r2433S54S65r1r16r314.某語言的文法G為:證明G不是LR(0)文法而是SLR文法，請給出該文法的SLR分析表。答：拓廣文法G,增加產(chǎn)生式SIo：在項目集I。中：Io：有移進(jìn)項目ETd和歸約項目E存在移進(jìn)-歸約沖突，所

20、以G不是LR(0)文法。若產(chǎn)生式排序為：()()()()G的1G的1區(qū)(0)項目集族及識別活前綴的DFA如下圖:由產(chǎn)生式知：Follow(E)=#，bFollow(T)=d在I0，I2中：Follow(E)=#,b二。在I5中：Follow(E)a=#,ba=0Follow(T)a=da=0Follow(T)Foliow(E)=db,b=0所以在I0,I2,I5中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow集解決，所以G是SLR(1)文法。構(gòu)造的SLR(1)分析表如下表：nameACTIONGOTOabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r2436r1

21、r17r315.給出文法66的1區(qū)(1)項目集規(guī)范族中I0項目集的全體項目。GS為:答：%：%：3/fs,#$-BDfDBfal),#/a/bE一b#/a/bDf-5,/16.給出文法GS的1區(qū)(1)項目集規(guī)范族中I0項目集的全體項目。GS為:答：%：%：%：Tf，S,D;DSiD,D-*DBD*B,B-*ajBf*b,井A/J#/:/aA井h/aA杵/；力Zb17.文法GM及其LR分析表如下，請給出對串dbba#的分析過程。nameACTIONGOTO答：對串dbba#的分析過程如下表步驟狀態(tài)棧文法符號棧剩余輸入符號動作10#dbba#移進(jìn)203#dbba#用Vd歸約302#Vbba#移進(jìn)4

22、024#Vbba#用A歸約50246#VbAba#移進(jìn)602467#VbAba#移進(jìn)7024678#VbAba#用AAba歸約80246#VbA#用MVbA歸約901#M#接受18.文法GS及其LR分析表如下，請給出對輸入串da;aoa#的分析過程。GS:SSSSSSSSSSnameACTIONGOTOda;a#S0S2S3S311S4acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1S4r1答：輸入串da;aoa#的分析過程如下表:步驟狀態(tài)棧文法符號棧剩余輸入符號動作10#da;aoa#移進(jìn)202#da;aoa#移進(jìn)3023#da;aoa#用Sa歸約4

23、025#dS;aoa#移進(jìn)50254#dS;aoa#移進(jìn)602543#dS;aoa#用Sa歸約702546#dS;Soa#用SS;S歸約8025#dSoa#移進(jìn)90257#dSoa#移進(jìn)1002573#dSoa#用Sa歸約1102578#dSoS#用SdSoS歸約1201#S#接受19.文法GM及其LR分析表如下，請給出對串dada#的分析過程。GM1S-VdB狀態(tài)ACTIONGOTOdea#SBV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：對串dada#的分析過程如下表步驟狀態(tài)棧文法符號棧剩余輸入符號動作10#dada#用V歸約202#Vdada

24、#移進(jìn)3024#Vdada#移進(jìn)40245#Vdada#用Ba歸約50246#VdBda#移進(jìn)602467#VdBda#移進(jìn)7024678#VdBda#用BBda歸約80246#VdB#用SVdB歸約901#S#接受.按指定類型給出下列語言的文法。L=anbmcln0,m0)用正規(guī)文法。L2=aOnlnbdmIn0,m0用二型文法。答：(1)描述L語言的正規(guī)文法如下：aIbibc(2)描述L2語言的二型文法如下：a01101bDDdDId.下列語言或文法確切屬于按喬姆斯基(Chomsky)分類的哪種類型,請?zhí)钤?)內(nèi)。(1)Ll=aOnlnbdmIn0,m0()L2=anbncnbmIn0m0()L3=anbmdn0m0()albla()I1()1()答：Ll=a