運行時的存儲組織及管理

1、運行時的存儲組織及管理編譯器的應用模型編譯器的應用模型出出錯錯處處理理語法分析程序語法分析程序語義分析程序語義分析程序目標代碼生成程序目標代碼生成程序詞法分析程序詞法分析程序中間代碼生成程序中間代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序表表格格管管理理編譯的前端編譯的前端Front End編譯的后端編譯的后端Back End4/12/20222運行時的存儲組織及管理運行時的存儲組織及管理概述概述存儲組織存儲組織運行時的存儲分配策略運行時的存儲分配策略靜態(tài)存儲分配靜態(tài)存儲分配動態(tài)存儲分配動態(tài)存儲分配對非局部名字的訪問對非局部名字的訪問參數(shù)傳遞參數(shù)傳遞4/12/20223運行時的存儲組織及管理運行時的存

2、儲組織及管理 計算環(huán)境 運行時的環(huán)境 計算 目標代碼當詞法分析掃描得到標識符，并將它填入符號表的過程中需要給識別出來的標識符分配內(nèi)存空間。源程序由一組過程按某種規(guī)那么組成。過程的一次執(zhí)行稱作一次活動。在過程的語句序列執(zhí)行之前，過程中訪問的對象構成此過程的運行環(huán)境，由運行支持程序組織好。編譯程序根據(jù)如何組織運行環(huán)境而生成目標代碼。映射源程序4/12/20224運行時環(huán)境的作用運行時環(huán)境的作用目標程序運行時所需存儲空間的組織與管理以及源目標程序運行時所需存儲空間的組織與管理以及源程序中變量存儲空間的分配。程序中變量存儲空間的分配。4/12/20225有關源程序中的一些問題有關源程序中的一些問題問題

3、的提出：如何問題的提出：如何構造運行程序的策略和方法構造運行程序的策略和方法過程過程活動樹活動樹控制?？刂茥Ｕf明的作用域說明的作用域名字的綁定名字的綁定構造運行程序和源程序有關的一些問題構造運行程序和源程序有關的一些問題4/12/20226過程過程源程序由一組過程組成，不同的程序設計語言，由源程序由一組過程組成，不同的程序設計語言，由過程構成源程序的方法不同。過程構成源程序的方法不同。構成源程序的兩個過程行文，要么是嵌套的，要么構成源程序的兩個過程行文，要么是嵌套的，要么是不相交的。是不相交的。4/12/20227program sort(input, output);var a:array0

4、.10 of integer;procedure readarry;var i: integer;beginfor i:=1 to 9 do read(ai)end;function partition(y,z:integer):integer;var i,j,x,v : integer;begin end;procedure quicksort(m,n:integer)var i:integer;beginif(nm) then begini:=partition(m,n);quicksort(m,i-1);quicksort(i+1,n)endendbegina0 := -9999;a10

5、:=9999;readarray;quicksort(1,9)end4/12/20228活動樹活動樹程序執(zhí)行期間的控制流：程序執(zhí)行期間的控制流： 程序執(zhí)行的控制是連續(xù)的：在任何一步，控制都處于程序的某一點程序執(zhí)行的控制是連續(xù)的：在任何一步，控制都處于程序的某一點過程的每一次執(zhí)行都是從過程體的開頭過程的每一次執(zhí)行都是從過程體的開頭 開始，并最終把控制返回到緊接開始，并最終把控制返回到緊接著該過程被調(diào)用點的后面。著該過程被調(diào)用點的后面。過程的一次活動過程的一次活動: 過程體的每一次執(zhí)行。過程體的每一次執(zhí)行。過程過程p的一次活動的的一次活動的:在該過程體的執(zhí)行中的第一步和最后一步之在該過程體的執(zhí)行中

6、的第一步和最后一步之間的一序列步驟的間的一序列步驟的，其中包括執(zhí)行過程，其中包括執(zhí)行過程p所調(diào)用的過程的所調(diào)用的過程的執(zhí)行時間，以及這些過程所調(diào)用的過程的執(zhí)行時間，以及這些過程所調(diào)用的過程的，如此等等。，如此等等。一個過程是遞歸的，如果同一過程的一次新的活動可以在前面活動結束一個過程是遞歸的，如果同一過程的一次新的活動可以在前面活動結束以前開始。以前開始。4/12/20229活動樹活動樹為什么過程的活動可以用樹形結構描述？為什么過程的活動可以用樹形結構描述？過程活動的特點：過程活動的特點：每當控制流從過程每當控制流從過程p的活動進入到過程的活動進入到過程q的活動中后，的活動中后，它將返回到過程

7、它將返回到過程p的同一次活動中。的同一次活動中。也就是說，如果也就是說，如果a和和b是兩個過程活動，那么它們的生是兩個過程活動，那么它們的生存期要么是不重疊的，要么是嵌套的。存期要么是不重疊的，要么是嵌套的。在樹形結構中，節(jié)點間的關系就反映了過程之間的在樹形結構中，節(jié)點間的關系就反映了過程之間的關系：關系：父子關系：嵌套父子關系：嵌套兄弟關系：先后兄弟關系：先后4/12/202210活動樹活動樹用一顆樹來描繪控制進入和離開活動的途徑。這祥用一顆樹來描繪控制進入和離開活動的途徑。這祥的樹稱作活動樹。的樹稱作活動樹。每個節(jié)點代表過程的一個活動每個節(jié)點代表過程的一個活動根節(jié)點代表主程序的活動根節(jié)點代

8、表主程序的活動當且僅當控制流從活動當且僅當控制流從活動a進入活動進入活動b時，節(jié)點時，節(jié)點a是是b的父的父節(jié)點節(jié)點當且僅當當且僅當a的生存期先于的生存期先于b的生存期時，的生存期時，a節(jié)點處于節(jié)點處于b結結點的左邊點的左邊一個結點代表一個唯一的活動，一個結點代表一個唯一的活動， 且每一個活動只有且每一個活動只有一個結點表示，當控制進入某一個活動時，可以直一個結點表示，當控制進入某一個活動時，可以直接說，控制在這個結點上。接說，控制在這個結點上。4/12/202211program sort(input, output);var a:array0.10 of integer;procedure

9、readarry;var i: integer;beginfor i:=1 to 9 do read(ai)end;function partition(y,z:integer):integer;var i,j,x,v : integer;begin end;procedure quicksort(m,n:integer)var i:integer;beginif(nm) then begini:=partition(m,n);quicksort(m,i-1);quicksort(i+1,n)endendbegina0 := -9999;a10:=9999;readarray;quicksor

10、t(1,9)endsrq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)q(2,3)p(2,3)q(2,1)q(3,3)q(5,9)4/12/202212控制?？刂茥３绦虻目刂屏鲗趶幕顒訕涓?jié)點開始的深度優(yōu)先遍歷。程序的控制流對應于從活動樹根節(jié)點開始的深度優(yōu)先遍歷。從左至右從左至右活動樹表示了完整的程序控制的先后順序。在真正運行過程中，活動活動樹表示了完整的程序控制的先后順序。在真正運行過程中，活動樹并不是真實存在的數(shù)據(jù)結構。樹并不是真實存在的數(shù)據(jù)結構。在程序運行過程中，我們只需要保存那些活潑著的過程。在程序運行過程中，我們只需要保存那些活潑著的過程?？刂茥？刂茥？刂茥５母舅枷?/p>

11、：控制棧的根本思想：當一個活動開始執(zhí)行時，把代表這個活動的結點推進棧；當這個活動結當一個活動開始執(zhí)行時，把代表這個活動的結點推進棧；當這個活動結束時，把代表這個活動的結點從棧中彈出。束時，把代表這個活動的結點從棧中彈出?？刂茥Ｖ荒鼙硎净顒訕涞囊痪植靠刂茥Ｖ荒鼙硎净顒訕涞囊痪植炕顒訕渲皇沁壿嬌洗嬖诘幕顒訕渲皇沁壿嬌洗嬖诘念愃朴谡Z法分析樹類似于語法分析樹4/12/202213棧和活動樹的變化棧和活動樹的變化ssrS rq(1,9)S q(1.9)p(1,9)S q(1.9) p(1,9)q(1,3)S q(1.9) q(1,3)p(1,3)S q(1.9) q(1,3) p(1,3)q(1,0)S

12、 q(1.9) q(1,3) q(1,0)q(2,3)S q(1.9) q(1,3) q(2,3)4/12/202214控制棧控制?？刂茥Ｖ械幕顒佣际腔顫姷?，當前控制進入的活動控制棧中的活動都是活潑的，當前控制進入的活動在棧頂，從棧頂活動到棧底活動的活動序列是從活在棧頂，從棧頂活動到棧底活動的活動序列是從活動樹上當前結點通向根的路徑上的結點序列。動樹上當前結點通向根的路徑上的結點序列。從棧底活動到棧頂活動的活動序列表示了活動的生從棧底活動到棧頂活動的活動序列表示了活動的生存期的嵌套關系。存期的嵌套關系。 結論：擴充控制?？捎脕韺崿F(xiàn)如結論：擴充控制棧可用來實現(xiàn)如Pascal語言的棧式語言的棧式存

13、儲分配。控制棧中存儲活動記錄存儲分配?？刂茥Ｖ写鎯顒佑涗?/12/202215聲明的作用域聲明的作用域聲明語句是把名字與名字的屬性信息綁定在一起的語法結構。聲明語句是把名字與名字的屬性信息綁定在一起的語法結構。說明的作用域是一個說明起作用的范圍說明的作用域是一個說明起作用的范圍(源程序行文源程序行文)。一個名字在源程序行文中可能有幾處說明，語言的作用域規(guī)那么規(guī)定了一個名字在源程序行文中可能有幾處說明，語言的作用域規(guī)那么規(guī)定了在語句序列中引用的一個名字是在何處說明的名字。在語句序列中引用的一個名字是在何處說明的名字。編譯時，處理說明時，把名字及其屬性信息填寫進符號表；處理編譯時，處理說明時，把

14、名字及其屬性信息填寫進符號表；處理引用時，查找這個名字的屬性信息，符號表管理程序根據(jù)語言的引用時，查找這個名字的屬性信息，符號表管理程序根據(jù)語言的作用域規(guī)那么，返回其作用域中綁定的屬性信息。作用域規(guī)那么，返回其作用域中綁定的屬性信息。4/12/202216名字與存儲的綁定名字與存儲的綁定名字與存儲單元的綁定是指把源程序中的名字與存儲單元的綁定是指把源程序中的映射到映射到的過程。的過程。把名字映射到一個存儲單元上；把名字映射到一個存儲單元上；把存儲單把存儲單元映射到那里所存放的值上。元映射到那里所存放的值上。或者說，環(huán)境把一個名字映射為一個左值，而狀態(tài)或者說，環(huán)境把一個名字映射為一個左值，而狀態(tài)

15、把一個左值映射為一個右值。把一個左值映射為一個右值。4/12/202217名字與存儲的綁定名字與存儲的綁定名字名字存儲單元存儲單元值值存儲分配存儲分配程序運行程序運行環(huán)境環(huán)境狀態(tài)狀態(tài)l-valuer-value4/12/202218靜態(tài)概念靜態(tài)概念 動態(tài)對應動態(tài)對應過程定義過程定義 過程活動過程活動名字說明名字說明 名字的綁定名字的綁定說明的作用域說明的作用域 活動的生存期活動的生存期4/12/202219存儲組織存儲組織運行時刻內(nèi)存的劃分：假定編譯器從操作系統(tǒng)得到運行時刻內(nèi)存的劃分：假定編譯器從操作系統(tǒng)得到一塊存儲區(qū)，運行時的存儲空間要劃分成塊一塊存儲區(qū)，運行時的存儲空間要劃分成塊:生成的目

16、標代碼生成的目標代碼;數(shù)據(jù)對象數(shù)據(jù)對象;記錄過程活動的控制棧對應的數(shù)據(jù)結構記錄過程活動的控制棧對應的數(shù)據(jù)結構4/12/202220目標代碼目標代碼靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)棧棧堆堆1. 編譯后知道目標代碼的大小。編譯后知道目標代碼的大小。放入放入靜態(tài)確定的區(qū)域中靜態(tài)確定的區(qū)域中2. 某些數(shù)據(jù)對象的長度也可以在編譯某些數(shù)據(jù)對象的長度也可以在編譯時知道，也可以放在靜態(tài)區(qū)域中。主時知道，也可以放在靜態(tài)區(qū)域中。主程序中的數(shù)據(jù)：程序中的數(shù)據(jù)：c,FORTRAN3. 棧?？刂茥＃嚎刂茥＃篜ascal,c4. 堆堆開銷比棧大開銷比棧大(分配和釋放方式分配和釋放方式)：Pascal,c4/12/202221活動記錄活動

17、記錄把過程的一個活動所需要的信息組織成一塊連續(xù)的把過程的一個活動所需要的信息組織成一塊連續(xù)的存儲單元，稱為活動記錄。存儲單元，稱為活動記錄。一個活動所需要的信息的每個數(shù)據(jù)項有相同的生存一個活動所需要的信息的每個數(shù)據(jù)項有相同的生存期，因此，組織成一個活動記錄是很自然的。期，因此，組織成一個活動記錄是很自然的。對于對于pascal語言來說，運行過程中，當調(diào)用一個過程語言來說，運行過程中，當調(diào)用一個過程時，在棧頂構筑它的活動記錄；當這個過程的活動時，在棧頂構筑它的活動記錄；當這個過程的活動執(zhí)行完后，把它從棧頂彈出。執(zhí)行完后，把它從棧頂彈出。4/12/202222活動記錄活動記錄控制鏈控制鏈:指向調(diào)用

18、過程活動的活動記指向調(diào)用過程活動的活動記錄。錄。訪問鏈：指向本活動要訪問的非局部數(shù)訪問鏈：指向本活動要訪問的非局部數(shù)據(jù)所在的活動記錄。據(jù)所在的活動記錄。保存機器狀態(tài)：調(diào)用過程活動在調(diào)用點保存機器狀態(tài)：調(diào)用過程活動在調(diào)用點的機器狀態(tài)，包括計數(shù)器，各種存放器的機器狀態(tài)，包括計數(shù)器，各種存放器的值。的值。局部數(shù)據(jù)：過程中定義的局部量。局部數(shù)據(jù)：過程中定義的局部量。臨時變量：編譯產(chǎn)生。臨時變量：編譯產(chǎn)生。返回值返回值實在參數(shù)實在參數(shù)控制鏈控制鏈訪問鏈訪問鏈保存機器狀態(tài)保存機器狀態(tài)局部數(shù)據(jù)局部數(shù)據(jù)臨時變量臨時變量4/12/202223編譯時刻的局部數(shù)據(jù)的設計編譯時刻的局部數(shù)據(jù)的設計PROCEDURE s

19、ub(x,y:real); VAR i ,j:integer; a:ARRAY1.5 OF real; e, f : real; BEGINf :=e+i*j; END;名字名字 形形 類型類型 偏移量偏移量 x 形形 real 1 y 形形 real 2 i int 20 j int 21 a array 22 e real 27 f real 28符號表符號表4/12/202224中間代碼中間代碼編譯結束，知道每個過程的活動記錄的長度，將其編譯結束，知道每個過程的活動記錄的長度，將其填寫到相應的過程表中，運行時，調(diào)用哪個過程，填寫到相應的過程表中，運行時，調(diào)用哪個過程，就在運行棧頂，推進那

20、個過程的活動記錄棧箭頭就在運行棧頂，推進那個過程的活動記錄棧箭頭加上活動記錄長度。加上活動記錄長度。f :=e+i*j;*ijt1+et1t2:= t2f4/12/202225運行時刻存儲分配策略運行時刻存儲分配策略分配策略是：分配策略是：靜態(tài)分配；靜態(tài)分配；棧式分配，或稱棧式動態(tài)分配；棧式分配，或稱棧式動態(tài)分配；堆式分配，或稱堆式動態(tài)分配。堆式分配，或稱堆式動態(tài)分配。 采用哪種分配策略是由源語言的語義決定的。采用哪種分配策略是由源語言的語義決定的。4/12/202226靜態(tài)存儲分配靜態(tài)存儲分配靜態(tài)存儲分配：在靜態(tài)存儲分配：在由由實現(xiàn)對存儲實現(xiàn)對存儲空間的管理和為源程序中的變量分配存儲的方法。

21、空間的管理和為源程序中的變量分配存儲的方法。靜態(tài)存儲分配的條件靜態(tài)存儲分配的條件如果在編譯時能夠確定源程序中變量在運行時的數(shù)據(jù)如果在編譯時能夠確定源程序中變量在運行時的數(shù)據(jù)空間大小，且運行時不改變，那么就可以采用靜態(tài)存空間大小，且運行時不改變，那么就可以采用靜態(tài)存儲分配方法。儲分配方法。允許局部名字的值在過程停止活動后仍然保持，也允許局部名字的值在過程停止活動后仍然保持，也就是當控制再次進入程序時，局部名字的值同控制就是當控制再次進入程序時，局部名字的值同控制上次離開時一樣。上次離開時一樣。還能用控制棧進行還能用控制棧進行控制嗎？控制嗎？4/12/202227靜態(tài)存儲分配的局限靜態(tài)存儲分配的局

22、限在編譯時刻知道數(shù)據(jù)目標的大小和它們在內(nèi)存位置在編譯時刻知道數(shù)據(jù)目標的大小和它們在內(nèi)存位置上的約束；上的約束；不能遞歸調(diào)用過程一個過程的兩個活動的生存期不能遞歸調(diào)用過程一個過程的兩個活動的生存期不相交不相交,一個過程的所有活動可以使用同一個活動記一個過程的所有活動可以使用同一個活動記錄；錄；不能動態(tài)地建立數(shù)據(jù)結構。不能動態(tài)地建立數(shù)據(jù)結構。4/12/202228靜態(tài)存儲分配策略靜態(tài)存儲分配策略CNSUME目標代碼目標代碼PRDUCE目標代碼目標代碼Char *50 buf int next char cChar *80 buffer int nextCnsume活動記錄活動記錄prduce活動記錄活動記錄目標代碼目標代碼靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)4/12/202229靜態(tài)存儲分配策略靜態(tài)存儲分配策略由于每個變量所需空間的大小在編譯時，因此可以由于每個變量所需空間的大小在編譯時，因此可以用簡單的方法給變量分配目標地址。用簡單的方法給變量分配目標地址。開辟一數(shù)據(jù)區(qū)。首地址在加載時定開辟一數(shù)據(jù)區(qū)。首地址在