中國科學技術(shù)大學陳意云編譯原理全套參考資料陳意云編譯原理全套參考資料chapter6

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

2、據(jù)安排程序執(zhí)行過程中，所有活動記錄的組織方式 第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留過程能否訪問非局部變量第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式第六章 運行時存儲空間的組織和管理 影響

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

4、地分配第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式過程能否作為參數(shù)被傳遞過程能否作為結(jié)果值傳遞存儲塊能否在程序控制下動態(tài)地分配存儲塊是否必須顯式地釋放 局部存儲分配策略6.1.1 過程過程定義、過程調(diào)用、形式參數(shù)、實在參數(shù)、活動的生存期 局部存儲分配策略6.1.2 名字的作用域和綁定名字的作用域一個聲明起作用的程序部分稱為該聲明的作用域。即使一個名字在程序中只聲明一次，該名字在程序運行時也可能表示不同的數(shù)據(jù)對象。 局部存儲分配策略從名字到值的兩步映射。名字存儲單元狀態(tài)值環(huán)

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

6、態(tài) 對 應 過程的定義 過程的活動 名字的聲明 名字的綁定 局部存儲分配策略靜態(tài)概念和動態(tài)概念的對應靜 態(tài) 概 念 動 態(tài) 對 應 過程的定義 過程的活動 名字的聲明 名字的綁定 聲明的作用域 綁定的生存期 局部存儲分配策略6.1.3 活動記錄一般的活動記錄的布局返 回 值臨 時 數(shù) 據(jù)實 在 參 數(shù)控 制 鏈訪 問 鏈機 器 狀 態(tài)局 部 數(shù) 據(jù) 局部存儲分配策略6.1.4 局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。 局部存儲分配策略6.1.4 局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。變量所需的存儲空間可以根據(jù)其類型而靜態(tài)確定。 局部存儲分配策略6.1.4 局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的

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

8、以用相對于某個位置的地址來表示。數(shù)據(jù)對象的存儲安排還有一個對齊問題。 局部存儲分配策略在SPARC/Solaris工作站上下面兩個結(jié)構(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; 局部存儲分配策略在SPARC/Solaris工作站上下面兩個結(jié)構(gòu)的size分別是24和16，為什么不一樣？typedef struct _atypedef struct _bchar c1;0 char c1;

9、0long i;4 char c2; 1charc2;8 long i; 4double f;16 double f; 8a; b; 局部存儲分配策略在X86/Linux機器的結(jié)果和SPARC/Solaris工作站不一樣，是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; 局部存儲分配策略 程序塊本身含有局部變量聲明的語句可以嵌套最接近的嵌套作用域規(guī)則并列程序塊不會同時活躍并列程序塊的變量可以重疊

10、分配 局部存儲分配策略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 / 局部存儲分配策略main() / begin of B0 /int a = 0;int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of

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

12、3; / end of B3 / end of B1 / end of B0 /聲 明 作 用 域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 a0b0b1a2, b3重疊分配存儲單元 全局存儲分配策略介紹程序運行時所需的各個活動記錄在存儲空間的分配策略 全局存儲分配策略介紹程序運行時所需的各個活動記錄在存儲空間的分配策略描述過程的目標代碼怎樣訪問綁定到局部名字的存儲單元 全局存儲分配策略介紹程序運行時所需的各個活動記錄在存儲空間的分配策略描述過程的目標代碼怎樣訪問綁定到局部名字的存儲

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

14、的生存期是程序的整個運行時間。 全局存儲分配策略 靜態(tài)分配名字在程序被編譯時綁定到存儲單元，不需要運行時的任何支持。綁定的生存期是程序的整個運行時間?？刂圃俅芜M入該過程時，局部變量的值和控制上一次離開時的一樣。 全局存儲分配策略 靜態(tài)分配名字在程序被編譯時綁定到存儲單元，不需要運行時的任何支持。綁定的生存期是程序的整個運行時間。控制再次進入該過程時，局部變量的值和控制上一次離開時的一樣。每個活動記錄的大小是固定的。 全局存儲分配策略 靜態(tài)分配名字在程序被編譯時綁定到存儲單元，不需要運行時的任何支持。綁定的生存期是程序的整個運行時間。控制再次進入該過程時，局部變量的值和控制上一次離開時的一樣。每

15、個活動記錄的大小是固定的。過程調(diào)用時保存信息的地址在編譯時也是已知的。 全局存儲分配策略靜態(tài)分配給語言帶來限制遞歸過程不被允許 全局存儲分配策略靜態(tài)分配給語言帶來限制遞歸過程不被允許數(shù)據(jù)對象的長度和它在內(nèi)存中位置的限制，必須是在編譯時可以知道的 全局存儲分配策略靜態(tài)分配給語言帶來限制遞歸過程不被允許數(shù)據(jù)對象的長度和它在內(nèi)存中位置的限制，必須是在編譯時可以知道的數(shù)據(jù)結(jié)構(gòu)不能動態(tài)建立 全局存儲分配策略Fortran語言被設計成允許靜態(tài)存儲分配consume的代碼produce的代碼character 50 bufferinteger nextcharacter ccharacter 80 buff

16、erinteger nextproduce的活動記錄consume的活動記錄靜態(tài)數(shù)據(jù)代碼 全局存儲分配策略C語言程序的外部變量和程序中出現(xiàn)的常量都可以靜態(tài)分配。聲明在函數(shù)外面外部變量靜態(tài)外部變量聲明在函數(shù)里面靜態(tài)局部變量自動變量 全局存儲分配策略 棧式分配活動樹:用樹來描繪控制進入和離開活動的方式sq(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) 全局存儲分配策略活動樹的特點每個結(jié)點代表某過程的一個活動根結(jié)點代表主程序的活動結(jié)點a是結(jié)點b的父結(jié)點，當

17、且僅當控制流從a的活動進入b的活動結(jié)點a處于結(jié)點b的左邊，當且僅當a的生存期先于b的生存期 全局存儲分配策略當前活躍著的過程活動可以保存在一個棧中控制棧的內(nèi)容：s, q (1, 9), q (1, 3), q (2, 3) sq(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) 全局存儲分配策略運行棧：把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄） 全局存儲分配策略運行棧：把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記

18、錄） sa : arrays 全局存儲分配策略運行棧：把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄） si: integerra : arraysr 全局存儲分配策略運行棧：把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄） sk: integerq (1, 9)a : arraysq(1,9)r 全局存儲分配策略運行棧：把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄） sk: integerq (1, 9)a : arrayq (1, 3)k: integersq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3) 全局存儲分配策

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

20、活動記錄，把信息填入它的域中的代碼過程返回序列過程返回時執(zhí)行的恢復機器狀態(tài)，釋放活動記錄，使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼調(diào)用序列和返回序列常常都分成兩部分，分處于調(diào)用過程和被調(diào)用過程中 全局存儲分配策略即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異設計這些序列和活動記錄的一些原則是以活動記錄中間的某個位置作為基地址 全局存儲分配策略即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異設計這些序列和活動記錄的一些原則是以活動記錄中間的某個位置作為基地址長度能較早確定的域放在活動記錄的中間 全局存儲分配策略即使是同一種語言，過程調(diào)用序

21、列、返回序列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異設計這些序列和活動記錄的一些原則是以活動記錄中間的某個位置作為基地址長度能較早確定的域放在活動記錄的中間一般把臨時數(shù)據(jù)域放在局部數(shù)據(jù)域的后面 全局存儲分配策略即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異設計這些序列和活動記錄的一些原則是以活動記錄中間的某個位置作為基地址長度能較早確定的域放在活動記錄的中間一般把臨時數(shù)據(jù)域放在局部數(shù)據(jù)域的后面把參數(shù)域和可能有的返回值域放在緊靠調(diào)用者活動記錄的地方 全局存儲分配策略即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異設計這些序列

22、和活動記錄的一些原則是以活動記錄中間的某個位置作為基地址長度能較早確定的域放在活動記錄的中間一般把臨時數(shù)據(jù)域放在局部數(shù)據(jù)域的后面把參數(shù)域和可能有的返回值域放在緊靠調(diào)用者活動記錄的地方用同樣的代碼來執(zhí)行各個活動的保存和恢復 全局存儲分配策略調(diào)用者和被調(diào)用者之間的任務劃分返回值和參數(shù)控制鏈訪問鏈和機器狀態(tài)局部數(shù)據(jù)臨時數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時數(shù)據(jù) 控制鏈訪問鏈和機器狀態(tài)top_sp base_sp 被調(diào)用者的責任調(diào)用者的責任被調(diào)用者的活動記錄調(diào)用者的活動記錄棧 全局存儲分配策略過程p調(diào)用過程q的調(diào)用序列p在棧上留出放返回值的空間，并計算實參，依次放入棧頂，同時改變top_sp的值p把返回地址和當

23、前base_sp的值存入q的活動記錄中，建立q的訪問鏈，增加base_sp的值q保存寄存器的值和其它機器狀態(tài)信息q根據(jù)局部數(shù)據(jù)域和臨時數(shù)據(jù)域的大小增加top_sp的值，初始化它的局部數(shù)據(jù)，并開始執(zhí)行過程體 全局存儲分配策略調(diào)用者和被調(diào)用者之間的任務劃分返回值和參數(shù)控制鏈訪問鏈和機器狀態(tài)局部數(shù)據(jù)臨時數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時數(shù)據(jù) 控制鏈訪問鏈和機器狀態(tài)top_sp base_sp 被調(diào)用者的責任調(diào)用者的責任被調(diào)用者的活動記錄調(diào)用者的活動記錄棧 全局存儲分配策略過程p調(diào)用過程q的返回序列q把返回值置入鄰近p的活動記錄的地方q對應調(diào)用序列的步驟（4），減小top_sp的值 q恢復寄存器（包括bas

24、e_sp）和機器狀態(tài)，返回pp根據(jù)參數(shù)個數(shù)與類型和返回值類型調(diào)整top_sp，然后取出返回值 全局存儲分配策略調(diào)用者和被調(diào)用者之間的任務劃分返回值和參數(shù)控制鏈訪問鏈和機器狀態(tài)局部數(shù)據(jù)臨時數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時數(shù)據(jù) 控制鏈訪問鏈和機器狀態(tài)top_sp base_sp 被調(diào)用者的責任調(diào)用者的責任被調(diào)用者的活動記錄調(diào)用者的活動記錄棧 全局存儲分配策略過程的參數(shù)個數(shù)可變的情況函數(shù)返回值改成用寄存器傳遞編譯器產(chǎn)生將這些參數(shù)逆序進棧的代碼被調(diào)用函數(shù)能準確地知道第一個參數(shù)的位置被調(diào)用函數(shù)根據(jù)第一個參數(shù)到棧中取第二、第三個參數(shù)等等 全局存儲分配策略調(diào)用者和被調(diào)用者之間的任務劃分返回值和參數(shù)控制鏈訪問鏈和

25、機器狀態(tài)局部數(shù)據(jù)臨時數(shù)據(jù)返回值和參數(shù)局部數(shù)據(jù)臨時數(shù)據(jù) 控制鏈訪問鏈和機器狀態(tài)top_sp base_sp 被調(diào)用者的責任調(diào)用者的責任被調(diào)用者的活動記錄調(diào)用者的活動記錄棧 全局存儲分配策略活動記錄的長度在編譯時不能確定的情況局部數(shù)組的大小要等到過程激活時才能確定在活動記錄中為這樣的數(shù)組分別存放數(shù)組指針的單元運行時，這些指針指向分配在棧頂?shù)拇鎯臻g 全局存儲分配策略訪問動態(tài)分配的數(shù)組q的數(shù)組q的活動記錄p的數(shù)組控制鏈top_sp base_sp p的活動記錄數(shù)組A的指針數(shù)組B的指針數(shù)組A數(shù)組B控制鏈 全局存儲分配策略懸空引用：引用某個已被釋放的存儲單元 全局存儲分配策略懸空引用：引用某個已被釋放的

26、存儲單元main()|int dangle ( ) |int q;|int j = 20; q = dangle ( );|return &j;| 全局存儲分配策略 堆式分配棧式分配策略在下列情況下行不通：過程活動停止后，局部名字的值還必須維持 全局存儲分配策略 堆式分配棧式分配策略在下列情況下行不通：過程活動停止后，局部名字的值還必須維持被調(diào)用者的活動比調(diào)用者的活動活得更長，此時活動樹不能正確描繪程序的控制流 全局存儲分配策略 堆式分配棧式分配策略在下列情況下行不通：過程活動停止后，局部名字的值還必須維持被調(diào)用者的活動比調(diào)用者的活動活得更長，此時活動樹不能正確描繪程序的控制流不遵守棧式規(guī)則的

27、有Pascal語言和C語言的動態(tài)變量 全局存儲分配策略 堆式分配棧式分配策略在下列情況下行不通：過程活動停止后，局部名字的值還必須維持被調(diào)用者的活動比調(diào)用者的活動活得更長，此時活動樹不能正確描繪程序的控制流不遵守棧式規(guī)則的有Pascal語言和C語言的動態(tài)變量Java禁止程序員自己釋放空間 非局部名字的訪問本節(jié)介紹無過程嵌套的靜態(tài)作用域（C語言）有過程嵌套的靜態(tài)作用域（Pascal語言）動態(tài)作用域（Lisp語言） 非局部名字的訪問 無過程嵌套的靜態(tài)作用域過程體中的非局部引用可以直接使用靜態(tài)確定的地址 非局部名字的訪問 無過程嵌套的靜態(tài)作用域過程體中的非局部引用可以直接使用靜態(tài)確定的地址局部變量在

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

29、的靜態(tài)作用域過程嵌套深度sort1readarray2exchange2quicksort2partition3 非局部名字的訪問 有過程嵌套的靜態(tài)作用域過程嵌套深度sort1readarray2exchange2quicksort2partition3變量的嵌套深度：它的聲明所在過程的嵌套深度作為該名字的嵌套深度 非局部名字的訪問尋找非局部名字存儲單元的訪問鏈 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)訪問鏈s

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

31、引用嵌套深度為na的變量a，na np。如何訪問a的存儲單元？從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈np na次。到達a的聲明所在過程的活動記錄。訪問鏈的追蹤用間接操作就可完成。 非局部名字的訪問訪問非局部名字的存儲單元 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, 3)i, j訪問鏈sort readarray exchange qu

32、icksort partition 非局部名字的訪問過程p對變量a訪問時，a的地址由下面的二元組表示：（np na，a在活動記錄中的偏移） 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況x肯定就聲明在p中 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況x肯定就聲明在p中被調(diào)用過程的訪問鏈必須指向調(diào)用過程的活動記錄的訪問鏈 非局部名字的訪問建立訪問鏈sa, xq (1, 9)k, v訪問鏈sa, xq (1

33、, 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訪問鏈sort readarray exchange quicksort partition 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況p和x的嵌套深度分別為1，2，nx 1的外圍過程

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

35、 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訪問鏈sort readarray exchange quicksort partition 非局部名字的訪問program param(input, output);（過程作為參數(shù)）procedure b(function h(n: integer): integer); begin wri

36、teln(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. 非局部名字的訪問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: int

37、eger): integer; begin f := m+n end f; begin m := 0; b(f) end c; begin cend.過程作為參數(shù)傳遞時，怎樣在該過程被激活時建立它的訪問鏈。 非局部名字的訪問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

38、 f; begin m := 0; b(f) end c; begin cend.過程作為參數(shù)傳遞時，怎樣在該過程被激活時建立它的訪問鏈 從b的訪問鏈難以建立f的訪問鏈 非局部名字的訪問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.訪 問 鏈訪 問 鏈p

39、aramcmb 非局部名字的訪問program ret (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

40、) end; begin f := a; b(f) end. 非局部名字的訪問program ret (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): intege

41、r); begin writeln ( g(2) end; begin f := a; b(f) end.retabaddm 非局部名字的訪問C語言的函數(shù)聲明不能嵌套，函數(shù)不論在什么情況下激活，要訪問的數(shù)據(jù)分成兩種情況:非靜態(tài)局部變量（包括形式參數(shù)），它們分配在活動記錄棧頂?shù)哪莻€活動記錄中外部變量（包括定義在其它源文件中的外部變量）和靜態(tài)的局部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū) 非局部名字的訪問 動態(tài)作用域被調(diào)用過程的非局部名字a和它在調(diào)用過程中引用的是同樣的存儲單元。 非局部名字的訪問 動態(tài)作用域被調(diào)用過程的非局部名字a和它在調(diào)用過程中引用的是同樣的存儲單元。新的綁定僅為被調(diào)用過程的局部名字建立，

42、這些名字在被調(diào)用過程的活動記錄中占用的存儲單元。 非局部名字的訪問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 r := 0.25; show; small; writeln; show; small; writeln end. 非局部名字的訪問program dynamic(input, output); var r: real; proc

43、edure 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.dynamicshowsmallsmallshowshowshow 非局部名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure s

44、mall; 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.dynamicshowsmallsmallshowshowshow 非局部名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin

45、 r := 0.125; show end; begin動態(tài)作用域 r := 0.25;0.250 0.125 show; small; writeln;0.250 0.125 show; small; writeln end.dynamicshowsmallsmallshowshowshow 非局部名字的訪問實現(xiàn)動態(tài)作用域的方法深訪問用控制鏈搜索運行棧，尋找包含該非局部名字的第一個活動記錄淺訪問為每個名字在靜態(tài)分配的存儲空間中保存它的當前值當過程p的新活動出現(xiàn)時，p的局部名字n使用在靜態(tài)數(shù)據(jù)區(qū)分配給n的存儲單元。n的先前值可以保存在p的活動記錄中，當p的活動結(jié)束時再恢復 參 數(shù) 傳 遞6.4

46、.1 值調(diào)用實參的右值傳給被調(diào)用過程 值調(diào)用可以如下實現(xiàn)把形參當作所在過程的局部名看待，形參的存儲單元在該過程的活動記錄中。 參 數(shù) 傳 遞6.4.1 值調(diào)用實參的右值傳給被調(diào)用過程 值調(diào)用可以如下實現(xiàn)把形參當作所在過程的局部名看待，形參的存儲單元在該過程的活動記錄中。調(diào)用過程計算實參，并把右值放入形參的存儲單元中。 參 數(shù) 傳 遞6.4.2 引用調(diào)用實參的左值傳給被調(diào)用過程 引用調(diào)用可以如下實現(xiàn)：把實參的左值放入形參的存儲單元。 參 數(shù) 傳 遞6.4.2 引用調(diào)用實參的左值傳給被調(diào)用過程 引用調(diào)用可以如下實現(xiàn)：把實參的左值放入形參的存儲單元。在被調(diào)用過程的目標代碼中，任何對形參的引用都是通過

47、傳給該過程的指針來間接引用實參的。 參 數(shù) 傳 遞6.4.3 復寫-恢復調(diào)用值調(diào)用和引用調(diào)用的混合復寫-恢復調(diào)用可以如下實現(xiàn)：實參的右值和左值同時傳給被調(diào)用過程。 參 數(shù) 傳 遞6.4.3 復寫-恢復調(diào)用值調(diào)用和引用調(diào)用的混合復寫-恢復調(diào)用可以如下實現(xiàn)：實參的右值和左值同時傳給被調(diào)用過程。在被調(diào)用過程中，像值調(diào)用那樣使用實參的右值。 參 數(shù) 傳 遞6.4.3 復寫-恢復調(diào)用值調(diào)用和引用調(diào)用的混合復寫-恢復調(diào)用可以如下實現(xiàn)：實參的右值和左值同時傳給被調(diào)用過程。在被調(diào)用過程中，像值調(diào)用那樣使用實參的右值。當控制返回調(diào)用過程時，根據(jù)傳遞來的實參的左值，將形參當前的值復寫到實參存儲單元。 參 數(shù) 傳

48、遞6.4.4 換名調(diào)用用實參表達式對形參進行正文替換。procedure swap(var x, y: integer);var temp: integer; begin temp := x; x := y; y := temp end 參 數(shù) 傳 遞6.4.4 換名調(diào)用用實參表達式對形參進行正文替換。procedure swap(var x, y: integer);var temp: integer; begin 調(diào)用swap(i, ai) temp := x; x := y; y := temp end 參 數(shù) 傳 遞6.4.4 換名調(diào)用用實參表達式對形參進行正文替換。procedure

49、 swap(var x, y: integer);var temp: integer; begin 調(diào)用swap(i, ai) temp := x;temp := i; x := y;i := ai; y := tempai := temp end本 章 要 點影響存儲分配策略的語言特征各種存儲分配策略，主要了解靜態(tài)分配和動態(tài)棧式分配活動記錄中各種數(shù)據(jù)域的作用和安排非局部數(shù)據(jù)訪問的實現(xiàn)方法各種參數(shù)傳遞方式及其實現(xiàn)例 題 1一個C語言程序及其在X86/Linux操作系統(tǒng)上的編譯結(jié)果如下。根據(jù)所生成的匯編程序來解釋程序中四個變量的存儲分配、作用域、生存期和置初值方式等方面的區(qū)別。static lo

50、ng aa = 10;short bb = 20;func() static long cc = 30; short dd = 40;例 題 1.data|.align 4.align 4|.type cc.2,object.type aa,object|.size cc.2,4.size aa,4| cc.2:aa:|.long 30.long 10| .text.globl bb|.align 4.align 2| .globl func .type bb,object| func:.size bb,2|. . .bb:|movw $40,-2(%ebp).value 20|. . .例

51、題 2main()char *cp1, *cp2;cp1 = 12345;cp2 = abcdefghij;strcpy(cp1,cp2);printf(cp1 = %sncp2 = %sn, cp1, cp2);運行結(jié)果是：cp1 = abcdefghijcp2 = ghij為什么cp2所指的串被修改了？例 題 2因為常量串“12345”和“abcdefghij”連續(xù)分配在常數(shù)區(qū)執(zhí)行前：1 2 3 4 5 0 a b c d e f g h i j 0 cp1 cp2例 題 2因為常量串“12345”和“abcdefghij”連續(xù)分配在常數(shù)區(qū)執(zhí)行前：1 2 3 4 5 0 a b c d e

52、 f g h i j 0 cp1 cp2執(zhí)行后：a b c d e f g h i j 0 f g h i j 0 cp1 cp2例 題 2因為常量串“12345”和“abcdefghij”連續(xù)分配在常數(shù)區(qū)執(zhí)行前：1 2 3 4 5 0 a b c d e f g h i j 0 cp1 cp2執(zhí)行后：a b c d e f g h i j 0 f g h i j 0 cp1 cp2現(xiàn)在的編譯器大都把程序中的串常量單獨存放在一個只讀的數(shù)據(jù)段中。例 題 3下面的程序運行時輸出3個整數(shù)。試從運行環(huán)境和printf的實現(xiàn)來分析，為什么此程序會有3個整數(shù)輸出？ main()printf(“%d, %d

53、, %dn”);例 題 4func(i)long i;long j; j= i -1;func(j);例 題 4func(i)func: long i; pushl %ebp 老的基地址指針壓棧 movl %esp,%ebp修改基地址指針 long j; subl $4,%esp 為j分配空間 j= i -1; movl 8(%ebp),%edx 取i到寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把實參j的值壓棧 call func 函數(shù)調(diào)用 addl $4,%esp 恢復棧

54、頂指針L1: leave 恢復基地址指針、棧頂指針 ret 返回調(diào)用者例 題 4func(i)func: long i; pushl %ebp 老的基地址指針壓棧 movl %esp,%ebp修改基地址指針 long j; subl $4,%esp 為j分配空間 j= i -1; movl 8(%ebp),%edx 取i到寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把實參j的值壓棧 call func 函數(shù)調(diào)用 addl $4,%esp 恢復棧頂指針L1: leave 恢復基

55、地址指針、棧頂指針 ret 返回調(diào)用者. . .參數(shù)i返址控制鏈變量j. . .ebp esp 棧低高例 題 4func(i)func: long i; pushl %ebp 老的基地址指針壓棧 movl %esp,%ebp修改基地址指針 long j; subl $4,%esp 為j分配空間 j= i -1; movl 8(%ebp),%edx 取i到寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把實參j的值壓棧 call func 函數(shù)調(diào)用 addl $4,%esp 恢復棧

56、頂指針L1: leave 恢復基地址指針、棧頂指針 ret 返回調(diào)用者. . .參數(shù)i返址控制鏈變量j. . .ebp esp 棧低高調(diào)用序列返回序列例 題 5func(i,j,f,e) short i,j; float f,e; short i1,j1; float f1,e1; printf(&i,&j,&f,&e); printf(&i1,&j1,&f1,&e1); main() short i,j; float f,e; func(i,j,f,e);Address of i,j,f,e = 36, 42, 44, 54（八進制數(shù)）Address of i1,j1,f1,e1 = 26,

57、 24, 20, 14 例 題 5func(i,j,f,e) Sizes of short, int, long, float, short i,j; float f,e;double = 2, 4, 4, 4, 8 short i1,j1; float f1,e1; printf(&i,&j,&f,&e); printf(&i1,&j1,&f1,&e1); main() short i,j; float f,e; func(i,j,f,e);Address of i,j,f,e = 36, 42, 44, 54（八進制數(shù)）Address of i1,j1,f1,e1 = 26, 24, 20, 14例 題 5func(i,j,f,e) Sizes of short, int, long, float, short i,j; float f,e;double = 2, 4, 4, 4, 8 short i1,j1; float f1,e1; printf(&i,&j,&f,&e); printf(&i1,&j1,&f1,&e1); main() 為什么4個形式參數(shù)i,j,f,e的地址 間隔和它們類型的大小不一致 short i,j; float f,e; func(