編譯原理演示文稿7.ppt

1、第七章 編譯程序 7.1 編譯程序考慮的因素 編譯程序設(shè)計(jì)時(shí)，除了需用到前介紹的分析技術(shù)和制導(dǎo)翻譯技術(shù)外，還要考慮如何從源程序數(shù)據(jù)空間映射到具體物理存儲(chǔ)空間，也就是運(yùn)行時(shí)的數(shù)據(jù)表示。在運(yùn)行時(shí)如何組織或存放數(shù)據(jù)、在源程序中同名標(biāo)識(shí)符是怎樣描述不同的對(duì)象、運(yùn)行時(shí)的程序控制權(quán)是如何轉(zhuǎn)移和參數(shù)是如何傳遞的以及如何生成質(zhì)量較高的目標(biāo)代碼都是編譯程序設(shè)計(jì)者需考慮的問(wèn)題。,7.1.1 數(shù)據(jù)類(lèi)型 類(lèi)型的合法性檢查是判斷數(shù)據(jù)的類(lèi)型是否與上下文的要求相一致，例如Pascal的運(yùn)算符+不能作用在字符型數(shù)據(jù)上，而C語(yǔ)言的+卻能作用在字符型數(shù)據(jù)上。在數(shù)據(jù)類(lèi)型上定義的各種運(yùn)算通常包括賦值和一系列類(lèi)型轉(zhuǎn)換規(guī)則，這些規(guī)則保證

2、了作用在數(shù)據(jù)對(duì)象上的某個(gè)運(yùn)算符順便通過(guò)由編譯程序的類(lèi)型的合法性檢查，并實(shí)現(xiàn)其合法的算和賦值。因此，給出定義： 定義7.1 數(shù)據(jù)類(lèi)型是對(duì)該類(lèi)型數(shù)據(jù)（變量或常量）的取值是否合法以及對(duì)該類(lèi)型據(jù)的運(yùn)算是否合法的一種說(shuō)明。,實(shí)現(xiàn)和完成數(shù)據(jù)類(lèi)型的合法性檢查，它包括以下任務(wù)： (1) 檢查運(yùn)算符作用在運(yùn)算對(duì)象上的合法性，這一合法性保證了該運(yùn)算能產(chǎn)生正確的運(yùn)算結(jié)果。 (2) 根據(jù)程序設(shè)計(jì)語(yǔ)言運(yùn)算符的類(lèi)型轉(zhuǎn)換規(guī)則，將一種類(lèi)型數(shù)據(jù)轉(zhuǎn)換成另一種數(shù)據(jù)類(lèi)型。 (3) 能夠使用相應(yīng)的目標(biāo)機(jī)器指令實(shí)現(xiàn)這種在上述類(lèi)型上定義的運(yùn)算。,例:設(shè)有Pascal程序段 var a,b:integer; x:real; begin re

3、ad(a); b:=10; x:=a mod b; a:=a-x*10 end;,對(duì)于讀語(yǔ)句read(a)和賦值語(yǔ)句b:=10都滿(mǎn)足簡(jiǎn)單的類(lèi)型檢查。在賦值語(yǔ)句x:=a mod b中雖然a mod b的結(jié)果是整型的，但仍能滿(mǎn)足將a mod b的結(jié)果賦給實(shí)型變量x。這是因?yàn)樵赑ascal中定義了將整型轉(zhuǎn)換成實(shí)型的轉(zhuǎn)換規(guī)則，因而編譯程序需生成將a mod b的結(jié)果轉(zhuǎn)換成實(shí)型的指令代碼。而對(duì)于語(yǔ)句a:=a-x*10，雖然通過(guò)Pascal定義的類(lèi)型規(guī)則可以將a轉(zhuǎn)換成實(shí)型，求出a-x*10的結(jié)果類(lèi)型為實(shí)型，但Pascal不允許將實(shí)型賦給整型，則出錯(cuò)。,例:設(shè)有C語(yǔ)言程序段 int a,b; real x;

4、 scanf(“%d”, ,可以看出，上述二個(gè)程序段期望完成的功能是一樣的，但前者不能通過(guò)編譯，而后者能順利通過(guò)編譯的類(lèi)型檢查，這是因?yàn)镃語(yǔ)言中賦值語(yǔ)句a:=a-x*10中也包含了強(qiáng)制將實(shí)型轉(zhuǎn)換成整型。 根據(jù)語(yǔ)言的類(lèi)型定義方式，可以將類(lèi)型分為基本類(lèi)型和構(gòu)造類(lèi)型，基本類(lèi)型是指系統(tǒng)已定義的數(shù)據(jù)類(lèi)型，如C語(yǔ)言中的整型、浮點(diǎn)型（實(shí)型）、字符型。構(gòu)造類(lèi)型的指通過(guò)基本類(lèi)型或已定義的類(lèi)型構(gòu)造出的新的數(shù)據(jù)類(lèi)型，如Pascal中的數(shù)組、記錄和集合。引進(jìn)了構(gòu)造類(lèi)型后，類(lèi)型的合法性檢查變得復(fù)雜。其檢查方法有二大類(lèi)，一類(lèi)是名字等價(jià)，另一類(lèi)是結(jié)構(gòu)等價(jià)。 所謂名字等價(jià)也就是如果二個(gè)類(lèi)型是等價(jià)的，當(dāng)且僅當(dāng)二個(gè)類(lèi)型的名字或與

5、類(lèi)型名字的別名是等價(jià)的。,例:設(shè)有Pascal程序段 type int=integer; var a:integer; b:integer; c:int; a和b是同一類(lèi)型名integer故它們是等價(jià)的；雖然a和c的類(lèi)型名不同，但是int是integer的一種別名，故a和c的類(lèi)型還是等價(jià)的。 所謂結(jié)構(gòu)等價(jià)也就是如果二個(gè)類(lèi)型是等價(jià)的，當(dāng)且僅當(dāng)二個(gè)類(lèi)型具有相同的類(lèi)型表達(dá)式。,定義7.2 類(lèi)型表達(dá)式是遞歸定義的: (1) 類(lèi)型表達(dá)式是基本數(shù)據(jù)類(lèi)型 (2) 類(lèi)型表達(dá)式是由數(shù)組、記錄、集合、指針、函數(shù)等作用在類(lèi)型表達(dá)式上的類(lèi)型。 檢查類(lèi)型的名字等價(jià)相對(duì)簡(jiǎn)單，只要為定義的類(lèi)型名建立一張符號(hào)表，通過(guò)查表就可

6、以判定二個(gè)類(lèi)型是否名字等價(jià)。雖然，對(duì)于類(lèi)型的等價(jià)的直觀概念是結(jié)構(gòu)等價(jià)，但結(jié)構(gòu)等價(jià)檢查的實(shí)現(xiàn)方法稍復(fù)雜。需為每個(gè)類(lèi)型建立表示類(lèi)型的結(jié)構(gòu)樹(shù)或無(wú)環(huán)有向圖，如圖為類(lèi)型。 record name :array1.20 of char; age:integer end; 的樹(shù)結(jié)構(gòu)表示。 其中，array中的integer 表示下標(biāo)的類(lèi)型,對(duì)于如說(shuō)明鏈表或樹(shù)的數(shù)據(jù)結(jié)構(gòu)的定義時(shí)，需遞歸定義。因此遞歸定義的類(lèi)型圖為無(wú)環(huán)有向圖。圖為類(lèi)型 type link=node; node=record name :array1.20 of char; next:link end; 的無(wú)環(huán)有向圖。,檢查二個(gè)類(lèi)型是結(jié)構(gòu)等價(jià)，只

7、要二個(gè)類(lèi)型結(jié)構(gòu)樹(shù)或無(wú)環(huán)有向圖相等即可。檢查類(lèi)型等價(jià)也分成靜態(tài)檢查和動(dòng)態(tài)檢查。由編譯程序能完成的類(lèi)型檢查叫做靜態(tài)類(lèi)型檢查；由目標(biāo)程序運(yùn)行時(shí)所作的類(lèi)型檢查就稱(chēng)為動(dòng)態(tài)類(lèi)型檢查。一般地，如果要在生成的目標(biāo)代碼中完成類(lèi)型檢查，則目標(biāo)代中不但要保存數(shù)據(jù)的值，而且還保存該數(shù)據(jù)的類(lèi)型，則可完工成相應(yīng)的動(dòng)態(tài)類(lèi)型檢查。因算法語(yǔ)言的類(lèi)型檢查多數(shù)是靜態(tài)的類(lèi)型檢查，在這里僅介紹了靜態(tài)的類(lèi)型檢查。,7.1.2 數(shù)據(jù)結(jié)構(gòu) 一種程序設(shè)計(jì)語(yǔ)言如允許使用的數(shù)組、記錄、集合、字符串、表、棧等形式的數(shù)據(jù)結(jié)構(gòu)，在編譯程序中應(yīng)為它們提供相應(yīng)的翻譯。為了能對(duì)這些數(shù)據(jù)結(jié)構(gòu)中的元素的引用，編譯程序必須完成從這些數(shù)據(jù)的邏輯結(jié)構(gòu)到訪問(wèn)這些數(shù)據(jù)元素

8、的物理結(jié)構(gòu)的映射。 使用上述數(shù)據(jù)結(jié)構(gòu)應(yīng)考慮： (1) 映射算法相對(duì)簡(jiǎn)單，根據(jù)邏輯結(jié)構(gòu)容易計(jì)算出物理地址。 (2) 從邏輯結(jié)構(gòu)投影到物理結(jié)構(gòu)時(shí)，不至于越界或存儲(chǔ)溢出。 (3) 使用的數(shù)據(jù)結(jié)構(gòu)承擔(dān)這種程序設(shè)計(jì)語(yǔ)言的主要功能。 (4) 在這些數(shù)據(jù)結(jié)構(gòu)上定義的運(yùn)算。,例:設(shè)有類(lèi)Pascal程序段 program example(input,output); type student=record no:integer; name:array1.10 of char; score:integer end; weekday=(sun,mon,tue,wed,thu,fri,sat); var st:arr

9、ay1.50 of student; day:weekday; i,j:integer; begin today:= sun; i:=1; sti.no:=30; :=wang fang end.,從上可以看出，st是一個(gè)記錄型的數(shù)組，它首先通過(guò)數(shù)組的映射計(jì)算出sti的地址，然后再通過(guò)記錄的映射分別計(jì)算出sti.no 和 的地址。對(duì)于枚舉類(lèi)型的數(shù)據(jù)sun,mon,tue,wed,thu,fri,sat如何描述它們的值和在枚舉類(lèi)型的數(shù)據(jù)上的運(yùn)算。對(duì)于字符串應(yīng)考慮是否允許整體賦值和字符串是否允許連接等運(yùn)算，運(yùn)算后的結(jié)果到存儲(chǔ)器中。連接后的結(jié)果如超出字

10、符串設(shè)定的長(zhǎng)度，如何強(qiáng)制或報(bào)錯(cuò)。 如要實(shí)現(xiàn)一個(gè)“?！钡臄?shù)據(jù)類(lèi)型，就應(yīng)該考慮是否設(shè)置棧的最大容量，棧上的運(yùn)算如：push和pop。棧元素所允許的數(shù)據(jù)類(lèi)型，如棧元素的類(lèi)型允許是數(shù)組、記錄、集合、字符串，但不能是表或棧。還要考慮如何將棧頂映射的物理存儲(chǔ)空間。如設(shè)定靜態(tài)的定長(zhǎng)的?？臻g用指針或下標(biāo)指示當(dāng)前棧頂或設(shè)定不定長(zhǎng)的動(dòng)態(tài)空間當(dāng)入棧時(shí)申請(qǐng)存儲(chǔ)空間，出棧時(shí)返回存儲(chǔ)空間。,7.1.3 作用域規(guī)則 一個(gè)程序設(shè)計(jì)語(yǔ)言的作用域規(guī)則確定了該程序設(shè)計(jì)語(yǔ)言的某個(gè)程序的不同程序塊中所說(shuō)明的標(biāo)識(shí)符的可訪問(wèn)性。從另一個(gè)角度來(lái)看，在程序中當(dāng)訪問(wèn)一個(gè)標(biāo)識(shí)符通過(guò)作用域規(guī)則可確定究竟訪問(wèn)的是哪一個(gè)實(shí)體中說(shuō)明的標(biāo)識(shí)符。一般來(lái)說(shuō)一個(gè)

11、程序設(shè)計(jì)語(yǔ)言的一個(gè)標(biāo)識(shí)符或數(shù)據(jù)項(xiàng)的作用域是在說(shuō)明該標(biāo)識(shí)符或數(shù)據(jù)項(xiàng)的程序塊內(nèi)，如Pascal中的標(biāo)識(shí)符的作用域規(guī)則，敘述如下： (1) 一個(gè)標(biāo)識(shí)符的作用域是從該標(biāo)識(shí)符的定義點(diǎn)開(kāi)始至定義該標(biāo)識(shí)符的分程序結(jié)束為止，包含在這個(gè)分程序中的所有內(nèi)分程序，并遵循規(guī)則2。 (2) 當(dāng)一個(gè)標(biāo)識(shí)符x在分程序A中被定義，在A所包含的分程序B中又重新被定義，則分程序B以及包含在B中的所有分所出的x不再是A中定義的x，而是B中定義的x。,例:設(shè)有Pascal程序段 program example(input,output); var x,y: real; procedure pro; var y,z: integer;

12、 begin x:=y; end begin end.,在過(guò)程pro中賦值語(yǔ)句x:=y的x為主程序中說(shuō)明的x，而y為過(guò)程序中說(shuō)明的y。 作用域還包括文件作用域，如C語(yǔ)言的函數(shù)作用域是從說(shuō)明點(diǎn)開(kāi)始，一直延伸到源文件結(jié)束。 作用域規(guī)則的不同直接影響到編譯程序需生成的代碼。作用域規(guī)則分為靜態(tài)作用域和動(dòng)態(tài)作用域二種。靜態(tài)作用域是指當(dāng)標(biāo)識(shí)符在本分程序中沒(méi)有說(shuō)明時(shí)，到說(shuō)明該分程序的上一分程序中找相應(yīng)的標(biāo)識(shí)符，依次類(lèi)推直至找到該標(biāo)識(shí)符或整個(gè)上層分程序中均沒(méi)找到該標(biāo)識(shí)符為止。否則出錯(cuò)。動(dòng)態(tài)作用域是指當(dāng)標(biāo)識(shí)符在本分程序邏輯中沒(méi)有說(shuō)明時(shí)，到調(diào)用該分程序的程序中找，依次類(lèi)推直至找到該標(biāo)識(shí)符或整個(gè)調(diào)用程序中均沒(méi)找到該

13、標(biāo)識(shí)符為止，同樣動(dòng)態(tài)作用域也分為找到和出錯(cuò)。顯然上述Pascal中的作用域規(guī)則是靜態(tài)作用域規(guī)則，靜態(tài)作用域規(guī)則在編譯中處理要比動(dòng)態(tài)作用域的處理簡(jiǎn)單些。,7.1.4 控制結(jié)構(gòu) 一種程序設(shè)計(jì)語(yǔ)言的控制結(jié)構(gòu)是該語(yǔ)言在程序運(yùn)行期間用于改變控制流的語(yǔ)言特征集合。它包括有條件控制轉(zhuǎn)移，條件執(zhí)行、循環(huán)控制、過(guò)程序調(diào)用、轉(zhuǎn)移和出口。編譯程序在翻譯時(shí)必須保證源程序不能違法控制結(jié)構(gòu)的語(yǔ)義。如Pascal中只能從循環(huán)體內(nèi)轉(zhuǎn)向循環(huán)體外、C語(yǔ)言中不能從一個(gè)函數(shù)轉(zhuǎn)向另一個(gè)函數(shù)、BASIC中不能在循環(huán)體內(nèi)修改循環(huán)變量的值，而C沒(méi)有這種限制。 例:錯(cuò)誤的控制結(jié)構(gòu) begin for i:=1 to 10 begin labe

14、l:x:=x+1; end; goto label end,程序的控制結(jié)構(gòu)實(shí)際是程序執(zhí)行權(quán)的轉(zhuǎn)移。為了減少程序員編制的源程序中的錯(cuò)誤。通常對(duì)程序的結(jié)構(gòu)一定的約定。因此，在設(shè)計(jì)或翻譯程序設(shè)計(jì)語(yǔ)言的的控制結(jié)構(gòu)時(shí)，需考慮： 設(shè)定或限制某種程序的控制，應(yīng)滿(mǎn)足程序設(shè)計(jì)的方法學(xué)或結(jié)構(gòu)化程序設(shè)計(jì)的思想。 對(duì)每一種程序的控制結(jié)構(gòu)，均能用編譯的翻譯技術(shù)來(lái)實(shí)現(xiàn)翻譯。 提供程序的控制結(jié)構(gòu)有利于程序員實(shí)現(xiàn)程序和查找源程序的錯(cuò)誤。 綜上所述，如何實(shí)現(xiàn)控制結(jié)構(gòu)的翻譯也是編譯程序必須考慮的問(wèn)題。,7.2 運(yùn)行時(shí)的內(nèi)存分配 編譯程序需要為常量或變量等數(shù)據(jù)分配運(yùn)行時(shí)的存儲(chǔ)空間。編譯程序從操作系統(tǒng)中申請(qǐng)編譯程序計(jì)算出的所需的內(nèi)存

15、或者編譯程序生成在運(yùn)時(shí)需申請(qǐng)內(nèi)存的指令。 內(nèi)存分配包括以下3個(gè)任務(wù)： (1) 確定用來(lái)表示某一數(shù)據(jù)項(xiàng)的內(nèi)存的大小。 (2) 使用適當(dāng)?shù)膬?nèi)存分配策略實(shí)現(xiàn)具體數(shù)據(jù)的作用域和生命期。 (3) 確定以適當(dāng)?shù)乃惴ㄔL問(wèn)生命期內(nèi)的數(shù)據(jù)，包括基本型數(shù)據(jù)構(gòu)造型數(shù)據(jù)。 以上三個(gè)任務(wù)實(shí)際上是完成邏輯數(shù)據(jù)到具體數(shù)據(jù)的映射。根據(jù)內(nèi)存分配的時(shí)機(jī)，分為靜態(tài)存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配方式。采用哪一種分配策略是根據(jù)源語(yǔ)言的結(jié)構(gòu)特點(diǎn)、源語(yǔ)言的數(shù)據(jù)類(lèi)型、源語(yǔ)言中的作用域規(guī)則，源語(yǔ)言存儲(chǔ)管理和組織的方式的復(fù)雜度都會(huì)影響到存儲(chǔ)空間的分配策略。 下面就存儲(chǔ)分配的主要技術(shù)，進(jìn)行分析和討論。,7.2.1 靜態(tài)和動(dòng)態(tài)內(nèi)存分配 為目標(biāo)程序分配運(yùn)行時(shí)

16、所需的存儲(chǔ)空間，一種是在目標(biāo)程序運(yùn)行前，由編譯程序?yàn)閿?shù)據(jù)分配存儲(chǔ)空間，在程序的運(yùn)行期間不再分配和解除這種內(nèi)存分配。另一種在程序運(yùn)行期間均可以對(duì)內(nèi)存實(shí)現(xiàn)分配或解除分配，一旦存儲(chǔ)分配解除該存儲(chǔ)空間內(nèi)的數(shù)據(jù)便失去意義。前者稱(chēng)為靜態(tài)存儲(chǔ)分配，后者稱(chēng)為動(dòng)態(tài)存儲(chǔ)分配。 定義7.3 內(nèi)存結(jié)合是指數(shù)據(jù)項(xiàng)的邏輯地址映射到內(nèi)存物理地址的聯(lián)系 內(nèi)存分配和內(nèi)存結(jié)合是兩個(gè)不同的概念，內(nèi)存分配相當(dāng)于在上網(wǎng)時(shí)用戶(hù)申請(qǐng)了用戶(hù)名，此時(shí)網(wǎng)絡(luò)營(yíng)運(yùn)商將某個(gè)用戶(hù)名“分配”給了該用戶(hù)，但此時(shí)該用戶(hù)不一定在上網(wǎng)。內(nèi)存結(jié)合相當(dāng)于網(wǎng)絡(luò)用戶(hù)用了申請(qǐng)到的用戶(hù)名上網(wǎng)。網(wǎng)絡(luò)用戶(hù)的結(jié)合從用戶(hù)的上網(wǎng)起至該用戶(hù)下網(wǎng)止。,內(nèi)存分配是實(shí)現(xiàn)內(nèi)存結(jié)合的過(guò)程和手段，

17、內(nèi)存結(jié)合在內(nèi)存解除分配時(shí)終止。源程序數(shù)據(jù)項(xiàng)的結(jié)合時(shí)刻決定編譯程序的處理方式。當(dāng)編譯程序可以產(chǎn)生內(nèi)存分配的代碼時(shí)，不要在運(yùn)行產(chǎn)生這種分配。這會(huì)影響到目標(biāo)程序的效率。由于內(nèi)存分配的時(shí)機(jī)不同，引入靜態(tài)存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配的兩種方式。 1. 靜態(tài)存儲(chǔ)分配 在靜態(tài)存儲(chǔ)分配中，編譯程序在運(yùn)行前為數(shù)據(jù)分配內(nèi)存。典型的靜態(tài)存儲(chǔ)分配是在編譯時(shí)分配的。這要求編譯程序在編譯時(shí)能確定目標(biāo)程序運(yùn)行中據(jù)需的全部數(shù)據(jù)空間的大小，編譯程序?qū)?shù)據(jù)和內(nèi)存結(jié)合從而實(shí)現(xiàn)存儲(chǔ)分配。編譯程序一旦實(shí)現(xiàn)靜態(tài)存儲(chǔ)分配，在整個(gè)程序運(yùn)行期間不再進(jìn)行存儲(chǔ)分配或解除存儲(chǔ)分配的工作直到整個(gè)程序運(yùn)行結(jié)束。如C語(yǔ)言中的全局變量和靜態(tài)變量都是靜態(tài)存儲(chǔ)分配的

18、。,例:圖說(shuō)明了下列C語(yǔ)言程序段的靜態(tài)數(shù)據(jù)存儲(chǔ)分配 int a,b,c; char d100; int f (); main() int x=5,y=8; printf(“%d ”,f (x);) printf(“%d ”,g (y);) int f(int n) static int p=0; p+=n; return(p); ,int g(int m) static float q=0; q+=m; return(q); 圖中的陰影部分表示其它數(shù)據(jù)的存儲(chǔ)空間。 靜態(tài)存儲(chǔ)分配的限制： (1) 數(shù)據(jù)對(duì)象的長(zhǎng)度和它在內(nèi)存中的位置在編譯時(shí)都是已知的 (2) 不能建立如遞歸過(guò)程或遞歸函數(shù)中的一個(gè)名字

19、對(duì)應(yīng)多個(gè)存儲(chǔ)空間的結(jié)合 (3) 不能建立數(shù)據(jù)對(duì)象長(zhǎng)度不定的存儲(chǔ)空間,2. 動(dòng)態(tài)存儲(chǔ)分配 為了避免上述對(duì)靜態(tài)存儲(chǔ)分配的限制，引進(jìn)了動(dòng)態(tài)存儲(chǔ)分配。動(dòng)態(tài)分配的數(shù)據(jù)區(qū)在運(yùn)行不是一成不變的，它有時(shí)引入，有時(shí)退出，是一個(gè)動(dòng)態(tài)的變化過(guò)程。動(dòng)態(tài)存儲(chǔ)分配分為二大類(lèi)，一類(lèi)是隨著程序單元的進(jìn)入而分配，隨著程序單元的退出而撤銷(xiāo)。另一類(lèi)是由程序控制其分配和撤銷(xiāo)。它們分別用棧和堆來(lái)實(shí)現(xiàn)，被稱(chēng)為棧式動(dòng)態(tài)存儲(chǔ)分配和堆式動(dòng)態(tài)存儲(chǔ)分配。 a)棧式動(dòng)態(tài)分配 當(dāng)一個(gè)程序設(shè)計(jì)語(yǔ)言允許遞歸時(shí)，則每次進(jìn)入該遞歸過(guò)程或函數(shù)時(shí)，就應(yīng)分配一塊大小相同的內(nèi)存。當(dāng)該過(guò)程或函數(shù)結(jié)束時(shí)相應(yīng)的內(nèi)存釋放。由于遞歸過(guò)程或函數(shù)的進(jìn)入和退出符合棧的先進(jìn)后出的原則

20、，故這一類(lèi)存儲(chǔ)分配可用棧實(shí)現(xiàn)。把每次進(jìn)入過(guò)程或函數(shù)需分配的數(shù)據(jù)區(qū)稱(chēng)為活動(dòng)記錄。,活動(dòng)記錄包括（如圖所示）： (1) 連接數(shù)據(jù) a) 老的SP。 每個(gè)活動(dòng)記錄，有一個(gè)基址指針?lè)Q為SP。為了撤銷(xiāo)本活動(dòng)記錄時(shí)能指出上一個(gè)調(diào)用者的活動(dòng)記錄就應(yīng)保存調(diào)用者的SP稱(chēng)為老的SP。而老的棧頂不必保存，因?yàn)槔系臈ｍ敒楝F(xiàn)SP-1（設(shè)SP占一個(gè)存儲(chǔ)單元） b) 返回地址 返回地址是指子程序完成后的返回地址（對(duì)于函數(shù)還要返回其函數(shù)值）。 (2) 程序狀態(tài)字 為保存調(diào)用者的機(jī)器信息，如程序計(jì)數(shù)器、標(biāo)志寄存器和寄存器的值，在返回時(shí)，預(yù)以恢復(fù)。 (3) 參數(shù)個(gè)數(shù) (4)形式單元 存放實(shí)在參數(shù)的值或地址。,(5) 局部數(shù)據(jù) 局

21、部數(shù)據(jù)包括：局部變量、靜態(tài)數(shù)組的數(shù)據(jù)區(qū)、動(dòng)態(tài)數(shù)組的內(nèi)情向量和臨時(shí)工作單元。,例:設(shè)有程序結(jié)構(gòu)如下所示： program main; 全局變量或數(shù)組說(shuō)明； proc R; end R; proc Q; end Q; 在采用棧式動(dòng)態(tài)分配時(shí)，因每進(jìn)入一個(gè)過(guò)程就為該過(guò)程或函數(shù)分配存儲(chǔ)空間。則圖（a）表示主程序中調(diào)用了R；在R中又調(diào)用了Q的存儲(chǔ)結(jié)構(gòu)。圖（b）表示在Q中又調(diào)用了Q的存儲(chǔ)結(jié)構(gòu)。圖（c）表示在Q退出，又調(diào)用了R的存儲(chǔ)結(jié)構(gòu)。圖（d）表示在R退出的存儲(chǔ)結(jié)構(gòu)。圖（e）表示在Q退出的存儲(chǔ)結(jié)構(gòu)。圖（f）表示在R退出的存儲(chǔ)結(jié)構(gòu)。,經(jīng)過(guò)討論了棧的存儲(chǔ)分配，還要考慮過(guò)程式或函數(shù)調(diào)用和返回需完成的工作。前面第六

22、章說(shuō)過(guò)過(guò)程調(diào)用的四元式序列是： par T1 par T2 par T3 par Tn call P,n,現(xiàn)考慮四元式par和call是如何執(zhí)行的，也就是par和call要完成怎樣的工作。對(duì)于每個(gè)par Ti 需產(chǎn)生把參數(shù)填入活動(dòng)記錄的指令。由于SP、返回地址、參數(shù)個(gè)數(shù)和程序狀態(tài)字的所需的字節(jié)數(shù)對(duì)于某個(gè)過(guò)程來(lái)說(shuō)是不變的且可以計(jì)算出的，因此，每個(gè)參數(shù)存放的地址（相對(duì)于SP的地址）也是可以計(jì)算出的,設(shè)其和為m，則對(duì)于par Ti可翻譯成類(lèi)似于如下指令： TOP+ i+m:= Ti 這里TOP為老的TOP，每個(gè)參數(shù)均只占一個(gè)單元，Ti為參數(shù)的值或參數(shù)的地址。 四元式call P,n應(yīng)翻譯成： TOP

23、+1 := SP /*保護(hù)現(xiàn)行的SP*/ TOP+i+1 :=當(dāng)前寄存器值 /*保護(hù)現(xiàn)場(chǎng)*/ TOP+m-1 :=n /*保存參數(shù)個(gè)數(shù)*/ call P,進(jìn)入過(guò)程P后，應(yīng)賦新的SP，保護(hù)返回地址（返回地址也可以由指令call P保存系統(tǒng)的棧中），定義新的TOP值。即執(zhí)行指令： SP:= TOP+1 SP+1 :=返回地址 TOP：=TOP+L /*L為P過(guò)程所需的單元數(shù)*/ 當(dāng)執(zhí)行到過(guò)程、函數(shù)的返回語(yǔ)句或過(guò)程、函數(shù)中的語(yǔ)句全部被執(zhí)行完畢應(yīng)返回調(diào)用者。其工作為計(jì)算出內(nèi)存出棧后的TOP、將復(fù)原老的SP，對(duì)于函數(shù)還應(yīng)將函數(shù)值存放到指定的連接單元中，然后執(zhí)行返子指令： TOP:= SP -1 SP:=

24、 SP+0 /*如返回的是函數(shù)則執(zhí)行一條將函數(shù)值保存到指定單元或寄存中*/ RET /*返回調(diào)用程序*/ 在這里SP、TOP、參數(shù)等均只占一個(gè)單元，若它們占用不等長(zhǎng)的單元在編譯中也是可以計(jì)算出的，其實(shí)現(xiàn)方法類(lèi)似。,b)堆式動(dòng)態(tài)存儲(chǔ)分配 當(dāng)一種程序設(shè)計(jì)語(yǔ)言允許用類(lèi)似于Pascal中new和dispose語(yǔ)句申請(qǐng)和釋放內(nèi)存，則不能用棧式存儲(chǔ)分配，這因?yàn)槠渖暾?qǐng)和釋放的次序不滿(mǎn)足先進(jìn)后出的條件。這種數(shù)據(jù)只能借助于一種稱(chēng)為堆式動(dòng)態(tài)存儲(chǔ)分配的方法來(lái)實(shí)現(xiàn)。假定程序運(yùn)行時(shí)有一個(gè)較大的存儲(chǔ)空間，當(dāng)用戶(hù)申請(qǐng)堆內(nèi)存時(shí)，就分配一塊，不用時(shí)返回。由于分配和返回的時(shí)間沒(méi)有規(guī)律可循。當(dāng)程序運(yùn)行一段時(shí)間后，原來(lái)一塊較大的存儲(chǔ)

25、空間很可能分成很多很多塊。然而當(dāng)需要長(zhǎng)度為N的存儲(chǔ)空間只能尋找比N大或相等的內(nèi)存塊分配，以此往復(fù)。最后在存儲(chǔ)器池中出現(xiàn)了很多碎片。這些碎片就很難再為程序其它部分所用。為了解決碎片問(wèn)題，一種方法是通過(guò)移動(dòng)將碎片合并在一起，但這種方法是低效的，移動(dòng)需化費(fèi)很多機(jī)時(shí)。另一種方法是將原較大的存儲(chǔ)空間分成若干等長(zhǎng)的塊，申請(qǐng)時(shí)分配以塊為單位不足一塊的長(zhǎng)度也分配一塊，返回時(shí)則必定也是以塊為單位的。這樣解決了碎片問(wèn)題，即外零頭問(wèn)題。但以塊為單位分配浪費(fèi)了塊內(nèi)的存儲(chǔ)空間，也就是生成了內(nèi)零頭。這種方法雖然在分配時(shí)沒(méi)有完全利用全部存儲(chǔ)空間，但提高了系統(tǒng)的效率。由于操作系統(tǒng)也需要管理內(nèi)存，在編譯實(shí)現(xiàn)時(shí)直接可以利用操作系

26、統(tǒng)的內(nèi)存管理，即需要內(nèi)存時(shí)，向操作系統(tǒng)申請(qǐng)內(nèi)存，釋放時(shí)直接將內(nèi)存返回操作系統(tǒng)。,7.2.2 嵌套結(jié)構(gòu)的內(nèi)存分配 前面介紹的棧式動(dòng)態(tài)存儲(chǔ)分配，每個(gè)過(guò)程或函數(shù)只能使用局部變量不能使用非局部變量，這與Pascal語(yǔ)言結(jié)構(gòu)的特點(diǎn)是不同的。Pascal允許過(guò)程嵌套定義，也就是在過(guò)程或函數(shù)內(nèi)需要使用非局部變量。下面是有嵌套過(guò)的Pascal程序。 program sort(input,output); var a:array1.10 of integer; x:integer; procedure readarray; var a endreadarray procedure exchange(i,j:in

27、teger); begin x:=ai; ai:=aj; aj:=x endexchange,procedure quicksort(m,n:integer); var k,v:integer; function partition(y,z:integer):integer; var i,j:integer; begin a v exchange(i,j); endpartition; beginendquicksort; beginendsort,為了處理一致性，把主程序sort看作最外層過(guò)程。這樣過(guò)程說(shuō)明的嵌套情況為： sort readarray exchange quicksort p

28、artition 雖然在過(guò)程readarray、exchange、partition引變量a，但該變量卻為主程序中的a。在過(guò)程exchange中還引用了主程序中的x。下面要解決如何調(diào)用外層中的變量。 在這里介紹靜態(tài)作用域，動(dòng)態(tài)作用域的調(diào)用方式可參照此方法稍作修改，也能完成。從上圖中可以看出，無(wú)論是靜態(tài)作用域還是動(dòng)態(tài)作用域當(dāng)內(nèi)層過(guò)程需調(diào)用外層變量時(shí)，其外層過(guò)程的活動(dòng)記錄必然在棧中。要調(diào)用外層變量只要在內(nèi)層過(guò)程中指出外層變量的活動(dòng)記錄的位置（SP）值，再根據(jù)由符號(hào)表中指出的外層變量的相對(duì)位置就可以得到該外層變量的地址。,方法一：在活動(dòng)記錄中增加區(qū)頭向量 考慮程序的執(zhí)行次序?yàn)椋?sortquicks

29、ortquicksortpartitionexchange 對(duì)于exchange可能用到的外層變量為sort的變量；對(duì)于partition可能用到的外層變量為quicksort 和sort的變量。以sort標(biāo)記為0層；,readarray、exchange、quicksort標(biāo)記為1層；partition標(biāo)記為2層，則第i層過(guò)程中除了能調(diào)用本層變量外，還能調(diào)用第0層至第i-1層的外層變量。把從第0層至第i層活動(dòng)記錄的地址存放在一起組成了區(qū)頭向量，如圖所示。,當(dāng)sort調(diào)用quicksort時(shí)，quicksort的區(qū)頭向量為sort的區(qū)頭向量和quicksort活動(dòng)記錄的地址。對(duì)于quickso

30、rt調(diào)用quicksort時(shí)，不能用前面一個(gè)quicksort的區(qū)頭向量再加上本層活動(dòng)記錄的地址，發(fā)現(xiàn)quicksort和quicksort是并列的，也就是層數(shù)相同的，因此允許調(diào)用的外層變量是相同的，故可從前面的quicksort中拷貝層數(shù)個(gè)地址再加上本層活動(dòng)記錄的地址組成新的區(qū)頭向量。類(lèi)似地，partition從第2個(gè)quicksort過(guò)程中拷貝層數(shù)個(gè)地址再加上本層活動(dòng)記錄地址組成新的區(qū)頭向量。exchange從partition過(guò)程中拷貝層數(shù)個(gè)地址再加上本層活動(dòng)記錄地址組成新的區(qū)頭向量。,設(shè)有圖嵌套調(diào)用的情形，下面分另討論不同之處調(diào)用Pi的區(qū)頭向量的構(gòu)造情況。 在 Pi中調(diào)用Pi，則從P0

31、Pi-1均是Pi可以調(diào)用的，因此從上一層Pi的區(qū)頭向量中拷貝P0Pi-1的地址，加上Pi活動(dòng)記錄的地址組成新的區(qū)頭向量。在 Pi+1中調(diào)用Pi，則從P0Pi-1均是Pi可以調(diào)用的，而Pi 和Pi+1不是Pi的外層不要間接調(diào)用或不能調(diào)用，因此從上一層Pi+1的區(qū)頭向量中拷貝P0Pi-1的地址，加上Pi活動(dòng)記錄的地址組成新的區(qū)頭向量。同理，在 Pi+1中調(diào)用Pi，拷貝P0Pi-1的地址加上Pi活動(dòng)記錄的地址組成新的區(qū)頭向量。最后討論在 Pi+2中調(diào)用Pi，則仍然是從P0Pi-1均是Pi的外層，而Pi 、Pi+1和Pi+2不是Pi的外層，因此從上一層Pi+2的區(qū)頭向量中拷貝P0Pi-1的地址，加上P

32、i活動(dòng)記錄的地址也就組成了所需的區(qū)頭向量。,綜上所述，對(duì)于調(diào)用第i層的過(guò)程只要從前面調(diào)用者中拷貝0i-1個(gè)地址，加上本數(shù)據(jù)區(qū)的地址組成新的區(qū)頭向量。這樣要在活動(dòng)記錄中增加稱(chēng)之為區(qū)頭向量的部分，如圖所示。 每個(gè)過(guò)程的d值和過(guò)程的層數(shù)l在編譯時(shí)都是可以計(jì)算出來(lái)的，則四元式call P,n應(yīng)翻譯成： TOP+1 := SP /*保護(hù)現(xiàn)行的SP*/ TOP+i+1 :=當(dāng)前寄存器值 /*保護(hù)現(xiàn)場(chǎng)*/ TOP+m-1 :=n /*保存參數(shù)個(gè)數(shù)*/,從調(diào)用者的區(qū)頭向量中拷貝l個(gè)單元至進(jìn)入過(guò)程的區(qū)頭向量中；將TOP+1即新的SP放入?yún)^(qū)頭向量的最后單元，組成新的區(qū)頭向量。 call P設(shè)訪問(wèn)外層變量的層數(shù)為l

33、i，則訪問(wèn)外層變量的語(yǔ)句翻譯成： x:=SP li+d,或SP li+d:=x 的指令。 圖表示執(zhí)行次序?yàn)閟ortquicksortquicksortpartitionexchange的區(qū)頭向量變化圖。 方法二：在活動(dòng)記錄中增加訪問(wèn)鏈 在過(guò)程的活動(dòng)記錄中增加一個(gè)稱(chēng)為訪問(wèn)鏈的的指針，當(dāng)過(guò)程q在源程序中嵌套p中，則將q中訪問(wèn)鏈直接指向p。那么執(zhí)行次序?yàn)椋?sortquicksortquicksortpartitionexchange,具有訪問(wèn)鏈的存儲(chǔ)器棧變化圖，如上所示。下面需解決二個(gè)問(wèn)題： (1) 如何建立訪問(wèn)鏈 (2) 怎樣根據(jù)訪問(wèn)鏈獲得外層變量 建立訪問(wèn)鏈也就是在運(yùn)行時(shí)能求過(guò)程說(shuō)明的直接外層

34、。由于主程序沒(méi)有外層，故編譯程序需為進(jìn)入主程序時(shí)，生成置主程序的訪問(wèn)鏈為空指令。下面討論執(zhí)行中過(guò)程R（可能為主程序）調(diào)用過(guò)程S時(shí)，怎樣求出S的訪問(wèn)鏈。在編譯時(shí)R和S的層數(shù)都是可以求出分別記為lR和lS。R可以調(diào)用S，則S在R的作用域內(nèi)，可得lSlR+1。當(dāng)lS = lR+1時(shí)，則S是在R內(nèi)說(shuō)明的，也就是S是R的直接外層，只要生成將S的訪問(wèn)鏈置為指向R的SP（或R的訪問(wèn)鏈）的指令。,當(dāng)lS = lR時(shí)，則S和R是并列的它們具有相同的直接外層，也就是R的外層也就是S的外層，只要生成將R的訪問(wèn)鏈賦給S的訪問(wèn)鏈的指令即可。lSlR時(shí)，S的直接外層必然在棧中，即R必然被S的直接外層直接或間接調(diào)用，否則S

35、不在作用域內(nèi)。因此，只要對(duì)訪問(wèn)鏈向前搜索lR - lS層，即可得到S的直接外層。編譯程序生對(duì)訪問(wèn)鏈向前搜索lR - lS層的指令和將也為第lS的訪問(wèn)鏈賦給S的訪問(wèn)鏈。如R的層數(shù)為5，S的層數(shù)為2，則向前搜索3級(jí)求得層數(shù)也為2的活動(dòng)記錄，它的訪問(wèn)鏈即為S的訪問(wèn)鏈。 獲得外層變量的方法與上述類(lèi)似。設(shè)有p過(guò)程中訪問(wèn)了變量a，那么p過(guò)程的層數(shù)記為lp，變量a層數(shù)記為la，只要向前搜索la - lp層,就可得到變量a所在的活動(dòng)記錄中，由于a的相對(duì)位置在編譯中也是在符號(hào)表中可以查到的，故能生成對(duì)變量a訪問(wèn)的指令。,分程序內(nèi)含有數(shù)據(jù)說(shuō)明語(yǔ)句起源于Algol，但C語(yǔ)言中延用此概念，C語(yǔ)言的分程序的語(yǔ)法為 說(shuō)明

36、 語(yǔ)句 也就是在C語(yǔ)言中的復(fù)合語(yǔ)句中，允許說(shuō)明變量。而且在分程序的語(yǔ)句中還可以再有說(shuō)明。這種具有嵌套性的分程序稱(chēng)為分程序結(jié)構(gòu)。一個(gè)分程序結(jié)構(gòu)的語(yǔ)言的說(shuō)明作用域遵循最近嵌套原則： (1) 一個(gè)分程序B中說(shuō)明的作用域包括B，除了在B內(nèi)的分程序重新說(shuō)明 (2) 如果名字x不在B中說(shuō)明，則x是最靠近且B有說(shuō)明x的分程序說(shuō)明的x,設(shè)有程序段： main() /*分程序B0開(kāi)始*/ int a=0; int b=0; /*分程序B1開(kāi)始*/ int b=1; /*分程序B2開(kāi)始*/ int a=2; printf(“%d,%dn”,a,b); /*分程序B2結(jié)束*/ /*分程序B3開(kāi)始*/ int b=3

37、; printf(“%d,%dn”,a,b); /*分程序B3結(jié)束*/,printf(“%d,%dn”,a,b); /*分程序B1結(jié)束*/ printf(“%d,%dn”,a,b); /*分程序B0結(jié)束*/ 則在B0中說(shuō)明的int a=0的作用域?yàn)锽0- B2；在B0中說(shuō)明的int b=0的作用域?yàn)锽0- B1；在B1中說(shuō)明的int b=1的作用域?yàn)锽1- B3；在B2中說(shuō)明的int a=2的作用域?yàn)锽2；在B3中說(shuō)明的int b=3的作用域?yàn)锽3。其變量標(biāo)分別記為：a0,b0,b1,a2,b3。 分程序結(jié)構(gòu)也可以用棧式存儲(chǔ)分配來(lái)實(shí)現(xiàn)。因?yàn)槊總€(gè)變量作用域也符合先進(jìn)后出的特點(diǎn)。解決分程序邏輯結(jié)構(gòu)

38、的存儲(chǔ)分配，可采用下列二種方法。一是把分看成一個(gè)無(wú)參過(guò)程，用上述過(guò)程嵌套的方法來(lái)解決。這種過(guò)程的特點(diǎn)是只說(shuō)明一次，也只使用一次，它在分程序前調(diào)用，在分程序結(jié)束退出，調(diào)用外即為說(shuō)明之處。二是把一個(gè)過(guò)程體中所需的存儲(chǔ)一次全部分配好。由于B2中說(shuō)明的a和B3中說(shuō)明的b的作用域不相交，故可分同一塊存儲(chǔ)空間，如下圖所示。,在動(dòng)態(tài)作用域中，進(jìn)入新的過(guò)程時(shí)僅當(dāng)新過(guò)程中說(shuō)明了同名變量時(shí)，解釋為新的存儲(chǔ)。解決動(dòng)態(tài)作用的方法也有二種，一是所謂深訪問(wèn)，它在活動(dòng)記錄中存放一個(gè)控制鏈指向上一級(jí)調(diào)用過(guò)程，也可利用SP指針。當(dāng)發(fā)現(xiàn)非局部變量時(shí)從控制鏈一級(jí)一級(jí)向前搜索，直至搜索到為止，這種搜索可能深入棧中，因此而得名。搜索的

39、深度取決于程序的運(yùn)行，而編譯時(shí)不能決定的。另一種所謂淺訪問(wèn)，它采用體外循環(huán)的方法，為每個(gè)同名變量的名字分配靜態(tài)的數(shù)據(jù)空間，當(dāng)進(jìn)入有同名變量的過(guò)程時(shí)將靜態(tài)區(qū)的同名變量值保存到過(guò)程的同名變量的位置上，在過(guò)程的整個(gè)運(yùn)行過(guò)程中，使用靜態(tài)區(qū)同名變量，過(guò)程結(jié)束后將先前保存在過(guò)程內(nèi)的變量恢復(fù)。兩種方法各有優(yōu)缺點(diǎn)。深訪問(wèn)訪問(wèn)非局部變量是需較長(zhǎng)的時(shí)間，但它不需要額外的開(kāi)銷(xiāo)。而淺訪問(wèn)可以直接訪問(wèn)非局部變量，但需要一些輔助的時(shí)間和空間來(lái)維護(hù)。,7.2.3 數(shù)組的分配和訪問(wèn) 由于靜態(tài)數(shù)組所需空間的大小是在編譯時(shí)可以計(jì)算出來(lái)的，因此可在嵌套結(jié)構(gòu)的棧式存儲(chǔ)分配中只要為每個(gè)數(shù)組分直接分配相應(yīng)的存儲(chǔ)空間。下標(biāo)變量的訪問(wèn)無(wú)論是

40、本層變量還是外層變量都可以用前面介紹過(guò)的方法翻譯成通過(guò)基址SP和相對(duì)位置訪問(wèn)下標(biāo)變量的值。 動(dòng)態(tài)數(shù)組的所需的空間在運(yùn)行時(shí)才能確定，這樣動(dòng)態(tài)數(shù)組的存儲(chǔ)空間也只能在運(yùn)行時(shí)分配。前面說(shuō)過(guò)編譯程序需為內(nèi)情向量分配了存儲(chǔ)空間，然后生成填寫(xiě)內(nèi)情向量的指令。下面討論動(dòng)態(tài)數(shù)組的空間存放在何處。一種方法是將動(dòng)態(tài)數(shù)組的空間存放在堆內(nèi)存中，此時(shí)可以生成為動(dòng)態(tài)數(shù)組申請(qǐng)堆存儲(chǔ)的指令，并將首地址也填入內(nèi)情向量中。當(dāng)訪問(wèn)下標(biāo)變量時(shí)，則編譯程序可以生成要根據(jù)下標(biāo)變量的下標(biāo)和數(shù)組的內(nèi)情向量求出數(shù)組元素在堆中的存儲(chǔ)位置。,另外，應(yīng)該注意在過(guò)程結(jié)束時(shí)，還需生成一條將堆內(nèi)存返回的指令，不然會(huì)造成存儲(chǔ)器的泄漏。嚴(yán)重時(shí)還會(huì)造成系統(tǒng)癱瘓。

41、另一種方法也將動(dòng)態(tài)數(shù)組的存儲(chǔ)空間分配在棧中。當(dāng)進(jìn)入嵌套過(guò)程時(shí)，其活動(dòng)記錄的狀態(tài)如圖(a)所示。此時(shí)應(yīng)填寫(xiě)動(dòng)態(tài)數(shù)組的內(nèi)情向量，TOP+1作為第一個(gè)動(dòng)態(tài)數(shù)組的首地址。此時(shí)該動(dòng)態(tài)數(shù)組所需的存儲(chǔ)空間可以計(jì)算出來(lái)了，可在棧頂分配該動(dòng)態(tài)數(shù)組的存儲(chǔ)空間。并將棧指針指向新的棧頂。如有二個(gè)或二個(gè)以上的動(dòng)態(tài)數(shù)組，則繼續(xù)為每個(gè)動(dòng)態(tài)數(shù)組分配內(nèi)存。以次類(lèi)推，最后棧指針指向如圖(b)中的TOP位置。此方法當(dāng)過(guò)程退出時(shí)，則不必生成返回內(nèi)存的指令，這是因?yàn)橥顺鲞^(guò)程時(shí)TOP賦的是SP-1，SP賦的是過(guò)程中保存的老的SP，指向調(diào)用者的活動(dòng)記錄。達(dá)到將動(dòng)態(tài)數(shù)組分配的內(nèi)存和原來(lái)的活動(dòng)記錄一起返回給棧。,7.3 代碼優(yōu)化 作為一個(gè)高級(jí)

42、語(yǔ)言的使用者很希望編譯程序所產(chǎn)生的代碼能夠和直接用機(jī)器語(yǔ)言編寫(xiě)的程序的效果一樣好。但事實(shí)上很難做到這一點(diǎn)，即使能做到這一點(diǎn)，也許所需化費(fèi)實(shí)現(xiàn)優(yōu)化的時(shí)間和空間比優(yōu)化所得到的節(jié)省的時(shí)間多得多。在這里介紹的代碼優(yōu)化是指對(duì)原代碼進(jìn)行變換，從而獲得時(shí)間和空間效率相對(duì)高的程序，而不一定且一般也不是時(shí)間和空間最省的程序。在進(jìn)行優(yōu)化時(shí)應(yīng)做到： (1) 代碼的變換必須保持原程序的語(yǔ)義 (2) 從理論上，變換加快了程序的速度 (3) 這種變換是值得的 如果一種所謂的優(yōu)化改變了原程序的語(yǔ)義 實(shí)際上產(chǎn)生了一個(gè)錯(cuò)誤程序，這種變換也是無(wú)效的。盡管在優(yōu)化后可能對(duì)于一些程序反而比原來(lái)增加了開(kāi)銷(xiāo)，但總體來(lái)說(shuō)是節(jié)省的，而且節(jié)省應(yīng)

43、達(dá)到一個(gè)可度量的值，不然優(yōu)化中的損失不可能在運(yùn)行中彌補(bǔ)。由于各個(gè)機(jī)器的指令系統(tǒng)是不同的，即使是相同的四元式程序所生成的“最優(yōu)”的代碼也是不同的.其優(yōu)化算法也可能是不同的。為了算法的一致性在這里僅討論與目標(biāo)機(jī)器無(wú)關(guān)的優(yōu)化算法。,一個(gè)程序的優(yōu)化是由下面兩個(gè)階段構(gòu)成的： (1) 局部?jī)?yōu)化：應(yīng)用于僅包括少量語(yǔ)句的小程序的優(yōu)化變換。 (2) 全局優(yōu)化：應(yīng)用于一個(gè)程序單元，如一個(gè)函數(shù)或一個(gè)過(guò)程的優(yōu)化變換。 7.3.1 優(yōu)化變換 程序的執(zhí)行效率是可以通過(guò)地編譯期優(yōu)化變換是重寫(xiě)程序段以提高程序的工作效率而不改變語(yǔ)義。雖然變換的方法很多但常用的大致有下列幾種： 1. 編譯求值 一般來(lái)說(shuō)程序的目標(biāo)代碼可能要運(yùn)行多

44、次，而編譯只編譯一次。如果一些原屬于執(zhí)行時(shí)完成的工作能在編譯時(shí)解決，則提前完成這些工作。如在計(jì)算sin(3.1415927/6)時(shí)，3.1415927/6的值在編譯時(shí)可以計(jì)算的，其值為0.523598783，運(yùn)行時(shí)只要執(zhí)行sin(0.523598783)。因此程序的執(zhí)行效率是可以通過(guò)地編譯期間完成程序中的執(zhí)行語(yǔ)義來(lái)提高的。這時(shí)編譯程序消除了程序在執(zhí)行時(shí)的需求，從而達(dá)到減少程序的執(zhí)行時(shí)間、提高程序的工作效率。編譯時(shí)的求值卻體現(xiàn)了這一點(diǎn)。,2. 合并運(yùn)算 設(shè)有程序段： x:=a+b+c+d; if a+b0 then ; y:=(a+b)*(b+c)+d; 則子表達(dá)式a+b在不同的表達(dá)式中均使用過(guò)

45、，因此只要計(jì)算一次a+b的值，其余的值就可以使用該臨時(shí)變量的值。而將其它公共子表達(dá)式刪除。 實(shí)現(xiàn)這種優(yōu)化過(guò)程首先要識(shí)別產(chǎn)生相同值的表達(dá)式，在這里a和b都有沒(méi)有重新被定值，故子表達(dá)式相同即為值相同。其次計(jì)算相同的子表達(dá)式，用已存放在臨時(shí)變量的值逐個(gè)代替試寫(xiě)出算術(shù)表達(dá)式。 表達(dá)式的等價(jià)可以考慮它們的運(yùn)算對(duì)象是否程序所在位置處于相同的值。如一般情況下a+b值和b+a的值是等價(jià)的,還有執(zhí)行過(guò)c:=b后，a*b和a*c是等價(jià)的。實(shí)現(xiàn)這種“代數(shù)等價(jià)”，雖然提高了優(yōu)化的效率，但同時(shí)也增加了優(yōu)化的花費(fèi)。,例:寫(xiě)出算術(shù)表達(dá)式a+b*c-(c*b+a-c)/(b*c+d)優(yōu)化后的四元式 （1）（* ,b,c,t1

46、） （2）（+,a,t1,t2） （3）（-, t2,c,t3） （4）（+,t1,d,t4） （5）（/, t3,t4,t5） （6）（-, t2,t5,t6）,3. 刪除死碼 如果能在程序中刪除其代碼而不影響程序的運(yùn)行結(jié)果的代碼被稱(chēng)為“死碼”，“死碼”可以通過(guò)程序的控制流來(lái)獲得，如條件語(yǔ)句： if x3 then if x，而x在程序的其它處從未被引用過(guò)，顯然x:=也為“死碼”。刪除這種“死碼”時(shí)應(yīng)注意，只有當(dāng)?shù)膱?zhí)行不會(huì)產(chǎn)生副作用時(shí)可以刪除，也就是它不包含函數(shù)或過(guò)程，即使含有函數(shù)但沒(méi)有函數(shù)的副作用，才能刪除它。,4. 減少頻率 減少頻率是指程序中執(zhí)行頻率高的程序段移至程序執(zhí)行頻率低的程序部

47、分中。其主要變換有相對(duì)循環(huán)不變量的內(nèi)碼外提。如程序段： for i:=1 to 1000 do begin x:=1; y:=5*x; z:=y+i end 此時(shí)循環(huán)體內(nèi)的語(yǔ)句x:=1和y:=5*x;需執(zhí)行1000次，且它們相對(duì)于循環(huán)變量i來(lái)說(shuō)是不變的，因此將它們提出循環(huán)，置循環(huán)體外。即為： x:=1; y:=5*x; for i:=1 to 1000 do z:=y+i 這樣對(duì)于語(yǔ)句x:=1和y:=5*x僅執(zhí)行一次。,例:設(shè)有循環(huán)語(yǔ)句 c:=0; FOR i:=1 TO n DO BEGIN a:=x*y; b:=m*m; c:=c+b*b END 試寫(xiě)循環(huán)外提后的四元式序列。 根據(jù)題意，可

48、寫(xiě)出循環(huán)語(yǔ)句的四元式序列為： （1）（:= 0,_,c） （2）（:= 1,_,i） （3）（jl,n,i,14） （4）（*, x,y,t1） （5）（:=,t1,_,a） （6）（*, m,m,t2）,（7）（:=, t2,_,b） （8）（*, b,b,t3） （9）（+,c, t3, t4） （10）（:=, t4,_,c） （11）（+, i,1, t5） （12）（:=, t5,_,i） （13）（jmp, _,_,3） 由于a:=x*y是循環(huán)不變運(yùn)算，則可外提。b2與c之和雖然賦給了c，但b本身對(duì)于循環(huán)變量來(lái)說(shuō)也是不變的，故也可以外提。其外提后生成的四元式如下：,（1）（:= 0

49、,_,c） （2）（:= 1,_,i） （3）（*, x,y,t1） （4）（:=,t1,_,a） （5）（*, m,m,t2） （6）（:=, t2,_,b） （7）（*, b,b,t3） （8）（jl,n,i,14） （9）（+,c, t3, t4） （10）（:=, t4,_,c） （11）（+, i,1, t5） （12）（:=, t5,_,i） （13）（jmp, _,_,8）,5. 強(qiáng)度削弱和變換循環(huán)條件 強(qiáng)度削弱是指用一個(gè)運(yùn)算速度較快的運(yùn)算符代替耗時(shí)較多的運(yùn)算符，也就是將強(qiáng)度高的運(yùn)算符削減為低強(qiáng)度的運(yùn)算符。如：X2寫(xiě)成X*X，2*X寫(xiě)成X+X。 在循環(huán)中的強(qiáng)度削弱方法為： (1)

50、 設(shè)循環(huán)變量為i，對(duì)于循環(huán)體內(nèi)的運(yùn)算L:=K*i+C可削弱為T(mén):=T+K (2) 對(duì)臨時(shí)變量T賦初值C (3) 刪除強(qiáng)度削弱后的無(wú)用變量,例:設(shè)有循環(huán)語(yǔ)句 FOR i:=1 TO n DO BEGIN L:=K*i+C; END 則削弱為： T:=C; FOR i:=1 TO n DO BEGIN T:=T+K L:=T; END,強(qiáng)度削弱對(duì)于程序循環(huán)中數(shù)組的訪問(wèn)是十分重要的，如在一個(gè)Pascal循環(huán)中的數(shù)組引用ai,j的地址，這樣就造成了高強(qiáng)度的運(yùn)算i*n(按行存放)，用上述方法就可以大地降低運(yùn)算的強(qiáng)度。但需要注意的是這種方法不能適用于下標(biāo)變量允許為實(shí)數(shù)（浮點(diǎn)數(shù)）類(lèi)型，這是因?yàn)閷?shí)數(shù)在累加時(shí)會(huì)

51、產(chǎn)生積累誤差，最后的T中不是所需的K*i+C。 設(shè)有循環(huán)語(yǔ)句: for (i=1;i=n;i+) t=4*i; x=f(t); 由于在循環(huán)語(yǔ)句中i和t的關(guān)系始終保持4倍的關(guān)系，而且循環(huán)內(nèi)的其它部分也沒(méi)有引用i，則可將循環(huán)條件改變?yōu)?for (t=1;t=4*n; t+=4) 這樣經(jīng)過(guò)變換后i的值在循環(huán)內(nèi)不再引用，故可在循環(huán)中刪節(jié)除，從而達(dá)到優(yōu)化的目的。,6. 減少?gòu)?fù)寫(xiě)傳播 把形如b:=a的賦值語(yǔ)句稱(chēng)為復(fù)寫(xiě)語(yǔ)句，簡(jiǎn)稱(chēng)復(fù)寫(xiě)。當(dāng)b:=a;c:=b時(shí)，只要a在被新的賦值之后的程序不再引用b，則可用c:= a代替c:=b。 【例7-10】設(shè)有程序段 y:=x;z:=y;z:=y; t1:=f(y); t

52、2:=g(z); 則改寫(xiě)為： t1:=f(x); t2:=g(x);,7.3.2 局部?jī)?yōu)化 局部?jī)?yōu)化所需的化費(fèi)相對(duì)較低，也就從優(yōu)化所得到的收益也相對(duì)較低。局部?jī)?yōu)化顧名思義只是在較小的程序段中進(jìn)行優(yōu)化，從而達(dá)到優(yōu)化的目的。這種程序段稱(chēng)為“基本塊”。 定義7.4 基本塊是指程序中的一語(yǔ)句的順序序列(S1,S2, Sn)，其中只有第一個(gè)語(yǔ)句(S1)允許有是程序的控制語(yǔ)句轉(zhuǎn)移的目的語(yǔ)句和最后一個(gè)語(yǔ)句(Sn)允許是一個(gè)控制轉(zhuǎn)移語(yǔ)句。 基本塊劃分算法： (1) 求出稱(chēng)為入口的基本塊的第一個(gè)語(yǔ)句，如：程序的第一個(gè)語(yǔ)句或有控制語(yǔ)句轉(zhuǎn)入的語(yǔ)句。 (2) 對(duì)于每一入口語(yǔ)句構(gòu)造其所屬的基本塊： 1)由入口語(yǔ)句到下一

53、入口語(yǔ)句的前一語(yǔ)句 2)由入口語(yǔ)句到一轉(zhuǎn)移語(yǔ)句 3)由入口語(yǔ)句到一停語(yǔ)句 (3) 對(duì)于未被劃入任一基本塊的語(yǔ)句，為通過(guò)任何基本塊都不能到達(dá)該語(yǔ)句，故為無(wú)用語(yǔ)句應(yīng)刪除。,對(duì)于基本塊內(nèi)的公共子表達(dá)式的刪除，可采用計(jì)算出每項(xiàng)個(gè)定值的四元式編號(hào)，當(dāng)兩個(gè)子表達(dá)式完全相同時(shí)，則它們具有相同的定值的四元式編號(hào)，表示在二個(gè)四元式之間沒(méi)有新的定值。 為了簡(jiǎn)單起見(jiàn)。在基本塊內(nèi)將四元式編號(hào)以1開(kāi)始的連續(xù)號(hào)碼編號(hào)。由于一個(gè)被定值的變號(hào)與被定值的變量有關(guān)，則在符號(hào)表中的每一變量增加一個(gè)稱(chēng)為定值編號(hào)的屬性。設(shè)有(n) A:=B op C，其中n為對(duì)A定值的四元式編號(hào)，B、C為變量，op為運(yùn)算符。在符號(hào)表中需保存每個(gè)變量定

54、值的位置n，對(duì)尚未定值的變量符號(hào)表中的定值編號(hào)的屬性以0表示。另外建立一四元式的符號(hào)表，為每個(gè)四元式的運(yùn)算對(duì)象上都上都附加一個(gè)定值信息來(lái)指出該運(yùn)算對(duì)象，這些信息也用四元式的編號(hào)表示。,再為每個(gè)四元式保存一個(gè)引用信息表示是否要為程序中的其它處引用而保留其值，其初值為false。當(dāng)設(shè)表達(dá)式e是e的子表達(dá)式，在翻譯是時(shí)形成了關(guān)于e的四元組時(shí)，其運(yùn)算對(duì)象所關(guān)聯(lián)的定值信息可從符號(hào)表中獲得。將新產(chǎn)生的四元式和四元式符號(hào)表中現(xiàn)有的四元式比較，如果存在一個(gè)登記項(xiàng)為k的與新的四元組完全匹配的四元式，則說(shuō)明其值與新的表達(dá)式的值完全相同，也就是新的四元式不必存放在四元式符號(hào)表中，用四元式符號(hào)表k的結(jié)果名代替e中的對(duì)

55、象，并對(duì)四元式k的引用信息置為true，以便決定該值是否保存到臨時(shí)變量中。,例:設(shè)有基本塊： (:=,3.14 ,_,t1) (*,2, t1, t2) (*,x, y, t3) (*,t1 , t2, a) (:=,a, _, b) (*,2, t1, t4) (*,x, y, t5) (*,t4 , t5, t6) (*,x , y, t7) (*,t6 , t7, b),其局部?jī)?yōu)化的過(guò)程為設(shè)所有變量的定值編號(hào)為0，當(dāng)四元式(:=,3.14 ,_,t1)、(*,2, t1, t2)和(*,x, y, t3)進(jìn)入時(shí)為圖(a)；,當(dāng)四元式(*,t1 , t2, a)和(:=,a, _, b)進(jìn)

56、入時(shí)，如圖(b)；,優(yōu)化四元式(*,2, t1, t4)時(shí)，在四元式表中查到匹配的四元式(2)，故該四元不要入表，以后以t2代替原來(lái)的t4；同樣四元式(*,x, y, t5)只要用t3代替t5；則對(duì)于四元式(*,t4 , t5, t6)將改為(*,t2 , t3, t4)填表。四元式 (*,x , y, t7) 也能找到匹配的四元式，則不要添加到表中；最后(*,t6 , t7,b)添入表中為(*,t4 , t3,b)，并將t2 和 t3的引用信息改為true,如圖(c)。,上述方法很容易地?cái)U(kuò)充到編譯時(shí)的合并常量。對(duì)于語(yǔ)句a:=n，其中a為變量，n為常量。則在在常量表中加入常量n，其登記項(xiàng)為k，

57、并將定值位置k與a相關(guān)聯(lián)用-k表示。當(dāng)生成一個(gè)四元組是，如果每個(gè)運(yùn)算對(duì)象都是一個(gè)常量或是一個(gè)負(fù)的定值位置時(shí)，就可以實(shí)常量合并。 例:將上例中加入用合并常量算法 加入用合并常量算法后其結(jié)果，如圖所示。,7.3.3 全局優(yōu)化 要產(chǎn)生高效的代碼，編譯程序僅在基本塊內(nèi)優(yōu)化是不夠的。編譯程序應(yīng)把程序作為一整體來(lái)考慮，對(duì)各個(gè)基本塊的信息進(jìn)行數(shù)據(jù)流的分析從而達(dá)到優(yōu)化的目的。全局優(yōu)化和局部?jī)?yōu)化相比，全局優(yōu)化需要更多的分析，以便確定優(yōu)化的可行性。這里僅介紹全局子表達(dá)式的消除，包括公共表達(dá)式的消除和死代碼的消除。 設(shè)有子表達(dá)式存在于程序的若干基本塊中，記為SB = bi|bi是基本塊。設(shè)子表達(dá)式存在于程序的一組基

58、本塊中，且在某個(gè)bk中存在對(duì)子表達(dá)式的求值。當(dāng)程序的每次執(zhí)行，都能滿(mǎn)足下列兩個(gè)條件，則在基本塊bi中子表達(dá)式是可以消除的。 (1) 基本塊bi只在已執(zhí)行了一次或多次的某個(gè)bk后執(zhí)行。 (2) 在基本塊bk對(duì)的最后一次求值后，沒(méi)有改變中的變量的值。,第一個(gè)條件保證了基本塊bi中的子表達(dá)式已被求值；第二個(gè)條件則保證了在基本塊bk求得的值和在基本塊bi求得的值是等價(jià)的。如子表達(dá)式為x*y，則不能改變變量x或y的值。 定義7.5 程序流程圖是一個(gè)三元組G=(N,E,n0)，其中，N為圖的所有結(jié)點(diǎn)的集合也就是基本塊的集合。E表示圖中的有向圖中的邊集，邊(bi,bj)它表示基本塊bi的最后一個(gè)語(yǔ)句轉(zhuǎn)向基本

59、塊bj的第一個(gè)語(yǔ)句。n0表示程序的開(kāi)始結(jié)點(diǎn)。,利用程序流程圖分析基本塊的控制和數(shù)據(jù)流的關(guān)系，實(shí)際上是分析基本塊之間的關(guān)系是否滿(mǎn)足上述二個(gè)條件。下面介紹一些基本概念： (1) 前趨和后繼：若(bi,bj)E，則稱(chēng)bi是bj的前趨，bj是bi的后繼。 (2) 路徑：路徑是從一個(gè)結(jié)點(diǎn)沿邊序列到另一個(gè)結(jié)點(diǎn)的邊的有序序列。 (3) 祖先和后代：若存在一條從bi到bj的路徑，則稱(chēng)為bi是bj的祖先, bj是bi的后代。 (4) 活躍變量：如果變量a在一個(gè)基本塊bi的某個(gè)程序點(diǎn)pi處定值，并在以后的程序中引用該值，則稱(chēng)變量a是活躍的,控制流分析是對(duì)一個(gè)程序進(jìn)行分析以收集與程序結(jié)構(gòu)相關(guān)的信息。數(shù)據(jù)流分析是對(duì)程序中使用的數(shù)據(jù)進(jìn)行分析，以收集對(duì)優(yōu)化有用的信息，能用來(lái)判斷是否能對(duì)程序段進(jìn)行優(yōu)化。 定義7.6 如果在基本塊bi包含一個(gè)對(duì)子表達(dá)式求值，且從求值之后不再包括對(duì)表達(dá)式中的運(yùn)算對(duì)象的賦值，或子表達(dá)式在基本塊是入口有效bi不再包括對(duì)表達(dá)式中的運(yùn)算對(duì)象的賦值稱(chēng)子