河南科技大學期末考試編譯原理試卷及答案

1、得分河南科技大學電信科卷A一 填空題（每空2分，共20分）1. 不同的編譯程序關于數(shù)據(jù)空間的存儲分配策略可能不同，但大部分編譯中采用的方案有兩種：靜態(tài)存儲分配方案和動態(tài)存儲分配方案，而后者又分為（1） 和 （2） 。2. 規(guī)范規(guī)約是最（3）規(guī)約。3. 編譯程序的工作過程一般劃分為5個階段：詞法分析、（4） 、語義分析與中間代碼生成，代碼優(yōu)化及（5） 。另外還有（6）和出錯處理。4表達式x+y*z/(a+b)的后綴式為 （7） 。5文法符號的屬性有綜合屬性和 （8）。6假設二位數(shù)組按行存放，而且每個元素占用一個存儲單元，則數(shù)組a1.15,1.20某個元素ai，j的地址計算公式為（9）。7局部優(yōu)化

2、是局限于一個（10）范圍內(nèi)的一種優(yōu)化。得分二 選擇題（1-6為單選題，7-8為多選題，每問2分，共20分）1. 一個上下文無關文法G包括四個組成部分：一組終結符，一組非終結符，一個（ ），以及一組（ ）。A 字符串 B 產(chǎn)生式 C 開始符號 D 文法2.程序的基本塊是指（ ）。A 一個子程序 B 一個僅有一個入口和一個出口的語句C 一個沒有嵌套的程序段 D 一組順序執(zhí)行的程序段，僅有一個入口和一個出口3. 高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（ ）分析方法。A 自左向右 B 自頂向下 C 自底向上 D 自右向左4在通常的語法分析方法中，（ ）特別適用于表達式的分析。A 算符

3、優(yōu)先分析法 B LR分析法C 遞歸下降分析法 D LL（1）分析法5經(jīng)過編譯所得到的目標程序是（ ）。A 四元式序列 B 間接三元式序列C 二元式序列 D 機器語言程序或匯編語言程序6 一個文法所描述的語言是（ ）；描述一個語言的文法是（ ）。A 唯一的 B 不唯一的 C 可能唯一，也可能不唯一7 如果在文法G中存在一個句子，當其滿足下列條件（ ）之一時，則稱該文法是二義文法。A 其最左推導和最右推導相同 B 該句子有兩個不同的最左推導C 該句子有兩個不同的最右推導 D 該句子有兩棵不同的語法樹E 該句子對應的語法樹唯一8 下面（ ）語法制導翻譯中，采用拉鏈回填技術。A. 賦值語句 B. 布爾

4、表達式的計算 C. 條件語句 D. 循環(huán)語句得分三 解答題（共60分）1 （共15分）已知文法GE: EETE|（E）|i T*|+（1） 將文法G改造成LL（1）文法；（5分）（2） 構造文法G中每個非終結符的FIRST集合及FOLLOW集合；（5分）（3） 構造LL（1）分析表。（5分）2 （共12分）給定文法GS：SS(S)|（1） 給出句子()()()()的規(guī)范推導過程；（4分）（2） 指出每步推導所得句型的句柄；（4分）（3） 畫出該句子的語法推導樹。（4分）3 （共8分）在一個移入-規(guī)約分析過程中采用以下的語法制導翻譯模式，在按一個產(chǎn)生式規(guī)約時，立即執(zhí)行括號中的動作。 AaB pr

5、int “0”； Ac print “1”； BAb print “2”；（1） 當分析器的輸入為aacbb時，打印的字符串是什么？（3分）（2） 寫出分析過程。（5分）4 （10分）翻譯循環(huán)語句 while (a<b) do if (c>d) then x:=y+z 。要求：給出加注釋的分析樹及四元式序列。參考以下部分翻譯模式：(1) Sif E then M S1 backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1 .nextlist)(2) Swhile M1 E do M2 S1 backpatch(S

6、1.nextlist,M1,.quad); backpatch(E.truelist,M2,.quad); S.nextlist:=E.falselist emit (j,-,-,M1 .quad)(3) SA S.nextlist:=makelist()(4) LS L.nextlist:=S.nextlist(5) M M.quad:=nextquad(6) Eid1 relop id2 E.truelist:=makelist(nextquad); e.falselist:=makelist(nextquad+1); emit(jrelop.op,id1.place ,id2.place

7、,0); emit(j,-,-,0)(7) SL:=E emit(:=,E.place,-,L.place)(8) EE1+E2 E.place:=newtemp; emit(+,E1.place,E2.place,E.place,)5 （共15分）設有表格構造文法GS： Sa|(T) TT,S|S(1) 計算文法GS的FIRSTVT集和LASTVT集。（5分）(2) 構造GS的優(yōu)先關系表，并判斷GS是否為算符優(yōu)先文法。（5分）(3) 計算GS的優(yōu)先函數(shù)。（5分）得分二 單項選擇題（每題2分，共10分）1. 設有文法GI： II1|I0|Ia|Ic|a|b|c下列符號串中是該文法句子的有（ ）

8、。 ab0 a0c01 aaa bc10可選項有：A B C D2.程序的基本塊是指（ ）。A 一個子程序 B 一個僅有一個入口和一個出口的語句C 一個沒有嵌套的程序段 D 一組順序執(zhí)行的程序段，僅有一個入口和一個出口3. 高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（ ）分析方法。A 自左向右 B 自頂向下 C 自底向上 D 自右向左4經(jīng)過編譯所得到的目標程序是（ ）。A 四元式序列 B 間接三元式序列C 二元式序列 D 機器語言程序或匯編語言程序5 運行階段的存儲組織與管理的目的是（ ）。 提高編譯程序的運行速度 節(jié)省編譯程序的存儲空間 提高目標程序的運行速度 為運行階段的存儲

9、分配做準備可選項有：A. B. C. D. 得分2. （10分） 已知文法GS: SaBc|bABAaAb|bBb|（4） 構造其LL（1）分析表；（5） 判斷符號串baabbb是否為該文法的句子（寫出含有符號棧、輸入串和規(guī)則的分析過程）。3. (10分) 已知文法G為：EE+T|TTT*P|PPi（1） 構造該文法的優(yōu)先關系表（不考慮語句括號#），并指出此文法是否為算符優(yōu)先文法。（2） 構造文法G的優(yōu)先函數(shù)表。4 （8分）在一個移入-規(guī)約分析過程中采用以下的語法制導翻譯模式，在按一個產(chǎn)生式規(guī)約時，立即執(zhí)行括號中的動作。 SbAb print “1” A(B print “2” Aa prin

10、t “3”BAa) print “4”（3） 當輸入序列為b(aa)a)a)b時，打印的字符串是什么？（4） 寫出移入-規(guī)約分析過程。5 （12分）翻譯循環(huán)語句 while (x>y) do if (a=b) then x:=2*y+a 。要求：給出加注釋的分析樹、三地址碼序列及相應的四元式序列。參考以下部分翻譯模式：(1) Sif E then M S1 backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1 .nextlist)(2) Swhile M1 E do M2 S1 backpatch(S1.nextlis

11、t,M1,.quad); backpatch(E.truelist,M2,.quad); S.nextlist:=E.falselist emit (j,-,-,M1 .quad)(3) SA S.nextlist:=makelist()(4) LS L.nextlist:=S.nextlist(5) M M.quad:=nextquad(6) Eid1 relop id2 E.truelist:=makelist(nextquad); e.falselist:=makelist(nextquad+1); emit(jrelop.op,id1.place ,id2.place,0); emit

12、(j,-,-,0)(7) SL:=E emit(:=,E.place,-,L.place)(8) EE1+E2 E.place:=newtemp; emit(+,E1.place,E2.place,E.place,)6. (8分) Generate assembly code for the following sequence assuming that x,y and z are in memory locations(noticing only two registers R1 and R2).S=0I=0 L1: if x>y goto L2 Z=s+ai I=i+1Goto L

13、1 L2:7 (6分) Give out the all basic blocks of the following program fragment and construct the relevant flow graph(DAG). read C A=0 B=1 L4: A=A+B if B>C goto L2 B=B+1 goto L4L2: write A8. (8分)Translate the assignment statement bi=b*c-b*d into (1) A syntax tree.(2) Three address instructions.答案：(1)

14、 棧式動態(tài)存儲分配(2) 堆式動態(tài)存儲分配(3) 左(4) 語法分析(5) 目標代碼生成(6) 表格管理(7) xyz*ab+/+(8) 繼承屬性(9) a+(i-1)*20+j-1(10) 基本塊一、 選擇題（每問2分，共20分）1.C B 2.D 3.B 4.A 5.D 6.A,C7.BCD,選對一個得1分且不超過滿分，選錯一個扣一分，扣完為止。8.BCD，選對一個得1分且不超過滿分，選錯一個扣一分，扣完為止。二、 解答題1（1）文法存在左遞歸，消除左遞歸后的文法為：E(E)E|i E（2分）ETEE| （2分）T*|+ （1分）（2）(5分)沒考慮#扣0.5分，其它錯或少寫一個扣0.5分

15、FIRST(E)=(,i FIRST(E)=*,+, FIRST(T)=*,+ FOLLOW(E)=),*,+,# FOWLLOW(E)= ),*,+,# FOLLOW(T)=(,i（3）每錯一個扣0.5分，全錯或不寫不得分，扣完為止，共5分()i*+#EE(E)EEiEEE ETEEE ETEEE E TT*T+2（1）規(guī)范推導過程如下。寫錯推導符號扣0.5分,錯寫或少寫一步推導扣0.5分，扣完為止，最左推導扣2分，共4分。（2）（1）中加下劃線的部分是句柄，標識如（1）。每少寫一個句柄扣0.5分，扣完為止，共4分。（3）每少寫步扣0.5分，扣完為止，共4分。SS ( S )S ( S )

16、) )S ( S ) )S ( S ) ) S ( S ) )3（1）打印的字符串是：12020（錯一個扣0.5分，共3分）（2）歸約過程中錯一步扣0.5分，扣完為止。（共5分）4（1）每少寫一步扣0.5分，扣完為止，共5分。while M1.q=100 E1.t=102 do M2.q=102 S1E1.f=107 do S1.nl=103 (E3.t=102) L.p=x := E4.p=T1(E3.f=103) c>d x E5.p=y + E6.p=z y zS a<b if E2.t=102 then M3.q=104 S2 E2.f=103（2）少寫一個四元式扣0.5分

17、，全錯或不寫不得分，回填錯誤扣0.5分，共5分。四元式序列為： 5（1）少寫一個扣1分，全錯或不寫不得分，共5分。FIRSTVT(S)=a,(FIRSTVT(T)=, a,(LASTVT(S)= a,)LASTVT(T)= a,), ,(2)優(yōu)先表如下。每錯一個扣0.5分，全錯或不寫不得分，扣完為止，共3分文法GS沒有兩個非終結符相鄰的情況，且其優(yōu)先表中任一對終結符之間最多滿足、 三種關系中的一種，因此是GS算符優(yōu)先文法。（2分）可以不考慮終結符“#”。a(),#A(),#或者（3）優(yōu)先函數(shù)?？梢圆豢紤]終結符“#”。每錯一個扣0.5分，全錯或不寫不得分，扣完為止，共5分。a(),#f66266

18、2g777252或者a(),f44244g55523三、 填空題（每空2分，共20分）1目標程序 （target code） 語法分析（syntax analyzer） 代碼優(yōu)化器（code optimizer） 代碼產(chǎn)生器（code generator） 符號表管理（symbol table manager）2 繼承屬性（inherited attribute）3 局部優(yōu)化（local optimization）4 四元式（quatriple）5 E + * ( ) id四、 單項選擇題（每題2分，共10分）1.B 2.D 3.B 4.D 5.C五、 解答題（共70分）1（1） L(G)=0

19、m1m|M1 共2分，寫成扣1分（2） S=>0S1=>00S11=>000111，共3分， =>寫成->扣1分（3） 共3分，錯處扣0.5分，扣完為止2.（1）空白表格也可以填寫“錯誤”字樣,共4分，錯一個扣0.5分，扣完為止abc$(#)SSaBcSbABAAaAbAbBBbBB （2）共6分，其中判斷“baabbb是該文法句子”為2分，其他錯一個扣0.5分，扣完為止符號棧輸入串規(guī)則$S$BAb$BA$BbAa$BbA$BbbAa$BbbA$Bbbb$Bbb$Bb$b$baabbb$baabbb$aabbb$aabbb$abbb$abbb$bbb$bbb$bb

20、$b$SbABAaAbAaAbAbBsuccess3.(1) 共6分，其中判斷“該文法為算符優(yōu)先文法”為2分，其他錯一個扣0.5分，扣完為止+*i+><<*>><i>>(2) 共4分，錯一個扣0.5分，扣完為止+*if244g1354（1）34242421 ，共4分，錯一個扣0.5分（2）共4分，錯一個扣0.5分，扣完為止stackInput stringaction$b$b($b($b($b(a$b(A$b(Aa$ b(Aa)$ b(B$b(A$b(Aa$b(Aa)$b（B$b(A$b(Aa$b(Aa)$b(B$bA$bAb$S$s$b(aa)

21、a)a)b$(aa)a)a)b$(aa)a)a)b$abbb$(aa)a)a)b$bbb$aa)a)a)b$bb$a)a)a)b$a)a)a)b$)a)a)b$a)a)b$a)a)b$a)a)b$)a)b$a)b$a)b$a)b$)b$b$b$b$shiftshiftshiftshiftshiftreduce, Aashiftshiftreduce, BAa）reduce, A(B shiftshiftreduce, BAa）reduce, A(Bshiftshiftreduce, BAa）reduce, A(Bshiftreduce, SbAbaccept5 共12分，其中帶注釋的分析樹、三地址碼序列和四元式序列分別為4分，