【正文】 (1) np nx的情況 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 這時 x肯定就聲明在 p中 非局部名字的訪問 ? 建立訪問鏈 – 假定嵌套深度為 np的過程 p調用嵌套深度為 nx的過程 x (1) np nx的情況 – 被調用過程的訪問鏈必須指向調用過程的活動記錄的訪問鏈 ? 訪問非局部名字的存儲單元 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調用嵌套深度為 nx的過程 x (2) np ? nx的情況 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 這時 p和 x的嵌套深度分別為 1， 2， … ，nx? 1的外圍過程肯定相同 非局部名字的訪問 ? 建立訪問鏈 – 假定嵌套深度為 np的過程 p調用嵌套深度為 nx的過程 x (2) np ? nx的情況 – 追蹤訪問鏈 np ? nx + 1次 ， 到達了靜態(tài)包圍 x和 p的且離它們最近的那個過程的最新活動記錄 – 所到達的活動記錄就是 x的活動記錄中的訪問鏈應該指向的那個活動記錄 ? 訪問非局部名字的存儲單元 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)。 全局棧式存儲分配 棧上可變長數(shù)據(jù) 活動記錄的長度在編譯時不能確定的情況 ? 例：局部數(shù)組的大小要等到過程激活時才能確定 備注： Java語言的實現(xiàn)是將它們分配在堆上 全局棧式存儲分配 訪問動態(tài)分配的數(shù)組 控制鏈 數(shù)組 A的指針 數(shù)組 B的指針 top_sp base_sp . . . . . . . . . 棧 (1) 編譯時，在活動記錄中為這樣的數(shù)組分配存放數(shù)組指針的單元 全局棧式存儲分配 訪問動態(tài)分配的數(shù)組 (2) 運行時，這些指針指向分配在棧頂?shù)臄?shù)組存儲空間 控制鏈 數(shù)組 A的指針 數(shù)組 B的指針 top_sp base_sp . . . . . . . . . 棧 數(shù)組 A 數(shù)組 B 全局棧式存儲分配 訪問動態(tài)分配的數(shù)組 (3) 運行時，對數(shù)組 A和 B的訪問都要通過相應指針來間接訪問 控制鏈 數(shù)組 A的指針 數(shù)組 B的指針 top_sp base_sp . . . . . . . . . 棧 數(shù)組 A 數(shù)組 B 全局棧式存儲分配 訪問動態(tài)分配的數(shù)組 q的數(shù)組 q的活動記錄 p的數(shù)組 p的活動記錄 控制鏈 top_sp base_sp 數(shù)組 A的指針 數(shù)組 B的指針 數(shù)組 A 數(shù)組 B 控制鏈 . . . . . . . . . 棧 全局棧式存儲分配 懸空引用 懸空引用： 引用某個已被釋放的存儲單元 全局棧式存儲分配 懸空引用 懸空引用： 引用某個已被釋放的存儲單元 例： main中引用 p指向的對象 main( ) { | int ? dangle ( ) { int ?q。 B1? B3 int a = 2。 }/? end of B2 ?/ {/? begin of B3 ?/ int b = 3。 } /? end of B3 ?/ } /? end of B1 ?/ } /? end of B0 ?/ 局部存儲分配 main() / ? 例 ?/ { /? begin of B0 ?/ int a = 0。 int b = 0。 12 double f。 4 char c2。 對齊： char : 1, long : 4, double : 8 局部存儲分配 ? 例 在 X86/Linux機器的結果和 SPARC/Solaris工作站不一樣 ， 是 20和 16。 4 double f。 0 long i。 }a。 char c2。編譯原理和技術 中國科學技術大學 計算機科學與技術學院 陳意云 第六章 運行時存儲空間的組織和管理 術語 – 過程的 活動 過程的一次執(zhí)行稱為過程的一次活動 – 活動記錄 過程的活動需要可執(zhí)行代碼和存放所需信息的存儲空間 ,后者稱為活動記錄 本章內容 ? 討論一個活動記錄中的數(shù)據(jù)布局 ? 程序執(zhí)行過程中，所有活動記錄的組織方式 第六章 運行時存儲空間的組織和管理 ? 影響存儲分配策略的語言特征 – 過程能否遞歸 – 當控制從過程的活動返回時 ， 局部變量的值是否要保留 – 過程能否訪問非局部變量 – 過程調用的參數(shù)傳遞方式 – 過程能否作為參數(shù)被傳遞 – 過程能否作為結果值傳遞 – 存儲塊能否在程序控制下動態(tài)地分配 – 存儲塊是否必須顯式地釋放 局部存儲分配 過程 語言概念： 過程定義、 過程 調用、形式參數(shù)、實在參數(shù)、 活動的 生存期 局部存儲分配 名字的作用域和綁定 名字的作用域 ? 一個聲明起作用的程序部分稱為該聲明的 作用域 ? 即使一個名字在程序中只聲明一次，該名字在程序運行時也可能表示不同的數(shù)據(jù)對象 局部存儲分配 環(huán)境和狀態(tài) ? 環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值（即 名字到值有兩步映射 ） ? 賦值改變狀態(tài)，但不改變環(huán)境 ? 過程調用改變環(huán)境 ? 如果環(huán)境將名字 x映射到存儲單元 s， 則說 x被綁定 到 s 名字 存儲單元 狀態(tài) 值 環(huán)境 局部存儲分配 靜態(tài)概念和動態(tài)概念的對應 靜 態(tài) 概 念 動 態(tài) 對 應 過程的定義 過程的活動 局部存儲分配 靜態(tài)概念和動態(tài)概念的對應 靜 態(tài) 概 念 動 態(tài) 對 應 過程的定義 過程的活動 名字的聲明 名字的綁定 局部存儲分配 靜態(tài)概念和動態(tài)概念的對應 靜 態(tài) 概 念 動 態(tài) 對 應 過程的定義 過程的活動 名字的聲明 名字的綁定 聲明的作用域 綁定的生存期 局部存儲分配 活動記錄 活動記錄的常見布局 返 回 值 臨 時 數(shù) 據(jù) 參 數(shù) 控 制 鏈 訪 問 鏈 機 器 狀 態(tài) 局 部 數(shù) 據(jù) 局部存儲分配 局部數(shù)據(jù)的布局 ? 字節(jié)是可編址內存的最小單位 ? 變量所需的存儲空間可以根據(jù)其類型而靜態(tài)確定 ? 一個過程所聲明的局部變量 ， 按這些變量聲明時出現(xiàn)的次序 ， 在局部數(shù)據(jù)域中依次分配空間 ? 局部數(shù)據(jù)的地址可以用相對于活動記錄中某個位置的地址來表示 ? 數(shù)據(jù)對象的存儲布局還有一個對齊問題 局部存儲分配 ? 例 在 SPARC/Solaris工作站上下面兩個結構體的 size分別是 24和 16， 為什么不一樣 ？ typedef struct _a{ typedef struct _b{ char c1。 char c2。 double f。 0 char c1。 8 long i。 }b。 0 long i。 4 double f。 對齊： char : 1, long : 4, double : 4 局部存儲分配 程序塊 ? 本身含有局部變量聲明的語句 ? 可以嵌套 ? 最接近的嵌套 作用域規(guī)則 ? 并列程序塊不會同時活躍 ? 并列程序塊的變量可以重疊分配 局部存儲分配 main() / ? 例 ?/ { /? begin of B0 ?/ int a = 0。 } /? end of B2 ?/ { /? begin of B3 ?/ int b = 3。 {/? begin of B2 ?/ int a = 2。 B0 ? B1 int b = 1。 top_sp的值在此過程中被改變 返回值和參數(shù) top_sp base_sp 臨時數(shù)據(jù)局部數(shù)據(jù) 控制鏈 和保存的機器狀態(tài) ? ? ? 返回值和參數(shù) top_sp 全局棧式存儲分配 過程 p調用過程 q的調用序列 (2) p把返回地址和當前 base_sp的值存入 q的活動記錄中，建立 q的訪問鏈，增加 base_sp的值 返回值和參數(shù) top_sp base_sp 臨時數(shù)據(jù)局部數(shù)據(jù) 控制鏈 和保存的機器狀態(tài) ? ? ? 返回值和參數(shù) 控制鏈和返回地址 base_sp top_sp 全局棧式存儲分配 過程 p調用過程 q的調用序列 (3) q保存寄存器的值和其它機器狀態(tài)信息 返回值和參數(shù) top_sp base_sp 臨時數(shù)據(jù)局部數(shù)據(jù) 控制鏈 和保存的機器狀態(tài) ? ? ? 返回值和參數(shù) 控制鏈 和保存的機器狀態(tài) 全局棧式存儲分配 過程 p調用過程 q的調用序列 (4) q根據(jù)局部數(shù)據(jù)域和臨時數(shù)據(jù)域的大小增加 top_sp的值，初始化它的局部數(shù)據(jù)，并開始執(zhí)行過程體 臨時數(shù)據(jù)局部數(shù)據(jù) 返回值和參數(shù) 返回值和參數(shù) ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 臨時數(shù)據(jù)局部數(shù)據(jù) 控制鏈 和保存的機器狀態(tài) ? ? ? 全局棧式存儲分配 調用者 p和被調用者 q之間的任務劃分 被調用者 q的責任 調用者 p的責任 調用者 p的 活動記錄 被調用者 q的活動記錄 臨時數(shù)據(jù)局部數(shù)據(jù) 返回值和參數(shù) 返回值和參數(shù) ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 棧 增 長 方 向 臨時數(shù)據(jù)局部數(shù)據(jù) 控制鏈 和保存的機器狀態(tài) ? ? ? 全局棧式存儲分配 過程 p調用過程 q的返回序列 臨時數(shù)據(jù)局部數(shù)據(jù) 返回值和參數(shù) 返回值和參數(shù) ? ? ? 控制鏈 和保存的機器狀態(tài) top_sp base_sp 棧 增 長 方 向 臨時數(shù)據(jù)局部數(shù)據(jù) 控制鏈 和保存的機器狀態(tài) ? ? ? 全局棧式存儲分配 過程 p調用過程 q的返回序列 臨時數(shù)據(jù)