編譯原理試卷及答案

一、單項選擇題1.編譯程序前三個階段完成的工作是（）A.詞法分析、語法分析和代碼優(yōu)化B.代碼生成、代碼優(yōu)化和詞法分析C.詞法分析、語法分析和語義分析D.詞法分析、語法分析和目標代碼生成答案：C2.詞法分析器的輸出結果是（）A.單詞的種別編碼B.單詞在符號表中的位置C.單詞的種別編碼和自身值D.單詞自身值答案：C3.語法分析器的輸入是（）A.單詞符號串B.源程序C.語法單位D.目標程序答案：A4.一個句型中的最左（）稱為該句型的句柄。A.短語B.直接短語C.素短語D.終結符號答案：B5.下面關于算符優(yōu)先分析法的說法正確的是（）A.算符優(yōu)先分析法是一種規(guī)范歸約分析法B.算符優(yōu)先分析法中只考慮終結符之間的優(yōu)先關系C.算符優(yōu)先分析法比規(guī)范歸約分析法更準確D.算符優(yōu)先分析法的效率比規(guī)范歸約分析法低答案：B6.若項目集Ik含有A→α?，則在狀態(tài)k時，只要面臨的輸入符號a∈FOLLOW(A)，就采取“A→α?”動作的一定是（）A.LALR分析法B.LR(0)分析法C.LR(1)分析法D.SLR(1)分析法答案：D7.中間代碼生成時所依據的是（）A.語法規(guī)則B.詞法規(guī)則C.語義規(guī)則D.等價變換規(guī)則答案：C8.優(yōu)化可生成（）的目標代碼。A.運行時間較短B.占用存儲空間較小C.運行時間短但占用內存空間大D.運行時間短且占用存儲空間小答案：D9.設有文法G[S]：S→S1|S0|Sa|Sc|a|b|c，下列符號串中是該文法的句子的有（）A.ab0B.a0c01C.aaaD.bc10答案：B10.喬姆斯基把文法分成四種類型，3型文法也稱為（）A.上下文無關文法B.正則文法C.上下文有關文法D.短語文法答案：B二、多項選擇題1.編譯程序的工作過程一般可以劃分為（）等幾個階段。A.詞法分析B.語法分析C.語義分析D.中間代碼生成E.代碼優(yōu)化和目標代碼生成答案：ABCDE2.下面哪些是詞法分析的任務（）A.從源程序中識別出一個個單詞符號B.識別出單詞的種別編碼C.識別出單詞的自身值D.把識別出的單詞符號輸出E.檢查源程序中的語法錯誤答案：ABCD3.語法分析常用的方法有（）A.自頂向下B.自底向上C.自左向右D.自右向左E.由中間向兩邊答案：AB4.下面關于語法樹的說法正確的有（）A.語法樹的根結點是開始符號B.語法樹的葉結點是終結符號C.語法樹的內部結點是語法單位D.每棵語法樹都對應唯一的一個最左推導E.每棵語法樹都對應唯一的一個最右推導答案：ABC5.算符優(yōu)先關系表的構造需要計算（）A.FIRSTVTB.LASTVTC.FOLLOWD.SELECTE.優(yōu)先函數答案：AB6.一個LR分析器由（）組成。A.總控程序B.分析表C.分析棧D.源程序E.目標程序答案：ABC7.下面哪些是中間代碼的形式（）A.逆波蘭式B.四元式C.三元式D.間接三元式E.樹形表示答案：ABCDE8.代碼優(yōu)化的主要目標是（）A.提高目標程序的運行速度B.減少目標程序運行所需的空間C.提高目標程序的可讀性D.優(yōu)化數據結構E.提高代碼的可維護性答案：AB9.設有文法G[E]：E→E+T|T，T→TF|F，F→(E)|i，下面哪些是該文法的句型（）A.E+TFB.(E+T)C.i+iiD.TF+iE.E+E+E答案：ABCD10.下面關于文法分類的說法正確的有（）A.0型文法也稱為短語文法B.1型文法也稱為上下文有關文法C.2型文法也稱為上下文無關文法D.3型文法也稱為正則文法E.每種類型的文法都有其對應的自動機答案：ABCDE三、判斷題1.編譯程序是對高級語言程序的解釋執(zhí)行。（）答案：錯誤2.詞法分析和語法分析本質上都是對源程序的結構進行分析。（）答案：正確3.一個句型對應的一棵語法樹包括了該句型的所有推導。（）答案：錯誤4.算符優(yōu)先分析法每次都是對句柄進行歸約。（）答案：錯誤5.LR(0)分析表構造時，若項目集中存在移進-歸約沖突，則該文法不是LR(0)文法。（）答案：正確6.中間代碼生成是編譯程序中一個可選的階段。（）答案：錯誤7.代碼優(yōu)化的目的是為了提高目標程序的運行速度和減少目標程序運行所需的空間。（）答案：正確8.語法制導翻譯是一種基于屬性文法的處理方法。（）答案：正確9.一個文法是二義性的，則該文法所描述的語言也是二義性的。（）答案：錯誤10.正則文法一定是上下文無關文法。（）答案：正確四、簡答題1.簡述編譯程序的總體結構。編譯程序一般由詞法分析器、語法分析器、語義分析與中間代碼生成器、代碼優(yōu)化器、目標代碼生成器以及表格管理和出錯處理程序組成。詞法分析器將源程序分割成一個個單詞符號；語法分析器對單詞符號串進行語法結構分析；語義分析與中間代碼生成器進行語義處理并生成中間代碼；代碼優(yōu)化器對中間代碼進行優(yōu)化；目標代碼生成器生成目標機器的指令代碼；表格管理程序負責管理各類表格；出錯處理程序對源程序中的錯誤進行處理。2.簡述自頂向下語法分析的基本思想。自頂向下語法分析是從開始符號出發(fā)，試圖用一切可能的方法，自上而下、從左到右地為輸入串建立一棵語法樹。也就是根據輸入符號串，按照文法的產生式規(guī)則，逐步推導，若最終能推導出與輸入符號串相同的符號串，則分析成功；若在推導過程中發(fā)現無法與輸入符號匹配，則分析失敗。在分析過程中，通常需要消除文法的左遞歸和提取左因子，以避免無限循環(huán)和回溯。3.簡述SLR(1)分析法與LR(0)分析法的主要區(qū)別。LR(0)分析法在構造分析表時，只要項目集Ik含有A→α?，不管面臨什么輸入符號，都執(zhí)行歸約動作。而SLR(1)分析法在項目集Ik含有A→α?時，只有當面臨的輸入符號a∈FOLLOW(A)時，才執(zhí)行歸約動作。這就使得SLR(1)分析法能夠處理一些LR(0)分析法無法處理的文法，SLR(1)分析表比LR(0)分析表有更強的分析能力，但仍存在局限性。4.簡述代碼優(yōu)化的主要策略。代碼優(yōu)化的主要策略有：刪除公共子表達式，即對表達式中重復出現的子表達式只計算一次；復寫傳播，把變量的賦值操作傳播到使用該變量的地方，簡化計算；刪除無用代碼，去除那些對程序運行結果沒有影響的代碼；合并已知量，對于編譯時就能確定值的表達式進行計算并替換；強度削弱，用執(zhí)行時間短的運算代替執(zhí)行時間長的運算；循環(huán)優(yōu)化，如循環(huán)不變代碼外提、歸納變量刪除等，提高循環(huán)執(zhí)行效率。五、討論題1.討論如何判斷一個文法是否是二義性的，并舉例說明二義性文法可能帶來的問題。判斷一個文法是否二義性，通常看是否存在一個句子，它有兩棵不同的語法樹，或者存在兩種不同的最左推導或最右推導。例如文法G[E]：E→E+E|EE|(E)|i，對于句子i+ii，有兩種不同的最左推導：一是E?E+E?i+E?i+EE?i+iE?i+ii；二是E?EE?E+EE?i+EE?i+iE?i+ii。二義性文法可能帶來的問題：編譯器在語法分析時會產生不確定性，無法確定唯一的語法結構，導致語義理解和代碼生成的困難，不同的解釋可能會產生不同的目標代碼，影響程序的正確性和一致性。2.討論算符優(yōu)先分析法與規(guī)范歸約分析法在歸約過程中的主要區(qū)別。算符優(yōu)先分析法歸約的是最左素短語，它只考慮終結符之間的優(yōu)先關系，不考慮非終結符，歸約過程中不一定要按句柄進行歸約。例如對于輸入串“a+bc”，算符優(yōu)先分析法根據終結符的優(yōu)先關系先歸約“bc”。而規(guī)范歸約分析法歸約的是句柄，它是嚴格按照最左推導的逆過程進行歸約，考慮整個文法的產生式結構和符號之間的關系。例如對于同樣輸入串，規(guī)范歸約可能先從“a”“b”“c”等最小的語法單位逐步按句柄歸約到更大的語法單位，最終歸約到開始符號。規(guī)范歸約更注重語法結構的完整性和正確性，而算符優(yōu)先分析法更側重于終結符的運算優(yōu)先級。3.討論中間代碼生成在編譯過程中的作用和優(yōu)點。中間代碼生成在編譯過程中起到了承上啟下的關鍵作用。作用：它將源程序的語義分析結果以一種中間表示形式呈現，使得后續(xù)的代碼優(yōu)化和目標代碼生成可以基于這種統(tǒng)一的、與機器無關的形式進行處理。優(yōu)點：首先，提高了編譯程序的可移植性，因為中間代碼與具體目標機器無關，只需要針對不同目標機器開發(fā)相應的目標代碼生成器即可。其次，方便代碼優(yōu)化，中間代碼形式相對簡單規(guī)范，有利于各種優(yōu)化算法的實現，可提高目標代碼的質量。再者，分離了語義分析和目標代碼生成，使得編譯過程結構更加清晰，易于維護和擴展。4.討論如何對一個給定的編譯程序進行測試和調試，以確保其正確性和可靠性。對編譯程序進行測試和調試可從以下方面著手。測試：首先準備大量不同類型的源程序，包括正確的和包含各種錯誤的程序，涵蓋不同語法結構、語義場景等。使用這些源程序運行編譯程序，檢查輸出結果。對