中國地質大學（北京）繼續(xù)教育學院2016年03課程考試第7頁(共7頁)《編譯原理》模擬題（補）單項選擇題1.（）是兩類程序語言處理程序。A.高級語言程序和低級語言程序 B.解釋程序和編譯程序C.編譯程序和操作系統(tǒng) D.系統(tǒng)程序和應用程序2.編譯程序前三個階段完成的工作是（）。A.詞法分析、語法分析和代碼優(yōu)化B.代碼生成、代碼優(yōu)化和詞法分析C.詞法分析、語法分析、語義分析和中間代碼生成D.詞法分析、語法分析和代碼優(yōu)化3.一個上下文無關文法G包括四個組成部分：一組終結符，一組非終結符，一個開始符號，以及一組（）。A.字符串 B.產生式 C.非開始符號 D.文法4.詞法分析器的輸出結果是（）。A.單詞的種別編碼 B.單詞在符號表中的位置C.單詞的種別編碼和自身值 D.單詞自身值5.一個句型中稱為句柄的是該句型的最左（）。A.非終結符號 B.短語 C.句子 D.直接短語6.高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（）分析方法。A.自左向右 B.自頂向下 C.自底向上 D.自右向左7.在通常的語法分析方法中，（）特別適用于表達式的分析。A.算符優(yōu)先分析法 B.LR分析法C.遞歸下降分析法 D.LL（1）分析法8.優(yōu)化可生成_____的目標代碼。A.運行時間較短 B.占用存儲空間較小C.運行時間短但占用內存空間大 D.運行時間短且占用存儲空間小9.（）是兩類程序語言處理程序。A.系統(tǒng)程序和應用程序 B.編譯程序和操作系統(tǒng)C.解釋程序和編譯程序 D.高級語言程序和低級語言程序10.經過編譯所得到的目標程序是（）。A.四元式序列 B.間接三元式序列C.二元式序列 D.機器語言程序或匯編語言程序11.程序的基本塊是指（）。A.一個子程序B.一個僅有一個入口和一個出口的語句C.一個沒有嵌套的程序段D.一組順序執(zhí)行的程序段，僅有一個入口和一個出口12.一個上下文無關文法G包括四個組成部分：一組終結符，一組非終結符，一個開始符號，以及一組（）。A.字符串 B.產生式 C.非開始符號 D.文法13.文法G產生的（）的全體是該文法描述的語言。A.句型 B.終結符集 C.非終結符集 D.句子14.詞法分析器用于識別（）。A.字符串 B.語句 C.單詞 D.標識符15.常用的中間代碼形式不含（）。A.三元式 B.四元式 C.逆波蘭式 D.語法樹16.下列______優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A.強度削弱 B.刪除歸納變量 C.刪除多余運算 D.代碼外提填空題1.一個名字的屬性包括（）和作用域。2.一張轉換圖只包含有限個狀態(tài),其中有一個被認為是初態(tài)，而且實際上至少要有一個（）。3.規(guī)范規(guī)約是最（）規(guī)約。4.語法分析器的輸入是（），其輸出是語法單位。5.語法分析的有效工具是（）。6.一個LR分析器包括兩部分：一個總控程序和（）。7.中間代碼產生（）是依據語言的規(guī)則進行的。8.編譯方式與解釋方式的根本區(qū)別在于（）。9.編譯程序的工作過程一般劃分為5個階段：詞法分析、（）、語義分析與中間代碼生成，代碼優(yōu)化及目標代碼生成。10.掃描器的任務是從源程序中識別出一個個（）。11.詞法分析基于（）文法進行，即識別的單詞是該類文法的句子。12.語法分析的有效工具是（）。13.語法分析最常用的兩類方法是（）和自下而上分析法。14.分析句型時，應用算符優(yōu)先分析技術時，每步被直接歸約的是（）。判斷題1.一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。 （）2.正規(guī)文法產生的語言都可以用上下文無關文法來描述。 （）3.確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。 （）4.如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。（）5.綜合屬性是用于“自上而下”傳遞信息。 （）6.遞歸下降分析法是自頂向上分析方法。 （）7.一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應。 （）8.LR法是自頂向下語法分析方法。 （）9.產生式是用于定義詞法成分的一種書寫規(guī)則。 （）10.一個句型的句柄一定是文法某產生式的右部。 （）11.每個文法都能改寫為LL(1)文法。 （）12.語法分析時必須先消除文法中的左遞歸。 （）13.規(guī)范歸約和規(guī)范推導是互逆的兩個過程。 （）14.算符優(yōu)先關系表不一定存在對應的優(yōu)先函數(shù)。 （）15.LR法是自頂向下語法分析方法。 （）16.對中間代碼的優(yōu)化依賴于具體的計算機。 （）簡答題1.寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。2.已知文法G[S]為 S→aSb|Sb|b，試證明文法G[S]為二義文法。3.文法G(S) S→dAB A→aA|a B→Bb|ε描述的語言是什么？4.寫一個文法使其語言為偶數(shù)集，且每個偶數(shù)不以0開頭。5.證明文法G(S) S→SaS|ε是二義性的。五、程序設計題1.已知文法G(S)：S→a|∧|(T)T→T,S|S寫出句子((a，a)，a)的規(guī)范歸約過程及每一步的句柄。2.已知文法G[E]:E→ETE|(E)|iT→*|+將文法G改造成LL（1）文法；構造文法G中每個非終結符的FIRST集合及FOLLOW集合；構造LL（1）分析表。參考答案：單項選擇題12345678BCBCDBAD910111213141516CDDBDCDC二．填空題1.類型2.終態(tài)3.左4.單詞符號串5.語法樹6.一張分析表7.語義8.是否生成目標代碼9.語法分析10.單詞符號11.正則12.語法樹13.自上而下14.最左素短語三．判斷題12345678╳╳√√╳√√╳910111213141516╳√√╳╳╳╳╳四.簡答題1.文法G(N)：N→AB|BA→AC|DB→1|3|5|7|9D→B|2|4|6|8C→0|D2.證明：由文法G[S]：S→aSb|Sb|b，對句子aabbbb對應的兩棵語法樹為：因此，文法G[S]為二義文法。L(G)={danbm|n>0,m≥0}4.文法G(S)：S→AB|B|A0A→AD|CB→2|4|6|8C→1|3|5|7|9|BD→0|C5.證明：因為文法G[S]存在句子aa有兩個不同的最左推導，所以文法G[S]是是二義性的。S=>SaS=>SaSaS=>aSaS=>aaS=>aaS=>SaS=>aS=>aSaS=>aaS=>aa五.程序設計題1.句型 歸約規(guī)則 句柄((a，a)，a) S→a a((S，a)，a) T→S S((T，a)，a) S→a a((T，S)，a) T→T，S T，S((T)，a) S→(T) (T)(S，a) T→S S(T，a) S→a a(T，S) T→T，S T，S(T) S→(T) (T)S2.文法存在左遞歸，消除左遞歸后的文法為：E→(E)E‘|i