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

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

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

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

4、C. 條件語(yǔ)句D. 循環(huán)語(yǔ)句三 解答題（共 60 分）得分1 （共 15 分）已知文法 GE:EETE|（E）|iT*|+（1） 將文法 G 改造成 LL（1）文法；（5 分）（2） 構(gòu)造文法 G 中每個(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） 畫出該句子的語(yǔ)法推導(dǎo)樹。（4 分）3 （共 8 分）在一個(gè)移入-規(guī)約分析過程中采用以下的語(yǔ)法制導(dǎo)翻譯模式，在按一個(gè)產(chǎn)生式規(guī)約時(shí)，立即

5、執(zhí)行括號(hào)中的動(dòng)作。AaBprint “0”；Acprint “1”；BAbprint “2”；（1） 當(dāng)分析器的輸入為 aacbb 時(shí)，打印的字符串是什么？（3 分）（2） 寫出分析過程。（5 分）4 （10 分）翻譯循環(huán)語(yǔ)句 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) 計(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下列

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

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

10、print “3”BAa)print “4”（3） 當(dāng)輸入序列為 b(aa)a)a)b 時(shí)，打印的字符串是什么？（4） 寫出移入-規(guī)約分析過程。5 （12 分）翻譯循環(huán)語(yǔ)句 while (x>y) 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.

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) 棧式動(dòng)態(tài)存儲(chǔ)分配(2) 堆

14、式動(dòng)態(tài)存儲(chǔ)分配(3) 左(4) 語(yǔ)法分析(5) 目標(biāo)代碼生成(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,選對(duì)一個(gè)得 1 分且不超過滿分，選錯(cuò)一個(gè)扣一分，扣完為止。8.BCD，選對(duì)一個(gè)得 1 分且不超過滿分，選錯(cuò)一個(gè)扣一分，扣完為止。二、解答題1（1）文法存在左遞歸，消除左遞歸后的文法為：E(E)E|i E（2 分）ETEE| （2 分）T*|+（1 分）（2）(5 分)沒考慮#扣 0.5 分，其它錯(cuò)或少寫一個(gè)扣 0.5 分FIRST(

15、E)=(,iFIRST(E)=*,+, FIRST(T)=*,+FOLLOW(E)=),*,+,#FOWLLOW(E)= ),*,+,# FOLLOW(T)=(,i（3）每錯(cuò)一個(gè)扣 0.5 分，全錯(cuò)或不寫不得分，扣完為止，共 5 分()i*+#EE(E)EEiEEE ETEEETEEE E E TT*T+2（1）規(guī)范推導(dǎo)過程如下。寫錯(cuò)推導(dǎo)符號(hào)扣 0.5 分,錯(cuò)寫或少寫一步推導(dǎo)扣 0.5 分，扣完為止，最左推導(dǎo)扣 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）中加下劃線的部分是句柄，標(biāo)識(shí)如（1）。每少寫一個(gè)句柄扣 0.5 分，扣完為止，共 4 分。（3）每少寫步扣 0.5 分，扣完為止，共 4 分。SS( S )S( S )S( S ) S( S )S( S ) 3（1）打印的字符串是：12020（錯(cuò)一個(gè)扣 0.5 分，共 3 分）（2）歸約過程中錯(cuò)一步扣 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）少寫一個(gè)四元式扣 0.5 分，全錯(cuò)或不寫不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）少寫一個(gè)扣 1 分，全錯(cuò)或不寫不得分，共 5 分。FIRSTVT(S)=a,( FIRSTVT(T)=, a,( LASTVT(S)= a,) LASTVT(T)= a,), ,(2)優(yōu)先表如下。每錯(cuò)一個(gè)扣 0.5 分，全錯(cuò)或不寫不得分，扣完為止，共 3 分文法 GS沒有兩個(gè)非終結(jié)符相鄰的情況，且其優(yōu)先表中任一對(duì)終結(jié)符之間最多滿足、 三種關(guān)系中的一種，因此是 GS算符優(yōu)先文法。（2 分）可以不考慮終結(jié)符“#”。a(),#A(),#或者（3）優(yōu)先函數(shù)。可以不考慮終結(jié)符“#”。每錯(cuò)一個(gè)扣 0.5 分，全錯(cuò)或不寫不得分，扣完為止，共 5 分。a(),#f6626

19、62g777252或者a(),f44244g55523三、 填空題（每空 2 分，共 20 分）1 目標(biāo)程序 （target code）語(yǔ)法分析（syntax analyzer）代碼優(yōu)化器（codeoptimizer）代碼產(chǎn)生器（code generator）符號(hào)表管理（symbol tablemanager）2繼承屬性（inherited attribute）3局部?jī)?yōu)化（local optimization）4 四元式（quatriple）5 E+ * ( ) id四、單項(xiàng)選擇題（每題 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 分，錯(cuò)處扣 0.5 分，扣完為止2.（1）空白表格也可以填寫“錯(cuò)誤”字樣,共 4 分，錯(cuò)一個(gè)扣 0.5 分，扣完為止abc$(#)SSaBcSbABAAaAbAbBBbBB（2）共 6 分，其中判斷“baabbb 是該文法句子”為 2 分，其他錯(cuò)一個(gè)扣 0.5 分，扣完為止符號(hào)棧輸入串規(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 分，其他錯(cuò)一個(gè)扣 0.5 分，扣完為止+*i+><<*>><i>>(2) 共 4 分，錯(cuò)一個(gè)扣 0.5 分，扣完為止+*if244g1354（1）34242421，共 4 分，錯(cuò)一個(gè)扣 0.5 分（2）共 4 分，錯(cuò)一個(gè)扣 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 分，錯(cuò)一個(gè)序列扣 0.5 分，而錯(cuò)某點(diǎn)（某項(xiàng)）少于或等于 5 個(gè)扣 0.5 分帶注釋語(yǔ)法樹(略)三地址碼序列四元式序列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 分，錯(cuò)一個(gè)扣 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 (從這開始，下面的語(yǔ)句中的 R1 也可以全部變成 R2) ADD R1,R1,1 (OR INC R1)ST I,R1BR L1L2:7 共 6 分，基本塊劃分和流圖各為 3 分，錯(cuò)一處扣 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 分，錯(cuò)一項(xiàng)扣 1 分，扣完為止（2）共 4 分，錯(cuò)一項(xiàng)扣 1 分，扣完為止 t1=b*ct2=b*d t3=t1-t2t4=i+1 (or t4=i) bt4=t3一、判斷題：1.一個(gè)上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。()2.一個(gè)句型的直接短語(yǔ)是唯一的。()3.已經(jīng)證明文法的二義性是可判定的。（）4.每個(gè)基本塊可用一個(gè) DAG 表示。（）5.每個(gè)過程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。（）6.2 型文法一定是 3 型文法。（）7.一個(gè)句型一定句子。(

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

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

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

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

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

31、為 不以 0 開頭的偶數(shù)集。2.已知文法 G(S)及相應(yīng)翻譯方案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ù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 A, B 的值是什么? 5.文法 G(S)SdAB

32、AaA| aBBb| 描述的語(yǔ)言是什么？6.證明文法 G(S)SSaS| 是二義性的。7.已知文法 G(S)SBA ABS| d BaA| bS | c的預(yù)測(cè)分析表如下abcd#SSBASBASBAAABSABSABSAdBBaABbSBc給出句子 adccd 的分析過程。8.寫一個(gè)文法 G, 使其語(yǔ)言為 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-.>.>(<.<.=.<.)-.>.>,<.<.>.>請(qǐng)

33、計(jì)算出該優(yōu)先關(guān)系表所對(duì)應(yīng)的優(yōu)先函數(shù)表。10.何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？11.目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問題？12.一字母表=a, b，試寫出上所有以 a 為首的字組成的正規(guī)集相對(duì)應(yīng)的正規(guī)式。13.基本的優(yōu)化方法有哪幾種？14.寫一個(gè)文法 G, 使其語(yǔ)言為 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ù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 a 的值是

34、什么? 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 aend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 a 的值是什么? 21.寫一個(gè)文法 G, 使其語(yǔ)言為 L(G)=anbncm| n>0 為奇數(shù)，

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

36、S）：S(T) | a TT+S | S(1）計(jì)算 FIRSTVT 和 LASTVT；（2）構(gòu)造優(yōu)先關(guān)系表。4.設(shè)某語(yǔ)言的 for 語(yǔ)句的形式為for i:E(1) to E(2) do S其語(yǔ)義解釋為i:E(1) LIMIT:E(2)again: if iLIMIT then BeginS;i:i1 goto again End;（1）寫出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式；（2）寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。5.把語(yǔ)句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è)基本塊出口時(shí)只有 M 還被引用，請(qǐng)寫出優(yōu)化后的四元序列。7.已知文法 G(S)Sa | | (T) TT,S | S(1) 給出句子(a,(a,a)的最左推導(dǎo)；(2) 給出句型(T,S),a)的短語(yǔ), 直接短語(yǔ)，句柄。8.對(duì)于 C 語(yǔ)言 do S while E 語(yǔ)句(1)改寫文法，使之適合語(yǔ)法制導(dǎo)翻譯；(2)寫出改寫后產(chǎn)生式的語(yǔ)義動(dòng)作。9.已知文法 G(S) SaAcBe AAb| b Bd(1)給出句子 abbcde 的最左推導(dǎo)及畫出語(yǔ)法樹；(2)給出句型 aAbcde 的短語(yǔ)、素短語(yǔ)。10.設(shè)文法 G(S):

38、 S(T) | aS | a TT,S | S消除左遞歸和提公共左因子；構(gòu)造相應(yīng)的 FIRST 和 FOLLOW 集合；構(gòu)造預(yù)測(cè)分析表。11.把語(yǔ)句 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 的最左推導(dǎo)及畫出語(yǔ)法樹；(2) 給出句型 (E+T)*i+F 的短語(yǔ)，素短語(yǔ)和最左素短語(yǔ)。13.設(shè)文法 G（S）：ST | ST TU |TU Ui |-U（1）計(jì)算 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.(最右推導(dǎo)）2.(詞法分析），（語(yǔ)法分析），（中間代碼生成），（代碼優(yōu)化），（目標(biāo)代碼生成）3.(二義性的）4.(執(zhí)行性），（說明性）5.(單詞符號(hào)），（語(yǔ)法單位）。6.(源程序），（單詞符號(hào)）7.(類型、種屬、所占單元大小、地址）8.(現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址) 9.(句柄）10.(

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

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