編譯原理階段練習(xí)四

1、編譯原理練習(xí)四、填空題1. 編譯過(guò)程中，常見(jiàn)的中間語(yǔ)言形式有四元式、 三元式 、逆波蘭表示和樹(shù)形表示。2、表達(dá)式 x+yizVa>0A (8+z)>3 的逆波蘭表示為 xy+z 豈aO>8z+3>A V 。3、 在編譯程序中安排中間代碼生成的目的是便于代碼優(yōu)化 和 便于目標(biāo)程序的 移植。4、 根據(jù)所涉及程序的范圍，優(yōu)化可分為局部?jī)?yōu)化、循環(huán)優(yōu)化和全局優(yōu)化三種。5、編譯程序進(jìn)行數(shù)據(jù)流分析的目的是為了進(jìn)行全局優(yōu)化。6、 局部?jī)?yōu)化是局限與一個(gè)基本塊 范圍內(nèi)的一種優(yōu)化。7、 基本塊內(nèi)可進(jìn)行的優(yōu)化有：刪除公共子表達(dá)式、刪除無(wú)用代碼、合并已知 常量等。8 從詞法分析器到中間代碼生成與

2、被編譯的源代碼有關(guān)，稱(chēng)之為編譯器的 前端,而目標(biāo)代碼生成主要與目標(biāo)機(jī)有關(guān)，稱(chēng)之為編譯器的后端 。9. 編譯器通常按需要把寄存器分為三組使用：可分配寄存器、保留寄存器 和 零用寄存器。10. 釋放寄存器的總的原則是釋放代價(jià)最小的寄存器。二、選擇題1 .表達(dá)式-a+b*(-c+d)的逆波蘭式是da. ab+-cd+-*b.a-b+c-d+*c. a-bc+-d+*d. a-bc-d+*+2.在編譯程序中安排中間代碼生成的目的是_bda. 便于進(jìn)行存儲(chǔ)空間的組織b. 有利于目標(biāo)代碼的優(yōu)化c. 有利于編譯程序的移植d. 有利于目標(biāo)代碼的移植e. 有利于提高目標(biāo)代碼的質(zhì)量3. -a-(b*c/(c-d)

3、+(-b)*a)a.abc*cd-b-a*+/-c.a-bc*cd-/b-a*+-的逆波蘭表示是cb. a-bc*cd-b-a*+/-d.a-bc*/cd-b-a*+-4. 賦值語(yǔ)句 X:=-(a+b)/(c-d)-(a+b*c)a. Xab+cd-/-bc*a+-:=c. Xab+-cd-/abc*+-:=的逆波蘭表示是_cb. Xab+/cd-bc*a+-:=d. Xab+cd-/abc*+-:=5. 對(duì)任何一個(gè)編譯程序來(lái)說(shuō)，產(chǎn)生中間代碼是b .a. 不可缺少的b.不一定必要的6.逆波蘭表達(dá)式ab+cd+*所代表的中綴形式的表達(dá)式是a. a+b+c*db. (a+b)*(c+d)c. (a

4、+b)*c+dd. a+b*c+d7.目標(biāo)代碼生成應(yīng)著重考慮的問(wèn)題是a da. 每個(gè)語(yǔ)法成分的語(yǔ)義b. 目標(biāo)程序運(yùn)行所占用的空間c. 目標(biāo)程序運(yùn)行速度d. 目標(biāo)代碼中需要哪些信息，怎樣截取這些信息e. 如何使生成的目標(biāo)代碼盡可能簡(jiǎn)短8. 代碼優(yōu)化的主要目標(biāo)是a b c。a. 如何提高目標(biāo)程序的運(yùn)行速度b. 如何減少目標(biāo)程序運(yùn)行所需的空間c. 如何協(xié)調(diào)a和bd. 如何使生成的目標(biāo)代碼盡可能的簡(jiǎn)短9. 編譯程序在優(yōu)化時(shí)_b用到源程序中的注釋a. 可能要b.不可能10. 在編譯程序采用的優(yōu)化方法中，c d e 是在循環(huán)語(yǔ)句范圍內(nèi)進(jìn)行的a. 合并已知常量b. 刪除多余運(yùn)算c. 刪除歸納變量d. 強(qiáng)度消

5、弱e. 代碼外提11. 程序基本塊是指衛(wèi)。a. 一個(gè)子程序b. 一個(gè)僅有一個(gè)入口和一個(gè)出口的語(yǔ)句c. 一個(gè)沒(méi)有嵌套的程序段d. 一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口12. 合并表達(dá)式中的常量運(yùn)算的目的是 _c。a. 合并常量，使表達(dá)式中的常量盡可能少b. 合并常量，是表達(dá)式盡可能簡(jiǎn)短c. 將可在編譯時(shí)刻計(jì)算的常量運(yùn)算在編譯時(shí)刻計(jì)算出來(lái)，然后用所計(jì)算出來(lái)的值替換表達(dá)式中出現(xiàn)的所以這種常量運(yùn)算，使得生成的代碼指令盡可能少13下面的程序段可以進(jìn)行哪些優(yōu)化cd_ei:=1j:=10read k1: x:=x*iy:=j*iz:=x*ywrite ji:=i+1if i<100 goto

6、1halta.合并已知常量b.刪除多余運(yùn)算c.刪除歸納變量d.強(qiáng)度消弱e.代碼外提三、為什么要使用中間語(yǔ)言形式？ 解答：使用中間語(yǔ)言形式有如下好處：i. 中間語(yǔ)言與具體機(jī)器無(wú)關(guān)，把與機(jī)器特性緊密相關(guān)的內(nèi)容盡可能放到后端，有利于重定目標(biāo)，一種中間語(yǔ)言可以為生成多種不同型號(hào)目標(biāo) 機(jī)上的目標(biāo)代碼服務(wù)ii. 可以對(duì)中間語(yǔ)言進(jìn)行與機(jī)器無(wú)關(guān)的優(yōu)化，有利于提高目標(biāo)代碼的質(zhì)量iii. 使各階段的開(kāi)發(fā)復(fù)雜性降低，有利于編譯程序的開(kāi)發(fā) 四、設(shè)有表達(dá)式A*（B*C-A） < B+C*D（1）寫(xiě)出逆波蘭式中間代碼（2）寫(xiě)出三元式中間代碼（3）寫(xiě)出多元式中間代碼畫(huà)出樹(shù)解答：逆波蘭表示：ABC*A-*BCD*+三元

7、式表示：（1）* B C（2）- （1） A（3）* A （2）（4）* C D（5） + B（4）（6）乞（3）（5）多元式表示：（1）*BC T1（2）-T1 A T 2（3）*AT 2 T3（4）*CD T4（5）+BT 4 T 5（6）<T3 T 5 T 6樹(shù)表示:B C五、試寫(xiě)出下列語(yǔ)句的四元式中間代碼(1) if x>0 then x:=0 else x:=1(2) while x>0 do x:=x-1(3) if x>0 then if x<0 then x:=x+1 else x:=1 else x:=1(4) while x>0 do w

8、hile y>0 do beg in y:=y-x; x:=x-1 end 解答：(1)>x0tFJ5t1 /:=0/xRJ6/:=1/x>x0t1FJ6t1 /-x1t2:=t2/ xRJ1/略六、給出從多元式劃分基本塊的方法解答：基本塊劃分算法：1) 求出多元式程序中各個(gè)基本塊的入口語(yǔ)句：?(1)程序的第一個(gè)句句；或者?(2)能由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到達(dá)的語(yǔ)句；或者，?(3)僅跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。從而2) 對(duì)以上求出的每一入口語(yǔ)句，構(gòu)造其所屬的基本塊。3) 凡未被納入某一基本塊中的語(yǔ)句，都是程序中控制流程無(wú)法到達(dá)的語(yǔ)句, 也是不會(huì)被執(zhí)行的語(yǔ)句，可把他們刪除。七、給出程序流圖(以基本塊為結(jié)點(diǎn))的一種表示方法。 解