運(yùn)行時的存儲組織及管理

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

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

3、的提出：如何問題的提出：如何構(gòu)造運(yùn)行程序的策略和方法構(gòu)造運(yùn)行程序的策略和方法過程過程活動樹活動樹控制?？刂茥Ｕf明的作用域說明的作用域名字的綁定名字的綁定構(gòu)造運(yùn)行程序和源程序有關(guān)的一些問題構(gòu)造運(yùn)行程序和源程序有關(guān)的一些問題4/12/20226過程過程源程序由一組過程組成，不同的程序設(shè)計語言，由源程序由一組過程組成，不同的程序設(shè)計語言，由過程構(gòu)成源程序的方法不同。過程構(gòu)成源程序的方法不同。構(gòu)成源程序的兩個過程行文，要么是嵌套的，要么構(gòu)成源程序的兩個過程行文，要么是嵌套的，要么是不相交的。是不相交的。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ù)的：在任何一步，控制都處于程序的某一點(diǎn)程序執(zhí)行的控制是連續(xù)的：在任何一步，控制都處于程序的某一點(diǎn)過程的每一次執(zhí)行都是從過程體的開頭過程的每一次執(zhí)行都是從過程體的開頭 開始，并最終把控制返回到緊接開始，并最終把控制返回到緊接著該過程被調(diào)用點(diǎn)的后面。著該過程被調(diào)用點(diǎn)的后面。過程的一次活動過程的一次活動: 過程體的每一次執(zhí)行。過程體的每一次執(zhí)行。過程過程p的一次活動的的一次活動的:在該過程體的執(zhí)行中的第一步和最后一步之在該過程體的執(zhí)行中

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

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

8、表主程序的活動當(dāng)且僅當(dāng)控制流從活動當(dāng)且僅當(dāng)控制流從活動a進(jìn)入活動進(jìn)入活動b時，節(jié)點(diǎn)時，節(jié)點(diǎn)a是是b的父的父節(jié)點(diǎn)節(jié)點(diǎn)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)a的生存期先于的生存期先于b的生存期時，的生存期時，a節(jié)點(diǎn)處于節(jié)點(diǎn)處于b結(jié)結(jié)點(diǎn)的左邊點(diǎn)的左邊一個結(jié)點(diǎn)代表一個唯一的活動，一個結(jié)點(diǎn)代表一個唯一的活動， 且每一個活動只有且每一個活動只有一個結(jié)點(diǎn)表示，當(dāng)控制進(jìn)入某一個活動時，可以直一個結(jié)點(diǎn)表示，當(dāng)控制進(jìn)入某一個活動時，可以直接說，控制在這個結(jié)點(diǎn)上。接說，控制在這個結(jié)點(diǎn)上。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控制?？刂茥３绦虻目刂屏鲗?yīng)于從活動樹根節(jié)點(diǎn)開始的深度優(yōu)先遍歷。程序的控制流對應(yīng)于從活動樹根節(jié)點(diǎn)開始的深度優(yōu)先遍歷。從左至右從左至右活動樹表示了完整的程序控制的先后順序。在真正運(yùn)行過程中，活動活動樹表示了完整的程序控制的先后順序。在真正運(yùn)行過程中，活動樹并不是真實存在的數(shù)據(jù)結(jié)構(gòu)。樹并不是真實存在的數(shù)據(jù)結(jié)構(gòu)。在程序運(yùn)行過程中，我們只需要保存那些活潑著的過程。在程序運(yùn)行過程中，我們只需要保存那些活潑著的過程。控制?？刂茥？刂茥５母舅枷?/p>

11、：控制棧的根本思想：當(dāng)一個活動開始執(zhí)行時，把代表這個活動的結(jié)點(diǎn)推進(jìn)棧；當(dāng)這個活動結(jié)當(dāng)一個活動開始執(zhí)行時，把代表這個活動的結(jié)點(diǎn)推進(jìn)棧；當(dāng)這個活動結(jié)束時，把代表這個活動的結(jié)點(diǎn)從棧中彈出。束時，把代表這個活動的結(jié)點(diǎn)從棧中彈出?？刂茥Ｖ荒鼙硎净顒訕涞囊痪植靠刂茥Ｖ荒鼙硎净顒訕涞囊痪植炕顒訕渲皇沁壿嬌洗嬖诘幕顒訕渲皇沁壿嬌洗嬖诘念愃朴谡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控制?？刂茥？刂茥Ｖ械幕顒佣际腔顫姷?，當(dāng)前控制進(jìn)入的活動控制棧中的活動都是活潑的，當(dāng)前控制進(jìn)入的活動在棧頂，從棧頂活動到棧底活動的活動序列是從活在棧頂，從棧頂活動到棧底活動的活動序列是從活動樹上當(dāng)前結(jié)點(diǎn)通向根的路徑上的結(jié)點(diǎn)序列。動樹上當(dāng)前結(jié)點(diǎn)通向根的路徑上的結(jié)點(diǎn)序列。從棧底活動到棧頂活動的活動序列表示了活動的生從棧底活動到棧頂活動的活動序列表示了活動的生存期的嵌套關(guān)系。存期的嵌套關(guān)系。 結(jié)論：擴(kuò)充控制?？捎脕韺崿F(xiàn)如結(jié)論：擴(kuò)充控制棧可用來實現(xiàn)如Pascal語言的棧式語言的棧式存

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

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

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

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

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

18、過程活動的活動記指向調(diào)用過程活動的活動記錄。錄。訪問鏈：指向本活動要訪問的非局部數(shù)訪問鏈：指向本活動要訪問的非局部數(shù)據(jù)所在的活動記錄。據(jù)所在的活動記錄。保存機(jī)器狀態(tài)：調(diào)用過程活動在調(diào)用點(diǎn)保存機(jī)器狀態(tài)：調(diào)用過程活動在調(diào)用點(diǎn)的機(jī)器狀態(tài)，包括計數(shù)器，各種存放器的機(jī)器狀態(tài)，包括計數(shù)器，各種存放器的值。的值。局部數(shù)據(jù)：過程中定義的局部量。局部數(shù)據(jù)：過程中定義的局部量。臨時變量：編譯產(chǎn)生。臨時變量：編譯產(chǎn)生。返回值返回值實在參數(shù)實在參數(shù)控制鏈控制鏈訪問鏈訪問鏈保存機(jī)器狀態(tài)保存機(jī)器狀態(tài)局部數(shù)據(jù)局部數(shù)據(jù)臨時變量臨時變量4/12/202223編譯時刻的局部數(shù)據(jù)的設(shè)計編譯時刻的局部數(shù)據(jù)的設(shè)計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中間代碼中間代碼編譯結(jié)束，知道每個過程的活動記錄的長度，將其編譯結(jié)束，知道每個過程的活動記錄的長度，將其填寫到相應(yīng)的過程表中，運(yùn)行時，調(diào)用哪個過程，填寫到相應(yīng)的過程表中，運(yùn)行時，調(diào)用哪個過程，就在運(yùn)行棧頂，推進(jìn)那

20、個過程的活動記錄棧箭頭就在運(yùn)行棧頂，推進(jìn)那個過程的活動記錄棧箭頭加上活動記錄長度。加上活動記錄長度。f :=e+i*j;*ijt1+et1t2:= t2f4/12/202225運(yùn)行時刻存儲分配策略運(yùn)行時刻存儲分配策略分配策略是：分配策略是：靜態(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)存儲分配的條件如果在編譯時能夠確定源程序中變量在運(yùn)行時的數(shù)據(jù)如果在編譯時能夠確定源程序中變量在運(yùn)行時的數(shù)據(jù)空間大小，且運(yùn)行時不改變，那么就可以采用靜態(tài)存空間大小，且運(yùn)行時不改變，那么就可以采用靜態(tài)存儲分配方法。儲分配方法。允許局部名字的值在過程停止活動后仍然保持，也允許局部名字的值在過程停止活動后仍然保持，也就是當(dāng)控制再次進(jìn)入程序時，局部名字的值同控制就是當(dāng)控制再次進(jìn)入程序時，局部名字的值同控制上次離開時一樣。上次離開時一樣。還能用控制棧進(jìn)行還能用控制棧進(jìn)行控制嗎？控制嗎？4/12/202227靜態(tài)存儲分配的局限靜態(tài)存儲分配的局

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