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