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

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

2、結(jié)構(gòu)存放所需信息的數(shù)據(jù)結(jié)構(gòu) 活動記錄活動記錄Zhou, Erqiang3School of Information and Software Engineering活動記錄關(guān)于活動記錄關(guān)于活動記錄 討論討論一個(gè)活動記錄一個(gè)活動記錄中的數(shù)據(jù)安排中的數(shù)據(jù)安排 程序執(zhí)行過程中程序執(zhí)行過程中 所有活動記錄所有活動記錄的組織方式的組織方式 Zhou, Erqiang4School of Information and Software Engineering活動記錄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ú)立的對應(yīng)一個(gè)函數(shù)的每次執(zhí)行都獨(dú)立的對應(yīng)一個(gè)棧幀棧幀 當(dāng)前被執(zhí)行函數(shù)對應(yīng)的當(dāng)前被執(zhí)行函數(shù)對應(yīng)的棧幀棧幀在在棧的頂部棧的頂部 通過通過基址指針基址指針 與與 變量的偏移變量的偏移訪問臨時(shí)變量訪問臨時(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活動記錄函數(shù)被多次調(diào)用函數(shù)被多次調(diào)用 對應(yīng)多個(gè)活動記錄對應(yīng)多個(gè)活動記錄 程序運(yùn)行對應(yīng)一個(gè)程序運(yùn)行對應(yīng)一個(gè)活動記錄樹活動記錄樹 輸入不同，活動記錄樹輸入不同，活動記錄樹可能可能有所不同有所不同 活動記錄之間活動記錄之間“相互嵌套相互嵌套” 可用可用“棧?！眮砀櫢骰顒佑涗泚砀櫢骰顒佑涗?當(dāng)函數(shù)返回后相應(yīng)的記錄當(dāng)函數(shù)返回后相應(yīng)的記錄不再不再被引用被引用Zhou, Erqiang7School of Information a

7、nd Software Engineering活動記錄“當(dāng)函數(shù)返回后相應(yīng)的記錄當(dāng)函數(shù)返回后相應(yīng)的記錄不再被引用不再被引用”有沒有反例？有沒有反例？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)函數(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)函數(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ū)別？兩種鏈接的區(qū)別？活動記錄活動記錄的內(nèi)容活動記錄的內(nèi)容 返回地址返回地址

11、 控制鏈（動態(tài)鏈接）控制鏈（動態(tài)鏈接） 指向主調(diào)程序的活動記錄指向主調(diào)程序的活動記錄 存取鏈（靜態(tài)鏈接）存取鏈（靜態(tài)鏈接） 指向指向非局部變量非局部變量所在的活動記錄所在的活動記錄Zhou, Erqiang11School of Information and Software Engineering活動記錄活動記錄的內(nèi)容活動記錄的內(nèi)容 CPU CPU 現(xiàn)場現(xiàn)場 實(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ū)別？編譯器不同而有所不同編譯器不同而有所不同變量的存儲分配局部變量局部變量 存儲空間存儲空間大小大小可根據(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變量的存儲分配局部數(shù)據(jù)的地址局部數(shù)據(jù)的地址 D D表示

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

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

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

16、來在編譯時(shí)不能確定下來 但運(yùn)行能確定但運(yùn)行能確定 x x 稱為稱為半動態(tài)變量半動態(tài)變量 支持語言：支持語言：C99 C99 動態(tài)數(shù)組動態(tài)數(shù)組Zhou, Erqiang17School of Information and Software Engineering活動記錄活動記錄大小位置大小位置在編譯時(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; 活動記錄活動記錄保存什么？保存什么？變量的存儲分配3 3）x x 為為半動態(tài)變量半動態(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變量的存儲分配3 3）活動

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

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

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

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變量的存儲分配數(shù)據(jù)對象的存儲安排中的數(shù)據(jù)對象的存儲安排中的對齊問題對齊問題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變量的存儲分配數(shù)據(jù)對象的存儲安排中的數(shù)據(jù)對象的存儲安排中的對齊問題對齊問題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存儲分配模式靜態(tài)分配靜態(tài)分配 程序語言僅支持靜態(tài)變量程序語言僅支持靜態(tài)變量棧式分配棧式分配 半靜態(tài)變量、半動態(tài)變量半靜態(tài)變量、半動態(tài)變量 調(diào)用關(guān)系先進(jìn)后出調(diào)用關(guān)系先進(jìn)后出堆式分配堆式分配 動態(tài)變量動態(tài)變量Zhou, Erqiang26Sch

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

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

26、（活動記錄首地址D D，長度為，長度為L L）(2) (2) 指針指針free表示棧頂下一個(gè)可用單元表示棧頂下一個(gè)可用單元 free = current + L(3) (3) 局部變量局部變量X X在活動記錄中的位移為在活動記錄中的位移為 i i 變量的地址變量的地址current+i, , 值為值為Dcurrent+i棧式存儲分配 之半靜態(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的棧幀（活動記錄）之上的棧幀（活動

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

28、 F; F call G; G call F;.School of Information and Software Engineering31Zhou, Erqiang棧式存儲分配 之半靜態(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棧式存儲分配 之半靜態(tài)變量ip + 5例子：過程例子：過程A A調(diào)用過程調(diào)用過程P PSchool of Information and Software Engineering33Zhou, Erqiang棧式存儲分配 之半靜態(tài)變量返回地址返回地址動態(tài)連接動態(tài)連接currentfreeA A的活動記錄的活動記錄返回地址返回地址動態(tài)連接動態(tài)連接P P的活動記錄的活動記錄currentfree

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

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

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

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

34、中說明的變量嵌套的層次嵌套的層次 若若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)系保存到活動記錄將嵌套關(guān)系保存到活動記錄通過通過“靜態(tài)連接靜態(tài)連接”實(shí)現(xiàn)實(shí)現(xiàn)靜態(tài)連接靜態(tài)連接 指向嵌套指向嵌套直接直接外層外層最新最新活動記錄的指針活動記錄的指針 保存位置：活動記錄中保存位置：活動記錄中第第3 3個(gè)個(gè)存儲單元存儲單元靜態(tài)鏈靜態(tài)鏈 運(yùn)行時(shí)各活動記錄運(yùn)

36、行時(shí)各活動記錄由靜態(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的活動記錄首地址的活動記錄首地址假設(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)境的引用通過通過靜態(tài)連接靜態(tài)連接可以引用非局部環(huán)境可以引用非局部環(huán)境 如何如何建立靜態(tài)連接建立靜態(tài)連接呢

40、？呢？什么時(shí)候建立？什么時(shí)候建立？ 保存位置：在活動記錄的保存位置：在活動記錄的第第3 3個(gè)個(gè)存儲單元存儲單元 在返回地址、動態(tài)連接之后保存在返回地址、動態(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通過通過當(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)用語句單元調(diào)用語句 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動態(tài)作用域規(guī)則動態(tài)作用域

43、規(guī)則 一種最近一種最近活動規(guī)則活動規(guī)則對非局部變量對非局部變量 引用的最近的引用的最近的“調(diào)用外層調(diào)用外層”中說明的變量中說明的變量 生存期嵌套生存期嵌套例：例：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)境的引用如何引用非局部變量？如何引用非局部變量？直接使用直接使用動態(tài)連接！動態(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)的形參 在單元中對形參的引用在單元中對形參的引用 實(shí)際上是實(shí)際上是對對形式單元中形式單元中實(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)