目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織

關(guān)于目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織第1頁，講稿共54頁，2023年5月2日，星期三

從邏輯上看，在代碼生成前，編譯程序必須進(jìn)行目標(biāo)程序運(yùn)行環(huán)境的配置和數(shù)據(jù)空間的分配。

數(shù)據(jù)空間應(yīng)包括：用戶定義的各種類型的數(shù)據(jù)對(duì)象（變量和常數(shù)）所需的存儲(chǔ)空間；作為保留中間結(jié)果和傳遞參數(shù)的臨時(shí)工作單元；調(diào)用過程時(shí)所需的連接單元；組織輸入/輸出所需的緩沖區(qū)。

目標(biāo)代碼所占用空間的大小在編譯時(shí)能確定。有些數(shù)據(jù)對(duì)象所占用的空間也能在編譯時(shí)確定，其地址可以編譯進(jìn)目標(biāo)代碼中。而有些數(shù)據(jù)對(duì)象具有可變體積和待分配性質(zhì)，無法在編譯時(shí)確定存儲(chǔ)空間的位置。

第2頁，講稿共54頁，2023年5月2日，星期三

因此運(yùn)行時(shí)的存儲(chǔ)區(qū)常常劃分成：目標(biāo)代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)，如圖10.1

。目標(biāo)代碼區(qū)code靜態(tài)數(shù)據(jù)區(qū)static棧Stack堆heap圖10.1目標(biāo)程序運(yùn)行時(shí)存儲(chǔ)區(qū)的典型劃分?jǐn)?shù)據(jù)空間第3頁，講稿共54頁，2023年5月2日，星期三所謂數(shù)據(jù)空間的分配，本質(zhì)上看，是將程序中的每個(gè)名字與一個(gè)存儲(chǔ)位置關(guān)聯(lián)起來，該存儲(chǔ)位置用以保存名字的值。編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基本依據(jù)是程序語言設(shè)計(jì)時(shí)對(duì)程序運(yùn)行中存儲(chǔ)空間的使用和管理辦法的規(guī)定。第4頁，講稿共54頁，2023年5月2日，星期三決定存儲(chǔ)管理復(fù)雜程度的因素--源語言本身，比如源語言允許的數(shù)據(jù)類型有多少？語言中允許的數(shù)據(jù)項(xiàng)是靜態(tài)確定還是動(dòng)態(tài)確定？程序結(jié)構(gòu)有什么特點(diǎn)，是段結(jié)構(gòu)還是分程序結(jié)構(gòu)？過程定義是否允許嵌套？等等。源語言的結(jié)構(gòu)特點(diǎn)、源語言的數(shù)據(jù)類型、源語言中決定名字作用域的規(guī)則等因素影響存儲(chǔ)空間的管理和組織的復(fù)雜程度，決定數(shù)據(jù)空間分配的基本策略。第5頁，講稿共54頁，2023年5月2日，星期三10.1數(shù)據(jù)空間的三種不同使用方法和管理方法數(shù)據(jù)空間的使用和管理方法:

簡單的棧式分配方案嵌套過程的棧式分配方案分程序結(jié)構(gòu)的存儲(chǔ)分配方案靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配——棧式堆式第6頁，講稿共54頁，2023年5月2日，星期三10.1.1靜態(tài)存儲(chǔ)分配如果在編譯時(shí)能確定目標(biāo)程序運(yùn)行中所需的全部的數(shù)據(jù)空間的大小，編譯時(shí)安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對(duì)象的存儲(chǔ)位置，稱這種分配策略為靜態(tài)存儲(chǔ)分配。如C中的靜態(tài)變量，外部變量等。第7頁，講稿共54頁，2023年5月2日，星期三10.1.2動(dòng)態(tài)存儲(chǔ)分配如果一個(gè)程序設(shè)計(jì)語言允許遞歸過程、允許動(dòng)態(tài)的申請(qǐng)建立和撤消存儲(chǔ)空間、可變數(shù)組或允許用戶自由申請(qǐng)和釋放空間，那么，就需要采用動(dòng)態(tài)存儲(chǔ)管理技術(shù)。因?yàn)閷?duì)于這種程序在編譯時(shí)無法知道它在運(yùn)行時(shí)需要多大的存儲(chǔ)空間，它所需要的數(shù)據(jù)空間的大小需待程序運(yùn)行時(shí)動(dòng)態(tài)地確定。若一個(gè)數(shù)組所需的存儲(chǔ)空間的大小在編譯時(shí)就已知道，則稱它為確定（靜態(tài)）數(shù)組，否則稱為可變（動(dòng)態(tài)）數(shù)組。第8頁，講稿共54頁，2023年5月2日，星期三10.1.2.1棧式動(dòng)態(tài)存儲(chǔ)分配這種分配策略是將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧。在具有遞歸結(jié)構(gòu)的語言程序中，每當(dāng)調(diào)用一個(gè)過程時(shí)，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過程工作結(jié)束時(shí)就釋放這部分空間。過程所需的數(shù)據(jù)空間包括兩部分：生存期在本過程這次活動(dòng)中的數(shù)據(jù)對(duì)象；用以管理過程活動(dòng)的記錄信息。棧式動(dòng)態(tài)存儲(chǔ)分配策略適用于PASCAL，C，ALGOL之類具有遞歸結(jié)構(gòu)的語言的實(shí)現(xiàn)。

第9頁，講稿共54頁，2023年5月2日，星期三10.1.2.2堆式動(dòng)態(tài)存儲(chǔ)分配如果一個(gè)程序語言提供用戶自由地申請(qǐng)數(shù)據(jù)空間和退還數(shù)據(jù)空間的機(jī)制，或者不僅有過程而且有進(jìn)程的程序結(jié)構(gòu)，一般用堆式的動(dòng)態(tài)存儲(chǔ)分配方案。如Ｃ++中的new，delete，PASCAL的new，等機(jī)制。此時(shí),空間的使用未必服從“先申請(qǐng)后釋放，后申請(qǐng)先釋放”的原則，那么棧式的動(dòng)態(tài)分配方案就不適用了。通常使用一種稱為堆式的動(dòng)態(tài)存儲(chǔ)分配方案。這種分配方式的存儲(chǔ)管理技術(shù)甚為復(fù)雜，我們這里舉出這種分配方法必須考慮的幾個(gè)問題。

第10頁，講稿共54頁，2023年5月2日，星期三堆式的動(dòng)態(tài)存儲(chǔ)分配策略:當(dāng)運(yùn)行程序要求一塊體積為N的空間時(shí)，我們應(yīng)該分配哪一塊給它呢？理論上說，應(yīng)從比N稍大一點(diǎn)的一個(gè)空閑塊中取出N個(gè)單元，以便使大的空閑塊派更大的用場。但這種做法較麻煩。因此，常常仍采用“先碰上哪塊比N大就從其中分出N個(gè)單元”的原則。但不論采用什么原則，整個(gè)大存區(qū)在一定時(shí)間之后必然會(huì)變成零碎不堪?？傆幸粋€(gè)時(shí)候會(huì)出現(xiàn)異樣的情形：運(yùn)行程序要求一塊體積為N的空間，但發(fā)現(xiàn)沒有比N大的空閑塊了，然而所有空閑塊的總和卻要比N大得多！出現(xiàn)這種情形時(shí)怎么辦呢？這是一個(gè)比前面的問題難得多的問題。解決辦法似乎很簡單，這就是，把所有空閑塊連接在一起，形成一片可分配的連續(xù)空間。這里主要問題是，我們必須調(diào)整運(yùn)行程序?qū)Ω髡加脡K的全部引用點(diǎn)。

第11頁，講稿共54頁，2023年5月2日，星期三堆式的動(dòng)態(tài)存儲(chǔ)分配策略:另外，如果運(yùn)行程序要求一塊體積為N的空間，但所有空閑塊的總和也不夠N，那又應(yīng)怎么辦呢？有的管理系統(tǒng)采用一種叫做廢品回收的辦法來對(duì)付這種局面。即尋找那些運(yùn)行程序業(yè)己無用但尚未釋放在占用塊，或者那些行程序目前很少使用的占用塊，把這此占用塊收回來，重新分配。但是，我們?nèi)绾沃滥男K運(yùn)行時(shí)在使用或者目前很少使用呢？即便知道了，一經(jīng)收回后運(yùn)行程序在某個(gè)時(shí)候又要用它時(shí)又應(yīng)該怎么辦呢？要使用廢品回收技術(shù)，除了在語言上要有明確的具體限制外，還需要有特別的硬件措施，否則回收幾乎不能實(shí)現(xiàn)。第12頁，講稿共54頁，2023年5月2日，星期三堆式動(dòng)態(tài)儲(chǔ)分配的實(shí)現(xiàn)通常有如下兩種途徑：1）定長塊管理堆式動(dòng)態(tài)儲(chǔ)分配最簡單的實(shí)現(xiàn)是按定長塊進(jìn)行。初始化時(shí)，將堆存儲(chǔ)空間分成長度相等的若干塊，每塊中指定一個(gè)鏈域，按照鄰塊的順序把所有塊鏈成一個(gè)鏈表，用指針available指向鏈表中的第一塊。分配時(shí)每次都分配指針available所指的塊，然后available指向相鄰的下一塊。歸還時(shí)，把所歸還的塊插入鏈表?？紤]插入方便，可以把所歸還的塊插在available所指的塊之前，然后available指向新歸還的塊。第13頁，講稿共54頁，2023年5月2日，星期三占用占用占用空閑空閑空閑available(a)占用占用空閑空閑空閑(b)空閑available圖10.3定長塊管理第14頁，講稿共54頁，2023年5月2日，星期三2）變長塊管理除了按定長塊進(jìn)行分配之外，還可以根據(jù)需要分配長度不同的存儲(chǔ)塊，可以隨要求而變。按這種方法，初始化時(shí)存儲(chǔ)空間是一個(gè)整塊。按照用戶的需要，分配時(shí)先是從一個(gè)整塊里分割出滿足需要的一小塊，以后，歸還時(shí)，如果新歸還的塊能和現(xiàn)有的空間能合并，則合并成一塊；如果不能和任何空閑塊合并，則可以把空閑塊鏈成一個(gè)鏈表。再進(jìn)行分配時(shí)，從空閑塊鏈表中找出滿足需要的一塊，或者整塊分配出去，或者從該塊上分割一小塊分配出去。若空閑塊表中有若干個(gè)滿足需要的空閑塊時(shí)，該分配哪一塊呢?通常有三種不同的分配策略：

第15頁，講稿共54頁，2023年5月2日，星期三變長塊管理通常有三種不同的分配策略：

首次滿足法（時(shí)間優(yōu)先）;最優(yōu)滿足法（空間優(yōu)先）;最差滿足法（時(shí)間優(yōu)先）。上述三種分配策略各有所長。

第16頁，講稿共54頁，2023年5月2日，星期三10.2棧式存儲(chǔ)分配的實(shí)現(xiàn)前面提到，使用棧式存儲(chǔ)分配策略意味著，運(yùn)行時(shí)每當(dāng)進(jìn)入一個(gè)過程，就在棧頂為該過程的臨時(shí)工作單元，局部變量，機(jī)器狀態(tài)及返回地址等信息分配所需的數(shù)據(jù)空間，當(dāng)一個(gè)過程工作完畢返回時(shí)，它在棧頂?shù)臄?shù)據(jù)空間也即釋放。

為討論方便，首先引入一個(gè)術(shù)語--過程的活動(dòng)記錄AR(ActivationRecord)。過程的活動(dòng)記錄是一段連續(xù)的存儲(chǔ)區(qū)，用以存放過程的一次執(zhí)行所需要的動(dòng)態(tài)信息，這些信息可以如圖10.6所示。圖10.6過程的活動(dòng)記錄返回地址實(shí)參控制鏈存取鏈機(jī)器狀態(tài)信息局部變量臨時(shí)工作單元第17頁，講稿共54頁，2023年5月2日，星期三①臨時(shí)工作單元：比如計(jì)算表達(dá)式過程中需存放中間結(jié)果用的臨時(shí)值單元。②局部變量：一個(gè)過程的局部變量。③機(jī)器狀態(tài)信息：保存該過程執(zhí)行前關(guān)于機(jī)器狀態(tài)的信息，諸如程序計(jì)數(shù)器、寄存器的值，這些值都需要在控制從該過程返回時(shí)給予恢復(fù)。④存取鏈：用以存取非局部變量，這些變量存放于其它過程的活動(dòng)記錄中。并不是所有語言需要該信息。⑤控制鏈：指向調(diào)用該過程的那個(gè)過程的活動(dòng)記錄。⑥實(shí)參：也稱形式單元，由調(diào)用過程向該被調(diào)過程提供實(shí)參的值（或地址）。當(dāng)然在實(shí)際編譯程序中，也常常使用機(jī)器寄存器傳遞實(shí)參。⑦返回地址：保存該被調(diào)過程返回后的地址。圖10.6過程的活動(dòng)記錄返回地址實(shí)參控制鏈存取鏈機(jī)器狀態(tài)信息局部變量臨時(shí)工作單元靜態(tài)鏈，指向靜態(tài)直接外層最新活動(dòng)記錄的起始地址，即指向定義本過程的直接外層過程

（或主程序）運(yùn)行時(shí)最新活動(dòng)記錄的基地址。動(dòng)態(tài)鏈，指向調(diào)用該過程前正在運(yùn)行過程的數(shù)據(jù)段基地址。第18頁，講稿共54頁，2023年5月2日，星期三10.2.1簡單的棧式分配的實(shí)現(xiàn)

程序結(jié)構(gòu)特點(diǎn):過程定義不嵌套，過程可遞歸調(diào)用，含可變數(shù)組；例：

program

main

全局變量的說明procR……endR;procQ……endQ;主程序執(zhí)行語句endmain圖10.7過程定義不嵌套的程序結(jié)構(gòu)第19頁，講稿共54頁，2023年5月2日，星期三這種情況下，采用棧式動(dòng)態(tài)分配策略，即，運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程，則為該過程分配一段存儲(chǔ)區(qū)，當(dāng)一個(gè)過程工作完畢返回時(shí)，它所占用的存儲(chǔ)區(qū)可釋放。程序運(yùn)行時(shí)的存儲(chǔ)空間(棧)中在某一時(shí)刻可能會(huì)包含某個(gè)過程的幾個(gè)活動(dòng)記錄（某個(gè)過程遞歸調(diào)用的情況）；另外，同樣的一個(gè)存儲(chǔ)位置，在不同運(yùn)行時(shí)刻可能分配給不同的數(shù)據(jù)對(duì)象。例如圖10.7的程序結(jié)構(gòu)中，若主程序調(diào)用了過程Q，Q又調(diào)用了R，在R進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖10.8（a）所示。若主程序調(diào)用了過程Q，Q遞歸調(diào)用自己，在Q過程第二次進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖10.8（b）所示。第20頁，講稿共54頁，2023年5月2日，星期三TOP

臨時(shí)工作單元局部簡單變量局部數(shù)組的內(nèi)情向量

保存運(yùn)行過程前的狀態(tài)（返回地址，寄存器值…）實(shí)參（形式單元）和參數(shù)個(gè)數(shù)SP

存取鏈（靜態(tài)鏈）控制鏈（動(dòng)態(tài)鏈，老SP）圖10.6過程的活動(dòng)記錄Main

Q

R

TOP

R的活動(dòng)記錄SP

主程序全局?jǐn)?shù)據(jù)區(qū)Q的活動(dòng)記錄MainQQQ的活動(dòng)記錄主程序全局?jǐn)?shù)據(jù)區(qū)Q的活動(dòng)記錄圖10.8棧式存儲(chǔ)分配靜態(tài)鏈，指向靜態(tài)直接外層最新活動(dòng)記錄的起始地址，即指向定義本過程的直接外層過程

（或主程序）運(yùn)行時(shí)最新活動(dòng)記錄的基地址。動(dòng)態(tài)鏈，指向調(diào)用該過程前正在運(yùn)行過程的數(shù)據(jù)段基地址。指向調(diào)用該過程的那個(gè)過程的最新活動(dòng)記錄的起始地址用以存取非局部變量，這些變量存放于其他過程的活動(dòng)記錄中。第21頁，講稿共54頁，2023年5月2日，星期三TOP

臨時(shí)工作單元局部簡單變量局部數(shù)組的內(nèi)情向量

返回地址實(shí)參（形式單元）SP

參數(shù)個(gè)數(shù)控制鏈（老SP）圖10.9無嵌套定義的過程活動(dòng)記錄內(nèi)容

常常使用兩個(gè)指針指示棧最頂端的數(shù)據(jù)區(qū)，一個(gè)稱為SP，一個(gè)稱為TOP。SP總是指向現(xiàn)行過程活動(dòng)記錄的起點(diǎn)，TOP則始終指向已占用的棧頂單元。這種語言若含有可變數(shù)組，則其過程活動(dòng)記錄的內(nèi)容可如圖10.9所示。這里把控制鏈也稱作老SP，即調(diào)用該過程的那個(gè)過程的最新活動(dòng)記錄的起點(diǎn)。

第22頁，講稿共54頁，2023年5月2日，星期三10.2.2嵌套過程語言的棧式實(shí)現(xiàn)主要特點(diǎn)：（語言）一個(gè)過程可以引用包圍它的任一外層過程所定義的標(biāo)識(shí)符（如變量，數(shù)組或過程等）。（實(shí)現(xiàn)）一個(gè)過程可以引用它的任一外層過程的最新活動(dòng)記錄中的某些數(shù)據(jù)。第23頁，講稿共54頁，2023年5月2日，星期三(1)programsort(input,output);//sort的過程頭

(2)

vara:array[0..10]ofinteger;

(3)

x:integer;

(4)

procedurereadarray;//sort內(nèi)嵌套定義的readarray的過程頭

(5)

vari:integer;

(6)

begin…a…end{readarray};//readarray的過程體

(7)

procedureexchange(i,j:integer);

//sort內(nèi)嵌套定義的exchange的過程頭

(8)

begin

(9)

x∶=a[i];a[i]∶=a[j];a[j]∶=x;//exchange的過程體

(10)

end{exchange};

(11)

procedurequicksort(m,n:integer);

//sort內(nèi)嵌套定義的quicksort的過程頭

(12)

vark,v:integer;

(13)

functionpartition(y,z:integer):integer;

//quicksort內(nèi)嵌套定義的partition的函數(shù)頭

(14)

vari.j:integer;

(15)

begin…a…//partition的函數(shù)體

(16)

…v…

(17)

…exchange(i,j);…

(18)

end{partition};

(19)

begin…end{quicksort};//quicksort的過程體

(20)begin…end{sort}.//sort的例程體圖10.11具有嵌套過程的PASCAL程序第24頁，講稿共54頁，2023年5月2日，星期三圖10.11的PASCAL程序中過程定義的嵌套情況如下：

sort

readarray

exchange

quicksort

partition局部變量a,x局部變量k,v過程quicksort的活動(dòng)記錄過程sort的活動(dòng)記錄圖10.12存儲(chǔ)棧布局記錄下列信息：可以引用過程

sort的局部變量第25頁，講稿共54頁，2023年5月2日，星期三

關(guān)鍵技術(shù)：解決對(duì)非局部量的引用（存?。ＴO(shè)法跟蹤每個(gè)外層過程的最新活動(dòng)記錄AR的位置。跟蹤辦法：

1.用靜態(tài)鏈（如PL/0的SL）。

2.用DISPLAY表。跟蹤的辦法很多，我們介紹兩種，一種是在過程活動(dòng)記錄中增設(shè)存取鏈，指向包含該過程的直接外層過程的最新活動(dòng)記錄的起始位置。過程活動(dòng)記錄的內(nèi)容如圖10.13（a）所示。圖10.12所提到的情況可用圖10.13（b）說明。

第26頁，講稿共54頁，2023年5月2日，星期三圖10.13嵌套定義過程的活動(dòng)記錄和存儲(chǔ)棧(a)局部變量┆存取鏈控制鏈TOPSP┆┆存取鏈控制鏈(老SP)┆┆TOPSP(b)quicksort的ARsort的AR第27頁，講稿共54頁，2023年5月2日，星期三再回到圖10.11的例子。如果該程序的某次執(zhí)行順序?yàn)椋?/p>

sort→quicksort→quicksort→partition→exchange…

即主程序(最外層過程)sort開始執(zhí)行,繼而進(jìn)入過程quicksort，而又一次進(jìn)入過程quicksort，接著進(jìn)入過程partition，進(jìn)入過程exchange…。

圖10.15給出了進(jìn)入過程exchange之后運(yùn)行棧的示意，我們僅把存取鏈和控制鏈的值標(biāo)明。

可以看出，過程exchange由過程（函數(shù)）partition調(diào)用，但exchange的直接外層過程是sort，所以過程exchange的活動(dòng)記錄的存取鏈指向sort的活動(dòng)記錄的始址。第28頁，講稿共54頁，2023年5月2日，星期三圖10.15運(yùn)行棧靜態(tài)鏈，指向靜態(tài)直接外層最新活動(dòng)記錄的起始地址，動(dòng)態(tài)鏈，指向調(diào)用該過程前正在運(yùn)行過程的數(shù)據(jù)段基地址。exchange的活動(dòng)記錄partition的活動(dòng)記錄quicksort的活動(dòng)記錄quicksort的活動(dòng)記錄sort的活動(dòng)記錄第29頁，講稿共54頁，2023年5月2日，星期三

解決對(duì)非局部量的引用（存?。┑挠行мk法是用Display表。Display表---嵌套層次顯示表，即每進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄的同時(shí)建立一張Display表。DISPLAY表是一個(gè)指針數(shù)組d，也可看做是一個(gè)小棧，自頂向下每個(gè)單元依次存放著現(xiàn)行層，直接外層，……直至最外層（0層，主程序?qū)樱┑让恳粚舆^程的最新活動(dòng)記錄的基地址（SP），當(dāng)前激活過程的層次為K，則Display表就含有K+1個(gè)單元

。第30頁，講稿共54頁，2023年5月2日，星期三例：見P238-239第31頁，講稿共54頁，2023年5月2日，星期三

分程序結(jié)構(gòu)ProcedureA(m,n);integerm,n;

B1:beginrealz;arrayB[m:n];B2:beginreald,e;L3:2end;B4:beginarrayC[1:m];1B5:beginreale;L6:54end;end;L8:end;第32頁，講稿共54頁，2023年5月2日，星期三

分程序結(jié)構(gòu)的存儲(chǔ)分配方案

處理分程序結(jié)構(gòu)存儲(chǔ)分配方案的一種簡單辦法是，把分程序看成“無名無參過程”，它在哪里定義就在哪里被調(diào)用。因此，可以把處理過程的存儲(chǔ)辦法應(yīng)用到處理分程序中。但這種做法是極為低效的。一則，每逢進(jìn)入一個(gè)分程序，就照樣建立連接數(shù)據(jù)和DISPLAY表,這是不必要的。二則，當(dāng)從內(nèi)層分程序向外層轉(zhuǎn)移時(shí)，可能同時(shí)要結(jié)束若干個(gè)分程序。第33頁，講稿共54頁，2023年5月2日，星期三

按照過程處理辦法，意味著必須一層一層地通過“返回”來恢復(fù)所要到達(dá)的那個(gè)分程序的數(shù)據(jù)區(qū)，但不能直接到達(dá)。例如：如果有一個(gè)從第5層分程序轉(zhuǎn)出到達(dá)第1層分程序的標(biāo)號(hào)L，雖然在第5層分程序工作時(shí)知道L所屬的層數(shù)，我們極易從DISPLAY中獲得第1層分程序的活動(dòng)記錄基址（SP），但是怎么知道第1層分程序進(jìn)入時(shí)的TOP呢？唯一的辦法是從5,4,3和2各層順序退出。但這種辦法是很浪費(fèi)時(shí)間的。第34頁，講稿共54頁，2023年5月2日，星期三

為了解決上述問題，可采取兩種措施。第一，對(duì)每個(gè)過程或分程序都建立有自己的棧頂指示器TOP，代替原來僅有過程的棧頂指示器,每個(gè)TOP的值保存在各自活動(dòng)記錄中。這樣，上述的第二個(gè)問題便可解決。第二，不把分程序看作“無參過程”，每個(gè)分程序享用包圍它的那個(gè)最近過程的DISPLAY。每個(gè)分程序都隸屬于某個(gè)確定的過程，分程序的層次是相對(duì)于它所屬的那個(gè)過程進(jìn)行編號(hào)的。第35頁，講稿共54頁，2023年5月2日，星期三：

每個(gè)過程被當(dāng)作是0層分程序。而過程體分程序（假定是一個(gè)分程序）當(dāng)作是它所管轄的第1層分程序。這樣，每個(gè)過程的活動(dòng)記錄所含的內(nèi)容有：1.過程的TOP值，它指向過程活動(dòng)記錄的棧頂位置。2.連接數(shù)據(jù)，共四項(xiàng)：(1)老SP值；(2)返回地址；(3)全局DISPAY地址；(4)調(diào)用時(shí)的棧頂單元地址，老TOP。第36頁，講稿共54頁，2023年5月2日，星期三

3.參數(shù)個(gè)數(shù)和形式單元4.DISPAY表。5.過程所轄的各分程序的局部數(shù)據(jù)單元。對(duì)于每個(gè)分程序來說，它們包括：（1)分程序的TOP值。當(dāng)進(jìn)入分程序時(shí)它含現(xiàn)行棧頂?shù)刂?，以后，用來定義棧的新高度（分程序的TOP值）；（2)分程序的局部變量，數(shù)組內(nèi)情向量和臨時(shí)工作單元。第37頁，講稿共54頁，2023年5月2日，星期三過程Ａ的活動(dòng)記錄B４的ＴＯＰ

數(shù)組B的內(nèi)情向量變量z

kdDISPLAY6形式單元m,n5參數(shù)個(gè)數(shù)：２4調(diào)用時(shí)的棧頂?shù)刂罚ɡ希裕希校?全局DISPLAY地址2返回地址1老SP0過程的ＴＯＰ，指向活動(dòng)記錄之頂SP數(shù)組Ｃ的內(nèi)情向量B２的ＴＯＰB５的ＴＯＰB１的ＴＯＰ變量e變量d和e第38頁，講稿共54頁，2023年5月2日，星期三B

B1T

OB的

信

息

向

量

ZB1的

PDISPLAY

形式單元

m,n2連

接數(shù)

據(jù)A的TOP

∶

∶(b)進(jìn)

入

分

程

序B1DISPLAY

形式單元

m,n2連

接數(shù)

據(jù)

∶

∶(a)到

達(dá)

標(biāo)

號(hào)B1處A的TOP第39頁，講稿共54頁，2023年5月2日，星期三

（d）進(jìn)入分程序B2

數(shù)

組Be

dB22的TOPB的

信

息

向

量

zB1的TOPDISPLAY

形式單元

m,n2連接

數(shù)

據(jù)A的TOP

∶

∶

數(shù)

組BB的

信

息

向

量

zB1的TOPDISPLAY

形式單元

m,n2連

接

數(shù)

據(jù)A的TOP

∶

∶（c）數(shù)組Ｂ分配之后第40頁，講稿共54頁，2023年5月2日，星期三(e)進(jìn)入分程序B4分配數(shù)組C之后

數(shù)

組C

數(shù)

組BC的

向

量

內(nèi)

情B4的TOPB的

內(nèi)

情

向

量

ZB1的TOPDISPLAY

形式單元

m,n2連

接

數(shù)

據(jù)A的TOP

∶

∶(f)進(jìn)入分程序B5

數(shù)

組

C

數(shù)

組B

eB5的TOPC

的

內(nèi)

情

向

量B4的TOPB的

內(nèi)

情

向

量

zB1的TOPDISPLAY

形式單元

m,n2連接數(shù)據(jù)A的TOP

∶

∶第41頁，講稿共54頁，2023年5月2日，星期三10.3參數(shù)傳遞(1)procedureexchangel(i,j:integer);(2)varx:integer;(3)begin;(4)x:=a[i];a[i]:=a[j];a[j]:=x(5)end;

帶有非局部變量和形參的PASCAL過程非局變量a[i]和a[j]的值進(jìn)行交換，i,j為形參（在這里是傳值）第42頁，講稿共54頁，2023年5月2日，星期三

(1)programreference(input,output);(2)vara,b:integer;(3)procedureswap({var}x,y:integer);(4)vartemp:integer;(5)begin(6)temp:=x;(7)x:=y;(8)y:=temp(9)end;(10)begin(11)a:=1;b:=2;(12)swap(a,b);(13)writeln(‘a(chǎn)=‘,a);writeln(‘b=‘,b)(14)end.

帶有過程swap的PASCAL程序第43頁，講稿共54頁，2023年5月2日，星期三

10.3.1傳值（值調(diào)用call-by-value）特點(diǎn)是對(duì)形式參數(shù)的任何運(yùn)算不影響實(shí)參的值。例如：過程swap(x,y:integer);swap(a,b）；

其結(jié)果：a,b調(diào)用前的值不改變。第44頁，講稿共54頁，2023年5月2日，星期三傳值的實(shí)現(xiàn)（1）形式參數(shù)當(dāng)作過程的局部變量處理，即在被調(diào)過程的活動(dòng)記錄中開辟了形參的存儲(chǔ)空間，這些存儲(chǔ)位置即是我們所說的形式單元（用以存放實(shí)參）。（2）調(diào)用過程計(jì)算實(shí)參的值，并將其放在對(duì)應(yīng)形式單元開辟的空間中。（3）被調(diào)用過程執(zhí)行時(shí)，就像使用局部變量一樣使用這些形式單元。第45頁，講稿共54頁，2023年5月2日，星期三procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；調(diào)用swap(a,b)過程將不會(huì)影響a和b的值。其結(jié)果等價(jià)于執(zhí)行下列運(yùn)算：

x:=a；

y:=b；

temp:=x；

x:=y；

y:=temp第46頁，講稿共54頁，2023年5月2日，星期三10.3.2傳地址（變量參數(shù)call-by-address、call-by-location、call-by-reference）

例如：過程swap(varx,y:integer);swap(a,b）；（a,b為調(diào)用時(shí)的實(shí)參）調(diào)用結(jié)果a,b的值被改變。第47頁，講稿共54頁，2023年5月2日，星期三傳地址的實(shí)現(xiàn)把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形參，即調(diào)用過程把一個(gè)指向?qū)崊⒌拇鎯?chǔ)地址的指針傳遞給被調(diào)用過程相應(yīng)的形參：（1）實(shí)在參數(shù)是一個(gè)名字，或具有左值的表達(dá)式----傳遞左值（2）實(shí)在參數(shù)是無左值的表達(dá)式----計(jì)算值，放入