第6章運(yùn)行時(shí)存儲(chǔ)空間的組織和管理ppt課件

1、第六章 運(yùn)轉(zhuǎn)時(shí)存儲(chǔ)空間的組織和管理 術(shù)語過程的活動(dòng)過程的一次執(zhí)行稱為過程的一次活動(dòng)活動(dòng)記錄過程的活動(dòng)需求可執(zhí)行代碼和存放所需信息的存儲(chǔ)空間,后者稱為活動(dòng)記錄本章內(nèi)容討論一個(gè)活動(dòng)記錄中的數(shù)據(jù)規(guī)劃程序執(zhí)行過程中，一切活動(dòng)記錄的組織方式 第六章 運(yùn)轉(zhuǎn)時(shí)存儲(chǔ)空間的組織和管理 影響存儲(chǔ)分配戰(zhàn)略的言語特征 過程能否遞歸當(dāng)控制從過程的活動(dòng)前往時(shí)，部分變量的值能否要保管過程能否訪問非部分變量過程調(diào)用的參數(shù)傳送方式過程能否作為參數(shù)被傳送過程能否作為結(jié)果值傳送存儲(chǔ)塊能否在程序控制下動(dòng)態(tài)地分配存儲(chǔ)塊能否必需顯式地釋放6.1 部分存儲(chǔ)分配6.1.1 過程言語概念：過程定義、過程調(diào)用、方式參數(shù)、真實(shí)參數(shù)、活動(dòng)的生存期6

2、.1 部分存儲(chǔ)分配6.1.2 名字的作用域和綁定1、名字的作用域一個(gè)聲明起作用的程序部分稱為該聲明的作用域即使一個(gè)名字在程序中只聲明一次，該名字在程序運(yùn)轉(zhuǎn)時(shí)也能夠表示不同的數(shù)據(jù)對(duì)象6.1 部分存儲(chǔ)分配2、環(huán)境和形狀環(huán)境把名字映射到左值，而形狀把左值映射到右值即名字到值有兩步映射賦值改動(dòng)形狀，但不改動(dòng)環(huán)境 過程調(diào)用改動(dòng)環(huán)境假設(shè)環(huán)境將名字x映射到存儲(chǔ)單元s，那么說x被綁定到s名字存儲(chǔ)單元形狀值環(huán)境6.1 部分存儲(chǔ)分配3、靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng)靜 態(tài) 概 念 動(dòng) 態(tài) 對(duì) 應(yīng) 過程的定義 過程的活動(dòng) 6.1 部分存儲(chǔ)分配3、靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng)靜 態(tài) 概 念 動(dòng) 態(tài) 對(duì) 應(yīng) 過程的定義 過程的活

3、動(dòng) 名字的聲明 名字的綁定 6.1 部分存儲(chǔ)分配3、靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng)靜 態(tài) 概 念 動(dòng) 態(tài) 對(duì) 應(yīng) 過程的定義 過程的活動(dòng) 名字的聲明 名字的綁定 聲明的作用域 綁定的生存期 6.1 部分存儲(chǔ)分配6.1.3 活動(dòng)記錄活動(dòng)記錄的常見規(guī)劃返 回 值臨 時(shí) 數(shù) 據(jù)參 數(shù)控 制 鏈訪 問 鏈機(jī) 器 狀 態(tài)局 部 數(shù) 據(jù)6.1 部分存儲(chǔ)分配6.1.4 部分?jǐn)?shù)據(jù)的規(guī)劃字節(jié)是可編址內(nèi)存的最小單位變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定一個(gè)過程所聲明的部分變量，按這些變量聲明時(shí)出現(xiàn)的次序，在部分?jǐn)?shù)據(jù)域中依次分配空間部分?jǐn)?shù)據(jù)的地址可以用相對(duì)于某個(gè)位置的地址來表示數(shù)據(jù)對(duì)象的存儲(chǔ)規(guī)劃還有一個(gè)對(duì)齊問題6.1

4、 部分存儲(chǔ)分配例在SPARC/Solaris任務(wù)站上下面兩個(gè)構(gòu)造體的size分別是24和16，為什么不一樣？typedef struct _atypedef struct _bchar c1; char c1;long i; char c2;charc2; long i;double f; double f;a; b;對(duì)齊：char : 1, long : 4, double : 86.1 部分存儲(chǔ)分配例在SPARC/Solaris任務(wù)站上下面兩個(gè)構(gòu)造體的size分別是24和16，為什么不一樣？typedef struct _atypedef struct _bchar c1;0 char c

5、1;0long i;4 char c2; 1charc2;8 long i; 4double f;16 double f; 8a; b;對(duì)齊：char : 1, long : 4, double : 86.1 部分存儲(chǔ)分配例在X86/Linux機(jī)器的結(jié)果和SPARC/Solaris任務(wù)站不一樣，是20和16。typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2; 1charc2;8 long i; 4double f;12 double f; 8a; b;對(duì)齊：char : 1, long : 4, doub

6、le : 46.1 部分存儲(chǔ)分配6.1.5 程序塊本身含有部分變量聲明的語句可以嵌套最接近的嵌套作用域規(guī)那么并列程序塊不會(huì)同時(shí)活潑并列程序塊的變量可以重疊分配6.1 部分存儲(chǔ)分配main() / 例 / / begin of B0 / int a = 0; int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / / end of B1 / end of B0 /聲 明 作 用 域 int a = 0; B0 B2

7、 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 a0b0b1a2, b3重疊分配存儲(chǔ)單元 6.2 全局棧式存儲(chǔ)分配本節(jié)引見引見程序運(yùn)轉(zhuǎn)時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配戰(zhàn)略描畫過程的目的代碼怎樣訪問綁定到部分名字的存儲(chǔ)單元引見三種分配戰(zhàn)略靜態(tài)分配戰(zhàn)略棧式分配戰(zhàn)略堆式分配戰(zhàn)略6.2 全局棧式存儲(chǔ)分配6.2.1 運(yùn)轉(zhuǎn)時(shí)內(nèi)存的劃分代 碼靜 態(tài) 數(shù) 據(jù)堆棧6.2 全局棧式存儲(chǔ)分配1、靜態(tài)分配名字在程序被編譯時(shí)綁定到存儲(chǔ)單元，不需求運(yùn)轉(zhuǎn)時(shí)的任何支持綁定的生存期是程序的整個(gè)運(yùn)轉(zhuǎn)期間6.2 全局棧式存儲(chǔ)分配2、靜態(tài)分配給言語帶來限制

8、遞歸過程不被允許數(shù)據(jù)對(duì)象的長度和它在內(nèi)存中位置的限制，必需是在編譯時(shí)可以知道的數(shù)據(jù)構(gòu)造不能動(dòng)態(tài)建立6.2 全局棧式存儲(chǔ)分配例C程序的外部變量、靜態(tài)部分變量以及程序中出現(xiàn)的常量都可以靜態(tài)分配聲明在函數(shù)外面外部變量 靜態(tài)分配靜態(tài)外部變量 靜態(tài)分配聲明在函數(shù)里面靜態(tài)部分變量 也是靜態(tài)分配自動(dòng)變量 不能靜態(tài)分配6.2 全局棧式存儲(chǔ)分配6.2.2 活動(dòng)樹和運(yùn)轉(zhuǎn)棧1、活動(dòng)樹用樹來描畫控制進(jìn)入和分開活動(dòng)的方式mq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2

9、 全局棧式存儲(chǔ)分配活動(dòng)樹的特點(diǎn)每個(gè)結(jié)點(diǎn)代表某過程的一個(gè)活動(dòng)根結(jié)點(diǎn)代表主程序的活動(dòng)結(jié)點(diǎn)a是結(jié)點(diǎn)b的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從a的活動(dòng)進(jìn)入b的活動(dòng)結(jié)點(diǎn)a處于結(jié)點(diǎn)b的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期6.2 全局棧式存儲(chǔ)分配當(dāng)前活潑著的過程活動(dòng)可以保管在一個(gè)棧中例 控制棧的內(nèi)容：m, q (1, 9), q (1, 3), q (2, 3) mq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2 全局棧式存儲(chǔ)分配2、運(yùn)轉(zhuǎn)棧：把控制棧中的信息拓廣到包括過

10、程活動(dòng)所需的一切部分信息即活動(dòng)記錄 6.2 全局棧式存儲(chǔ)分配2、運(yùn)轉(zhuǎn)棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的一切部分信息即活動(dòng)記錄 ma : arraym6.2 全局棧式存儲(chǔ)分配2、運(yùn)轉(zhuǎn)棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的一切部分信息即活動(dòng)記錄 mi: integerra : arraymr6.2 全局棧式存儲(chǔ)分配2、運(yùn)轉(zhuǎn)棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的一切部分信息即活動(dòng)記錄 mk: integerq (1, 9)a : arraymq(1,9)r6.2 全局棧式存儲(chǔ)分配2、運(yùn)轉(zhuǎn)棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的一切部分信息即活動(dòng)記錄 mk: integerq

11、 (1, 9)a : arrayq (1, 3)k: integermq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)6.2 全局棧式存儲(chǔ)分配6.2.3 調(diào)用序列過程調(diào)用和過程前往都需求執(zhí)行一些代碼來管理活動(dòng)記錄棧，保管或恢復(fù)機(jī)器形狀等過程調(diào)用序列過程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄，把信息填入它的域中的代碼過程前往序列過程前往時(shí)執(zhí)行的恢復(fù)機(jī)器形狀，釋放活動(dòng)記錄，使調(diào)用過程可以繼續(xù)執(zhí)行的代碼調(diào)用序列和前往序列經(jīng)常都分成兩部分，分處于調(diào)用過程和被調(diào)用過程中6.2 全局棧式存儲(chǔ)分配即使是同一種言語，過程調(diào)用序列、前往序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異設(shè)計(jì)這些序列和活動(dòng)記錄的一些原

12、那么以活動(dòng)記錄中間的某個(gè)位置作為基地址長度能較早確定的域放在活動(dòng)記錄的中間返 回 值臨 時(shí) 數(shù) 據(jù)參 數(shù)控 制 鏈訪 問 鏈機(jī) 器 狀 態(tài)局 部 數(shù) 據(jù)6.2 全局棧式存儲(chǔ)分配即使是同一種言語，過程調(diào)用序列、前往序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異設(shè)計(jì)這些序列和活動(dòng)記錄的一些原那么普通把暫時(shí)數(shù)據(jù)域放在部分?jǐn)?shù)據(jù)域的后面把參數(shù)域和能夠有的前往值域放在緊靠調(diào)用者活動(dòng)記錄的地方返 回 值臨 時(shí) 數(shù) 據(jù)參 數(shù)控 制 鏈訪 問 鏈機(jī) 器 狀 態(tài)局 部 數(shù) 據(jù)6.2 全局棧式存儲(chǔ)分配即使是同一種言語，過程調(diào)用序列、前往序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異設(shè)計(jì)這些序列和活動(dòng)記錄的一些原那么

13、用同樣的代碼來執(zhí)行各個(gè)活動(dòng)的保管和恢復(fù)返 回 值臨 時(shí) 數(shù) 據(jù)參 數(shù)控 制 鏈訪 問 鏈機(jī) 器 狀 態(tài)局 部 數(shù) 據(jù)6.2 全局棧式存儲(chǔ)分配1、過程p調(diào)用過程q的調(diào)用序列前往值和參數(shù)top_sp base_sp 暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 6.2 全局棧式存儲(chǔ)分配1、過程p調(diào)用過程q的調(diào)用序列(1) p計(jì)算實(shí)參，依次放入棧頂，并在棧頂留出放前往值的空間。top_sp的值在此過程中被改動(dòng)前往值和參數(shù)top_sp base_sp 暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 前往值和參數(shù)6.2 全局棧式存儲(chǔ)分配1、過程p調(diào)用過程q的調(diào)用序列(2) p把前往地址和當(dāng)前base_sp的值存入

14、q的活動(dòng)記錄中，建立q的訪問鏈，添加base_sp的值前往值和參數(shù)top_sp base_sp 暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 前往值和參數(shù)控制鏈和前往地址6.2 全局棧式存儲(chǔ)分配1、過程p調(diào)用過程q的調(diào)用序列(3) q保管存放器的值和其它機(jī)器形狀信息前往值和參數(shù)top_sp base_sp 暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 前往值和參數(shù)控制鏈 和保管的機(jī)器形狀6.2 全局棧式存儲(chǔ)分配1、過程p調(diào)用過程q的調(diào)用序列(4) q根據(jù)部分?jǐn)?shù)據(jù)域和暫時(shí)數(shù)據(jù)域的大小添加top_sp的值，初始化它的部分?jǐn)?shù)據(jù)，并開場執(zhí)行過程體暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)前往值和參數(shù)前往值和參數(shù) 控制鏈 和保管的機(jī)器形

15、狀top_sp base_sp 暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 6.2 全局棧式存儲(chǔ)分配調(diào)用者p和被調(diào)用者q之間的義務(wù)劃分被調(diào)用者q的責(zé)任調(diào)用者p的責(zé)任調(diào)用者p的活動(dòng)記錄被調(diào)用者q的活動(dòng)記錄暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)前往值和參數(shù)前往值和參數(shù) 控制鏈 和保管的機(jī)器形狀top_sp base_sp 棧增長方向暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 6.2 全局棧式存儲(chǔ)分配2、過程p調(diào)用過程q的前往序列暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)前往值和參數(shù)前往值和參數(shù) 控制鏈 和保管的機(jī)器形狀top_sp base_sp 棧增長方向暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 6.2 全局棧式存儲(chǔ)分配2、過程p調(diào)用過程q的前往

16、序列暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)前往值和參數(shù)前往值和參數(shù) 控制鏈 和保管的機(jī)器形狀top_sp base_sp 棧增長方向暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 (1) q把前往值置入臨近p的活動(dòng)記錄的地方 參數(shù)個(gè)數(shù)可變場所難以確定存放前往值的位置，因此通常用存放器傳送前往值6.2 全局棧式存儲(chǔ)分配2、過程p調(diào)用過程q的前往序列(2) q對(duì)應(yīng)調(diào)用序列的步驟(4)，減小top_sp的值前往值和參數(shù)top_sp base_sp 暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 前往值和參數(shù)控制鏈 和保管的機(jī)器形狀6.2 全局棧式存儲(chǔ)分配2、過程p調(diào)用過程q的前往序列(3) q恢復(fù)存放器(包括base_sp)和機(jī)器形

17、狀，前往p前往值和參數(shù)top_sp base_sp 暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 前往值和參數(shù)6.2 全局棧式存儲(chǔ)分配2、過程p調(diào)用過程q的前往序列前往值和參數(shù)top_sp base_sp 暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 (4) p根據(jù)參數(shù)個(gè)數(shù)與類型和前往值類型調(diào)整top_sp，然后取出前往值6.2 全局棧式存儲(chǔ)分配3、過程的參數(shù)個(gè)數(shù)可變的情況暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)參 數(shù)參 數(shù) 控制鏈 和保管的機(jī)器形狀top_sp base_sp 棧增長方向暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 (1) 函數(shù)前往值改成用存放器傳送6.2 全局棧式存儲(chǔ)分配3、過程的參數(shù)個(gè)數(shù)可變的情況暫時(shí)數(shù)據(jù)部

18、分?jǐn)?shù)據(jù)參數(shù)1, , 參數(shù)n參數(shù)1, ,參數(shù)m 控制鏈 和保管的機(jī)器形狀top_sp base_sp 棧增長方向暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 (2) 編譯器產(chǎn)生將實(shí)參表達(dá)式逆序計(jì)算并將結(jié)果進(jìn)棧的代碼 自上而下依次是參數(shù)1, , 參數(shù)n6.2 全局棧式存儲(chǔ)分配3、過程的參數(shù)個(gè)數(shù)可變的情況暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)參數(shù)1, , 參數(shù)n參數(shù)1, ,參數(shù)m 控制鏈 和保管的機(jī)器形狀top_sp base_sp 棧增長方向暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 (3) 被調(diào)用函數(shù)能準(zhǔn)確地知道第一個(gè)參數(shù)的位置6.2 全局棧式存儲(chǔ)分配3、過程的參數(shù)個(gè)數(shù)可變的情況暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)參數(shù)1, , 參數(shù)n參數(shù)1,

19、 ,參數(shù)m 控制鏈 和保管的機(jī)器形狀top_sp base_sp 棧增長方向暫時(shí)數(shù)據(jù)部分?jǐn)?shù)據(jù)控制鏈 和保管的機(jī)器形狀 (4) 被調(diào)用函數(shù)根據(jù)第一個(gè)參數(shù)到棧中取第二、第三個(gè)參數(shù)等等6.2 全局棧式存儲(chǔ)分配6.2.4 棧上可變長數(shù)據(jù)活動(dòng)記錄的長度在編譯時(shí)不能確定的情況例：部分?jǐn)?shù)組的大小要等到過程激活時(shí)才干確定備注： Java言語的實(shí)現(xiàn)是將它們分配在堆上6.2 全局棧式存儲(chǔ)分配訪問動(dòng)態(tài)分配的數(shù)組控制鏈數(shù)組A的指針數(shù)組B的指針top_sp base_sp . . . . . . .棧(1) 編譯時(shí)，在活動(dòng)記錄中為這樣的數(shù)組分別存放數(shù)組指針的單元6.2 全局棧式存儲(chǔ)分配訪問動(dòng)態(tài)分配的數(shù)組(2) 運(yùn)轉(zhuǎn)時(shí)，

20、這些指針指向分配在棧頂?shù)拇鎯?chǔ)空間控制鏈數(shù)組A的指針數(shù)組B的指針top_sp base_sp . . . . . . .棧數(shù)組A數(shù)組B6.2 全局棧式存儲(chǔ)分配訪問動(dòng)態(tài)分配的數(shù)組(3) 運(yùn)轉(zhuǎn)時(shí)，對(duì)數(shù)組A和B的訪問都要經(jīng)過相應(yīng)指針來間接訪問控制鏈數(shù)組A的指針數(shù)組B的指針top_sp base_sp . . . . . . .棧數(shù)組A數(shù)組B6.2 全局棧式存儲(chǔ)分配訪問動(dòng)態(tài)分配的數(shù)組q的數(shù)組q的活動(dòng)記錄p的數(shù)組p的活動(dòng)記錄控制鏈top_sp base_sp 數(shù)組A的指針數(shù)組B的指針數(shù)組A數(shù)組B控制鏈. . . . . . .棧6.2 全局棧式存儲(chǔ)分配6.2.5 懸空援用懸空援用：援用某個(gè)已被釋放的存儲(chǔ)單

21、元6.2 全局棧式存儲(chǔ)分配6.2.5 懸空援用懸空援用：援用某個(gè)已被釋放的存儲(chǔ)單元main()|int dangle ( ) |int q;|int j = 20; q = dangle ( );|return &j;|6.3 非部分名字的訪問本節(jié)引見無過程嵌套的靜態(tài)作用域C言語有過程嵌套的靜態(tài)作用域Pascal言語動(dòng)態(tài)作用域Lisp言語6.3 非部分名字的訪問6.3.1 無過程嵌套的靜態(tài)作用域過程體中的非部分援用可以直接運(yùn)用靜態(tài)確定的地址部分變量在棧頂?shù)幕顒?dòng)記錄中，可以經(jīng)過base_sp指針來訪問無須深化棧中取數(shù)據(jù)，無須訪問鏈過程可以作為參數(shù)來傳送，也可以作為結(jié)果來前往6.3 非部分名字的訪

22、問6.3.2 有過程嵌套的靜態(tài)作用域sortreadarrayexchangequicksortpartition6.3 非部分名字的訪問6.3.2 有過程嵌套的靜態(tài)作用域過程嵌套深度sort1readarray2exchange2quicksort2partition3變量的嵌套深度：它的聲明所在過程的嵌套深度作為該名字的嵌套深度6.3 非部分名字的訪問訪問鏈用來尋覓非部分名字的存儲(chǔ)單元sa, xq (1, 9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈p (1, 3)i, j訪問

23、鏈e (1, 3)訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈p (1, 3)i, j訪問鏈6.3 非部分名字的訪問訪問非部分名字的存儲(chǔ)單元 假定過程p的嵌套深度為np，它援用嵌套深度為na的變量a，na np。如何訪問a的存儲(chǔ)單元sort1readarray2exchange2quicksort2partition36.3 非部分名字的訪問訪問非部分名字的存儲(chǔ)單元 假定過程p的嵌套深度為np，它援用嵌套深度為na的變量a，na np。如何訪問a的存儲(chǔ)單元從棧頂?shù)幕顒?dòng)記錄開場，追蹤訪問鏈np na次到達(dá)a的聲明所在過程的活動(dòng)記錄訪問鏈的追蹤用間接操作就可完成so

24、rt1readarray2exchange2quicksort2partition36.3 非部分名字的訪問訪問非部分名字的存儲(chǔ)單元 sort readarray exchange quicksort partitionsa, xq (1, 9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈p (1, 3)i, j訪問鏈e (1, 3)訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈p (1, 3)i, j訪問鏈6.3 非部分名字的訪問過程p對(duì)變量a訪問時(shí)，a

25、的地址由下面的二元組表示：np na，a在活動(dòng)記錄中的偏移6.3 非部分名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程x(1) np nx的情況sort1readarray2exchange2quicksort2partition3 這時(shí)x一定就聲明在p中6.3 非部分名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程x(1) np nx的情況被調(diào)用過程的訪問鏈必需指向調(diào)用過程的活動(dòng)記錄的訪問鏈6.3 非部分名字的訪問訪問非部分名字的存儲(chǔ)單元 sort readarray exchange quicksort partitionsa, xq (1,

26、9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈p (1, 3)i, j訪問鏈e (1, 3)訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈p (1, 3)i, j訪問鏈6.3 非部分名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程x(2) np nx的情況sort1readarray2exchange2quicksort2partition3 這時(shí)p和x的嵌套深度分別為1，2，nx 1的外圍過程一定一樣6.3 非部分名字的訪問建立訪

27、問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程x(2) np nx的情況追蹤訪問鏈np nx + 1次，到達(dá)了靜態(tài)包圍x和p的且離它們最近的那個(gè)過程的最新活動(dòng)記錄所到達(dá)的活動(dòng)記錄就是x的活動(dòng)記錄中的訪問鏈應(yīng)該指向的那個(gè)活動(dòng)記錄6.3 非部分名字的訪問訪問非部分名字的存儲(chǔ)單元 sort readarray exchange quicksort partitionsa, xq (1, 9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈p (1, 3)i, j訪問鏈e (1, 3)訪問

28、鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈p (1, 3)i, j訪問鏈6.3 非部分名字的訪問program param(input, output);過程作為參數(shù)procedure b(function h(n: integer): integer); begin writeln(h(2) end b;procedure c; var m: integer; function f(n: integer): integer; begin f := m+n end f; begin m := 0; b(f) end c; begin cend.過程作為參數(shù)傳送時(shí)，

29、怎樣在該過程被激活時(shí)建立它的訪問鏈 從b的訪問鏈難以建立f的訪問鏈6.3 非部分名字的訪問program param(input, output);過程作為參數(shù)procedure b(function h( begin writeln(h(2) end ;procedure c; var m: integer; function f(n: integer) begin f := m+n end f; begin m := 0; b(f) end c; begin cend.訪 問 鏈訪 問 鏈paramcmb f的起始地址連同它的訪問鏈一同傳送6.3 非部分名字的訪問program ret (

30、input, output);過程作為前往值 var f: function (integer): integer;function a: function (integer): integer; var m: integer; function addm (n: integer): integer; begin return m+n end; begin m:= 0; return addm end; procedure b (g: function (integer): integer); begin writeln (g(2) end; begin f := a; b(f) end.ar

31、etbaddm 執(zhí)行addm時(shí)，a的活動(dòng)記錄已不存在，取不到m的值6.3 非部分名字的訪問C言語的函數(shù)聲明不能嵌套，函數(shù)不論在什么情況下激活，要訪問的數(shù)據(jù)分成兩種情況非靜態(tài)部分變量包括方式參數(shù)，它們分配在活動(dòng)記錄棧頂?shù)哪莻€(gè)活動(dòng)記錄中外部變量包括定義在其它源文件之中的外部變量和靜態(tài)的部分變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)6.3 非部分名字的訪問6.3.3 動(dòng)態(tài)作用域被調(diào)用過程的非部分名字a和它在調(diào)用過程中援用的是同樣的存儲(chǔ)單元新的綁定僅為被調(diào)用過程的部分名字建立，這些名字在被調(diào)用過程的活動(dòng)記錄中占用的存儲(chǔ)單元6.3 非部分名字的訪問program dynamic(input, output); var

32、 r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow6.3 非部分名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3)

33、 end; procedure small; var r: real; begin r := 0.125; show end; begin靜態(tài)作用域 r := 0.25;0.2500.250 show; small; writeln;0.2500.250 show; small; writeln end.dynamicshowsmallsmallshowshowshow6.3 非部分名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small

34、; var r: real; begin r := 0.125; show end; begin動(dòng)態(tài)作用域 r := 0.25;0.250 0.125 show; small; writeln;0.250 0.125 show; small; writeln end.dynamicshowsmallsmallshowshowshow6.3 非部分名字的訪問實(shí)現(xiàn)動(dòng)態(tài)作用域的方法深訪問用控制鏈搜索運(yùn)轉(zhuǎn)棧，尋覓包含該非部分名字的第一個(gè)活動(dòng)記錄淺訪問為每個(gè)名字在靜態(tài)分配的存儲(chǔ)空間中保管它的當(dāng)前值當(dāng)過程p的新活動(dòng)出現(xiàn)時(shí)，p的部分名字n運(yùn)用在靜態(tài)數(shù)據(jù)區(qū)分配給n的存儲(chǔ)單元。n的先前值保管在p的活動(dòng)記錄中，當(dāng)

35、p的活動(dòng)終了時(shí)再恢復(fù)6.3 非部分名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow?r 靜態(tài)區(qū)運(yùn)用值的地方 棧區(qū)暫存值的地方dyn

36、amicr?6.3 非部分名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.25rdynamicr? 靜態(tài)區(qū)運(yùn)用值的地方 棧區(qū)暫

37、存值的地方6.3 非部分名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.25rdynamicr?show 靜態(tài)區(qū)運(yùn)用值的地方

38、棧區(qū)暫存值的地方6.3 非部分名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.25rdynamicr?smallr0.25 靜

39、態(tài)區(qū)運(yùn)用值的地方 棧區(qū)暫存值的地方6.3 非部分名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.125rdynamicr?smallr0.25 靜態(tài)區(qū)運(yùn)用值的地方 棧區(qū)暫存值的地方6.3 非部分名字的訪問program dynamic(input, out