【正文】 l。 small。 procedure show。 begin (綠色表示已執(zhí)行部分 ) r := 。 writeln end. dynamic show small small show show show r dynamic r ? show 靜態(tài)區(qū) 使用值的地方 棧區(qū) 暫存值的地方 非局部名字的訪問 program dynamic(input, output)。 begin r := 。 show。 procedure small。 small。 procedure show。 show。 var r: real。 show end。 small。 var r: real。 procedure b (g: function (integer): integer)。 b(f) end. a ret b addm 非局部名字的訪問 program ret (input, output)。 var m: integer。 procedure c。（ 過程作為參數(shù) ） procedure b(function h(… begin writeln(h(2)) end 。 begin c end. 函數(shù) f作為參數(shù)傳遞時(shí)，怎樣在 f被激活時(shí)建立它的訪問鏈 非局部名字的訪問 program param(input, output)。（ 過程作為參數(shù) ） procedure b(function h(n: integer): integer)。 B3 a0 b0 b1 a2, b3 重疊分配存儲(chǔ)單元 全局棧式存儲(chǔ)分配 本節(jié)介紹 ? 介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略 ? 描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲(chǔ)單元 ? 介紹三種分配策略 – 靜態(tài)分配策略 – 棧式分配策略 – 堆式分配策略 全局棧式存儲(chǔ)分配 運(yùn)行時(shí)內(nèi)存的劃分 代 碼 靜 態(tài) 數(shù) 據(jù) 堆 棧 全局棧式存儲(chǔ)分配 靜態(tài)分配 ? 名字在程序被編譯時(shí)綁定到存儲(chǔ)單元 ， 不需要運(yùn)行時(shí)的任何支持 ? 綁定的生存期是程序的整個(gè)運(yùn)行期間 全局棧式存儲(chǔ)分配 靜態(tài)分配給語言帶來限制 ? 遞歸過程不被允許 ? 數(shù)據(jù)對(duì)象的長度和它在內(nèi)存中位置的限制 ，必須是在編譯時(shí)可以知道的 ? 數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立 全局棧式存儲(chǔ)分配 ? 例 C程序的外部變量 、 靜態(tài)局部變量以及程序中出現(xiàn)的常量都可以靜態(tài)分配 ? 聲明在函數(shù)外面 – 外部變量 靜態(tài)分配 – 靜態(tài)外部變量 靜態(tài)分配 ? 聲明在函數(shù)里面 – 靜態(tài)局部變量 也是靜態(tài)分配 – 自動(dòng)變量 不能靜態(tài)分配 全局棧式存儲(chǔ)分配 活動(dòng)樹和運(yùn)行棧 活動(dòng)樹 – 用樹來描繪控制進(jìn)入和離開活動(dòng)的方式 m q(1,9) r p(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) 全局棧式存儲(chǔ)分配 ? 活動(dòng)樹的特點(diǎn) – 每個(gè)結(jié)點(diǎn)代表某過程的一個(gè)活動(dòng) – 根結(jié)點(diǎn)代表主程序的活動(dòng) – 結(jié)點(diǎn) a是結(jié)點(diǎn) b的父結(jié)點(diǎn) ， 當(dāng)且僅當(dāng)控制流從 a的活動(dòng)進(jìn)入 b的活動(dòng) – 結(jié)點(diǎn) a處于結(jié)點(diǎn) b的左邊 ， 當(dāng)且僅當(dāng) a的生存期先于 b的生存期 m q(1,9) r p(1,9) q(1,3) . . . . q(5,9) . . . . 全局棧式存儲(chǔ)分配 ? 當(dāng)前活躍著的過程活動(dòng)可以保存在一個(gè)棧中 – 例 控制棧的內(nèi)容： m, q (1, 9), q (1, 3), q (2, 3) m q(1,9) r p(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) 全局棧式存儲(chǔ)分配 運(yùn)行棧： 把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息 （ 即活動(dòng)記錄 ） 全局棧式存儲(chǔ)分配 運(yùn)行棧： 把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息 （ 即活動(dòng)記錄 ） main 棧 main 函數(shù)調(diào)用關(guān)系樹 全局棧式存儲(chǔ)分配 運(yùn)行棧： 把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息 （ 即活動(dòng)記錄 ） main r 函數(shù)調(diào)用關(guān)系樹 main int i r ( ) 棧 全局棧式存儲(chǔ)分配 運(yùn)行棧： 把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息 （ 即活動(dòng)記錄 ） main q(1,9) r 函數(shù)調(diào)用關(guān)系樹 main int i q (1, 9) int m, n 棧 全局棧式存儲(chǔ)分配 運(yùn)行棧： 把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息 （ 即活動(dòng)記錄 ） main q(1,9) r p(1,9) q(1,3) main int i q (1, 9) int m, n int i q (1, 3) int m, n 棧 函數(shù)調(diào)用關(guān)系樹 全局棧式存儲(chǔ)分配 運(yùn)行棧： 把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息 （ 即活動(dòng)記錄 ） main q(1,9) r p(1,9) q(1,3) q(1,0) p(1,3) main int i q (1, 9) int m, n int i q (1, 3) int m, n int i q (1, 0) int m, n 棧 函數(shù)調(diào)用關(guān)系樹 全局棧式存儲(chǔ)分配 調(diào)用序列 ? 過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧 ， 保存或恢復(fù)機(jī)器狀態(tài)等 ? 過程調(diào)用序列 過程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄 ， 把信息填入它的域中 ， 使被調(diào)用過程可以開始執(zhí)行的代碼 ? 過程返回序列 被調(diào)用過程返回時(shí)執(zhí)行的恢復(fù)機(jī)器狀態(tài) ， 釋放被調(diào)用過程活動(dòng)記錄 ， 使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼 ? 調(diào)用序列和返回序列 常常都分成兩部分 ， 分處于調(diào)用過程和被調(diào)用過程中 全局棧式存儲(chǔ)分配 ? 即使是同一種語言 ， 過程調(diào)用序列 、 返回序列和活動(dòng)記錄中各域的排放次序 ， 也會(huì)因?qū)崿F(xiàn)而異 ? 設(shè)計(jì)這些序列和活動(dòng)記錄 的一些原則 – 以活動(dòng)記錄中間的某個(gè) 位置作為基地址 – 長度能較早確定的域放在 活動(dòng)記錄的中間 臨 時(shí) 數(shù) 據(jù) 參 數(shù) 局 部 數(shù) 據(jù) 機(jī) 器 狀 態(tài) 訪 問 鏈 控 制 鏈 返 回 值 全局棧式存儲(chǔ)分配 ? 即使是同一種語言 ， 過程調(diào)用序列 、 返回序列和活動(dòng)記錄中各域的排放次序 ， 也會(huì)因?qū)崿F(xiàn)而異 ? 設(shè)計(jì)這些序列和活動(dòng)記錄 的一些原則 – 一般把臨時(shí)數(shù)據(jù)域放在 局部數(shù)據(jù)域的后面 – 把參數(shù)域和可能有的返回 值域放在緊靠調(diào)用者活動(dòng) 記錄的地方 臨 時(shí) 數(shù) 據(jù) 參 數(shù) 局 部 數(shù) 據(jù) 機(jī) 器 狀 態(tài) 訪 問 鏈 控 制 鏈 返 回 值 全局棧式存儲(chǔ)分配 ? 即使是同一種語言 ， 過程調(diào)用序列 、 返回序列和活動(dòng)記錄中各域的排放次序 ， 也會(huì)因?qū)崿F(xiàn)而異 ? 設(shè)計(jì)這些序列和活動(dòng)記錄 的一些原則 – 用同樣的代碼來執(zhí)行各個(gè) 活動(dòng)的保存和恢復(fù) 臨 時(shí) 數(shù) 據(jù) 參 數(shù) 局 部 數(shù) 據(jù) 機(jī) 器 狀 態(tài) 訪 問 鏈 控 制 鏈 返 回 值 全局棧式存儲(chǔ)分配 過程 p調(diào)用過程 q的調(diào)用序列 返回值和參數(shù) top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù) 控制鏈 和保存的機(jī)器狀態(tài) ? ? ? 全局棧式存儲(chǔ)分配 過程 p調(diào)用過程 q的調(diào)用序列 (1) p計(jì)算實(shí)參，依次放入棧頂，并在棧頂留出放返回值的空間。 { /? begin of B1 ?/ int b = 1。 }b。 0 char c1。 1 char c2。 double f。 char c1。 }b。 16 double f。 1 char c2。 { /? begin of B1 ?/ int b = 1。 }/? end of B3 ?/ }/? end of B1 ?/ }/? end of B0 ?/ 聲 明 作 用 域 int a = 0。 | int j = 20。 var m: integer。 var m: integer。 function f(n: integer)… begin f := m+n end {f}。 begin m := 0。 begin m:= 0。 var m: integer。 b(f) end. a ret b addm 執(zhí)行 addm時(shí)， a的活動(dòng)記錄已不存在，取不到 m的值 非局部名字的訪問 ? C語言的函數(shù)聲明不能嵌套 ， 函數(shù)不論在什么情況下激活 ， 要訪問的數(shù)據(jù)分成兩種情況 – 非靜態(tài)局部變量 （ 包括形式參數(shù) ） ， 它們分配在活動(dòng)記錄棧頂?shù)哪莻€(gè)活動(dòng)記錄中 – 外部變量 （ 包括定義在其它源文件之中的外部變量 ） 和靜態(tài)的局部變量 ， 它們都分配在靜態(tài)數(shù)據(jù)區(qū) – 因此 C語言允許函數(shù) （ 的指針 ） 作為返回值 非局部名字的訪問 動(dòng)態(tài)作用域 ? 被調(diào)用過程的非局部名字 a和它在調(diào)用過程中引用的是同樣的存儲(chǔ)單元 – 基于 運(yùn)行時(shí)的調(diào)用關(guān)系 – 而不 是基于靜態(tài)作用域來確定 ? 新的綁定僅為被調(diào)用過程的局部名字建立 ，這些名字在被調(diào)用過程的活動(dòng)記錄中占用存儲(chǔ)單元 – 這一點(diǎn) 與靜態(tài)作用域沒有區(qū)別 非局部名字的訪問 program dynamic(input, output)。 begin r := 。 procedure show。 small。 procedure small。 show。 var r: real。 small。 show end。 var r: real。 show。 begin write(r: 5: 3) end。 writeln。 var r: real。 small。 show end。 var temp: integer。 var temp: integer。 temp := x。 … … … … } struct student st[10000]。 func( ) { static long cc = 30。 func( ) { static long cc = 30。 func( ) { static long cc = 30。 j= i 1。 pushl %ebp 老的基地址指針壓棧 { movl %esp,%ebp修改 基地址指針 long j。 decl %edx i – 1 } movl %edx,4(%ebp) i – 1 ? j movl 4(%ebp),%eax pushl %eax 把實(shí)參 j的值壓棧 call func 函數(shù)調(diào)用 addl $4,%esp 恢復(fù)棧頂指針 L1: leave 即 mov ebp, esp。 subl $4,%esp 為 j分配空間 j= i 1。 pop ebp ret 即 pop eip(下條指令地址 ） . . . . . . ebp