編譯原理試題

理試題一、單項(xiàng)選擇題1．將編譯程序分成若干個(gè)“遍”是為了(B)A.提高程序的執(zhí)行效率使程序的結(jié)構(gòu)更加清晰C.利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率D.利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率2．不可能是目標(biāo)代碼的是(D)A.匯編指令代碼 B.可重定位指令代碼C.絕對(duì)指令代碼 D.中間代碼3．詞法分析器的輸入是(B)A.單詞符號(hào)串 B.源程序C.語法單位 口.目標(biāo)程序4．中間代碼生成時(shí)所遵循的是(C)A.語法規(guī)則 B.詞法規(guī)則C.語義規(guī)則 D.等價(jià)變換規(guī)則5．編譯程序是對(duì)(D)A.匯編程序的翻譯 B.高級(jí)語言程序的解釋執(zhí)行C.機(jī)器語言的執(zhí)行 D.高級(jí)語言的翻譯6．詞法分析應(yīng)遵循(C)A.語義規(guī)則 B.語法規(guī)則C.構(gòu)詞規(guī)則 D.等價(jià)變換規(guī)則7．詞法分析器的輸出結(jié)果是(C)A.單詞的種別編碼 B.單詞在符號(hào)表中的位置C.單詞的種別編碼和屬性值D.單詞屬性值8.正規(guī)式M1和M2等價(jià)是指(C)A.M1和M2的狀態(tài)數(shù)相等 B.M1和M2的有向弧條數(shù)相等M1和M2所識(shí)別的語言集相等D.M1和M2狀態(tài)數(shù)和有向弧條數(shù)相等9.詞法分析器作為獨(dú)立的階段使整個(gè)編譯程序結(jié)構(gòu)更加簡(jiǎn)潔、明確，因此，(B)A.詞法分析器應(yīng)作為獨(dú)立的一遍B.詞法分析器作為子程序較好C.詞法分析器分解為多個(gè)過程，由語法分析器選擇使用.D.詞法分析器并不作為一個(gè)獨(dú)立的階段.如果L(M1)=L(M2),貝UM1與M2(A)A.等價(jià) B.都是二義的C.都是無二義的D.它們的狀態(tài)數(shù)相等.文法G：S-xSxly所識(shí)別的語言是(C)A.xyxB.(xyx)*c.xnyxn(nN0) d.x*yx*.文法G描述的語言L(G)是指(A)A.L(G)=卜|SBa,aeV*\B.L(G)=卜|SBa,ae(VTuVN)*\C.L(G)=]a|S=*>a,aeV*[D.L(G)=<!a|S=*>a,ae(VuV)*I TJ I TN.有限狀態(tài)自動(dòng)機(jī)能識(shí)別(C)A.上下文無關(guān)文法 B.上下文有關(guān)文法C.正規(guī)文法 D.短語文法.如果文法G是無二義的，則它的任何句子(A)A.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同B.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同C.最左推導(dǎo)和最右推導(dǎo)必定相同D.可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同.由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是(C)A.短語B.句柄C.句型D.句子.文法G：EfE+T|TTT*P|PPf(E)|i則句型P+T+i的句柄為(B)A.P+TB.PC.P+T+iD.i.文法G：Sfb|A|(T)TTVS|S則FIRSTVT(T)=(C)A.{b，A，(} B.{b，A，)}C.{b,A,(,V}D.{b,A,),V}.產(chǎn)生正規(guī)語言的文法為(D)A.0型B.1型C.2型D.3型.任何算符優(yōu)先文法(D)優(yōu)先函數(shù)。A.有一個(gè)B.沒有C.有若干個(gè)D.可能有若干個(gè).采用自上而下分析，必須(A)A.消除左遞歸 B.消除右遞歸C.消除回溯 D.提取公共左因子.在規(guī)范歸約中，用(B)來刻畫可歸約串。A.直接短語 B.句柄C.最左素短語D.素短語.有文法G：EfE*T|TTfT+i|i句子1+2*8+6按該文法G歸約，其值為(B)A.23 B.42 C.30 D.17.如果文法是無二義的，那么規(guī)范歸約是指(B)A.最左推導(dǎo)的逆過程 B.最右推導(dǎo)的逆過程C.規(guī)范推導(dǎo) 口.最左歸約的逆過程.文法G:SfS+T|TTfT*P|PPf(S)|i句型P+T+i的短語有(B)A.i,P+TB.P,P+T,i,P+T+iC.P+T+iD.P，P+T，i.四元式之間的聯(lián)系是通過(B)實(shí)現(xiàn)的。A.指示器B.臨時(shí)變量 C.符號(hào)表D.程序變量.后綴式ab+cd+/可用表達(dá)式（B）來表示。A.a+b／c+dB.（a+b）／（c+d） C.a+b／（c+d）D.a+b+c／d.使用間接三元式表示法的主要目的（A）A.便于優(yōu)化處理 B.便于表的修改C.節(jié)省存儲(chǔ)空間 D.生成中間代碼更容易.表達(dá)式JAVB）A（CVD）的逆波蘭表示為（B）A.nABVACDVB.AnBVCDVAC.ABVnCDVAD.AnBVACDV二、判斷題TOC\o"1-5"\h\z.一個(gè)確定有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。 （X）.設(shè)R和S分別是字母表￡上的正規(guī)式，則有L（R|S）=L（R）UL（S）。（J）.自動(dòng)機(jī)M1和M2的狀態(tài)數(shù)不同，則二者必不等價(jià)。 （X）.確定有限自動(dòng)機(jī)以及非確定有限自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。 （J）.對(duì)任意一個(gè)右線性正規(guī)文法G,都存在一個(gè)NFAM,滿足L（G）=L（M）。 （J）.對(duì)任意一個(gè)右線性正規(guī)文法G,都存在一個(gè)DFAM,滿足L（G）=L（M）0（J）.對(duì)任何正規(guī)式e,都存在一個(gè)NFAM,滿足L（M）=L（e）0（J）.對(duì)任何正規(guī)式e,都存在一個(gè)DFAM,滿足L（M）=L（e）0（J）.從一個(gè)句型到另一個(gè)句型的推導(dǎo)過程是唯一的。（X）.詞法分析作為單獨(dú)的一遍來處理較好。 （X）.一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。（X）.二義文法不是上下文無關(guān)文法。（X）.自上而下分析法是一種“移進(jìn)一歸約”法。（X）.文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則。（J）.產(chǎn)生式是定義語法范疇的一種書寫規(guī)則。（J）.要構(gòu)造行之有效的自上而下的分析器，則必須消除左遞歸。（X）.如果文法G是無二義的，那么規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（J）.自下而上的分析法是一種“移進(jìn)一歸約”法。（J）.如果文法G是二義的，那么規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（X）三、填空題解釋程序和編譯程序的區(qū)別在于（是否生成目標(biāo)代碼）。編譯過程通?？煞譃?個(gè)階段,分別是（詞法分析）、（語法分析）、語義分析與中間代碼產(chǎn)生、代碼優(yōu)化和目標(biāo)代碼生成。編譯程序工作過程中,第一階段輸入是（源程序）,最后階段的輸出為（目標(biāo)代碼）程序。把語法范疇翻譯成中間代碼所依據(jù)的是（語義規(guī)則）。目標(biāo)代碼可以是（匯編）指令代碼或（可重定位）指令代碼或絕對(duì)機(jī)器指令代碼。詞法分析的任務(wù)是：輸入源程序,對(duì)構(gòu)成源程序的（字符串）進(jìn)行掃描和分解。源程序中的錯(cuò)誤通常分為（語法錯(cuò)誤）和（語義錯(cuò)誤）兩大類。（編譯程序）是將源程序翻譯成目標(biāo)程序的程序。一個(gè)上下文無關(guān)文法G包括四個(gè)部分：（終結(jié)符號(hào)）、（非終結(jié)符號(hào)）、（開始符號(hào)）和一組（產(chǎn)生式）。.若ananAna，則稱這個(gè)序列是從a到a的一個(gè)（推導(dǎo)）。1 2 n 1n.設(shè)文法G的開始符號(hào)為S,如果Sna則稱a是L（G）的一個(gè)（句型）。.文法G所產(chǎn)生的句子的全體是文法G所定義的（語言）。13．若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)的兩棵不同的語法樹，則稱這個(gè)文法是（二義文法）。14．程序語言的單詞符號(hào)一般可分為五種：（關(guān)鍵字）、（標(biāo)識(shí)符）、常數(shù)、（運(yùn)算符）和界符。.（確定有限自動(dòng)機(jī)DFA）是非確定有限自動(dòng)機(jī)NFA的一個(gè)特例。.對(duì)于正規(guī)文法G和有限自動(dòng)機(jī)M,若L（G）=L（M）,則稱G和M是（等價(jià)）的。17．若兩個(gè)正規(guī)式所表示的正規(guī)集相等，則認(rèn)為二者是（等價(jià)）的。.按照語法分析樹的建立方法，語法分析可分為兩類：（自上而下分析）和（自下而上分析）。18.規(guī)范歸約中的可歸約串是指（句柄）。.算符優(yōu)先分析中的可歸約串是指（最左素短語）。.（自下而上）語法分析的關(guān)鍵問題是精確定義可歸約串的概念。四、簡(jiǎn)答.給出上下文無關(guān)文法的定義。一個(gè)上下文無關(guān)文法G是一個(gè)四元式（V,V,S,P）,其中：V是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)；TV是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，VUV=①；SN是一個(gè)非終結(jié)符號(hào)，稱為開始符號(hào)； TNP是一個(gè)產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式的形式是Pfa,其中，P￡VN,ae（VTuv）*o N T開始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。.給出正規(guī)式與正規(guī)集的遞歸定義。⑴￡和①都是￡上的正規(guī)式，它們所表示的正規(guī)集分別為｛￡｝和①；（2）任何aeE,a是￡上的一個(gè)正規(guī)式，它所表示的正規(guī)集為｛a｝；（3）假定U和V都是￡上的正規(guī)式，它們所表示的正規(guī)集分別記為L（U）和L（V）,那么，（U|V）、（U-V）和（U）*也都是正規(guī)式，它們所表示的正規(guī)集分別為L（U）UL（V）、L（U）L（V）（連接積）和（L（U））*（閉包）。僅由有限次使用上述三步驟而得到的表達(dá)式才是￡上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是￡上的正規(guī)集。.設(shè)文法G為：SfaAcB|BdSAfBaB|aBc|aBfaScA|cAB|b對(duì)于輸入串a(chǎn)acabccb,給出最左推導(dǎo)。S=>aAcB=>aaBccB=>aacABccB=>aacaBccB=>aacabccB=>aacabccb.設(shè)文法G為：SfBAAfBS|dBfaA|bS|c對(duì)于輸入串a(chǎn)dccd,給出最左推導(dǎo)。S=>BA=>aAA=>adA=>adBS=>adcS=>adcBA=>adccA=>adccd.證明：文法G：PfPaP|PbP|cP|Pe|f為二義文法。對(duì)于文法G定義的句子fbfbf,有兩棵不同的語法樹：

所以該文法是二義文法。:\.證明：文法G：,Pb>P-S+S|S*H（S）為二義文法為Pf對(duì)于文法G定義的句子1+南，有兩棵不同的語法樹:所以該文法是二義文法。］\gHIPQL'q7?給定正規(guī)文法G.S、,*SS-aS同bA-SaS+Si請(qǐng)構(gòu)造與之等價(jià)的有限自動(dòng)機(jī)。8.給定正規(guī)文法G:i iS-aAA-bA|aB|bB-aA請(qǐng)構(gòu)造與之等價(jià)的有限自動(dòng)機(jī)。Sbfi.對(duì)下面給出的NFA確定化。SbfiSJ—對(duì)下面給出的NFA確定化。baa對(duì)下面給出的DFA最小化。有如下布爾表達(dá)式a<bandZC<ifa<bgOtogotoLfalseL1:ifc<dgotogotoL2

L2:ife<fgotoLtruegotoLfalse14.有如下語句:ifa<bthenifc<dthenp:=a+1elsep:=b+1elsep:=c+1請(qǐng)翻譯成三地址語句。ifa<bgotoL1gotoL2L1:ifc<dgotoL3gotoL4L3:T1:=a+1p:=T1gotoL5L4:T2:=b+1p:=T2L5:gotoLnextL2:T3:=c+1p:=T3Lnext:…五、語法分析.設(shè)有文法G:S—a|b|(A)A-SdA|S⑴完成下列算符優(yōu)先關(guān)系表，并判斷是否為算符優(yōu)先文法(請(qǐng)說明理由)。ab()d#a?〉?〉?〉b?〉?〉?〉(<?<?<?;<?)?〉?〉?〉d<?<?<??〉<??〉#<?<?<?二由于該文法的任何產(chǎn)生的右部都不含兩個(gè)相繼的非終結(jié)符，故屬于算符文法。從上表可以看出，任何兩個(gè)終結(jié)符之間至多滿足=、＜-、-＞三種關(guān)系之一，故G為算符優(yōu)先文法。SdSS*S(''A')(請(qǐng)說明理由)。⑵給出句型(SdSdS)對(duì)應(yīng)的語法樹，指出該句型的短語、句柄SdSS*S(''A')(請(qǐng)說明理由)。短語：(SdSdS)SdSdS句柄：S*t(S1)i*t(S1)i#*