編譯原理與技術(shù)模擬試題一

1、編譯原理與技術(shù)模擬試題一一、填空題(20分)編譯程序的工作過程可劃分為詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、等階段，一般在階段對表達(dá)式中運(yùn)算對象的類型進(jìn)行檢查。和預(yù)測分析法是自上而下的語法分析方法。1.3常用的存儲(chǔ)分配策略有存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配，其中，動(dòng)態(tài)存儲(chǔ)分配策略包括分配和分配。1.4移進(jìn)、歸約是分析中的典型操作。1.5對于數(shù)組M1.6,1.8，如果每個(gè)元素占k個(gè)存儲(chǔ)單元，且起始地址為a,則以行為主序存放時(shí)元素M4,4的地址是，以列為主序存放時(shí)元素M4,4的地址是。二、單選題(20分)2.1詞法分析器不能。A.識(shí)別出數(shù)值常量B.過濾源程序中的注釋C.掃描源程序并識(shí)別記號(hào)D.發(fā)現(xiàn)括號(hào)

2、不匹配2.2給定文法LbA|ca,是該文法的句子。A.bbaB.cabC.bcaD.cba一個(gè)句型中的最左稱為該句型的句柄。A.短語B.直接短語C.非終結(jié)符號(hào)D.終結(jié)符號(hào)已知文法GS:StA1AA1|S0|0。與G等價(jià)的正規(guī)式是。A.0(0|1)*B.1*|0*1C.0(1|10)*1D.1(10|01)*0源程序是句子的集合，可以較好地反映句子的結(jié)構(gòu)。A.線性表B.樹C.完全圖D.堆棧2.6與逆波蘭式ab+c*d+對應(yīng)的中綴表達(dá)式是。A.a+b+c*dB.(a+b)*c+dC.(a+b)*(c+d)D.a+b*c+d2.7識(shí)別上下文無關(guān)語言的自動(dòng)機(jī)是。A.下推自動(dòng)機(jī)B.NFAC.DFAD.圖

3、靈機(jī)2.8是與規(guī)范歸約(最左歸約)互逆的一個(gè)過程。A.最左推導(dǎo)B.最右推導(dǎo)C.詞法分析D.語義分析2.9文法G產(chǎn)生的的全體是該文法描述的語言，A.句子B.短語C.終結(jié)符D.非終結(jié)符2.10在表達(dá)式x:=y+1中，作為左值出現(xiàn)(其中，“:=”表示賦值)。A.xB.yC.1D.y+1三、簡答題(30分)3.1 (5分)請分別寫出傳值調(diào)用、引用調(diào)用方式下，下面代碼的輸出結(jié)果。programmain(input,output)proceduref(a,b)begina:=b-a;b:=a*b+1;end;beginx:=5;y:=10;f(y,x)；print(x,y);end.3.2 (10分)請計(jì)

4、算下面文法G(E)中各非終結(jié)符的FIRST和FOLLOW!合。請說明該文法為什么不是LL(1)文法。G(E):E*T|TT-F|F(E)|id（10分）下圖所示的分析樹用到了某個(gè)上下文無關(guān)文法的所有產(chǎn)生式。（a）給出該文法的所有非終結(jié)符號(hào)集合N和終結(jié)符號(hào)集合T。（b）給出該文法的產(chǎn)生式集合。SaAcBaBbSC£3.4（5分）某程序執(zhí)行到某一時(shí)刻時(shí)控制棧中的內(nèi)容如下所示（其中M是主程序，P、QR、S均是過程），給出所有在生存期的活動(dòng)的調(diào)用關(guān)系（提示：若A調(diào)用B,則記為AtB）。top控制鏈二S的活動(dòng)記錄f£s的活動(dòng)記錄c的活動(dòng)記錄R的活動(dòng)記錄P的活動(dòng)記錄M勺活動(dòng)記錄四、綜合

5、題（40分）*4.1（15分）設(shè)有正規(guī)式r=1（0|1）1，試給出：（a）（5分）識(shí)別該正規(guī)集的NFA（b）（10分）識(shí)別該正規(guī)集的DFA（要有計(jì)算過程）；英文字母組成，如a,b等）：E-E1*TE.place=newtemp;emit(*,E1.place,T.place,E.place;|TE.place=T.place;T-T1-FT.place=newtemp;emit(-,T1.place,F.place,T.place;|FT.place=F.place;F-(E)F.place=E.place;|idF.place=;（a）（4分）畫出句子a-b*c的分析樹；（b）

6、（3分）寫出當(dāng)a=1、b=2、c=3時(shí)的計(jì)算結(jié)果；（*表示算術(shù)乘、-表示算術(shù)減）（c）（8分）將文法G簡化為：E-E*T|T,TT-F|F,FTd,給出其識(shí)別活前綴的DFA該DFA的項(xiàng)目集中有沖突嗎？若有，是哪種類型的沖突。10分）閱讀以下程序代碼if（y>0andx>0）while（x>y）dox=x-yelsey=1a）（4分）請畫出其代碼結(jié)構(gòu)圖（流程圖）；b）（6分）給出其三地址碼序列。參考答案一、填空題語義分析、目標(biāo)代碼生成、語義分析遞歸下降法靜態(tài)、棧、堆自下而上或LRa+27*k，a+21k、單選題2.1DCBCB2.6B2.7A2.8B2.9A2.10A三、簡答題

7、3.1傳值調(diào)用方式:510引用調(diào)用方式:-24-5FIRST(F)=FIRST(T)=FIRST(E)=(,idFOLLOW(F)=-,*,#,)tbScA|b|&FOLLOW(E)=#,*,)FOLLOW(T)=-,*,#,)N=S,A,BT=a,b,c,dStaAcB|BdMtPtRtQtsts四、綜合題4.1NFA如下圖所示10初態(tài)記為s1記為s2，終態(tài)(b)s0=A&閉包(s0)=s0e閉包(smove(s0,1)=B&閉包(smove(s1,0)=B=s1&閉包(smove(s1,1)=B,C&閉包(smove(s2,0)=B=s1&閉包(smove(s2,1)=B,C=s2DFA如下圖所示4.2(a)(b)-3(c)拓廣文法，增加產(chǎn)生式:S-.EE.E*TE.TT.T-FT.FF.idES-E,識(shí)別活前綴的DFA如下圖所示EE*.TT.T-FT.FF.idE-E*T.TT.-FidT"TT-F.TF.Fid.ET.TT.-FS-E.EE.*TTT-.FF.idF111存在移進(jìn)-歸約沖突(10分)閱讀以下程序代碼if(y>0andx>0)while(x>y)dox=x-yelsey=1(a) (4分)請畫出其代碼結(jié)構(gòu)圖(流程圖)；(b) (6分)給出其三