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

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

2、中第一個(gè)L的含義是從左到右掃描輸入串。（）7. 在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。（）8. 一個(gè)語義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。（）9. 一個(gè)句型的直接短語是唯一的。（）10. 確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。（）解：1.V 2.V3.x 4.x 5.V6.V 7. x 8.x 9.x 10.V、選擇題（每個(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、3. 將編譯程序分成若干個(gè)“遍”是為了 。A.提高程序的執(zhí)行效率 B.利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率C.使程序的結(jié)構(gòu)更加清晰D.利用有限機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率4. 后綴式ab+cd+/可用表達(dá)式 來表示。5. 文法G: Sf xSx|y所識(shí)別的語言是 。A. xyxB. (xyx)*C. xnyxn(n 鳥)D.6. 文法 GE:Ef E+T|TTf T*P|PPf (E)|i則句型P+T+i的句柄和最左素短語為A. P+T 和 i B.7. 設(shè)有文法GE:Ef E*T|TTf T+i|i句子1+2*8+6按該文法P 和 P+T C. i 和 P+T+i D.A. 42 B.

4、238. 規(guī)范歸約指A.最右推導(dǎo)的逆過程C.規(guī)范推導(dǎo)9. 詞法分析所依據(jù)的是一G歸約,C. 30其值為D.17x*yx*B.最左推導(dǎo)的逆過程D.最左歸約的逆過程A.語義規(guī)則B.構(gòu)詞規(guī)則10. 狀態(tài)轉(zhuǎn)換圖（見下圖）接受的集合為C.語法規(guī)則D.等價(jià)變換規(guī)則1B.以0結(jié)尾的二進(jìn)制數(shù)組成的集合D.含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合 明確，因此，A.以0開頭的二進(jìn)制數(shù)組成的集合C.含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合11. 詞法分析器作為獨(dú)立的階段使整個(gè)編譯程序結(jié)構(gòu)更加簡潔、A.詞法分析器作為子程序較好B.詞法分析器并不作為一個(gè)獨(dú)立的階段D.詞法分析器應(yīng)作C.詞法分析器分解為多個(gè)過程，由語法分析器選擇使用 為獨(dú)立

5、的一遍12. 若a為終結(jié)符，則A-aaB為項(xiàng)目。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、W VN)B. Vt中任意兩個(gè)符號(hào)之間至多存在一種算符優(yōu)先關(guān)系C. 沒有相同右部的產(chǎn)生式D. 沒有形如U &的產(chǎn)生式18.

6、下述語句類中，編譯階段通常不產(chǎn)生可執(zhí)行代碼。A.變量說明語句 B.流程控制語句 C.輸入輸出語句 D.賦值語句19. 文法所描述的語言是 的集合。A. 文法的字母表中符號(hào)組成的符號(hào)串B. 文法的字母表中終結(jié)符號(hào)組成的符號(hào)串C. 由文法開始符號(hào)推導(dǎo)的符號(hào)串D. 由文法開始符號(hào)推導(dǎo)的終結(jié)符號(hào)串20. 符號(hào)串a(chǎn)b1b2是文法GA : A aB, B bB|b的句子，該句子的句柄是 <A. b1B.b2C. aD.b1b2解：1. B2. D3. C4. B5.C6. B7. A8. A9. B10.D11. A12. A13. C14. D15.C16. D17. A18. A19. D20.

7、B三、已知文法G的產(chǎn)生式為：ET|E+T|E-TTF|T*F(2-1)F(E)|i試求：(1)消除該文法的左遞歸；(5 分)(5 分)(2)利用得到的文法G'2-1),求(i+i*i)的最左推導(dǎo)和語法分析樹 解: (1)E TE'E' +TE'TE'|&T FT'|(2-1)'T' *FT'|&E TEFT'E')FT E (E)T E (E) ££(TE '(FT'E')(i+iT ' E')(i+i*FT 'E'

8、) (i+i*iT ' E') (i+i*i(iT'E')(i £E') (i+TE ') (i+££ (i+i*i)/ E(根、E 'F11T'£( )1TE '£./ / y-/ i+: *£F (E)|ii*i(2)四、已知文法G3：S afl(T);T T,S|SS為開始符合，試求：(共30分，每小題10其中：S、T是非終結(jié)符，a八、，、(和)是終結(jié)符,(1) 計(jì)算非終結(jié)符的FISTVT和LASTVT;(2) 給出終結(jié)符的算符優(yōu)先關(guān)系表；(3) 給出(a,

9、(a,a)的算符優(yōu)先分析過程，指出每次規(guī)約的素短語。 分)解：(I)FIRSTVT 和 LASTVT 如下：FIRSTVT(S)=a , A, (FIRSTVT(T)= , a,A,(LASTVT(S)=a , A, )LASTVT(T)= , a,A, )(2)構(gòu)造優(yōu)先關(guān)系表如下：aA()#a>>>A>>>(<<<=<)>>><<<>>#<<<=輸入串(a,(a,a)的算符優(yōu)先分析過程如下:棧輸入字符串動(dòng)作#(a , (a , a)#預(yù)備#(a , (a , a)#進(jìn)

10、#(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)生式為：E T|E+T|E-TT F|T*F(2-1)F (E)|i試給出表達(dá)式ii*i2+i3的規(guī)范式規(guī)約過程。用下面的格式描述該過程。(10分)步驟符號(hào)棧輸入串所用產(chǎn)生式:輸入串 步驟i1*i 2

11、+i3的分析步驟：符號(hào)棧輸入串所用產(chǎn)生式0#i1*i 2+i3#預(yù)備1#i1*i 2+i3#進(jìn)2#F*i2+i3#歸，用FT3#T*i 2+i3#歸，用T - F4#T*i2+i3#進(jìn)5#T*i2+i3#進(jìn)6#T*F+i3#歸，用FT7#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的抽象語法樹，并描述建立抽象語法 樹過程。（10分）產(chǎn)生式語義規(guī)則E >E 什TE. nptr :=mkno de(,E1 .

12、+pt', T.nptr)EE 1-TE. nptr :=mkno de(-'，&ptr , T.nptr )E>TE. nptr :=T.n ptrT> (E)T. nptr :=E.n ptrT> idT. nptr :=mklear( id,id.en try )T> numT. nptr :=mklear( num , num.val )表6-1屬性文法答:(1)(2)(3)(4)(5)P1p2p3P4P5=mkleaf( id , en trya );=mkleaf( num , 4 );=mknode( +'' , p

13、1 , p2 );=mkleaf( id , en tryc );=mknode( + ' , p3 , p4 );+指向符號(hào)表中a的表項(xiàng)的指針idT1Fid指向符號(hào)表中C的表項(xiàng)的指針num4表達(dá)式a - 4 + c的語法樹七已知翻譯規(guī)則產(chǎn)生式語義規(guī)則St if E then S1St if E then S1 else S2E.true := newlabel;E.false := S.next;S1.next := S.next;S.code := E.code | gen( E.true' : ' ) | S1.codeE.true := newlabel;E.f

14、alse := newlabel;51. next := S.next;52. next := S.next;S.code := E.code |gen( E.true: ' ) | S1.code |gen( ' goto ' S.next ) |gen( E.false: ' ) | S2.codeSt while E do S1S.begin := newlabel;E.true := newlabel;E.false := S.next;S1.next := S.begin;S.code := gen( S.bgein: ' ) | E.code

15、 |gen( E.true: ' ) | S1.code |gen( goto ' S.begin )試把下面的語句翻譯成三地址代碼While A<C and B<D DoIf A=1 then C:=C+1 elseWhile A<=D Do A:=A+2100： if A<C goto 102 101: goto L.false 115102： if B<D goto 104103： goto L.false 115104： goto 106105： goto L.false 109106： T仁C+1107： C:=T1108: goto S

16、.next 113109: if A<=D goto 111110： goto S.next 113111： T2=A+2112： A:=T2113： goto 109114： goto 100八、已知翻譯規(guī)則（見第七題），試把下面的原程序翻譯成三地址代碼while a < b do if c < d the nx := y + z elsex := y - z答：L1: if a < b goto L2goto LnextL2: if c < d goto L3goto L4L3: t1 := y + zx := t1goto L1 （ goto L5）L4: t2 := y - zx := t2L5 goto L1Ln ext: goto