1編譯原理期末復習題(答案)

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

2、在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。 （ ） 8. 一個語義子程序描述了一個文法所對應(yīng)的翻譯工作。 （ ） 9. 一個句型的直接短語是唯一的。 （ ） 10. 確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。 （ ） 解：1. 2. 3.× 4.× 5. 6. 7.× 8.× 9.× 10.二、選擇題（每個小題1分，共20分）1. 文法分為四種類型，即0型、1型、2型、3型。其中3型文法是_。 A. 短語文法 B. 正規(guī)文法 C. 上下文有關(guān)文法 D. 上下文無關(guān)文法2.  不可能是目標代碼。  

3、;  A. 匯編指令代碼     B. 可重定位指令代碼   C. 絕對指令代碼  D. 中間代碼3. 將編譯程序分成若干個“遍”是為了 。  A. 提高程序的執(zhí)行效率 B. 利用有限的機器內(nèi)存并提高機器的執(zhí)行效率 C. 使程序的結(jié)構(gòu)更加清晰 D. 利用有限機器內(nèi)存但降低了機器的執(zhí)行效率 4. 后綴式ab+cd+/可用表達式 來表示。 A. a+b/c+d B. (a+b)/(c+d) C. a+b/(c+d) D. a+b+c/d 5. 文法G：SxSx|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的句柄和最左素短語為 。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. 最右推導的逆過程 B. 最左推導的逆過程 C. 規(guī)范推導 D. 最左歸約的逆過程9. 詞法分析所依據(jù)的是 。 A. 語義規(guī)則B. 構(gòu)詞規(guī)則C. 語法規(guī)則D. 等價變換規(guī)則10. 狀態(tài)轉(zhuǎn)換圖（見下圖）接受的集合

5、為 。 0  1 0YX A. 以 0開頭的二進制數(shù)組成的集合 B. 以0結(jié)尾的二進制數(shù)組成的集合 C. 含奇數(shù)個0的二進制數(shù)組成的集合 D. 含偶數(shù)個0的二進制數(shù)組成的集合11. 詞法分析器作為獨立的階段使整個編譯程序結(jié)構(gòu)更加簡潔、明確，因此， 。 A. 詞法分析器作為子程序較好 B. 詞法分析器并不作為一個獨立的階段 C. 詞法分析器分解為多個過程，由語法分析器選擇使用 D. 詞法分析器應(yīng)作為獨立的一遍12. 若a為終結(jié)符，則A·a為 項目。 A. 移進B. 歸約C. 接受D. 待約13. 中間代碼生成所依據(jù)的是 。 A. 語法規(guī)則B. 詞法規(guī)則C. 語義規(guī)則D. 等價

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

7、 輸入輸出語句 D. 賦值語句 19. 文法所描述的語言是 的集合。 A. 文法的字母表中符號組成的符號串 B. 文法的字母表中終結(jié)符號組成的符號串 C. 由文法開始符號推導的符號串 D. 由文法開始符號推導的終結(jié)符號串 20. 符號串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)的最左推導和語法分析樹。（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為開始符合，試求：(1)計算非終結(jié)符的FISTVT和LASTVT;(2)給出終結(jié)符的算符優(yōu)先關(guān)系表；(3)給出(a,(a,a)的算符優(yōu)先分析過程，指出每次規(guī)約的素短語。（共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)先分析過程如下：棧輸入字符串動作#(a，(a，a)#預(yù)備#(a，(a，a)#進#(a,(a，a)#進#(s,(a，a)#歸#(t,(a，a)#歸#(t，(a，a)#進#(t，(a，a)#進#(t，(a,a)#進#(t，(s,a)#歸#

11、(t，(t,a)#歸#(t，(t,a)#進#(t，(t，a)#進#(t，(t，s)#歸#(t，(t)#歸#(t，(t)#進#(t，s)#歸#(t)#歸#(t)#進#s#歸五、已知文法G 的產(chǎn)生式為：E®T|E+T|E-TT®F|T*F (2-1)F® (E)|i試給出表達式i1*i2+i3的規(guī)范式規(guī)約過程。用下面的格式描述該過程。（10分）步驟 符號棧 輸入串 所用產(chǎn)生式答：輸入串i1*i2+i3的分析步驟：步驟 符號棧 輸入串 所用產(chǎn)生式0#i1*i2+i3#預(yù)備1#i1*i2+i3#進2#F*i2+i3#歸，用Fi3#T*i2+i3#歸，用TF4#T*i2+i

12、3#進5#T*i2+i3#進6#T*F+i3#歸，用Fi7#T+i3#歸，用FE*F8#E+i3#歸，用FT9#E+i3#進10#E+i3#進11 #E+F# 歸，用Ei 12 #E+T# 歸，用TF13#E#歸，用EE+T14#E#接受六、屬性文法如表5-1所示，試求表達式a+4+c的抽象語法樹，并描述建立抽象語法樹過程。（10分）表6-1 屬性文法產(chǎn)生式語義規(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)生式語義規(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 )試把下面的語句翻譯成三地址代碼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ī)則（見第七題），試把下面的原程序翻譯成三地址代碼。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九、對以下四元式程序，試求：（1）它的流圖（5分），（2）對其中的循環(huán)進行循環(huán)優(yōu)化（10分）。I:=1Read J,KL: A:=K*IB:=J*IC:=A*BWrite CI:=I+1If I<100 goto LHalt十、 已知一個三地址代碼如下。試完成（1）給出對應(yīng)的流圖（5分）；（2）對流圖中的代碼進行優(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