編譯原理第9章.ppt

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