《編譯原理》考試題

《編譯原理》考試題一、選擇題：(每題2分，共20分)文法G所描述的語言是 的集合。文法G的字匯表V中所有符號組成的符號串文法G的字匯表V的閉包V*中的所有符號串由文法的識別符號推出的所有符號串由文法的識別符號推出的所有終結(jié)符號串設(shè)有文法G[S]=(,{S,B},S,{S-b|bB,B-bS})，試問該文法所描述的語言是 。A)L(G[S])={bi|i>0} B)L(G[S])={b2i|i>0}C)L(G[S])={b2i+1|i>0} D)L(G[S])={b2i+1|i>1}—個句型中的最左 稱為該句型的句柄。A，短語 B，簡單短語C)素短語 D，終結(jié)符號 正則文法能產(chǎn)生下面的語言：L={anbn|n》1}。A，存在一個 B，存在多個C)不存在 D，無法判斷編譯程序中的語法分析器接受以 為單位的輸入，并產(chǎn)生有關(guān)信息供以后各階段使用。A)表達(dá)式 B)產(chǎn)生式C)單詞 D，語句編譯方法中，自頂向下的語法分析方法有_A，簡單優(yōu)先分析方法 B，算符優(yōu)先分析方法C)SLR方法 D)LL(1)分析方法簡單優(yōu)先分析法每次都是對 進(jìn)行歸約。A，最左短語 B，簡單短語C)句柄 D，最左素短語LR語法分析棧中存放的狀態(tài)是識別 的DFA狀態(tài)。A，前綴 B，可歸前綴C)項(xiàng)目 D，句柄表達(dá)式-(a+b)/(c-d)-(a+b*c，的逆波蘭表示是 (@代表單目運(yùn)算-)A)ab+cd-/@bc*a+- B)ab+/cd@bc*a+--C)ab+@cd-/abc*+- D)ab+cd-/abc*+@-TOC\o"1-5"\h\z10?喬姆斯基(Chomsky)把文法分成四種類型，即0型、1型、2型和3型。其中，3型文法是 。A，上下文無關(guān)文法 B，上下文有關(guān)文法C)正則文法 D，短語文法二、 填空題：(每空1分，共20分)假設(shè)G是一個文法，S是文法的開始符號，如果*x，則稱x是 。2?已知文法G[E]:E-E+T|T,T-T*F|F，F(xiàn)-(E)|i;該文法的開始符號是 ，終結(jié)符號集合 Vt是 ，非終結(jié)符號集合 Vn是 ，句型T+T*F+i的短語有T+T*F+i，第一個T,T*F和 。3?確定的有限自動機(jī)DFA是一個 ，通常表示為 。LL(1)分析法中，第一個L的含義是 ，第二個L的含義是 ，“1”的含義是 。5?自底向上語法分析方法的基本思想是：從待輸入的符號串開始，利用文法的規(guī)則步步向上進(jìn)行 ，試圖 到文法的 。在編譯程序中安排中間代碼生成的目的是 和 。文法符號的屬性有兩種，一種稱為 ，另一種稱為 ?！獋€程序是正確的，包含兩層含義：一是 ；二是文法G產(chǎn)生的 全體是該文法描述的語言。三、 判斷題：(每題2分，共20分)符號就是字符。移進(jìn)一歸約法是一種語法分析方法。每一個NFA都對應(yīng)有唯一的一個最小化的DFA。編譯程序的輸入是高級語言程序，輸出是機(jī)器語言程序。編譯程序與解釋程序的區(qū)別在于編譯程序?qū)υ闯绦蜻M(jìn)行了翻譯，而解釋程序則沒有。有的編譯程序可以沒有目標(biāo)代碼生成部分?！獋€語言的文法是唯一的。每一個DFA都對應(yīng)有唯一的一個NFA。所有的LL(K)文法都是二義性的。10回填就是稍后填寫轉(zhuǎn)移指令的地址。四、應(yīng)用題：(每題5分，共40分)1?請消除文法G[S]:S-a|(T)|；T-T;S|S的左遞歸。請構(gòu)造語言L={anbnc[n》1,i>0}的文法。3?已知文法G[S]:S—aB|bA,A—aS|bAA|a,B—bS|aBB|b,請給出串a(chǎn)abb的最左和最右推導(dǎo)。為正規(guī)式(a|b)*a(a|b)構(gòu)造一個非確定的有限自動機(jī)(NFA)。請將圖中的DFA最小化(寫明過程)?？紤]文法G[A]:A—AVB|B,B—BAC|C, D|D,D—(A)|i,請求出該文法中各非終結(jié)符的FIRST集和FOLLOW集，并判斷該文法是否是LL(1)文法。請給