編譯原理電子教案第九章運行時存儲空間組織謝強計算機科學與技術學ieqiang@本章的主要內容目標程序運行時的活動運行時存儲器的劃分靜態(tài)存儲分配簡單棧式存儲分配嵌套過程語言的棧式實現(xiàn)堆式動態(tài)存儲2本章要求

知識點：有關源語言中一些問題的討論，存儲組織，運行時刻存儲分配策略，對非局部名字的訪問，參數傳遞。深刻理解：活動記錄，棧式存儲分配，訪問鏈（存取鏈），display表。熟練掌握：（1）對于已知過程，設計出其活動記錄；（2）對于已知程序，若采用棧式存儲分配，隨著程序的執(zhí)行，畫出相應動態(tài)棧，訪問鏈（存取鏈）以及display表的變化；3計算環(huán)境計算源程序映射運行時的環(huán)境目標代碼計算源程序中的名字（常量，變量）→目標機存儲空間。它受命于源程序的執(zhí)行語義。

源程序由一組過程按某種規(guī)則組成。過程的一次執(zhí)行稱作一次活動，在過程的語句序列執(zhí)行之前，過程中訪問的對象構成此過程的運行環(huán)境，由運行支持程序組織好。編譯程序根據如何組織運行環(huán)境而生成目標代碼。

在程序語言中，程序中使用的存儲單元都由標志符來表示。它對應的內存地址都是由編譯程序在編譯時或由其生成的目標程序在運行時進行分配。

4本章教學線索1目標程序運行時的活動1.1過程的活動1.2說明的作用域（作用范圍）1.3名字與存儲的綁定1.4參數傳遞2運行時存儲器的劃分3靜態(tài)存儲分配4簡單棧式存儲分配5嵌套過程語言的棧式實現(xiàn)6堆式動態(tài)存儲51.1過程的活動過程：過程定義是一個說明，其最簡單的形式是一個標識符和一段語句相關，標示符是過程名，語句是過程體。調用：當過程名出現(xiàn)在可執(zhí)行語句里的時候，稱該過程在這一點被調用。過程調用導致過程體的執(zhí)行。過程的活動：一個過程的活動指的是該過程的一次執(zhí)行，也就是說，每次執(zhí)行一個活動?；顒拥纳嫫冢褐傅氖菑膱?zhí)行該過程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行該過程時調用其它過程花費的時間?；顒拥纳嫫诨蛘呤乔短椎模蛘呤遣恢丿B的。過程的遞歸：如果一個過程在沒有退出當前的活動時，又開始其新的活動，則這個過程是遞歸的。（遞歸有直接遞歸和間接遞歸）61.2說明的作用域（作用范圍）說明把名字與名字的屬性信息綁定在一起。說明的作用域是一個說明起作用的范圍（源程序行文）。一個名字在源程序行文中可能有幾處說明，語言的作用域規(guī)則規(guī)定了在語句序列中引用的一個名字時，該名字是在何處說明的。編譯時，處理說明語句時把名字及其屬性信息填寫進符號表（add（id.entry，））；處理引用名字時，查找這個名字的屬性信息（lookup（）），符號表管理程序根據語言的作用域規(guī)則，使lookup（）返回id的作用域中綁定的屬性信息。71.3名字與存儲的綁定名字與存儲單元的綁定是指把源程序中的數據名字映射到目標機存儲單元的過程。引進兩個函數，environment和state。environment把名字映射到一個存儲單元上；state把存儲單元映射到那里所存放的值上。可以說，函數environment把一個名字映射為一個L-value（左-值）,而函數state把一個L-value（左-值）映射為一個R-value（右-值）。如圖下圖所示。存儲單元值存儲分配

程序運行environmentstateL-valueR-value從名字到值的兩個階段映射名字

靜態(tài)概念動態(tài)對應過程定義過程活動名字說明名字的綁定說明的作用域活動的生存期81.4參數傳遞形參與實參：過程定義中的參數稱為形參；過程調用中的參數稱為實參。問題：如何把實在參數傳遞給形參？函數的返回值怎樣獲取？參數傳遞的三種形式：傳地址：把實在參數的地址傳遞給相應的形式參數；傳值：直接把實在參數的值傳遞給形式參數傳名：換名，少見的方法！特別要注意傳地址與傳值的區(qū)別！9本章教學線索1目標程序運行時的活動2運行時存儲器的劃分2.1運行時刻內存的劃分2.2活動記錄2.3存儲分配策略3靜態(tài)存儲分配4簡單棧式存儲分配5嵌套過程語言的棧式實現(xiàn)6堆式動態(tài)存儲102.1運行時刻內存的劃分運行時刻的存儲空間必須劃分以用來存放：生成的目標代碼；數據目標；用于保存過程活動蹤跡的一個控制棧。存儲空間劃分的各部分：

目標代碼靜態(tài)數據棧堆1.編譯后知道目標代碼的大小。2.Pascal主程序中的數據,c,FORTRAN3.棧:Pascal4.堆:Pascal112.2活動記錄把過程的一個活動所需要的信息組織成一塊連續(xù)的存儲單元，稱為活動記錄。一個活動所需要的信息的每個數據項有相同的生存期，因此，組織成一個活動記錄是很自然的。對于Pascal語言來說，運行過程中，當調用一個過程時，在棧頂構筑它的活動記錄；當這個過程的活動執(zhí)行完后，把它從棧頂彈出。源語言不同，實現(xiàn)方法不同，組成活動記錄的域不同。實現(xiàn)Pascal語言的活動記錄的結構如圖所示。臨時單元內情向量局部向量形式單元靜態(tài)鏈動態(tài)鏈返回地址連接數據SPTOP12連接數據：返回地址動態(tài)鏈：指向調用該過程前的最新活動記錄地址的指針。運行時，使運行棧上各數據區(qū)按動態(tài)建立的次序結成鏈，鏈頭為棧頂起始位置。靜態(tài)鏈：指向靜態(tài)直接外層最新活動記錄地址的指針，用來訪問非局部數據。形式單元：存放相應的實在參數的地址或值。局部數據區(qū)：局部變量、內情向量、臨時工作單元（如存放對表達式求值的結果）132.3存儲分配策略靜態(tài)分配策略：在編譯時對所有的數據對象分配固定的存儲單元，并且在運行時始終保持不變。棧式動態(tài)分配策略：在運行時把存儲器作為一個棧進行管理，運行時，每當調用一個過程，它所需要的存儲空間就動態(tài)地分配于棧頂，一旦退出，它所占的空間就予以釋放。堆式動態(tài)分配策略：在運行時把存儲器組織成堆結構，以便用戶可以對存儲空間進行申請與歸還。14活動樹程序執(zhí)行期間的控制流：程序執(zhí)行的控制是順序的；過程的每一次執(zhí)行都是從過程體的開頭開始，并最終把控制返回到緊接著該過程被調用點的后面。用一顆樹來描繪控制進入和離開活動的途徑。這樣的樹稱作活動樹。在一棵活動樹中：每一個結點代表一個過程的活動；

根結點代表主程序的活動；

代表a的結點是b結點的父結點當且僅當控制從活動a進入活動b；結點a在結點b的左邊當且僅當a的生存期發(fā)生在b的生存期之前?？刂茥３绦驁?zhí)行的控制流對應于從根開始，按先根次序遍歷活動樹。因此，用一個棧保存過程活動的生存蹤跡，把它稱作控制棧。當一個活動開始執(zhí)行時，把代表這個活動的結點推進棧；當這個活動結束時，把代表這個活動的結點從棧中彈出。15srq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)q(2,3)控制棧ssrsq(1.9)sq(1.9)p(1,9)sq(1.9)q(1,3)sq(1.9)q(1,3)p(1,3)sq(1.9)q(1,3)q(1,0)sq(1.9)q(1,3)q(2,3)活動樹與控制棧

控制棧中的活動都是活躍的，當前控制進入的活動在棧頂，從棧頂活動到棧底活動的活動序列是從活動樹上當前結點通向根的路徑上的結點序列：

s,q（1，9），q（l，3），q（2，3），從棧底活動到棧頂活動的活動序列表示了活動的生存期的嵌套關系。結論：擴充控制?？捎脕韺崿F(xiàn)如Pascal語言的棧式存儲分配，進入一個活動，在棧頂建立這個活動所使用的存儲空間；這個活動結束，從棧頂彈出其使用的存儲空間。16本章教學線索1目標程序運行時的活動2運行時存儲器的劃分3靜態(tài)存儲分配3.1靜態(tài)分配3.2FORTRAN的局部數據區(qū)3.3臨時變量的地址分配4簡單棧式存儲分配5嵌套過程語言的棧式實現(xiàn)6堆式動態(tài)存儲173.1靜態(tài)分配在編譯時就能夠確定一個程序在運行時所需要的存儲空間的大小，則在編譯時就能夠安排好目標程序運行時的全部數據空間，并能夠確定每個數據項的單元地址。適于靜態(tài)管理的語言必須滿足的條件：數組的上下界必須是常數過程調用不允許遞歸不允許用戶動態(tài)地建立數據實體編譯程序可以確定出現(xiàn)在程序中的數據實體的地址（一般相對于各數據區(qū)基地址的偏移量)。由于過程調用不允許遞歸，數據實體的存儲地址就和過程相聯(lián)系，過程調用的活動記錄就可以直接安排在目標代碼之后，并把各數據項的存儲地址填入到相關的目標代碼中，以便在運行時訪問這些數據存儲空間。這里，不存在對存儲區(qū)域的再利用。目標代碼運行時不必進行運行時的存儲管理。183.2FORTRAN的局部數據區(qū)FORTRAN的編譯程序將每個程序段都定義對應的局部數據區(qū)，每個數據區(qū)都有一個編號，在地址分配時，在符號表中，對每個數據名將登記上它是屬于哪個數據區(qū)的，以及在該區(qū)中的相對位置（DA、ADDR）。一般情況下，程序段的局部數據區(qū)可以直接安排在該段程序的指令代碼之后，編譯時統(tǒng)計每個數據區(qū)的單元數，對于各區(qū)的首地址暫時不分配，在運行前再用一個“裝入程序”（LOADER）把它們連成一個整體。FORTRAN的局部數據區(qū)內容：臨時變量數組簡單變量形式單元寄存器保護區(qū)返回地址稱為：隱參數返回地址：用來保存調用此程序段時的返回地址；寄存器保護區(qū)：用來保存調用段留在寄存器中的有關信息。形式單元：用來存放實在參數的地址或值。193.3臨時變量的地址分配

在三地址代碼－四元式生成中將產生大量的中間變量，在存儲空間的分配中也必須對這些臨時變量分配存儲空間。分配策略：如果兩個臨時變量名作用域不相交，則它們可以分配在同一單元中。一個臨時變量名自它第一次被定值（賦值）的地方起直至它最后一次被引用的地方止，這區(qū)間的程序所能到達的全體四元式構成了它的作用域。令臨時變量名都分配在局部數據區(qū)中，若某一單元已分配給某些臨時變量名，則把這些名字的作用域（它們必須互不相交信息記錄）作為此單元的分配信息記錄下來。每當要對一個新臨時變量名進行分配時，首先求出此名的作用域，然后按序檢查每個已分配單元，一旦發(fā)現(xiàn)新求出的作用域與某個單元所記錄的全部作用域均不相交時就把這個單元分配給這個新名，同時把它的作用域也添加到該單元的分配信息之中。如果新臨時變量的作用域和所有已分配單元的作用域均有沖突，則就分配給它一個新的單元，同時把新名的作用域作為此單元的分配信息。20一般情況下，四元式中的臨時變量都是一邊生成，馬上使用，一次賦值，一次使用，其作用域類似于配對使用的括號。因此，可以用一個棧來放表達式計算過程中的中間結果。令k為棧的指示器，設它的初值是局部區(qū)中用來存放臨時變量值的區(qū)域首地址，每當發(fā)現(xiàn)對一個新的臨時變量名Ti定值時，就用k的現(xiàn)行值作為Ti的地址，然后把k累增1。每當引用了某個臨時變量名Ti作為操作數時（此時Ti的地址必已分配），就把指示器k的值遞減1。例子：P25421本章教學線索1目標程序運行時的活動2運行時存儲器的劃分3靜態(tài)存儲分配4簡單棧式存儲分配4.1語言要求4.2基于棧的存儲控制4.3同靜態(tài)存儲分配的區(qū)別4.4整體的分配情況4.5C語言的活動記錄4.6C的過程調用、進入、數據對象空間分配和過程返回5嵌套過程語言的棧式實現(xiàn)6堆式動態(tài)存儲224簡單棧式存儲分配基于控制棧的原理：

存儲空間被組織成棧，活動記錄的推入和彈出分別對應于活動的開始和結束。與靜態(tài)分配不同的是，在每次活動中把局部名字和新的存儲單元綁定，在活動結束時，活動記錄從棧中彈出，因而局部名字的存儲空間也隨之消失。確定活動記錄中局部數據的地址：假設sp標記一個活動記錄的開始的位置，dx表示x的地址相對于sp的偏移量。那么，x在過程的目標代碼中的地址可寫成dx（sp），在運行時刻，當把x的活動記錄筑于棧頂時，寄存器sp被賦于實際的地址，sp可以是一個寄存器。23調用序列和返回序列

通過在目標代碼中生成調用序列和返回序列實現(xiàn)過程的調用。激活一個過程的活動是執(zhí)行過程語句的結果。過程語句：

p(e1，e2，……，en)的目標代碼（調用序列）完成任務：1）調用者對實在參數求值，并把它們傳送給被調用過程的活動記錄的參數域。2）調用者在被調用者的活動記錄中存放返回地址和老sp之值。之后調用者把sp之值增加到top的下一個存儲單元位置（被調用者的活動記錄首地址）。3）被調用者存放寄存器值和其它狀態(tài)信息。4）被調用者初始化其局部數據并開始執(zhí)行。返回序列，return目標代碼完成的任務是：被調用者在自己的活動記錄的返回值域中放一個返回值。利用狀態(tài)域中的信息，被調用者恢復sp和其它寄存器，并且按返回地址轉移到調用者的代碼之中。調用者復制返回值到自己的活動記錄中。任務的劃分，根據源語言、目標機器和操作系統(tǒng)等具體情況而定。上述任務，由運行支持子程序完成，可視為虛擬機指令。244.1語言要求過程不允許嵌套，但允許過程遞歸調用，如C語言。254.2基于棧的存儲控制將存儲組織成一個棧，過程的活動記錄作為一個元素進行出入棧管理。運行時，每當進入一個過程時，就把它的活動記錄入棧，而形成該過程工作時的數據區(qū)，當該活動結束時，再出棧。264.3同靜態(tài)存儲分配的區(qū)別不同的是：每次活動過程中，局部名字與新的存儲單元綁定，活動結束后，活動記錄從棧中彈出，局部名的存儲空間也隨之消失。注意：1）因而會出現(xiàn)同一過程的不同活動（不同時期）存儲空間的分配不一樣

2）由于遞歸，過程的活動可能有多個同時在棧中（活動記錄）27

4.4整體的分配情況

R的活動記錄Q的活動記錄Main的活動記錄全局數據區(qū)TopSP程序運行時的某一時刻，表明主過程Main調用Q，而Q又調用R。SP：總是指向現(xiàn)行過程活動記錄的起點，用于訪問局部數據；Top：總是指向（已占用）棧頂單元。284.5C語言的活動記錄1）連接數據：老SP、返回地址2）參數個數3）形式單元4）過程的局部變量、數組內情向量、臨時工作單元注意：C語言的非局部變量僅能出現(xiàn)在源程序頭，非局部變量可采用靜態(tài)存儲分配5）局部變量（形參）的訪問： 在編譯時，對局部變量和形參都分配了存儲單元，其地址為相對于活動記錄基地址SP的偏移量。則其絕對地址就為：

絕對地址=活動記錄基地址+相對地址

臨時工作單元內情向量簡單變量形式單元參數個數返回地址老SPSPTOP294.6C的過程調用、進入、數據對象空間分配和過程返回1）調用：將實參的地址或值傳遞給新的活動記錄中的形式單元。 過程調用的四元式：paramT1paramT2……paramTncallP，n由于形式單元在活動記錄中的起始位置是固定的，因此對于每一個形式參數paramTi，可以翻譯為如下指令：（i+3）[TOP]=Ti

（傳參數值）（i+3）[TOP]=addr（Ti）（傳參數地址）2）過程進入四元式：CALLP，n的翻譯：

1[TOP]=SP（保護現(xiàn)行的SP，即老SP）

3[TOP]=n（傳遞參數個數）

JSRP（轉子指令，轉向P的第一條指令）303）數據對象空間分配

SP=TOP+1（定義新的SP）

1[SP]=返回地址（保護返回地址）

TOP=TOP+L定義新的TOP

（L為過程P的活動記錄所需的單元數，在處理說明語句時可以計算出來）4）過程的返回（過程的活動記錄出棧，同時恢復棧頂活動記錄的TOP和SP）如果有返回值（函數），將返回值傳遞到每個特定寄存器中。

TOP=SP–1SP=0[SP]x=2[TOP]UJ0[x]（UJ為無條件轉移語句，按x中的返回地址實行變址轉移）31本章教學線索1目標程序運行時的活動2運行時存儲器的劃分3靜態(tài)存儲分配4簡單棧式存儲分配5嵌套過程語言的棧式實現(xiàn)5.1嵌套過程語言非局部名字訪問的實現(xiàn)5.2參數傳遞的實現(xiàn)6堆式動態(tài)存儲325嵌套過程語言的棧式實現(xiàn)語言要求：過程不僅允許遞歸調用，還允許過程進行嵌套定義。存儲分配的實現(xiàn)：采用棧式存儲分配，對于運行時的局部名和形參完全可以采用簡單棧式存儲分配，由于允許過程嵌套定義，因此對非局部變量的訪問需要單獨處理，可以采用:靜態(tài)鏈或顯示表（Display）來實現(xiàn)。嵌套層次：記錄過程在定義時所在的層數。約定主程序的層數為0。如果過程P的直接外層Q的層數為i，則P的層數就為i+1。在實現(xiàn)時，采用一個計數器，遇到過程定義procBegin時，計數器增加1，遇到過程結束procend時，計數器減1。將過程的層數作為過程名的一個屬性記錄在符號表中。335.1嵌套過程語言非局部名字訪問的實現(xiàn)1）靜態(tài)鏈和活動記錄在活動記錄中增加一個域，存儲指向直接外層的最新活動記錄的地址，這樣形成的鏈稱為靜態(tài)鏈。它表明過程定義時的嵌套關系。活動記錄中存儲老SP形成的鏈稱為動態(tài)鏈，它表明了過程活動時的調用關系?；顒佑涗浀慕Y構：臨時單元內情向量簡單變量形式單元形參個數靜態(tài)鏈返回地址動態(tài)鏈（老SP）SPTOP對于非局部變量的返回可以沿靜態(tài)鏈進行訪問。34programP;vara,xinteger;procedureQ(b:integer);vari:integer;procedureR(u:integer,v:integer);varc,d:integer;beginifu=1thenR(u+1,v)v=(a+c)*(b-d);end{R}beginR(1,x);end{Q}procedureS;varc,i:integer;begina=1;Q(c);end{S}begina=0;S;end011224d23c22v（形參）21u（形參）202(形參個數）191118返回地址171116i15b(形參）141(形參個數）13012返回地址11510i9c80706返回地址504x3a201返回地址00PSQR過程Q調用R時活動記錄情況352）嵌套層次顯示表和活動記錄在進入一個過程后，在建立其活動記錄區(qū)的同時建立一張嵌套層次表display，該表給出了過程的嵌套關系，如果該過程的嵌套層次為i，則它的display表就包含i+1個單元（假設主過程的層次為0），display本身是一個棧。由于過程的層數可以靜態(tài)確定，因此每個過程的display表的體積在編譯時可以確定，可以將display表作為活動記錄的一部分，置于形式單元的上端。例如：R的外層是Q，Q的外層是P，則R運行時display表的情況：R現(xiàn)行活動記錄地址Q的最新活動記錄地址P的活動記錄地址36對于非局部變量的絕對地址就為：

絕對地址=display[靜態(tài)層次]+相對地址（非局部變量所在的靜態(tài)層次可以在編譯時處理說明語句時確定，可以記錄在符號表中）在活動記錄中，display表的相對位置d是確定的，因此，在現(xiàn)行過程中引用了某一外層過程（k層）的變量x，可以用以下指令獲取x的值：LDR1，（d+k）[SP]/*獲取x所在的最新活動記錄的SP值*/LDR2，x[R1]/*變址取數，把X的值傳遞給R2*/臨時單元內情向量簡單變量Display形參參數個數全局display返回地址老SP(動態(tài)鏈）SPTOP全局display：連接數據，用于記住調用過程的display表的地址，作為生成本過程display的關鍵參數。display根據全局display所指示的地址，從調用它的過程中的display表中抄入i個地址（假設該過程層數為i），然后將自己的起始地址放在display表頂。37programP;vara,xinteger;procedureQ(b:integer);vari:integer;procedureR(u:integer,v:integer);varc,d:integer;beginifu=1thenR(u+1,v)v=(a+c)*(b-d);end{R}beginR(1,x);end{Q}procedureS;varc,i:integer;begina=1;Q(c);end{S}begina=0;S;end0112191318017b（形參）161（形參個數）159(全局display）14返回地址13512i11c105908072（全局display)6返回地址504x3a201返回地址00displaydisplaydisplayS調用Q時PSQ385.2參數傳遞的實現(xiàn)ParT，T為數組根據不同語言的要求或傳遞數組T的首地址，或傳送它的內情向量地址。ParT，T為過程一般需要傳遞過程T的入口地址和現(xiàn)行的display地址。ParT，T為標號一般需要傳遞標號T的地址和標號定義所在過程的活動記錄首地址。ParT，T為形式參數傳遞形式單元T的內容。39本章教學線索1目標程序運行時的活動2運行時存儲器的劃分3靜態(tài)存儲分配4簡單棧式存儲分配5嵌套過程語言的棧式實現(xiàn)6堆式動態(tài)存儲6.1堆式分配的必要性（以C語言為例）6.2

堆式存儲管理的實現(xiàn)6.3

減少碎片的技術6.4

空間的釋放406堆式動態(tài)存儲對于允許程序為變量在運行時動態(tài)申請和釋放存儲空間的語言，采用堆式分配是最有效的解決方案。堆式分配的基本思想是，為運行的程序劃出適當大的空間(稱為堆Heap)，每當程序申請空間時，就從堆的空閑區(qū)找出一塊空間分配給程序，每當釋放時則回收。416.1

堆式分配的必要性（以C語言為例）在C中處理鏈表等結構時,常常隨機地插入或刪除一些結點,利用指針變量和結構類型,可動態(tài)地生成新結點(使用malloc()函數),或刪除之(使用free()函數).例如structnode{chardata;structnode*next;}；定義了鏈表的結點，下面函數可在表的尾部添加新結點:voidAppend(structnode*head,charch){structnode*p=head;while((p->next)!=NULL)p=p->next;p->next=malloc(sizeof(structnode));p->next->data=ch;p->next->next=NULL;}還可用下面的函數在表頭刪除一結點:voidDelete(structnode*head){structnode*p=head;if(p!=NULL){head=head->next;free(p);}}426.2

堆式存儲管理的實現(xiàn)1定長塊管理

堆式動態(tài)儲分配最簡單的實現(xiàn)是按定長塊進行。初始化時，將堆存儲空間分成長度相等的若干塊，每塊中指定一個鏈域，按照鄰塊的順序把所有塊鏈成一個鏈表，用指針available指向鏈