編譯原理期末試題

編譯原理》期末試題(一)一、 是非題(請在括號內(nèi)，正確的劃V,錯誤的劃X)(每個2分，共20分)?編譯程序是對高級語言程序的解釋執(zhí)行。(X)TOC\o"1-5"\h\z?一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。 (X)3．一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。 (V)4．語法分析時必須先消除文法中的左遞歸 。(X)LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點。 (話6．逆波蘭表示法表示表達式時無須使用括號。 (V)靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 (X)進行代碼優(yōu)化時應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。 (X)兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。(X)一個語義子程序描述了一個文法所對應(yīng)的翻譯工作。 (X)二、 選擇題(請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論 )(每個4分，共40分)1.詞法分析器的輸出結(jié)果是 。A.()單詞的種別編碼 B.()單詞在符號表中的位置C.()單詞的種別編碼和自身值D.()單詞自身值正規(guī)式M1和M2等價是指 。A.()M1和M2的狀態(tài)數(shù)相等 B.()M1和M2的有向邊條數(shù)相等C．()M1和M2所識別的語言集相等 D．()M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等文法G:SfxSx|y所識別的語言是 。()xyxB.()(xyx)*C.()xnyxn(n >0).()x*yx*4.如果文法G是無二義的，則它的任何句子aA．()最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B．()最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同第1頁共6頁

C．()最左推導(dǎo)和最右推導(dǎo)必定相同D．()可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同5．構(gòu)造編譯程序應(yīng)掌握 。A．()源程序 B．()目標(biāo)語言C．()編譯方法 D．()以上三項都是6．四元式之間的聯(lián)系是通過 實現(xiàn)的。A．()指示器 B．()臨時變量C．()符號表 D．()程序變量7?表達式 (門BN0VD)的逆波蘭表示為 。A.()A.()nB.()AnCDVAC.C.()ABVnCDVAD．()AnBCVD VA8.8.優(yōu)化可生成 的目標(biāo)代碼A．A．()運行時間較短B．()占用存儲空間較小C．C．()運行時間短但占用內(nèi)存空間大D．()運行時間短且占用存儲空間小9．下列 優(yōu)化方法不是針對循環(huán)優(yōu)化進行的A.()強度削弱 9．下列 優(yōu)化方法不是針對循環(huán)優(yōu)化進行的A.()強度削弱 B．()刪除歸納變量C．()刪除多余運算 D．()代碼外提10．編譯程序使用 區(qū)別標(biāo)識符的作用域。A.()說明標(biāo)識符的過程或函數(shù)名B．()說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次C．()說明標(biāo)識符的過程或函數(shù)的動態(tài)層次D.()標(biāo)識符的行號三、填空題(每空1分，共10分)1．計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：第2頁共6頁解釋__和__編譯并識別出一2．掃描器是__詞法分析器___，它接受輸入的__源程序___，對源程序進行___詞法分析個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。并識別出一3．自上而下分析法采用___移進__、歸約、錯誤處理、___接受__等四種操作。.一個LR分析器包括兩部分：一個總控程序和張分析表__。5．后綴式abc-/所代表的表達式是___a/(b-c)__。局部優(yōu)化是在__基本塊___范圍內(nèi)進行的一種優(yōu)化。四、簡答題(20分)簡要說明語義分析的基本功能。答：語義分析的基本功能包括:確定類型、類型檢查、語義處理和某些靜態(tài)語義檢查考慮文法G[S]:—(T)|a+S|aT—T,S|S消除文法的左遞歸及提取公共左因子。解：消除文法G[S]的左遞歸：S—(T)|a+S|aT—ST'T'—,ST'|提取公共左因子：S—(T)|aS'S'—+S&|T—ST'寫出相應(yīng)的逆波蘭表示第3頁共6頁T'—,ST'寫出相應(yīng)的逆波蘭表示第3頁共6頁試為表達式w+(a+b)*(c+d/(e-10)+8)第第#頁共6頁4．運行時的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：DISPLAY表是嵌套層次顯示表。每當(dāng)進入一個過程后，在建立它的活動記錄區(qū)的同時建立一張嵌套層次顯示表diaplay.假定現(xiàn)在進入的過程層次為i，則它的diaplay表含有i+1個單元，自頂向下每個單元依次存放著現(xiàn)行層、直接外層、…、直至最外層(主程序，0層)等每層過程的最新活動記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變量。5．對下列四元式序列生成目標(biāo)代碼：A:=B*CD:=E+FG:=A+DH:=G*2其中，H是基本塊出口的活躍變量，R0和R1是可用寄存器答：LDR0，BMULR0，CLDR1，EADDR1，F(xiàn)ADDR0，R1MULR0，2STR0，H《編譯原理》期末大題1.設(shè)有如下文法G(S),試消除其左遞歸G（S）：S—>Ac|cA—>Bb|bB—>Sa|a解：S—ab