編譯原理復習題及答案

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