編譯原理期末考試題目及答案一、選擇題（每題2分，共20分）1.編譯程序是對（）。A.匯編語言的翻譯B.高級語言的翻譯C.機器語言的執(zhí)行D.高級語言程序的解釋執(zhí)行答案：B。編譯程序是將高級語言源程序翻譯成目標機器的機器語言或匯編語言的程序。2.詞法分析器的輸出結果是（）。A.單詞的種別編碼B.單詞在符號表中的位置C.單詞的種別編碼和自身值D.單詞自身值答案：C。詞法分析器從源程序中識別出一個個單詞，并輸出單詞的種別編碼和自身值。3.一個句型中的最左（）稱為該句型的句柄。A.短語B.簡單短語C.素短語D.終結符號答案：B。句柄是一個句型中的最左簡單短語。4.算符優(yōu)先分析法每次都是對（）進行歸約。A.句柄B.最左素短語C.素短語D.簡單短語答案：B。算符優(yōu)先分析法每次歸約的是最左素短語。5.四元式之間的聯(lián)系是通過（）實現(xiàn)的。A.指示器B.臨時變量C.符號表D.程序變量答案：B。四元式之間的聯(lián)系通常通過臨時變量來實現(xiàn)。6.代碼優(yōu)化的目的是（）。A.節(jié)省時間B.節(jié)省空間C.節(jié)省時間和空間D.把編譯程序進行等價變換答案：C。代碼優(yōu)化的目的是提高目標程序的執(zhí)行效率，即節(jié)省時間和空間。7.編譯程序使用（）區(qū)別標識符的作用域。A.語法樹B.符號表C.控制流圖D.三元式答案：B。符號表用于記錄標識符的各種信息，包括作用域等。8.若文法G定義的語言是無限集，則文法必然是（）。A.遞歸的B.前后文無關的C.二義性的D.無二義性的答案：A。只有遞歸的文法才能產(chǎn)生無限集的語言。9.（）不是編譯程序的組成部分。A.詞法分析程序B.代碼提供程序C.設備管理程序D.語法分析程序答案：C。編譯程序主要由詞法分析程序、語法分析程序、語義分析程序、中間代碼提供程序、代碼優(yōu)化程序和代碼提供程序等組成，設備管理程序不屬于編譯程序的組成部分。10.設有文法G[S]：S→a|(T)，T→T,S|S，該文法（）。A.是LL(1)文法B.是算符優(yōu)先文法C.是SLR(1)文法D.不是算符優(yōu)先文法答案：B。通過對該文法的算符優(yōu)先關系的分析，可以判斷它是算符優(yōu)先文法。二、填空題（每空2分，共20分）1.編譯過程可分為詞法分析、語法分析、語義分析、中間代碼提供、代碼優(yōu)化和代碼提供六個階段。2.一個上下文無關文法包含四個組成部分，即一組終結符號、一組非終結符號、一個開始符號和一組產(chǎn)生式。3.自頂向下語法分析方法會遇到的主要問題有左遞歸和回溯。4.常用的兩種動態(tài)存儲分配策略是棧式存儲分配和堆式存儲分配。三、判斷題（每題2分，共10分）1.編譯程序提供的目標程序一定是可執(zhí)行的程序。（×）編譯程序提供的目標程序可能是匯編語言程序或機器語言程序，不一定是可執(zhí)行的，還需要經(jīng)過鏈接等操作。2.一個文法所有句型的集合就是該文法所定義的語言。（×）一個文法所有句子的集合才是該文法所定義的語言，句型包含句子和含非終結符的形式。3.算符優(yōu)先分析法只能分析算符優(yōu)先文法。（√）算符優(yōu)先分析法是針對算符優(yōu)先文法設計的分析方法。4.代碼優(yōu)化是對中間代碼或目標代碼進行等價變換，以提高程序的執(zhí)行效率。（√）代碼優(yōu)化的本質(zhì)就是進行等價變換來提高效率。5.詞法分析和語法分析本質(zhì)上都是對源程序的掃描，所以可以合并成一個階段。（×）詞法分析和語法分析雖然都有掃描操作，但它們的任務和處理對象不同，不能簡單合并。四、簡答題（每題10分，共30分）1.簡述編譯程序和解釋程序的區(qū)別。編譯程序是將高級語言源程序一次性翻譯成目標機器的機器語言或匯編語言程序，然后再執(zhí)行該目標程序。編譯過程完成后，源程序就不再參與執(zhí)行過程，執(zhí)行速度相對較快，適合處理大型程序。例如，C語言程序通過編譯程序提供可執(zhí)行文件后，后續(xù)直接執(zhí)行該可執(zhí)行文件。解釋程序則是對高級語言源程序逐句進行解釋執(zhí)行，即每讀入一句源程序，就對其進行解釋并執(zhí)行，不提供目標程序。解釋程序的執(zhí)行效率相對較低，但是具有較好的交互性和可移植性，適合快速開發(fā)和調(diào)試程序，如Python語言通常使用解釋程序來執(zhí)行。2.什么是LL(1)文法？判斷一個文法是否為LL(1)文法的步驟有哪些？LL(1)文法是一種自頂向下的分析文法。第一個L表示從左到右掃描輸入串，第二個L表示最左推導，1表示在分析過程中只需要向前看一個輸入符號。判斷一個文法是否為LL(1)文法的步驟如下：（1）計算每個非終結符的FIRST集。FIRST(α)是由符號串α所能推導出的所有可能的終結符串的首終結符組成的集合，如果α能推導出ε，則ε也屬于FIRST(α)。（2）計算每個非終結符的FOLLOW集。FOLLOW(A)是指在所有句型中緊跟在非終結符A后面的終結符的集合，對于開始符號，要在其FOLLOW集中加入結束符。（3）對于文法中的每個非終結符A的產(chǎn)生式A→α1|α2|…|αn，計算SELECT(A→αi)集。SELECT(A→αi)=FIRST(αi)（如果αi不能推導出ε）；SELECT(A→αi)=(FIRST(αi){ε})∪FOLLOW(A)（如果αi能推導出ε）。（4）檢查對于每個非終結符A的任意兩個不同的產(chǎn)生式A→α和A→β，是否有SELECT(A→α)∩SELECT(A→β)=?。如果所有非終結符的產(chǎn)生式都滿足這個條件，則該文法是LL(1)文法。3.簡述代碼優(yōu)化的主要類型。代碼優(yōu)化主要有以下幾種類型：（1）局部優(yōu)化：是在基本塊內(nèi)進行的優(yōu)化?；緣K是指程序中順序執(zhí)行的語句序列，其中只有一個入口和一個出口。局部優(yōu)化包括刪除公共子表達式、復寫傳播、刪除無用代碼等。例如，在一個基本塊內(nèi)，如果有多次計算相同的表達式，就可以刪除重復的計算，只保留一次計算結果。（2）循環(huán)優(yōu)化：針對程序中的循環(huán)結構進行的優(yōu)化。常見的循環(huán)優(yōu)化技術有代碼外提、強度削弱、刪除歸納變量等。代碼外提是將循環(huán)中不變的代碼提到循環(huán)外面，減少循環(huán)內(nèi)的計算量；強度削弱是將強度大的運算替換為強度小的運算，如將乘法替換為加法；刪除歸納變量是消除循環(huán)中不必要的變量。（3）全局優(yōu)化：在整個程序范圍內(nèi)進行的優(yōu)化。它考慮程序中不同基本塊之間的關系，例如公共子表達式的刪除可以跨越多個基本塊進行。全局優(yōu)化還包括數(shù)據(jù)流分析，通過分析程序中數(shù)據(jù)的流動情況來進行優(yōu)化。五、綜合題（每題10分，共20分）1.已知文法G[S]：S→aABeA→b|AbB→d（1）構造該文法的FIRST集和FOLLOW集。FIRST集：FIRST(S)={a}FIRST(A)=FIRST(B)=b11zvbbFOLLOW集：FOLLOW(S)={}FOLLOW(A)=fbbdjv1FOLLOW(B)={e}（2）判斷該文法是否為LL(1)文法。對于非終結符A，其產(chǎn)生式為A→b|Ab。SELECT(A→b)=FIRST(b)=SELECT(A→Ab)=FIRST(Ab)=因為SELECT(A→b)∩SELECT(A→Ab)=≠?，所以該文法不是LL(1)文法。2.給出表達式(a+b)c