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

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁(yè)眉頁(yè)腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請(qǐng)聯(lián)系刪除，謝謝！編譯原理復(fù)習(xí)題及答案一、選擇題1．一個(gè)正規(guī)語(yǔ)言只能對(duì)應(yīng)(B)A一個(gè)正規(guī)文法B一個(gè)最小有限狀態(tài)自動(dòng)機(jī)2．文法G[A]：A→εA→aBB→AbB→a是(A)A正規(guī)文法B二型文法3．下面說(shuō)法正確的是(A)A一個(gè)SLR（1）文法一定也是LALR（1）文法B一個(gè)LR（1）文法一定也是LALR（1）文法4．一個(gè)上下文無(wú)關(guān)文法消除了左遞歸，提取了左公共因子后是滿足LL（1）文法的(A)A必要條件B充分必要條件5．下面說(shuō)法正確的是(B)A一個(gè)正規(guī)式只能對(duì)應(yīng)一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)B一個(gè)正規(guī)語(yǔ)言可能對(duì)應(yīng)多個(gè)正規(guī)文法6．算符優(yōu)先分析與規(guī)范歸約相比的優(yōu)點(diǎn)是(A)A歸約速度快B對(duì)文法限制少7．一個(gè)LR（1）文法合并同心集后若不是LALR（1）文法(B)A則可能存在移進(jìn)/歸約沖突B則可能存在歸約/歸約沖突C則可能存在移進(jìn)/歸約沖突和歸約/歸約沖突8．下面說(shuō)法正確的是(A)ALe某是一個(gè)詞法分析器的生成器BYacc是一個(gè)語(yǔ)法分析器9．下面說(shuō)法正確的是(A)A一個(gè)正規(guī)文法也一定是二型文法B一個(gè)二型文法也一定能有一個(gè)等價(jià)的正規(guī)文法10．編譯原理是對(duì)(C)。A、機(jī)器語(yǔ)言的執(zhí)行B、匯編語(yǔ)言的翻譯C、高級(jí)語(yǔ)言的翻譯D、高級(jí)語(yǔ)言程序的解釋執(zhí)行C．FORTRAND．PASCAL11．(A)是一種典型的解釋型語(yǔ)言。A．BASICB．C12．把匯編語(yǔ)言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由(B)完成的。A.編譯器B.匯編器C.解釋器D.預(yù)處理器13．用高級(jí)語(yǔ)言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫(B)A．源程序B．目標(biāo)程序C．連接程序14．(C)不是編譯程序的組成部分。A.詞法分析程序B.代碼生成程序D．解釋程序D.語(yǔ)法分析程序C.設(shè)備管理程序15．通常一個(gè)編譯程序中，不僅包含詞法分析，語(yǔ)法分析，語(yǔ)義分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等六個(gè)部分，還應(yīng)包括(C)。A．模擬執(zhí)行器B．解釋器C．表格處理和出錯(cuò)處理D．符號(hào)執(zhí)行器16．編譯程序絕大多數(shù)時(shí)間花在(D)上。A．出錯(cuò)處理B．詞法分析C．目標(biāo)代碼生成D．表格管理17．源程序是句子的集合，(B)可以較好地反映句子的結(jié)構(gòu)。A.線性表B.樹C.完全圖18．詞法分析器的輸出結(jié)果是(D)。A、單詞自身值C、單詞的種別編碼19．詞法分析器不能(D)A.識(shí)別出數(shù)值常量D.堆棧B、單詞在符號(hào)表中的位置D、單詞的種別編碼和自身值B.過濾源程序中的注釋D.發(fā)現(xiàn)括號(hào)不匹配C.掃描源程序并識(shí)別記號(hào)20．文法：G：S→某S所識(shí)別的語(yǔ)言是(D)。A、某y某B、(某y某)某21．如果文法G是無(wú)二義的，則它的任何句子α(A)A．最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹必定相同B．最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹可能不同C．最左推導(dǎo)和最右推導(dǎo)必定相同C、某某y某某D、某ny某n(n≥0)D．可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹相同22．正則文法(A)二義性的。A.可以是B.一定不是C.一定是23．(B)這樣一些語(yǔ)言，它們能被確定的有窮自動(dòng)機(jī)識(shí)別，但不能用正則表達(dá)式表示。A.存在B.不存在C.無(wú)法判定是否存在24．給定文法A→bA|ca，為該文法句子的是(C)A.bbaB.cabC.bcaD.cba25．設(shè)有文法G[S]：SS1|S0|Sa|Sc|a|b|c，下列符號(hào)串中是該文法的句子有(D)A.ab0B.a0c01C.a0b0aD.bc1026．文法G產(chǎn)生的(D)的全體是該文法描述的語(yǔ)言。A．句型B.終結(jié)符集C.非終結(jié)符集27．若文法G定義的語(yǔ)言是無(wú)限集，則文法必然是(A)A．遞歸的B.上下文無(wú)關(guān)的C.二義性的28．描述一個(gè)語(yǔ)言的文法是(B)A．唯一的B.不唯一的29．一個(gè)文法所描述的語(yǔ)言是(A)A．唯一的B.不唯一的30．采用自上而下分析，必須(A)。A、消除回溯C、消除右遞歸C.可能唯一C.可能唯一B、消除左遞歸D.句子D.無(wú)二義性的D、提取公共左因子31．編譯過程中，語(yǔ)法分析器的任務(wù)是(A)①分析單詞的構(gòu)成②分析單詞串如何構(gòu)成語(yǔ)句③分析語(yǔ)句是如何構(gòu)成程序④分析程序的結(jié)構(gòu)A.②③B.④C.①②③④D.②③④32．詞法分析器的輸入是(A)。A．符號(hào)串B．源程序C．語(yǔ)法單位D．目標(biāo)程序33．兩個(gè)有窮自動(dòng)機(jī)等價(jià)是指它們的(C)。A．狀態(tài)數(shù)相等C．所識(shí)別的語(yǔ)言相等B．有向弧數(shù)相等D．狀態(tài)數(shù)和有向弧數(shù)相等34．若狀態(tài)k含有項(xiàng)目“A→α·”，且僅當(dāng)輸入符號(hào)a∈FOLLOW(A)時(shí)，才用規(guī)則“A→α”歸約的語(yǔ)法分析方法是(D)。A．LALR分析法B．LR(0)分析法C．LR(1)分析法D．SLR(1)分析法35．若a為終結(jié)符，則A→α·aβ為(B)項(xiàng)目。A．歸約B．移進(jìn)C．接受D．待約36．在使用高級(jí)語(yǔ)言編程時(shí),首先可通過編譯程序發(fā)現(xiàn)源程序的全部和部分(A)錯(cuò)誤。A.語(yǔ)法B.語(yǔ)義C.語(yǔ)用D.運(yùn)行37．喬姆斯基(Chomky)把文法分為四種類型，即0型。其中3型文法是(B)A.非限制文法B.正則文法C.上下文有關(guān)文法D.上下文無(wú)關(guān)文法38．一個(gè)句型中的(A)稱為該句型的句柄。A.最左直接短語(yǔ)B.最右直接短語(yǔ)C.終結(jié)符D.非終結(jié)符39．在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是(D)A.尋找句柄B.尋找句型C.消除遞歸40．在自頂向下的語(yǔ)法分析方法中，分析的關(guān)鍵是(C)A.尋找句柄B.尋找句型C.消除遞歸D.選擇候選式D.選擇候選式41．在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型(C)的DFA狀態(tài)。A.句柄B.前綴C.活前綴D.LR(0)項(xiàng)目42．一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分，它們是一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組(B)A.句子B.產(chǎn)生式C.單詞D.句型43．詞法分析器用于識(shí)別(C)A.句子B.產(chǎn)生式C.單詞D.句型D.目標(biāo)程序D.代碼生成D.狀態(tài)集D.句子44．編譯程序是一種(B)A.匯編程序B.翻譯程序C.解釋程序45．按邏輯上劃分，編譯程序第三步工作是(A)A.語(yǔ)義分析B.詞法分析C.語(yǔ)法分析46．在語(yǔ)法分析處理中，F(xiàn)IRST集合、FOLLOW集合均是(B)A.非終結(jié)符集B.終結(jié)符集C.字母表47．編譯程序中語(yǔ)法分析器接收以(A)為單位的輸入。A.單詞B.表達(dá)式C.產(chǎn)生式48．編譯過程中，語(yǔ)法分析器的任務(wù)就是(B)A.分析單詞是怎樣構(gòu)成的C.分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的B.分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的D.分析程序的結(jié)構(gòu)D.個(gè)數(shù)是常量D.圖靈機(jī)D.語(yǔ)義分析49．若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子(A)。A.是無(wú)窮多個(gè)B.是有窮多個(gè)C.是可枚舉的50．識(shí)別上下文無(wú)關(guān)語(yǔ)言的自動(dòng)機(jī)是(C)A.下推自動(dòng)機(jī)B.NFA51．編譯原理各階段工作都涉及(B)A.詞法分析B.表格管理C.DFAC.語(yǔ)法分析52．正則表達(dá)式R1和R2等價(jià)是指(C)A.R1和R2都是定義在一個(gè)字母表上的正則表達(dá)式B.R1和R2中使用的運(yùn)算符相同C.R1和R2代表同一正則集D.R1和R2代表不同正則集53．已知文法G[S]:S→A1，A→A1|S0|0。與G等價(jià)的正規(guī)式是(C)A.0(0|1)某B.1某|0某1C.0(1|10)某154．與(a|b)某(a|b)等價(jià)的正規(guī)式是(C)。A.a某|b某B.(ab)某(a|b)55．(D)文法不是LL(1)的。A.遞歸B.右遞歸C.(a|b)(a|b)某C.2型D.1(10|01)某0D.(a|b)某D.含有公共左因子的56．給定文法A→bA|cc，則符號(hào)串①cc②bcbc③bcbcc④bccbcc⑤bbbcc中，是該文法句子的是(D)A.①B.③④⑤C.②④D.①⑤57．LR(1)文法都是()A.無(wú)二義性且無(wú)左遞歸C.無(wú)二義性但可能是左遞歸B.可能有二義性但無(wú)左遞歸D.可以既有二義性又有左遞歸D.758．文法E→E+E|E某E|i的句子i某i+i某i有(C)棵不同的語(yǔ)法樹。A.1B.3C.559．文法S→aaS|abc定義的語(yǔ)言是(C)。A.{a2kbc|k>0}B.{akbc|k>0}C.{a2k-1bc|k>0}C.接受項(xiàng)目C.移進(jìn)/歸約D.{akakbc|k>0}D.待約項(xiàng)目D.歸約/歸約60．若B為非終結(jié)符，則A→.B為(D)。A.移進(jìn)項(xiàng)目B.歸約項(xiàng)目61．同心集合并可能會(huì)產(chǎn)生新的(D)沖突。A.二義B.移進(jìn)/移進(jìn)62．就文法的描述能力來(lái)說(shuō)，有(C)A．SLR(1)LR(0)B．LR(1)LR(0)C．SLR(1)LR(1)D．無(wú)二義文法LR(1)63．如圖所示自動(dòng)機(jī)M，請(qǐng)問下列哪個(gè)字符串不是M所能識(shí)別的(D)。A.bbaaB.abbaC.ababD.aabb64．有限狀態(tài)自動(dòng)機(jī)能識(shí)別(C)A.上下文無(wú)關(guān)語(yǔ)言B.上下文有關(guān)語(yǔ)言C.正規(guī)語(yǔ)言D.0型文法定義的語(yǔ)言65．已知文法G是無(wú)二義的，則對(duì)G的任意句型α(A)A.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹必定相同B.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹可能相同C.最左推導(dǎo)和最右推導(dǎo)必定相同D.可能存在兩個(gè)不同的最左推導(dǎo)，但他們對(duì)應(yīng)的語(yǔ)法樹相同66．(B)不是DFA的成分A.有窮字母表B.多個(gè)初始狀態(tài)的集合C.多個(gè)終態(tài)的集合D.轉(zhuǎn)換函數(shù)D.a+b某c+dD．(a(b+c))+d67．與逆波蘭式(后綴表達(dá)式)ab+c某d+對(duì)應(yīng)的中綴表達(dá)式是(B)A.a+b+c某dB.(a+b)某c+dC.(a+b)某(c+d)68．后綴式abc+d+可用表達(dá)式(B)來(lái)表示。A．((a+b)c)+dB．(a+(bc))+d69．表達(dá)式A某(B-C某(C/D))的后綴式為(B)。A．ABC-CD/某某B．ABCCD/某-某C．(a(b+c))+dC．ABC-某CD/某D．以上都不對(duì)70．(D)不是NFA的成分。A.有窮字母表B.初始狀態(tài)集合C.終止?fàn)顟B(tài)集合D.有限狀態(tài)集合二、問答題1．將文法G[S]改寫為等價(jià)的G′[S]，使G′[S]不含左遞歸和左公共因子。G[S]：S→bSAe|bAA→Ab|d答：文法G[S]改寫為等價(jià)的不含左遞歸和左公共因子的G'[S]為：S→bBB→SAe|AA→dA'A'→bA'|ε2．將文法G[S]改寫為等價(jià)的G'[S]，使G'[S]不含左遞歸和左公共因子。G[S]：S→SAe|AeA→dAbA|dA|d答：文法G[S]改寫為等價(jià)的不含左遞歸和左公共因子的G'[S]為：S→AeS'S'→AeS'|εA→dA'A'→AB|εB→bA|ε3．將文法G[S]改寫為等價(jià)的G'[S]，使G'[S]不含左遞歸和左公共因子。G[S]：S→[AA→B]|ASB→aB|a答：文法G[S]改寫為等價(jià)的不含左遞歸和左公共因子的G'[S]為：S→[AA→B]A′A′→SA′|εB→aB′B′→B|ε4．判斷下面文法是否為L(zhǎng)L(1)文法，若是,請(qǐng)構(gòu)造相應(yīng)的LL(1)分析表。S→aHH→aMd|dM→Ab|εA→aM|e答：首先計(jì)算文法的FIRST集和FOLLOW集如下表。文法的FIRST集和FOLLOW集非終結(jié)符FIRST集FOLLOW集S{a}.........{#}...H{#}...{a，d}.....M{a，e，ε}{d，b}A....{a，e}.....由于predict（H→aMd）∩predict（H→d）={a}∩dntpdz3=predict（M→Ab）∩predict（M→ε）={a，e}∩{d，b}=predict（A→aM）∩predict（A→e）={a}∩{e}=所以該文法是LL(1)文法，LL(1)分析表如下表。adbS→aH.H→aMd→d.M→Ab.→ε→εA→aM.5．判斷下面文法是否為L(zhǎng)L(1)文法，若是，請(qǐng)構(gòu)造相應(yīng)的LL(1)分析表。S→aDD→STe|εT→bH|HH→d|ε答：首先計(jì)算文法的FIRST集和FOLLOW集如下表。非終結(jié)符FIRST集FOLLOW集S{a}{#，b，d，e}.D{a，ε}{#，b，d，e}e→Ab→e.#在項(xiàng)目集I0中：有移進(jìn)項(xiàng)目E→·aTd和歸約項(xiàng)目E→·存在移進(jìn)-歸約沖突，所以G不是LR(0)文法。.若產(chǎn)生式排序?yàn)椋?0)S′→E(1)E→aTd(2)E→ε(3)T→Eb(4)T→aG′的LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA如下圖：由產(chǎn)生式知：Follow(E)={#，b}Follow(T)=t1jvbvh在I0，I2中:Follow(E)∩{a}={#，b}∩{a}=在I5Follow(E)∩{a}={#，b}∩{a}=Follow(T)∩{a}=3bvrzbh∩{a}=Follow(T)∩Follow(E)=3dtbptx∩{#，b}=所以在I0，I2，I5中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow集解決,所以G′是SLR(1)文法。構(gòu)造的SLR(1)分析表如下表：ACTIONGOTOnameabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r24367r1r3r115．給出文法G[S]的LR(1)項(xiàng)目集規(guī)范族中I0項(xiàng)目集的全體項(xiàng)目。G[S]為：S→BD|DB→aD|bD→BI0:答：I0：16．給出文法G[S]的LR(1)項(xiàng)目集規(guī)范族中I0項(xiàng)目集的全體項(xiàng)目。G[S]為：S→D;D|DD→DB|BB→a|bI0:答：I0:17．給出文法G[S]的LR(1)項(xiàng)目集規(guī)范族中I0項(xiàng)目集的全體項(xiàng)目。G[S]為：S→S;V|VV→VaA|AA→b(S)|εI0:答：I0:18．文法G[M]及其LR分析表如下，請(qǐng)給出對(duì)串dbba#的分析過程。G[M]:1)M→VbA2)V→d3)V→ε4)A→a5)A→Aba6)A→εACTIONGOTOnamebda#MA0r3S311acc2S43r24r6S5r665r4r46S7r17S88r5r5答：對(duì)串dbba#的分析過程如下表步驟狀態(tài)棧文法符號(hào)棧剩余輸入符號(hào)動(dòng)作#dbba#移進(jìn)10#dbba#用V→d歸約203#Vbba#移進(jìn)302#Vbba#用A→ε歸約4024#VbAba#50246#VbAba#移進(jìn)602467#VbAba#移進(jìn)7024678#VbA#用A→Aba歸約80246#M#用M→VbA歸約901接受19．文法G[S]及其LR分析表如下，請(qǐng)給出對(duì)輸入串da;aoa#的分析過程。G[S]:0)S′→S1)S→dSoS2)S→dS3)S→S;SV24)S→aname012345678dS2S2S2S2aS3r4S7r3r1ACTION;S4r4S4r3S4aS3S3S3S3#accr4r2r3r1GOTOS1568答：輸入串da;aoa#的分析過程如下表：步驟狀態(tài)棧文法符號(hào)棧#10#d202#da3023#dS4025#dS;50254#dS;a602543#dS;S702546#dS8025#dSo90257#dSoa1002573#dSoS1102578#S1201剩余輸入符號(hào)da;aoa#a;aoa#;aoa#;aoa#aoa#oa#oa#oa#a####動(dòng)作移進(jìn)移進(jìn)用S→a歸約移進(jìn)移進(jìn)用S→a歸約用S→S;S歸約移進(jìn)移進(jìn)用S→a歸約用S→dSoS歸約接受20．文法G[M]及其LR分析表如下，請(qǐng)給出對(duì)串dada#的分析過程。G[M]:1)S→VdB2