【正文】 全局棧式存儲分配 過程 p調用過程 q的調用序列 (1) p計算實參，依次放入棧頂，并在棧頂留出放返回值的空間。 top_sp的值在此過程中被改變 返回值和參數 top_sp base_sp 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? 返回值和參數 top_sp 全局棧式存儲分配 過程 p調用過程 q的調用序列 (2) p把返回地址和當前 base_sp的值存入 q的活動記錄中，建立 q的訪問鏈，增加 base_sp的值 返回值和參數 top_sp base_sp 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? 返回值和參數 控制鏈和返回地址 base_sp top_sp 全局棧式存儲分配 過程 p調用過程 q的調用序列 (3) q保存寄存器的值和其它機器狀態(tài)信息 返回值和參數 top_sp base_sp 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? 返回值和參數 控制鏈 和保存的機器狀態(tài) 全局棧式存儲分配 過程 p調用過程 q的調用序列 (4) q根據局部數據域和臨時數據域的大小增加 top_sp的值，初始化它的局部數據，并開始執(zhí)行過程體 臨時數據局部數據 返回值和參數 返回值和參數 ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? 全局棧式存儲分配 調用者 p和被調用者 q之間的任務劃分 被調用者 q的責任 調用者 p的責任 調用者 p的 活動記錄 被調用者 q的活動記錄 臨時數據局部數據 返回值和參數 返回值和參數 ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 棧 增 長 方 向 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? 全局棧式存儲分配 過程 p調用過程 q的返回序列 臨時數據局部數據 返回值和參數 返回值和參數 ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 棧 增 長 方 向 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? 全局棧式存儲分配 過程 p調用過程 q的返回序列 臨時數據局部數據 返回值 和參數 返回值和參數 ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 棧 增 長 方 向 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? (1) q把返回值置入鄰近 p的活動記錄的地方 參數個數可變場合難以確定存放返回值的位置，因此通常用寄存器傳遞返回值 全局棧式存儲分配 過程 p調用過程 q的返回序列 (2) q對應調用序列的步驟 (4)，減小top_sp的值 返回值和參數 top_sp base_sp 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? 返回值和參數 控制鏈 和保存的機器狀態(tài) 全局棧式存儲分配 過程 p調用過程 q的返回序列 (3) q恢復寄存器 (包括 base_sp)和機器狀態(tài)，返回 p 返回值和參數 top_sp base_sp 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? 返回值和參數 全局棧式存儲分配 過程 p調用過程 q的返回序列 返回值和參數 top_sp base_sp 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? (4) p根據參數個數與類型和返回值類型調整 top_sp， 然后取出返回值 全局棧式存儲分配 過程的參數個數可變的情況 臨時數據局部數據 參 數 參 數 ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 棧 增 長 方 向 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? (1) 函數返回值改成用寄存器傳遞 全局棧式存儲分配 過程的參數個數可變的情況 臨時數據局部數據 參數 1, …, 參數 n 參數 1, …, 參數 m ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 棧 增 長 方 向 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? (2) 編譯器產生將實參表達式逆序計算并將結果進棧的代碼 自上而下依次是參數 1, …, 參數n 全局棧式存儲分配 過程的參數個數可變的情況 臨時數據局部數據 參數 1, …, 參數 n 參數 1, …, 參數 m ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 棧 增 長 方 向 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? (3) 被調用函數能準確地知道第一個參數的位置 全局棧式存儲分配 過程的參數個數可變的情況 臨時數據局部數據 參數 1, …, 參數 n 參數 1, …, 參數 m ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 棧 增 長 方 向 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? (4) 被調用函數根據第一個參數到棧中取第二、第三個參數等等 全局棧式存儲分配 過程的參數個數可變的情況 臨時數據局部數據 參數 1, …, 參數 n 參數 1, …, 參數 m ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 棧 增 長 方 向 臨時數據局部數據 控制鏈 和保存的機器狀態(tài) ? ? ? C語言的 printf函 數就是按此方式， 用 C語言編寫的 下面語句的輸出？ printf(“%d, %d, %d\n”)。 全局棧式存儲分配 棧上可變長數據 活動記錄的長度在編譯時不能確定的情況 ? 例：局部數組的大小要等到過程激活時才能確定 備注： Java語言的實現是將它們分配在堆上 全局棧式存儲分配 訪問動態(tài)分配的數組 控制鏈 數組 A的指針 數組 B的指針 top_sp base_sp . . . . . . . . . 棧 (1) 編譯時，在活動記錄中為這樣的數組分配存放數組指針的單元 全局棧式存儲分配 訪問動態(tài)分配的數組 (2) 運行時，這些指針指向分配在棧頂的數組存儲空間 控制鏈 數組 A的指針 數組 B的指針 top_sp base_sp . . . . . . . . . 棧 數組 A 數組 B 全局棧式存儲分配 訪問動態(tài)分配的數組 (3) 運行時，對數組 A和 B的訪問都要通過相應指針來間接訪問 控制鏈 數組 A的指針 數組 B的指針 top_sp base_sp . . . . . . . . . 棧 數組 A 數組 B 全局棧式存儲分配 訪問動態(tài)分配的數組 q的數組 q的活動記錄 p的數組 p的活動記錄 控制鏈 top_sp base_sp 數組 A的指針 數組 B的指針 數組 A 數組 B 控制鏈 . . . . . . . . . 棧 全局棧式存儲分配 懸空引用 懸空引用： 引用某個已被釋放的存儲單元 全局棧式存儲分配 懸空引用 懸空引用： 引用某個已被釋放的存儲單元 例： main中引用 p指向的對象 main( ) { | int ? dangle ( ) { int ?q。 | int j = 20。 q = dangle ( )。 | return j。 } | } 非局部名字的訪問 本節(jié)介紹 ? 無過程嵌套的靜態(tài)作用域 （ C語言 ） ? 有過程嵌套的靜態(tài)作用域 （ Pascal語言 ） ? 動態(tài)作用域 （ Lisp語言 ） 非局部名字的訪問 無過程嵌套的靜態(tài)作用域 ? 過程體中的非局部引用可以直接使用靜態(tài)確定的地址 （ 非局部數據此時就是全局數據 ） ? 局部變量在棧頂的活動記錄中 ， 可以通過base_sp指針來訪問 ? 無須深入棧中取數據 ， 無須訪問鏈 ? 過程可以作為參數來傳遞 ， 也可以作為結果來返回 非局部名字的訪問 有過程嵌套的靜態(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的存儲單元 – 從棧頂的活動記錄開始 ， 追蹤訪問鏈 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 訪問鏈 非局部名字的訪問 非局部名字的訪問