編譯原理與技術(shù)講義 第7章 運(yùn)行時(shí)環(huán)境

1、編譯原理與技術(shù)第7章 運(yùn)行時(shí)環(huán)境 青島大學(xué)信息工程學(xué)院主要內(nèi)容程序運(yùn)行的基本概念 參數(shù)傳遞機(jī)制 靜態(tài)運(yùn)行時(shí)環(huán)境運(yùn)行時(shí)存儲(chǔ)空間的組織和管理 棧式運(yùn)行時(shí)環(huán)境堆式運(yùn)行時(shí)環(huán)境 編譯原理與技術(shù)27.1 程序運(yùn)行的基本概念 過程及其活動(dòng)過程定義是把一個(gè)名字和若干語句聯(lián)系起來的一個(gè)聲明。這個(gè)名字是過程名，而這些語句就是過程體。返回值的過程通常稱為函數(shù)，完整的程序也可以看作一個(gè)過程。在面向?qū)ο蠹夹g(shù)中，過程叫做方法或操作。本章把過程、函數(shù)、方法這樣的程序單元統(tǒng)稱為過程。 編譯原理與技術(shù)37.1 程序運(yùn)行的基本概念過程及其活動(dòng)當(dāng)過程名出現(xiàn)在程序中作為一個(gè)語句或表達(dá)式使用時(shí)，就稱這個(gè)過程在程序點(diǎn)被調(diào)用。過程調(diào)用就是

2、執(zhí)行被調(diào)用過程的過程體。出現(xiàn)在過程定義中的參數(shù)叫做形式參數(shù)（形參），在過程調(diào)用點(diǎn)取代形參的稱為實(shí)在參數(shù)（實(shí)參）。 編譯原理與技術(shù)47.1 程序運(yùn)行的基本概念program sort(input, output) var a: array 0.10 of integer; procedure readarray;var i: integer; begin for i := 1 to 9 do read (ai)end; function partition (y, z: integer): integervar i, j, x, y: integer;begin.end;procrdure qu

3、icksort (m, n: integer);var i: integer;beginif ( n m ) then begin i = partition (m, n); quicksort (m, i1); quicksort (i+1, n); end;end;begin a0 := 9999; a10 := 9999; readarray; quicksort(1, 9);end;編譯原理與技術(shù)57.1 程序運(yùn)行的基本概念過程的活動(dòng)過程的每次調(diào)用就引起過程體的一次執(zhí)行，稱為過程的一次活動(dòng)。過程p的一個(gè)活動(dòng)的生存期就是從過程體開始執(zhí)行到執(zhí)行結(jié)束的時(shí)間，包括執(zhí)行被P調(diào)用其它所有過程所耗費(fèi)

4、的時(shí)間。一般而言，術(shù)語“生存期”指的是程序執(zhí)行過程中若干步驟的一個(gè)連續(xù)序列。編譯原理與技術(shù)67.1 程序運(yùn)行的基本概念過程的活動(dòng)任何兩個(gè)過程的活動(dòng)p和q只能存在下列關(guān)系：不重疊或者嵌套。過程的活動(dòng)p和q不重疊，指的是它們的執(zhí)行時(shí)間（生存期）沒有重疊；活動(dòng)p嵌套在活動(dòng)q，指的是活動(dòng)q的生存期包括了活動(dòng)p的生存期。兩個(gè)過程活動(dòng)p和q的關(guān)系表明，若程序的執(zhí)行控制在退出q之前進(jìn)入了p，則必須在退出q之前退出p。如果同一個(gè)過程的兩個(gè)不同活動(dòng)p和q重疊，即在該過程的活動(dòng)p沒有退出之前又重新另外一個(gè)活動(dòng)q，這樣的過程稱為遞歸過程。同一個(gè)過程的不同調(diào)用產(chǎn)生不同的活動(dòng)。 編譯原理與技術(shù)77.1 程序運(yùn)行的基本概

5、念活動(dòng)記錄過程的一次執(zhí)行要用一塊連續(xù)的存儲(chǔ)區(qū)來管理需要的信息，這塊存儲(chǔ)區(qū)叫做活動(dòng)記錄或幀。 返回值實(shí)在參數(shù)（可選）控制鏈（可選）訪問鏈機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值域：用于存放被調(diào)用過程返回給調(diào)用過程的值，根據(jù)不同的參數(shù)傳遞機(jī)制，返回值可以是數(shù)值或指向返回值地址的指針。實(shí)參域：用于存放調(diào)用過程提供的實(shí)在參數(shù)，根據(jù)不同的形參和實(shí)參的傳遞機(jī)制，實(shí)參域可以是數(shù)值或指向?qū)崊⒌刂返闹羔??？刂奇溣颍褐赶蛘{(diào)用者活動(dòng)記錄的指針，也稱為動(dòng)態(tài)鏈。訪問鏈域：對于像Pascal這樣的語言，需要訪問鏈來訪問非局部數(shù)據(jù)；對于FROTRAN和C則不需要，訪問鏈又稱靜態(tài)鏈。機(jī)器狀態(tài)域：保存該過程調(diào)用前的機(jī)器狀態(tài)信息，包括程序

6、計(jì)數(shù)器（pc）的值以及控制從該過程返回時(shí)必須恢復(fù)的機(jī)器寄存器的值。局部數(shù)據(jù)：存儲(chǔ)用于該過程執(zhí)行時(shí)的數(shù)據(jù)。臨時(shí)數(shù)據(jù)：保存該過程執(zhí)行時(shí)臨時(shí)的數(shù)據(jù)，如表達(dá)式的中間結(jié)果。 編譯原理與技術(shù)87.1 程序運(yùn)行的基本概念調(diào)用序列和返回序列調(diào)用序列，操作如 活動(dòng)記錄分配存儲(chǔ)空間；計(jì)算并存儲(chǔ)參數(shù)值；為調(diào)用分配并存儲(chǔ)影響調(diào)用的存儲(chǔ)器。 返回序列，操作如把返回值放到調(diào)用者可以訪問到的位置；恢復(fù)機(jī)器狀態(tài)；調(diào)整寄存器；釋放活動(dòng)記錄的存儲(chǔ)。編譯原理與技術(shù)97.1 程序運(yùn)行的基本概念活動(dòng)樹 每個(gè)結(jié)點(diǎn)代表過程的一個(gè)活動(dòng)記錄（調(diào)用）；根結(jié)點(diǎn)代表主程序；結(jié)點(diǎn)p是結(jié)點(diǎn)q的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從p的活動(dòng)進(jìn)入q的活動(dòng)；在同一層中，結(jié)

7、點(diǎn)p在結(jié)點(diǎn)q的左邊，當(dāng)且僅當(dāng)p的生存期先于q的生存期。編譯原理與技術(shù)107.1 程序運(yùn)行的基本概念例7.1 假如執(zhí)行圖7.1的程序，我們可以構(gòu)造出程序執(zhí)行期間的所有過程的活動(dòng)記錄，表示整個(gè)程序運(yùn)行的蹤跡，如圖7.3所示。樹根是主程序sort的活動(dòng)記錄，它首先調(diào)用了readarray和quisksort(1, 9)，按照程序的執(zhí)行順序，readarray在quisksort(1, 9)之前，即readarray的生存期先于在quisksort(1, 9)，所以，結(jié)點(diǎn)ra在qs(1, 9)的左邊。qs(1, 9)又調(diào)用了一次partition和兩次quisksort，圖中顯示的結(jié)點(diǎn)分別是pt(1,

8、 9)，qs(1, 3)和qs(5, 9)。注意，qs(1, 3)和qs(5, 9)都是遞歸調(diào)用，它們在quisksort(1, 9)結(jié)束之前結(jié)束。sortraqs(1, 9)qs(1, 3)pt(1, 9)qs(5, 9)qs(1, 0)pt(1, 3)qs(2, 3)qs(5, 5)pt(5, 9)qs(7, 9)qs(7, 7)pt(7, 9)qs(9, 9)qs(2, 1)pt(2, 3)qs(3, 3)編譯原理與技術(shù)117.1 程序運(yùn)行的基本概念名字的綁定和環(huán)境 按照程序設(shè)計(jì)語言的語義，環(huán)境表示把一個(gè)名字映射到一個(gè)存儲(chǔ)位置的函數(shù)，狀態(tài)表示把存儲(chǔ)單元映射到所保存的值的函數(shù)環(huán)境把名字映射

9、到左值，狀態(tài)把左值映射到右值。環(huán)境和狀態(tài)是有區(qū)別的：賦值改變狀態(tài)，但不改變環(huán)境。例如，和假設(shè)存儲(chǔ)單元100關(guān)聯(lián)的變量pi記錄的值是0。在賦值語句pi := 3.14之后，同樣是關(guān)聯(lián)pi的存儲(chǔ)單元的值就變成了3.14。如果環(huán)境把名字x映射到存儲(chǔ)單元s，就說x被綁定到s。術(shù)語存儲(chǔ)單元是象征性的，因?yàn)槿绻鹸不是一個(gè)基本類型，那么x的存儲(chǔ)單元s可能是一組存儲(chǔ)單元。編譯原理與技術(shù)127.2 參數(shù)傳遞機(jī)制按值調(diào)用實(shí)參在調(diào)用時(shí)刻計(jì)算得到的表達(dá)式，其值就是過程執(zhí)行時(shí)形參的值?？梢匀缦聦?shí)現(xiàn)：（1）把形參當(dāng)作所在過程的局部變量名看待，形參的存儲(chǔ)單元在該過程的活動(dòng)記錄中；（2）調(diào)用過程計(jì)算實(shí)參，并把值放入形參的存儲(chǔ)

10、單元中。它的最簡單形式可以解釋成值參數(shù)在過程的執(zhí)行中作為常數(shù)值，取代了過程體中所對應(yīng)的形式參數(shù)。C語言和Java語言使用按值調(diào)用，它們也是Pascal和Ada的缺省參數(shù)傳遞方法。編譯原理與技術(shù)137.2 參數(shù)傳遞機(jī)制按值調(diào)用把形參當(dāng)作所在過程的局部變量名看待，形參的存儲(chǔ)單元在該過程的活動(dòng)記錄中；調(diào)用過程計(jì)算實(shí)參，并把值放入形參的存儲(chǔ)單元中。 被調(diào)用過程的活動(dòng)記錄 . 形參1 形參2.調(diào)用序列在調(diào)用點(diǎn)計(jì)算實(shí)參1的值計(jì)算實(shí)參2的值把值分別送入形參圖7.5 按值調(diào)用示意圖按值調(diào)用的顯著特征是，對形參的任何運(yùn)算都不會(huì)影響調(diào)用者的實(shí)參的值。編譯原理與技術(shù)147.2 參數(shù)傳遞機(jī)制按值調(diào)用下列程序inc1不

11、會(huì)達(dá)到它期望的效果：void inc1 (int x)/* 不正確的程序 */ +x; return x; 在C語言中，需要傳遞地址來實(shí)現(xiàn)上述預(yù)想的效果：void inc1 (int* x)/* 正確的程序 */ +(*x); return *x; 當(dāng)然，希望對變量y增值時(shí)，這個(gè)函數(shù)的調(diào)用形式為inc1(&y)，因?yàn)楹瘮?shù)需要的是y的地址而不是值。編譯原理與技術(shù)157.2 參數(shù)傳遞機(jī)制引用調(diào)用（傳地址調(diào)用）（1）如果實(shí)參是變量或具有左值的表達(dá)式，則把該左值放入形參的存儲(chǔ)單元； 2. 如果實(shí)參是3或3a這樣沒有左值的表達(dá)式，則首先把它的計(jì)算值存入到一個(gè)新的存儲(chǔ)單元，然后把這個(gè)地址傳遞給形參。（2）

12、在被調(diào)用過程的目標(biāo)代碼中，對形參的任何引用都是通過形參存儲(chǔ)的地址間接引用實(shí)參的。被調(diào)用過程的活動(dòng)記錄 . 形參1 形參2.調(diào)用序列在調(diào)用點(diǎn)實(shí)參1的地址計(jì)算實(shí)參2的值并存入臨時(shí)變量t把t的地址圖7.6 引用調(diào)用示意圖引用調(diào)用的顯著特征是，對形參的任何運(yùn)算都直接影響調(diào)用者的實(shí)參 編譯原理與技術(shù)167.2 參數(shù)傳遞機(jī)制引用調(diào)用（傳地址調(diào)用）在Pascal中，引用調(diào)用是通過在過程聲明中使用關(guān)鍵字“var”實(shí)現(xiàn)的；C和C+在過程聲明中使用地址符號“&”實(shí)現(xiàn)參數(shù)的引用調(diào)用，例如：void inc1 (int &x)/* 正確的程序 */ +x; return x; 這個(gè)函數(shù)可以直接調(diào)用，不必使用地址操作符

13、：inc1(y)就可以使變量y的值增加。 編譯原理與技術(shù)177.2 參數(shù)傳遞機(jī)制值結(jié)果調(diào)用(復(fù)寫恢復(fù),復(fù)寫入復(fù)寫)（1）調(diào)用過程把實(shí)參的值和實(shí)參的地址同時(shí)傳給被調(diào)用過程；（2）被調(diào)用過程像按值調(diào)用那樣使用傳遞給形參的值；（3）把形參在被調(diào)用過程中最后的值拷貝到實(shí)參的存儲(chǔ)單元內(nèi)。被調(diào)用過程的活動(dòng)記錄 . 形參1 實(shí)參1的地址形參2調(diào)用序列在調(diào)用點(diǎn)計(jì)算實(shí)參1的值實(shí)參1的地址圖7.7 值結(jié)果調(diào)用示意圖 實(shí)參2的地址.計(jì)算實(shí)參2的值實(shí)參2的地址下列（按照C的語法格式）代碼：void p( int x, int y) +x; +y; main () int a = 1; p(a, a); return

14、a; 如果參數(shù)傳遞使用引用調(diào)用的方式，在調(diào)用p之后a的值是3；如果使用值結(jié)果調(diào)用的方式，a的值則是2。編譯原理與技術(shù)187.2 參數(shù)傳遞機(jī)制換名調(diào)用實(shí)參直到在被調(diào)用的過程中作為形參實(shí)際使用的時(shí)候才計(jì)算，所以也叫延遲計(jì)算。換名調(diào)用可以如下實(shí)現(xiàn)：（1）在調(diào)用點(diǎn)，用被調(diào)用過程的體來替換調(diào)用者的調(diào)用，但是形參用對應(yīng)的實(shí)參來替換。這種文字替換方式成為宏展開或內(nèi)聯(lián)展開。（2）在宏展開前，被調(diào)用過程的每個(gè)局部變量名字被系統(tǒng)地重新命名可以區(qū)別的名字。編譯原理與技術(shù)197.2 參數(shù)傳遞機(jī)制例如， 對于代碼void p(int x) +x; 如果出現(xiàn)了p(ai)這樣的調(diào)用，其效果就是+(ai)。所以，如果i在過程

15、p內(nèi)的變量x之前改變了值，結(jié)果將既不同于引用調(diào)用，也不同于值結(jié)果調(diào)用。編譯原理與技術(shù)207.2 參數(shù)傳遞機(jī)制例7.2 考慮下列（C語法格式的）代碼：int i;int a10;void p(int x) +i; +x; main() i = 1;a1 = 1;a2 = 5;p(ai);采用按值調(diào)用的參數(shù)傳遞機(jī)制，調(diào)用過程p：盡管在過程p中改變了i的值為2，但a2的值不變；a1的值仍然為1。采用按值調(diào)用的參數(shù)傳遞機(jī)制，調(diào)用過程p不改變a1和a2的值。采用引用調(diào)用和值結(jié)果的參數(shù)傳遞機(jī)制，調(diào)用過程p的結(jié)果一樣，都是把a(bǔ)1的值改變?yōu)?，而沒改變a2的值。（但是，如果采用值結(jié)果參數(shù)傳遞機(jī)制的另外一種實(shí)現(xiàn)

16、，在復(fù)寫出形參值的時(shí)候重新計(jì)算對應(yīng)實(shí)參的地址，那么，調(diào)用過程p的結(jié)果把a(bǔ)2設(shè)置為2，保持a1的值不變。）采用換名參數(shù)傳遞機(jī)制，調(diào)用過程p的結(jié)果是把a(bǔ)2設(shè)置為6并保持a1的值不變。編譯原理與技術(shù)217.2 參數(shù)傳遞機(jī)制例7.2 考慮下列（C語法格式的）代碼：int i;int a10;void p(int x) +i; +x; main() i = 1;a1 = 1;a2 = 5;p(ai);在這個(gè)程序中，由于i對于 p是非局部變量，無論哪種參數(shù)傳遞方式都在p中改變了值為2。但是，其它變量的結(jié)果隨著參數(shù)傳遞機(jī)制的不同而有差異。采用按值調(diào)用的參數(shù)傳遞機(jī)制，調(diào)用過程p：盡管在過程p中改變了i的值為2

17、，但a2的值不變；語句+x的效果相當(dāng)于+(a1)，調(diào)用沒有把改變的值送回a1，即a1的值仍然為1。采用引用調(diào)用的參數(shù)傳遞機(jī)制，調(diào)用過程p時(shí)把參數(shù)a1的地址傳遞給p的活動(dòng)記錄中對應(yīng)的形式單元x，執(zhí)行p的結(jié)果是a1 值增加1，為2。采用值結(jié)果的參數(shù)傳遞機(jī)制，調(diào)用過程p：把a(bǔ)1的值（此時(shí)為1）傳給p的活動(dòng)記錄中對應(yīng)的形式單元x，再把a(bǔ)1的地址傳給對應(yīng)x的作為地址的形式單元addr；執(zhí)行p的語句之后，x的值增加1為2，它作為x的最終值通過addr送入a1內(nèi)，而a2的值保持不變。采用換名的參數(shù)傳遞機(jī)制，調(diào)用過程p把語句+x替換成+(ai)，a2設(shè)置為6，但沒改變a1的值。 編譯原理與技術(shù)227.2 參數(shù)

18、傳遞機(jī)制換名調(diào)用與內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)展開可以縮短程序的運(yùn)行時(shí)間這是因?yàn)?，過程活動(dòng)的建立包括活動(dòng)記錄的空間分配、機(jī)器狀態(tài)的保存、調(diào)用數(shù)據(jù)的傳遞以及控制的轉(zhuǎn)移等，都需要占用機(jī)器的資源。若過程體較小，則過程調(diào)用序列的代碼可能會(huì)超過過程體本身的代碼。如果把過程體的代碼內(nèi)聯(lián)展開到調(diào)用者的代碼中，即使程序的代碼會(huì)稍長一些，程序的執(zhí)行速度也會(huì)提高。對于諸如Java和C#這樣的面向?qū)ο笳Z言，內(nèi)聯(lián)函數(shù)還可以減少在程序運(yùn)行時(shí)消息和函數(shù)體的動(dòng)態(tài)查找和聯(lián)編。內(nèi)聯(lián)函數(shù)產(chǎn)生了更大的代碼塊，使得代碼優(yōu)化技術(shù)的應(yīng)用更加方便。編譯原理與技術(shù)237.2 參數(shù)傳遞機(jī)制換名調(diào)用與內(nèi)聯(lián)函數(shù)例如，下面的C+函數(shù)讀入一行字符串，逐個(gè)判斷是否為數(shù)

19、字字符：isNumber (char ch) rerurn ch = 0 & ch = 9 ?1: 0; 這個(gè)函數(shù)本身的代碼很短，程序頻繁調(diào)用該函數(shù)所花費(fèi)的時(shí)間卻很多，從而降低了程序的執(zhí)行效率。C+提供了內(nèi)聯(lián)函數(shù)的機(jī)制，把上面的函數(shù)可以改為：inline isNumber (char ch)這樣就既保證了程序的可讀性，又提高了程序的執(zhí)行效率。編譯原理與技術(shù)247.3 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理局部數(shù)據(jù)的存放編譯對一個(gè)過程所聲明的局部變量按照它們的聲明順序，在活動(dòng)記錄的局部數(shù)據(jù)域中依次分配存儲(chǔ)空間。這些局部數(shù)據(jù)的地址可以相對于一個(gè)特殊的位置，譬如活動(dòng)記錄的開始地址，用相對地址來表示。相對地址（偏

20、移）就是數(shù)據(jù)對象和這個(gè)基準(zhǔn)位置的地址差?；顒?dòng)記錄中其它域的訪問也可以用相對于這個(gè)位置的相對地址來處理。編譯原理與技術(shù)257.3 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理運(yùn)行時(shí)存儲(chǔ)空間的劃分代碼為了使目標(biāo)代碼能夠運(yùn)行，編譯程序必須從系統(tǒng)中申請一塊存儲(chǔ)區(qū)域，分配給目標(biāo)代碼。典型的計(jì)算機(jī)存儲(chǔ)包括快速運(yùn)算域訪問的寄存器區(qū)域和比較慢的隨機(jī)訪問存儲(chǔ)（RAM），而RAM又可以劃分成為代碼區(qū)和數(shù)據(jù)區(qū)。對大多數(shù)需要編譯的語言，程序運(yùn)行 的時(shí)候不能改變程序的存儲(chǔ)區(qū)域，而且， 代碼區(qū)域和數(shù)據(jù)區(qū)域在概念上被認(rèn)為是 分離的。因?yàn)榇a區(qū)域在運(yùn)行前就已經(jīng)確定，所有的代碼地址在編譯時(shí)都可以計(jì)算出來。 過程1的代碼 過程2的代碼 . 過程n

21、的代碼 過程1的入口點(diǎn) 過程2的入口點(diǎn) 過程n的入口點(diǎn) .圖7.8 代碼區(qū)域編譯原理與技術(shù)267.3 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理運(yùn)行時(shí)存儲(chǔ)空間的劃分整個(gè)程序靜態(tài)數(shù)據(jù)可以象代碼一樣在編譯時(shí)刻分配地址。動(dòng)態(tài)數(shù)據(jù)的典型組織包括把存儲(chǔ)空間劃分為棧式數(shù)據(jù)區(qū)域和堆式數(shù)據(jù)區(qū)域。存儲(chǔ)分配的重要單元是過程的活動(dòng)記錄。根據(jù)語言特性，活動(dòng)記錄可以分配在靜態(tài)區(qū)域（如FORTRAN）、棧式數(shù)據(jù)區(qū)（C和Pascal）或者堆式數(shù)據(jù)區(qū)（Lisp語言）。 圖7.9 運(yùn)行時(shí)存儲(chǔ)空間的劃分 代碼區(qū)域 全局/靜態(tài)數(shù)據(jù)區(qū)域 棧式數(shù)據(jù)區(qū)域 堆式數(shù)據(jù)區(qū)域編譯原理與技術(shù)277.3 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理存儲(chǔ)分配要考慮的問題過程能否遞歸；

22、當(dāng)控制從過程的活動(dòng)返回時(shí)，是否需要保留局部變量的值；過程能否訪問非局部變量，如何有效地訪問；過程調(diào)用時(shí)形參和實(shí)參的傳遞方式；過程能否作為參數(shù)傳遞和結(jié)果返回；存儲(chǔ)區(qū)域能否在程序控制下動(dòng)態(tài)地分配；存儲(chǔ)區(qū)域能否在程序控制下顯示地回收。編譯原理與技術(shù)287.3 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理3種常見的存儲(chǔ)分配策略靜態(tài)存儲(chǔ)分配、棧式動(dòng)態(tài)存儲(chǔ)分配和堆式動(dòng)態(tài)分配存儲(chǔ)靜態(tài)存儲(chǔ)分配在程序編譯的時(shí)后就把數(shù)據(jù)對象分配在固定的存儲(chǔ)單元，且在運(yùn)行時(shí)始終保持不變。語言要求不含遞歸過程，不允許體積改變的數(shù)據(jù)對象和待定性質(zhì)的名字。FORTRAN語言的編譯程序可以采用靜態(tài)存儲(chǔ)分配策略。棧式動(dòng)態(tài)存儲(chǔ)分配 存儲(chǔ)器作為一個(gè)棧來管理，每當(dāng)

23、一個(gè)過程被激活和調(diào)用，程序就動(dòng)態(tài)地為這個(gè)過程在棧的頂部分配存儲(chǔ)區(qū)域，一旦過程執(zhí)行結(jié)束，就釋放所占用的存儲(chǔ)空間。這種策略適合那些允許過程嵌套的語言，如Pascal、Ada等。堆式動(dòng)態(tài)存儲(chǔ)分配則在程序運(yùn)行時(shí)把存儲(chǔ)器作為一個(gè)堆來管理，以便程序管理存儲(chǔ)的申請和回收。對于允許遞歸過程的Pascal、Ada、C、C#和Java等語言，編譯無法預(yù)先確定哪些遞歸過程在運(yùn)行時(shí)被激活，也不能確定它們的遞歸深度，而對每個(gè)過程都需要為其活動(dòng)記錄分配新的存儲(chǔ)空間。此外，程序員在程序中動(dòng)態(tài)地申請和釋放存儲(chǔ)空間，存儲(chǔ)空間申請和釋放的順序隨意，并不遵守先申請先釋放的隊(duì)列原則或后先請后釋放棧的原則。因此，這些語言還需要采用更復(fù)

24、雜的動(dòng)態(tài)堆式存儲(chǔ)分配策略。 編譯原理與技術(shù)297.4 靜態(tài)運(yùn)行時(shí)環(huán)境 FORTRAN是這種分配策略的典型語言。在這種運(yùn)行時(shí)環(huán)境中，不僅全局變量、而是所有變量都可以在編譯時(shí)分配存儲(chǔ)。此外，每個(gè)過程只有一個(gè)活動(dòng)記錄，它可以在程序運(yùn)行前靜態(tài)地分配存儲(chǔ)。所有變量，無論是全局的還是局部的，都可以通過固定的地址訪問。主程序的代碼過程1的代碼.過程n的代碼全局?jǐn)?shù)據(jù)區(qū)域主程序的活動(dòng)記錄過程1的活動(dòng)記錄.過程n的活動(dòng)記錄代碼區(qū)域數(shù)據(jù)區(qū)域圖7.10 靜態(tài)存儲(chǔ)分配結(jié)構(gòu)在這種運(yùn)行時(shí)環(huán)境中，活動(dòng)記錄的信息簿記工作和調(diào)用序列十分簡單。調(diào)用過程的時(shí)候，就計(jì)算每個(gè)實(shí)參并不它們放到被調(diào)用過程活動(dòng)記錄中相應(yīng)的形參的位置，然后保留

25、調(diào)用者的返回地址，生成一個(gè)到被調(diào)用過程起始的跳轉(zhuǎn)指令。返回時(shí)就需要一個(gè)簡單的到返回地址的跳轉(zhuǎn)指令。 編譯原理與技術(shù)307.4 靜態(tài)運(yùn)行時(shí)環(huán)境 例7.3 圖7.11是一個(gè)FORTRAN程序，它計(jì)算并打印一個(gè)表中實(shí)數(shù)的平均值。它只有一個(gè)主程序和一個(gè)子程序QUADMEAN，唯一一個(gè)全局變量是分別在主程序和QUADMEAN聲明的MAXSIZE，程序還調(diào)用了庫函數(shù)SORT。 PROGRAM TESTCOMMON MAXSIZEINTEGER MAXSIZEREAL TABLE(10), TEMPMAXSIZE = 10READ *, TABLE(1), TABLE(2), TABLE(3)CALL QU

26、ADMEAN(TABLE, 3, TEMP)PRINT *, TEMPEND SUBROUTIN QUADMEAN(A, SIZE, QMEAN) COMMON MAXSIZE INTEGER MAXSIZE, SIZE REAL A(SIZE), QMEAN, TEMP INTEGER K TEMP = 0.0 IF (SIZE.GT.MAXSIZE).OR.(SIZE.LT.1) GOTO 99 DO 10 K = 1, SIZE10TEMP = TEMP + A(K)*A(K)99 CONTINUE QMEAN = SORT(TEMP/SIZE) RETURN END編譯原理與技術(shù)317

27、.4 靜態(tài)運(yùn)行時(shí)環(huán)境這個(gè)程序的運(yùn)行時(shí)環(huán)境可以如圖7.12所示。其中箭頭連線表示過程QUADMEAN的三個(gè)參數(shù)A、SIZE和QMEAN的值在調(diào)用過程中從主程序拷貝得到，這是由于FORTRAN語言的參數(shù)傳遞是隱含的存儲(chǔ)引用，所以把它們的地址賦值到被調(diào)用的QUADMEAN中。QUADMEAN活動(dòng)記錄中的臨時(shí)變量用來存放計(jì)算TEMP+A(K)*A(K)或者TEMP/SIZE的值。如果沒有足夠的寄存器來存放臨時(shí)值，或者有一個(gè)調(diào)用要求保留這個(gè)值，那么，在完成計(jì)算之前要把該值存儲(chǔ)在活動(dòng)記錄中。編譯程序根據(jù)目標(biāo)機(jī)器的體系結(jié)構(gòu)（如寄存器的個(gè)數(shù)和使用規(guī)則）可以確定運(yùn)行時(shí)是否需要存放臨時(shí)變量的存儲(chǔ)，并安排大小合適的

28、臨時(shí)存儲(chǔ)單元。全局?jǐn)?shù)據(jù)主程序的活動(dòng)記錄QUADMEAN的活動(dòng)記錄MAXSIZETEMP3ASIZEQMEAN返回地址TEMPK臨時(shí)變量TABLE(1)TABLE(2)TABLE(10)編譯原理與技術(shù)327.5 棧式運(yùn)行時(shí)環(huán)境 如果一個(gè)語言允許過程遞歸調(diào)用，而且每次調(diào)用都重新分配局部變量，活動(dòng)記錄就不可能靜態(tài)地分配。這樣，活動(dòng)記錄可以基于棧結(jié)構(gòu)進(jìn)行分配，每一個(gè)新的過程調(diào)用都需要把一個(gè)新的活動(dòng)記錄放在棧頂，在過程執(zhí)行退出以后就再回收這個(gè)活動(dòng)記錄的存儲(chǔ)單元?；顒?dòng)記錄棧（又叫運(yùn)行?；蛘{(diào)用棧）在程序的執(zhí)行過程中隨著調(diào)用鏈增長和縮減。又分成無過程嵌套的棧式運(yùn)行時(shí)環(huán)境 和有過程嵌套的棧式運(yùn)行時(shí)環(huán)境。 編譯原

29、理與技術(shù)337.5.1 無過程嵌套的棧式運(yùn)行時(shí)環(huán)境在這類語言中，例如C，過程都是全局過程，不允許嵌套，但是允許遞歸調(diào)用。這樣的運(yùn)行時(shí)環(huán)境需要兩類信息：維護(hù)指向當(dāng)前活動(dòng)記錄的指針以便訪問局部變量;記錄直接調(diào)用者的位置或大小以便當(dāng)前調(diào)用結(jié)束后恢復(fù)調(diào)用者的活動(dòng)記錄。指向當(dāng)前活動(dòng)記錄的指針通常稱為幀指針sp，保存在一個(gè)寄存器中（就叫sp）。前一個(gè)活動(dòng)記錄通常用一個(gè)存放在當(dāng)前活動(dòng)記錄中稱為控制鏈的指針訪問。這個(gè)指針又叫動(dòng)態(tài)鏈，因?yàn)樗窃诔绦蜻\(yùn)行時(shí)指向調(diào)用程序的活動(dòng)記錄；又稱為老的幀指針，因?yàn)樗淼牧藄p的前一個(gè)值。 編譯原理與技術(shù)347.5.1 無過程嵌套的棧式運(yùn)行時(shí)環(huán)境例7.3 一個(gè)計(jì)算兩個(gè)非負(fù)數(shù)最

30、大公因子的歐幾理德算法的遞歸程序gcd，代碼如圖7.13(a)。假設(shè)輸入了15和10，main開始調(diào)用gcd(15, 10)，它的第二次調(diào)用gcd(10, 5)，接著是第三次調(diào)用gcd(5, 0)并且返回5。第三次調(diào)用的運(yùn)行時(shí)環(huán)境如圖7.13(b)所示。每次調(diào)用gcd都在棧頂新增一個(gè)大小一樣的活動(dòng)記錄，而且在這個(gè)活動(dòng)記錄中都有控制鏈指向調(diào)用它的前一個(gè)活動(dòng)記錄。幀指針fp指向當(dāng)前活動(dòng)記錄的控制鏈，這樣，在下一次調(diào)用時(shí)（比如第4次調(diào)用），這個(gè)fp就成為下一個(gè)活動(dòng)記錄的控制鏈的目的地址。每次調(diào)用gcd完成過程體的動(dòng)作之后，每個(gè)gcd的活動(dòng)記錄都從棧頂移出。當(dāng)執(zhí)行main中打印語句pringf的時(shí)候，

31、存儲(chǔ)器中只剩下main的活動(dòng)記錄和全局/靜態(tài)數(shù)據(jù)。#include int m, n;int gcd (int u, v) if ( v = 0 ) return u;else return gcd (v, u%v);main()scanf(“%d%d”, &m, &n);printf(“%dn”, gcd(m, n);return 編譯原理與技術(shù)357.5.1 無過程嵌套的棧式運(yùn)行時(shí)環(huán)境 m: 15 n: 10 u: 15 v: 10控制鏈 返回地址 u: 10 v: 5控制鏈 返回地址 u: 5 v: 0控制鏈 返回地址 自由空間全局/靜態(tài)區(qū)域main的活動(dòng)記錄第1次調(diào)用gcd時(shí)的活動(dòng)記錄

32、第2次調(diào)用gcd時(shí)的活動(dòng)記錄第3次調(diào)用gcd時(shí)的活動(dòng)記錄sp假設(shè)輸入了15和10，main開始調(diào)用gcd(15, 10)，它的第二次調(diào)用gcd(10, 5)，接著是第三次調(diào)用gcd(5, 0)并且返回5。第三次調(diào)用的運(yùn)行時(shí)環(huán)境如圖7.13(b)所示。每次調(diào)用gcd都在棧頂新增一個(gè)大小一樣的活動(dòng)記錄，而且在這個(gè)活動(dòng)記錄中都有控制鏈指向調(diào)用它的前一個(gè)活動(dòng)記錄。幀指針fp指向當(dāng)前活動(dòng)記錄的控制鏈，這樣，在下一次調(diào)用時(shí)（比如第4次調(diào)用），這個(gè)fp就成為下一個(gè)活動(dòng)記錄的控制鏈的目的地址。每次調(diào)用gcd完成過程體的動(dòng)作之后，每個(gè)gcd的活動(dòng)記錄都從棧頂移出。當(dāng)執(zhí)行main中打印語句pringf的時(shí)候，存儲(chǔ)

33、器中只剩下main的活動(dòng)記錄和全局/靜態(tài)數(shù)據(jù)。fp編譯原理與技術(shù)367.5.1 無過程嵌套的棧式運(yùn)行時(shí)環(huán)境名字的訪問在棧式環(huán)境中，參數(shù)和局部變量不能通過固定的地址訪問，而必須依據(jù)它們和當(dāng)前活動(dòng)記錄的位差來定位。在大多數(shù)語言中，過程聲明在編譯時(shí)確定并且分配給每個(gè)局部聲明的存儲(chǔ)大小，按照數(shù)據(jù)類型是固定的，所以，每個(gè)局部聲明的位差可以由編譯程序計(jì)算出來。編譯原理與技術(shù)377.5.1 無過程嵌套的棧式運(yùn)行時(shí)環(huán)境例7.4 考慮下列C程序void f(int x, char c) int a10; double y; 調(diào)用過程f的活動(dòng)記錄如圖所示。假設(shè)整型占2個(gè)字節(jié)，地址用4個(gè)字節(jié)，字符型用1個(gè)字節(jié)，雙精

34、度浮點(diǎn)型占8個(gè)字節(jié)，棧向下增長，那么，就可以在編譯時(shí)刻得到每個(gè)局部變量的位移值。這樣，假訪問ai就需要按照下列公式計(jì)算地址：(242i)(fp)。根據(jù)i的位置和機(jī)器的體系結(jié)構(gòu)，這樣的存儲(chǔ)訪問可能只需一條機(jī)器指令。 x c 控制鏈 返回地址 a9 a8 . a0 y x的偏移量 y的偏移量 a的偏移量 c的偏移量 fp圖7.14 例7.4調(diào)用過程f的活動(dòng)記錄 名字 偏移量 x +5 c +4 a -24 y -32編譯原理與技術(shù)387.5.1 無過程嵌套的棧式運(yùn)行時(shí)環(huán)境臨時(shí)局部量臨時(shí)變量是在整個(gè)過程調(diào)用中存放計(jì)算的中間結(jié)果的變量。例如，C語言的表達(dá)式ai = (i + j) (i/k + f(j

35、)，在自左向右的計(jì)算中需要臨時(shí)存儲(chǔ)下列結(jié)果：ai的地址、和i + j 以及i/k。這些臨時(shí)結(jié)果可以存放在寄存器中，或者在調(diào)用f以前存放在運(yùn)行棧的作的臨時(shí)單元。由于臨時(shí)變量的個(gè)數(shù)和類型可以事先確定，它們的訪問也可以在編譯時(shí)按照局部變量的方式進(jìn)行。 編譯原理與技術(shù)397.5.1 無過程嵌套的棧式運(yùn)行時(shí)環(huán)境嵌套聲明例7.5 考慮C語言的代碼：viod p( int x, double y) char a; int i;A: double x; int j; B: char *a; int k;在上面的代碼中，位于塊A上的變量j到過程p的fp的偏移量是17，塊B中k的偏移量是13（假設(shè)整型數(shù)占2個(gè)字節(jié)

36、，地址占4個(gè)字節(jié)，字符型占1個(gè)字節(jié)，雙精度浮點(diǎn)型占8個(gè)字節(jié)）。 x y 控制鏈 返回地址 a i x j 自由區(qū)域調(diào)用p時(shí)的活動(dòng)記錄為塊A分配的區(qū)域spfp x y 控制鏈 返回地址 a i a k 自由區(qū)域調(diào)用p時(shí)的活動(dòng)記錄為塊B分配的區(qū)域spfp圖7.12(a) 進(jìn)入過程p中塊A的活動(dòng)記錄圖7.15(b) 進(jìn)入過程p中塊B的活動(dòng)記錄編譯原理與技術(shù)407.5.2 有過程嵌套的棧式運(yùn)行時(shí)環(huán)境 例7.6 考慮下面的Pascal語言的程序。program nonLocalRef;procedure p;var n: integer;procedure q;begin (* 對變量n的任何引用就是非

37、局部、非全局的*)end;procedure r(n: integer);begin q;end;begin (* 開始過程q *) n := 1; r(2);end;begin (* 開始主程序 *)p;end;在Pascal、Ada等語言中，由于過程允許嵌套聲明，非局部名字不一定就是全局的。如果程序語言允許過程聲明的嵌套，那么，截至目前所描述的運(yùn)行時(shí)環(huán)境由于沒有提供訪問非局部、非全局名字的手段，其效率而顯得不高。編譯原理與技術(shù)417.5.2 有過程嵌套的棧式運(yùn)行時(shí)環(huán)境調(diào)用過程q時(shí)的運(yùn)行棧如圖7.16所示.在q內(nèi)任何對n的引用都必須引用p的局部變量n。但是，在這個(gè)程序中，僅僅依靠如圖所示的運(yùn)

38、行棧，編譯不能通過確定的偏移量找到在q內(nèi)引用的n的具體聲明，因?yàn)閚在過程r和p中的偏移量不同。因此還需要區(qū)別名字作用域的定義規(guī)則。 自由空間 返回地址 n: 1 n: 2 返回地址 返回地址主程序的活動(dòng)記錄調(diào)用p時(shí)的活動(dòng)記錄調(diào)用r時(shí)的活動(dòng)記錄調(diào)用q時(shí)的活動(dòng)記錄fpsp控制鏈控制鏈控制鏈圖7.16 Pascal程序沒有訪問鏈的運(yùn)行棧編譯原理與技術(shù)427.5.2 有過程嵌套的棧式運(yùn)行時(shí)環(huán)境用靜態(tài)鏈訪問非局部量 解決上述靜態(tài)作用域問題的途徑是在每個(gè)活動(dòng)記錄中增加訪問鏈（又稱為靜態(tài)鏈）來記錄額外的信息。訪問鏈指向過程定義環(huán)境的活動(dòng)記錄，即指向直接外層的最新的活動(dòng)記錄，而不是調(diào)用環(huán)境的活動(dòng)記錄。 編譯原

39、理與技術(shù)437.5.2 有過程嵌套的棧式運(yùn)行時(shí)環(huán)境圖7.17增加了訪問鏈，這樣，在過程q內(nèi)對非局部量n的引用將按照訪問鏈到過程p，通過固定的偏移量找到。如果把訪問鏈載入一個(gè)寄存器，則可以方便地用一條指令實(shí)現(xiàn)非局部變量的訪問。例如，若寄存器r用作訪問鏈，地址占用4個(gè)字節(jié)，則它在q中的值是4 (fp)，那么，在q中就可以按照地址6 (r)訪問到在過程p中定義的變量n。注意，由于過程p是全局過程，所以它的活動(dòng)記錄中無需訪問鏈。在p中對任何非局部量的引用都可以按照全局了的訪問機(jī)制實(shí)現(xiàn)。 圖7.17 Pascal程序帶訪問鏈的運(yùn)行棧 自由空間 返回地址 n: 1 n: 2 返回地址 返回地址主程序的活動(dòng)

40、記錄調(diào)用p時(shí)的活動(dòng)記錄調(diào)用r時(shí)的活動(dòng)記錄調(diào)用q時(shí)的活動(dòng)記錄fpsp控制鏈控制鏈控制鏈無訪問鏈訪問鏈訪問鏈編譯原理與技術(shù)447.5.2 有過程嵌套的棧式運(yùn)行時(shí)環(huán)境program sort(input, output) var a: array0.10 of integer; x: integer; procedure readarray;var i: integer;begin ai end readarray ; procedure exchange (i, j: integer); begin x := ai; ai := aj; aj := x end exchange; procrdur

41、e quicksort(m, n: integer); var k, v: integer; function partition(y, z: integer): integer var i, j, x, y: integer; begin a v exchange(i, j); end partition; begin if ( n m ) thenbegin i = partition(m, n); quicksort(m, i1); quicksort(i+1, n); end; end quicksort ;begina0 := 9999;a10 := 9999;readarray;q

42、uicksort(1, 9);end sort;圖7.18 有過程嵌套Pascal語言的快速排序程序編譯原理與技術(shù)457.5.2 有過程嵌套的棧式運(yùn)行時(shí)環(huán)境按照最近的嵌套規(guī)則，在partition中出現(xiàn)的a的聲明在主程序中。同樣，在partition中調(diào)用的過程exchange對partition而言也是非局部的，它的定義首先quicksort在找，如果沒有，則在其外部過程sort中尋找。圖7.19顯示了程序運(yùn)行時(shí)棧的簡化情形，每個(gè)活動(dòng)記錄占三行：參數(shù)、訪問鏈（sort沒有訪問鏈）以及局部變量分別依次放在一行。 無訪問鏈 a, x m, n 訪問鏈 k, v sort的活動(dòng)記錄 quickso

43、rt(1,9)的活動(dòng)記錄圖7.19(a) 主程序sort調(diào)用quicksort 無訪問鏈 a, x m, n 訪問鏈 k, v sort的活動(dòng)記錄 quicksort(1,9)的活動(dòng)記錄 m, n 訪問鏈 k, v y, z 訪問鏈 i, jquicksort(1,3)的活動(dòng)記錄partition(1,3)的活動(dòng)記錄圖7.19(b) quicksort第一次遞歸調(diào)用partition，執(zhí)行exchange調(diào)用前sort的活動(dòng)記錄quicksort(1,9)的活動(dòng)記錄quicksort(1,3)的活動(dòng)記錄partition(1,3)的活動(dòng)記錄exchange(1,3)的活動(dòng)記錄 無訪問鏈 a,

44、x m, n 訪問鏈 k, v m, n 訪問鏈 k, v y, z 訪問鏈 i, j i, j 訪問鏈圖7.19(c) quicksort第一次遞歸調(diào)用partition，執(zhí)行exchange調(diào)用編譯原理與技術(shù)467.5.2 有過程嵌套的棧式運(yùn)行時(shí)環(huán)境過程quicksort的每個(gè)活動(dòng)記錄以及exchange的活動(dòng)記錄都有訪問鏈指向主程序sort，以便訪問非局部數(shù)組a和變量x。特別地，在圖7.19（c）中，過程partition活動(dòng)記錄的訪問鏈指向最靠近的quicksort的活動(dòng)記錄，即quicksort(1,3)。對于過程partition，可以通過一次訪問鏈在最近的外圍quicksort中

45、找到v的數(shù)值；而要找到變量ai的值，則首先需要通過訪問鏈找到quicksort，其中沒有a的聲明，則繼續(xù)延著quicksort的訪問鏈找到sort，通過偏移量可以訪問ai的值。為了實(shí)現(xiàn)這種嵌套的靜態(tài)作用域，編譯程序在局部地訪問名字以前必須能夠決定訪問鏈的嵌套層次。為此，需要引入聲明或過程的嵌套層次或嵌套深度的概念。通常定義最外層作用域（Pascal語言的主程序?qū)?、C語言的外部作用域）的嵌套深度為0；編譯時(shí)刻每進(jìn)入一個(gè)過程，層數(shù)就加1，過程退出時(shí)，層數(shù)就減1。例如，圖7.19中，過程sort的層數(shù)為0，變量a和x的層數(shù)是1，因?yàn)樗鼈冊谶^程sort內(nèi)部。同樣，過程quicksort的層數(shù)是1，過程

46、變量k和v以及過程partition的層數(shù)是2；partition內(nèi)變量的層數(shù)是3，exchange的層數(shù)也是3。如果引入了嵌套層數(shù)，那么訪問一個(gè)非局部量所需要的鏈接個(gè)數(shù)就是調(diào)用點(diǎn)的層數(shù)減去名字的聲明層數(shù)。例如，partition內(nèi)部引用非局部量a和v的嵌套層數(shù)分別是1和2，追蹤聲明這些變量活動(dòng)記錄的訪問鏈的次數(shù)分別就是312和321。編譯原理與技術(shù)477.5.2 有過程嵌套的棧式運(yùn)行時(shí)環(huán)境實(shí)現(xiàn)訪問鏈的調(diào)用序列相當(dāng)簡單。過程調(diào)用時(shí)，訪問鏈在fp之前存入當(dāng)前活動(dòng)記錄中；過程退出時(shí)，除了刪除訪問鏈和參數(shù)以外，還必須調(diào)整sp的值。主要問題是在過程調(diào)用時(shí)如何找到訪問鏈。這可以使用在編譯時(shí)附加在被調(diào)用過

47、程中聲明的嵌套層數(shù)來實(shí)現(xiàn)。事實(shí)上，需要做的就是生成一條訪問序列，就像要訪問被調(diào)用過程中變量一樣訪問同一嵌套層中的變量，這樣計(jì)算出來的地址就是訪問鏈。當(dāng)然，如果過程是局部的（差別在0層），那么，訪問鏈和控制鏈就相同，等于調(diào)用點(diǎn)的fp的值。 編譯原理與技術(shù)487.5.2 有過程嵌套的棧式運(yùn)行時(shí)環(huán)境用嵌套顯示表（display）訪問非局部量 如果非局部量的嵌套層次很大的時(shí)候，由于需要執(zhí)行很長的操作序列才能找到它的聲明處，用訪問鏈接來訪問非局部量的方式看起來缺乏效率。為了提高訪問非局部量的速度，可以采用一個(gè)指針數(shù)組，稱為嵌套層次顯示表（display）。每進(jìn)入一個(gè)過程后，就在它的活動(dòng)記錄中建立一個(gè)di

48、splay表，表元素的個(gè)數(shù)就是該過程嵌套層數(shù)加1。display本身采用棧的結(jié)構(gòu)，自頂向下依次存放當(dāng)前層、直接外層，直至最外層（0層，主程序）等的最新活動(dòng)記錄的基地址。由于過程的層數(shù)可以靜態(tài)地確定，所以，每個(gè)過程display表的體積可以在編譯時(shí)刻確定。這樣，從一個(gè)非局部聲明所在的靜態(tài)層數(shù)和相對于活動(dòng)記錄的偏移，就可以得到該非局部量的絕對地址：非局部量的絕對地址 = display嵌套層數(shù) +偏移offset編譯原理與技術(shù)497.5.2 有過程嵌套的棧式運(yùn)行時(shí)環(huán)境圖7.20把圖7.19的程序運(yùn)行時(shí)的環(huán)境用display表描述出來。在每個(gè)活動(dòng)記錄中訪問鏈的位置上存放一個(gè)display表，它的大小

49、可以在編譯時(shí)確定。圖中僅僅在當(dāng)前活動(dòng)記錄中列出了display表的所有元素，每個(gè)寫成i-display，表示指向第i層活動(dòng)記錄的指針。在當(dāng)前活動(dòng)記錄中還有一個(gè)指針指向調(diào)用當(dāng)前過程的最近的活動(dòng)記錄，以便過程結(jié)束后可以找到當(dāng)前過程的直接調(diào)用者的display表。圖7.20(a) 主程序sort調(diào)用quicksort圖7.20(b) quicksort第一次遞歸調(diào)用partition，執(zhí)行exchange調(diào)用前圖7.20(c) quicksort第一次遞歸調(diào)用partition，執(zhí)行exchange調(diào)用 0-display a, x m, n k, v sort的活動(dòng)記錄quicksort(1,9)

50、的活動(dòng)記錄 0-display 1-display next display sort的活動(dòng)記錄quicksort(1,9)的活動(dòng)記錄quicksort(1,3)的活動(dòng)記錄partition(1,3)的活動(dòng)記錄exchange(1,3)的活動(dòng)記錄 0-display a, x m, n display表 k, v m, n display表 k, v y, zdisplay表 i, j i, j next-display 3-display 0-display 1-display 2-display 0-display a, x m, n display表 k, v m, ndisplay表s

51、ort的活動(dòng)記錄quicksort(1,9)的活動(dòng)記錄 k, v y, z next display i, jquicksort(1,3)的活動(dòng)記錄partition(1,3)的活動(dòng)記錄 0-display 1-display 2-display編譯原理與技術(shù)507.6 堆式運(yùn)行時(shí)環(huán)境棧式運(yùn)行時(shí)環(huán)境的局限性懸掛引用 一個(gè)最簡單的情況就是要返回局部變量的地址如下列C代碼：int *dangle() int x; return &x；賦值語句addrdangle()就可能造成addr指向活動(dòng)記錄中一個(gè)不安全的位置，其值可能被隨后的任何調(diào)用隨意改變。 垃圾收集 程序員動(dòng)態(tài)地、沒有時(shí)間限制地申請數(shù)據(jù)空

52、間和回收數(shù)據(jù)空間，如指針和對象，因此，這些語言的運(yùn)行時(shí)環(huán)境也需要處理指針的分配和回收。 編譯原理與技術(shù)517.6 堆式運(yùn)行時(shí)環(huán)境堆式動(dòng)態(tài)存儲(chǔ)分配的實(shí)現(xiàn) 堆式存儲(chǔ)分配的實(shí)現(xiàn)可以按照定長塊和變長塊進(jìn)行。初始時(shí)，將堆存儲(chǔ)空間分成大小相等的若干存儲(chǔ)塊，每塊制訂一個(gè)鏈域，按照相鄰塊的順序把所有塊鏈成一個(gè)鏈表，用指針avaiable指向鏈表中的第一塊。每次分配時(shí)都首先分配指針avaiable所指的塊，然后avaiable指向鄰接的下一塊，如圖7.21(a)所示。回收后，把歸還的塊插入鏈表，如圖7.21(b)所示。占用占用占用空閑空閑空閑（a）avaiable占用空閑占用空閑空閑空閑（b）avaiable編

53、譯原理與技術(shù)527.6 堆式運(yùn)行時(shí)環(huán)境變長塊存儲(chǔ)管理需要分配長度不同的存儲(chǔ)塊，可以隨請求而變。若空閑塊鏈表中有不止一個(gè)可以滿足需要的空閑塊時(shí)，通常有三種不同的分配策略。次滿足法：只要在空閑塊鏈表中找到可以滿足需要的一個(gè)空閑塊，就進(jìn)行分配。如果該塊很大，則按申請的大小分割，剩余的部分作為空閑塊仍然留在空閑塊鏈表中；如果該塊比需要的不是大出很多，則把整個(gè)塊分配出去，以免在空閑塊鏈表中留下許多無用的小碎塊。最優(yōu)滿足法：這個(gè)方法通常將空閑塊鏈表中的空閑塊按照塊的體積從小到大排序。分配時(shí)只需將空閑塊鏈表中第一個(gè)大于申請塊大小的空閑塊分配，這就是一個(gè)不小于申請塊、但又最接近申請塊大小的空閑塊。當(dāng)然，在回收

54、時(shí)也需要將釋放的空閑塊插入到鏈表的適當(dāng)位置上。最差滿足法：這個(gè)方法就分配是一個(gè)不小于申請塊、但又是最大的空閑塊。通常將空閑塊鏈表中的空閑塊按照塊的體積從大到小排序。分配時(shí)只需將空閑塊鏈表中的第一個(gè)空閑塊刪除，將其中的一部分分配出去，而其它部分作為一個(gè)新的空閑塊插入到鏈表的適當(dāng)位置上。當(dāng)然，在回收時(shí)也需要將釋放的空閑塊插入到鏈表的適當(dāng)位置上。 編譯原理與技術(shù)537.6.2 堆的自動(dòng)管理 使用malloc和free執(zhí)行指針的動(dòng)態(tài)分配和回收是堆管理的手工方式，因?yàn)槌绦騿T需要明顯地編寫這些函數(shù)的調(diào)用語句。與之相對應(yīng)，運(yùn)行棧由調(diào)用序列自動(dòng)地管理。自動(dòng)存儲(chǔ)管理不需要程序員的干預(yù)，回收已經(jīng)分配、而且盡可能長

55、時(shí)間不再使用的存儲(chǔ)。這個(gè)過程需要操作系統(tǒng)、機(jī)器體系結(jié)構(gòu)方面的支持，并且由運(yùn)行系統(tǒng)來決定何時(shí)和如何執(zhí)行無用單元的收集，這個(gè)過程也稱為垃圾收集（無用單元回收）。由于無需程序員在程序代碼中編寫語句，它完全由編譯程序及其它系統(tǒng)完成的，所以又稱為隱式回收。在大多數(shù)面向?qū)ο笳Z言、函數(shù)式語言和邏輯式語言中，存儲(chǔ)單元的自動(dòng)分配和回收應(yīng)用的更加廣泛。 編譯原理與技術(shù)547.6.2 堆的自動(dòng)管理垃圾收集的不同技術(shù)垃圾集合的兩個(gè)比較現(xiàn)實(shí)的近義詞是“沒有指針指向的存儲(chǔ)塊的集合”和“從堆式分配程序數(shù)據(jù)中不可達(dá)的存儲(chǔ)塊的集合”。這兩類集合中的數(shù)據(jù)不可能被程序使用?！盁o指針”引出了一項(xiàng)稱為引用計(jì)數(shù)的垃圾回收技術(shù)，使用“不可

56、達(dá)”標(biāo)準(zhǔn)的回收技術(shù)是標(biāo)記和清掃、雙空間復(fù)制以及分代垃圾收集。 編譯原理與技術(shù)557.6.2 堆的自動(dòng)管理引用計(jì)數(shù)引用計(jì)數(shù)是一個(gè)很直觀的垃圾收集算法，它在每個(gè)存儲(chǔ)塊中增加一個(gè)引用計(jì)數(shù)，記錄指向該塊的指針數(shù)目（引用的次數(shù)）。每當(dāng)從堆中分配一個(gè)存儲(chǔ)塊的時(shí)候，它的引用計(jì)數(shù)就初始化為1。只要存儲(chǔ)塊的應(yīng)用被復(fù)制，它的引用計(jì)數(shù)就加1（遞增）。同樣，每當(dāng)存儲(chǔ)塊的引用被刪除，它的引用計(jì)數(shù)就減1（遞減）。當(dāng)該數(shù)目下降到0時(shí)就聲明該塊為無用而可以收回。引用計(jì)數(shù)的實(shí)現(xiàn)需要跟蹤所有的引用操作以及遞歸地回收應(yīng)用計(jì)數(shù)為0的存儲(chǔ)塊。引用計(jì)數(shù)的垃圾收集技術(shù)存在效率等問題，但是它在管理相對較小的動(dòng)態(tài)存儲(chǔ)分配方面是一個(gè)非常流行的技術(shù)，通常在人工開發(fā)的軟件中使用，a2程序數(shù)據(jù)區(qū)堆d1b3