編譯技術(shù)：第07章 運(yùn)行時(shí)存儲(chǔ)空間的組織

1、第七章 運(yùn)行時(shí)存儲(chǔ)空間的組織運(yùn)行時(shí)環(huán)境從從“程序運(yùn)行程序運(yùn)行”說(shuō)起說(shuō)起 最初由最初由“OSOS”對(duì)程序進(jìn)行控制對(duì)程序進(jìn)行控制 OS OS 為程序分配存儲(chǔ)空間為程序分配存儲(chǔ)空間 OS OS 將代碼復(fù)制到所分配的存儲(chǔ)空間將代碼復(fù)制到所分配的存儲(chǔ)空間 OS OS 跳轉(zhuǎn)到程序的入口地址（跳轉(zhuǎn)到程序的入口地址（main）Zhou, Erqiang2School of Information and Software Engineering運(yùn)行時(shí)環(huán)境函數(shù)的活動(dòng)函數(shù)的活動(dòng) 函數(shù)的函數(shù)的一次執(zhí)行一次執(zhí)行稱為函數(shù)的一次活動(dòng)稱為函數(shù)的一次活動(dòng) 函數(shù)的活動(dòng)需要函數(shù)的活動(dòng)需要 可執(zhí)行代碼可執(zhí)行代碼 存放所需信息的數(shù)據(jù)

2、結(jié)構(gòu)存放所需信息的數(shù)據(jù)結(jié)構(gòu) 活動(dòng)記錄活動(dòng)記錄Zhou, Erqiang3School of Information and Software Engineering活動(dòng)記錄關(guān)于活動(dòng)記錄關(guān)于活動(dòng)記錄 討論討論一個(gè)活動(dòng)記錄一個(gè)活動(dòng)記錄中的數(shù)據(jù)安排中的數(shù)據(jù)安排 程序執(zhí)行過(guò)程中程序執(zhí)行過(guò)程中 所有活動(dòng)記錄所有活動(dòng)記錄的組織方式的組織方式 Zhou, Erqiang4School of Information and Software Engineering活動(dòng)記錄Zhou, Erqiang5School of Information and Software Engineeringintint g()

3、 g() returnreturn 10; 10; intint f() f() returnreturn g(); g(); intint main() main() g(); g(); f(); f(); returnreturn 0; 0; intint g() g() returnreturn 10; 10; intint f(int x) f(int x) if if (x(x = 0)= 0) return return g(); g(); elseelse returnreturn f(x-1); f(x-1); intint main() main() f( f(2 2););

4、 returnreturn 0; 0; 函數(shù)棧幀Zhou, Erqiang6School of Information and Software Engineering函數(shù)棧幀函數(shù)棧幀(stack frame)(stack frame) 函數(shù)的每次執(zhí)行都獨(dú)立的對(duì)應(yīng)一個(gè)函數(shù)的每次執(zhí)行都獨(dú)立的對(duì)應(yīng)一個(gè)棧幀棧幀 當(dāng)前被執(zhí)行函數(shù)對(duì)應(yīng)的當(dāng)前被執(zhí)行函數(shù)對(duì)應(yīng)的棧幀棧幀在在棧的頂部棧的頂部 通過(guò)通過(guò)基址指針基址指針 與與 變量的偏移變量的偏移訪問(wèn)臨時(shí)變量訪問(wèn)臨時(shí)變量 void MyFunction()void MyFunction() int a, b, c; int a, b, c; a = 10; a =

5、 10; b = 5; b = 5; c = 2; c = 2;_MyFunction:_MyFunction: push push ebp ; ebp ; 保存保存“基址指針基址指針” ebpebp mov mov ebp, esp ; ebp, esp ; “基址指針基址指針” ebpebp指向棧頂指向棧頂 sub sub esp, 12 ; esp, 12 ; 在棧中為臨時(shí)變量分配空間在棧中為臨時(shí)變量分配空間mov ebp - 4, 10 ; mov ebp - 4, 10 ; 將將1010保存至變量保存至變量 a amov ebp - 8, 5 ; location of bmov e

6、bp - 8, 5 ; location of bmov ebp - 12, 2 ; location of cmov ebp - 12, 2 ; location of c活動(dòng)記錄函數(shù)被多次調(diào)用函數(shù)被多次調(diào)用 對(duì)應(yīng)多個(gè)活動(dòng)記錄對(duì)應(yīng)多個(gè)活動(dòng)記錄 程序運(yùn)行對(duì)應(yīng)一個(gè)程序運(yùn)行對(duì)應(yīng)一個(gè)活動(dòng)記錄樹活動(dòng)記錄樹 輸入不同，活動(dòng)記錄樹輸入不同，活動(dòng)記錄樹可能可能有所不同有所不同 活動(dòng)記錄之間活動(dòng)記錄之間“相互嵌套相互嵌套” 可用可用“棧?！眮?lái)跟蹤各活動(dòng)記錄來(lái)跟蹤各活動(dòng)記錄 當(dāng)函數(shù)返回后相應(yīng)的記錄當(dāng)函數(shù)返回后相應(yīng)的記錄不再不再被引用被引用Zhou, Erqiang7School of Information a

7、nd Software Engineering活動(dòng)記錄“當(dāng)函數(shù)返回后相應(yīng)的記錄當(dāng)函數(shù)返回后相應(yīng)的記錄不再被引用不再被引用”有沒(méi)有反例？有沒(méi)有反例？Zhou, Erqiang8School of Information and Software Engineeringfunctionfunction CreateCounter() CreateCounter() varvar counter = 0; counter = 0;returnreturn function() function() counter +;counter +;returnreturn counter; counter;

8、活動(dòng)記錄“當(dāng)函數(shù)返回后相應(yīng)的記錄當(dāng)函數(shù)返回后相應(yīng)的記錄不再被引用不再被引用”反例反例Zhou, Erqiang9School of Information and Software Engineeringfunction CreateCounter() function CreateCounter() var counter = 0;var counter = 0;return function() return function() counter +;counter +;return counter;return counter; function MyFunction() functio

9、n MyFunction() f = CreateCounter();f = CreateCounter();print(f();print(f();print(f();print(f(); MyFunctionCreateCountercounter = 0;f = 活動(dòng)記錄“當(dāng)函數(shù)返回后相應(yīng)的記錄當(dāng)函數(shù)返回后相應(yīng)的記錄不再被引用不再被引用”反例反例Zhou, Erqiang10School of Information and Software Engineeringfunction CreateCounter() function CreateCounter() var counter

10、= 0;var counter = 0;return function() return function() counter +;counter +;return counter;return counter; function MyFunction() function MyFunction() f = CreateCounter();f = CreateCounter();f();f();f();f(); MyFunctionCreateCountercounter = 1;f = counter=2;兩種鏈接的區(qū)別？?jī)煞N鏈接的區(qū)別？活動(dòng)記錄活動(dòng)記錄的內(nèi)容活動(dòng)記錄的內(nèi)容 返回地址返回地址

11、 控制鏈（動(dòng)態(tài)鏈接）控制鏈（動(dòng)態(tài)鏈接） 指向主調(diào)程序的活動(dòng)記錄指向主調(diào)程序的活動(dòng)記錄 存取鏈（靜態(tài)鏈接）存取鏈（靜態(tài)鏈接） 指向指向非局部變量非局部變量所在的活動(dòng)記錄所在的活動(dòng)記錄Zhou, Erqiang11School of Information and Software Engineering活動(dòng)記錄活動(dòng)記錄的內(nèi)容活動(dòng)記錄的內(nèi)容 CPU CPU 現(xiàn)場(chǎng)現(xiàn)場(chǎng) 實(shí)際參數(shù)的個(gè)數(shù)實(shí)際參數(shù)的個(gè)數(shù) 形式參數(shù)形式參數(shù) 局部變量局部變量 臨時(shí)變量臨時(shí)變量 等等等等Zhou, Erqiang12School of Information and Software Engineering實(shí)際參數(shù)在哪里？實(shí)際

12、參數(shù)在哪里？局部變量局部變量 和和 臨時(shí)變量臨時(shí)變量有什么區(qū)別？有什么區(qū)別？編譯器不同而有所不同編譯器不同而有所不同變量的存儲(chǔ)分配局部變量局部變量 存儲(chǔ)空間存儲(chǔ)空間大小大小可根據(jù)其類型而可根據(jù)其類型而靜態(tài)確定靜態(tài)確定分配方法分配方法 按這些變量聲明時(shí)出現(xiàn)的次序按這些變量聲明時(shí)出現(xiàn)的次序 在局部數(shù)據(jù)域中依次分配空間在局部數(shù)據(jù)域中依次分配空間局部數(shù)據(jù)的地址局部數(shù)據(jù)的地址 棧幀的首地址棧幀的首地址 + + 數(shù)據(jù)的偏移數(shù)據(jù)的偏移Zhou, Erqiang13School of Information and Software Engineering變量的存儲(chǔ)分配局部數(shù)據(jù)的地址局部數(shù)據(jù)的地址 D D表示

13、活動(dòng)記錄的首地址表示活動(dòng)記錄的首地址 offset(x) offset(x)： x x 在活動(dòng)記錄中的偏移在活動(dòng)記錄中的偏移 D+offset(x) D+offset(x) 為為 x x 的地址的地址1)1)如果如果 D D 和和 offset( offset(x x) ) 在編譯時(shí)都能確定下來(lái)在編譯時(shí)都能確定下來(lái) x x 稱為稱為靜態(tài)變量靜態(tài)變量 如果語(yǔ)言僅支持靜態(tài)變量如果語(yǔ)言僅支持靜態(tài)變量 那么將那么將不支持不支持哪些功能？哪些功能？Zhou, Erqiang14School of Information and Software Engineering活動(dòng)記錄在編譯時(shí)可確定活動(dòng)記錄在編譯

14、時(shí)可確定包括包括大小大小和和位置位置變量的存儲(chǔ)分配D D表示活動(dòng)記錄的首地址表示活動(dòng)記錄的首地址 編譯時(shí)編譯時(shí)靜態(tài)確定靜態(tài)確定( (分配分配) ) 函數(shù)每次活動(dòng)時(shí)函數(shù)每次活動(dòng)時(shí) 活動(dòng)記錄的位置活動(dòng)記錄的位置相對(duì)固定相對(duì)固定 進(jìn)程空間只允許有該函數(shù)的進(jìn)程空間只允許有該函數(shù)的一個(gè)活動(dòng)一個(gè)活動(dòng)記錄記錄 不支持遞歸調(diào)用不支持遞歸調(diào)用 不支持動(dòng)態(tài)數(shù)組不支持動(dòng)態(tài)數(shù)組Zhou, Erqiang15School of Information and Software Engineering相對(duì)于程序自己相對(duì)于程序自己 的進(jìn)程空間的進(jìn)程空間變量的存儲(chǔ)分配2 2）如果）如果 offset( offset(x x)

15、 ) 在在編譯編譯時(shí)能確定下來(lái)時(shí)能確定下來(lái) D D 在在運(yùn)行運(yùn)行時(shí)能確定下來(lái)時(shí)能確定下來(lái) x x 稱為稱為半靜態(tài)變量半靜態(tài)變量 如果語(yǔ)言支持半靜態(tài)變量如果語(yǔ)言支持半靜態(tài)變量 程序單元可多次被激活程序單元可多次被激活 支持遞歸調(diào)用支持遞歸調(diào)用 活動(dòng)記錄可用棧來(lái)實(shí)現(xiàn)活動(dòng)記錄可用棧來(lái)實(shí)現(xiàn) 變量支持變量支持“棧式分配棧式分配”Zhou, Erqiang16School of Information and Software Engineering活動(dòng)記錄活動(dòng)記錄大小大小 在編譯時(shí)可確定在編譯時(shí)可確定變量的存儲(chǔ)分配3 3）如果）如果 D D和和offset(offset(x x) ) 在編譯時(shí)不能確定下

16、來(lái)在編譯時(shí)不能確定下來(lái) 但運(yùn)行能確定但運(yùn)行能確定 x x 稱為稱為半動(dòng)態(tài)變量半動(dòng)態(tài)變量 支持語(yǔ)言：支持語(yǔ)言：C99 C99 動(dòng)態(tài)數(shù)組動(dòng)態(tài)數(shù)組Zhou, Erqiang17School of Information and Software Engineering活動(dòng)記錄活動(dòng)記錄大小位置大小位置在編譯時(shí)不能確定在編譯時(shí)不能確定在運(yùn)行時(shí)可確定在運(yùn)行時(shí)可確定intint f() f() intint n; n; scanf(%d, &n); scanf(%d, &n); intint ar arrayrayn;n; printf(%dn, printf(%dn, sizeofsize

17、of(arrray);(arrray); returnreturn 0; 0; 活動(dòng)記錄活動(dòng)記錄保存什么？保存什么？變量的存儲(chǔ)分配3 3）x x 為為半動(dòng)態(tài)變量半動(dòng)態(tài)變量 x x 的其它屬于信息，如的其它屬于信息，如 數(shù)組元素的類型數(shù)組元素的類型 數(shù)組的維數(shù)數(shù)組的維數(shù) 數(shù)組首地址指針數(shù)組首地址指針 僅分配空間，運(yùn)行時(shí)確定值僅分配空間，運(yùn)行時(shí)確定值 x x 的描述符保存各屬性的描述符保存各屬性 運(yùn)行時(shí)根據(jù)屬性計(jì)算變量的位置運(yùn)行時(shí)根據(jù)屬性計(jì)算變量的位置Zhou, Erqiang18School of Information and Software Engineering變量的存儲(chǔ)分配3 3）活動(dòng)

18、記錄中有）活動(dòng)記錄中有半動(dòng)態(tài)變量半動(dòng)態(tài)變量 活動(dòng)記錄能否由活動(dòng)記錄能否由“棧?！眮?lái)實(shí)現(xiàn)？來(lái)實(shí)現(xiàn)？ 半動(dòng)態(tài)變量能否支持半動(dòng)態(tài)變量能否支持“棧式分配棧式分配”？ 半動(dòng)態(tài)變量可以半動(dòng)態(tài)變量可以 動(dòng)態(tài)分配在活動(dòng)記錄的動(dòng)態(tài)分配在活動(dòng)記錄的“尾部尾部” 即運(yùn)行棧的即運(yùn)行棧的“棧頂棧頂” 半動(dòng)態(tài)變量的半動(dòng)態(tài)變量的生存期生存期與活動(dòng)記錄相同與活動(dòng)記錄相同 隨函數(shù)的退出而消亡隨函數(shù)的退出而消亡Zhou, Erqiang19School of Information and Software Engineering變量的存儲(chǔ)分配4 4）如果）如果 offset( offset(x x) ) 在編譯、運(yùn)行時(shí)都不能確

19、定下來(lái)在編譯、運(yùn)行時(shí)都不能確定下來(lái) x x 的大小在運(yùn)行時(shí)不固定的大小在運(yùn)行時(shí)不固定 運(yùn)行時(shí)可動(dòng)態(tài)改變，運(yùn)行時(shí)可動(dòng)態(tài)改變，x x 稱為稱為動(dòng)態(tài)變量動(dòng)態(tài)變量 如果將如果將 x x 保存在活動(dòng)記錄中保存在活動(dòng)記錄中 每個(gè)活動(dòng)記錄的長(zhǎng)度不確定每個(gè)活動(dòng)記錄的長(zhǎng)度不確定 x x 的生存期與活動(dòng)記錄不同步的生存期與活動(dòng)記錄不同步 不能使用棧式分配不能使用棧式分配 如何解決？如何解決？Zhou, Erqiang20School of Information and Software Engineering變量的存儲(chǔ)分配4 4）x x 為為動(dòng)態(tài)變量動(dòng)態(tài)變量 使用另外的數(shù)據(jù)結(jié)構(gòu)使用另外的數(shù)據(jù)結(jié)構(gòu)“堆堆”來(lái)存儲(chǔ)來(lái)

20、存儲(chǔ) 需要堆的情況：需要堆的情況： 局部變量的值在單元活動(dòng)后還需保留局部變量的值在單元活動(dòng)后還需保留 調(diào)用單元與被調(diào)用單元調(diào)用單元與被調(diào)用單元 生存期不滿足先進(jìn)后出模式生存期不滿足先進(jìn)后出模式 Zhou, Erqiang21School of Information and Software Engineering進(jìn)程的存儲(chǔ)組織方式進(jìn)程的存儲(chǔ)組織方式 變量的存儲(chǔ)分配Zhou, Erqiang22School of Information and Software Engineering代碼代碼靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)堆堆 棧棧 變量的存儲(chǔ)分配數(shù)據(jù)對(duì)象的存儲(chǔ)安排中的數(shù)據(jù)對(duì)象的存儲(chǔ)安排中的對(duì)齊問(wèn)題對(duì)齊問(wèn)題

21、typedeftypedef struct _a struct _a typedeftypedef struct _b struct _b charchar c1; c1; charchar c1; c1; longlong i1; i1; charchar c2; c2; charchar c2; c2; intint i1; i1; intint i2; i2; intint i2; i2;a;a; b; b;sizeof(a) sizeof(a) 與與 sizeof(b) sizeof(b) 一樣嗎一樣嗎？為什么為什么？Zhou, Erqiang23School of Informati

22、on and Software Engineering變量的存儲(chǔ)分配數(shù)據(jù)對(duì)象的存儲(chǔ)安排中的數(shù)據(jù)對(duì)象的存儲(chǔ)安排中的對(duì)齊問(wèn)題對(duì)齊問(wèn)題Zhou, Erqiang24School of Information and Software Engineeringchar c1; 1long i1; 4char c2; 1int i2; 4char c1; 1long i1; 4int i2; 4n+4nchar c2; 1n+8n+12struct _a32位機(jī)器位機(jī)器：sizeof(struct _a) = 16變量的存儲(chǔ)分配數(shù)據(jù)對(duì)象的存儲(chǔ)安排中的數(shù)據(jù)對(duì)象的存儲(chǔ)安排中的對(duì)齊問(wèn)題對(duì)齊問(wèn)題Zhou, Erq

23、iang25School of Information and Software Engineeringchar c1; 1char c2; 1long i1; 4int i2; 4char c1; 1long i1; 4int i2; 4char c2; 1n+4nn+1n+8struct _b32位機(jī)器位機(jī)器：sizeof(struct _b) = 12存儲(chǔ)分配模式靜態(tài)分配靜態(tài)分配 程序語(yǔ)言僅支持靜態(tài)變量程序語(yǔ)言僅支持靜態(tài)變量棧式分配棧式分配 半靜態(tài)變量、半動(dòng)態(tài)變量半靜態(tài)變量、半動(dòng)態(tài)變量 調(diào)用關(guān)系先進(jìn)后出調(diào)用關(guān)系先進(jìn)后出堆式分配堆式分配 動(dòng)態(tài)變量動(dòng)態(tài)變量Zhou, Erqiang26Sch

24、ool of Information and Software Engineering棧式存儲(chǔ)分配半靜態(tài)變量半靜態(tài)變量 offset(offset(x x) ) 在在編譯編譯時(shí)確定、時(shí)確定、D D 在在運(yùn)行運(yùn)行時(shí)確定時(shí)確定 活動(dòng)記錄活動(dòng)記錄 大小在編譯大小在編譯時(shí)確定、時(shí)確定、位置在運(yùn)行位置在運(yùn)行時(shí)確定時(shí)確定半動(dòng)態(tài)變量半動(dòng)態(tài)變量 D D和和offset(offset(x x) ) 在運(yùn)行確定在運(yùn)行確定 活動(dòng)記錄大小、位置在活動(dòng)記錄大小、位置在激活激活時(shí)確定時(shí)確定Zhou, Erqiang27School of Information and Software Engineering例子：過(guò)程例

25、子：過(guò)程A A調(diào)用過(guò)程調(diào)用過(guò)程P PSchool of Information and Software Engineering28Zhou, Erqiang棧式存儲(chǔ)分配 之半靜態(tài)變量currentfreeA A的活動(dòng)記錄的活動(dòng)記錄返回地址返回地址 IP+X動(dòng)態(tài)連接動(dòng)態(tài)連接currentP P的活動(dòng)記錄的活動(dòng)記錄currentfree哪些指針在返回時(shí)需要恢復(fù)？哪些指針在返回時(shí)需要恢復(fù)？返回地址：指令指針?lè)祷氐刂罚褐噶钪羔業(yè)P？current,free處理方法處理方法(1) (1) 設(shè)置當(dāng)前棧指針設(shè)置當(dāng)前棧指針current 表示當(dāng)前活動(dòng)記錄的開始位置表示當(dāng)前活動(dòng)記錄的開始位置 （活動(dòng)記錄首地址

26、（活動(dòng)記錄首地址D D，長(zhǎng)度為，長(zhǎng)度為L(zhǎng) L）(2) (2) 指針指針free表示棧頂下一個(gè)可用單元表示棧頂下一個(gè)可用單元 free = current + L(3) (3) 局部變量局部變量X X在活動(dòng)記錄中的位移為在活動(dòng)記錄中的位移為 i i 變量的地址變量的地址current+i, , 值為值為Dcurrent+i棧式存儲(chǔ)分配 之半靜態(tài)變量Zhou, Erqiang29School of Information and Software Engineering處理方法處理方法(4) A(4) A調(diào)用調(diào)用B B時(shí)，時(shí)，B B單元被激活單元被激活 在在A A的棧幀（活動(dòng)記錄）之上的棧幀（活動(dòng)

27、記錄）之上 建立建立B B的當(dāng)前實(shí)例的活動(dòng)記錄的當(dāng)前實(shí)例的活動(dòng)記錄 將將currentcurrent和和freefree綁定于綁定于B B的活動(dòng)記錄的活動(dòng)記錄 綁定之前保存綁定之前保存currentcurrent指針的當(dāng)前值指針的當(dāng)前值(5) (5) 從從B B返回時(shí)，釋放其活動(dòng)記錄返回時(shí)，釋放其活動(dòng)記錄 恢復(fù)恢復(fù)currentcurrent和和freefree指針指針 棧式存儲(chǔ)分配 之半靜態(tài)變量Zhou, Erqiang30School of Information and Software Engineering動(dòng)態(tài)連接動(dòng)態(tài)連接動(dòng)態(tài)鏈動(dòng)態(tài)鏈AEFGF例：例：A call E; E call

28、 F; F call G; G call F;.School of Information and Software Engineering31Zhou, Erqiang棧式存儲(chǔ)分配 之半靜態(tài)變量CALL P的翻譯的翻譯 1) 1) D free := ? （保存返回地址）（保存返回地址） 2) 2) Dfree + 1 := current （保存（保存currentcurrent） 3) 3) current := free （建立新的（建立新的currentcurrent） 4) 4) free := free + L （調(diào)整（調(diào)整freefree） 5) 5) ip := P（轉(zhuǎn)移到（

29、轉(zhuǎn)移到P P） 6) ( 6) (函數(shù)返回后需執(zhí)行的指令函數(shù)返回后需執(zhí)行的指令) )School of Information and Software Engineering32Zhou, Erqiang棧式存儲(chǔ)分配 之半靜態(tài)變量ip + 5例子：過(guò)程例子：過(guò)程A A調(diào)用過(guò)程調(diào)用過(guò)程P PSchool of Information and Software Engineering33Zhou, Erqiang棧式存儲(chǔ)分配 之半靜態(tài)變量返回地址返回地址動(dòng)態(tài)連接動(dòng)態(tài)連接currentfreeA A的活動(dòng)記錄的活動(dòng)記錄返回地址返回地址動(dòng)態(tài)連接動(dòng)態(tài)連接P P的活動(dòng)記錄的活動(dòng)記錄currentfree

30、如何返回？如何返回？free = currentcurrent = Dcurrent+1ip = DfreeRETURN語(yǔ)句的翻譯語(yǔ)句的翻譯 1) 1) 恢復(fù)恢復(fù)free free := current 2) 2) 恢復(fù)主調(diào)過(guò)程的恢復(fù)主調(diào)過(guò)程的current current := Dcurrent + 1 3) 3) 返回返回 ip := DfreeSchool of Information and Software Engineering34Zhou, Erqiang棧式存儲(chǔ)分配 之半靜態(tài)變量例子：過(guò)程例子：過(guò)程P P退出，返回過(guò)程退出，返回過(guò)程A AcurrentSchool of Inf

31、ormation and Software Engineering35Zhou, Erqiang棧式存儲(chǔ)分配 之半靜態(tài)變量返回地址返回地址動(dòng)態(tài)連接動(dòng)態(tài)連接currentfreeA A的活動(dòng)記錄的活動(dòng)記錄返回地址返回地址動(dòng)態(tài)連接動(dòng)態(tài)連接P P的活動(dòng)記錄的活動(dòng)記錄freefree = currentcurrent = Dcurrent+1ip = Dfree處理方法處理方法 在活動(dòng)記錄中為變量在活動(dòng)記錄中為變量i i 建立描述符建立描述符 在活動(dòng)記錄的最后（棧頂）分配變量在活動(dòng)記錄的最后（棧頂）分配變量 i i 用用描述中的指針域描述中的指針域指向變量指向變量 i i 的存儲(chǔ)位置的存儲(chǔ)位置 產(chǎn)生相

32、關(guān)指令產(chǎn)生相關(guān)指令 創(chuàng)建變量存儲(chǔ)空間創(chuàng)建變量存儲(chǔ)空間 修改描述符修改描述符School of Information and Software Engineering36Zhou, Erqiang棧式存儲(chǔ)分配 之半動(dòng)態(tài)變量處理方法處理方法School of Information and Software Engineering37Zhou, Erqiang棧式存儲(chǔ)分配 之半動(dòng)態(tài)變量返回地址返回地址動(dòng)態(tài)連接動(dòng)態(tài)連接currentfree編譯時(shí)編譯時(shí)A A的活動(dòng)記錄的活動(dòng)記錄變量變量x x描述符描述符( (地址地址, ,大小等大小等) )運(yùn)行時(shí)運(yùn)行時(shí) 獲取元素個(gè)數(shù)獲取元素個(gè)數(shù) 計(jì)算數(shù)組大小計(jì)算數(shù)

33、組大小其它變量其它變量x x的存儲(chǔ)空間的存儲(chǔ)空間free修改修改free指針指針 free = free + L修改描述符修改描述符變量的作用域變量的作用域 指可訪問(wèn)該變量的程序范圍指可訪問(wèn)該變量的程序范圍 如何確定這個(gè)范圍？如何確定這個(gè)范圍？ 制定作用域規(guī)則制定作用域規(guī)則作用域規(guī)則作用域規(guī)則 靜態(tài)作用域規(guī)則靜態(tài)作用域規(guī)則 動(dòng)態(tài)作用域規(guī)則動(dòng)態(tài)作用域規(guī)則School of Information and Software Engineering38Zhou, Erqiang非局部環(huán)境的引用靜態(tài)作用域規(guī)則靜態(tài)作用域規(guī)則 最近嵌套規(guī)則最近嵌套規(guī)則 引用引用最近的最近的“外層嵌套外層嵌套”中說(shuō)明的變量

34、中說(shuō)明的變量嵌套的層次嵌套的層次 若若A是是B的直接外層的直接外層, ,則則 B的層次的層次 = A的層次的層次 + 1+ 1School of Information and Software Engineering39Zhou, Erqiang非局部環(huán)境的引用School of Information and Software Engineering40Zhou, Erqiang非局部環(huán)境的引用unit A;y: int;unit B;end B;y: int;unit C;end D;end C;.unit D;.end A;end E;z: int;unit F;end G;unit

35、G; x,y: int; .unit E;z:=x+y;end F;.x: int;A(0)B(1)C(2)D(3)E(1)F(2)G(2)嵌套層次圖嵌套層次圖F F或或G G中能否調(diào)用中能否調(diào)用B?B?F F或或G G中能否調(diào)用中能否調(diào)用C?C?如何實(shí)現(xiàn)引用？如何實(shí)現(xiàn)引用？靜態(tài)作用域規(guī)則的引用方法靜態(tài)作用域規(guī)則的引用方法 將嵌套關(guān)系保存到活動(dòng)記錄將嵌套關(guān)系保存到活動(dòng)記錄通過(guò)通過(guò)“靜態(tài)連接靜態(tài)連接”實(shí)現(xiàn)實(shí)現(xiàn)靜態(tài)連接靜態(tài)連接 指向嵌套指向嵌套直接直接外層外層最新最新活動(dòng)記錄的指針活動(dòng)記錄的指針 保存位置：活動(dòng)記錄中保存位置：活動(dòng)記錄中第第3 3個(gè)個(gè)存儲(chǔ)單元存儲(chǔ)單元靜態(tài)鏈靜態(tài)鏈 運(yùn)行時(shí)各活動(dòng)記錄運(yùn)

36、行時(shí)各活動(dòng)記錄由靜態(tài)連接由靜態(tài)連接所構(gòu)成的鏈所構(gòu)成的鏈School of Information and Software Engineering41Zhou, Erqiang非局部環(huán)境的引用例：例：A call E; E call F; F call G; G call F;School of Information and Software Engineering42Zhou, Erqiang非局部環(huán)境的引用AEFGF.A(0)B(1)C(2)D(3)E(1)F(2)G(2)如何計(jì)算非局如何計(jì)算非局部部x x變量地址？變量地址？非局部變量非局部變量x x的地址的求法的地址的求法School

37、 of Information and Software Engineering43Zhou, Erqiang非局部環(huán)境的引用AEFGF.A(0)B(1)C(2)D(3)E(1)F(2)G(2)F F 引用引用 單元單元A A中的變量中的變量x x其在其在A A中的偏移為中的偏移為offsetoffsetcurrent嵌套層次：嵌套層次：2 2Dcurrent+2為靜態(tài)連接為靜態(tài)連接Dcurrent + 2Dcurrent + 2 + offsetcurrent非局部變量非局部變量x x的地址的求法的地址的求法 A是是B的直接外層的直接外層( (第第1個(gè)外層個(gè)外層) ) DA Dcurrent

38、 + 2 A是是B的第的第2個(gè)外層個(gè)外層 DA = DDcurrent + 2 + 2 A是是B的第的第3個(gè)外層個(gè)外層 DA = DDDcurrent + 2 2 2 可定義函數(shù)實(shí)現(xiàn)可定義函數(shù)實(shí)現(xiàn) DA 的獲取的獲取 School of Information and Software Engineering44Zhou, Erqiang非局部環(huán)境的引用嵌套層次：嵌套層次：2 2Dcurrent+2為靜態(tài)連接為靜態(tài)連接Dcurrent + 2Dcurrent + 2 + offsetDA:單元單元A的活動(dòng)記錄首地址的活動(dòng)記錄首地址假設(shè)單元假設(shè)單元p中引用了單元中引用了單元t中的變量中的變量x

39、且且p, t的深度分別為的深度分別為np, nt設(shè)設(shè)d = np nt, , 定義函數(shù)定義函數(shù) f(d) if( d = 0 ) then return current ; else return D f(d-1) + 2 ; f(0) = current; f(1) = Dcurrent+2; f(2) = D f(1)+2 = D Dcurrent+2 +2;School of Information and Software Engineering45Zhou, Erqiang非局部環(huán)境的引用通過(guò)通過(guò)靜態(tài)連接靜態(tài)連接可以引用非局部環(huán)境可以引用非局部環(huán)境 如何如何建立靜態(tài)連接建立靜態(tài)連接呢

40、？呢？什么時(shí)候建立？什么時(shí)候建立？ 保存位置：在活動(dòng)記錄的保存位置：在活動(dòng)記錄的第第3 3個(gè)個(gè)存儲(chǔ)單元存儲(chǔ)單元 在返回地址、動(dòng)態(tài)連接之后保存在返回地址、動(dòng)態(tài)連接之后保存 在在處理程序單元調(diào)用處理程序單元調(diào)用時(shí)建立時(shí)建立怎么建立？怎么建立？ 利用利用當(dāng)前的棧幀當(dāng)前的棧幀 考查嵌套結(jié)構(gòu)下單元調(diào)用關(guān)系考查嵌套結(jié)構(gòu)下單元調(diào)用關(guān)系School of Information and Software Engineering46Zhou, Erqiang非局部環(huán)境的引用嵌套結(jié)構(gòu)下單元嵌套結(jié)構(gòu)下單元 A 調(diào)用單元調(diào)用單元 BSchool of Information and Software Engineer

41、ing47Zhou, Erqiang非局部環(huán)境的引用(3) nA-nB = 1(4) nA-nB 1(1) nA-nB = -1(2) nA-nB = 0BAcall BABcall BBAcall BBcall BA通過(guò)通過(guò)當(dāng)前棧幀當(dāng)前棧幀建立建立B的靜態(tài)連接的靜態(tài)連接current=f(0)Dcurrent + 2 =f(1)f(2)f(d+1)因此，靜態(tài)連接因此，靜態(tài)連接 Dfree+2 的值的值為為 f(d+1)單元調(diào)用語(yǔ)句單元調(diào)用語(yǔ)句 CALL P 的翻譯的翻譯 1) 1) D free := ? （保存返回地址）（保存返回地址） 2) 2) Dfree + 1 := current

42、 （保存（保存currentcurrent） 3) 3) Dfree + 2 := f(d+1) （保存靜態(tài)連接）（保存靜態(tài)連接） 4) 4) current := free （建立新的（建立新的currentcurrent） 5) 5) free := free + L （調(diào)整（調(diào)整freefree） 6) 6) ip := P（轉(zhuǎn)移到（轉(zhuǎn)移到P P） 7) ( 7) (函數(shù)返回后需執(zhí)行的指令函數(shù)返回后需執(zhí)行的指令) )School of Information and Software Engineering48Zhou, Erqiang非局部環(huán)境的引用ip + 6動(dòng)態(tài)作用域規(guī)則動(dòng)態(tài)作用域

43、規(guī)則 一種最近一種最近活動(dòng)規(guī)則活動(dòng)規(guī)則對(duì)非局部變量對(duì)非局部變量 引用的最近的引用的最近的“調(diào)用外層調(diào)用外層”中說(shuō)明的變量中說(shuō)明的變量 生存期嵌套生存期嵌套例：例：AEF的調(diào)用序列的調(diào)用序列 F的直接調(diào)用外層為的直接調(diào)用外層為E E的直接調(diào)用外層為的直接調(diào)用外層為ASchool of Information and Software Engineering49Zhou, Erqiang非局部環(huán)境的引用如何引用非局部變量？如何引用非局部變量？直接使用直接使用動(dòng)態(tài)連接！動(dòng)態(tài)連接！數(shù)據(jù)參數(shù)傳遞數(shù)據(jù)參數(shù)傳遞School of Information and Software Engineering50Z

44、hou, Erqiang參數(shù)傳遞procedure swap (a , b : integer);var temp : integer;begin temp := a; a := b; b := tempend; swap ( i , ai ) i = 3 , a = 7，1，4，5，8數(shù)據(jù)參數(shù)傳遞之?dāng)?shù)據(jù)參數(shù)傳遞之引址調(diào)用引址調(diào)用 將將實(shí)參的地址實(shí)參的地址傳遞給相應(yīng)的形參傳遞給相應(yīng)的形參 在單元中對(duì)形參的引用在單元中對(duì)形參的引用 實(shí)際上是實(shí)際上是對(duì)對(duì)形式單元中形式單元中實(shí)參地址實(shí)參地址的引用的引用School of Information and Software Engineering51Zhou, Erqiang參數(shù)傳遞swap(i,ai); swap(i,ai); 相當(dāng)于執(zhí)行相當(dāng)于執(zhí)行: : a := i a := i的地址的地址; ; b := a3 b := a3的地址的地址; ; temp := a temp := a ; (temp=3); (temp=3) a a := b := b ; (i=4); (i=4) b b := temp; (a3=temp=3) := temp; (a3=temp=3)執(zhí)行結(jié)果執(zhí)行結(jié)果: i=4, a3=3: i=4, a3=3數(shù)據(jù)參數(shù)傳遞之?dāng)?shù)據(jù)參數(shù)傳遞之值調(diào)用值調(diào)用 形參只起形參只起局部變量局部變量作用作用 (1)(1)