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

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

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

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

4、*c+d7 .目標(biāo)代碼生成應(yīng)著重考慮的問題是a da.每個(gè)語法成分的語義b.目標(biāo)程序運(yùn)行所占用的空間c.目標(biāo)程序運(yùn)行速度d.目標(biāo)代碼中需要哪些信息，怎樣截取這些信息e.如何使生成的目標(biāo)代碼盡可能簡短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)代碼盡可能的簡短9 .編譯程序在優(yōu)化時(shí) b 用到源程序中的注釋a.可能要 b.不可能10 .在編譯程序采用的優(yōu)化方法中，c d e 是在循環(huán)語句范圍內(nèi)進(jìn)行的。a.合并已知常量b.刪除多余運(yùn)算c.刪除歸納變量d.強(qiáng)度消弱e.代碼外提11 .程序基本塊是指.d。a

5、. 一個(gè)子程序b. 一個(gè)僅有一個(gè)入口和一個(gè)出口的語句c. 一個(gè)沒有嵌套的程序段d. 一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口12 .合并表達(dá)式中的常量運(yùn)算的目的是 。a.合并常量，使表達(dá)式中的常量盡可能少b.合并常量，是表達(dá)式盡可能簡短c.將可在編譯時(shí)刻計(jì)算的常量運(yùn)算在編譯時(shí)刻計(jì)算出來，然后用所計(jì)算出來的值替換表達(dá)式中出現(xiàn)的所以這種常量運(yùn)算，使得生成的代碼指令盡可能少13 .下面的程序段可以進(jìn)行哪些優(yōu)化cdei:=1j:=10 read k1: x:=x*i y:=j*i z:=x*y write j i:=i+1 if i<100 goto 1 halta.合并已知常量b.刪除多余

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

7、1) A(3)* A (2)(4)* C D(5)+ B (4)(6)工(3) (5)多兀式表小：(1)* B C T1(2)-T 1 A T 2(3)* A T 2 T3(4)* C D T 4(5)+ B T 4 T 5(6)三 T 3 T 5 T 6樹表小:五、試寫出下列語句的四元式中間代碼(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 while y>0 do

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