編譯原理陳意云chapter

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、地局部數(shù)據(jù)的地址可以用相對(duì)于某個(gè)位置的地址來(lái)表示址來(lái)表示 數(shù)據(jù)對(duì)象的存儲(chǔ)安排還有一個(gè)對(duì)齊問(wèn)題數(shù)據(jù)對(duì)象的存儲(chǔ)安排還有一個(gè)對(duì)齊問(wèn)題6.1 局部存儲(chǔ)分配局部存儲(chǔ)分配在在SPARC/Solaris工作站上下面兩個(gè)結(jié)構(gòu)的工作站上下面兩個(gè)結(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 局部存儲(chǔ)分配局部存儲(chǔ)分配在在SPARC/Solaris工作站上下面兩個(gè)結(jié)構(gòu)的工作站

16、上下面兩個(gè)結(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 局部存儲(chǔ)分配局部存儲(chǔ)分配在在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 局部存儲(chǔ)分配局部存儲(chǔ)分配6.1.5 程序塊程序塊 本身含有局部變量聲明的語(yǔ)句本身含有局部變量聲明的語(yǔ)句 可以嵌套可以嵌套 最接近的嵌套最接近的嵌套作用域規(guī)則作用域規(guī)則 并列程序塊不會(huì)同時(shí)活躍并列程序塊不會(huì)同時(shí)活躍 并列程序塊的變量可以重疊分配并列程序塊的變量可以重疊分配6.1 局部存儲(chǔ)分配局部存儲(chǔ)分配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 局部存儲(chǔ)分配局部存儲(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 /聲聲 明明 作作 用用 域域

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 局部存儲(chǔ)分配局部存儲(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; B

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

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

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

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

24、長(zhǎng)度和它在內(nèi)存中位置的限制，必須是在編譯時(shí)可以知道的必須是在編譯時(shí)可以知道的6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配靜態(tài)分配給語(yǔ)言帶來(lái)限制靜態(tài)分配給語(yǔ)言帶來(lái)限制 遞歸過(guò)程不被允許遞歸過(guò)程不被允許 數(shù)據(jù)對(duì)象的長(zhǎng)度和它在內(nèi)存中位置的限制，數(shù)據(jù)對(duì)象的長(zhǎng)度和它在內(nèi)存中位置的限制，必須是在編譯時(shí)可以知道的必須是在編譯時(shí)可以知道的 數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配 C語(yǔ)言程序的外部變量和程序中出現(xiàn)的常量語(yǔ)言程序的外部變量和程序中出現(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)分配自動(dòng)變量自動(dòng)變量 不能靜態(tài)分配不能靜態(tài)分配6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配6.2.2 活動(dòng)樹(shù)和運(yùn)行?；顒?dòng)樹(shù)和運(yùn)行?；顒?dòng)樹(shù)活動(dòng)樹(shù):用樹(shù)來(lái)描繪控制進(jìn)入和離開(kāi)活動(dòng)的方式用樹(shù)來(lái)描繪控制進(jìn)入和離開(kāi)活動(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 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配活動(dòng)樹(shù)的特點(diǎn)活動(dòng)樹(shù)的特點(diǎn) 每個(gè)結(jié)點(diǎn)代表某過(guò)程的一個(gè)活動(dòng)每個(gè)結(jié)點(diǎn)代表某

26、過(guò)程的一個(gè)活動(dòng) 根結(jié)點(diǎn)代表主程序的活動(dòng)根結(jié)點(diǎn)代表主程序的活動(dòng) 結(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的活動(dòng)進(jìn)入的活動(dòng)進(jìn)入b的活動(dòng)的活動(dòng) 結(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 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配當(dāng)前活躍著的過(guò)程活動(dòng)可以保存在一個(gè)棧中當(dāng)前活躍著的過(guò)程活動(dòng)可以保存在一個(gè)棧中控制棧的內(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 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配運(yùn)行棧：運(yùn)行棧：把控制棧中的信息拓廣到包括過(guò)程把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）活動(dòng)所需的所有局部信息（即活動(dòng)記錄） 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配運(yùn)行棧：運(yùn)行棧：把控制棧中的信息拓廣到包括過(guò)程把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）活動(dòng)所需的所有局部信息（即活動(dòng)記錄） ma : arraym6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配運(yùn)行棧：運(yùn)行棧：把控制棧中的信息拓廣到包括過(guò)程把控制棧中的信息拓廣到包括過(guò)

28、程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）活動(dòng)所需的所有局部信息（即活動(dòng)記錄） mi: integerra : arraymr6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配運(yùn)行棧：運(yùn)行棧：把控制棧中的信息拓廣到包括過(guò)程把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）活動(dòng)所需的所有局部信息（即活動(dòng)記錄） mk: integerq (1, 9)a : arraymq(1,9)r6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配運(yùn)行棧：運(yùn)行棧：把控制棧中的信息拓廣到包括過(guò)程把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）活動(dòng)所需的所有局部信息（即活動(dòng)記錄） 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 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配6.2.3 調(diào)用序列調(diào)用序列 過(guò)程調(diào)用和過(guò)程返回都需要執(zhí)行一些代碼來(lái)過(guò)程調(diào)用和過(guò)程返回都需要執(zhí)行一些代碼來(lái)管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配6.2.3 調(diào)用序列調(diào)用序列 過(guò)程調(diào)用和過(guò)程返回都需要執(zhí)行一些代碼來(lái)過(guò)程調(diào)用和過(guò)程返回都需要執(zhí)行一些代碼來(lái)管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等 過(guò)程調(diào)用序列過(guò)程調(diào)用序列過(guò)程調(diào)

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

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

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

33、列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異現(xiàn)而異 設(shè)計(jì)這些序列和活動(dòng)記錄設(shè)計(jì)這些序列和活動(dòng)記錄的一些原則的一些原則以活動(dòng)記錄中間的某個(gè)以活動(dòng)記錄中間的某個(gè)位置作為基地址位置作為基地址返返 回回 值值臨臨 時(shí)時(shí) 數(shù)數(shù) 據(jù)據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問(wèn)問(wèn) 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配 即使是同一種語(yǔ)言，過(guò)程調(diào)用序列、返回序即使是同一種語(yǔ)言，過(guò)程調(diào)用序列、返回序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)嵙泻突顒?dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異現(xiàn)而異 設(shè)計(jì)這些序列和活動(dòng)記錄設(shè)計(jì)這些序列和活動(dòng)記錄的一些原則的一些原則以活動(dòng)記錄中間的某個(gè)

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

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

36、據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問(wèn)問(wèn) 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配 即使是同一種語(yǔ)言，過(guò)程調(diào)用序列、返回序即使是同一種語(yǔ)言，過(guò)程調(diào)用序列、返回序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)嵙泻突顒?dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異現(xiàn)而異 設(shè)計(jì)這些序列和活動(dòng)記錄設(shè)計(jì)這些序列和活動(dòng)記錄的一些原則的一些原則用同樣的代碼來(lái)執(zhí)行各個(gè)用同樣的代碼來(lái)執(zhí)行各個(gè)活動(dòng)的保存和恢復(fù)活動(dòng)的保存和恢復(fù)返返 回回 值值臨臨 時(shí)時(shí) 數(shù)數(shù) 據(jù)據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問(wèn)問(wèn) 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配

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)用者的活動(dòng)記錄活動(dòng)記錄被被調(diào)用者的調(diào)用者的活動(dòng)記錄活動(dòng)記錄臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 棧棧增增長(zhǎng)長(zhǎng)方方向向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配過(guò)程過(guò)程p調(diào)用過(guò)程調(diào)用過(guò)程q的調(diào)用序列的調(diào)用序列 p計(jì)算實(shí)參，依次放入棧頂，并在棧頂留出放計(jì)算實(shí)參，依次放入棧頂，并在棧頂

38、留出放返回值的空間。返回值的空間。top_sp的值在此過(guò)程中被改的值在此過(guò)程中被改變變 p把返回地址和當(dāng)前把返回地址和當(dāng)前base_sp的值存入的值存入q的活動(dòng)的活動(dòng)記錄中，建立記錄中，建立q的訪問(wèn)鏈，增加的訪問(wèn)鏈，增加base_sp的值的值 q保存寄存器的值和其它機(jī)器狀態(tài)信息保存寄存器的值和其它機(jī)器狀態(tài)信息 q根據(jù)局部數(shù)據(jù)域和臨時(shí)數(shù)據(jù)域的大小增加根據(jù)局部數(shù)據(jù)域和臨時(shí)數(shù)據(jù)域的大小增加top_sp的值，初始化它的局部數(shù)據(jù)，并開(kāi)始的值，初始化它的局部數(shù)據(jù)，并開(kāi)始執(zhí)行過(guò)程體執(zhí)行過(guò)程體6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配調(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)用者的活動(dòng)記錄活動(dòng)記錄被被調(diào)用者的調(diào)用者的活動(dòng)記錄活動(dòng)記錄臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 棧棧增增長(zhǎng)長(zhǎng)方方向向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配過(guò)程過(guò)程p調(diào)用過(guò)程調(diào)用過(guò)程q的返回序列的返回序列 q把返回值置入鄰近把返回值置入鄰近p的活動(dòng)記錄的地方的活動(dòng)記錄的地方 q對(duì)應(yīng)調(diào)用序列的步驟（對(duì)應(yīng)調(diào)用序列的步驟（4），減?。?，減小top_sp的的值值

40、 q恢復(fù)寄存器（包括恢復(fù)寄存器（包括base_sp）和機(jī)器狀態(tài)，和機(jī)器狀態(tài)，返回返回p p根據(jù)參數(shù)個(gè)數(shù)根據(jù)參數(shù)個(gè)數(shù)與類型和返回值類型與類型和返回值類型調(diào)整調(diào)整top_sp，然后取出返回值然后取出返回值6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配調(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)用者的活動(dòng)記錄活動(dòng)記錄被被調(diào)用者的調(diào)用者的活動(dòng)記錄活動(dòng)記錄臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 棧棧增增長(zhǎng)長(zhǎng)方方向向臨

41、時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配過(guò)程的參數(shù)個(gè)數(shù)可變的情況過(guò)程的參數(shù)個(gè)數(shù)可變的情況 函數(shù)返回值改成用寄存器傳遞函數(shù)返回值改成用寄存器傳遞 編譯器產(chǎn)生將這些參數(shù)逆序進(jìn)棧的代碼編譯器產(chǎn)生將這些參數(shù)逆序進(jìn)棧的代碼 被調(diào)用函數(shù)能準(zhǔn)確地知道第一個(gè)參數(shù)的位置被調(diào)用函數(shù)能準(zhǔn)確地知道第一個(gè)參數(shù)的位置 被調(diào)用函數(shù)根據(jù)第一個(gè)參數(shù)到棧中取第二、被調(diào)用函數(shù)根據(jù)第一個(gè)參數(shù)到棧中取第二、第三個(gè)參數(shù)等等第三個(gè)參數(shù)等等6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配調(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)用者的活動(dòng)記錄活動(dòng)記錄被被調(diào)用者的調(diào)用者的活動(dòng)記錄活動(dòng)記錄臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 棧棧增增長(zhǎng)長(zhǎng)方方向向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配6.2.4 棧上可變長(zhǎng)數(shù)據(jù)棧上可變長(zhǎng)數(shù)據(jù)活動(dòng)記錄的長(zhǎng)度在編譯時(shí)不能確定的情況活動(dòng)記錄的長(zhǎng)度在編譯時(shí)不能確定的情況 局部數(shù)組的大小要等到過(guò)程激活時(shí)才能確定局部數(shù)組的大小要等到過(guò)程激活時(shí)才能確定 在活動(dòng)記錄中為這

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

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

45、套的靜態(tài)作用域 過(guò)程體中的非局部引用可以直接使用靜態(tài)確過(guò)程體中的非局部引用可以直接使用靜態(tài)確定的地址定的地址6.3 非局部名字的訪問(wèn)非局部名字的訪問(wèn)6.3.1 無(wú)過(guò)程嵌套的靜態(tài)作用域無(wú)過(guò)程嵌套的靜態(tài)作用域 過(guò)程體中的非局部引用可以直接使用靜態(tài)確過(guò)程體中的非局部引用可以直接使用靜態(tài)確定的地址定的地址 局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過(guò)局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過(guò)base_sp指針來(lái)訪問(wèn)指針來(lái)訪問(wèn)6.3 非局部名字的訪問(wèn)非局部名字的訪問(wèn)6.3.1 無(wú)過(guò)程嵌套的靜態(tài)作用域無(wú)過(guò)程嵌套的靜態(tài)作用域 過(guò)程體中的非局部引用可以直接使用靜態(tài)確過(guò)程體中的非局部引用可以直接使用靜態(tài)確定的地址定的地址 局

46、部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過(guò)局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過(guò)base_sp指針來(lái)訪問(wèn)指針來(lái)訪問(wèn) 無(wú)須深入棧中取數(shù)據(jù)，無(wú)須訪問(wèn)鏈無(wú)須深入棧中取數(shù)據(jù)，無(wú)須訪問(wèn)鏈6.3 非局部名字的訪問(wèn)非局部名字的訪問(wèn)6.3.1 無(wú)過(guò)程嵌套的靜態(tài)作用域無(wú)過(guò)程嵌套的靜態(tài)作用域 過(guò)程體中的非局部引用可以直接使用靜態(tài)確過(guò)程體中的非局部引用可以直接使用靜態(tài)確定的地址定的地址 局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過(guò)局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過(guò)base_sp指針來(lái)訪問(wèn)指針來(lái)訪問(wèn) 無(wú)須深入棧中取數(shù)據(jù)，無(wú)須訪問(wèn)鏈無(wú)須深入棧中取數(shù)據(jù)，無(wú)須訪問(wèn)鏈 過(guò)程可以作為參數(shù)來(lái)傳遞，也可以作為結(jié)果過(guò)程可以作為參數(shù)來(lái)傳遞，也可以作為

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

48、on3變量的嵌套深度：它的聲明所在過(guò)程的嵌套變量的嵌套深度：它的聲明所在過(guò)程的嵌套深度作為該名字的嵌套深度深度作為該名字的嵌套深度6.3 非局部名字的訪問(wèn)非局部名字的訪問(wèn)尋找非局部名字存儲(chǔ)單元的訪問(wèn)鏈尋找非局部名字存儲(chǔ)單元的訪問(wèn)鏈 sa, xq (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈訪問(wèn)鏈e (1, 3)訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈p (1,

49、3)i, j訪問(wèn)鏈訪問(wèn)鏈6.3 非局部名字的訪問(wèn)非局部名字的訪問(wèn)假定過(guò)程假定過(guò)程p的嵌套深度為的嵌套深度為np，它引用嵌套深度它引用嵌套深度為為na的變量的變量a，na np。如何訪問(wèn)如何訪問(wèn)a的存儲(chǔ)單元的存儲(chǔ)單元sort1readarray2exchange2quicksort2partition36.3 非局部名字的訪問(wèn)非局部名字的訪問(wèn)假定過(guò)程假定過(guò)程p的嵌套深度為的嵌套深度為np，它引用嵌套深度它引用嵌套深度為為na的變量的變量a，na np。如何訪問(wèn)如何訪問(wèn)a的存儲(chǔ)單元的存儲(chǔ)單元 從棧頂?shù)幕顒?dòng)記錄開(kāi)始，追蹤訪問(wèn)鏈從棧頂?shù)幕顒?dòng)記錄開(kāi)始，追蹤訪問(wèn)鏈np na次次6.3 非局部名字的訪問(wèn)非局

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

51、活動(dòng)記錄的聲明所在過(guò)程的活動(dòng)記錄 訪問(wèn)鏈的追蹤用間接操作就可完成訪問(wèn)鏈的追蹤用間接操作就可完成6.3 非局部名字的訪問(wèn)非局部名字的訪問(wèn)訪問(wèn)非局部名字的存儲(chǔ)單元訪問(wèn)非局部名字的存儲(chǔ)單元 sort readarray exchange quicksort partitionsa, xq (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈訪問(wèn)鏈e (1, 3)訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1,

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

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

54、 (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈訪問(wèn)鏈e (1, 3)訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈訪問(wèn)鏈6.3 非局部名字的訪問(wèn)非局部名字的訪問(wèn)建立訪問(wèn)鏈建立訪問(wèn)鏈假定嵌套深度為假定嵌套深度為np的過(guò)程的過(guò)程p調(diào)用嵌套深度為調(diào)用嵌套深度為nx的過(guò)程的過(guò)程x np nx的情況的情況sort1readarray2exchang

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

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

57、活動(dòng)記錄就是x的活動(dòng)記錄中的訪問(wèn)鏈的活動(dòng)記錄中的訪問(wèn)鏈應(yīng)該指向的那個(gè)活動(dòng)記錄應(yīng)該指向的那個(gè)活動(dòng)記錄6.3 非局部名字的訪問(wèn)非局部名字的訪問(wèn)建立訪問(wèn)鏈建立訪問(wèn)鏈sort readarray exchange quicksort partitionsa, xq (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈訪問(wèn)鏈e (1, 3)訪問(wèn)鏈訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈訪問(wèn)鏈

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

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

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