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

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

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

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

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

5、共 即執(zhí)行括號(hào)中的動(dòng)作。 0”； AaB print “ 1”；c print “ A ”；Ab print “2 B 分）時(shí)，打印的字符串是什么？（31） 當(dāng)分析器的輸入為aacbb（ 分）5 寫(xiě)出分析過(guò)程。（）（2。要求：給出加注釋的分析樹(shù)及四分）翻譯循環(huán)語(yǔ)句10 while (ad) then x:=y+z 4 （ 元式序列。 參考以下部分翻譯模式： backpatch(E.truelist,M.quad); (1) Sif E then M S1 .nextlist) S.nextlist:=merge(E.falselist,S1 . . (2) Swhile M E do M S

6、backpatch(S.nextlist,M.quad); 1,1121 backpatch(E.truelist,M.quad); 2, S.nextlist:=E.falselist emit (j,-,-,M .quad) 1(3) SA S.nextlist:=makelist() (4) LS L.nextlist:=S.nextlist (5) M M.quad:=nextquad (6) Eidrelop id E.truelist:=makelist(nextquad); 21 e.falselist:=makelist(nextquad+1); emit(jrelop.op,

7、id.place ,id.place,); 021) emit(j,-,-,0L:=E emit(:=,E.place,-,L.place) (7) S E.place:=newtemp; E+E(8) E21.place,E.place,) emit(+,E.place,E21 GS：5 （共15分）設(shè)有表格構(gòu)造文法|(T) a| ST,S|S T 5LASTVT集。（分）計(jì)算文法(1) GS的FIRSTVT集和 （5分）GS(2) 構(gòu)造GS的優(yōu)先關(guān)系表，并判斷是否為算符優(yōu)先文法。 5分）計(jì)算(3) GS的優(yōu)先函數(shù)。（ 得分 分）分，共10（每題二 單項(xiàng)選擇題2 I1|I0|Ia|Ic|a|

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

9、 ）。 提高編譯程序的運(yùn)行速度 節(jié)省編譯程序的存儲(chǔ)空間 提高目標(biāo)程序的運(yùn)行速度 為運(yùn)行階段的存儲(chǔ)分配做準(zhǔn)備 可選項(xiàng)有： A. B. C. D. 得分GS: 已知文法分） （2. 10 aBc|bAB SaAb|b A b|B 1）分析表； 構(gòu)造其LL（4） 。baabbb 判斷符號(hào)串是否為該文法的句子（寫(xiě)出含有符號(hào)棧、輸入串和規(guī)則的分析過(guò)程）（5） 為：) 已知文法G3. (10分E+T|T ET*P|P Ti P ，并指出此文法是否為算符優(yōu)先文法。構(gòu)造該文法的優(yōu)先關(guān)系表（不考慮語(yǔ)句括號(hào) #）（1） G的優(yōu)先函數(shù)表。 （2）構(gòu)造文法規(guī)約分析過(guò)程中采用以下的語(yǔ)法制導(dǎo)翻譯模式，在按一個(gè)產(chǎn)生式規(guī)約時(shí)

10、，立即執(zhí)-分）在一個(gè)移入（4 8 行括號(hào)中的動(dòng)作。. . SbAb print “1” A(B print “2” Aa print “3” BAa) print “4” （3） 當(dāng)輸入序列為b(aa)a)a)b時(shí)，打印的字符串是什么？ （4） 寫(xiě)出移入-規(guī)約分析過(guò)程。 5 （12分）翻譯循環(huán)語(yǔ)句 while (xy) do if (a=b) then x:=2*y+a 。要求：給出加注釋的分析樹(shù)、三地址碼序列及相應(yīng)的四元式序列。 參考以下部分翻譯模式： (1) Sif E then M S backpatch(E.truelist,M.quad); 1 S.nextlist:=merge(E

11、.falselist,S.nextlist) 1 (2) Swhile M E do M S backpatch(S.nextlist,M.quad); 1,1211 backpatch(E.truelist,M.quad); 2, S.nextlist:=E.falselist emit (j,-,-,M .quad) 1(3) SA S.nextlist:=makelist() (4) LS L.nextlist:=S.nextlist (5) M M.quad:=nextquad (6) Eidrelop id E.truelist:=makelist(nextquad); 21 e.f

12、alselist:=makelist(nextquad+1); emit(jrelop.op,id.place , id.place,0); 21 emit(j,-,-,0) (7) SL:=E emit(:=,E.place,-,L.place) (8) EE+E E.place:=newtemp; 21 emit(+,E.place,E.place,E.place,) 216. (8分) Generate assembly code for the following sequence assuming that x,y and z are in memory locations(noti

13、cing only two registers R1 and R2). S=0 I=0 L1: if xy goto L2 . . Z=s+ai I=i+1 Goto L1 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 BC goto L2 B=B+1 goto L4 L2: write A 8. (8分)Translate the assignme

14、nt statement bi=b*c-b*d into (1) A syntax tree. (2) Three address instructions. 答案： (1) 棧式動(dòng)態(tài)存儲(chǔ)分配 (2) 堆式動(dòng)態(tài)存儲(chǔ)分配 (3) 左 (4) 語(yǔ)法分析 (5) 目標(biāo)代碼生成 (6) 表格管理 (7) xyz*ab+/+ (8) 繼承屬性 (9) a+(i-1)*20+j-1 (10) 基本塊. . 選擇題（每問(wèn)2分，共20一、分） 1.C B 2.D 3.B 4.A 5.D 6.A,C 7.BCD,。 分且不超過(guò)滿(mǎn)分，選錯(cuò)一個(gè)扣一分，扣完為止選對(duì)一個(gè)得18.BCD，。 分且不超過(guò)滿(mǎn)分，選錯(cuò)一個(gè)扣一

15、分，扣完為止選對(duì)一個(gè)得1二、 解答題 1（1）文法存在左遞歸，消除左遞歸后的文法為： E (E)E|i E（2分） ETEE| （2分） T*|+ （1分） （2）(5分)沒(méi)考慮#扣0.5分，其它錯(cuò)或少寫(xiě)一個(gè)扣0.5分 FIRST(E)=(,i FIRST(E)=*,+, FIRST(T)=*,+ FOLLOW(E)=),*,+,# FOWLLOW(E)= ),*,+,# FOLLOW(T)=(,i （3）每錯(cuò)一個(gè)扣0.5分，全錯(cuò)或不寫(xiě)不得分，扣完為止，共5分 E1.f=107 ( ) i * + # E E(E)E iE E E E ETEEE ETEE E E T * T+ T 2（1）規(guī)

16、范推導(dǎo)過(guò)程如下。寫(xiě)錯(cuò)推導(dǎo)符號(hào)扣0.5分,錯(cuò)寫(xiě)或少寫(xiě)一步推導(dǎo)扣0.5分，扣完為止，最左推導(dǎo)扣2分，共4分。 ?)()()?S(S(S)()()?S(S()()()()S?S)()S(S)()?S()()()?S(S()()?SS(S?S()?S ?()()()()()()()S(S(S(?)()()()? （2）（1）中加下劃線的部分是句柄，標(biāo)識(shí)如（1）。每少寫(xiě)一個(gè)句柄扣0.5分，扣完為止，共4分。 （3）每少寫(xiě)步扣0.5分，扣完為止，共4分。 S S ( S ) ) S ( S ) ) ( S ) S ) S ( S ) ) . S ( S ) ) . 分3）（錯(cuò)一個(gè)扣0.5分，共3（1）打印

17、的字符串是：12020 5分）歸約過(guò)程中錯(cuò)一步扣0.5分，扣完為止。（共（2） 5分。）每少寫(xiě)一步扣0.5分，扣完為止，共4（1S while M1.q=100 E1.t=102 do M2.q=102 S1 ad E6.p=z z y （2）少寫(xiě)一個(gè)四元式扣0.5分，全錯(cuò)或不寫(xiě)不得分，回填錯(cuò)誤扣0.5分，共5分。 四元式序列為： 100(j?,a,b,102)101(j,_,_,107)102(j?,c,d,104)103(j,_,_,106)104(?,y,z,T1)105(:?,T1,_,x)106(j,_,_,100) 5（1）少寫(xiě)一個(gè)扣1分，全錯(cuò)或不寫(xiě)不得分，共5分。 FIRSTVT

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

19、 6 6 2 6 6 2 g 7 7 7 2 5 2 或者 a ( ) , f 4 4 2 4 4 g 5 5 5 2 3 三、 填空題（每空2分，共20分） 1目標(biāo)程序 （target code） 語(yǔ)法分析（syntax analyzer） 代碼優(yōu)化器（code optimizer） 代碼產(chǎn)生器（code generator） 符號(hào)表管理（symbol table manager） 2 繼承屬性（inherited attribute） 3 局部?jī)?yōu)化（local optimization） 4 四元式（quatriple） 5 E + * ( ) id 四、 單項(xiàng)選擇題（每題2分，共10分）

20、 1.B 2.D 3.B 4.D 5.C 五、 解答題（共70分） mm1 共2分，11） L(G)=0|M寫(xiě)成扣1分 （1（2） S=0S1=00S11=000111，共3分， =寫(xiě)成-扣1分 . . （3） 共3分，錯(cuò)處扣0.5分，扣完為止 2.（1）空白表格也可以填寫(xiě)“錯(cuò)誤”字樣,共4分，錯(cuò)一個(gè)扣0.5分，扣完為止 a b c $(#) S SaBc bAB S A AaAb Ab B Bb B B （2）共6分，其中判斷“baabbb是該文法句子”為2分，其他錯(cuò)一個(gè)扣0.5分，扣完為止 符號(hào)棧 輸入串 規(guī)則 $S $BAb $BA $BbAa $BbA $BbbAa $BbbA $Bb

21、bb $Bbb $Bb $b $ baabbb$ baabbb$ aabbb$ aabbb$ abbb$ abbb$ bbb$ bbb$ bb$ b$ $ $ SbAB AaAb AaAb Ab B success 3.(1) 共6分，其中判斷“該文法為算符優(yōu)先文法”為2分，其他錯(cuò)一個(gè)扣0.5分，扣完為止 + * i + (2) 共4分，錯(cuò)一個(gè)扣0.5分，扣完為止 + * i f 2 4 4 g 1 3 5 4（1）34242421 ，共4分，錯(cuò)一個(gè)扣0.5分 （2）共4分，錯(cuò)一個(gè)扣0.5分，扣完為止 stack Input string action $ $b b(aa)a)a)b$ (aa

22、)a)a)b$ shift . . $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$ (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$ $ $ shift shift shift shift a reduce, Ashift shift ）

23、Aareduce, B(B reduce, Ashift shift Aa）reduce, B(B reduce, Ashift shift Aa）reduce, B(B reduce, Ashift bAb reduce, Saccept 分，而0.54分，錯(cuò)一個(gè)序列扣5 共12分，其中帶注釋的分析樹(shù)、三地址碼序列和四元式序列分別為 0.5分錯(cuò)某點(diǎn)（某項(xiàng)）少于或等于5個(gè)扣) 略(帶注釋語(yǔ)法樹(shù) 四元式序列三地址碼序列 M1: if (xy) goto M2 100 (j, x,y,102) goto M4 101 (j,-,-,108) M2: if (a=b) goto M3 102 (j=

24、,a,b,104) goto M1 103 (j,-,-,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 (-,-,-,-) 0.586共分，錯(cuò)一個(gè)扣分，扣完為止. . LD R1,0 ST S,R1 ST I,R1 L1: LD R1,X SUB R1,R1,Y (OR SUB R1,Y) BGTZ R1,L2 LD R2,a(R1) ADD R2,R2,S (OR ADD R2,S) ST Z,R2 LD R1,I (從這開(kāi)始

25、，下面的語(yǔ)句中的R1也可以全部變成R2) ADD R1,R1,1 (OR INC R1) ST I,R1 BR L1 L2: 1分，扣完為止3 7共6分，基本塊劃分和流圖各為分，錯(cuò)一處扣 read c B1 A=0 B=1 L4: A=A+B B2 If BC goto L2 (OR B4) B=B+1 B3 L4 (OR B2) Goto L2: write A B4 1（8. ）共1分，錯(cuò)一項(xiàng)扣4分，扣完為止 2（）共分，扣完為止1分，錯(cuò)一項(xiàng)扣4t1=b*c t2=b*d t3=t1-t2 t4=i+1 (or t4=i) . . bt4=t3 一、判斷題： 1.一個(gè)上下文無(wú)關(guān)文法的開(kāi)始符

26、，可以是終結(jié)符或非終結(jié)符。 ( ) 2.一個(gè)句型的直接短語(yǔ)是唯一的。 ( ) 3.已經(jīng)證明文法的二義性是可判定的。 （ ） 4.每個(gè)基本塊可用一個(gè)DAG表示。 （ ） 5.每個(gè)過(guò)程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。 （ ） 6.2型文法一定是3型文法。 （ ） 7.一個(gè)句型一定句子。 ( ) 8.算符優(yōu)先分析法每次都是對(duì)句柄進(jìn)行歸約。 ( ) 9.采用三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對(duì)中間代碼進(jìn)行優(yōu)化。 （ ） 10.編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。 ( ) 11.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( ) 12.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。 (

27、 ) 13.遞歸下降分析法是一種自下而上分析法。 ( ) 14.并不是每個(gè)文法都能改寫(xiě)成LL(1)文法。 ( ) 15.每個(gè)基本塊只有一個(gè)入口和一個(gè)出口。 ( ) 16.一個(gè)LL(1)文法一定是無(wú)二義的。 ( ) 17.逆波蘭法表示的表達(dá)試亦稱(chēng)前綴式。 ( ) 18.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。 ( ) 19.正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。 ( ) 20.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( ) 21.3型文法一定是2型文法。 ( ) 22.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則文法是二義性的。 ( ) 二、填空題： 1.( )稱(chēng)為規(guī)范

28、推導(dǎo)。 2.編譯過(guò)程可分為 （ ） ，（ ），（ ），（ ）和（ ）五個(gè)階段。 3.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是（ ）。 4.從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為（ ）語(yǔ)句和（ ）語(yǔ)句兩大類(lèi)。 5.語(yǔ)法分析器的輸入是（ ），其輸出是（ ）。 6.掃描器的任務(wù)是從（ ）中識(shí)別出一個(gè)個(gè)（ ）。 7.符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如（ ）等等。 8.一個(gè)過(guò)程相應(yīng)的DISPLAY表的內(nèi)容為（ ）。 9.一個(gè)句型的最左直接短語(yǔ)稱(chēng)為句型的（ ）。 10.常用的兩種動(dòng)態(tài)存貯分配辦法是（ ）動(dòng)態(tài)分配和（ ）動(dòng)態(tài)分配。 11.一個(gè)名字的屬性包括( )和( )。 1

29、2.常用的參數(shù)傳遞方式有（ ），（ ）和（ ）。 13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（ ），（ ）和（ ）三個(gè)級(jí)別。 14.語(yǔ)法分析的方法大致可分為兩類(lèi)，一類(lèi)是（ ）分析法，另一類(lèi)是（ ）分析法。 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)化分成為（ ），（ ）和（ ）三個(gè)級(jí)別。 19.語(yǔ)法分析是依據(jù)語(yǔ)言的（ ）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語(yǔ)言的（ ）規(guī)則進(jìn)行的。 20.一個(gè)句

30、型的最左直接短語(yǔ)稱(chēng)為句型的（ ）。 ）文法。不含多重定義，則該文法是（，若它的預(yù)測(cè)分析表一個(gè)文法21.GM . . 22.對(duì)于數(shù)據(jù)空間的存貯分配， FORTRAN采用( )策略， PASCAL采用( )策略。 23.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)， 則稱(chēng)這個(gè)文法是( )。 24.最右推導(dǎo)亦稱(chēng)為（ ），由此得到的句型稱(chēng)為（ ）句型。 25.語(yǔ)法分析的方法大致可分為兩類(lèi)，一類(lèi)是（ ）分析法，另一類(lèi)是（ ）分析法。 26.對(duì)于文法G，僅含終結(jié)符號(hào)的句型稱(chēng)為 ( )。 27.所謂自上而下分析法是指（ ）。 28.語(yǔ)法分析器的輸入是（ ），其輸出是（ ）。 。 ）29.局限于基本塊范圍的優(yōu)

31、化稱(chēng)（ 30.預(yù)測(cè)分析程序是使用一張（ ）和一個(gè)（ ）進(jìn)行聯(lián)合控制的。 31.2型文法又稱(chēng)為（ ）文法；3型文法又稱(chēng)為（ ）文法。 32.每條指令的執(zhí)行代價(jià)定義為（ 。） ）進(jìn)行歸約。33.算符優(yōu)先分析法每次都是對(duì)（ 三、名詞解釋題： 局部?jī)?yōu)化1. 二義性文法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.待用信息 語(yǔ)義21. 四、簡(jiǎn)答題： 開(kāi)頭的偶數(shù)集。使其語(yǔ)言為 不以0寫(xiě)一個(gè)文法

32、1.G, 2.已知文法G(S)及相應(yīng)翻譯方案 aAb print “1”S “2”Sa print 3”AAS print “ ”Ac print “4 輸入acab, 輸出是什么？G(S) 3. 已知文法bAa S(B | a AAa) B b(aa)b的規(guī)范歸約過(guò)程。寫(xiě)出句子 4. 考慮下面的程序： . . procedure p(x, y, z)； begin y:=x+y; z:=z*z; end begin A:=2; B:=A*2; P(A, A, B); Print A, B end. 試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 A, B的值是什么? 5.文法G

33、(S) SdAB AaA| a BBb| 描述的語(yǔ)言是什么？ 6.證明文法G(S) SSaS| 是二義性的。 7.已知文法G(S) SBA ABS| d BaA| bS | c 的預(yù)測(cè)分析表如下 a b c d # S SBA SBA SBA A ABS ABS ABS Ad B BaA BbS Bc 給出句子 adccd 的分析過(guò)程。 lmlnn8.寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 L(G)=abcab| l=0, m=1, n=2 9.已知文法G(S): Sa| (T) TT,S|S 的優(yōu)先關(guān)系表如下： ,關(guān)系a)( .-.-a .-).- .,0為奇數(shù)， m0為偶數(shù) 22.寫(xiě)出表達(dá)式a:=(b

34、+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) 改寫(xiě)文法，使之適合語(yǔ)法制導(dǎo)翻譯； (2) 寫(xiě)出改寫(xiě)后產(chǎn)生式的語(yǔ)義動(dòng)作。 3.設(shè)文法G（S）： S(T) | a TT+S | S (

35、1）計(jì)算FIRSTVT 和LASTVT； （2）構(gòu)造優(yōu)先關(guān)系表。 4.設(shè)某語(yǔ)言的for語(yǔ)句的形式為 (1)(2)for i:E to E do S 其語(yǔ)義解釋為 (1)i:E (2)LIMIT:E again: if iLIMIT then Begin S; i:i1 goto again End; （1）寫(xiě)出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式； （2）寫(xiě)出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。 5.把語(yǔ)句 while a0 then a:=a+1 else a:=a*3-1; 翻譯成四元式序列。 6.設(shè)有基本塊 D:=A-C E:=A*C F:=D*E S:=2 T:=A-C Q:=A*C G:=2*S J:=T

36、*Q K:=G*5 L:=K+J M:=L 假設(shè)基本塊出口時(shí)只有M還被引用，請(qǐng)寫(xiě)出優(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)改寫(xiě)文法，使之適合語(yǔ)法制導(dǎo)翻譯； (2)寫(xiě)出改寫(xiě)后產(chǎn)生式的語(yǔ)義動(dòng)作。 9.已知文法G(S) SaAcBe AAb| b . . Bd (1)給出句子abbcde的最左推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)； (2)給出句型aAbcde的短語(yǔ)、素短語(yǔ)。 10.設(shè)文法G(S): S(T) | aS |

37、 a TT,S | S 消除左遞歸和提公共左因子； 構(gòu)造相應(yīng)的FIRST和FOLLOW集合； 構(gòu)造預(yù)測(cè)分析表。 11.把語(yǔ)句 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)及畫(huà)出語(yǔ)法樹(shù)； (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)造優(yōu)先關(guān)系表。 . . 參考答案 一、是非題： 1. 2. 3.

38、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í)行性），（說(shuō)明性） 5.(單詞符號(hào)），（語(yǔ)法單位）。 6.(源程序），（單詞符號(hào)） 7.(類(lèi)型、種屬、所占單元大小、地址） 8.(現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址) 9.(句柄） 10.(棧式)，（堆式） 11.(類(lèi)型)，（作用域） 12.(傳地址），（傳值），（傳名） 13.(局部?jī)?yōu)化），（循環(huán)優(yōu)化），（

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