第5章運(yùn)行環(huán)境計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院國家示范性軟件學(xué)院第五章運(yùn)行環(huán)境1源程序最終需要運(yùn)行。因此需了解目標(biāo)程序如何在內(nèi)存中運(yùn)行、為了程序的正確運(yùn)行需要什么樣的支持。討論內(nèi)容：1.過程在運(yùn)行時(shí)具有什么樣的動(dòng)態(tài)特性；2.運(yùn)行時(shí)需要什么樣的環(huán)境支持（存儲(chǔ)空間分配）；3.過程的調(diào)用與返回應(yīng)如何實(shí)現(xiàn)等。本章討論的前提：源程序的基本結(jié)構(gòu)是順序執(zhí)行的過程，過程之間通過子程序調(diào)用的方式進(jìn)行控制流的轉(zhuǎn)移。2<1>過程、活動(dòng)、生存期5.1.1過程與活動(dòng)

5.1過程的動(dòng)態(tài)特性定義5.1

活動(dòng)的生存期是指：從進(jìn)入活動(dòng)的第一條指令開始執(zhí)行，到離開此活動(dòng)前的最后一條指令執(zhí)行結(jié)束的這段時(shí)間。**其中包括調(diào)用其它過程時(shí)其它活動(dòng)的生存期。過程的一次執(zhí)行稱為一次活動(dòng)?；顒?dòng)是一個(gè)動(dòng)態(tài)的概念，它有有限的生存期。3子程序調(diào)用：call/return，特點(diǎn)是有去必有回。順序調(diào)用：生存期不相交嵌套調(diào)用：生存期嵌套容易混淆的概念： -過程的嵌套（源程序定義中、靜態(tài)概念） -活動(dòng)的嵌套（目標(biāo)程序調(diào)用中、動(dòng)態(tài)概念）消息傳遞：send/receive，特點(diǎn)是可以有去無回。<2>活動(dòng)之間的通信5.1.1過程與活動(dòng)4特點(diǎn)：程序的執(zhí)行在時(shí)間上是順序的、排他的。<3>順序執(zhí)行程序的控制流5.1.1過程與活動(dòng)即在程序執(zhí)行的任一瞬間，有且僅有一個(gè)活動(dòng)正在活動(dòng)。(順序執(zhí)行程序的)控制流滿足：①控制流是連續(xù)的；②過程間的控制流可以用樹來表示。假想時(shí)間是一支筆，則任何一個(gè)順序程序的執(zhí)行過程（控制流）是一個(gè)“一筆畫”。5定義5.2

用來描繪控制進(jìn)入活動(dòng)、離開活動(dòng)方式的樹被稱為

活動(dòng)樹，它具有下述性質(zhì)：通俗講：

結(jié)點(diǎn)a是b

的父親：a調(diào)用b結(jié)點(diǎn)a處于b的左邊：先調(diào)用a后調(diào)用b<4>活動(dòng)樹1.每個(gè)結(jié)點(diǎn)代表過程的一個(gè)活動(dòng)；2.根代表主程序的活動(dòng)；3.結(jié)點(diǎn)a是b的父親，當(dāng)且僅當(dāng)控制流從a的活動(dòng)進(jìn)入b的活動(dòng)；4.結(jié)點(diǎn)a處于b的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期。5.1.1過程與活動(dòng)6例

考慮【例4.34】的快排序過程：funcsort(){funcreadarray();funcquicksort(m,n:Int);funcpartition(low,high:Int):Int;readarray();quicksort(0,a.size-1);}考慮sort的執(zhí)行：時(shí)間縮為一個(gè)點(diǎn)，且翻轉(zhuǎn)：5.1.1過程與活動(dòng)7

活動(dòng)樹的實(shí)質(zhì)是反映了順序執(zhí)行程序的調(diào)用和時(shí)序關(guān)系，把每個(gè)活動(dòng)的生存期縮小到了一點(diǎn)。例

快排序程序的一次執(zhí)行的活動(dòng)樹：圖中：s－sortr－readarrayq－quicksortp－partition30105208僅關(guān)心活動(dòng)之間的控制流、生存期，不關(guān)心活動(dòng)執(zhí)行細(xì)節(jié)、時(shí)長5.1.1過程與活動(dòng)quicksort(m,n):if(m<n){i=partition(m,n);quicksort(m,i-1);quicksort(i+1,n);}8<1>程序控制流：對(duì)應(yīng)活動(dòng)樹從根開始的一次深度優(yōu)先遍歷。

其中，過程調(diào)用的序列：對(duì)應(yīng)于對(duì)樹的先序遍歷；

過程返回的序列：對(duì)應(yīng)于對(duì)樹的后序遍歷?？刂屏髋c活動(dòng)樹的關(guān)系：5.1.2控制棧與活動(dòng)記錄<2>活動(dòng)樹上的結(jié)點(diǎn)之間具有下述關(guān)系：同一層次的活動(dòng)生存期不交；任一時(shí)刻，處在生存期的活動(dòng)構(gòu)成一條從根到某結(jié)點(diǎn)的路徑；路徑上各結(jié)點(diǎn)生存期是嵌套的（后進(jìn)先出）。9<3>控制棧與活動(dòng)記錄

活動(dòng)記錄中至少應(yīng)該存放兩類信息：控制流與活動(dòng)樹的關(guān)系：控制棧：保存所有在生存期的活動(dòng)(一條后進(jìn)先出的路徑)活動(dòng)記錄：棧中的每個(gè)元素稱為一個(gè)活動(dòng)記錄，為活動(dòng)

提供的活動(dòng)場(chǎng)所。

控制信息：控制活動(dòng)的正確調(diào)用與返回、控制活動(dòng)記錄的正確切換；訪問信息：用于為當(dāng)前活動(dòng)提供對(duì)數(shù)據(jù)訪問（包括對(duì)本地?cái)?shù)據(jù)和非本地?cái)?shù)據(jù)的訪問）。5.1.2控制棧與活動(dòng)記錄10例

快排序程序運(yùn)行時(shí)某個(gè)狀態(tài)的控制棧：控制棧中，保存了某個(gè)時(shí)刻的一系列活動(dòng)記錄（對(duì)應(yīng)活動(dòng)處在生存期）。5.1.2控制棧與活動(dòng)記錄棧頂，正在執(zhí)行的活動(dòng)棧底，主程序11定義5.3

運(yùn)行時(shí)為名字X分配存儲(chǔ)空間S，這一過程稱為綁定（binding）。名字X是一個(gè)對(duì)象，可以是：5.1.3名字的綁定<1>名字的綁定換句話說，綁定是名字X與存儲(chǔ)空間S的結(jié)合。我們的討論僅限于X是一個(gè)數(shù)據(jù)對(duì)象。(1)數(shù)據(jù)對(duì)象，如變量，與之結(jié)合的是一個(gè)存儲(chǔ)單元；(2)操作對(duì)象，如過程，與之結(jié)合的是可執(zhí)行的代碼。12

名字的聲明與名字的綁定均需要有對(duì)應(yīng)的存儲(chǔ)空間，而存儲(chǔ)空間的對(duì)應(yīng)方式，一個(gè)是靜態(tài)的，一個(gè)是動(dòng)態(tài)的。聲明時(shí)關(guān)心的是聲明的作用域，即當(dāng)一個(gè)名字被引用時(shí)，在不同的作用域中與該名字的不同聲明結(jié)合；名字和作用域是靜態(tài)的一對(duì)一關(guān)系。綁定時(shí)關(guān)心的是綁定的生存期，即當(dāng)一個(gè)名字在運(yùn)行時(shí)被實(shí)際分配的存儲(chǔ)單元，名字與存儲(chǔ)單元結(jié)合的這段時(shí)間被稱為綁定的生存期(即名字的生存期)。運(yùn)行時(shí)名字與存儲(chǔ)單元的結(jié)合可以是一對(duì)多的關(guān)系。靜態(tài) 動(dòng)態(tài)過程的定義 過程的活動(dòng) 名字的聲明 名字的綁定聲明的作用域 綁定的生存期符號(hào)表 活動(dòng)記錄<2>靜態(tài)與動(dòng)態(tài)5.1.3名字的綁定13多個(gè)活動(dòng)記錄！下下頁簡化的符號(hào)表5.1.3名字的綁定過程定義中的嵌套關(guān)系控制棧與活動(dòng)記錄14例5.4

若有變量聲明x=3.14、常量聲明pi=3.14，則兩個(gè)賦值

中變量和常量的映射關(guān)系：常量沒有左值（存儲(chǔ)空間），所以不能被賦值。<3>變量與值的兩步映射5.1.3名字的綁定環(huán)境改變存儲(chǔ)，狀態(tài)改變值15環(huán)境是一對(duì)多的映射：允許遞歸調(diào)用的情況下，同一作用域中的一個(gè)名字，可以同時(shí)綁定到多個(gè)存儲(chǔ)單元。如：同一個(gè)快排序過程的三個(gè)活動(dòng)的活動(dòng)記錄q(1,9)、

q(1,3)和q(1,0)均被放在控制棧中。5.1.3名字的綁定狀態(tài)是一對(duì)多的映射：一個(gè)存儲(chǔ)單元可以(在不同時(shí)間)存放不同的值。<3>變量與值的兩步映射16<4>影響存儲(chǔ)分配策略的因素編譯器怎樣對(duì)存儲(chǔ)空間進(jìn)行組織、采用什么樣的存儲(chǔ)分配策略，很大程度上取決于語言中采用的機(jī)制，如：過程能否遞歸，過程能否嵌套，過程調(diào)用時(shí)參數(shù)如何傳遞，哪些實(shí)體可以作為參數(shù)和返回值，是否允許動(dòng)態(tài)地為對(duì)象分配和撤銷存儲(chǔ)空間，存儲(chǔ)空間是否必須顯式地釋放，等等5.1.3名字的綁定17代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)堆↓空閑區(qū)域↑棧1.靜態(tài)分配策略：編譯時(shí)安排數(shù)據(jù)對(duì)象的存儲(chǔ)空間，即綁定是靜態(tài)確定的。5.2.1運(yùn)行時(shí)內(nèi)存的劃分與數(shù)據(jù)空間的存儲(chǔ)分配策略5.2運(yùn)行時(shí)數(shù)據(jù)空間的組織數(shù)據(jù)區(qū)與分配策略：2.棧分配策略：按棧的方式管理運(yùn)行時(shí)

的數(shù)據(jù)存儲(chǔ)空間。3.堆分配策略：在運(yùn)行時(shí)根據(jù)要求從堆

中動(dòng)態(tài)地分配和釋放存儲(chǔ)空間。18編譯時(shí)進(jìn)行名字與存儲(chǔ)空間的結(jié)合,運(yùn)行時(shí)不再改變。每次過程活動(dòng)時(shí)，同一個(gè)名字映射到同一存儲(chǔ)單元。5.2.2靜態(tài)與動(dòng)態(tài)分配簡介特點(diǎn)：綁定是1對(duì)1的映射。<1>靜態(tài)分配策略：19靜態(tài)分配的限制：使用該策略的常見數(shù)據(jù)對(duì)象如：全局?jǐn)?shù)據(jù)、過程體內(nèi)的靜態(tài)數(shù)據(jù)等。它們一般在整個(gè)程序運(yùn)行的期間被共享。數(shù)據(jù)對(duì)象的大小和它在內(nèi)存中位置：必須在編譯時(shí)確定，如數(shù)組的長度、寬度不能是動(dòng)態(tài)的；不允許程序遞歸，因?yàn)橐粋€(gè)過程的所有活動(dòng)使用同樣的名字綁定，即綁定是一對(duì)一的；不能動(dòng)態(tài)生成或撤消數(shù)據(jù)，因?yàn)檫\(yùn)行時(shí)沒有存儲(chǔ)分配機(jī)制。5.2.2靜態(tài)與動(dòng)態(tài)分配簡介<1>靜態(tài)分配策略：特點(diǎn)：綁定是1對(duì)1的映射。20<2>棧分配策略

限制：當(dāng)活動(dòng)停止后，活動(dòng)中的局部名字的值不能保持；無法處理需要隨時(shí)分配/撤銷(不滿足LIFO)的動(dòng)態(tài)數(shù)據(jù)；被調(diào)用者的活動(dòng)比調(diào)用者活得更長。（活動(dòng)樹不能正確描繪此類過程間的控制流，如send/receive）重點(diǎn)：后邊詳細(xì)討論5.2.2靜態(tài)與動(dòng)態(tài)分配簡介特點(diǎn)：按棧的方式分配存儲(chǔ)空間存儲(chǔ)安排：21<3>堆分配策略

特點(diǎn)：可任意分配和撤消數(shù)據(jù)；對(duì)語言(幾乎)沒有限制；靜態(tài)、棧與堆的關(guān)系：可以靜態(tài)分配的數(shù)據(jù)均可以棧分配；可以靜態(tài)和棧分配的數(shù)據(jù)均可以堆分配；反之不一定。5.2.2靜態(tài)與動(dòng)態(tài)分配簡介堆分配的基本思想：（用一個(gè)雙向鏈表記錄可用空間信息）

22過程的動(dòng)態(tài)特性過程、活動(dòng)、活動(dòng)的生存期順序執(zhí)行程序的控制流活動(dòng)樹與控制?？刂茥Ｅc活動(dòng)記錄名字的綁定綁定是運(yùn)行時(shí)名字與存儲(chǔ)空間的結(jié)合環(huán)境與狀態(tài)、名字與存儲(chǔ)空間1對(duì)多的關(guān)系影響存儲(chǔ)分配策略的因素運(yùn)行時(shí)內(nèi)存的劃分和數(shù)據(jù)空間的分配策略靜態(tài)數(shù)據(jù)區(qū)（靜態(tài)分配策略）動(dòng)態(tài)數(shù)據(jù)區(qū)—棧數(shù)據(jù)區(qū)（棧分配策略）

—堆數(shù)據(jù)區(qū)（堆分配策略）5.1,5.2節(jié)內(nèi)容小結(jié)23<1>活動(dòng)記錄的具體內(nèi)容（控制信息＋訪問信息）1.參數(shù)與返回值2.控制鏈(可選)3.訪問鏈(可選)4.保存的機(jī)器狀態(tài)5.本地(局部)數(shù)據(jù)6.臨時(shí)變量其中：參數(shù)與返回值：存放實(shí)參和返回值；控制鏈：指向調(diào)用者活動(dòng)記錄的指針。用于當(dāng)調(diào)用返回時(shí)，將當(dāng)前棧頂正確切換到調(diào)用者的活動(dòng)記錄；訪問鏈：用于在嵌套定義的過程中指示訪問非本地?cái)?shù)據(jù)；4.機(jī)器狀態(tài)：本次調(diào)用前的程序計(jì)數(shù)器，寄存器等；5.

過程內(nèi)部聲明的數(shù)據(jù)：如本地變量等；6.

臨時(shí)變量：源程序中不出現(xiàn)的、由編譯程序產(chǎn)生的變量，如表達(dá)式x+y+z求值時(shí)產(chǎn)生的t1、t2等。5.3.1控制棧中的活動(dòng)記錄5.3棧式動(dòng)態(tài)分配24<2>控制棧的兩個(gè)重要指針（全程量）top－控制棧的棧頂sp－每個(gè)活動(dòng)記錄中的相對(duì)尋址，也代表此活動(dòng)記錄在整個(gè)程序運(yùn)行過程中，top指示棧頂，sp指向棧頂活動(dòng)記錄中的某個(gè)位置。首先通過一個(gè)例子來看程序運(yùn)行時(shí)控制棧中活動(dòng)記錄是怎樣變化的，然后討論采用什么樣的方法來實(shí)現(xiàn)這樣的變化。5.3.1控制棧中的活動(dòng)記錄25例5.5

控制棧的變化過程(從s到r、q(1,9)、q(1,3)、q(1,0))5.3.1控制棧中的活動(dòng)記錄棧底在上棧頂在下26<1>簡化的活動(dòng)記錄參數(shù)與返回值控制鏈本地?cái)?shù)據(jù)臨時(shí)變量top→top→sp→(過程運(yùn)行時(shí)引用)(調(diào)用與返回序列引用)問題：如何使得過程調(diào)用和返回時(shí)能夠?qū)崿F(xiàn)：

①程序控制流正確轉(zhuǎn)移，

②活動(dòng)記錄正確切換。解決方案：在過程運(yùn)行代碼的適當(dāng)位置，加入實(shí)現(xiàn)這些功能的代碼。稱它們?yōu)檎{(diào)用序列和返回序列。任何時(shí)刻top和sp都是唯一的?。ㄒ?yàn)橹挥幸粋€(gè)棧）5.3.2調(diào)用序列與返回序列棧底在上棧頂在下27<2>調(diào)用序列和返回序列的位置調(diào)用序列：①、②返回序列：③、④5.3.2調(diào)用序列與返回序列28<3>調(diào)用序列和返回序列內(nèi)容調(diào)用者（①）：傳遞參數(shù)維護(hù)訪問鏈（如果必要）保存返回地址和控制鏈保存機(jī)器狀態(tài)

(指令計(jì)數(shù)器寄存器等)將控制轉(zhuǎn)向被調(diào)用者被調(diào)用者（②）：設(shè)置新的活動(dòng)記錄大小為可變數(shù)組分配空間(若有)初始化本地?cái)?shù)據(jù)（若必要）...（開始可執(zhí)行代碼）被調(diào)用者（③）：保留返回值（若為函數(shù)）恢復(fù)訪問鏈（如果必要）恢復(fù)調(diào)用時(shí)機(jī)器狀態(tài)恢復(fù)控制鏈將控制返回調(diào)用者調(diào)用者（④）：接收返回值(若有的話)...（繼續(xù)執(zhí)行代碼）分工原則：盡量將調(diào)用序列和返回序列放在被調(diào)用者中調(diào)用序列：5.3.2調(diào)用序列與返回序列返回序列：<1>允許嵌套定義過程的語言29名字在不同的作用域內(nèi)，可以有不同的定義（靜態(tài)作用域規(guī)則＋最近嵌套規(guī)則）如何通過當(dāng)前的活動(dòng)記錄訪問非本地?cái)?shù)據(jù)前提：每個(gè)名字均可以通過其所在活動(dòng)記錄的sp尋址

設(shè)法：任何活動(dòng)記錄內(nèi)，均可得到其外層活動(dòng)記錄的sp5.3.3棧式分配中對(duì)非本地名字的訪問30通過引入訪問鏈實(shí)現(xiàn)對(duì)非本地名字的訪問；訪問鏈的雙重作用：本身所在的位置(左值)，可以作為本活動(dòng)記錄中數(shù)據(jù)的相對(duì)地址的基址；內(nèi)容(右值)指向它直接外層過程的、最新出現(xiàn)的活動(dòng)記錄的訪問鏈。<2>訪問鏈5.3.3棧式分配中對(duì)非本地名字的訪問31

設(shè)過程p的嵌套深度是np，過程p中引用一個(gè)嵌套深度為na且na≤np的變量a。設(shè)p和a的層次之差為x，即na+x=np，于是x=np-na。則a的存儲(chǔ)可以如下方式找到：當(dāng)控制在p中，p的一個(gè)活動(dòng)記錄肯定在棧頂。從棧頂?shù)幕顒?dòng)記錄中追蹤訪問鏈np-na次。（np-na的值是靜態(tài)作用域規(guī)則決定的，可以在編譯時(shí)計(jì)算得到）；追蹤訪問鏈np-na次后，找到a的聲明所在過程的活動(dòng)記錄的訪問鏈sp(a)。<3>利用訪問鏈訪問非本地?cái)?shù)據(jù)5.3.3棧式分配中對(duì)非本地名字的訪問32與本地變量相比，非本地變量的地址需要兩個(gè)信息：可存放在符號(hào)表a的條目中，用于生成存取變量a的代碼。5.3.3棧式分配中對(duì)非本地名字的訪問<3>利用訪問鏈訪問非本地?cái)?shù)據(jù)（np-na，Δa）（5.1）強(qiáng)調(diào)：本地變量僅需偏移量，非本地變量還需要層次差；層次差與偏移量一樣，均可以靜態(tài)確定33例如：在p(1,3)中訪問s中變量a：

因?yàn)椋簄p-na=2

所以：追蹤訪問鏈2次，即可到達(dá)a所在過程的sp。（np-na，Δa）（5.1）顯示表形式5.3.3棧式分配中對(duì)非本地名字的訪問<3>利用訪問鏈訪問非本地?cái)?shù)據(jù)34

建立訪問鏈的代碼是過程調(diào)用序列的一部分；假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程x，則建立訪問鏈分下邊兩種情況：①

np＜nx：必有

np-nx=-1

（為什么？）此時(shí)被調(diào)用過程x的訪問鏈必須指向棧中剛好在它下面的調(diào)用過程p活動(dòng)記錄的訪問鏈（無需追蹤訪問鏈）。②

np≥nx：p和x有公共外層，即深度為1,2,

...(nx-1)的過程。從調(diào)用過程追蹤訪問鏈np-nx+1次，到達(dá)靜態(tài)包圍x和p的最接近過程的最新活動(dòng)記錄。所到達(dá)的訪問鏈就是被調(diào)用過程x必須指向的訪問鏈綜合①②，追蹤訪問鏈次數(shù)：

np-nx+1 （5.2）

<4>如何在調(diào)用序列中生成訪問鏈35例5.6

再考察例4.34的快排序過程，從s到s、q(1,9)、q(1,3)、p(1,3)、e(1,3)再返回s，控制棧與訪問鏈的變化過程。①

s調(diào)用q(1,9)：

ns-nq+1=1-2+1=0

根據(jù)(5.2)直接將q(1,9)的訪問鏈指向s的訪問鏈地址②

q(1,9)調(diào)用q(1,3)

：

nq-nq+1=2-2+1=1從q(1,9)追蹤訪問鏈一次，到達(dá)s的訪問鏈；<4>如何在調(diào)用序列中生成訪問鏈36③

q(1,3)調(diào)用p(1,3)

：nq-np+1=2-3+1=0，處理與①同④p(1,3)調(diào)用e(1,3)：

np-ne+1=3-2+1=2，從p(1,3)追蹤訪問鏈一次，到達(dá)s的訪問鏈提示：訪問鏈反映靜態(tài)層次嵌套 控制鏈反映動(dòng)態(tài)調(diào)用嵌套通過訪問鏈可以正確訪問數(shù)據(jù)。<4>如何在調(diào)用序列中生成訪問鏈37

任何一個(gè)深度為i的活動(dòng)，它可以訪問的本地與非本地?cái)?shù)據(jù)只能是嵌套深度不大于i的、最新被調(diào)用的活動(dòng)。例如：若當(dāng)前活動(dòng)為p(1,3)，其可訪問的活動(dòng)記錄為：

p(1,3)、q(1,3)、s嵌套深度：3、2、1（每層一個(gè)）

棧中有兩個(gè)嵌套深度為2的活動(dòng)，但p(1,3)可以訪問的是最新的活動(dòng)q(1,3)，而不是q(1,9)。（為什么？）換句話說，在嵌套層次小于等于當(dāng)前活動(dòng)嵌套層次的活動(dòng)中，每層僅有一個(gè)（本層最新）活動(dòng)記錄可以被訪問到。<5>利用顯示表訪問非本地?cái)?shù)據(jù)38利用訪問鏈訪問非本地?cái)?shù)據(jù)的弱點(diǎn)：若當(dāng)前活動(dòng)的過程嵌套深度為n，則需要追蹤訪問鏈n-i次（i=1,2,...,n-1），才能找到所需活動(dòng)記錄的sp。（（np-na，Δa）（5.1））

解決思路：讓當(dāng)前活動(dòng)記錄可以直接訪問每層最新活動(dòng)記錄的sp（即回避對(duì)訪問鏈的追蹤）。

具體方法：displaydisplay是一個(gè)以嵌套深度為下標(biāo)的數(shù)組，每個(gè)元素是一個(gè)棧性質(zhì)的單鏈表，連接此嵌套深度的、在生存期的所有活動(dòng)記錄（sp），最新活動(dòng)記錄在表頭?？梢栽L問幾個(gè)非本地的活動(dòng)記錄由靜態(tài)嵌套深度確定；可以訪問哪幾個(gè)非本地的活動(dòng)記錄由動(dòng)態(tài)的運(yùn)行軌跡確定；同一深度的活動(dòng)在控制棧中滿足LIFO的原則。<5>利用顯示表訪問非本地?cái)?shù)據(jù)39訪問q(1,3)中的k：dsp=display[2]Δk[dsp]例如：當(dāng)前控制棧若為s、q(1,9)、q(1,3)、p(1,3)

則display內(nèi)容示意如下：可以訪問幾個(gè)非本地的活動(dòng)記錄由靜態(tài)嵌套深度確定；可以訪問哪幾個(gè)非本地的活動(dòng)記錄由動(dòng)態(tài)的運(yùn)行軌跡確定；同一深度的活動(dòng)在控制棧中滿足LIFO的原則。<5>利用顯示表訪問非本地?cái)?shù)據(jù)40若嵌套深度為np的過程p

引用嵌套深度為na（na≤np）的變量a，則a的活動(dòng)記錄的訪問鏈地址可以在d[na]中找到，訪問非本地變量a的地址信息可用有序?qū)Γ?.3）表示：

（na， Δa）（5.3）對(duì)照：（np-na，Δa） （5.1）

例如訪問S中的a：dsp=d[1]Δa[dsp]其中：1=na訪問鏈形式兩步即可訪問到非本地?cái)?shù)據(jù)：

dsp=d[na] Δa[dsp]<5>利用顯示表訪問非本地?cái)?shù)據(jù)41

在沿訪問鏈追蹤的訪問模式中，訪問鏈只需建立，無需撤銷，因?yàn)榛顒?dòng)記錄的撤銷自然也撤銷了訪問鏈。若采用顯示表方式，則當(dāng)進(jìn)入和退出活動(dòng)時(shí)，均需對(duì)顯示表進(jìn)行維護(hù)，以保證對(duì)非本地?cái)?shù)據(jù)的正確訪問?；顒?dòng)記錄中訪問鏈的右值：訪問鏈方式：指向最新直接外層活動(dòng)記錄的sp