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

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

2、執(zhí)行被調(diào)用過程的過程體。出現(xiàn)在過程定義中的參數(shù)叫做形式參數(shù)（形參），在過程調(diào)用點取代形參的稱為實在參數(shù)（實參）。 編譯原理與技術(shù)47.1 程序運行的基本概念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 程序運行的基本概念過程的活動過程的每次調(diào)用就引起過程體的一次執(zhí)行，稱為過程的一次活動。過程p的一個活動的生存期就是從過程體開始執(zhí)行到執(zhí)行結(jié)束的時間，包括執(zhí)行被P調(diào)用其它所有過程所耗費

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

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

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

7、點p在結(jié)點q的左邊，當(dāng)且僅當(dāng)p的生存期先于q的生存期。編譯原理與技術(shù)107.1 程序運行的基本概念例7.1 假如執(zhí)行圖7.1的程序，我們可以構(gòu)造出程序執(zhí)行期間的所有過程的活動記錄，表示整個程序運行的蹤跡，如圖7.3所示。樹根是主程序sort的活動記錄，它首先調(diào)用了readarray和quisksort(1, 9)，按照程序的執(zhí)行順序，readarray在quisksort(1, 9)之前，即readarray的生存期先于在quisksort(1, 9)，所以，結(jié)點ra在qs(1, 9)的左邊。qs(1, 9)又調(diào)用了一次partition和兩次quisksort，圖中顯示的結(jié)點分別是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 程序運行的基本概念名字的綁定和環(huán)境 按照程序設(shè)計語言的語義，環(huán)境表示把一個名字映射到一個存儲位置的函數(shù)，狀態(tài)表示把存儲單元映射到所保存的值的函數(shù)環(huán)境把名字映射

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

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

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

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

13、：inc1(y)就可以使變量y的值增加。 編譯原理與技術(shù)177.2 參數(shù)傳遞機(jī)制值結(jié)果調(diào)用(復(fù)寫恢復(fù),復(fù)寫入復(fù)寫)（1）調(diào)用過程把實參的值和實參的地址同時傳給被調(diào)用過程；（2）被調(diào)用過程像按值調(diào)用那樣使用傳遞給形參的值；（3）把形參在被調(diào)用過程中最后的值拷貝到實參的存儲單元內(nèi)。被調(diào)用過程的活動記錄 . 形參1 實參1的地址形參2調(diào)用序列在調(diào)用點計算實參1的值實參1的地址圖7.7 值結(jié)果調(diào)用示意圖 實參2的地址.計算實參2的值實參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)用實參直到在被調(diào)用的過程中作為形參實際使用的時候才計算，所以也叫延遲計算。換名調(diào)用可以如下實現(xiàn)：（1）在調(diào)用點，用被調(diào)用過程的體來替換調(diào)用者的調(diào)用，但是形參用對應(yīng)的實參來替換。這種文字替換方式成為宏展開或內(nèi)聯(lián)展開。（2）在宏展開前，被調(diào)用過程的每個局部變量名字被系統(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ī)制的另外一種實現(xiàn)

16、，在復(fù)寫出形參值的時候重新計算對應(yīng)實參的地址，那么，調(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);在這個程序中，由于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ù)a1的地址傳遞給p的活動記錄中對應(yīng)的形式單元x，執(zhí)行p的結(jié)果是a1 值增加1，為2。采用值結(jié)果的參數(shù)傳遞機(jī)制，調(diào)用過程p：把a(bǔ)1的值（此時為1）傳給p的活動記錄中對應(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)展開可以縮短程序的運行時間這是因為，過程活動的建立包括活動記錄的空間分配、機(jī)器狀態(tài)的保存、調(diào)用數(shù)據(jù)的傳遞以及控制的轉(zhuǎn)移等，都需要占用機(jī)器的資源。若過程體較小，則過程調(diào)用序列的代碼可能會超過過程體本身的代碼。如果把過程體的代碼內(nèi)聯(lián)展開到調(diào)用者的代碼中，即使程序的代碼會稍長一些，程序的執(zhí)行速度也會提高。對于諸如Java和C#這樣的面向?qū)ο笳Z言，內(nèi)聯(lián)函數(shù)還可以減少在程序運行時消息和函數(shù)體的動態(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ù)讀入一行字符串，逐個判斷是否為數(shù)

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

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

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

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

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

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

25、調(diào)用者的返回地址，生成一個到被調(diào)用過程起始的跳轉(zhuǎn)指令。返回時就需要一個簡單的到返回地址的跳轉(zhuǎn)指令。 編譯原理與技術(shù)307.4 靜態(tài)運行時環(huán)境 例7.3 圖7.11是一個FORTRAN程序，它計算并打印一個表中實數(shù)的平均值。它只有一個主程序和一個子程序QUADMEAN，唯一一個全局變量是分別在主程序和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)運行時環(huán)境這個程序的運行時環(huán)境可以如圖7.12所示。其中箭頭連線表示過程QUADMEAN的三個參數(shù)A、SIZE和QMEAN的值在調(diào)用過程中從主程序拷貝得到，這是由于FORTRAN語言的參數(shù)傳遞是隱含的存儲引用，所以把它們的地址賦值到被調(diào)用的QUADMEAN中。QUADMEAN活動記錄中的臨時變量用來存放計算TEMP+A(K)*A(K)或者TEMP/SIZE的值。如果沒有足夠的寄存器來存放臨時值，或者有一個調(diào)用要求保留這個值，那么，在完成計算之前要把該值存儲在活動記錄中。編譯程序根據(jù)目標(biāo)機(jī)器的體系結(jié)構(gòu)（如寄存器的個數(shù)和使用規(guī)則）可以確定運行時是否需要存放臨時變量的存儲，并安排大小合適的

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

29、理與技術(shù)337.5.1 無過程嵌套的棧式運行時環(huán)境在這類語言中，例如C，過程都是全局過程，不允許嵌套，但是允許遞歸調(diào)用。這樣的運行時環(huán)境需要兩類信息：維護(hù)指向當(dāng)前活動記錄的指針以便訪問局部變量;記錄直接調(diào)用者的位置或大小以便當(dāng)前調(diào)用結(jié)束后恢復(fù)調(diào)用者的活動記錄。指向當(dāng)前活動記錄的指針通常稱為幀指針sp，保存在一個寄存器中（就叫sp）。前一個活動記錄通常用一個存放在當(dāng)前活動記錄中稱為控制鏈的指針訪問。這個指針又叫動態(tài)鏈，因為它是在程序運行時指向調(diào)用程序的活動記錄；又稱為老的幀指針，因為它代表的了sp的前一個值。 編譯原理與技術(shù)347.5.1 無過程嵌套的棧式運行時環(huán)境例7.3 一個計算兩個非負(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)用的運行時環(huán)境如圖7.13(b)所示。每次調(diào)用gcd都在棧頂新增一個大小一樣的活動記錄，而且在這個活動記錄中都有控制鏈指向調(diào)用它的前一個活動記錄。幀指針fp指向當(dāng)前活動記錄的控制鏈，這樣，在下一次調(diào)用時（比如第4次調(diào)用），這個fp就成為下一個活動記錄的控制鏈的目的地址。每次調(diào)用gcd完成過程體的動作之后，每個gcd的活動記錄都從棧頂移出。當(dāng)執(zhí)行main中打印語句pringf的時候，

31、存儲器中只剩下main的活動記錄和全局/靜態(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 無過程嵌套的棧式運行時環(huán)境 m: 15 n: 10 u: 15 v: 10控制鏈 返回地址 u: 10 v: 5控制鏈 返回地址 u: 5 v: 0控制鏈 返回地址 自由空間全局/靜態(tài)區(qū)域main的活動記錄第1次調(diào)用gcd時的活動記錄

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

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

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

35、)，在自左向右的計算中需要臨時存儲下列結(jié)果：ai的地址、和i + j 以及i/k。這些臨時結(jié)果可以存放在寄存器中，或者在調(diào)用f以前存放在運行棧的作的臨時單元。由于臨時變量的個數(shù)和類型可以事先確定，它們的訪問也可以在編譯時按照局部變量的方式進(jìn)行。 編譯原理與技術(shù)397.5.1 無過程嵌套的棧式運行時環(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個字節(jié)

36、，地址占4個字節(jié)，字符型占1個字節(jié)，雙精度浮點型占8個字節(jié)）。 x y 控制鏈 返回地址 a i x j 自由區(qū)域調(diào)用p時的活動記錄為塊A分配的區(qū)域spfp x y 控制鏈 返回地址 a i a k 自由區(qū)域調(diào)用p時的活動記錄為塊B分配的區(qū)域spfp圖7.12(a) 進(jìn)入過程p中塊A的活動記錄圖7.15(b) 進(jìn)入過程p中塊B的活動記錄編譯原理與技術(shù)407.5.2 有過程嵌套的棧式運行時環(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等語言中，由于過程允許嵌套聲明，非局部名字不一定就是全局的。如果程序語言允許過程聲明的嵌套，那么，截至目前所描述的運行時環(huán)境由于沒有提供訪問非局部、非全局名字的手段，其效率而顯得不高。編譯原理與技術(shù)417.5.2 有過程嵌套的棧式運行時環(huán)境調(diào)用過程q時的運行棧如圖7.16所示.在q內(nèi)任何對n的引用都必須引用p的局部變量n。但是，在這個程序中，僅僅依靠如圖所示的運

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

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

40、記錄調(diào)用p時的活動記錄調(diào)用r時的活動記錄調(diào)用q時的活動記錄fpsp控制鏈控制鏈控制鏈無訪問鏈訪問鏈訪問鏈編譯原理與技術(shù)447.5.2 有過程嵌套的棧式運行時環(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 有過程嵌套的棧式運行時環(huán)境按照最近的嵌套規(guī)則，在partition中出現(xiàn)的a的聲明在主程序中。同樣，在partition中調(diào)用的過程exchange對partition而言也是非局部的，它的定義首先quicksort在找，如果沒有，則在其外部過程sort中尋找。圖7.19顯示了程序運行時棧的簡化情形，每個活動記錄占三行：參數(shù)、訪問鏈（sort沒有訪問鏈）以及局部變量分別依次放在一行。 無訪問鏈 a, x m, n 訪問鏈 k, v sort的活動記錄 quickso

43、rt(1,9)的活動記錄圖7.19(a) 主程序sort調(diào)用quicksort 無訪問鏈 a, x m, n 訪問鏈 k, v sort的活動記錄 quicksort(1,9)的活動記錄 m, n 訪問鏈 k, v y, z 訪問鏈 i, jquicksort(1,3)的活動記錄partition(1,3)的活動記錄圖7.19(b) quicksort第一次遞歸調(diào)用partition，執(zhí)行exchange調(diào)用前sort的活動記錄quicksort(1,9)的活動記錄quicksort(1,3)的活動記錄partition(1,3)的活動記錄exchange(1,3)的活動記錄 無訪問鏈 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 有過程嵌套的棧式運行時環(huán)境過程quicksort的每個活動記錄以及exchange的活動記錄都有訪問鏈指向主程序sort，以便訪問非局部數(shù)組a和變量x。特別地，在圖7.19（c）中，過程partition活動記錄的訪問鏈指向最靠近的quicksort的活動記錄，即quicksort(1,3)。對于過程partition，可以通過一次訪問鏈在最近的外圍quicksort中

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

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

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

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

49、可以在編譯時確定。圖中僅僅在當(dāng)前活動記錄中列出了display表的所有元素，每個寫成i-display，表示指向第i層活動記錄的指針。在當(dāng)前活動記錄中還有一個指針指向調(diào)用當(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的活動記錄quicksort(1,9)

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

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

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

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

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

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