編譯原理第9章.ppt

第九章程序運行期間的存儲空間組織 本節(jié)內(nèi)容與要點 運行時存儲空間的劃分活動記錄概念存儲空間分配策略1 靜態(tài)存儲分配2 動態(tài)存儲分配簡單棧式存儲分配嵌套過程語言的棧式分配典型范例解析 運行時存儲空間的劃分 編譯程序為了使它編譯后得到的目標(biāo)程序能夠運行 要從操作系統(tǒng)中獲得一塊存儲空間 對這塊提供運行的空間應(yīng)該進行劃分以便存放 生成的目標(biāo)代碼 數(shù)據(jù)對象和跟蹤過程活動的控制棧 目標(biāo)代碼的大小在編譯時可以確定 所以編譯程序可以把它放在一個靜態(tài)確定的區(qū)域 有一些數(shù)據(jù)對象的大小在編譯時也能確定 因此它們也可以放在靜態(tài)確定的區(qū)域 運行時存儲空間的劃分 續(xù) 返回 活動記錄 為了管理過程在一次執(zhí)行中所需要的信息 使用一個連續(xù)的存儲塊 這樣的一個連續(xù)存儲塊稱為活動記錄 ActivationRecord 當(dāng)過程調(diào)用時 產(chǎn)生一個過程的新的活動 用一個活動記錄表示該活動的相關(guān)信息 并將其壓入棧 當(dāng)過程返回 活動結(jié)束 時 當(dāng)前活動記錄一般包含如下內(nèi)容 連接數(shù)據(jù)返回地址動態(tài)鏈 指向調(diào)用該過程前的最新活動記錄地址的指針 運行時 使運行棧上各數(shù)據(jù)區(qū)按動態(tài)建立的次序結(jié)成鏈 鏈頭為棧頂起始位置 靜態(tài)鏈 指向靜態(tài)直接外層最新活動記錄地址的指針 用來訪問非局部數(shù)據(jù) 形式單元 存放相應(yīng)的實在參數(shù)的地址或值 局部數(shù)據(jù)區(qū) 局部變量 內(nèi)情向量 臨時工作單元 如存放對表達式求值的結(jié)果 指針SP指向現(xiàn)行過程 即最新進入工作的那個過程 的活動記錄在棧里的起始位置 活動記錄結(jié)構(gòu)圖 TOP SP 連接數(shù)據(jù) 返回 存儲分配策略 靜態(tài)分配策略在編譯時對所有數(shù)據(jù)對象分配固定的存儲單元 且在運行時始終保持不變 棧式動態(tài)分配策略在運行時把存儲器作為一個棧進行管理 運行時 每當(dāng)調(diào)用一個過程 它所需要的存儲空間就動態(tài)地分配于棧頂 一旦退出 它所占空間就予以釋放 堆式動態(tài)分配策略在運行時把存儲器組織成堆結(jié)構(gòu) 以便用戶關(guān)于存儲空間的申請與歸還 回收 凡申請者從堆中分給一塊 凡釋放者退回給堆 返回 一 靜態(tài)分配策略 適用范圍和特點 1 程序語言不允許遞歸過程 2 不許含可變體積的數(shù)據(jù)項目或待定性質(zhì)的名字 3 在編譯時就能夠確定一個程序在運行時所需的存貯空間大小 能夠安排好目標(biāo)程序運行的全部數(shù)據(jù)空間 并能確定每個數(shù)據(jù)項的單元地址 適于靜態(tài)存貯分配的語言必須滿足以下條件 1 數(shù)組的上下界必須是常數(shù) 2 過程調(diào)用不允許遞歸 3 不允許采用動態(tài)的數(shù)據(jù)結(jié)構(gòu) 即在程序運行過程中申請和釋放的數(shù)據(jù)結(jié)構(gòu) 由于過程調(diào)用不允許遞歸 數(shù)據(jù)項的存貯地址就與過程相聯(lián)系 過程調(diào)用所使用的局部數(shù)據(jù)區(qū)可以直接安排在過程的目標(biāo)代碼之后 并把各數(shù)據(jù)項的存貯地址填入相關(guān)的目標(biāo)代碼中 以便在過程運行時訪問這個局部數(shù)據(jù)區(qū) 這里 不存在對存貯區(qū)的再利用問題 在執(zhí)行目標(biāo)程序時不必進行運行時的存貯空間管理 過程的進入和退出變得極為簡單 例 一個程序段的局部數(shù)據(jù)區(qū) 返回 返回 二 動態(tài)分配策略 適用 程序語言允許遞歸過程和可變 體積的 數(shù)組 其程序數(shù)據(jù)空間的分配需采用某種動態(tài)策略 在程序運行時動態(tài)地進行分配 棧式動態(tài)分配策略 目標(biāo)程序可用一個棧作為動態(tài)的數(shù)據(jù)空間 運行時 每當(dāng)進入一個過程或分程序 它所需的數(shù)據(jù)空間就動態(tài)地分配于棧頂 一旦退出 它所占用的空間就予以釋放 堆式動態(tài)分配策略 如果程序語言允許用戶動態(tài)地申請和釋放存貯空間 而且申請和釋放之間不一定遵守先請后放和后請先放的原則 此時就必須讓運行程序持有一個大存貯區(qū) 稱為堆 凡申請者從堆中分給一塊 凡釋放者退還給堆 返回 簡單的棧式存貯分配 適用于簡單程序語言的實現(xiàn) 語言沒有分程序結(jié)構(gòu) 過程定義不允許嵌套 但允許過程的遞歸調(diào)用 允許過程含有可變數(shù)組 C語言就是這樣一種語言 其局部名稱的存儲分配 可以直接采用棧式存儲分配策略 1 棧式存儲分配 使用棧式存儲分配法意味著把存儲組成一個棧 運行時 每當(dāng)進入一個過程 一個新的活動開始 時 就把它的活動記錄壓入棧 從而形成過程工作時的數(shù)據(jù)區(qū) 一個過程的活動記錄的體積在編譯時是可靜態(tài)確定的 當(dāng)該活動結(jié)束 過程退出 時 再把它的活動記錄彈出棧 這樣 它在棧頂上的數(shù)據(jù)區(qū)也隨即不復(fù)存在 C語言的程序結(jié)構(gòu) 全局數(shù)據(jù)說明Main Main中的數(shù)據(jù)說明 voidR R中的數(shù)據(jù)說明 voidR R中的數(shù)據(jù)說明 C語言程序的存儲組織 TOP SP SP 總指向現(xiàn)行過程活動記錄的起點 用于訪問局部數(shù)據(jù) TOP 始終指向 已占用 棧頂單元 2 C的活動記錄 C的活動記錄有以下四個項目 1 連接數(shù)據(jù) 兩項 1 老SP值 即前一活動記錄的起始地址 2 返回地址 2 參數(shù)個數(shù) 3 形式單元 存放實在參數(shù)的值或地址 4 過程的局部變量 數(shù)組內(nèi)情向量和臨時工作單元 C過程的活動記錄 0 1 2 SP TOP 3 過程的執(zhí)行 分為三步 1 過程調(diào)用 2 過程進入 3 過程返回 1 過程調(diào)用 par相應(yīng)的目標(biāo)代碼 過程調(diào)用的四元式序列為 parT1parT2 parTncallp n 每個parTi i 1 2 n 可直接翻譯成如下指令 i 3 TOP Ti 傳遞參數(shù)值 或 i 3 TOP addr Ti 傳遞參數(shù)地址 1 過程調(diào)用 call相應(yīng)的目標(biāo)代碼 四元式callp n翻譯成 1 TOP SP 保護現(xiàn)行SP 3 TOP n 傳遞參數(shù)個數(shù) JSRP 轉(zhuǎn)子指令 轉(zhuǎn)向P過程的第一條指令 調(diào)用過程 P的活動記錄 0 1 2 3 4 TOP 3 TOP SP 2 過程進入 轉(zhuǎn)入過程P后 首先要做的工作是定義新活動記錄的SP 保護返回地址和定義新活動記錄的TOP值 即執(zhí)行下述指令 SP TOP 1 定義新SP 1 SP 返回地址 保護返回地 TOP TOP L 定義新TOP L是過程P的活動記錄所需的單元數(shù) 這個數(shù)在編譯時可靜態(tài)地計算出來 活動記錄的體積在編譯時可靜態(tài)地確定 對每個數(shù)組說明 相應(yīng)的目標(biāo)指令組將做以下幾件工作 計算各維的上 下限 調(diào)用數(shù)組空間分配子程序 其參數(shù)是各維的上 下限和內(nèi)情向量單元首地址 數(shù)組空間分配子程序計算并填好內(nèi)情向量的所有信息 然后在TOP所指的位置之上留出數(shù)組所需的空間 并將TOP調(diào)整為指向數(shù)組區(qū)的頂端 此后 在過程段執(zhí)行語句的工作過程中 凡引用形式參數(shù) 局部變量或數(shù)組元素都是以SP為基址進行相對訪問的 進入過程P后所做工作示意 SP TOP 調(diào)用過程 P的活動記錄 長度為L 0 1 3 過程返回 C語言以及其它一些相似的語言含有return E 的返回語句 E為表達式 假定E值已計算出來并已存放在某臨時單元T中 可將T只傳送到某個特定寄存器 調(diào)用過程將從這個特定的寄存器中獲得P的結(jié)果 剩下的工作就是恢復(fù)SP和TOP為進入過程P之前的原值 即指向工作空間 并按返回地址實行無條件轉(zhuǎn)移 過程P返回示意 即執(zhí)行下述指令序列 TOP SP 1 恢復(fù)調(diào)用過程的TOP值 SP 0 SP 恢復(fù)調(diào)用過程的SP值 X 2 TOP 將返回地址送X UJ0 X 無條件轉(zhuǎn)移 按X地址返回 調(diào)用過程空間 P空間 SP TOP 返回 嵌套過程語言的棧式分配 由于過程定義是嵌套的 一個過程可以引用包圍它的任一外層過程所定義的變量或數(shù)組 運行時 一個過程Q可能引用它的任一外層過程P的最新活動記錄中的某些數(shù)據(jù) 這些數(shù)據(jù)視為過程Q的非局部量 非局部名字的訪問的實現(xiàn) 為了在活動記錄中查找非局部名字所對應(yīng)的存儲空間 過程Q運行時必須知道它的所有外層過程的最新活動記錄的地址 由于允許遞歸性 過程的活動記錄的位置 即使是相對位置 也往往是變遷的 因此 必須設(shè)法跟蹤每個外層過程的最新活動記錄的位置 跟蹤的辦法很多 本節(jié)討論兩種方法 一種是通過靜態(tài)鏈 另一種是通過顯示表 display 一 靜態(tài)鏈和活動記錄 引入一個稱為靜態(tài)鏈的指針 該指針為活動記錄的一個域 指向直接外層的最新活動記錄的地址 這就意味著在運行時棧上的數(shù)據(jù)區(qū) 活動記錄 之間又拉出一條鏈 這個鏈稱為靜態(tài)鏈 靜態(tài)鏈?zhǔn)菑囊粋€過程的當(dāng)前活動記錄指向其直接外層的最新活動記錄 具有靜態(tài)鏈的活動記錄結(jié)構(gòu) SP TOP 假定過程的嵌套關(guān)系如下 P vara Q b vari R varc d callR S varc I callQ callS 過程調(diào)用試運行棧的變化 SP TOP S過程 P過程 Q過程 例 請見書上P258頁嵌套程序 寫出遞歸調(diào)用時活動記錄的變化 程序見下頁 返回 二 嵌套層次顯示表 display 和活動記錄 為了提高訪問非局部量的速度 還可以引用一個指針數(shù)組 稱為嵌套層次顯示表 每進入一個過程后 在建立它的活動記錄區(qū)的同時建立一張嵌套層次表display 假定現(xiàn)進入的過程的層數(shù)為i 則它的display表含有i 1個單元 此表本身是一個小找 自頂向下每個單元依次存放著現(xiàn)行層 直接外層 直至最外層 0層 主程序?qū)?等每一層過程的最新活動記錄的基地址 例如 令過程R的外層為Q Q的外層為P 則過程R運行時display表的內(nèi)容應(yīng)為 0 1 2 由于過程的層數(shù)可以靜態(tài)確定 因此每個過程的display表的體積在編譯時即可知道 由一個非局部量說明所在的靜態(tài)層數(shù)和相對活動記錄的相對地址 就可得到絕對地址 絕對地址 display 靜態(tài)層數(shù) 相對地址 活動記錄結(jié)構(gòu) 0 1 2 3 d SP TOP d個單元 d 0 1 k 由于每個過程的形式單元的數(shù)目在編譯時是知道的 因此DISPLAY的相對地址d 相對于活動記錄起點 在編譯時也是完全確定的 被調(diào)用過程為了建立自己的DISPLAY 則必須知道它的直接外層過程的DISPLAY 這意味著必須把直接外層的DISPLAY地址作為連接數(shù)據(jù)之一 稱為 全局DISPLAY地址 傳送給被調(diào)用過程 于是連接數(shù)據(jù)變?yōu)榘?老SP值 返回地址 全局DISPLAY地址 注意 0層過程 主程序 的DISPLAY只含一項 這一項就是在主程序開始工作時建立的第一個SP值 2 過程調(diào)用 進入和返回 1 過程調(diào)用 過程調(diào)用所做工作與簡單棧式存貯分配大體相同 只是現(xiàn)在增加了一個連接數(shù)據(jù) 所以每個parTi相應(yīng)的指令應(yīng)改為 i 4 TOP Ti 或者 i 4 TOP addr T callp n所對應(yīng)的指令應(yīng)為 1 TOP SP 保護現(xiàn)行SP 3 TOP SP d 將直接外層的DISPLAY始址作為P的全局DISPLAY地址 4 TOP n 傳遞參數(shù)個數(shù) lJSRP 轉(zhuǎn)向P的第一條指令 2 過程進入 在轉(zhuǎn)入過程P后 首先執(zhí)行和簡單棧式存貯分配相同的指令 SP TOP 1 定義新的SP 1 SP 返回地址 保護返回地址 TOP TOP L 定義新的TOP 其次 應(yīng)按第三項連接數(shù)據(jù)所提供的全局DISPLAY地址 自底而上地抄錄i個單元內(nèi)容 i為P的層次 然后再添上新的SP值而形成現(xiàn)行過程P的DISPLAY 共i 1個單元 3 過程返回 當(dāng)過程P工作完畢要返回到調(diào)用段時 若return語句含有返回值或P是個函數(shù)過程 則把己算好的值傳送到某個特定的寄存器 然后執(zhí)行 TOP SP 1 恢復(fù)調(diào)用過程的TOP值 SP O SP 恢復(fù)調(diào)用過程的SP值 X 2 TOP 將返回地址送X UJ0 X 無條件轉(zhuǎn)移 返回 過程返回執(zhí)行的指令與簡單棧式存貯分配的過程返回完全一樣 TOP P過程空間 調(diào)用過程空間 SP 1 2 3 4 d 定義新的SP 定義新的TOP 按全局display地址復(fù)制display表