編譯原理考試題及答案

一、單項(xiàng)選擇題（每題2分，共20分）1.編譯程序前三個(gè)階段完成的工作是（）A.詞法分析、語(yǔ)法分析和代碼優(yōu)化B.代碼生成、代碼優(yōu)化和詞法分析C.詞法分析、語(yǔ)法分析和語(yǔ)義分析D.詞法分析、語(yǔ)義分析和代碼生成2.詞法分析器的輸出結(jié)果是（）A.單詞的種別編碼B.單詞在源程序中的位置C.單詞的種別編碼和自身值D.單詞自身值3.正規(guī)式M1和M2等價(jià)是指（）A.M1和M2的狀態(tài)數(shù)相等B.M1和M2的有向邊條數(shù)相等C.M1和M2所識(shí)別的語(yǔ)言集相等D.M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等4.語(yǔ)法分析器可以發(fā)現(xiàn)源程序中的（）A.語(yǔ)義錯(cuò)誤B.語(yǔ)法和語(yǔ)義錯(cuò)誤C.錯(cuò)誤并校正D.語(yǔ)法錯(cuò)誤5.一個(gè)上下文無關(guān)文法G包括四個(gè)組成部分，它們是一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組（）A.句子B.產(chǎn)生式C.單詞D.句型6.若項(xiàng)目集Ik含有A→α?，則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào)a∈FOLLOW(A)時(shí)，才采取“A→α?”動(dòng)作的一定是（）A.LALR文法B.LR(0)文法C.LR(1)文法D.SLR(1)文法7.下列（）優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A.強(qiáng)度削弱B.刪除歸納變量C.合并已知量D.代碼外提8.基本塊內(nèi)的優(yōu)化為（）A.代碼外提，刪除歸納變量B.刪除多余運(yùn)算，刪除無用賦值C.強(qiáng)度削弱，代碼外提D.循環(huán)展開，循環(huán)合并9.下述正規(guī)表達(dá)式中，能描述字母表{0,1}上所有長(zhǎng)度不為3的符號(hào)串的是（）A.(0|1)000(0|1)B.(0|1)(ε|0|00|000|1|10|100|1000)C.(0|1)D.(0|1)(ε|0|00|1|10|100)10.若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子（）A.是無窮多個(gè)B.是有窮多個(gè)C.是可枚舉的D.個(gè)數(shù)是常量答案：1.C2.C3.C4.D5.B6.D7.C8.B9.D10.A二、多項(xiàng)選擇題（每題2分，共20分）1.編譯程序階段包括（）A.詞法分析B.語(yǔ)法分析C.語(yǔ)義分析D.代碼生成2.下面哪些是正規(guī)式的運(yùn)算（）A.并B.連接C.閉包D.交3.語(yǔ)法分析的方法有（）A.自頂向下B.自底向上C.自左向右D.自右向左4.下面哪些屬于LR分析器（）A.LR(0)分析器B.SLR(1)分析器C.LR(1)分析器D.LALR(1)分析器5.中間代碼的形式有（）A.逆波蘭式B.四元式C.三元式D.樹6.對(duì)基本塊進(jìn)行優(yōu)化的方法有（）A.刪除多余運(yùn)算B.合并已知量C.強(qiáng)度削弱D.刪除無用賦值7.符號(hào)表的作用有（）A.輔助語(yǔ)義的正確性檢查B.輔助代碼生成C.存儲(chǔ)源程序的字符D.記錄標(biāo)識(shí)符的信息8.屬于詞法分析的操作有（）A.識(shí)別單詞B.過濾注釋C.識(shí)別句子D.發(fā)現(xiàn)詞法錯(cuò)誤9.下列關(guān)于語(yǔ)法樹的說法正確的是（）A.語(yǔ)法樹的根結(jié)由開始符號(hào)所標(biāo)記B.一棵語(yǔ)法樹表示了一個(gè)句型的推導(dǎo)過程C.一個(gè)句型一定只對(duì)應(yīng)一棵語(yǔ)法樹D.不同推導(dǎo)過程對(duì)應(yīng)的語(yǔ)法樹不同10.代碼優(yōu)化的目的是（）A.提高目標(biāo)程序的運(yùn)行速度B.減少目標(biāo)程序運(yùn)行所需的空間C.提高編譯程序的編譯速度D.減少編譯程序的存儲(chǔ)空間答案：1.ABCD2.ABC3.AB4.ABCD5.ABCD6.ABD7.ABD8.ABD9.AB10.AB三、判斷題（每題2分，共20分）1.編譯程序是對(duì)高級(jí)語(yǔ)言程序的解釋執(zhí)行。（）2.一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。（）3.正規(guī)文法產(chǎn)生的語(yǔ)言都可以用正規(guī)表達(dá)式來表示。（）4.遞歸下降分析法是一種自底向上的語(yǔ)法分析方法。（）5.一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。（）6.對(duì)任何一個(gè)編譯程序來說，生成中間代碼是不可缺少的一部分。（）7.代碼優(yōu)化的目的是為了縮短源程序的長(zhǎng)度。（）8.符號(hào)表中的信息欄中登記了每個(gè)名字的屬性和特征等有關(guān)信息。（）9.詞法分析作為單獨(dú)的一遍來處理較好。（）10.對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。（）答案：1.×2.×3.√4.×5.√6.×7.×8.√9.×10.×四、簡(jiǎn)答題（每題5分，共20分）1.簡(jiǎn)述編譯程序的總體結(jié)構(gòu)。答案：編譯程序一般由詞法分析器、語(yǔ)法分析器、語(yǔ)義分析與中間代碼生成器、代碼優(yōu)化器、目標(biāo)代碼生成器組成，還有表格管理程序和錯(cuò)誤處理程序輔助。各部分協(xié)同完成源程序到目標(biāo)程序的轉(zhuǎn)換。2.簡(jiǎn)述自頂向下語(yǔ)法分析的基本思想。答案：從開始符號(hào)出發(fā)，通過推導(dǎo)試圖構(gòu)造出與輸入符號(hào)串匹配的句子。根據(jù)產(chǎn)生式規(guī)則，逐步向下擴(kuò)展語(yǔ)法樹，若最終能構(gòu)造出一棵與輸入串對(duì)應(yīng)的語(yǔ)法樹，則分析成功，否則失敗。3.什么是符號(hào)表？其作用是什么？答案：符號(hào)表是編譯過程中用于記錄源程序中標(biāo)識(shí)符信息的數(shù)據(jù)結(jié)構(gòu)。作用是輔助語(yǔ)義檢查，保證標(biāo)識(shí)符使用的合法性；在代碼生成階段為地址分配等提供依據(jù)，記錄標(biāo)識(shí)符屬性等信息。4.簡(jiǎn)述中間代碼的特點(diǎn)。答案：中間代碼介于源語(yǔ)言和目標(biāo)語(yǔ)言之間，與具體機(jī)器無關(guān)，便于對(duì)其進(jìn)行優(yōu)化。形式多樣，如四元式、三元式等。它結(jié)構(gòu)簡(jiǎn)單、含義明確，可有效提高編譯程序的可移植性與目標(biāo)代碼生成效率。五、討論題（每題5分，共20分）1.討論詞法分析和語(yǔ)法分析的聯(lián)系與區(qū)別。答案：聯(lián)系：詞法分析為語(yǔ)法分析提供輸入單元——單詞。語(yǔ)法分析基于詞法分析的結(jié)果進(jìn)行句子結(jié)構(gòu)分析。區(qū)別：詞法分析關(guān)注單詞的識(shí)別，處理源程序的字符流；語(yǔ)法分析著眼于句子結(jié)構(gòu)，依據(jù)語(yǔ)法規(guī)則處理單詞序列，分析層次和處理對(duì)象不同。2.結(jié)合實(shí)際，談?wù)劥a優(yōu)化在編譯過程中的重要性。答案：代碼優(yōu)化可提升目標(biāo)程序性能。在實(shí)際應(yīng)用中，能減少程序運(yùn)行時(shí)間和存儲(chǔ)空間，提高系統(tǒng)效率。比如在大型軟件系統(tǒng)中，優(yōu)化后的代碼可降低資源消耗，提升響應(yīng)速度，尤其對(duì)資源受限的設(shè)備，代碼優(yōu)化至關(guān)重要。3.討論LR分析器的不同類型（LR(0)、SLR(1)、LR(1)、LALR(1)）的優(yōu)缺點(diǎn)。答案：LR(0)簡(jiǎn)單但能力弱，會(huì)有沖突；SLR(1)較簡(jiǎn)單，能力稍強(qiáng)但仍有局限；LR(1)分析能力強(qiáng)但狀態(tài)多；LALR(1)狀態(tài)數(shù)適中，能力不錯(cuò)。優(yōu)點(diǎn)是能高效分析多種文法，缺