1編譯原理期末復(fù)習(xí)題(答案)

1、序號(hào)北方工業(yè)大學(xué)編譯原理課程期末復(fù)習(xí)題（答案）A卷訂線裝開(kāi)課學(xué)院考試方式：閉卷考試時(shí)間：120 分鐘班級(jí) 姓名 學(xué)號(hào) 題 號(hào)一二三四五六七八九十總 分得 分閱卷人一判斷題（每個(gè)小題1分，共10分）1. 程序語(yǔ)言主要由語(yǔ)法和語(yǔ)義兩方面定義。 （ ）2. 自上而下分析方法會(huì)遇到的主要問(wèn)題有左遞歸和回溯。 （ ）3. 已知文法G：Eài | EAE，Aà+|* ，其中的終結(jié)符號(hào)集包括i，+。（ ）4. 編譯程序是將高級(jí)語(yǔ)言程序翻譯成機(jī)器語(yǔ)言程序。 （ ）5. 只含有綜合屬性的屬性文法稱為S-屬性文法。 （ ）6. LL(1)文法中第一個(gè)L的含義是從左到右掃描輸入串。 （ ）7.

2、在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。 （ ） 8. 一個(gè)語(yǔ)義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。 （ ） 9. 一個(gè)句型的直接短語(yǔ)是唯一的。 （ ） 10. 確定的自動(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. 短語(yǔ)文法 B. 正規(guī)文法 C. 上下文有關(guān)文法 D. 上下文無(wú)關(guān)文法2.  不可能是目標(biāo)代碼。  

3、;  A. 匯編指令代碼     B. 可重定位指令代碼   C. 絕對(duì)指令代碼  D. 中間代碼3. 將編譯程序分成若干個(gè)“遍”是為了 。  A. 提高程序的執(zhí)行效率 B. 利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率 C. 使程序的結(jié)構(gòu)更加清晰 D. 利用有限機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率 4. 后綴式ab+cd+/可用表達(dá)式 來(lái)表示。 A. a+b/c+d B. (a+b)/(c+d) C. a+b/(c+d) D. a+b+c/d 5. 文法G：SxSx|y所識(shí)別的語(yǔ)言是 。A. xyxB. (xyx)*C. x

4、nyxn(n0) D. x*yx*6. 文法GE： EE+T|T TT*P|P P(E)|i則句型P+T+i的句柄和最左素短語(yǔ)為 。A. P+T和iB. P和P+T C. i和P+T+i D. P和T7. 設(shè)有文法GE： EE*T|T   TT+i|i句子1+2*8+6按該文法G歸約，其值為 。 A. 42 B. 23 C. 30 D. 178. 規(guī)范歸約指 。 A. 最右推導(dǎo)的逆過(guò)程 B. 最左推導(dǎo)的逆過(guò)程 C. 規(guī)范推導(dǎo) D. 最左歸約的逆過(guò)程9. 詞法分析所依據(jù)的是 。 A. 語(yǔ)義規(guī)則B. 構(gòu)詞規(guī)則C. 語(yǔ)法規(guī)則D. 等價(jià)變換規(guī)則10. 狀態(tài)轉(zhuǎn)換圖（見(jiàn)下圖）接受的集合

5、為 。 0  1 0YX A. 以 0開(kāi)頭的二進(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è)編譯程序結(jié)構(gòu)更加簡(jiǎn)潔、明確，因此， 。 A. 詞法分析器作為子程序較好 B. 詞法分析器并不作為一個(gè)獨(dú)立的階段 C. 詞法分析器分解為多個(gè)過(guò)程，由語(yǔ)法分析器選擇使用 D. 詞法分析器應(yīng)作為獨(dú)立的一遍12. 若a為終結(jié)符，則A·a為 項(xiàng)目。 A. 移進(jìn)B. 歸約C. 接受D. 待約13. 中間代碼生成所依據(jù)的是 。 A. 語(yǔ)法規(guī)則B. 詞法規(guī)則C. 語(yǔ)義規(guī)則D. 等價(jià)

6、變換規(guī)則14. 終結(jié)符具有 屬性。  A. 傳遞B. 繼承C. 抽象D. 綜合15. 下推自動(dòng)機(jī)識(shí)別的語(yǔ)言是 。 A. 0型語(yǔ)言 B. 1型語(yǔ)言 C. 2型語(yǔ)言 D. 3型語(yǔ)言16. 常用的中間代碼形式不含 。  A. 三元式 B. 四元式 C. 逆波蘭表達(dá)式 D. 語(yǔ)法樹(shù)17. 算符文法是指 的文法。 A. 沒(méi)有形如U.VW.的產(chǎn)生式（U、V、WÎVN） B. VT中任意兩個(gè)符號(hào)之間至多存在一種算符優(yōu)先關(guān)系 C. 沒(méi)有相同右部的產(chǎn)生式 D. 沒(méi)有形如U的產(chǎn)生式 18. 下述語(yǔ)句類中，_在編譯階段通常不產(chǎn)生可執(zhí)行代碼。 A. 變量說(shuō)明語(yǔ)句 B. 流程控制語(yǔ)句 C.

7、 輸入輸出語(yǔ)句 D. 賦值語(yǔ)句 19. 文法所描述的語(yǔ)言是 的集合。 A. 文法的字母表中符號(hào)組成的符號(hào)串 B. 文法的字母表中終結(jié)符號(hào)組成的符號(hào)串 C. 由文法開(kāi)始符號(hào)推導(dǎo)的符號(hào)串 D. 由文法開(kāi)始符號(hào)推導(dǎo)的終結(jié)符號(hào)串 20. 符號(hào)串a(chǎn)b1b2是文法GA：AaB, BbB|b的句子，該句子的句柄是_。 A. b1 B. b2 C. a D. b1b2 解：1. B 2.   D 3. C 4. B 5. C 6. B 7. A 8. A 9. B 10. D 11. A 12. A 13. C 14.  D 15. C 16.  D 17.

8、A 18. A 19. D 20. B 三、已知文法G的產(chǎn)生式為：E®T|E+T|E-TT®F|T*F (2-1)F® (E)|i試求：（1）消除該文法的左遞歸；（5分）（2）利用(1)得到的文法G(2-1)，求(i+i*i)的最左推導(dǎo)和語(yǔ)法分析樹(shù)。（5分）解：（1）E®TEE®+TE|-TE |T®FT|T®*FT| (2-1)F®(E)|i（2）EÞTEÞFTEÞ(E)TEÞ(E)Þ(TE)Þ(FTE)Þ(iTE')Þ(iE

9、)Þ(i+TE)Þ(i+FTE)Þ(i+iTE)Þ(i+i*FTE)Þ(i+i*iTE)Þ(i+i*i) Þ(i+i*i)EE(根)Ti()Fi+TTEi*四、已知文法G3：S®a|(T);T®T,S|S其中：S、T是非終結(jié)符，a、 、, 、 （ 和 ）是終結(jié)符，S為開(kāi)始符合，試求：(1)計(jì)算非終結(jié)符的FISTVT和LASTVT;(2)給出終結(jié)符的算符優(yōu)先關(guān)系表；(3)給出(a,(a,a)的算符優(yōu)先分析過(guò)程，指出每次規(guī)約的素短語(yǔ)。（共30分，每小題10分）解：(1)FIRSTVT和LASTVT如下：FIR

10、STVT(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)先分析過(guò)程如下：棧輸入字符串動(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)#歸#

11、(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)生式為：E®T|E+T|E-TT®F|T*F (2-1)F® (E)|i試給出表達(dá)式i1*i2+i3的規(guī)范式規(guī)約過(guò)程。用下面的格式描述該過(guò)程。（10分）步驟 符號(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#歸，用Fi3#T*i2+i3#歸，用TF4#T*i2+i

12、3#進(jìn)5#T*i2+i3#進(jìn)6#T*F+i3#歸，用Fi7#T+i3#歸，用FE*F8#E+i3#歸，用FT9#E+i3#進(jìn)10#E+i3#進(jìn)11 #E+F# 歸，用Ei 12 #E+T# 歸，用TF13#E#歸，用EE+T14#E#接受六、屬性文法如表5-1所示，試求表達(dá)式a+4+c的抽象語(yǔ)法樹(shù)，并描述建立抽象語(yǔ)法樹(shù)過(guò)程。（10分）表6-1 屬性文法產(chǎn)生式語(yǔ)義規(guī)則EE1+T E.nptr := mknode( + , E1.nptr , T.nptr )EE1-T E.nptr := mknode( - , E1.nptr , T.nptr )ETE.nptr := T.nptrT(E)T.

13、nptr := E.nptrTid T.nptr := mklear( id , id.entry )Tnum 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 );七已知翻譯規(guī)則產(chǎn)生式語(yǔ)義規(guī)則S if E then S1S if E then S1 else S2E.true :

14、= 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.codeSwhile E do S1S.begin := newlabel;E.true

15、:= 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 )試把下面的語(yǔ)句翻譯成三地址代碼While A<C and B<D DoIf A=1 then C:=C+1 elseWhile A<=D Do A:=A+2108：goto S.next 113109：if A<=D goto 111110：goto S.next 113 111：T2=A+2112：A:

16、=T2113：goto 109 114：goto 100100：if A<C goto 102101：goto L.false 115102：if B<D goto 104103：goto L.false 115104：goto 106105：goto L.false 109106：T1=C+1107：C:=T1答：八、已知翻譯規(guī)則（見(jiàn)第七題），試把下面的原程序翻譯成三地址代碼。while a < b doif c < d thenx := y + zelsex := y - z答： L1:if a < b goto L2goto LnextL2:if c <

17、; d goto L3goto L4L3:t1 := y + zx := t1goto L1（goto L5） L4:t2 := y - zx := t2L5goto L1 Lnext: goto L1九、對(duì)以下四元式程序，試求：（1）它的流圖（5分），（2）對(duì)其中的循環(huán)進(jìn)行循環(huán)優(yōu)化（10分）。I:=1Read J,KL: A:=K*IB:=J*IC:=A*BWrite CI:=I+1If I<100 goto LHalt十、 已知一個(gè)三地址代碼如下。試完成（1）給出對(duì)應(yīng)的流圖（5分）；（2）對(duì)流圖中的代碼進(jìn)行優(yōu)化（10分）。I:=1Read J,KL1:If I>100 goto L2A:=K*IB:=J*IC:=A*BWrite CI:=I+1I:=1Read J,KA:=K*IB:=J