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

得分 一 填空題（每空 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ō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局部優(yōu)化是局限于一個(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è)出口的語句C 一個(gè)沒有嵌套的程序段 D 一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口3. 高級(jí)語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（ ）分析方法。A 自左向右 B 自頂向下 C 自底向上 D 自右向左4在通常的語法分析方法中，（ ）特別適用于表達(dá)式的分析。A 算符優(yōu)先分析法 B LR 分析法C 遞歸下降分析法 D LL（1）分析法5經(jīng)過編譯所得到的目標(biāo)程序是（ ）。A 四元式序列 B 間接三元式序列C 二元式序列 D 機(jī)器語言程序或匯編語言程序6 一個(gè)文法所描述的語言是（ ）；描述一個(gè)語言的文法是（ ）。A 唯一的 B 不唯一的 C 可能唯一，也可能不唯一7 如果在文法 G 中存在一個(gè)句子，當(dāng)其滿足下列條件（ ）之一時(shí)，則稱該文法是二義文法。A 其最左推導(dǎo)和最右推導(dǎo)相同 B 該句子有兩個(gè)不同的最左推導(dǎo)C 該句子有兩個(gè)不同的最右推導(dǎo) D 該句子有兩棵不同的語法樹E 該句子對(duì)應(yīng)的語法樹唯一8 下面（ ）語法制導(dǎo)翻譯中，采用拉鏈回填技術(shù)。A. 賦值語句 B. 布爾表達(dá)式的計(jì)算 C. 條件語句 D. 循環(huán)語句三 解答題（共 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） 畫出該句子的語法推導(dǎo)樹。（ 4 分）3 （共 8 分）在一個(gè)移入-規(guī)約分析過程中采用以下的語法制導(dǎo)翻譯模式，在按一個(gè)產(chǎn)生式規(guī)約時(shí)，立即執(zhí)行括號(hào)中的動(dòng)作。AaB print “0”；Ac print “1”；BAb print “2”；（1） 當(dāng)分析器的輸入為 aacbb 時(shí)，打印的字符串是什么？（3 分）（2） 寫出分析過程。（5 分）4 （10 分）翻譯循環(huán)語句 while (ad) then x:=y+z 。要求：給出加注釋的分析樹及四元式序列。參考以下部分翻譯模式：(1) Sif E then M S 1 backpatch(E.truelist,M.quad); S.nextlist:=merge(E.falselist,S1 .nextlist)(2) Swhile M 1 E do M2 S1 backpatch(S1.nextlist,M1,.quad);backpatch(E.truelist,M2,.quad);S.nextlist:=E.falselistemit (j,-,-,M1 .quad)(3) SA S.nextlist:=makelist()(4) LS L.nextlist:=S.nextlist(5) M M.quad:=nextquad(6) Eid 1 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,-,L.place)(8) EE 1+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下列符號(hào)串中是該文法句子的有（ ）。 ab0 a0c01 aaa bc10可選項(xiàng)有：A B C D 2.程序的基本塊是指（ ）。A 一個(gè)子程序 B 一個(gè)僅有一個(gè)入口和一個(gè)出口的語句C 一個(gè)沒有嵌套的程序段 D 一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口3. 高級(jí)語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（ ）分析方法。A 自左向右 B 自頂向下 C 自底向上 D 自右向左4經(jīng)過編譯所得到的目標(biāo)程序是（ ）。A 四元式序列 B 間接三元式序列C 二元式序列 D 機(jī)器語言程序或匯編語言程序5 運(yùn)行階段的存儲(chǔ)組織與管理的目的是（ ）。 提高編譯程序的運(yùn)行速度 節(jié)省編譯程序的存儲(chǔ)空間 提高目標(biāo)程序的運(yùn)行速度 為運(yùn)行階段的存儲(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)系表（不考慮語句括號(hào)#），并指出此文法是否為算符優(yōu)先文法。（2） 構(gòu)造文法 G 的優(yōu)先函數(shù)表。4 （8 分）在一個(gè)移入-規(guī)約分析過程中采用以下的語法制導(dǎo)翻譯模式，在按一個(gè)產(chǎn)生式規(guī)約時(shí)，立即執(zhí)行括號(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） 寫出移入-規(guī)約分析過程。5 （12 分）翻譯循環(huán)語句 while (xy) do if (a=b) then x:=2*y+a 。要求：給出加注釋的分析樹、三地址碼序列及相應(yīng)的四元式序列。參考以下部分翻譯模式：(1) Sif E then M S 1 backpatch(E.truelist,M.quad); S.nextlist:=merge(E.falselist,S1 .nextlist)(2) Swhile M 1 E do M2 S1 backpatch(S1.nextlist,M1,.quad);backpatch(E.truelist,M2,.quad);S.nextlist:=E.falselistemit (j,-,-,M1 .quad)(3) SA S.nextlist:=makelist()(4) LS L.nextlist:=S.nextlist(5) M M.quad:=nextquad(6) Eid 1 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,-,L.place)(8) EE 1+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 xy goto L2Z=s+aiI=i+1Goto L1L2: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=1L4: A=A+Bif BC 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) 堆式動(dòng)態(tài)存儲(chǔ)分配(3) 左(4) 語法分析(5) 目標(biāo)代碼生成(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,選對(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(E)=(,i FIRST(E)=*,+, FIRST(T)=*,+FOLLOW(E)=),*,+,# FOWLLOW(E)= ),*,+,# FOLLOW(T)=(,i（ 3） 每錯(cuò)一個(gè)扣 0.5 分，全錯(cuò)或不寫不得分，扣完為止，共 5 分( ) i * + #E E(E)E EiEE E ETEE ETEE E E E T T* 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( ) S(S)() S( )() S(S)()() S(S(S)()() S(S( )()() S(S(S)()()() S(S( )()()() S( )()()() ()()()()（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 分，扣完為止，共 5 分。Swhile M1.q=100 E1.t=102 do M2.q=102 S1E1.f=107 ad x E5.p=y + E6.p=z（ 2） 少寫一個(gè)四元式扣 0.5 分，全錯(cuò)或不寫不 y z四元式序列為