【正文】 c end. 從 b的訪問鏈難以建立 f的訪問鏈 訪 問 鏈 訪 問 鏈 param c m b f 非局部名字的訪問 program param(input, output)。 b(f) end {c}。 } | } 非局部名字的訪問 本節(jié)介紹 ? 無過程嵌套的靜態(tài)作用域 （ C語言 ） ? 有過程嵌套的靜態(tài)作用域 （ Pascal語言 ） ? 動態(tài)作用域 （ Lisp語言 ） 非局部名字的訪問 無過程嵌套的靜態(tài)作用域 ? 過程體中的非局部引用可以直接使用靜態(tài)確定的地址 （ 非局部數(shù)據(jù)此時就是全局數(shù)據(jù) ） ? 局部變量在棧頂?shù)幕顒佑涗浿?， 可以通過base_sp指針來訪問 ? 無須深入棧中取數(shù)據(jù) ， 無須訪問鏈 ? 過程可以作為參數(shù)來傳遞 ， 也可以作為結(jié)果來返回 非局部名字的訪問 有過程嵌套的靜態(tài)作用域 sort readarray exchange quicksort partition 非局部名字的訪問 有過程嵌套的靜態(tài)作用域 ? 過程 嵌套深度 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 ? 變量的嵌套深度：它的聲明所在過程的嵌套 深度作為該名字的嵌套深度 ? 訪問鏈 – 用來尋找非局部 名字的存儲單元 s a, x q (1, 9) k, v 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 p (1, 3) i, j 訪問鏈 e (1, 3) 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 p (1, 3) i, j 訪問鏈 非局部名字的訪問 非局部名字的訪問 ? 訪問非局部名字的存儲單元 假定過程 p的嵌套深度為 np， 它引用嵌套深度為 na 的變量 a， na ? np， 如何訪問 a的存儲單元 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 非局部名字的訪問 ? 訪問非局部名字的存儲單元 假定過程 p的嵌套深度為 np， 它引用嵌套深度為 na 的變量 a， na ? np， 如何訪問 a的存儲單元 – 從棧頂?shù)幕顒佑涗涢_始 ， 追蹤訪問鏈 np ? na次 – 到達 a的聲明所在過程的活動記錄 – 訪問鏈的追蹤用間接操作就可完成 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 ? 訪問非局部名字的存儲單元 sort readarray exchange quicksort partition s a, x q (1, 9) k, v 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 p (1, 3) i, j 訪問鏈 e (1, 3) 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 p (1, 3) i, j 訪問鏈 非局部名字的訪問 非局部名字的訪問 ? 過程 p對變量 a訪問時 ， a的地址由下面的二元組表示： （ np ? na， a在活動記錄中的偏移 ） 非局部名字的訪問 ? 建立訪問鏈 – 假定嵌套深度為 np的過程 p調(diào)用嵌套深度為 nx的過程 x (1) np nx的情況 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 這時 x肯定就聲明在 p中 非局部名字的訪問 ? 建立訪問鏈 – 假定嵌套深度為 np的過程 p調(diào)用嵌套深度為 nx的過程 x (1) np nx的情況 – 被調(diào)用過程的訪問鏈必須指向調(diào)用過程的活動記錄的訪問鏈 ? 訪問非局部名字的存儲單元 sort readarray exchange quicksort partition s a, x q (1, 9) k, v 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 p (1, 3) i, j 訪問鏈 e (1, 3) 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 p (1, 3) i, j 訪問鏈 非局部名字的訪問 非局部名字的訪問 ? 建立訪問鏈 – 假定嵌套深度為 np的過程 p調(diào)用嵌套深度為 nx的過程 x (2) np ? nx的情況 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 這時 p和 x的嵌套深度分別為 1， 2， … ，nx? 1的外圍過程肯定相同 非局部名字的訪問 ? 建立訪問鏈 – 假定嵌套深度為 np的過程 p調(diào)用嵌套深度為 nx的過程 x (2) np ? nx的情況 – 追蹤訪問鏈 np ? nx + 1次 ， 到達了靜態(tài)包圍 x和 p的且離它們最近的那個過程的最新活動記錄 – 所到達的活動記錄就是 x的活動記錄中的訪問鏈應(yīng)該指向的那個活動記錄 ? 訪問非局部名字的存儲單元 sort readarray exchange quicksort partition s a, x q (1, 9) k, v 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 p (1, 3) i, j 訪問鏈 e (1, 3) 訪問鏈 s a, x q (1, 3) k, v 訪問鏈 q (1, 9) k, v 訪問鏈 p (1, 3) i, j 訪問鏈 非局部名字的訪問 非局部名字的訪問 program param(input, output)。 B1? B3 int a = 2。 } /? end of B3 ?/ } /? end of B1 ?/ } /? end of B0 ?/ 局部存儲分配 main() / ? 例 ?/ { /? begin of B0 ?/ int a = 0。 12 double f。 對齊： char : 1, long : 4, double : 8 局部存儲分配 ? 例 在 X86/Linux機器的結(jié)果和 SPARC/Solaris工作站不一樣 ， 是 20和 16。 0 long i。 char c2。 char c2。 0 char c1。 }b。 4 double f。 } /? end of B2 ?/ { /? begin of B3 ?/ int b = 3。 B0 ? B1 int b = 1。 | return j。 begin m := 0。 b(f) end {c}。 begin c end. f作為參數(shù)傳遞時，它的起始地址連同它的訪問鏈一起傳遞 訪 問 鏈 訪 問 鏈 param c m b f, 非局部名字的訪問 program param(input, output)。（ 過程作為返回值 ） var f: function (integer): integer。 begin writeln (g(2)) end。 begin m:= 0。 begin write(r: 5: 3) end。 writeln。 var r: real。 small。 show end。 n的先前值保存在 p的 活動記錄 中 ， 當(dāng) p的活動結(jié)束時再恢復(fù) 非局部名字的訪問 program dynamic(input, output)。 begin (綠色表示已執(zhí)行部分 ) r := 。 procedure show。 small。 procedure small。 show。 begin r := 。 writeln end. dynamic show small small show show show r dynamic r ? small r 靜態(tài)區(qū) 使用值的地方 棧區(qū) 暫存值的地方 非局部名字的訪問 program dynamic(input, output)。 begin (綠色表示已執(zhí)行部分 ) r := 。 procedure show。 small。 y := temp end 參 數(shù) 傳 遞 換名調(diào)用 從概念上說 ， 每次調(diào)用時 ， 用實參表達式對 形參進行正文替換 ， 然后再執(zhí)行 procedure swap(var x, y: integer)。 i := a[i]。 a[i] := temp y := temp 交換兩個數(shù)據(jù)的程序 end 并非總是正確 堆 管 理 堆式分配 ? 堆用來存放生存期不確定的數(shù)據(jù) – C++和 Java允許程序員用 new創(chuàng)建對象 ， 它們的生存期沒有被約束在創(chuàng)建它們的過程活動的生成期之內(nèi) – 實現(xiàn)內(nèi)存回收是內(nèi)存管理器的責(zé)任 ? 堆空間的回收有兩種不同方式 – 程序顯式釋放空間： free（ C） 或 delete（ C++） – 垃圾收集器自動收集 （ Java） 。 short bb = 20。 short bb = 20。 short bb = 20。 short bb = 20。 pushl %ebp 老的基地址指針壓棧 { movl %esp,%ebp修改 基地址指針 long 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 恢復(fù)棧頂指針 L1: leave 即 mov ebp, esp。 subl $4,%esp 為 j分配空間 j= i 1。 pop ebp ret 即 pop eip(下條指令地址 ） . . . . . . ebp esp 參數(shù) i 返址 控制鏈 例 題 2 func(i) func: long i。 movl 8(%ebp),%edx 取 i到 寄存器 fun