編譯原理考試及答案

一、單項選擇題（每題2分，共20分）1.編譯程序前三個階段完成的工作是（）A.詞法分析、語法分析和代碼優(yōu)化B.代碼生成、代碼優(yōu)化和詞法分析C.詞法分析、語法分析和語義分析D.詞法分析、語法分析和目標(biāo)代碼生成答案：C2.詞法分析器的輸出結(jié)果是（）A.單詞的種別編碼B.單詞在符號表中的位置C.單詞的種別編碼和自身值D.單詞自身值答案：C3.正規(guī)式M1和M2等價是指（）A.M1和M2的狀態(tài)數(shù)相等B.M1和M2的有向邊條數(shù)相等C.M1和M2所識別的語言集相等D.M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等答案：C4.語法分析器可以發(fā)現(xiàn)源程序中的（）A.語義錯誤B.語法和語義錯誤C.錯誤并校正D.語法錯誤答案：D5.下面關(guān)于算符優(yōu)先分析法的說法正確的是（）A.算符優(yōu)先分析法是一種規(guī)范歸約分析法B.算符優(yōu)先分析法比規(guī)范歸約分析法效率高C.算符優(yōu)先分析法不會出現(xiàn)移進(jìn)-歸約沖突D.算符優(yōu)先分析法中只考慮終結(jié)符之間的優(yōu)先關(guān)系答案：D6.一個上下文無關(guān)文法消除了左遞歸，提取了左公共因子后是滿足LL(1)文法的（）A.必要條件B.充分條件C.充要條件D.既不充分也不必要條件答案：A7.下列（）優(yōu)化方法不是針對循環(huán)優(yōu)化進(jìn)行的。A.強(qiáng)度削弱B.刪除歸納變量C.合并已知量D.代碼外提答案：C8.中間代碼生成時所依據(jù)的是（）A.語法規(guī)則B.詞法規(guī)則C.語義規(guī)則D.等價變換規(guī)則答案：C9.代碼優(yōu)化的目的是（）A.節(jié)省時間B.節(jié)省空間C.節(jié)省時間和空間D.把編譯程序進(jìn)行等價交換答案：C10.編譯程序是對（）A.匯編程序的翻譯B.高級語言程序的解釋執(zhí)行C.機(jī)器語言的執(zhí)行D.高級語言的翻譯答案：D二、多項選擇題（每題2分，共20分）1.編譯程序的階段包括（）A.詞法分析B.語法分析C.語義分析D.代碼優(yōu)化E.代碼生成答案：ABCDE2.下面哪些是詞法分析的工具（）A.有窮自動機(jī)B.正規(guī)式C.語法樹D.優(yōu)先矩陣E.狀態(tài)轉(zhuǎn)換圖答案：ABE3.語法分析中常用的分析方法有（）A.自頂向下B.自底向上C.自左向右D.自右向左E.自內(nèi)向外答案：AB4.下面關(guān)于LL(1)文法的說法正確的有（）A.第一個L表示從左到右掃描輸入串B.第二個L表示最左推導(dǎo)C.LL(1)文法是無二義性的D.LL(1)文法可能存在回溯E.任何LL(1)文法都是遞歸可枚舉的答案：ABC5.算符優(yōu)先關(guān)系表的構(gòu)造需要考慮（）A.終結(jié)符之間的優(yōu)先關(guān)系B.非終結(jié)符之間的優(yōu)先關(guān)系C.句柄D.最左素短語E.規(guī)范句型答案：AD6.代碼優(yōu)化的種類有（）A.局部優(yōu)化B.循環(huán)優(yōu)化C.全局優(yōu)化D.中間代碼優(yōu)化E.目標(biāo)代碼優(yōu)化答案：ABC7.符號表的作用有（）A.收集符號的屬性B.輔助語義檢查C.輔助代碼生成D.優(yōu)化代碼E.消除二義性答案：ABC8.下面哪些屬于中間代碼形式（）A.逆波蘭式B.四元式C.三元式D.樹形表示E.后綴式答案：ABCDE9.目標(biāo)代碼的形式有（）A.絕對機(jī)器語言代碼B.可重定位機(jī)器語言代碼C.匯編語言代碼D.高級語言代碼E.中間語言代碼答案：ABC10.編譯程序和解釋程序的區(qū)別在于（）A.編譯程序生成目標(biāo)代碼，解釋程序不生成B.編譯程序執(zhí)行效率高，解釋程序執(zhí)行效率低C.編譯程序不生成目標(biāo)代碼，解釋程序生成D.編譯程序執(zhí)行效率低，解釋程序執(zhí)行效率高E.編譯程序和解釋程序都生成目標(biāo)代碼答案：AB三、判斷題（每題2分，共20分）1.編譯程序是將高級語言程序翻譯成匯編語言程序。（）答案：×2.詞法分析器的任務(wù)是從源程序中識別出一個個單詞。（）答案：√3.一個正規(guī)式只能對應(yīng)一個確定的有限自動機(jī)。（）答案：×4.語法分析時必須先消除文法的左遞歸。（）答案：×5.算符優(yōu)先分析法每次都是對句柄進(jìn)行歸約。（）答案：×6.LL(1)文法一定是無二義性的。（）答案：√7.中間代碼生成時不考慮目標(biāo)機(jī)器的特性。（）答案：√8.局部優(yōu)化是在基本塊內(nèi)進(jìn)行的優(yōu)化。（）答案：√9.符號表在編譯的全過程中都起作用。（）答案：√10.編譯程序生成的目標(biāo)代碼一定是機(jī)器語言代碼。（）答案：×四、簡答題（每題5分，共20分）1.簡述編譯程序的工作過程。答案：編譯程序工作過程分詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成。詞法分析將源程序分割成單詞；語法分析構(gòu)建語法樹；語義分析檢查語義；中間代碼生成便于優(yōu)化；代碼優(yōu)化提高效率；目標(biāo)代碼生成最終機(jī)器可執(zhí)行代碼。2.簡述正規(guī)式和有窮自動機(jī)的關(guān)系。答案：正規(guī)式和有窮自動機(jī)等價。任何正規(guī)式都能構(gòu)造一個與之等價的有窮自動機(jī)，反之，任何有窮自動機(jī)也能構(gòu)造出一個與之等價的正規(guī)式。這種等價性為詞法分析提供了理論基礎(chǔ)和實現(xiàn)途徑。3.簡述LL(1)文法的判別條件。答案：對于文法的每一個非終結(jié)符A的任何兩個不同產(chǎn)生式A→α|β，需滿足：First(α)∩First(β)=?；若β=>ε，則First(α)∩Follow(A)=?。滿足這些條件的文法就是LL(1)文法。4.簡述代碼優(yōu)化的原則。答案：代碼優(yōu)化原則有等價原則，優(yōu)化后不能改變程序運(yùn)行結(jié)果；有效原則，優(yōu)化能提高目標(biāo)代碼效率；合算原則，優(yōu)化付出代價小于帶來的效益，在時間和空間上達(dá)到平衡。五、討論題（每題5分，共20分）1.討論自頂向下和自底向上語法分析方法的優(yōu)缺點。答案：自頂向下優(yōu)點是直觀，易實現(xiàn)遞歸下降分析法；缺點是對文法要求高，可能存在回溯，效率低。自底向上優(yōu)點是對文法限制少，分析效率較高；缺點是分析過程較復(fù)雜，需要計算優(yōu)先關(guān)系等，出錯處理相對復(fù)雜。2.討論符號表在編譯過程中的重要性。答案：符號表很重要。它收集符號屬性，輔助語義檢查，保證標(biāo)識符使用合法。在代碼生成階段提供必要信息，幫助確定存儲分配等。貫穿編譯全程，是編譯程序正確工作和代碼生成優(yōu)化的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)。3.討論代碼優(yōu)化對編譯程序的意義。答案：代碼優(yōu)化能提高目標(biāo)代碼的質(zhì)量，減少運(yùn)行時間和存儲空間開銷。通過局部、循環(huán)、全局優(yōu)化等，使程序執(zhí)行更高效。優(yōu)化后的代碼可提升軟件性能，增強(qiáng)軟件競爭力