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

2、并進(jìn)行初步翻譯（產(chǎn)生中間代碼）。第四階段，優(yōu)化的任務(wù)是：對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)出更為高效（節(jié)省時(shí)間和空間）的目標(biāo)代碼。第五階段，目標(biāo)代碼生成的任務(wù)是：把中間代碼（或經(jīng)優(yōu)化處理之后）變換成特定機(jī)器上的低級(jí)語言代碼。4、 請(qǐng)回答句子、句型和語言的定義。（6分）答：假定G是一個(gè)文法，S是它的開始符號(hào)。如果S=>，則稱是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語言，將它記為L(G)。5、給出下面狀態(tài)轉(zhuǎn)換圖的(S,å,d,s0,F)的具體組成（6分）答：狀態(tài)集S：1，2，3，4輸入字符集：0，1轉(zhuǎn)換關(guān)系集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初態(tài)集S0：1終態(tài)集F：46、已知文法GZ：ZaAAbA|ab寫出文法對(duì)應(yīng)的語言（4分）答：ab(b)*ab7、請(qǐng)回答自上而下語法分析和自下而上語法分析有什么區(qū)別。（4分）答：自上而下的分析，是從文法的開始符號(hào)出發(fā)，試圖推導(dǎo)出句子。它要解決的關(guān)鍵問題是在對(duì)某一個(gè)非終結(jié)符進(jìn)行推導(dǎo)時(shí)，選擇以它為左部的多個(gè)產(chǎn)生式中的哪一個(gè)。自下面上的分析，是從輸入符號(hào)串出發(fā)，試圖歸約到文法的開始符號(hào)。分析過程中，每次選擇與某個(gè)產(chǎn)生式右部符號(hào)串相同的一個(gè)子串進(jìn)行歸約。它要解決的關(guān)鍵問題

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

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

6、Ba)=bFIRST(S)=b,cFIRST(A)=cFIRST(A)=a, FIRST(B)=d, 每個(gè)非終結(jié)符 的各個(gè)產(chǎn)生式候選首符集兩兩不相交求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è)條件，所以文法G是LL(1)文法。給出預(yù)測分析表（4分）答：如果FIRST包含的話，要看FOLLOW,若FOLLOW能推出該終結(jié)符，則填，否則不填abcd#SbBaABAcAAabABdB四、假設(shè)字母表是a,b，若要求所有以字母a開始，b結(jié)尾的符號(hào)串，寫出相應(yīng)正規(guī)式,并構(gòu)造與之相對(duì)應(yīng)的最小DFA.(10分)答：1.