1、運行時的存儲組織及管理運行時的存儲組織及管理11/4/20212004年12月28日1編譯器的應(yīng)用模型編譯器的應(yīng)用模型出出錯錯處處理理語法分析程序語法分析程序語義分析程序語義分析程序目標(biāo)代碼生成程序目標(biāo)代碼生成程序詞法分析程序詞法分析程序中間代碼生成程序中間代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序表表格格管管理理編譯的前端編譯的前端（Front End）編譯的后端編譯的后端（Back End）11/4/20212編譯原理編譯原理運行時的存儲組織及管理運行時的存儲組織及管理概述概述存儲組織存儲組織運行時的存儲分配策略運行時的存儲分配策略靜態(tài)存儲分配靜態(tài)存儲分配動態(tài)存儲分配動態(tài)存儲分配對非局部名字的訪

2、問對非局部名字的訪問參數(shù)傳遞參數(shù)傳遞11/4/20213編譯原理編譯原理運行時的存儲組織及管理運行時的存儲組織及管理 計算環(huán)境 運行時的環(huán)境 計算 目標(biāo)代碼當(dāng)詞法分析掃描得到標(biāo)識符，并將它填入符號表的當(dāng)詞法分析掃描得到標(biāo)識符，并將它填入符號表的過程中需要給識別出來的標(biāo)識符分配內(nèi)存空間。過程中需要給識別出來的標(biāo)識符分配內(nèi)存空間。源程序由一組源程序由一組按某種規(guī)則組成。按某種規(guī)則組成。過程的一次執(zhí)行稱作一次過程的一次執(zhí)行稱作一次。在過程的語句序列執(zhí)行之前，過程中訪問的對象構(gòu)在過程的語句序列執(zhí)行之前，過程中訪問的對象構(gòu)成此過程的運行環(huán)境，由運行支持程序組織好。成此過程的運行環(huán)境，由運行支持程序組織好

3、。編譯程序根據(jù)如何組織運行環(huán)境而生成目標(biāo)代碼。編譯程序根據(jù)如何組織運行環(huán)境而生成目標(biāo)代碼。映射源程序11/4/20214編譯原理編譯原理運行時環(huán)境的作用運行時環(huán)境的作用目標(biāo)程序運行時所需存儲空間的組織與管理以及源目標(biāo)程序運行時所需存儲空間的組織與管理以及源程序中變量存儲空間的分配。程序中變量存儲空間的分配。11/4/20215編譯原理編譯原理有關(guān)源程序中的一些問題有關(guān)源程序中的一些問題問題的提出：如何問題的提出：如何構(gòu)造運行程序的策略和方法構(gòu)造運行程序的策略和方法過程過程活動樹活動樹控制棧控制棧說明的作用域說明的作用域名字的綁定名字的綁定構(gòu)造運行程序和源程序有關(guān)的一些問題構(gòu)造運行程序和源程序有

4、關(guān)的一些問題11/4/20216編譯原理編譯原理過程過程源程序由一組過程組成，不同的程序設(shè)計語言，由源程序由一組過程組成，不同的程序設(shè)計語言，由過程構(gòu)成源程序的方法不同。過程構(gòu)成源程序的方法不同。構(gòu)成源程序的兩個過程行文，要么是嵌套的，要么構(gòu)成源程序的兩個過程行文，要么是嵌套的，要么是不相交的。是不相交的。11/4/20217編譯原理編譯原理program sort(input, output);var a:array0.10 of integer;procedure readarry;var i: integer;beginfor i:=1 to 9 do read(ai)end;funct

5、ion 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;quicksort(1,9)end11/4/20218編譯原理編譯原理活動樹活動樹程序執(zhí)行期間的控制流：程序執(zhí)行期間的控制流： 程序執(zhí)行的控制

6、是連續(xù)的：在任何一步，控制都處于程序的某程序執(zhí)行的控制是連續(xù)的：在任何一步，控制都處于程序的某一點一點過程的每一次執(zhí)行都是從過程體的開頭過程的每一次執(zhí)行都是從過程體的開頭 開始，并最終把控制返開始，并最終把控制返回到緊接著該過程被調(diào)用點的后面。回到緊接著該過程被調(diào)用點的后面。過程的一次活動過程的一次活動: 過程體的每一次執(zhí)行。過程體的每一次執(zhí)行。過程過程p的一次活動的的一次活動的:在該過程體的執(zhí)行中的第一步和在該過程體的執(zhí)行中的第一步和最后一步之間的一序列步驟的最后一步之間的一序列步驟的，其中包括執(zhí)行過程，其中包括執(zhí)行過程p所調(diào)用的過程的執(zhí)行時間，以及這些過程所調(diào)用的過程的所調(diào)用的過程的執(zhí)行時

7、間，以及這些過程所調(diào)用的過程的，如此等等。，如此等等。一個過程是遞歸的，如果同一過程的一次新的活動可以在前一個過程是遞歸的，如果同一過程的一次新的活動可以在前面活動結(jié)束以前開始。面活動結(jié)束以前開始。11/4/20219編譯原理編譯原理活動樹活動樹為什么過程的活動可以用樹形結(jié)構(gòu)描述？為什么過程的活動可以用樹形結(jié)構(gòu)描述？過程活動的特點：過程活動的特點：每當(dāng)控制流從過程每當(dāng)控制流從過程p的活動進入到過程的活動進入到過程q的活動中后，的活動中后，它將返回到過程它將返回到過程p的同一次活動中。的同一次活動中。也就是說，如果也就是說，如果a和和b是兩個過程活動，那么它們的生是兩個過程活動，那么它們的生存期

8、要么是不重疊的，要么是嵌套的。存期要么是不重疊的，要么是嵌套的。在樹形結(jié)構(gòu)中，節(jié)點間的關(guān)系就反映了過程之間的在樹形結(jié)構(gòu)中，節(jié)點間的關(guān)系就反映了過程之間的關(guān)系：關(guān)系：父子關(guān)系：嵌套父子關(guān)系：嵌套兄弟關(guān)系：先后兄弟關(guān)系：先后11/4/202110編譯原理編譯原理活動樹活動樹用一顆樹來描繪控制進入和離開活動的途徑。這祥用一顆樹來描繪控制進入和離開活動的途徑。這祥的樹稱作活動樹。的樹稱作活動樹。每個節(jié)點代表過程的一個活動每個節(jié)點代表過程的一個活動根節(jié)點代表主程序的活動根節(jié)點代表主程序的活動當(dāng)且僅當(dāng)控制流從活動當(dāng)且僅當(dāng)控制流從活動a進入活動進入活動b時，節(jié)點時，節(jié)點a是是b的父的父節(jié)點節(jié)點當(dāng)且僅當(dāng)當(dāng)且僅

9、當(dāng)a的生存期先于的生存期先于b的生存期時，的生存期時，a節(jié)點處于節(jié)點處于b結(jié)結(jié)點的左邊點的左邊一個結(jié)點代表一個唯一的活動，一個結(jié)點代表一個唯一的活動， 且每一個活動只有且每一個活動只有一個結(jié)點表示，當(dāng)控制進入某一個活動時，可以直一個結(jié)點表示，當(dāng)控制進入某一個活動時，可以直接說，控制在這個結(jié)點上。接說，控制在這個結(jié)點上。11/4/202111編譯原理編譯原理program sort(input, output);var a:array0.10 of integer;procedure readarry;var i: integer;beginfor i:=1 to 9 do read(ai)en

10、d;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;quicksort(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

11、,1)q(3,3)q(5,9)11/4/202112編譯原理編譯原理控制棧控制棧程序的控制流對應(yīng)于從活動樹根節(jié)點開始的深度優(yōu)先遍歷。程序的控制流對應(yīng)于從活動樹根節(jié)點開始的深度優(yōu)先遍歷。（從左至右）（從左至右）活動樹表示了完整的程序控制的先后順序。在真正運行過程活動樹表示了完整的程序控制的先后順序。在真正運行過程中，活動樹并不是真實存在的數(shù)據(jù)結(jié)構(gòu)。中，活動樹并不是真實存在的數(shù)據(jù)結(jié)構(gòu)。在程序運行過程中，我們只需要保存那些在程序運行過程中，我們只需要保存那些。控制棧控制棧控制棧的基本思想：控制棧的基本思想：當(dāng)一個活動開始執(zhí)行時，把代表這個活動的結(jié)點推進棧；當(dāng)這當(dāng)一個活動開始執(zhí)行時，把代表這個活動的結(jié)

12、點推進棧；當(dāng)這個活動結(jié)束時，把代表這個活動的結(jié)點從棧中彈出。個活動結(jié)束時，把代表這個活動的結(jié)點從棧中彈出。控制棧只能表示活動樹的一部分控制棧只能表示活動樹的一部分活動樹只是邏輯上存在活動樹只是邏輯上存在的的類似于語法分析樹類似于語法分析樹11/4/202113編譯原理編譯原理棧和活動樹的變化棧和活動樹的變化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 q(1.9) q(1,3) q(1,0)q(2,3)S q(1.9) q(1,3) q(2,3)

13、11/4/202114編譯原理編譯原理控制棧控制棧控制棧中的活動都是活躍的，當(dāng)前控制進入的活動控制棧中的活動都是活躍的，當(dāng)前控制進入的活動在棧頂，從棧頂活動到棧底活動的活動序列是從活在棧頂，從棧頂活動到棧底活動的活動序列是從活動樹上當(dāng)前結(jié)點通向根的路徑上的結(jié)點序列。動樹上當(dāng)前結(jié)點通向根的路徑上的結(jié)點序列。從棧底活動到棧頂活動的活動序列表示了活動的生從棧底活動到棧頂活動的活動序列表示了活動的生存期的存期的 結(jié)論：擴充控制棧可用來實現(xiàn)如結(jié)論：擴充控制棧可用來實現(xiàn)如Pascal語言的棧式語言的棧式存儲分配。（控制棧中存儲活動記錄）存儲分配。（控制棧中存儲活動記錄）11/4/202115編譯原理編譯原

14、理聲明的作用域聲明的作用域聲明語句是把名字與名字的屬性信息綁定在一起的語法結(jié)聲明語句是把名字與名字的屬性信息綁定在一起的語法結(jié)構(gòu)。構(gòu)。說明的作用域是一個說明起作用的范圍說明的作用域是一個說明起作用的范圍(源程序行文源程序行文)。一個名字在源程序行文中可能有幾處說明，語言的一個名字在源程序行文中可能有幾處說明，語言的規(guī)定了在語句序列中引用的一個名字是在何處說明的名規(guī)定了在語句序列中引用的一個名字是在何處說明的名字。字。編譯時，處理說明時，把名字及其屬性信息填寫進符號表；編譯時，處理說明時，把名字及其屬性信息填寫進符號表；處理引用時，查找這個名字的屬性信息，符號表管理程序根處理引用時，查找這個名字

15、的屬性信息，符號表管理程序根據(jù)語言的作用域規(guī)則，返回其作用域中綁定的屬性信息。據(jù)語言的作用域規(guī)則，返回其作用域中綁定的屬性信息。11/4/202116編譯原理編譯原理名字與存儲的綁定名字與存儲的綁定名字與存儲單元的綁定是指把源程序中的名字與存儲單元的綁定是指把源程序中的映射到映射到的過程。的過程。把名字映射到一個存儲單元上；把名字映射到一個存儲單元上；把存儲單把存儲單元映射到那里所存放的值上。元映射到那里所存放的值上。或者說，環(huán)境把一個名字映射為一個左值，而狀態(tài)或者說，環(huán)境把一個名字映射為一個左值，而狀態(tài)把一個左值映射為一個右值。把一個左值映射為一個右值。11/4/202117編譯原理編譯原理

16、名字與存儲的綁定名字與存儲的綁定名字名字存儲單元存儲單元值值存儲分配存儲分配程序運行程序運行環(huán)境環(huán)境狀態(tài)狀態(tài)l-valuer-value11/4/202118編譯原理編譯原理靜態(tài)概念靜態(tài)概念 動態(tài)對應(yīng)動態(tài)對應(yīng)過程定義過程定義 過程活動過程活動名字說明名字說明 名字的綁定名字的綁定說明的作用域說明的作用域 活動的生存期活動的生存期11/4/202119編譯原理編譯原理存儲組織存儲組織運行時刻內(nèi)存的劃分：假定編譯器從操作系統(tǒng)得到運行時刻內(nèi)存的劃分：假定編譯器從操作系統(tǒng)得到一塊存儲區(qū)，運行時的存儲空間要劃分成塊一塊存儲區(qū)，運行時的存儲空間要劃分成塊:生成的目標(biāo)代碼生成的目標(biāo)代碼;數(shù)據(jù)對象數(shù)據(jù)對象;記

17、錄過程活動的控制棧對應(yīng)的數(shù)據(jù)結(jié)構(gòu)記錄過程活動的控制棧對應(yīng)的數(shù)據(jù)結(jié)構(gòu)11/4/202120編譯原理編譯原理目標(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,c11/4/202121編譯原理編譯原理活動記錄活動記錄把過程

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

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

20、PROCEDURE sub(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符號表符號表11/4/202124編譯原理編譯原理中間代碼中間代碼編譯結(jié)束，知道每個過程的活動記錄的長度，將其編譯結(jié)束，知道每個過程的活動記錄的長度，將其填寫到相應(yīng)的過程表中，運行時，調(diào)用哪個過程，填寫到相應(yīng)的過程表中，運行

21、時，調(diào)用哪個過程，就在運行棧頂，推進那個過程的活動記錄（棧箭頭就在運行棧頂，推進那個過程的活動記錄（棧箭頭加上活動記錄長度）。加上活動記錄長度）。f :=e+i*j;*ijt1+et1t2:=t2f11/4/202125編譯原理編譯原理運行時刻存儲分配策略運行時刻存儲分配策略分配策略是：分配策略是：靜態(tài)分配；靜態(tài)分配；棧式分配，或稱棧式動態(tài)分配；棧式分配，或稱棧式動態(tài)分配；堆式分配，或稱堆式動態(tài)分配。堆式分配，或稱堆式動態(tài)分配。 采用哪種分配策略是由源語言的語義決定的。采用哪種分配策略是由源語言的語義決定的。11/4/202126編譯原理編譯原理靜態(tài)存儲分配靜態(tài)存儲分配靜態(tài)存儲分配：在靜態(tài)存儲

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

23、行控制嗎？行控制嗎？11/4/202127編譯原理編譯原理靜態(tài)存儲分配的局限靜態(tài)存儲分配的局限在編譯時刻知道數(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)。11/4/202128編譯原理編譯原理靜態(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ù)11/4/202129編譯原理編譯原理靜態(tài)存儲分配策略靜態(tài)存儲分配策略由于每個變量所需空間的大小在編譯時已知，因此由于每個變量所需空間的大小在編譯時已知，因此可以用簡單的方法給變量分配目標(biāo)地址。可以用簡單的方法給變量分配目標(biāo)地址。開辟一數(shù)據(jù)區(qū)。（首地址在加載時定）開辟一數(shù)據(jù)區(qū)。（首地址在加載時定）按編譯順序給每個模塊分配存儲空間。按編