編譯原理陳意云chapter

1、第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 過程的過程的活動活動過程的一次執(zhí)行稱為過程的一次活動過程的一次執(zhí)行稱為過程的一次活動第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 過程的過程的活動活動過程的一次執(zhí)行稱為過程的一次活動過程的一次執(zhí)行稱為過程的一次活動活動記錄活動記錄過程的活動需要可執(zhí)行代碼和存放所需信息過程的活動需要可執(zhí)行代碼和存放所需信息的存儲空間的存儲空間, ,后者稱為活動記錄后者稱為活動記錄第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 過程的過程的活動活動過程的一次執(zhí)行稱為過程的一次活動過程的一次執(zhí)行稱為過程的一

2、次活動活動記錄活動記錄過程的活動需要可執(zhí)行代碼和存放所需信息過程的活動需要可執(zhí)行代碼和存放所需信息的存儲空間的存儲空間, ,后者稱為活動記錄后者稱為活動記錄本章內(nèi)容本章內(nèi)容 討論一個活動記錄中的數(shù)據(jù)安排討論一個活動記錄中的數(shù)據(jù)安排第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 過程的過程的活動活動過程的一次執(zhí)行稱為過程的一次活動過程的一次執(zhí)行稱為過程的一次活動活動記錄活動記錄過程的活動需要可執(zhí)行代碼和存放所需信息過程的活動需要可執(zhí)行代碼和存放所需信息的存儲空間的存儲空間, ,后者稱為活動記錄后者稱為活動記錄本章內(nèi)容本章內(nèi)容 討論一個活動記錄中的數(shù)據(jù)安排討論一個活動記錄中的數(shù)

3、據(jù)安排 程序執(zhí)行過程中，所有活動記錄的組織方式程序執(zhí)行過程中，所有活動記錄的組織方式 第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 影響存儲分配策略的語言特征影響存儲分配策略的語言特征 過程能否遞歸過程能否遞歸第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 影響存儲分配策略的語言特征影響存儲分配策略的語言特征 過程能否遞歸過程能否遞歸 當(dāng)控制從過程的活動返回時，局部變量的值當(dāng)控制從過程的活動返回時，局部變量的值是否要保留是否要保留第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 影響存儲分配策略的語言特征影響存儲分配策略的語言特征 過

4、程能否遞歸過程能否遞歸 當(dāng)控制從過程的活動返回時，局部變量的值當(dāng)控制從過程的活動返回時，局部變量的值是否要保留是否要保留 過程能否訪問非局部變量過程能否訪問非局部變量第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 影響存儲分配策略的語言特征影響存儲分配策略的語言特征 過程能否遞歸過程能否遞歸 當(dāng)控制從過程的活動返回時，局部變量的值當(dāng)控制從過程的活動返回時，局部變量的值是否要保留是否要保留 過程能否訪問非局部變量過程能否訪問非局部變量 過程調(diào)用的參數(shù)傳遞方式過程調(diào)用的參數(shù)傳遞方式第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 影響存儲分配策略的語言特征影響

5、存儲分配策略的語言特征 過程能否遞歸過程能否遞歸 當(dāng)控制從過程的活動返回時，局部變量的值當(dāng)控制從過程的活動返回時，局部變量的值是否要保留是否要保留 過程能否訪問非局部變量過程能否訪問非局部變量 過程調(diào)用的參數(shù)傳遞方式過程調(diào)用的參數(shù)傳遞方式 過程能否作為參數(shù)被傳遞過程能否作為參數(shù)被傳遞第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 影響存儲分配策略的語言特征影響存儲分配策略的語言特征 過程能否遞歸過程能否遞歸 當(dāng)控制從過程的活動返回時，局部變量的值當(dāng)控制從過程的活動返回時，局部變量的值是否要保留是否要保留 過程能否訪問非局部變量過程能否訪問非局部變量 過程調(diào)用的參數(shù)傳遞方式過

6、程調(diào)用的參數(shù)傳遞方式 過程能否作為參數(shù)被傳遞過程能否作為參數(shù)被傳遞 過程能否作為結(jié)果值傳遞過程能否作為結(jié)果值傳遞第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 影響存儲分配策略的語言特征影響存儲分配策略的語言特征 過程能否遞歸過程能否遞歸 當(dāng)控制從過程的活動返回時，局部變量的值當(dāng)控制從過程的活動返回時，局部變量的值是否要保留是否要保留 過程能否訪問非局部變量過程能否訪問非局部變量 過程調(diào)用的參數(shù)傳遞方式過程調(diào)用的參數(shù)傳遞方式 過程能否作為參數(shù)被傳遞過程能否作為參數(shù)被傳遞 過程能否作為結(jié)果值傳遞過程能否作為結(jié)果值傳遞 存儲塊能否在程序控制下動態(tài)地分配存儲塊能否在程序控制下動態(tài)

7、地分配第六章第六章 運(yùn)行時存儲空間的組織和管理運(yùn)行時存儲空間的組織和管理 影響存儲分配策略的語言特征影響存儲分配策略的語言特征 過程能否遞歸過程能否遞歸 當(dāng)控制從過程的活動返回時，局部變量的值當(dāng)控制從過程的活動返回時，局部變量的值是否要保留是否要保留 過程能否訪問非局部變量過程能否訪問非局部變量 過程調(diào)用的參數(shù)傳遞方式過程調(diào)用的參數(shù)傳遞方式 過程能否作為參數(shù)被傳遞過程能否作為參數(shù)被傳遞 過程能否作為結(jié)果值傳遞過程能否作為結(jié)果值傳遞 存儲塊能否在程序控制下動態(tài)地分配存儲塊能否在程序控制下動態(tài)地分配 存儲塊是否必須顯式地釋放存儲塊是否必須顯式地釋放6.1 局部存儲分配局部存儲分配6.1.1 過程過

8、程過程定義、過程定義、過程過程調(diào)用、形式參數(shù)、實(shí)在參數(shù)、調(diào)用、形式參數(shù)、實(shí)在參數(shù)、活動的活動的生存期生存期6.1 局部存儲分配局部存儲分配6.1.2 名字的作用域和綁定名字的作用域和綁定名字的作用域名字的作用域 一個聲明起作用的程序部分稱為該聲明的一個聲明起作用的程序部分稱為該聲明的作作用域用域 即使一個名字在程序中只聲明一次，該名字即使一個名字在程序中只聲明一次，該名字在程序運(yùn)行時也可能表示不同的數(shù)據(jù)對象在程序運(yùn)行時也可能表示不同的數(shù)據(jù)對象6.1 局部存儲分配局部存儲分配 從名字到值的兩步映射從名字到值的兩步映射名字名字存儲單元存儲單元狀態(tài)狀態(tài)值值環(huán)境環(huán)境6.1 局部存儲分配局部存儲分配 從

9、名字到值的兩步映射從名字到值的兩步映射 環(huán)境把名字映射到左值，而狀態(tài)把左值映射環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值到右值名字名字存儲單元存儲單元狀態(tài)狀態(tài)值值環(huán)境環(huán)境6.1 局部存儲分配局部存儲分配 從名字到值的兩步映射從名字到值的兩步映射 環(huán)境把名字映射到左值，而狀態(tài)把左值映射環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值到右值 賦值改變狀態(tài)，但不改變環(huán)境賦值改變狀態(tài)，但不改變環(huán)境 名字名字存儲單元存儲單元狀態(tài)狀態(tài)值值環(huán)境環(huán)境6.1 局部存儲分配局部存儲分配 從名字到值的兩步映射從名字到值的兩步映射 環(huán)境把名字映射到左值，而狀態(tài)把左值映射環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值到右值

10、 賦值改變狀態(tài)，但不改變環(huán)境賦值改變狀態(tài)，但不改變環(huán)境 過程調(diào)用改變環(huán)境過程調(diào)用改變環(huán)境名字名字存儲單元存儲單元狀態(tài)狀態(tài)值值環(huán)境環(huán)境6.1 局部存儲分配局部存儲分配 從名字到值的兩步映射從名字到值的兩步映射 環(huán)境把名字映射到左值，而狀態(tài)把左值映射環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值到右值 賦值改變狀態(tài)，但不改變環(huán)境賦值改變狀態(tài)，但不改變環(huán)境 過程調(diào)用改變環(huán)境過程調(diào)用改變環(huán)境 如果環(huán)境將名字如果環(huán)境將名字x映射到存儲單元映射到存儲單元s，我們就我們就說說x被被綁定綁定到到s名字名字存儲單元存儲單元狀態(tài)狀態(tài)值值環(huán)境環(huán)境6.1 局部存儲分配局部存儲分配靜態(tài)概念和動態(tài)概念的對應(yīng)靜態(tài)概念和動態(tài)概

11、念的對應(yīng)靜靜 態(tài)態(tài) 概概 念念 動動 態(tài)態(tài) 對對 應(yīng)應(yīng) 過程的定義過程的定義 過程的活動過程的活動 6.1 局部存儲分配局部存儲分配靜態(tài)概念和動態(tài)概念的對應(yīng)靜態(tài)概念和動態(tài)概念的對應(yīng)靜靜 態(tài)態(tài) 概概 念念 動動 態(tài)態(tài) 對對 應(yīng)應(yīng) 過程的定義過程的定義 過程的活動過程的活動 名字的聲明名字的聲明 名字的綁定名字的綁定 6.1 局部存儲分配局部存儲分配靜態(tài)概念和動態(tài)概念的對應(yīng)靜態(tài)概念和動態(tài)概念的對應(yīng)靜靜 態(tài)態(tài) 概概 念念 動動 態(tài)態(tài) 對對 應(yīng)應(yīng) 過程的定義過程的定義 過程的活動過程的活動 名字的聲明名字的聲明 名字的綁定名字的綁定 聲明的作用域聲明的作用域 綁定的生存期綁定的生存期 6.1 局部存儲

12、分配局部存儲分配6.1.3 活動記錄活動記錄一般的活動記錄的布局一般的活動記錄的布局返返 回回 值值臨臨 時時 數(shù)數(shù) 據(jù)據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問問 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.1 局部存儲分配局部存儲分配6.1.4 局部數(shù)據(jù)的安排局部數(shù)據(jù)的安排 字節(jié)是可編址內(nèi)存的最小單位字節(jié)是可編址內(nèi)存的最小單位6.1 局部存儲分配局部存儲分配6.1.4 局部數(shù)據(jù)的安排局部數(shù)據(jù)的安排 字節(jié)是可編址內(nèi)存的最小單位字節(jié)是可編址內(nèi)存的最小單位 變量所需的存儲空間可以根據(jù)其類型而靜態(tài)變量所需的存儲空間可以根據(jù)其類型而靜態(tài)確定確定6.1 局部存儲分配局部存儲分配6.1.4 局部數(shù)據(jù)的

13、安排局部數(shù)據(jù)的安排 字節(jié)是可編址內(nèi)存的最小單位字節(jié)是可編址內(nèi)存的最小單位 變量所需的存儲空間可以根據(jù)其類型而靜態(tài)變量所需的存儲空間可以根據(jù)其類型而靜態(tài)確定確定 一個過程所聲明的局部變量，按這些變量聲一個過程所聲明的局部變量，按這些變量聲明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間空間6.1 局部存儲分配局部存儲分配6.1.4 局部數(shù)據(jù)的安排局部數(shù)據(jù)的安排 字節(jié)是可編址內(nèi)存的最小單位字節(jié)是可編址內(nèi)存的最小單位 變量所需的存儲空間可以根據(jù)其類型而靜態(tài)變量所需的存儲空間可以根據(jù)其類型而靜態(tài)確定確定 一個過程所聲明的局部變量，按這些變量聲一個過程所聲明的局部變量，按

14、這些變量聲明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間空間 局部數(shù)據(jù)的地址可以用相對于某個位置的地局部數(shù)據(jù)的地址可以用相對于某個位置的地址來表示址來表示6.1 局部存儲分配局部存儲分配6.1.4 局部數(shù)據(jù)的安排局部數(shù)據(jù)的安排 字節(jié)是可編址內(nèi)存的最小單位字節(jié)是可編址內(nèi)存的最小單位 變量所需的存儲空間可以根據(jù)其類型而靜態(tài)變量所需的存儲空間可以根據(jù)其類型而靜態(tài)確定確定 一個過程所聲明的局部變量，按這些變量聲一個過程所聲明的局部變量，按這些變量聲明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間空間 局部數(shù)據(jù)的地址可以用相對于某個位置的

15、地局部數(shù)據(jù)的地址可以用相對于某個位置的地址來表示址來表示 數(shù)據(jù)對象的存儲安排還有一個對齊問題數(shù)據(jù)對象的存儲安排還有一個對齊問題6.1 局部存儲分配局部存儲分配在在SPARC/Solaris工作站上下面兩個結(jié)構(gòu)的工作站上下面兩個結(jié)構(gòu)的size分別是分別是24和和16，為什么不一樣？，為什么不一樣？typedef struct _atypedef struct _bchar c1; char c1;long i; char c2;char c2; long i;double f; double f;a; b;6.1 局部存儲分配局部存儲分配在在SPARC/Solaris工作站上下面兩個結(jié)構(gòu)的工作站

16、上下面兩個結(jié)構(gòu)的size分別是分別是24和和16，為什么不一樣？，為什么不一樣？typedef struct _atypedef struct _bchar c1;0 char c1; 0long i;4 char c2; 1char c2;8 long i; 4double f; 16 double f; 8a; b;6.1 局部存儲分配局部存儲分配在在X86/Linux機(jī)器的結(jié)果和機(jī)器的結(jié)果和SPARC/Solaris工作工作站不一樣，是站不一樣，是20和和16。typedef struct _atypedef struct _bchar c1;0 char c1; 0long i;4 c

17、har c2; 1char c2;8 long i; 4double f; 12 double f; 8a; b;6.1 局部存儲分配局部存儲分配6.1.5 程序塊程序塊 本身含有局部變量聲明的語句本身含有局部變量聲明的語句 可以嵌套可以嵌套 最接近的嵌套最接近的嵌套作用域規(guī)則作用域規(guī)則 并列程序塊不會同時活躍并列程序塊不會同時活躍 并列程序塊的變量可以重疊分配并列程序塊的變量可以重疊分配6.1 局部存儲分配局部存儲分配main() / begin of B0 / int a = 0; int b = 0; / begin of B1 / int b = 1; / begin of B2 /

18、int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / / end of B1 / end of B0 /6.1 局部存儲分配局部存儲分配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 /聲聲 明明 作作 用用 域域

19、 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 6.1 局部存儲分配局部存儲分配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; B

20、0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 a0b0b1a2, b3重疊分配存儲單元重疊分配存儲單元 6.2 全局棧式存儲分配全局棧式存儲分配 介紹程序運(yùn)行時所需的各個活動記錄在存儲介紹程序運(yùn)行時所需的各個活動記錄在存儲空間的分配策略空間的分配策略6.2 全局棧式存儲分配全局棧式存儲分配 介紹程序運(yùn)行時所需的各個活動記錄在存儲介紹程序運(yùn)行時所需的各個活動記錄在存儲空間的分配策略空間的分配策略 描述過程的目標(biāo)代碼怎樣訪問綁定到局部名描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲單元字的存儲單元6.2 全局棧式存

21、儲分配全局棧式存儲分配 介紹程序運(yùn)行時所需的各個活動記錄在存儲介紹程序運(yùn)行時所需的各個活動記錄在存儲空間的分配策略空間的分配策略 描述過程的目標(biāo)代碼怎樣訪問綁定到局部名描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲單元字的存儲單元 介紹三種分配策略介紹三種分配策略 靜態(tài)分配策略靜態(tài)分配策略6.2 全局棧式存儲分配全局棧式存儲分配 介紹程序運(yùn)行時所需的各個活動記錄在存儲介紹程序運(yùn)行時所需的各個活動記錄在存儲空間的分配策略空間的分配策略 描述過程的目標(biāo)代碼怎樣訪問綁定到局部名描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲單元字的存儲單元 介紹三種分配策略介紹三種分配策略 靜態(tài)分配策略靜態(tài)分配策略

22、棧式分配策略棧式分配策略6.2 全局棧式存儲分配全局棧式存儲分配 介紹程序運(yùn)行時所需的各個活動記錄在存儲介紹程序運(yùn)行時所需的各個活動記錄在存儲空間的分配策略空間的分配策略 描述過程的目標(biāo)代碼怎樣訪問綁定到局部名描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲單元字的存儲單元 介紹三種分配策略介紹三種分配策略 靜態(tài)分配策略靜態(tài)分配策略 棧式分配策略棧式分配策略 堆式分配策略堆式分配策略6.2 全局棧式存儲分配全局棧式存儲分配6.2.1 運(yùn)行時內(nèi)存的劃分運(yùn)行時內(nèi)存的劃分代代 碼碼靜靜 態(tài)態(tài) 數(shù)數(shù) 據(jù)據(jù)堆堆棧棧6.2 全局棧式存儲分配全局棧式存儲分配靜態(tài)分配靜態(tài)分配 名字在程序被編譯時綁定到存儲單元，

23、不需名字在程序被編譯時綁定到存儲單元，不需要運(yùn)行時的任何支持要運(yùn)行時的任何支持6.2 全局棧式存儲分配全局棧式存儲分配靜態(tài)分配靜態(tài)分配 名字在程序被編譯時綁定到存儲單元，不需名字在程序被編譯時綁定到存儲單元，不需要運(yùn)行時的任何支持要運(yùn)行時的任何支持 綁定的生存期是程序的整個運(yùn)行期間綁定的生存期是程序的整個運(yùn)行期間6.2 全局棧式存儲分配全局棧式存儲分配靜態(tài)分配給語言帶來限制靜態(tài)分配給語言帶來限制 遞歸過程不被允許遞歸過程不被允許6.2 全局棧式存儲分配全局棧式存儲分配靜態(tài)分配給語言帶來限制靜態(tài)分配給語言帶來限制 遞歸過程不被允許遞歸過程不被允許 數(shù)據(jù)對象的長度和它在內(nèi)存中位置的限制，數(shù)據(jù)對象的

24、長度和它在內(nèi)存中位置的限制，必須是在編譯時可以知道的必須是在編譯時可以知道的6.2 全局棧式存儲分配全局棧式存儲分配靜態(tài)分配給語言帶來限制靜態(tài)分配給語言帶來限制 遞歸過程不被允許遞歸過程不被允許 數(shù)據(jù)對象的長度和它在內(nèi)存中位置的限制，數(shù)據(jù)對象的長度和它在內(nèi)存中位置的限制，必須是在編譯時可以知道的必須是在編譯時可以知道的 數(shù)據(jù)結(jié)構(gòu)不能動態(tài)建立數(shù)據(jù)結(jié)構(gòu)不能動態(tài)建立6.2 全局棧式存儲分配全局棧式存儲分配 C語言程序的外部變量和程序中出現(xiàn)的常量語言程序的外部變量和程序中出現(xiàn)的常量都可以靜態(tài)分配都可以靜態(tài)分配 聲明在函數(shù)外面聲明在函數(shù)外面外部變量外部變量 靜態(tài)分配靜態(tài)分配靜態(tài)外部變量靜態(tài)外部變量 靜態(tài)

25、分配靜態(tài)分配 聲明在函數(shù)里面聲明在函數(shù)里面靜態(tài)局部變量靜態(tài)局部變量 也是靜態(tài)分配也是靜態(tài)分配自動變量自動變量 不能靜態(tài)分配不能靜態(tài)分配6.2 全局棧式存儲分配全局棧式存儲分配6.2.2 活動樹和運(yùn)行?；顒訕浜瓦\(yùn)行?；顒訕浠顒訕?用樹來描繪控制進(jìn)入和離開活動的方式用樹來描繪控制進(jìn)入和離開活動的方式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 全局棧式存儲分配全局棧式存儲分配活動樹的特點(diǎn)活動樹的特點(diǎn) 每個結(jié)點(diǎn)代表某過程的一個活動每個結(jié)點(diǎn)代表某

26、過程的一個活動 根結(jié)點(diǎn)代表主程序的活動根結(jié)點(diǎn)代表主程序的活動 結(jié)點(diǎn)結(jié)點(diǎn)a是結(jié)點(diǎn)是結(jié)點(diǎn)b的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從a的活動進(jìn)入的活動進(jìn)入b的活動的活動 結(jié)點(diǎn)結(jié)點(diǎn)a處于結(jié)點(diǎn)處于結(jié)點(diǎn)b的左邊，當(dāng)且僅當(dāng)?shù)淖筮叄?dāng)且僅當(dāng)a的生存期的生存期先于先于b的生存期的生存期6.2 全局棧式存儲分配全局棧式存儲分配當(dāng)前活躍著的過程活動可以保存在一個棧中當(dāng)前活躍著的過程活動可以保存在一個棧中控制棧的內(nèi)容：控制棧的內(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)

27、q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2 全局棧式存儲分配全局棧式存儲分配運(yùn)行棧：運(yùn)行棧：把控制棧中的信息拓廣到包括過程把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄）活動所需的所有局部信息（即活動記錄） 6.2 全局棧式存儲分配全局棧式存儲分配運(yùn)行棧：運(yùn)行棧：把控制棧中的信息拓廣到包括過程把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄）活動所需的所有局部信息（即活動記錄） ma : arraym6.2 全局棧式存儲分配全局棧式存儲分配運(yùn)行棧：運(yùn)行棧：把控制棧中的信息拓廣到包括過程把控制棧中的信息拓廣到包括過

28、程活動所需的所有局部信息（即活動記錄）活動所需的所有局部信息（即活動記錄） mi: integerra : arraymr6.2 全局棧式存儲分配全局棧式存儲分配運(yùn)行棧：運(yùn)行棧：把控制棧中的信息拓廣到包括過程把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄）活動所需的所有局部信息（即活動記錄） mk: integerq (1, 9)a : arraymq(1,9)r6.2 全局棧式存儲分配全局棧式存儲分配運(yùn)行棧：運(yùn)行棧：把控制棧中的信息拓廣到包括過程把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄）活動所需的所有局部信息（即活動記錄） mk: integerq

29、(1, 9)a : arrayq (1, 3)k: integermq(1,9)rp(1,9) q(1,3)q(1,0)p(1,3)6.2 全局棧式存儲分配全局棧式存儲分配6.2.3 調(diào)用序列調(diào)用序列 過程調(diào)用和過程返回都需要執(zhí)行一些代碼來過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等管理活動記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等6.2 全局棧式存儲分配全局棧式存儲分配6.2.3 調(diào)用序列調(diào)用序列 過程調(diào)用和過程返回都需要執(zhí)行一些代碼來過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等管理活動記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等 過程調(diào)用序列過程調(diào)用序列過程調(diào)

30、用時執(zhí)行的分配活動記錄，把信息填入它的過程調(diào)用時執(zhí)行的分配活動記錄，把信息填入它的域中的代碼域中的代碼6.2 全局棧式存儲分配全局棧式存儲分配6.2.3 調(diào)用序列調(diào)用序列 過程調(diào)用和過程返回都需要執(zhí)行一些代碼來過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等管理活動記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等 過程調(diào)用序列過程調(diào)用序列過程調(diào)用時執(zhí)行的分配活動記錄，把信息填入它的過程調(diào)用時執(zhí)行的分配活動記錄，把信息填入它的域中的代碼域中的代碼 過程返回序列過程返回序列過程返回時執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放活動記錄，過程返回時執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放活動記錄，使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼使調(diào)

31、用過程能夠繼續(xù)執(zhí)行的代碼6.2 全局棧式存儲分配全局棧式存儲分配 過程調(diào)用和過程返回都需要執(zhí)行一些代碼來過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等管理活動記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等 過程調(diào)用序列過程調(diào)用序列過程調(diào)用時執(zhí)行的分配活動記錄，把信息填入它的過程調(diào)用時執(zhí)行的分配活動記錄，把信息填入它的域中的代碼域中的代碼 過程返回序列過程返回序列過程返回時執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放活動記錄，過程返回時執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放活動記錄，使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼 調(diào)用序列和返回序列調(diào)用序列和返回序列常常都分成兩部分，分常常都分成兩部分，分處于

32、調(diào)用過程和被調(diào)用過程中處于調(diào)用過程和被調(diào)用過程中6.2 全局棧式存儲分配全局棧式存儲分配 即使是同一種語言，過程調(diào)用序列、返回序即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)嵙泻突顒佑涗浿懈饔虻呐欧糯涡?，也會因?qū)崿F(xiàn)而異現(xiàn)而異 設(shè)計這些序列和活動記錄設(shè)計這些序列和活動記錄的一些原則的一些原則返返 回回 值值臨臨 時時 數(shù)數(shù) 據(jù)據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問問 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.2 全局棧式存儲分配全局棧式存儲分配 即使是同一種語言，過程調(diào)用序列、返回序即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)?/p>

33、列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異現(xiàn)而異 設(shè)計這些序列和活動記錄設(shè)計這些序列和活動記錄的一些原則的一些原則以活動記錄中間的某個以活動記錄中間的某個位置作為基地址位置作為基地址返返 回回 值值臨臨 時時 數(shù)數(shù) 據(jù)據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問問 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.2 全局棧式存儲分配全局棧式存儲分配 即使是同一種語言，過程調(diào)用序列、返回序即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)嵙泻突顒佑涗浿懈饔虻呐欧糯涡颍矔驅(qū)崿F(xiàn)而異現(xiàn)而異 設(shè)計這些序列和活動記錄設(shè)計這些序列和活動記錄的一些原則的一些原則以活動記錄中間的某個

34、以活動記錄中間的某個位置作為基地址位置作為基地址長度能較早確定的域放在長度能較早確定的域放在活動記錄的中間活動記錄的中間返返 回回 值值臨臨 時時 數(shù)數(shù) 據(jù)據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問問 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.2 全局棧式存儲分配全局棧式存儲分配 即使是同一種語言，過程調(diào)用序列、返回序即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)嵙泻突顒佑涗浿懈饔虻呐欧糯涡颍矔驅(qū)崿F(xiàn)而異現(xiàn)而異 設(shè)計這些序列和活動記錄設(shè)計這些序列和活動記錄的一些原則的一些原則一般把臨時數(shù)據(jù)域放在一般把臨時數(shù)據(jù)域放在局部數(shù)據(jù)域的后面局部數(shù)據(jù)域的后面返返 回回

35、值值臨臨 時時 數(shù)數(shù) 據(jù)據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問問 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.2 全局棧式存儲分配全局棧式存儲分配 即使是同一種語言，過程調(diào)用序列、返回序即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)嵙泻突顒佑涗浿懈饔虻呐欧糯涡?，也會因?qū)崿F(xiàn)而異現(xiàn)而異 設(shè)計這些序列和活動記錄設(shè)計這些序列和活動記錄的一些原則的一些原則一般把臨時數(shù)據(jù)域放在一般把臨時數(shù)據(jù)域放在局部數(shù)據(jù)域的后面局部數(shù)據(jù)域的后面把參數(shù)域和可能有的返回把參數(shù)域和可能有的返回值域放在緊靠調(diào)用者活動值域放在緊靠調(diào)用者活動記錄的地方記錄的地方返返 回回 值值臨臨 時時 數(shù)數(shù) 據(jù)

36、據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問問 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.2 全局棧式存儲分配全局棧式存儲分配 即使是同一種語言，過程調(diào)用序列、返回序即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)嵙泻突顒佑涗浿懈饔虻呐欧糯涡颍矔驅(qū)崿F(xiàn)而異現(xiàn)而異 設(shè)計這些序列和活動記錄設(shè)計這些序列和活動記錄的一些原則的一些原則用同樣的代碼來執(zhí)行各個用同樣的代碼來執(zhí)行各個活動的保存和恢復(fù)活動的保存和恢復(fù)返返 回回 值值臨臨 時時 數(shù)數(shù) 據(jù)據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問問 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.2 全局棧式存儲分配全局棧式存儲分配

37、調(diào)用者和被調(diào)用者之間的任務(wù)劃分調(diào)用者和被調(diào)用者之間的任務(wù)劃分被調(diào)用者的責(zé)任被調(diào)用者的責(zé)任調(diào)用者的責(zé)任調(diào)用者的責(zé)任調(diào)用者的調(diào)用者的活動記錄活動記錄被被調(diào)用者的調(diào)用者的活動記錄活動記錄臨時數(shù)據(jù)局部數(shù)據(jù)臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 棧棧增增長長方方向向臨時數(shù)據(jù)局部數(shù)據(jù)臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲分配全局棧式存儲分配過程過程p調(diào)用過程調(diào)用過程q的調(diào)用序列的調(diào)用序列 p計算實(shí)參，依次放入棧頂，并在棧頂留出放計算實(shí)參，依次放入棧頂，并在棧頂

38、留出放返回值的空間。返回值的空間。top_sp的值在此過程中被改的值在此過程中被改變變 p把返回地址和當(dāng)前把返回地址和當(dāng)前base_sp的值存入的值存入q的活動的活動記錄中，建立記錄中，建立q的訪問鏈，增加的訪問鏈，增加base_sp的值的值 q保存寄存器的值和其它機(jī)器狀態(tài)信息保存寄存器的值和其它機(jī)器狀態(tài)信息 q根據(jù)局部數(shù)據(jù)域和臨時數(shù)據(jù)域的大小增加根據(jù)局部數(shù)據(jù)域和臨時數(shù)據(jù)域的大小增加top_sp的值，初始化它的局部數(shù)據(jù)，并開始的值，初始化它的局部數(shù)據(jù)，并開始執(zhí)行過程體執(zhí)行過程體6.2 全局棧式存儲分配全局棧式存儲分配調(diào)用者和被調(diào)用者之間的任務(wù)劃分調(diào)用者和被調(diào)用者之間的任務(wù)劃分被調(diào)用者的責(zé)任被調(diào)

39、用者的責(zé)任調(diào)用者的責(zé)任調(diào)用者的責(zé)任調(diào)用者的調(diào)用者的活動記錄活動記錄被被調(diào)用者的調(diào)用者的活動記錄活動記錄臨時數(shù)據(jù)局部數(shù)據(jù)臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 棧棧增增長長方方向向臨時數(shù)據(jù)局部數(shù)據(jù)臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲分配全局棧式存儲分配過程過程p調(diào)用過程調(diào)用過程q的返回序列的返回序列 q把返回值置入鄰近把返回值置入鄰近p的活動記錄的地方的活動記錄的地方 q對應(yīng)調(diào)用序列的步驟（對應(yīng)調(diào)用序列的步驟（4），減小），減小top_sp的的值值

40、 q恢復(fù)寄存器（包括恢復(fù)寄存器（包括base_sp）和機(jī)器狀態(tài)，和機(jī)器狀態(tài)，返回返回p p根據(jù)參數(shù)個數(shù)根據(jù)參數(shù)個數(shù)與類型和返回值類型與類型和返回值類型調(diào)整調(diào)整top_sp，然后取出返回值然后取出返回值6.2 全局棧式存儲分配全局棧式存儲分配調(diào)用者和被調(diào)用者之間的任務(wù)劃分調(diào)用者和被調(diào)用者之間的任務(wù)劃分被調(diào)用者的責(zé)任被調(diào)用者的責(zé)任調(diào)用者的責(zé)任調(diào)用者的責(zé)任調(diào)用者的調(diào)用者的活動記錄活動記錄被被調(diào)用者的調(diào)用者的活動記錄活動記錄臨時數(shù)據(jù)局部數(shù)據(jù)臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 棧棧增增長長方方向向臨

41、時數(shù)據(jù)局部數(shù)據(jù)臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲分配全局棧式存儲分配過程的參數(shù)個數(shù)可變的情況過程的參數(shù)個數(shù)可變的情況 函數(shù)返回值改成用寄存器傳遞函數(shù)返回值改成用寄存器傳遞 編譯器產(chǎn)生將這些參數(shù)逆序進(jìn)棧的代碼編譯器產(chǎn)生將這些參數(shù)逆序進(jìn)棧的代碼 被調(diào)用函數(shù)能準(zhǔn)確地知道第一個參數(shù)的位置被調(diào)用函數(shù)能準(zhǔn)確地知道第一個參數(shù)的位置 被調(diào)用函數(shù)根據(jù)第一個參數(shù)到棧中取第二、被調(diào)用函數(shù)根據(jù)第一個參數(shù)到棧中取第二、第三個參數(shù)等等第三個參數(shù)等等6.2 全局棧式存儲分配全局棧式存儲分配調(diào)用者和被調(diào)用者之間的任務(wù)劃分調(diào)用者和被調(diào)用者之間的任務(wù)劃分被調(diào)用者的責(zé)任被調(diào)用者的責(zé)

42、任調(diào)用者的責(zé)任調(diào)用者的責(zé)任調(diào)用者的調(diào)用者的活動記錄活動記錄被被調(diào)用者的調(diào)用者的活動記錄活動記錄臨時數(shù)據(jù)局部數(shù)據(jù)臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 棧棧增增長長方方向向臨時數(shù)據(jù)局部數(shù)據(jù)臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲分配全局棧式存儲分配6.2.4 棧上可變長數(shù)據(jù)棧上可變長數(shù)據(jù)活動記錄的長度在編譯時不能確定的情況活動記錄的長度在編譯時不能確定的情況 局部數(shù)組的大小要等到過程激活時才能確定局部數(shù)組的大小要等到過程激活時才能確定 在活動記錄中為這

43、樣的數(shù)組分別存放數(shù)組指在活動記錄中為這樣的數(shù)組分別存放數(shù)組指針的單元針的單元 運(yùn)行時，這些指針指向分配在棧頂?shù)拇鎯者\(yùn)行時，這些指針指向分配在棧頂?shù)拇鎯臻g間6.2 全局棧式存儲分配全局棧式存儲分配訪問動態(tài)分配的數(shù)組訪問動態(tài)分配的數(shù)組q的數(shù)組的數(shù)組q的活動記錄的活動記錄p的數(shù)組的數(shù)組p的活動記錄的活動記錄控制鏈控制鏈top_sp base_sp 數(shù)組數(shù)組A的指針的指針數(shù)組數(shù)組B的指針的指針數(shù)組數(shù)組A數(shù)組數(shù)組B控制鏈控制鏈. . . . . . .棧棧6.2 全局棧式存儲分配全局棧式存儲分配6.2.5 懸空引用懸空引用懸空引用：懸空引用：引用某個已被釋放的存儲單元引用某個已被釋放的存儲單元6.2

44、 全局棧式存儲分配全局棧式存儲分配6.2.5 懸空引用懸空引用懸空引用：懸空引用：引用某個已被釋放的存儲單元引用某個已被釋放的存儲單元main()|int dangle ( ) |int q;|int j = 20; q = dangle ( ); |return &j;|6.3 非局部名字的訪問非局部名字的訪問本節(jié)介紹本節(jié)介紹 無過程嵌套的靜態(tài)作用域（無過程嵌套的靜態(tài)作用域（C語言）語言） 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域（Pascal語言）語言） 動態(tài)作用域動態(tài)作用域（Lisp語言）語言）6.3 非局部名字的訪問非局部名字的訪問6.3.1 無過程嵌套的靜態(tài)作用域無過程嵌

45、套的靜態(tài)作用域 過程體中的非局部引用可以直接使用靜態(tài)確過程體中的非局部引用可以直接使用靜態(tài)確定的地址定的地址6.3 非局部名字的訪問非局部名字的訪問6.3.1 無過程嵌套的靜態(tài)作用域無過程嵌套的靜態(tài)作用域 過程體中的非局部引用可以直接使用靜態(tài)確過程體中的非局部引用可以直接使用靜態(tài)確定的地址定的地址 局部變量在棧頂?shù)幕顒佑涗浿?，可以通過局部變量在棧頂?shù)幕顒佑涗浿校梢酝ㄟ^base_sp指針來訪問指針來訪問6.3 非局部名字的訪問非局部名字的訪問6.3.1 無過程嵌套的靜態(tài)作用域無過程嵌套的靜態(tài)作用域 過程體中的非局部引用可以直接使用靜態(tài)確過程體中的非局部引用可以直接使用靜態(tài)確定的地址定的地址 局

46、部變量在棧頂?shù)幕顒佑涗浿校梢酝ㄟ^局部變量在棧頂?shù)幕顒佑涗浿?，可以通過base_sp指針來訪問指針來訪問 無須深入棧中取數(shù)據(jù)，無須訪問鏈無須深入棧中取數(shù)據(jù)，無須訪問鏈6.3 非局部名字的訪問非局部名字的訪問6.3.1 無過程嵌套的靜態(tài)作用域無過程嵌套的靜態(tài)作用域 過程體中的非局部引用可以直接使用靜態(tài)確過程體中的非局部引用可以直接使用靜態(tài)確定的地址定的地址 局部變量在棧頂?shù)幕顒佑涗浿校梢酝ㄟ^局部變量在棧頂?shù)幕顒佑涗浿?，可以通過base_sp指針來訪問指針來訪問 無須深入棧中取數(shù)據(jù)，無須訪問鏈無須深入棧中取數(shù)據(jù)，無須訪問鏈 過程可以作為參數(shù)來傳遞，也可以作為結(jié)果過程可以作為參數(shù)來傳遞，也可以作為

47、結(jié)果來返回來返回6.3 非局部名字的訪問非局部名字的訪問6.3.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域sortreadarrayexchangequicksortpartition6.3 非局部名字的訪問非局部名字的訪問6.3.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域過程過程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition36.3 非局部名字的訪問非局部名字的訪問6.3.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域過程過程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partiti

48、on3變量的嵌套深度：它的聲明所在過程的嵌套變量的嵌套深度：它的聲明所在過程的嵌套深度作為該名字的嵌套深度深度作為該名字的嵌套深度6.3 非局部名字的訪問非局部名字的訪問尋找非局部名字存儲單元的訪問鏈尋找非局部名字存儲單元的訪問鏈 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訪問鏈訪問鏈e (1, 3)訪問鏈訪問鏈sa, xq (1, 3)k, v訪問鏈訪問鏈q (1, 9)k, v訪問鏈訪問鏈p (1,

49、3)i, j訪問鏈訪問鏈6.3 非局部名字的訪問非局部名字的訪問假定過程假定過程p的嵌套深度為的嵌套深度為np，它引用嵌套深度它引用嵌套深度為為na的變量的變量a，na np。如何訪問如何訪問a的存儲單元的存儲單元sort1readarray2exchange2quicksort2partition36.3 非局部名字的訪問非局部名字的訪問假定過程假定過程p的嵌套深度為的嵌套深度為np，它引用嵌套深度它引用嵌套深度為為na的變量的變量a，na np。如何訪問如何訪問a的存儲單元的存儲單元 從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈np na次次6.3 非局部名字的訪問非局

50、部名字的訪問假定過程假定過程p的嵌套深度為的嵌套深度為np，它引用嵌套深度它引用嵌套深度為為na的變量的變量a，na np。如何訪問如何訪問a的存儲單元的存儲單元 從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈np na次次 到達(dá)到達(dá)a的聲明所在過程的活動記錄的聲明所在過程的活動記錄6.3 非局部名字的訪問非局部名字的訪問假定過程假定過程p的嵌套深度為的嵌套深度為np，它引用嵌套深度它引用嵌套深度為為na的變量的變量a，na np。如何訪問如何訪問a的存儲單元的存儲單元 從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈np na次次 到達(dá)到達(dá)a的聲明所在過程的

51、活動記錄的聲明所在過程的活動記錄 訪問鏈的追蹤用間接操作就可完成訪問鏈的追蹤用間接操作就可完成6.3 非局部名字的訪問非局部名字的訪問訪問非局部名字的存儲單元訪問非局部名字的存儲單元 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,

52、 9)k, v訪問鏈訪問鏈p (1, 3)i, j訪問鏈訪問鏈6.3 非局部名字的訪問非局部名字的訪問過程過程p對變量對變量a訪問時，訪問時，a的地址由下面的二元的地址由下面的二元組表示：組表示：（np na，a在活動記錄中的偏移）在活動記錄中的偏移）6.3 非局部名字的訪問非局部名字的訪問建立訪問鏈建立訪問鏈假定嵌套深度為假定嵌套深度為np的過程的過程p調(diào)用嵌套深度為調(diào)用嵌套深度為nx的過程的過程x np nx的情況的情況sort1readarray2exchange2quicksort2partition 36.3 非局部名字的訪問非局部名字的訪問建立訪問鏈建立訪問鏈假定嵌套深度為假定嵌套

53、深度為np的過程的過程p調(diào)用嵌套深度為調(diào)用嵌套深度為nx的過程的過程x np nx的情況的情況 x肯定就聲明在肯定就聲明在p中中6.3 非局部名字的訪問非局部名字的訪問建立訪問鏈建立訪問鏈假定嵌套深度為假定嵌套深度為np的過程的過程p調(diào)用嵌套深度為調(diào)用嵌套深度為nx的過程的過程x np nx的情況的情況 x肯定就聲明在肯定就聲明在p中中被調(diào)用過程的訪問鏈必須指向調(diào)用過程的活動記被調(diào)用過程的訪問鏈必須指向調(diào)用過程的活動記錄的訪問鏈錄的訪問鏈6.3 非局部名字的訪問非局部名字的訪問建立訪問鏈建立訪問鏈sort readarray exchange quicksort partitionsa, xq

54、 (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 非局部名字的訪問非局部名字的訪問建立訪問鏈建立訪問鏈假定嵌套深度為假定嵌套深度為np的過程的過程p調(diào)用嵌套深度為調(diào)用嵌套深度為nx的過程的過程x np nx的情況的情況sort1readarray2exchang

55、e2quicksort2partition 36.3 非局部名字的訪問非局部名字的訪問建立訪問鏈建立訪問鏈假定嵌套深度為假定嵌套深度為np的過程的過程p調(diào)用嵌套深度為調(diào)用嵌套深度為nx的過程的過程x np nx的情況的情況 p和和x的嵌套深度分別為的嵌套深度分別為1，2，nx 1的外圍過的外圍過程肯定相同程肯定相同6.3 非局部名字的訪問非局部名字的訪問建立訪問鏈建立訪問鏈假定嵌套深度為假定嵌套深度為np的過程的過程p調(diào)用嵌套深度為調(diào)用嵌套深度為nx的過程的過程x np nx的情況的情況 p和和x的嵌套深度分別為的嵌套深度分別為1，2，nx 1的外圍過的外圍過程肯定相同程肯定相同追蹤訪問鏈追蹤

56、訪問鏈np nx + 1次，到達(dá)了靜態(tài)包圍次，到達(dá)了靜態(tài)包圍x和和p的且離它們最近的那個過程的最新活動記錄的且離它們最近的那個過程的最新活動記錄6.3 非局部名字的訪問非局部名字的訪問建立訪問鏈建立訪問鏈假定嵌套深度為假定嵌套深度為np的過程的過程p調(diào)用嵌套深度為調(diào)用嵌套深度為nx的過程的過程x np nx的情況的情況 p和和x的嵌套深度分別為的嵌套深度分別為1，2，nx 1的外圍過的外圍過程肯定相同程肯定相同追蹤訪問鏈追蹤訪問鏈np nx + 1次，到達(dá)了靜態(tài)包圍次，到達(dá)了靜態(tài)包圍x和和p的且離它們最近的那個過程的最新活動記錄的且離它們最近的那個過程的最新活動記錄所到達(dá)的活動記錄就是所到達(dá)的

57、活動記錄就是x的活動記錄中的訪問鏈的活動記錄中的訪問鏈應(yīng)該指向的那個活動記錄應(yīng)該指向的那個活動記錄6.3 非局部名字的訪問非局部名字的訪問建立訪問鏈建立訪問鏈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訪問鏈訪問鏈

58、p (1, 3)i, j訪問鏈訪問鏈6.3 非局部名字的訪問非局部名字的訪問program param(input, output);（過程作為參數(shù)）過程作為參數(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.6.3 非局部名字的訪問非局部名字的訪問progra

59、m param(input, output);（過程作為參數(shù)）過程作為參數(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ù)傳遞時，怎樣在該過程被激活時建立它的訪問鏈過程被激活時建立它的訪問鏈6.3 非局部名字的訪問非局部名

60、字的訪問program param(input, output);（過程作為參數(shù)）過程作為參數(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ù)傳遞時，怎樣在該過程被激活時建立它的訪問鏈過程被激活時建立它的訪問鏈 從從b的訪問鏈難以