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

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表達(dá)式x+y*z/(a+b)的后綴式為 （7） 。5文法符號的屬性有綜合屬性和 （8）。6假設(shè)二位數(shù)組按行存放，而且每個元素占用一個存儲單元，則數(shù)組a1.15,1.20某個元素ai，j的地址計(jì)算公式為（9）。7局部優(yōu)化是局限于一個（10）范

2、圍內(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在通常的語法分析方法中，（ ）特別適用于表達(dá)式的分析。A 算符優(yōu)先分析法 B LR分

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

4、件語句 D. 循環(huán)語句得分三 解答題（共60分）1 （共15分）已知文法GE: EETE|（E）|i T*|+（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ī)范推導(dǎo)過程；（4分）（2） 指出每步推導(dǎo)所得句型的句柄；（4分）（3） 畫出該句子的語法推導(dǎo)樹。（4分）3 （共8分）在一個移入-規(guī)約分析過程中采用以下的語法制導(dǎo)翻譯模式，在按一個產(chǎn)生式規(guī)約時，立即執(zhí)行括號中的動作。 AaB print “0”； Ac

5、 print “1”； BAb print “2”；（1） 當(dāng)分析器的輸入為aacbb時，打印的字符串是什么？（3分）（2） 寫出分析過程。（5分）4 （10分）翻譯循環(huán)語句 while (ad) 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(S1.nextlist,M1,.quad); backpatc

6、h(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(j,-,-,0)(7) SL:=E em

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

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

9、分） 已知文法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ī)約分析過程中采用以下的語法制導(dǎo)翻譯模式，在按一個產(chǎn)生式規(guī)約時，立即執(zhí)行括號中的動作。 SbAb print “1” A(B print “2” Aa print “3”BAa) print “4”（3） 當(dāng)輸入序列為b

10、(aa)a)a)b時，打印的字符串是什么？（4） 寫出移入-規(guī)約分析過程。5 （12分）翻譯循環(huán)語句 while (xy) do if (a=b) then x:=2*y+a 。要求：給出加注釋的分析樹、三地址碼序列及相應(yīng)的四元式序列。參考以下部分翻譯模式：(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.nextlist,M1,.quad); backpatch(E.truelist,

11、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(j,-,-,0)(7) SL:=E emit(:=,E.place

12、,-,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 xy goto L2 Z=s+ai I=i+1Goto L1 L2:7 (6分) Give out the all basic blo

13、cks of the following program fragment and construct the relevant flow graph(DAG). read C A=0 B=1 L4: A=A+B if BC 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) 棧式動態(tài)存儲分配(2) 堆式動態(tài)存儲分配(3) 左(4) 語法分析(5) 目標(biāo)代碼

14、生成(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分FIRST(E)=(,i FIRST(E)=*,+, FIRST(T)=*,+ FO

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

16、：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=103S ad x E5.p=y + E6.p=z y z（2）少寫一個四元式扣0.5分，全錯或不寫不得分，回填錯誤扣0.5分，共5分。四元式序列為： 5（1）少寫一個扣1分，全錯或不寫不得分，共5分。FIRSTVT(S)=a,(FIRSTVT(T)=, a,(LASTVT(S)= a,)LASTVT(T)= a,), ,(2)優(yōu)先表如下。每錯

17、一個扣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(),#f662662g777252或者a(),f44244g55523三、 填空題（每空2分，共20分）1目標(biāo)程序 （target code） 語法分析（syntax analyzer） 代碼優(yōu)化器（code optimizer） 代碼產(chǎn)生器（code generator）

18、符號表管理（symbol table manager）2 繼承屬性（inherited attribute）3 局部優(yōu)化（local optimization）4 四元式（quatriple）5 E + * ( ) id四、 單項(xiàng)選擇題（每題2分，共10分）1.B 2.D 3.B 4.D 5.C五、 解答題（共70分）1（1） L(G)=0m1m|M1 共2分，寫成扣1分（2） S=0S1=00S11=000111，共3分， =寫成-扣1分（3） 共3分，錯處扣0.5分，扣完為止2.（1）空白表格也可以填寫“錯誤”字樣,共4分，錯一個扣0.5分，扣完為止abc$(#)SSaBcSbABAAaA

19、bAbBBbBB （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$b$SbABAaAbAaAbAbBsuccess3.(1) 共6分，其中判斷“該文法為算符優(yōu)先文法”為2分，其他錯一個扣0.5分，扣完為止+*i+(2) 共4分，錯一個扣0.5分，扣完為止+*if244g1354（1）34242421 ，共4分，錯一個扣0.5分（2）共4分，錯一個扣0.5分，扣

20、完為止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)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）re

21、duce, A(B shiftshiftreduce, BAa）reduce, A(Bshiftshiftreduce, BAa）reduce, A(Bshiftreduce, SbAbaccept5 共12分，其中帶注釋的分析樹、三地址碼序列和四元式序列分別為4分，錯一個序列扣0.5分，而錯某點(diǎn)（某項(xiàng)）少于或等于5個扣0.5分帶注釋語法樹(略)三地址碼序列 四元式序列M1: if (xy) goto M2 100 (j, x,y,102) goto M4 101 (j,-,-,108)M2: if (a=b) goto M3 102 (j=,a,b,104) goto M1 103 (j,-

22、,-,100)M3: t1=2*y 104 (*,2,y,t1) t2=t1+a 105 (+,t1,a,t2) x=t2 106 (=,t2,-,x) goto M1 107 (j,-,-,100)M4: 108 (-,-,-,-)6共8分，錯一個扣0.5分，扣完為止LD R1,0ST S,R1ST I,R1L1: 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

23、)ST I,R1BR L1L2:7 共6分，基本塊劃分和流圖各為3分，錯一處扣 1分，扣完為止B4B3B2B1read cA=0B=1L4: A=A+BIf BC goto L2 (OR B4)B=B+1Goto L4 (OR B2)L2: write A 8. （1）共4分，錯一項(xiàng)扣1分，扣完為止（2）共4分，錯一項(xiàng)扣1分，扣完為止t1=b*ct2=b*dt3=t1-t2t4=i+1 (or t4=i)bt4=t3一、判斷題：1.一個上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。 ( )2.一個句型的直接短語是唯一的。 ( )3.已經(jīng)證明文法的二義性是可判定的。 （ ）4.每個基本塊可用一

24、個DAG表示。 （ ）5.每個過程的活動記錄的體積在編譯時可靜態(tài)確定。 （ ）6.2型文法一定是3型文法。 （ ）7.一個句型一定句子。 ( )8.算符優(yōu)先分析法每次都是對句柄進(jìn)行歸約。 ( )9.采用三元式實(shí)現(xiàn)三地址代碼時，不利于對中間代碼進(jìn)行優(yōu)化。 （ ）10.編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。 ( )11.一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( )12.目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 ( )13.遞歸下降分析法是一種自下而上分析法。 ( )14.并不是每個文法都能改寫成LL(1)文法。 ( )15.每個基本塊只有一個入口和一個出口。 ( )16

25、.一個LL(1)文法一定是無二義的。 ( )17.逆波蘭法表示的表達(dá)試亦稱前綴式。 ( )18.目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 ( )19.正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 ( )20.一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( )21.3型文法一定是2型文法。 ( )22.如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則文法是二義性的。 ( )二、填空題：1.( )稱為規(guī)范推導(dǎo)。2.編譯過程可分為 （ ） ，（ ），（ ），（ ）和（ ）五個階段。3.如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是（ ）。 4.從功能上說，程序語言的語句大體

26、可分為（ ）語句和（ ）語句兩大類。5.語法分析器的輸入是（ ），其輸出是（ ）。6.掃描器的任務(wù)是從（ ）中識別出一個個（ ）。7.符號表中的信息欄中登記了每個名字的有關(guān)的性質(zhì)，如（ ）等等。8.一個過程相應(yīng)的DISPLAY表的內(nèi)容為（ ）。9.一個句型的最左直接短語稱為句型的（ ）。10.常用的兩種動態(tài)存貯分配辦法是（ ）動態(tài)分配和（ ）動態(tài)分配。11.一個名字的屬性包括( )和( )。12.常用的參數(shù)傳遞方式有（ ），（ ）和（ ）。13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（ ），（ ）和（ ）三個級別。14.語法分析的方法大致可分為兩類，一類是（ ）分析法，另一類是（ ）分析法。

27、15.預(yù)測分析程序是使用一張（ ）和一個（ ）進(jìn)行聯(lián)合控制的。16.常用的參數(shù)傳遞方式有（ ），（ ）和（ ）。17.一張轉(zhuǎn)換圖只包含有限個狀態(tài),其中有一個被認(rèn)為是（ ）態(tài);而且實(shí)際上至少要有一個（ ）態(tài)。18.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（ ），（ ）和（ ）三個級別。19.語法分析是依據(jù)語言的（ ）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語言的（ ）規(guī)則進(jìn)行的。20.一個句型的最左直接短語稱為句型的（ ）。21.一個文法G，若它的預(yù)測分析表M不含多重定義，則該文法是（ ）文法。22.對于數(shù)據(jù)空間的存貯分配， FORTRAN采用( )策略， PASCAL采用( )策略。23.如果一個文法存在

28、某個句子對應(yīng)兩棵不同的語法樹， 則稱這個文法是( )。24.最右推導(dǎo)亦稱為（ ），由此得到的句型稱為（ ）句型。25.語法分析的方法大致可分為兩類，一類是（ ）分析法，另一類是（ ）分析法。26.對于文法G，僅含終結(jié)符號的句型稱為 ( )。27.所謂自上而下分析法是指（ ）。28.語法分析器的輸入是（ ），其輸出是（ ）。29.局限于基本塊范圍的優(yōu)化稱（ ）。30.預(yù)測分析程序是使用一張（ ）和一個（ ）進(jìn)行聯(lián)合控制的。31.2型文法又稱為（ ）文法；3型文法又稱為（ ）文法。32.每條指令的執(zhí)行代價定義為（ ）。33.算符優(yōu)先分析法每次都是對（ ）進(jìn)行歸約。三、名詞解釋題：1.局部優(yōu)化2.二

29、義性文法3.DISPLAY表4.詞法分析器5.最左推導(dǎo)6.語法7.文法8.基本塊9.語法制導(dǎo)翻譯10.短語11.待用信息12.規(guī)范句型13.掃描器14.超前搜索15.句柄16.語法制導(dǎo)翻譯17.規(guī)范句型18.素短語19.語法20.待用信息21.語義四、簡答題：1.寫一個文法G, 使其語言為 不以0開頭的偶數(shù)集。2.已知文法G(S)及相應(yīng)翻譯方案SaAb print “1”Sa print “2”AAS print “3”Ac print “4”輸入acab, 輸出是什么？3. 已知文法G(S)SbAaA(B | aBAa)寫出句子b(aa)b的規(guī)范歸約過程。4. 考慮下面的程序：procedu

30、re p(x, y, z)；beginy:=x+y;z:=z*z; end beginA:=2;B:=A*2;P(A, A, B);Print A, B end.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 A, B的值是什么? 5.文法G(S)SdABAaA| aBBb| 描述的語言是什么？6.證明文法G(S) SSaS| 是二義性的。7.已知文法G(S) SBAABS| dBaA| bS | c的預(yù)測分析表如下 a b c d # SSBASBASBA AABSABSABSAd BBaA BbS Bc給出句子 adccd 的分析過程。8.寫一個文法G, 使其語言為 L(G)

31、=albmclanbn| l=0, m=1, n=2 9.已知文法G(S):Sa| (T)TT,S|S的優(yōu)先關(guān)系表如下：關(guān)系a(),a-.(.=.,.請計(jì)算出該優(yōu)先關(guān)系表所對應(yīng)的優(yōu)先函數(shù)表。10.何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？11.目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時通常應(yīng)考慮哪幾個問題？12.一字母表=a, b，試寫出上所有以a為首的字組成的正規(guī)集相對應(yīng)的正規(guī)式。13.基本的優(yōu)化方法有哪幾種？14.寫一個文法G, 使其語言為 L(G)=abncn| n015.考慮下面的程序：procedure p(x, y, z);begin y:=y+z; z:=y*z+xend;begi

32、n a:=2; b:=3; p(a+b, b, a); print aend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 a的值是什么? 16.寫出表達(dá)式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 a end.試問，若參數(shù)傳遞的方式分別采

33、用傳地址和傳值時，程序執(zhí)行后輸出 a的值是什么? 21.寫一個文法G, 使其語言為 L(G)=anbncm| n0為奇數(shù)， m0為偶數(shù)22.寫出表達(dá)式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。23.一個文法G別是LL(1)文法的充要條件是什么？24.已知文法GSSS*aF | aF | *aFF+aF | +a消除文法左遞歸和提公共左因子。25.符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？五、計(jì)算題：1.設(shè)文法G(S): S | a | (T) TT,S | S 消除左遞歸； 構(gòu)造相應(yīng)的FIRST和FOLLOW集合； 構(gòu)造預(yù)測分析表 2.語句 if E then S(1)

34、 改寫文法，使之適合語法制導(dǎo)翻譯； (2) 寫出改寫后產(chǎn)生式的語義動作。 3.設(shè)文法G（S）：S(T) | aTT+S | S(1）計(jì)算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 thenBeginS;i:i1goto againEnd;（1）寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；（2）寫出每個產(chǎn)生式對應(yīng)的語義動作。5.把語句while a0 then a:=a+1else a:=a*3-1;翻譯成四元式序列。6.設(shè)有基本塊D:=A-

35、CE:=A*CF:=D*ES:=2T:=A-C Q:=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)的最左推導(dǎo)；(2) 給出句型(T,S),a)的短語, 直接短語，句柄。8.對于 C 語言do S while E語句 (1)改寫文法，使之適合語法制導(dǎo)翻譯； (2)寫出改寫后產(chǎn)生式的語義動作。9.已知文法G(S) SaAcBe AAb| b Bd(1)給出句子abbcde的最左推導(dǎo)及畫出語法樹；(2)給出句型aAbcde的短語、素短語。

36、10.設(shè)文法G(S): S(T) | aS | a TT,S | S 消除左遞歸和提公共左因子； 構(gòu)造相應(yīng)的FIRST和FOLLOW集合； 構(gòu)造預(yù)測分析表。11.把語句 if X0 Y0 do X:=A*3 else Y:=B+3;翻譯成四元式序列。12.已知文法G(S) EE+T | T TT*F| F F(E)| i (1) 給出句型 (i+i)*i+i的最左推導(dǎo)及畫出語法樹； (2) 給出句型 (E+T)*i+F 的短語，素短語和最左素短語。 13.設(shè)文法G（S）：ST | STTU |TUUi |-U（1）計(jì)算FIRSTVT 和LASTVT； （2）構(gòu)造優(yōu)先關(guān)系表。 參考答案一、是非題

37、：1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.二、填空題：1.(最右推導(dǎo)）2.(詞法分析），（語法分析），（中間代碼生成），（代碼優(yōu)化），（目標(biāo)代碼生成）3.(二義性的）4.(執(zhí)行性），（說明性）5.(單詞符號），（語法單位）。6.(源程序），（單詞符號）7.(類型、種屬、所占單元大小、地址）8.(現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址)9.(句柄）10.(棧式)，（堆式）11.(類型)，（作用域）12.(傳地址），（傳值），（傳名）13.(局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）

38、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ī)范推導(dǎo)），（規(guī)范）25.(自上而下），（自下而上）26.(句子)27.(從開始符號出發(fā)，向下推導(dǎo)，推出句子）28.(單詞符號），（語法單位）29.(局部優(yōu)化）30.(分析表），（符號棧）31.(上下文無關(guān)文法），（正規(guī)）32.(指令訪問主存次數(shù)加1）33.(最左素短語）三、名詞解釋題： 1.局部優(yōu)化-局限于基本塊范圍的

39、優(yōu)化稱。2.二義性文法-如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義性文法。3.DISPLAY表-過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動記錄的起始地址。4.詞法分析器-執(zhí)行詞法分析的程序。5.最左推導(dǎo)-任何一步=都是對中的最右非終結(jié)符替換。6.語法-一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7.文法-描述語言的語法結(jié)構(gòu)的形式規(guī)則。8.基本塊-指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是其中的第一個語句，出口就是其中的最后一個語句。9.語法制導(dǎo)翻譯-在語法分析過程中，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序進(jìn)行翻譯的辦法叫做語法制導(dǎo)翻譯。10.短語-令G是一個文法，S劃文法的開始符號，假定是文法G的一個句型，如果有SA且A，則稱是句型相對非終結(jié)符A的短語。11.待用信息-如果在一個基本塊中，四元式i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。12.規(guī)范句型-由規(guī)范推導(dǎo)所得到的句型。13.掃描器-執(zhí)行詞法分析的程序。14.超前搜索-在詞法分析過程中，有