運(yùn)行時(shí)的存儲(chǔ)組織及管理ppt課件

1、運(yùn)轉(zhuǎn)時(shí)的存儲(chǔ)組織及管理編譯器的運(yùn)用模型出錯(cuò)處理語(yǔ)法分析程序語(yǔ)義分析程序目的代碼生成程序詞法分析程序中間代碼生成程序代碼優(yōu)化程序表格管理編譯的前端Front End編譯的后端Back End運(yùn)轉(zhuǎn)時(shí)的存儲(chǔ)組織及管理概述存儲(chǔ)組織運(yùn)轉(zhuǎn)時(shí)的存儲(chǔ)分配戰(zhàn)略靜態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配對(duì)非部分名字的訪問參數(shù)傳送運(yùn)轉(zhuǎn)時(shí)的存儲(chǔ)組織及管理 計(jì)算環(huán)境 運(yùn)轉(zhuǎn)時(shí)的環(huán)境 計(jì)算 目的代碼當(dāng)詞法分析掃描得到標(biāo)識(shí)符，并將它填入符號(hào)表的過程中需求給識(shí)別出來的標(biāo)識(shí)符分配內(nèi)存空間。源程序由一組過程按某種規(guī)那么組成。過程的一次執(zhí)行稱作一次活動(dòng)。在過程的語(yǔ)句序列執(zhí)行之前，過程中訪問的對(duì)象構(gòu)成此過程的運(yùn)轉(zhuǎn)環(huán)境，由運(yùn)轉(zhuǎn)支持程序組織好。編譯程序根據(jù)

2、如何組織運(yùn)轉(zhuǎn)環(huán)境而生成目的代碼。映射源程序運(yùn)轉(zhuǎn)時(shí)環(huán)境的作用目的程序運(yùn)轉(zhuǎn)時(shí)所需存儲(chǔ)空間的組織與管理以及源程序中變量存儲(chǔ)空間的分配。有關(guān)源程序中的一些問題問題的提出：如何構(gòu)造運(yùn)轉(zhuǎn)程序的戰(zhàn)略和方法過程活動(dòng)樹控制棧闡明的作用域名字的綁定構(gòu)造運(yùn)轉(zhuǎn)程序和源程序有關(guān)的一些問題過程源程序由一組過程組成，不同的程序設(shè)計(jì)言語(yǔ)，由過程構(gòu)成源程序的方法不同。構(gòu)成源程序的兩個(gè)過程行文，要么是嵌套的，要么是不相交的。program sort(input, output);var a:array0.10 of integer;procedure readarry;var i: integer;beginfor i:=1 t

3、o 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;quicksort(1,9)end活動(dòng)樹程序執(zhí)行期間的控制流： 程序執(zhí)行的控制是延續(xù)的：在任何

4、一步，控制都處于程序的某一點(diǎn)過程的每一次執(zhí)行都是從過程體的開頭 開場(chǎng)，并最終把控制前往到緊接著該過程被調(diào)用點(diǎn)的后面。過程的一次活動(dòng): 過程體的每一次執(zhí)行。過程p的一次活動(dòng)的生存期:在該過程體的執(zhí)行中的第一步和最后一步之間的一序列步驟的執(zhí)行時(shí)間，其中包括執(zhí)行過程p所調(diào)用的過程的執(zhí)行時(shí)間，以及這些過程所調(diào)用的過程的執(zhí)行時(shí)間，如此等等。一個(gè)過程是遞歸的，假好像一過程的一次新的活動(dòng)可以在前面活動(dòng)終了以前開場(chǎng)?；顒?dòng)樹為什么過程的活動(dòng)可以用樹形構(gòu)造描畫？過程活動(dòng)的特點(diǎn)：每當(dāng)控制流從過程p的活動(dòng)進(jìn)入到過程q的活動(dòng)中后，它將前往到過程p的同一次活動(dòng)中。也就是說，假設(shè)a和b是兩個(gè)過程活動(dòng)，那么它們的生存期要么是

5、不重疊的，要么是嵌套的。在樹形構(gòu)造中，節(jié)點(diǎn)間的關(guān)系就反映了過程之間的關(guān)系：父子關(guān)系：嵌套兄弟關(guān)系：先后活動(dòng)樹用一顆樹來描畫控制進(jìn)入和分開活動(dòng)的途徑。這祥的樹稱作活動(dòng)樹。每個(gè)節(jié)點(diǎn)代表過程的一個(gè)活動(dòng)根節(jié)點(diǎn)代表主程序的活動(dòng)當(dāng)且僅當(dāng)控制流從活動(dòng)a進(jìn)入活動(dòng)b時(shí)，節(jié)點(diǎn)a是b的父節(jié)點(diǎn)當(dāng)且僅當(dāng)a的生存期先于b的生存期時(shí)，a節(jié)點(diǎn)處于b結(jié)點(diǎn)的左邊一個(gè)結(jié)點(diǎn)代表一個(gè)獨(dú)一的活動(dòng)， 且每一個(gè)活動(dòng)只需一個(gè)結(jié)點(diǎn)表示，當(dāng)控制進(jìn)入某一個(gè)活動(dòng)時(shí)，可以直接說，控制在這個(gè)結(jié)點(diǎn)上。program sort(input, output);var a:array0.10 of integer;procedure readarry;var i

6、: 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;quicksort(1,9)endsrq(1

7、,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)控制棧程序的控制流對(duì)應(yīng)于從活動(dòng)樹根節(jié)點(diǎn)開場(chǎng)的深度優(yōu)先遍歷。從左至右活動(dòng)樹表示了完好的程序控制的先后順序。在真正運(yùn)轉(zhuǎn)過程中，活動(dòng)樹并不是真實(shí)存在的數(shù)據(jù)構(gòu)造。在程序運(yùn)轉(zhuǎn)過程中，我們只需求保管那些活潑著的過程。控制?？刂茥５母舅枷耄寒?dāng)一個(gè)活動(dòng)開場(chǎng)執(zhí)行時(shí)，把代表這個(gè)活動(dòng)的結(jié)點(diǎn)推進(jìn)棧；當(dāng)這個(gè)活動(dòng)終了時(shí)，把代表這個(gè)活動(dòng)的結(jié)點(diǎn)從棧中彈出。控制棧只能表示活動(dòng)樹的一部分活動(dòng)樹只是邏輯上存在的類似于語(yǔ)法分析樹棧和活動(dòng)樹的變化ssrS rq(1,9)S q(1.9)p(1,9)S q(1.9) p(1

8、,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)控制?？刂茥Ｖ械幕顒?dòng)都是活潑的，當(dāng)前控制進(jìn)入的活動(dòng)在棧頂，從棧頂活動(dòng)到棧底活動(dòng)的活動(dòng)序列是從活動(dòng)樹上當(dāng)前結(jié)點(diǎn)通向根的途徑上的結(jié)點(diǎn)序列。從棧底活動(dòng)到棧頂活動(dòng)的活動(dòng)序列表示了活動(dòng)的生存期的嵌套關(guān)系。 結(jié)論：擴(kuò)展控制?？捎脕韺?shí)現(xiàn)如Pascal言語(yǔ)的棧式存儲(chǔ)分配?？刂茥Ｖ写鎯?chǔ)活動(dòng)記錄聲明的作用域聲明語(yǔ)句是把名字與名字的屬性信息綁定在一同的語(yǔ)法構(gòu)造。闡明的作用域是一個(gè)闡明起作用的范圍(源程序

9、行文)。一個(gè)名字在源程序行文中能夠有幾處闡明，言語(yǔ)的作用域規(guī)那么規(guī)定了在語(yǔ)句序列中援用的一個(gè)名字是在何處闡明的名字。編譯時(shí)，處置闡明時(shí)，把名字及其屬性信息填寫進(jìn)符號(hào)表；處置援用時(shí)，查找這個(gè)名字的屬性信息，符號(hào)表管理程序根據(jù)言語(yǔ)的作用域規(guī)那么，前往其作用域中綁定的屬性信息。名字與存儲(chǔ)的綁定名字與存儲(chǔ)單元的綁定是指把源程序中的數(shù)據(jù)名字映射到目的機(jī)存儲(chǔ)單元的過程。環(huán)境把名字映射到一個(gè)存儲(chǔ)單元上；形狀把存儲(chǔ)單元映射到那里所存放的值上?；蛘哒f，環(huán)境把一個(gè)名字映射為一個(gè)左值，而形狀把一個(gè)左值映射為一個(gè)右值。名字與存儲(chǔ)的綁定名字存儲(chǔ)單元值存儲(chǔ)分配程序運(yùn)轉(zhuǎn)環(huán)境形狀l-valuer-value靜態(tài)概念 動(dòng)態(tài)對(duì)應(yīng)

10、過程定義 過程活動(dòng)名字闡明 名字的綁定闡明的作用域 活動(dòng)的生存期存儲(chǔ)組織運(yùn)轉(zhuǎn)時(shí)辰內(nèi)存的劃分：假定編譯器從操作系統(tǒng)得到一塊存儲(chǔ)區(qū)，運(yùn)轉(zhuǎn)時(shí)的存儲(chǔ)空間要?jiǎng)澐殖蓧K:生成的目的代碼;數(shù)據(jù)對(duì)象;記錄過程活動(dòng)的控制棧對(duì)應(yīng)的數(shù)據(jù)構(gòu)造目的代碼靜態(tài)數(shù)據(jù)棧堆1. 編譯后知道目的代碼的大小。放入靜態(tài)確定的區(qū)域中2. 某些數(shù)據(jù)對(duì)象的長(zhǎng)度也可以在編譯時(shí)知道，也可以放在靜態(tài)區(qū)域中。主程序中的數(shù)據(jù)：c,FORTRAN3. ?？刂茥＃篜ascal,c4. 堆開銷比棧大(分配和釋放方式)：Pascal,c活動(dòng)記錄把過程的一個(gè)活動(dòng)所需求的信息組織成一塊延續(xù)的存儲(chǔ)單元，稱為活動(dòng)記錄。一個(gè)活動(dòng)所需求的信息的每個(gè)數(shù)據(jù)項(xiàng)有一樣的生存期，因

11、此，組織成一個(gè)活動(dòng)記錄是很自然的。對(duì)于pascal言語(yǔ)來說，運(yùn)轉(zhuǎn)過程中，當(dāng)調(diào)用一個(gè)過程時(shí)，在棧頂構(gòu)筑它的活動(dòng)記錄；當(dāng)這個(gè)過程的活動(dòng)執(zhí)行完后，把它從棧頂彈出?；顒?dòng)記錄控制鏈:指向調(diào)用過程活動(dòng)的活動(dòng)記錄。訪問鏈：指向本活動(dòng)要訪問的非部分?jǐn)?shù)據(jù)所在的活動(dòng)記錄。保管機(jī)器形狀：調(diào)用過程活動(dòng)在調(diào)用點(diǎn)的機(jī)器形狀，包括計(jì)數(shù)器，各種存放器的值。部分?jǐn)?shù)據(jù)：過程中定義的部分量。暫時(shí)變量：編譯產(chǎn)生。前往值真實(shí)參數(shù)控制鏈訪問鏈保管機(jī)器形狀部分?jǐn)?shù)據(jù)暫時(shí)變量編譯時(shí)辰的部分?jǐn)?shù)據(jù)的設(shè)計(jì)PROCEDURE sub(x,y:real); VAR i ,j:integer; a:ARRAY1.5 OF real; e, f : rea

12、l; 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符號(hào)表中間代碼編譯終了，知道每個(gè)過程的活動(dòng)記錄的長(zhǎng)度，將其填寫到相應(yīng)的過程表中，運(yùn)轉(zhuǎn)時(shí)，調(diào)用哪個(gè)過程，就在運(yùn)轉(zhuǎn)棧頂，推進(jìn)那個(gè)過程的活動(dòng)記錄棧箭頭加上活動(dòng)記錄長(zhǎng)度。f :=e+i*j;*ijt1+et1t2:=t2f運(yùn)轉(zhuǎn)時(shí)辰存儲(chǔ)分配戰(zhàn)略分配戰(zhàn)略是：靜態(tài)分配；棧式分配，或稱棧式動(dòng)態(tài)分配；堆式分配，或稱堆式動(dòng)態(tài)分配。 采用哪種分配戰(zhàn)略是由源言語(yǔ)的語(yǔ)義決議的。靜態(tài)存儲(chǔ)分配靜態(tài)存儲(chǔ)分配：在編譯階段

13、由編譯程序?qū)崿F(xiàn)對(duì)存儲(chǔ)空間的管理和為源程序中的變量分配存儲(chǔ)的方法。靜態(tài)存儲(chǔ)分配的條件假設(shè)在編譯時(shí)可以確定源程序中變量在運(yùn)轉(zhuǎn)時(shí)的數(shù)據(jù)空間大小，且運(yùn)轉(zhuǎn)時(shí)不改動(dòng)，那么就可以采用靜態(tài)存儲(chǔ)分配方法。允許部分名字的值在過程停頓活動(dòng)后依然堅(jiān)持，也就是當(dāng)控制再次進(jìn)入程序時(shí)，部分名字的值同控制上次分開時(shí)一樣。還能用控制棧進(jìn)展控制嗎？靜態(tài)存儲(chǔ)分配的局限在編譯時(shí)辰知道數(shù)據(jù)目的的大小和它們?cè)趦?nèi)存位置上的約束；不能遞歸調(diào)用過程一個(gè)過程的兩個(gè)活動(dòng)的生存期不相交,一個(gè)過程的一切活動(dòng)可以運(yùn)用同一個(gè)活動(dòng)記錄；不能動(dòng)態(tài)地建立數(shù)據(jù)構(gòu)造。靜態(tài)存儲(chǔ)分配戰(zhàn)略CNSUME目的代碼PRDUCE目的代碼Char *50 buf int next

14、 char cChar *80 buffer int nextCnsume活動(dòng)記錄prduce活動(dòng)記錄目的代碼靜態(tài)數(shù)據(jù)靜態(tài)存儲(chǔ)分配戰(zhàn)略由于每個(gè)變量所需空間的大小在編譯時(shí)知，因此可以用簡(jiǎn)單的方法給變量分配目的地址。開辟一數(shù)據(jù)區(qū)。首地址在加載時(shí)定按編譯順序給每個(gè)模塊分配存儲(chǔ)空間。在模塊內(nèi)部按順序給模塊的變量分配存儲(chǔ)，普通用相對(duì)地址，所占數(shù)據(jù)區(qū)的大小由變量類型決議。目的地址填入變量的符號(hào)表中。動(dòng)態(tài)存儲(chǔ)分配在目的程序運(yùn)轉(zhuǎn)階段由目的程序?qū)崿F(xiàn)對(duì)存儲(chǔ)空間的組織與管理，和為源程序中的變量分配存儲(chǔ)的方法。特點(diǎn)編譯時(shí)不能詳細(xì)確定程序所需數(shù)據(jù)空間編譯程序生成有關(guān)存儲(chǔ)分配的目的代碼實(shí)踐上的分配要在目的程序運(yùn)轉(zhuǎn)時(shí)進(jìn)展分程序構(gòu)造，且允許遞歸調(diào)