五套編譯原理期末考試試卷及答案

1、得分一 填空題（每空 2 分，共 20 分）1. 不同的編譯程序關(guān)于數(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ù)組按行存放，而且每個元素占用一個存儲單元，則數(shù)組 a1.15,1.20某個元素 ai，j的地址計算公式為（9）。7局部優(yōu)化是局

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

3、分析法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 下面（ ）語法制導翻譯中，采用拉鏈回填技術(shù)。A. 賦值語句B. 布爾表達式的計算

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

5、執(zhí)行括號中的動作。AaBprint “0”；Acprint “1”；BAbprint “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 M

6、2 S1 backpatch(S1.nextlist,M1,.quad);backpatch(E.truelist,M2,.quad);S.nextlist:=E.falselistemit (j,-,-,M1 .quad)(3)SAS.nextlist:=makelist()(4)LSL.nextlist:=S.nextlist(5)MM.quad:=nextquad(6)Eid1 relop id2E.truelist:=makelist(nextquad);e.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place ,id2.pl

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

8、符號串中是該文法句子的有（）。 ab0 a0c01 aaa bc10可選項有：A BCD2.程序的基本塊是指（）。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） 構(gòu)造其 LL（1）分析表；（5） 判斷符號串 baabbb 是否為該文法的句子（寫出含有符號棧、輸入串和規(guī)則的分析過程）。3. (10 分) 已知文法 G 為：EE+T|TTT*P|PPi（1） 構(gòu)造該文法的優(yōu)先關(guān)系表（不考慮語句括號#），并指出此文法是否為算符優(yōu)先文法。（2） 構(gòu)造文法 G 的優(yōu)先函數(shù)表。4 （8 分）在一個移入-規(guī)約分析過程中采用以下的語法制導翻譯模式，在按一個產(chǎn)生式規(guī)約時，立即執(zhí)行括號中的動作。SbAbprint “1”A(Bprint “2”Aa

10、print “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.

11、nextlist,M1,.quad);backpatch(E.truelist,M2,.quad);S.nextlist:=E.falselistemit (j,-,-,M1 .quad)(3)SAS.nextlist:=makelist()(4)LSL.nextlist:=S.nextlist(5)MM.quad:=nextquad(6)Eid1 relop id2E.truelist:=makelist(nextquad);e.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place ,id2.place,0);emit(j,-,-,

12、0)(7) SL:=Eemit(:=,E.place,-,L.place)(8) EE1+E2E.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=0L1: if x>y goto L2Z=s+aiI=i+1 Goto L1L2:7 (6 分)

13、 Give out the all basic blocks of the following program fragment and construct the relevant flow graph(DAG).read C A=0 B=1L4: A=A+Bif B>C goto L2 B=B+1goto L4 L2: write A8. (8 分)Translate the assignment statement bi=b*c-b*d into(1) A syntax tree.(2) Three address instructions.答案：(1) 棧式動態(tài)存儲分配(2) 堆

14、式動態(tài)存儲分配(3) 左(4) 語法分析(5) 目標代碼生成(6) 表格管理(7) xyz*ab+/+(8) 繼承屬性(9) a+(i-1)*20+j-1(10) 基本塊一、選擇題（每問 2 分，共 20 分）1.C B2.D3.B4.A5.D6.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 分FIRST(

15、E)=(,iFIRST(E)=*,+, FIRST(T)=*,+FOLLOW(E)=),*,+,#FOWLLOW(E)= ),*,+,# FOLLOW(T)=(,i（3）每錯一個扣 0.5 分，全錯或不寫不得分，扣完為止，共 5 分()i*+#EE(E)EEiEEE ETEEETEEE E E TT*T+2（1）規(guī)范推導過程如下。寫錯推導符號扣 0.5 分,錯寫或少寫一步推導扣 0.5 分，扣完為止，最左推導扣 2 分，共 4 分。S Þ S(S) Þ S(e ) Þ S(S)() Þ S(e )() Þ S(S)()() Þ S(S

16、(S)()() Þ S(S(e )()() Þ S(S(S)()()() Þ S(S(e )()()() Þ S(e )()()() Þ e ()()()()（2）（1）中加下劃線的部分是句柄，標識如（1）。每少寫一個句柄扣 0.5 分，扣完為止，共 4 分。（3）每少寫步扣 0.5 分，扣完為止，共 4 分。SS( S )S( S )S( S ) S( S )S( S ) 3（1）打印的字符串是：12020（錯一個扣 0.5 分，共 3 分）（2）歸約過程中錯一步扣 0.5 分，扣完為止。（共 5 分）4（1）每少寫一步扣 0.5 分，扣完為

17、止，共 5 分。Swhile M1.q=100E1.t=102do M2.q=102S1E1.f=107a<b ifE2.t=102 thenM3.q=104S2E2.f=103(E3.t=102) L.p=x :=E4.p=T1(E3.f=103)c>dxE5.p=y+ E6.p=z（2）少寫一個四元式扣 0.5 分，全錯或不寫不yz四元式序列為：100( j <, a, b,102) 101( j, _, _,107) 102( j >, c, d ,104) 103( j, _, _,106) 104(+, y, z,T1) 105(:=,T1, _, x) 10

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

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

20、|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ī)則$Sbaabbb$BAbbaabbb$SbAB$BAaabbb$BbAaaabbb$AaAb$BbAabbb$BbbAaabbb$AaAb$B

21、bbAbbb$Bbbbbbb$Ab$Bbbbb$Bbb$b$B$success3.(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(aa)a)a)b$b(aa)a)a)b$shift$b(aa)a)a)b$abbb$shift$b(aa)a)a)

22、b$bbb$shift$b(aa)a)a)b$bb$shift$b(aa)a)a)b$shift$b(Aa)a)a)b$reduce, Aa$b(Aa)a)a)b$shift$ b(Aa)a)a)b$shift$ b(Ba)a)b$reduce, BAa）$b(Aa)a)b$reduce, A(B$b(Aa)a)b$shift$b(Aa)a)b$shift$b（Ba)b$reduce, BAa）$b(Aa)b$reduce, A(B$b(Aa)b$shift$b(Aa)b$shift$b(Bb$reduce, BAa）$bAb$reduce, A(B$bAb$shift$S$reduce, S

23、bAb$s$accept5 共 12 分，其中帶注釋的分析樹、三地址碼序列和四元式序列分別為 4 分，錯一個序列扣 0.5 分，而錯某點（某項）少于或等于 5 個扣 0.5 分帶注釋語法樹(略)三地址碼序列四元式序列M1: if (x>y) goto M2100(j>, x,y,102)goto M4101(j,-,-,108)M2: if (a=b) goto M3102(j=,a,b,104)goto M1103(j,-,-,100)M3: t1=2*y104(*,2,y,t1)t2=t1+a105(+,t1,a,t2)x=t2106(=,t2,-,x)goto M1107(j

24、,-,-,100)M4:108(-,-,-,-)6共 8 分，錯一個扣 0.5 分，扣完為止LD R1,0ST S,R1ST I,R1 L1: LD R1,XSUB R1,R1,Y (OR SUB R1,Y) BGTZ R1,L2LD R2,a(R1)ADD R2,R2,S (OR ADD R2,S) ST Z,R2LD R1,I (從這開始，下面的語句中的 R1 也可以全部變成 R2) ADD R1,R1,1 (OR INC R1)ST I,R1BR L1L2:7 共 6 分，基本塊劃分和流圖各為 3 分，錯一處扣 1 分，扣完為止read c B1 A=0B=1B2L4: A=A+BIf

25、B>C goto L2 (OR B4)B3B=B+1GotoL4 (OR B2)B4L2: write A8. （1）共 4 分，錯一項扣 1 分，扣完為止（2）共 4 分，錯一項扣 1 分，扣完為止 t1=b*ct2=b*d t3=t1-t2t4=i+1 (or t4=i) bt4=t3一、判斷題：1.一個上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。()2.一個句型的直接短語是唯一的。()3.已經(jīng)證明文法的二義性是可判定的。（）4.每個基本塊可用一個 DAG 表示。（）5.每個過程的活動記錄的體積在編譯時可靜態(tài)確定。（）6.2 型文法一定是 3 型文法。（）7.一個句型一定句子。(

26、)8.算符優(yōu)先分析法每次都是對句柄進行歸約。()9.采用三元式實現(xiàn)三地址代碼時，不利于對中間代碼進行優(yōu)化。（）10.編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。()11.一個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。()12.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。()13.遞歸下降分析法是一種自下而上分析法。()14.并不是每個文法都能改寫成 LL(1)文法。()15.每個基本塊只有一個入口和一個出口。()16.一個 LL(1)文法一定是無二義的。()17.逆波蘭法表示的表達試亦稱前綴式。()18.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。()19.正規(guī)文法產(chǎn)生的語

27、言都可以用上下文無關(guān)文法來描述。()20.一個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。()21.3 型文法一定是 2 型文法。()22.如果一個文法存在某個句子對應兩棵不同的語法樹，則文法是二義性的。()二、填空題：1.( )稱為規(guī)范推導。2.編譯過程可分為 （） ，（），（），（）和（）五個階段。3.如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是（）。4.從功能上說，程序語言的語句大體可分為（）語句和（）語句兩大類。5.語法分析器的輸入是（），其輸出是（）。6.掃描器的任務(wù)是從（）中識別出一個個（）。7.符號表中的信息欄中登記了每個名字的有關(guān)的性質(zhì)，如（）等等。8.一個過程相應的 DIS

28、PLAY 表的內(nèi)容為（）。9.一個句型的最左直接短語稱為句型的（）。10.常用的兩種動態(tài)存貯分配辦法是（）動態(tài)分配和（）動態(tài)分配。11.一個名字的屬性包括()和()。12.常用的參數(shù)傳遞方式有（），（）和（）。13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（），（）和（）三個級別。14.語法分析的方法大致可分為兩類，一類是（）分析法，另一類是（）分析法。15.預測分析程序是使用一張（）和一個（）進行聯(lián)合控制的。16.常用的參數(shù)傳遞方式有（），（）和（）。17.一張轉(zhuǎn)換圖只包含有限個狀態(tài),其中有一個被認為是（）態(tài);而且實際上至少要有一個（）態(tài)。18.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（），

29、（）和（）三個級別。19.語法分析是依據(jù)語言的（）規(guī)則進行。中間代碼產(chǎn)生是依據(jù)語言的（）規(guī)則進行的。20.一個句型的最左直接短語稱為句型的（）。21.一個文法 G，若它的預測分析表 M 不含多重定義，則該文法是（）文法。22.對于數(shù)據(jù)空間的存貯分配， FORTRAN 采用()策略， PASCAL 采用()策略。23.如果一個文法存在某個句子對應兩棵不同的語法樹， 則稱這個文法是()。24.最右推導亦稱為（），由此得到的句型稱為（）句型。25.語法分析的方法大致可分為兩類，一類是（）分析法，另一類是（）分析法。26.對于文法 G，僅含終結(jié)符號的句型稱為 ()。27.所謂自上而下分析法是指（）。2

30、8.語法分析器的輸入是（），其輸出是（）。29.局限于基本塊范圍的優(yōu)化稱（）。30.預測分析程序是使用一張（）和一個（）進行聯(lián)合控制的。31.2 型文法又稱為（）文法；3 型文法又稱為（）文法。32.每條指令的執(zhí)行代價定義為（）。33.算符優(yōu)先分析法每次都是對（）進行歸約。三、名詞解釋題：1.局部優(yōu)化2.二義性文法3.DISPLAY 表4.詞法分析器5.最左推導6.語法7.文法8.基本塊9.語法制導翻譯10.短語11.待用信息12.規(guī)范句型13.掃描器14.超前搜索15.句柄16.語法制導翻譯17.規(guī)范句型18.素短語19.語法20.待用信息21.語義四、簡答題：1.寫一個文法 G, 使其語言

31、為 不以 0 開頭的偶數(shù)集。2.已知文法 G(S)及相應翻譯方案SaAbprint “1”Saprint “2”AASprint “3”Acprint “4”輸入 acab, 輸出是什么？3. 已知文法 G(S) SbAaA(B | a BAa)寫出句子 b(aa)b 的規(guī)范歸約過程。4. 考慮下面的程序：procedure p(x, y, z)； beginy:=x+y;z:=z*z; end beginA:=2;B:=A*2; P(A, A, B); Print A, Bend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 A, B 的值是什么? 5.文法 G(S)SdAB

32、AaA| aBBb| 描述的語言是什么？6.證明文法 G(S)SSaS| 是二義性的。7.已知文法 G(S)SBA ABS| d BaA| bS | c的預測分析表如下abcd#SSBASBASBAAABSABSABSAdBBaABbSBc給出句子 adccd 的分析過程。8.寫一個文法 G, 使其語言為 L(G)=albmclanbn| l>=0, m>=1, n>=2 9.已知文法 G(S):Sa| (T)TT,S|S的優(yōu)先關(guān)系表如下：關(guān)系a(),a-.>.>(<.<.=.<.)-.>.>,<.<.>.>請

33、計算出該優(yōu)先關(guān)系表所對應的優(yōu)先函數(shù)表。10.何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？11.目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？12.一字母表=a, b，試寫出上所有以 a 為首的字組成的正規(guī)集相對應的正規(guī)式。13.基本的優(yōu)化方法有哪幾種？14.寫一個文法 G, 使其語言為 L(G)=abncn| n0 15.考慮下面的程序：procedure p(x, y, z); beginy:=y+z;z:=y*z+xend; begina:=2;b:=3;p(a+b, b, a); print aend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 a 的值是

34、什么? 16.寫出表達式 ab*(c-d)/e 的逆波蘭式和三元序列。17.證明文法 G(A)AAA | (A)| 是二義性的。18.令=a,b，則正規(guī)式 a*b|b*a 表示的正規(guī)集是什么？19.何謂 DISPLAY 表？其作用是什么？20.考慮下面的程序：procedure p(x, y, z)； beginy:=y+2;z:=z+x; end begina:=5;b:=2;p(a+b, a-b, a); print aend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 a 的值是什么? 21.寫一個文法 G, 使其語言為 L(G)=anbncm| n>0 為奇數(shù)，

35、 m>0 為偶數(shù) 22.寫出表達式 a:=(b+c)*e+(b+c)/f 的逆波蘭式和三元序列。23.一個文法 G 別是 LL(1)文法的充要條件是什么？24.已知文法 GS SS*aF | aF | *aF F+aF | +a消除文法左遞歸和提公共左因子。25.符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？五、計算題：1.設(shè)文法 G(S): S | a | (T) TT,S | S 消除左遞歸； 構(gòu)造相應的 FIRST 和 FOLLOW 集合； 構(gòu)造預測分析表2.語句 if E then S(1) 改寫文法，使之適合語法制導翻譯；(2) 寫出改寫后產(chǎn)生式的語義動作。3.設(shè)文法 G（

36、S）：S(T) | a TT+S | S(1）計算 FIRSTVT 和 LASTVT；（2）構(gòu)造優(yōu)先關(guān)系表。4.設(shè)某語言的 for 語句的形式為for i:E(1) to E(2) do S其語義解釋為i:E(1) LIMIT:E(2)again: if iLIMIT then BeginS;i:i1 goto again End;（1）寫出適合語法制導翻譯的產(chǎn)生式；（2）寫出每個產(chǎn)生式對應的語義動作。5.把語句while a<10 doif c>0 then a:=a+1 else a:=a*3-1;翻譯成四元式序列。6.設(shè)有基本塊D:=A-CE:=A*CF:=D*ES:=2T:

37、=A-CQ:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假設(shè)基本塊出口時只有 M 還被引用，請寫出優(yōu)化后的四元序列。7.已知文法 G(S)Sa | | (T) TT,S | S(1) 給出句子(a,(a,a)的最左推導；(2) 給出句型(T,S),a)的短語, 直接短語，句柄。8.對于 C 語言 do S while E 語句(1)改寫文法，使之適合語法制導翻譯；(2)寫出改寫后產(chǎn)生式的語義動作。9.已知文法 G(S) SaAcBe AAb| b Bd(1)給出句子 abbcde 的最左推導及畫出語法樹；(2)給出句型 aAbcde 的短語、素短語。10.設(shè)文法 G(S):

38、 S(T) | aS | a TT,S | S消除左遞歸和提公共左因子；構(gòu)造相應的 FIRST 和 FOLLOW 集合；構(gòu)造預測分析表。11.把語句 if X>0 Y<0then while X>0 do X:=A*3 else Y:=B+3;翻譯成四元式序列。12.已知文法 G(S)EE+T | TTT*F| F F(E)| i(1) 給出句型 (i+i)*i+i 的最左推導及畫出語法樹；(2) 給出句型 (E+T)*i+F 的短語，素短語和最左素短語。13.設(shè)文法 G（S）：ST | ST TU |TU Ui |-U（1）計算 FIRSTVT 和 LASTVT；（2）構(gòu)造

39、優(yōu)先關(guān)系表。參考答案一、是非題：1.×2.×3.×4.5.6.×7.×8.×9.10.×11.×12.13.×14.15.16.17.×18.19.20.×21.22.二、填空題：1.(最右推導）2.(詞法分析），（語法分析），（中間代碼生成），（代碼優(yōu)化），（目標代碼生成）3.(二義性的）4.(執(zhí)行性），（說明性）5.(單詞符號），（語法單位）。6.(源程序），（單詞符號）7.(類型、種屬、所占單元大小、地址）8.(現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址) 9.(句柄）10.(

40、棧式)，（堆式）11.(類型)，（作用域）12.(傳地址），（傳值），（傳名）13.(局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）14.(自上而下），（自下而上）15.(分析表），（符號棧）16.(傳地址），（傳值），（傳名）17.(初），（終）18.(局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）19.(語法），（語義）20.(句柄） 21.(LL(1) 文法）22.(靜態(tài)），（動態(tài)）23.(二義性文法）24.(規(guī)范推導），（規(guī)范）25.(自上而下），（自下而上）26.(句子)27.(從開始符號出發(fā)，向下推導，推出句子）28.(單詞符號），（語法單位）29.(局部優(yōu)化）30.(分析表），（符號棧）31.(

41、上下文無關(guān)文法），（正規(guī)）32.(指令訪問主存次數(shù)加 1）33.(最左素短語）三、名詞解釋題：1.局部優(yōu)化-局限于基本塊范圍的優(yōu)化稱。2.二義性文法-如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義性文法。 3.DISPLAY 表-過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動記錄的起始地址。4.詞法分析器-執(zhí)行詞法分析的程序。5.最左推導-任何一步=>都是對中的最右非終結(jié)符替換。6.語法-一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7.文法-描述語言的語法結(jié)構(gòu)的形式規(guī)則。8.基本塊-指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是其中的第一個語句，出口就是其中的最后一個語句。9.語法制導翻譯-在語法分析過程中，根據(jù)每個產(chǎn)生式所對應的語義子程序進行翻譯的辦法叫做語法制導翻譯。10.短語-令 G 是一個文法，S 劃文法的開始符號，假定是文法 G 的一個句型，如果有 SA且A，則稱是句型相對非終結(jié)符 A 的短語。第 1 頁 共 25 頁11.待用信息-如果在一個基本塊中，四元式 i 對 A 定值，四元式 j 要引用 A 值，而從 i 到 j 之間沒有 A 的