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

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

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

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

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

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

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

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

8、.若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子(A)。A.是無(wú)窮多個(gè)A.是無(wú)窮多個(gè)B.是有窮多個(gè)C.是可枚舉的D.個(gè)數(shù)是常量D.圖靈機(jī)D.語(yǔ)義分析D.圖靈機(jī)D.語(yǔ)義分析A.下推自動(dòng)機(jī)B.NFAC.DFA.編譯原理各階段工作都涉及(B)A.詞法分析B.表格管理C.語(yǔ)法分析.正則表達(dá)式R1和R2等價(jià)是指(C)R1和R2都是定義在一個(gè)字母表上的正則表達(dá)式R1和R2中使用的運(yùn)算符相同R1和R2代表同一正則集R1和R2代表不同正則集.已知文法GS:SfA1,AfA1|S0|0。與G等價(jià)的正規(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)等價(jià)的正規(guī)式是(C)。A.a*|b*與(a|b)*(a|b)等價(jià)的正規(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,則符號(hào)串ccbcbcbcbccbccbccbbbcc中，是該文法句子的是(D)A.B.LR(1)文法都是()無(wú)二義性且無(wú)左遞歸無(wú)二義性但可能是左遞歸C.D.B.可能有二義性但無(wú)左遞歸可以既有二義性又有左遞歸文法EfE+E|E*E|i的句子i*i+i*i有(C)棵不同的語(yǔ)法樹(shù)。A.1B.A.1B.3C.5D.750

10、.文法SfaaS|abc定義的語(yǔ)言是(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)項(xiàng)目則A-.B為(D)。B.歸約項(xiàng)目C.接受項(xiàng)目同心集合并可能會(huì)產(chǎn)生新的(D)沖突。A.二義B.移進(jìn)/移進(jìn)C.移進(jìn)/歸約就文法的描述能力來(lái)說(shuō)，有(C)A.SLR(1)uLR(0)B.LR(1)uLR(0)C.SLR(1)uLR(1)如圖所示自動(dòng)機(jī)M,請(qǐng)問(wèn)下列哪個(gè)字符串不是M所能識(shí)別的(D)。A.bbaaB.abbaD.akakbclk0D.待約項(xiàng)目D.歸約/歸約D.無(wú)

11、二義文法uLR(1)D.aabbC.abab有限狀態(tài)自動(dòng)機(jī)能識(shí)別(C)A.上下文無(wú)關(guān)語(yǔ)言B.上下文有關(guān)語(yǔ)言C.正規(guī)語(yǔ)言已知文法G是無(wú)二義的，則對(duì)G的任意句型&仆)A.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同B.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能相同C.最左推導(dǎo)和最右推導(dǎo)必定相同D.可能存在兩個(gè)不同的最左推導(dǎo)，但他們對(duì)應(yīng)的語(yǔ)法樹(shù)相同(B)不是DFA的成分A.有窮字母表B.多個(gè)初始狀態(tài)的集合C.多個(gè)終態(tài)的集合與逆波蘭式(后綴表達(dá)式)ab+c*d+對(duì)應(yīng)的中綴表達(dá)式是(B)A.a+b+c*dB.(a+b)*c+dC.(a+b)*(c+d)后綴式abc+d+可用表達(dá)式(B)來(lái)表示。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型文法定義的語(yǔ)言D.轉(zhuǎn)換函數(shù)D.a+b*c+dD.(a(b+c)+dD.以上都不對(duì)(D)不是NFA的成分。A.有窮字母表B.初始狀態(tài)集合二、問(wèn)答題將文法GS改寫(xiě)為等價(jià)的GS,使GS不含左遞歸和左公共因子。GS：SS答：文法GS改寫(xiě)為等價(jià)的不含左遞歸和左公共因子的GS為：SS將文法GS改寫(xiě)為等價(jià)的GS,使GS不含左遞歸和左公共因子。GS：SS答：文法GS改寫(xiě)為等價(jià)的不含左遞歸和左公共因子的GS為：SSSS將文法GS改寫(xiě)為等價(jià)的GS,使

13、GS不含左遞歸和左公共因子。GS：SS答：文法GS改寫(xiě)為等價(jià)的不含左遞歸和左公共因子的GS為：判斷下面文法是否為L(zhǎng)L(1)文法，若是,請(qǐng)構(gòu)造相應(yīng)的LL(1)分析表。答:首先計(jì)算文法的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.判斷下面文法是否為L(zhǎng)L(1)文法，若是，請(qǐng)構(gòu)造相應(yīng)的LL(1)分析表。答:首先計(jì)算文法的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.判斷下面文法是否為L(zhǎng)L(1)文法，若是，請(qǐng)構(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.某語(yǔ)言的拓廣文法為:(0(證明G不是LR(0)文法而是SLR(1)文法，請(qǐng)給出SLR(1)分析表。Follow(D)=bFollow(D)=bIo：SfIo：SfS*Db5fBDfdDfBfBaBfG的1區(qū)(0)項(xiàng)目集族及識(shí)別活前綴的DFA如下圖:由產(chǎn)生式知拓廣文法G，

16、增加產(chǎn)生式早S在項(xiàng)目集I。中：有移進(jìn)項(xiàng)目D歸約項(xiàng)目D和存在移進(jìn)-歸約和歸約-歸約沖突，所以G不是LR(O)文法。若產(chǎn)生式排序?yàn)椋篎ollow(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等價(jià)的NFA。答：與正規(guī)式R等價(jià)的NFA如下圖給出與正規(guī)式R=(ab)*lb)*(al(ba)*)a等價(jià)的NFA。答：與正規(guī)式R等價(jià)的NFA如下圖給出與正規(guī)式R=(aba)*(ba)*lb)b等價(jià)的NFA。答：與正規(guī)式R等價(jià)的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.某語(yǔ)言的拓廣文法G為:證明G不是LR(0)文法而是SLR(1)文法，請(qǐng)給出SLR(1)13.某語(yǔ)言的拓廣文法G為:證明G不是LR(0)文法而是SLR(1)文法，請(qǐng)給出SLR(1)分析表。答：拓廣文法G，增加產(chǎn)生式S叮在項(xiàng)目集10中:有移進(jìn)項(xiàng)目T-aBd和歸約項(xiàng)目T存在移進(jìn)-歸約沖突，所以G不是LR(0)文法。若產(chǎn)生式排序?yàn)椋篏的1區(qū)(0)項(xiàng)目集族及識(shí)別活前綴的DFA如下圖所示:識(shí)別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.某語(yǔ)言的文法G為:證明G不是LR(0)文法而是SLR文法，請(qǐng)給出該文法的SLR分析表。答：拓廣文法G,增加產(chǎn)生式SIo：在項(xiàng)目集I。中：Io：有移進(jìn)項(xiàng)目ETd和歸約項(xiàng)目E存在移進(jìn)-歸約沖突，所

20、以G不是LR(0)文法。若產(chǎn)生式排序?yàn)椋?)()()()G的1G的1區(qū)(0)項(xiàng)目集族及識(shí)別活前綴的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)項(xiàng)目集規(guī)范族中I0項(xiàng)目集的全體項(xiàng)目。GS為:答：%：%：3/fs,#$-BDfDBfal),#/a/bE一b#/a/bDf-5,/16.給出文法GS的1區(qū)(1)項(xiàng)目集規(guī)范族中I0項(xiàng)目集的全體項(xiàng)目。GS為:答：%：%：%：Tf，S,D;DSiD,D-*DBD*B,B-*ajBf*b,井A/J#/:/aA井h/aA杵/；力Zb17.文法GM及其LR分析表如下，請(qǐng)給出對(duì)串dbba#的分析過(guò)程。nameACTIONGOTO答：對(duì)串dbba#的分析過(guò)程如下表步驟狀態(tài)棧文法符號(hào)棧剩余輸入符號(hào)動(dòng)作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分析表如下，請(qǐng)給出對(duì)輸入串da;aoa#的分析過(guò)程。GS:SSSSSSSSSSnameACTIONGOTOda;a#S0S2S3S311S4acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1S4r1答：輸入串da;aoa#的分析過(guò)程如下表:步驟狀態(tài)棧文法符號(hào)棧剩余輸入符號(hào)動(dòng)作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分析表如下，請(qǐng)給出對(duì)串dada#的分析過(guò)程。GM1S-VdB狀態(tài)ACTIONGOTOdea#SBV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：對(duì)串dada#的分析過(guò)程如下表步驟狀態(tài)棧文法符號(hào)棧剩余輸入符號(hào)動(dòng)作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èi)型給出下列語(yǔ)言的文法。L=anbmcln0,m0)用正規(guī)文法。L2=aOnlnbdmIn0,m0用二型文法。答：(1)描述L語(yǔ)言的正規(guī)文法如下：aIbibc(2)描述L2語(yǔ)言的二型文法如下：a01101bDDdDId.下列語(yǔ)言或文法確切屬于按喬姆斯基(Chomsky)分類(lèi)的哪種類(lèi)型,請(qǐng)?zhí)钤?)內(nèi)。(1)Ll=aOnlnbdmIn0,m0()L2=anbncnbmIn0m0()L3=anbmdn0m0()albla()I1()1()答：Ll=a