1、一、 簡答題（31分）1、 什么是編譯程序？（3分）答：編譯程序是指能把一種高級語言程序轉換成一種低級語言程序的程序，而兩者在邏輯上是等價的。2、 編譯前端由哪些部分組成？（3分）答：詞法分析、語法分析、語義分析與中間代碼產生、優化3、 編譯過程各階段分別完成什么任務？（各用一句話簡短回答）（5分）答：第一階段，詞法分析的任務是：輸入源程序，對構成源程序的字符串進行掃描和分解，識別出一個個的單詞。第二階段，語法分析的任務是：在詞法分析的基礎上，根據語言的語法規則，把單詞符號串分解成各類語法單位（語法范疇）。第三階段，語義分析與中間代碼產生的任務是：對語法分析所識別出的各類語法范疇，分析其含義，

2、并進行初步翻譯（產生中間代碼）。第四階段，優化的任務是：對前段產生的中間代碼進行加工變換，以期在最后階段能產出更為高效（節省時間和空間）的目標代碼。第五階段，目標代碼生成的任務是：把中間代碼（或經優化處理之后）變換成特定機器上的低級語言代碼。4、 請回答句子、句型和語言的定義。（6分）答：假定G是一個文法，S是它的開始符號。如果S=>，則稱是一個句型。僅含終結符號的句型是一個句子。文法G所產生的句子的全體是一個語言，將它記為L(G)。5、給出下面狀態轉換圖的(S,å,d,s0,F)的具體組成（6分）答：狀態集S：1，2，3，4輸入字符集：0，1轉換關系集d：d(1,0)=2,

3、d(1,1)=3, d(2,0)=2, d(2,1)=4, d(3,0)=2, d(3,1)=3,d(4,0)=2, d(4,1)=3初態集S0：1終態集F：46、已知文法GZ：ZaAAbA|ab寫出文法對應的語言（4分）答：ab(b)*ab7、請回答自上而下語法分析和自下而上語法分析有什么區別。（4分）答：自上而下的分析，是從文法的開始符號出發，試圖推導出句子。它要解決的關鍵問題是在對某一個非終結符進行推導時，選擇以它為左部的多個產生式中的哪一個。自下面上的分析，是從輸入符號串出發，試圖歸約到文法的開始符號。分析過程中，每次選擇與某個產生式右部符號串相同的一個子串進行歸約。它要解決的關鍵問題

4、是如何確定一個可歸約的子串。二、已知文法G：Ta|e|(F)P FT+F|TP*P|T試給出式子(a+e)*a的最左推導及語法樹（4分）答：最左推導：T=>(F)P =>(T+F)P =>(a+F)P =>(a+T)P =>(a+e)P =>(a+e)*P =>(a+e)*T =>(a+e)*a語法樹：試給出式子(a)*e的最右推導及語法樹（4分）答：最右推導：T=>(F)P =>(F)*P =>(F)*T =>(F)*e =>(T)*e =>(a)*e語法樹： 指出句型(a+T)*P的所有短語、直接短語和句柄

5、。（5分）答：先畫出語法樹短語：1,(a+T)*P相對于T的短語2,(a+T)相對于F的短語3,*P相對于P的短語4,a相對于T的短語5,T相對于F的短語直接短語：3，4，5句柄：4三、文法SAB|bBaAAab|cBdB|對文法G消除左遞歸（2分）答：公式：P >P|P >PP>P'|過程：=ab=cA > c AA > abA|對文法G消除左遞歸后得：SAB|bBaA > c AA > abA|BdB|對改寫后的文法判斷是否LL(1)文法，求相應FIRST和FOLLOW集合（7分）答：求FIRST:對S:FIRST(AB)=cFIRST(b

6、Ba)=bFIRST(S)=b,cFIRST(A)=cFIRST(A)=a, FIRST(B)=d, 每個非終結符 的各個產生式候選首符集兩兩不相交求FOLLOW:FOLLOW(S)=(#)FOLLOW(A)=(d,#)FOLLOW(A)=(d,#)FOLLOW(B)=(a,#)FIRST首符集合含的有FIRST(A)和FIRST(B)FIRST(A) FOLLOW(A) =  FIRST(B) FOLLOW(B)=  由以上步驟得文法G滿足LL(1)文法的3個條件，所以文法G是LL(1)文法。給出預測分析表（4分）答：如果FIRST包含的話，要看FOLLOW,若FOLLOW能推出該終結符，則填，否則不填abcd#SbBaABAcAAabABdB四、假設字母表是a,b，若要求所有以字母a開始，b結尾的符號串，寫出相應正規式,并構造與之相對應的最小DFA.(10分)答：1.