北方工業(yè)大學(xué)16編譯原理期末復(fù)習(xí)題答案

..序號(hào)北方工業(yè)大學(xué)序號(hào)A卷2016年春季學(xué)期訂線訂線裝考試方式：閉卷考試時(shí)間：120分鐘班級(jí)學(xué)號(hào)題號(hào)一二三四五六七八九十總分得分閱卷人一判斷題〔每個(gè)小題1分，共10分〕1.程序語言主要由語法和語義兩方面定義?！病?.自上而下分析方法會(huì)遇到的主要問題有左遞歸和回溯?！病?.文法G：Ei|EAE，A+|*，其中的終結(jié)符號(hào)集包括{i，+}。〔〕4.編譯程序是將高級(jí)語言程序翻譯成機(jī)器語言程序?！病?.只含有綜合屬性的屬性文法稱為S-屬性文法?！病?.LL(1)文法中第一個(gè)L的含義是從左到右掃描輸入串?！病?.在編譯中進(jìn)展語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤?！病?.一個(gè)語義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。〔〕9.一個(gè)句型的直接短語是唯一的?！病?0.確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。〔〕解：1.√2.√3.×4.×5.√6.√7.×8.×9.×10.√二、選擇題〔每個(gè)小題1分，共20分〕1.文法分為四種類型，即0型、1型、2型、3型。其中3型文法是____。A.短語文法B.正規(guī)文法C.上下文有關(guān)文法D.上下文無關(guān)文法2.不可能是目標(biāo)代碼。

A.匯編指令代碼

B.可重定位指令代碼

C.絕對(duì)指令代碼

D.中間代碼3.將編譯程序分成假設(shè)干個(gè)"遍〞是為了。

A.提高程序的執(zhí)行效率B.利用有限的機(jī)器存并提高機(jī)器的執(zhí)行效率C.使程序的構(gòu)造更加清晰D.利用有限機(jī)器存但降低了機(jī)器的執(zhí)行效率4.后綴式ab+cd+/可用表達(dá)式來表示。A.a+b/c+dB.(a+b)/(c+d)C.a+b/(c+d)D.a+b+c/d5.文法G：S→xSx|y所識(shí)別的語言是。 A.xyx B.(xyx)* C.xnyxn(n≥0) D.x*yx*6.文法G[E]：E→E+T|TT→T*P|PP→(E)|i那么句型P+T+i的句柄和最左素短語為。A.P+T和i B.P和P+T C.i和P+T+i D.P和T7.設(shè)有文法G[E]：E→E*T|TT→T+i|i句子1+2*8+6按該文法G歸約，其值為。A.42B.23C.30D.178.規(guī)歸約指。A.最右推導(dǎo)的逆過程 B.最左推導(dǎo)的逆過程 C.規(guī)推導(dǎo)D.最左歸約的逆過程 9.詞法分析所依據(jù)的是。A.語義規(guī)那么 B.構(gòu)詞規(guī)那么 C.語法規(guī)那么 D.等價(jià)變換規(guī)那么10.狀態(tài)轉(zhuǎn)換圖〔見下列圖〕承受的集合為。00

10YA.以0開頭的二進(jìn)制數(shù)組成的集合B.以0結(jié)尾的二進(jìn)制數(shù)組成的集合C.含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合D.含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合11.詞法分析器作為獨(dú)立的階段使整個(gè)編譯程序構(gòu)造更加簡(jiǎn)潔、明確，因此，。A.詞法分析器作為子程序較好B.詞法分析器并不作為一個(gè)獨(dú)立的階段C.詞法分析器分解為多個(gè)過程，由語法分析器選擇使用D.詞法分析器應(yīng)作為獨(dú)立的一遍12.假設(shè)a為終結(jié)符，那么A→α·aβ為工程。A.移進(jìn) B.歸約 C.承受 D.待約13.中間代碼生成所依據(jù)的是。 A.語法規(guī)那么 B.詞法規(guī)那么 C.語義規(guī)那么 D.等價(jià)變換規(guī)那么14.終結(jié)符具有屬性。A.傳遞 B.繼承 C.抽象 D.綜合15.下推自動(dòng)機(jī)識(shí)別的語言是。 A.0型語言B.1型語言C.2型語言D.3型語言16.常用的中間代碼形式不含。A.三元式B.四元式C.逆波蘭表達(dá)式D.語法樹17.算符文法是指的文法。A.沒有形如U→...VW...的產(chǎn)生式〔U、V、WVN〕B.VT中任意兩個(gè)符號(hào)之間至多存在一種算符優(yōu)先關(guān)系C.沒有一樣右部的產(chǎn)生式D.沒有形如U→ε的產(chǎn)生式18.下述語句類中，____________在編譯階段通常不產(chǎn)生可執(zhí)行代碼。A.變量說明語句B.流程控制語句C.輸入輸出語句D.賦值語句19.文法所描述的語言是的集合。A.文法的字母表中符號(hào)組成的符號(hào)串B.文法的字母表中終結(jié)符號(hào)組成的符號(hào)串C.由文法開場(chǎng)符號(hào)推導(dǎo)的符號(hào)串D.由文法開場(chǎng)符號(hào)推導(dǎo)的終結(jié)符號(hào)串20.符號(hào)串a(chǎn)b1b2是文法G[A]：A→aB,B→bB|b的句子，該句子的句柄是________。A.b1B.b2C.aD.b1b2解：1.B2.

D3.C4.B5.C 6.B7.A8.A9.B10.D11.A12.A13.C14.

D15.C16.

D17.A18.A19.D20.B三、文法G的產(chǎn)生式為：ET|E+T|E-TTF|T*F(2-1)F(E)|i試求：〔1〕消除該文法的左遞歸；〔5分〕〔2〕利用(1)得到的文法G’(2-1)，求(i+i*i)的最左推導(dǎo)和語法分析樹?！?分〕解：〔1〕ETE’E’+TE’|-TE’|εTFT’|T’*FT’|ε(2-1)’F(E)|i〔2〕ETE’FT’E’(E)T’E’(E)εε(TE’)(FT’E’)(iT’E')(iεE’)(i+TE’)(i+FT’E’)(i+iT’E’)(i+i*FT’E’)(i+i*iT’E’)(i+i*iεε)(i+i*i)EE’‘E(根)Tiε()Fi+T’εTE’‘i*ε四、文法G的產(chǎn)生式：ETE’E’+TE’|-TE’|εTFT’|T’*FT’|ε(2-1)’F(E)|i試求：〔1〕每個(gè)非終結(jié)符的FIRST集合；〔5分〕〔2〕每個(gè)非終結(jié)符的FOLLOW集合?！?分〕答：FIRST(E)={(,i}FOLLOW(E)={〕,#}FIRST(E’)={-,+,ε}FOLLOW(E’)={),#}FIRST(T)={(,i} FOLLOW(T)={-,+,),#}FIRST(T’)={*,ε} FOLLOW(T’)={-,+,),#}FIRST(F)={(,i} FOLLOW(F)={*,-,+,),#}五、文法G3：Sa|^|(T);TT,S|S其中：S、T是非終結(jié)符，a、^、,、〔和〕是終結(jié)符，S為開場(chǎng)符合，試求：(1)計(jì)算非終結(jié)符的FISTVT和LASTVT;(2)給出終結(jié)符的算符優(yōu)先關(guān)系表；(3)給出(a,(a,a))的算符優(yōu)先分析過程，指出每次規(guī)約的素短語?！补?0分，每題10分〕解：(1)FIRSTVT和LASTVT如下： FIRSTVT(S)={a，∧，(} FIRSTVT(T)={，，a，∧，(} LASTVT(S)={a，∧，)} LASTVT(T)={，，a，∧，)}(2)構(gòu)造優(yōu)先關(guān)系表如下：a∧()，#a>>>^>>>(<<<=<)>>>，<<<>>#<<<=(3)輸入串(a,(a,a))的算符優(yōu)先分析過程如下：棧輸入字符串動(dòng)作#(a，(a，a))#預(yù)備#(a，(a，a))#進(jìn)#(a,(a，a))#進(jìn)#(s,(a，a))#歸#(t,(a，a))#歸#(t，(a，a))#進(jìn)#(t，(a，a))#進(jìn)#(t，(a,a))#進(jìn)#(t，(s,a))#歸#(t，(t,a))#歸#(t，(t,a))#進(jìn)#(t，(t，a))#進(jìn)#(t，(t，s))#歸#(t，(t))#歸#(t，(t))#進(jìn)#(t，s)#歸#(t)#歸#(t)#進(jìn)#s#歸六、文法G的產(chǎn)生式為：ET|E+T|E-TTF|T*F(2-1)F(E)|i試給出表達(dá)式i1*i2+i3的規(guī)式規(guī)約過程。用下面的格式描述該過程?！?0分〕步驟符號(hào)棧輸入串所用產(chǎn)生式答：輸入串i1*i2+i3的分析步驟：步驟符號(hào)棧輸入串所用產(chǎn)生式0#i1*i2+i3# 預(yù)備1#i1*i2+i3# 進(jìn)2#F*i2+i3#歸，用F→i3#T*i2+i3# 歸，用T→F4#T*i2+i3#進(jìn)5#T*i2+i3# 進(jìn)6 #T*F+i3# 歸，用F→i7 #T +i3# 歸，用F→E*F8 #E+i3# 歸，用F→T9 #E+ i3# 進(jìn)10 #E+i3# 進(jìn)11#E+F # 歸，用E→i12#E+T #歸，用T→F13 #E# 歸，用E→E+T14 #E# 承受七、屬性文法如表5-1所示，試求表達(dá)式a+4+c的抽象語法樹，并描述建立抽象語法樹過程?！?0分〕表6-1屬性文法產(chǎn)生式 語義規(guī)那么E→E1+T E.nptr:=mknode(‘+’,E1.nptr,T.nptr)E→E1-T E.nptr:=mknode(‘-’,E1.nptr,T.nptr)E→T E.nptr:=T.nptrT→(E) T.nptr:=E.nptrT→id T.nptr:=mklear(id,id.entry)T→num T.nptr:=mklear(num,num.val)答：〔1〕p1:=mkleaf(id,entrya);〔2〕p2:=mkleaf(num,4);〔3〕p3:=mknode(‘+’,p1,p2);〔4〕p4:=mkleaf(id,entryc);〔5〕p5:=mknode(‘+’,p3,p4);八、翻譯模式如下：產(chǎn)生式語義規(guī)那么E→E1orE2E→E1andE2E→id1relopid2{E.place:=newtemp;emit(E.place‘:=’E1.place‘or’E2.place)}{E.place:=newtemp;emit(E.place‘:=’E1.place‘a(chǎn)nd’E2.place)}{E.place:=newtemp;emit(‘if’id1.placerelop.opid2.place‘goto’nextstat+3);emit(E.place‘:=’‘0’);emit(‘goto’nextstat+2);emit(E.place‘:=’‘1’)}試給出布爾表達(dá)式a<bandc<dore<f的三地址代碼〔10分〕。 107： 107：t2:=1 108：ife<fgoto111 109：t3:=0 110：goto112 111：t3:=1 112：t4:=t1andt2 113：t5:=t3ort4100：ifa<bgoto103101：t1:=0102：goto104103：t1:=1104：ifc<dgoto107105：t2:=0106：goto108九、翻譯規(guī)那么產(chǎn)生式語義規(guī)那么S→ifEthenS1S→ifEthenS1elseS2 E.true:=newlabel;E.false:=S.next;S1.next:=S.next;S.code:=E.code||gen(E.true’:’)||S1.codeE.true:=newlabel;E.false:=newlabel;S1.next:=S.next;S2.next:=S.next;S.code:=E.code||gen(E.true‘:’)||S1.code||gen(’goto’S.next)||gen(E.false‘:’)||S2.codeS→whileEdoS1S.begin:=newlabel;E.true:=newlabel;E.false:=S.next;S1.next:=S.begin;S.code:=gen(S.bgein‘:’)||E.code||gen(E.true‘:’)||S1.code||gen(‘goto’S.begin) 試把下面的語句翻譯成三地址代碼WhileA<CandB<DDoIfA=1thenC:=C+1else WhileA<=DDoA:=A+2108：gotoS.next113109：108：gotoS.next113109：ifA<=Dgoto111110：gotoS.next113111：T2=A+2112：A:=T2113：goto109114：goto100100：ifA<Cgoto102101：gotoL.false115102：ifB<Dgoto104103：gotoL.false115104：goto106105：gotoL.false109106：T1=C+1107：C:=T1十、翻譯規(guī)那么〔見第九題〕，試把下面的原程序翻譯成三地址代碼。whilea<bdo ifc<dthen x:=y+z else x:=y-z答：L1: ifa<b