編譯原理第9篇

第九章程序運行期間的存儲空間組織.本節(jié)內容與要點運行時存儲空間的劃分活動記錄概念存儲空間分配策略

1、靜態(tài)存儲分配

2、動態(tài)存儲分配

簡單棧式存儲分配

嵌套過程語言的棧式分配典型范例解析.運行時存儲空間的劃分編譯程序為了使它編譯后得到的目標程序能夠運行，要從操作系統(tǒng)中獲得一塊存儲空間。對這塊提供運行的空間應該進行劃分以便存放：生成的目標代碼、數據對象和跟蹤過程活動的控制棧。目標代碼的大小在編譯時可以確定，所以編譯程序可以把它放在一個靜態(tài)確定的區(qū)域。有一些數據對象的大小在編譯時也能確定，因此它們也可以放在靜態(tài)確定的區(qū)域。.運行時存儲空間的劃分（續(xù)）目標代碼靜態(tài)數據棧↓↑堆返回.活動記錄為了管理過程在一次執(zhí)行中所需要的信息，使用一個連續(xù)的存儲塊，這樣的一個連續(xù)存儲塊稱為活動記錄（ActivationRecord）。當過程調用時，產生一個過程的新的活動，用一個活動記錄表示該活動的相關信息，并將其壓入棧。.當過程返回（活動結束）時，當前活動記錄一般包含如下內容：連接數據返回地址動態(tài)鏈：指向調用該過程前的最新活動記錄地址的指針。運行時，使運行棧上各數據區(qū)按動態(tài)建立的次序結成鏈。鏈頭為棧頂起始位置。靜態(tài)鏈：指向靜態(tài)直接外層最新活動記錄地址的指針，用來訪問非局部數據。.形式單元：存放相應的實在參數的地址或值。局部數據區(qū)：局部變量、內情向量、臨時工作單元（如存放對表達式求值的結果）。指針SP指向現行過程（即最新進入工作的那個過程）的活動記錄在棧里的起始位置。.活動記錄結構圖臨時單元內情向量局部變量形式單元靜態(tài)鏈動態(tài)連返回地址TOPSP連接數據返回.存儲分配策略靜態(tài)分配策略在編譯時對所有數據對象分配固定的存儲單元，且在運行時始終保持不變。棧式動態(tài)分配策略在運行時把存儲器作為一個棧進行管理，運行時，每當調用一個過程，它所需要的存儲空間就動態(tài)地分配于棧頂，一旦退出，它所占空間就予以釋放。堆式動態(tài)分配策略在運行時把存儲器組織成堆結構，以便用戶關于存儲空間的申請與歸還（回收），凡申請者從堆中分給一塊，凡釋放者退回給堆。返回.一、靜態(tài)分配策略適用范圍和特點：

1、程序語言不允許遞歸過程；2、不許含可變體積的數據項目或待定性質的名字；3、在編譯時就能夠確定一個程序在運行時所需的存貯空間大小，能夠安排好目標程序運行的全部數據空間，并能確定每個數據項的單元地址。.適于靜態(tài)存貯分配的語言必須滿足以下條件：(1)數組的上下界必須是常數；(2)過程調用不允許遞歸；(3）不允許采用動態(tài)的數據結構（即在程序運行過程中申請和釋放的數據結構）。.由于過程調用不允許遞歸，數據項的存貯地址就與過程相聯(lián)系。過程調用所使用的局部數據區(qū)可以直接安排在過程的目標代碼之后，并把各數據項的存貯地址填入相關的目標代碼中，以便在過程運行時訪問這個局部數據區(qū)。這里，不存在對存貯區(qū)的再利用問題。在執(zhí)行目標程序時不必進行運行時的存貯空間管理，過程的進入和退出變得極為簡單。.例：一個程序段的局部數據區(qū)返回返回.二、動態(tài)分配策略適用：程序語言允許遞歸過程和可變（體積的）數組，其程序數據空間的分配需采用某種動態(tài)策略（在程序運行時動態(tài)地進行分配）。棧式動態(tài)分配策略：目標程序可用一個棧作為動態(tài)的數據空間。運行時，每當進入一個過程或分程序，它所需的數據空間就動態(tài)地分配于棧頂，一旦退出，它所占用的空間就予以釋放。堆式動態(tài)分配策略：如果程序語言允許用戶動態(tài)地申請和釋放存貯空間，而且申請和釋放之間不一定遵守先請后放和后請先放的原則，此時就必須讓運行程序持有一個大存貯區(qū)（稱為堆），凡申請者從堆中分給一塊，凡釋放者退還給堆。返回.簡單的棧式存貯分配適用于簡單程序語言的實現：語言沒有分程序結構，過程定義不允許嵌套，但允許過程的遞歸調用，允許過程含有可變數組。C語言就是這樣一種語言。其局部名稱的存儲分配，可以直接采用棧式存儲分配策略。

.1、棧式存儲分配使用棧式存儲分配法意味著把存儲組成一個棧。運行時，每當進入一個過程（一個新的活動開始）時，就把它的活動記錄壓入棧，從而形成過程工作時的數據區(qū)，一個過程的活動記錄的體積在編譯時是可靜態(tài)確定的。當該活動結束（過程退出）時，再把它的活動記錄彈出棧，這樣，它在棧頂上的數據區(qū)也隨即不復存在。.C語言的程序結構

全局數據說明

Main(){Main中的數據說明

}voidR(){R中的數據說明

}voidR(){R中的數據說明

}.C語言程序的存儲組織R的活動記錄Q的活動記錄Main的活動記錄主程序全局數據區(qū)

TOPSPSP:總指向現行過程活動記錄的起點，用于訪問局部數據。TOP:始終指向（已占用）棧頂單元。.2、C的活動記錄C的活動記錄有以下四個項目。1、連接數據（兩項）：(1)老SP值，即前一活動記錄的起始地址；(2)返回地址。2、參數個數。3、形式單元（存放實在參數的值或地址）。

4、過程的局部變量、數組內情向量和臨時工作單元。.C過程的活動記錄臨時單元內情向量簡單變量形式單元參數個數返回地址老SP012SPTOP.3.、過程的執(zhí)行分為三步：

(1)過程調用（2）過程進入（3）過程返回.(1)過程調用---par相應的目標代碼過程調用的四元式序列為：parT1parT2

…parTncallp,n每個parTi(i=1,2,…，n)可直接翻譯成如下指令：(i+3)[TOP]:=Ti/*傳遞參數值*/或(i+3)[TOP]:=addr[Ti]/*傳遞參數地址*/.(1)過程調用---call相應的目標代碼四元式callp,n翻譯成：1[TOP]:=SP/*保護現行SP*/3[TOP]:=n／*傳遞參數個數*/JSRP/*轉子指令，轉向P過程的第一條指令*/…T2T1參數個數n現行SP值…調用過程P的活動記錄01234TOP+3TOPSP.(2)過程進入轉入過程P后，首先要做的工作是定義新活動記錄的SP,保護返回地址和定義新活動記錄的TOP值，即執(zhí)行下述指令：SP:＝TOP+1/*定義新SP*/1[SP]：=返回地址/*保護返回地*/TOP:=TOP+L;/*定義新TOP*/L是過程P的活動記錄所需的單元數，這個數在編譯時可靜態(tài)地計算出來（活動記錄的體積在編譯時可靜態(tài)地確定）。.對每個數組說明，相應的目標指令組將做以下幾件工作：①計算各維的上、下限；②調用數組空間分配子程序，其參數是各維的上、下限和內情向量單元首地址。數組空間分配子程序計算并填好內情向量的所有信息，然后在TOP所指的位置之上留出數組所需的空間，并將TOP調整為指向數組區(qū)的頂端。此后，在過程段執(zhí)行語句的工作過程中，凡引用形式參數、局部變量或數組元素都是以SP為基址進行相對訪問的。.進入過程P后所做工作示意P的數組區(qū)返回地址SPTOP調用過程P的活動記錄（長度為L)01.(3)過程返回C語言以及其它一些相似的語言含有return(E)的返回語句，E為表達式。假定E值已計算出來并已存放在某臨時單元T中，可將T只傳送到某個特定寄存器（調用過程將從這個特定的寄存器中獲得P的結果）。剩下的工作就是恢復SP和TOP為進入過程P之前的原值（即指向工作空間），并按返回地址實行無條件轉移。.過程P返回示意即執(zhí)行下述指令序列：TOP:=SP-1／*恢復調用過程的TOP值*/SP:=0[SP]／*恢復調用過程的SP值*/X:=2[TOP]／＊將返回地址送X*/UJ0[X]/*無條件轉移，按X地址返回*/…返回地址老SP調用過程空間P空間SPTOP返回.嵌套過程語言的棧式分配由于過程定義是嵌套的，一個過程可以引用包圍它的任一外層過程所定義的變量或數組，運行時，一個過程Q可能引用它的任一外層過程P的最新活動記錄中的某些數據（這些數據視為過程Q的非局部量）。.非局部名字的訪問的實現為了在活動記錄中查找非局部名字所對應的存儲空間，過程Q運行時必須知道它的所有外層過程的最新活動記錄的地址。由于允許遞歸性，過程的活動記錄的位置（即使是相對位置）也往往是變遷的。因此，必須設法跟蹤每個外層過程的最新活動記錄的位置。跟蹤的辦法很多，本節(jié)討論兩種方法：一種是通過靜態(tài)鏈；另一種是通過顯示表（display，）。.一、靜態(tài)鏈和活動記錄引入一個稱為靜態(tài)鏈的指針，該指針為活動記錄的一個域，指向直接外層的最新活動記錄的地址。這就意味著在運行時棧上的數據區(qū)（活動記錄）之間又拉出一條鏈，這個鏈稱為靜態(tài)鏈，靜態(tài)鏈是從一個過程的當前活動記錄指向其直接外層的最新活動記錄。.具有靜態(tài)鏈的活動記錄結構臨時單元內情向量簡單變量形式參數形參個數存取鏈（靜態(tài)鏈）返回地址控制鏈（動態(tài)鏈）：老SPSPTOP.假定過程的嵌套關系如下：

P;vara;Q(b);vari;R;varc,d;…callR;…S;varc,I;…callQ;……callS;….過程調用試運行棧的變化.i形式參數：c形參個數：1靜態(tài)鏈：0返回地址老SPic形參個數：0靜態(tài)鏈：0返回地址老SP:0a形參個數：0靜態(tài)鏈：0返回地址0SPTOPS過程P過程Q過程.例：請見書上P258頁嵌套程序。寫出遞歸調用時活動記錄的變化。（程序見下頁）..返回.二、嵌套層次顯示表(display)和活動記錄為了提高訪問非局部量的速度，還可以引用一個指針數組，稱為嵌套層次顯示表。每進入一個過程后，在建立它的活動記錄區(qū)的同時建立一張嵌套層次表display.假定現進入的過程的層數為i，則它的display表含有i＋1個單元。此表本身是一個小找，自頂向下每個單元依次存放著現行層，直接外層，…，直至最外層（0層，主程序層）等每一層過程的最新活動記錄的基地址。.例如，令過程R的外層為Q，Q的外層為P,則過程R運行時display表的內容應為：R的現行活動記錄始址（SP的現行值）Q的最新活動記錄地址P的活動記錄地址012.由于過程的層數可以靜態(tài)確定，因此每個過程的display表的體積在編譯時即可知道。由一個非局部量說明所在的靜態(tài)層數和相對活動記錄的相對地址，就可得到絕對地址：絕對地址=display［靜態(tài)層數」+相對地址.活動記錄結構臨時變量內情變量簡單變量display形式單元參數個數全局display地址返回地址老SP0123dSPTOPd個單元第k層sp…最外層過程sp主程序spd+01k.由于每個過程的形式單元的數目在編譯時是知道的，因此DISPLAY的相對地址d（相對于活動記錄起點）在編譯時也是完全確定的。被調用過程為了建立自己的DISPLAY,則必須知道它的直接外層過程的DISPLAY,這意味著必須把直接外層的DISPLAY地址作為連接數據之一（稱為“全局DISPLAY地址”）傳送給被調用過程。于是連接數據變?yōu)榘棧孩倮蟂P值，②返回地址，③全局DISPLAY地址。注意:0層過程（主程序）的DISPLAY只含一項，這一項就是在主程序開始工作時建立的第一個SP值。.2.過程調用、進入和返回(1)過程調用。過程調用所做工作與簡單棧式存貯分配大體相同，只是現在增加了一個連接數據，所以每個parTi相應的指令應改為：(i+4)[TOP]：=Ti;或者(i+4)[TOP]:=addr[T;］

callp,n所對應的指令應為：1[TOP]:=SP；/*保護現行SP*/3[TOP]:=SP+d；/*將直接外層的DISPLAY始址作為P的全局DISPLAY地址*/4[TOP]:＝n：/*傳遞參數個數＊lJSRP/*轉向P的第一條指令*/.(2)過程進入。在轉入過程P后，首先執(zhí)行和簡單棧式存貯分配相同的指令：SP:＝TOP+1/*定義新的SP*/1[SP]:=返回地址/*保護返回地址*/TOP:=TOP+L；/*定義新的TOP*/其次，應按第三項連接數據所提供的全局DISPLAY地址，自底而上地抄錄i個單元內容(i為P的層次），然后再添上新的SP值而形成現行過程P的DISPLAY（共i+1個單元）。.(3)過程返回。當過程P工作完畢要返回到調用段時，若return語句含有返回值或P是個函數過程，則把己算好的值傳送到某個特定的寄存器，然后執(zhí)行：TOP:＝SP-1/*恢復調用過程的TOP值*/SP:=O[SP]/*恢復調用過程的SP值*/X:=2[TOP]/*將返回地址送X*/UJ0[X]/*無條件轉移，返回*/過程返回執(zhí)行的指令與簡單棧式存貯分配的過程返回完全一樣。.參數個數:n全局display地址調