第13章運(yùn)行時(shí)存儲(chǔ)空間的組織課件

第13章運(yùn)行時(shí)存儲(chǔ)空間的組織第13章運(yùn)行時(shí)存儲(chǔ)空間的組織1第一節(jié)程序的存儲(chǔ)空間1.代碼空間和數(shù)據(jù)空間1.1程序投入運(yùn)行的必要條件程序要投入運(yùn)行，必須在內(nèi)存中分配一定的存儲(chǔ)空間，并將程序裝入其中，包括：可運(yùn)行的代碼（代碼空間）代碼運(yùn)行的環(huán)境（數(shù)據(jù)空間）第一節(jié)程序的存儲(chǔ)空間1.代碼空間和數(shù)據(jù)空間21.2代碼空間（C）內(nèi)容：線性存放著目標(biāo)指令序列。當(dāng)前執(zhí)行的指令位置由指令指針ip指示。1.3數(shù)據(jù)空間（D）內(nèi)容：變量、常數(shù)、控制信息、描述符等。靜態(tài)分配：在運(yùn)行前就可確定數(shù)據(jù)空間的大小,在編譯時(shí)刻就能進(jìn)行的存儲(chǔ)分配。動(dòng)態(tài)分配：運(yùn)行時(shí)才能進(jìn)行的存儲(chǔ)分配。1.2代碼空間（C）32.活動(dòng)記錄程序由程序單元（函數(shù)、子程序）組成，因此程序的數(shù)據(jù)空間由相應(yīng)程序單元的數(shù)據(jù)空間組成。一個(gè)程序單元的數(shù)據(jù)空間叫做該程序單元的活動(dòng)記錄。一個(gè)程序單元在執(zhí)行過(guò)程中所需要的數(shù)據(jù)信息、管理信息都是通過(guò)它的活動(dòng)記錄來(lái)存放的。一個(gè)程序單元的每一次激活，都應(yīng)在內(nèi)存中建立相應(yīng)的活動(dòng)記錄。2.活動(dòng)記錄程序由程序單元（函數(shù)、子程序）組成，因此程序的42.1活動(dòng)記錄的內(nèi)容(1)返回地址(2)動(dòng)態(tài)連接(3)靜態(tài)連接(4)現(xiàn)場(chǎng)保護(hù)(5)參數(shù)區(qū)(6)變量區(qū)變量區(qū)參數(shù)區(qū)現(xiàn)場(chǎng)保護(hù)靜態(tài)連接動(dòng)態(tài)連接返回地址2.1活動(dòng)記錄的內(nèi)容(1)返回地址變量區(qū)參數(shù)區(qū)現(xiàn)場(chǎng)保護(hù)靜52.2活動(dòng)記錄的特點(diǎn)除了變量存儲(chǔ)區(qū)外，其余部分存儲(chǔ)長(zhǎng)度編譯時(shí)可以確定，所以變量i的地址可用下式表示： D+offset(i)其中，D是活動(dòng)記錄的首地址；offset(i)是變量i在活動(dòng)記錄中的位移。2.2活動(dòng)記錄的特點(diǎn)除了變量存儲(chǔ)區(qū)外，其余部分存儲(chǔ)長(zhǎng)度編譯62.3變量的類(lèi)型1)靜態(tài)變量編譯時(shí)可以確定活動(dòng)記錄的首地址D和變量的相對(duì)位置offset(i)。不管在程序單元的哪一次激活中，變量的存儲(chǔ)位置均為：D+offset(i)。2)半靜態(tài)變量編譯時(shí)可確定變量i的相對(duì)位置offset(i)，單元激活時(shí)可確定活動(dòng)記錄的首地址D。則每一次激活，變量對(duì)應(yīng)一個(gè)不同的存儲(chǔ)位置：D+offset(i)。2.3變量的類(lèi)型1)靜態(tài)變量73)半動(dòng)態(tài)變量編譯時(shí)不能確定變量i的相對(duì)位置offset(i)，但能確定i的存儲(chǔ)格式?？稍诨顒?dòng)記錄中為i建立一個(gè)描述符，用于記錄i在內(nèi)存中的存儲(chǔ)格式，并在描述符中建立一個(gè)指針域，用于記錄i在運(yùn)行時(shí)的具體存儲(chǔ)地址。例：動(dòng)態(tài)數(shù)組inta[1..m];intb[1..m][1..n];3)半動(dòng)態(tài)變量84)動(dòng)態(tài)變量編譯時(shí)不能確定變量i的相對(duì)位置offset(i)，也不能確定i的存儲(chǔ)格式。即描述符需要到運(yùn)行時(shí)才能確定，因此可在活動(dòng)記錄中為i設(shè)置兩個(gè)指針，一個(gè)記錄運(yùn)行時(shí)描述符的地址，另一個(gè)記錄運(yùn)行時(shí)i的地址。例： 某些語(yǔ)言中類(lèi)型可變的變量； 某些語(yǔ)言中維數(shù)可變的數(shù)組。4)動(dòng)態(tài)變量94.存儲(chǔ)分配模式4.1靜態(tài)分配可用于靜態(tài)變量的分配，變量與存儲(chǔ)區(qū)域的綁定關(guān)系在編譯時(shí)便可建立，并完成存儲(chǔ)分配；不允許遞歸調(diào)用，不允許動(dòng)態(tài)數(shù)組，不允許動(dòng)態(tài)類(lèi)型的數(shù)據(jù)對(duì)象。4.存儲(chǔ)分配模式4.1靜態(tài)分配104.2棧式分配用棧分配活動(dòng)記錄；各程序單元之間的調(diào)用遵循“后進(jìn)先出”模式；活動(dòng)記錄的建立和撤消也滿足“后進(jìn)先出”模式；分配方法：當(dāng)一個(gè)程序單元被激活時(shí),在棧頂分配其活動(dòng)記錄；當(dāng)程序單元退出時(shí)，在棧頂將其活動(dòng)記錄撤銷(xiāo)。4.2棧式分配11例子：某程序中各程序單元的調(diào)用順序?yàn)椋骸璓運(yùn)行P調(diào)用QQ調(diào)用R……R退出Q退出P退出……P的活動(dòng)記錄Q的活動(dòng)記錄R的活動(dòng)記錄.........例子：某程序中各程序單元的調(diào)用順序?yàn)椋篜的活動(dòng)記錄Q的活動(dòng)記124.3堆分配由于動(dòng)態(tài)變量的首地址、長(zhǎng)度、類(lèi)型等在編譯時(shí)無(wú)法確定，在執(zhí)行過(guò)程中也可能改變，所以不可能在棧上為這樣的對(duì)象分配存儲(chǔ)區(qū)。對(duì)于這些變量，必須分配在堆上。例如：C中通過(guò)malloc分配的變量；某些語(yǔ)言中的動(dòng)態(tài)變量等。4.3堆分配由于動(dòng)態(tài)變量的首地址、長(zhǎng)度、類(lèi)型等在編譯時(shí)無(wú)法134.4存儲(chǔ)空間的組織代碼靜態(tài)數(shù)據(jù)棧堆4.4存儲(chǔ)空間的組織代碼靜態(tài)數(shù)據(jù)棧堆14第二節(jié)棧式分配1.半靜態(tài)變量的棧式分配1.1特點(diǎn)變量及活動(dòng)記錄的長(zhǎng)度都可靜態(tài)確定；一個(gè)程序單元可能被多次激活，活動(dòng)記錄是在程序單元激活時(shí)動(dòng)態(tài)建立，并與代碼段建立聯(lián)系的。第二節(jié)棧式分配1.半靜態(tài)變量的棧式分配151.2處理方法(1)設(shè)置當(dāng)前棧指針current，表示當(dāng)前活動(dòng)記錄的開(kāi)始位置（活動(dòng)記錄首地址D）；(2)指針free表示數(shù)據(jù)存儲(chǔ)器下一個(gè)可用單元；(3)變量綁定于它在活動(dòng)記錄中的常數(shù)位移i，變量通過(guò)current變址訪問(wèn)；(4)A調(diào)用B時(shí)，在A活動(dòng)記錄的棧頂之上建立B的當(dāng)前實(shí)例的活動(dòng)記錄；(5)從B返回時(shí)，釋放其活動(dòng)記錄。1.2處理方法(1)設(shè)置當(dāng)前棧指針current，表示當(dāng)161.3動(dòng)態(tài)連接和動(dòng)態(tài)鏈動(dòng)態(tài)連接：A調(diào)用B時(shí)，B的活動(dòng)記錄中保存的A的活動(dòng)記錄地址。動(dòng)態(tài)鏈：由動(dòng)態(tài)連接組成的一個(gè)調(diào)用鏈。1.3動(dòng)態(tài)連接和動(dòng)態(tài)鏈動(dòng)態(tài)連接：A調(diào)用B時(shí)，B的活動(dòng)記錄17AEFGF例：AcallE;EcallF;FcallG;GcallF;...............AEFGF例：AcallE;EcallF;Fc181.4CALLP的翻譯(1)D[free]:=ip+5（保存返回地址）(2)D[free+1]:=current（保存current）(3)current:=free（建立新的current） (4)free:=free+L（調(diào)整free）(5)ip:=P（轉(zhuǎn)移到P）1.4CALLP的翻譯(1)D[free]:=19例子：過(guò)程A調(diào)用過(guò)程P返回地址動(dòng)態(tài)連接返回地址動(dòng)態(tài)連接A的活動(dòng)記錄P的活動(dòng)記錄currentfreefreecurrentcurrentcurrent例子：過(guò)程A調(diào)用過(guò)程P返回地址動(dòng)態(tài)連接返回地址動(dòng)態(tài)連接A的活201.5RETURN語(yǔ)句的翻譯(1)恢復(fù)free free:=current(2)恢復(fù)主調(diào)過(guò)程的current current:=D[current+1](3)返回 ip:=D[free]1.5RETURN語(yǔ)句的翻譯(1)恢復(fù)free21返回地址動(dòng)態(tài)連接返回地址動(dòng)態(tài)連接A的活動(dòng)記錄P的活動(dòng)記錄freecurrent過(guò)程P退出，返回過(guò)程Acurrentfree返回地址動(dòng)態(tài)連接返回地址動(dòng)態(tài)連接A的活動(dòng)記錄P的活動(dòng)記錄fr222.半動(dòng)態(tài)變量的棧式分配在活動(dòng)記錄中為變量i建立描述符；在活動(dòng)記錄的最后分配變量i；用描述中的指針域指向變量i的存儲(chǔ)位置。變量區(qū)……變量i的存儲(chǔ)區(qū)參數(shù)區(qū)現(xiàn)場(chǎng)保護(hù)靜態(tài)連接動(dòng)態(tài)連接返回地址currentfree2.半動(dòng)態(tài)變量的棧式分配在活動(dòng)記錄中為變量i建立描述符23(1)編譯時(shí)創(chuàng)建描述符，并產(chǎn)生在運(yùn)行時(shí)動(dòng)態(tài)修改描述符和創(chuàng)建變量存儲(chǔ)空間的指令。(2)一個(gè)單元激活后（進(jìn)入該單元），遇到變量i的說(shuō)明時(shí)，調(diào)用上述指令（填描述符，分配存儲(chǔ)空間），并調(diào)整free:=free+L。(1)編譯時(shí)創(chuàng)建描述符，并產(chǎn)生在運(yùn)行時(shí)動(dòng)態(tài)修改描述符和創(chuàng)建243.動(dòng)態(tài)變量的存儲(chǔ)分配在活動(dòng)記錄中為變量i分配兩個(gè)指針在堆上分配動(dòng)態(tài)變量的描述符和存儲(chǔ)空間用活動(dòng)記錄中的兩個(gè)指針指向上述兩個(gè)位置變量區(qū)…………返回地址currentfree變量i的描述符變量i的存儲(chǔ)區(qū)堆空間3.動(dòng)態(tài)變量的存儲(chǔ)分配在活動(dòng)記錄中為變量i分配兩個(gè)指25程序單元間通信方式是通過(guò)非局部環(huán)境和參數(shù)傳遞來(lái)實(shí)現(xiàn)的。對(duì)非局部環(huán)境的引用必須考慮變量的作用域，變量的作用域是指可訪問(wèn)該變量的程序范圍。第三節(jié)非局部環(huán)境程序單元間通信方式是通過(guò)非局部環(huán)境和參數(shù)傳遞來(lái)實(shí)現(xiàn)的。第三261.動(dòng)態(tài)作用域規(guī)則這是一種最近活動(dòng)規(guī)則，對(duì)非局部變量，引用的應(yīng)是最近的“調(diào)用外層”中說(shuō)明的變量。例：A-C-F的調(diào)用序列，F(xiàn)的直接調(diào)用外層為C、C的直接調(diào)用外層為A。2.引用方法通過(guò)“動(dòng)態(tài)鏈”找到最近的“調(diào)用外層”中說(shuō)明的變量。一、動(dòng)態(tài)作用域規(guī)則1.動(dòng)態(tài)作用域規(guī)則一、動(dòng)態(tài)作用域規(guī)則271.靜態(tài)作用域規(guī)則這是一種最近嵌套規(guī)則，對(duì)非局部變量，引用的應(yīng)是最近的“嵌套外層”中說(shuō)明的變量。

例：嵌套的層次若A是B的直接外層，則B的層次=A的層次+1。A(0)、B(1)、C(2)、D(3)、E(1)、F(2)、G(2)二、靜態(tài)作用域規(guī)則1.靜態(tài)作用域規(guī)則二、靜態(tài)作用域規(guī)則28unitA;y:int;unitB;endB;y:int;unitC;endD;endC;…...unitD;………...ABCDEFGunitA;y:int;unitB;endB;y:29endE;z:int;unitF;endG;unitG;x,y:int;…...………...unitE;z:=x+y;endF;………...endA;x:int;ABCDEFGendE;z:int;unitF;endG;unit302.引用方法通過(guò)“靜態(tài)鏈”找到最近的“嵌套外層”中說(shuō)明的變量。(1)靜態(tài)連接和靜態(tài)鏈靜態(tài)連接：指向嵌套直接外層的最新活動(dòng)記錄的指針。靜態(tài)鏈：各嵌套程序單元的活動(dòng)記錄中，靜態(tài)連接的序列構(gòu)成一個(gè)靜態(tài)鏈。2.引用方法通過(guò)“靜態(tài)鏈”找到最近的“嵌套外層”中說(shuō)明的變31AEFGF例：AcallE;EcallF;FcallG;GcallF;...............AEFGF例：AcallE;EcallF;Fc32假設(shè)當(dāng)前處在棧頂?shù)氖菃卧狟的活動(dòng)記錄，單元B中引用了單元A中的變量x。單元A的層次為nA、單元B的層次為nB。要找到變量x的存放地址，即：DA+offset(x)關(guān)鍵是要找到單元A的活動(dòng)記錄DA。(2)非局部變量x的地址的求法假設(shè)當(dāng)前處在棧頂?shù)氖菃卧狟的活動(dòng)記錄，單元B中引用了單元A中33nB-nA=0：A和B是同一層（A就是B） DA=currentnB-nA=1：A是B的直接外層（第1個(gè)外層） DA＝D[current+2]nB-nA=2：A是B的第2個(gè)外層 DA=D[D[current+2]+2]nB-nA=3：A是B的第3個(gè)外層 DA=D[D[D[current+2]＋2]＋2]DA的求法nB-nA=0：A和B是同一層（A就是B）DA的求法34令nB-nA=d，定義函數(shù)f(d)，表示從B的活動(dòng)記錄出發(fā)，沿靜態(tài)鏈搜索d步，可以到達(dá)A的活動(dòng)記錄。f(d){ if(d=0)thenreturncurrent; elsereturnD[f(d-1)+2];}令nB-nA=d，定義函數(shù)f(d)，表示從B的活動(dòng)記35(3)靜態(tài)連接的建立（單元X調(diào)用單元B時(shí)）當(dāng)前棧頂為X的活動(dòng)記錄，需要建立B的活動(dòng)記錄。(3)nX-nB=1(4)nX-nB>1(1)nX-nB=-1XBcallBBXcallBBcallBX(2)nX-nB=0BXcallB……………(3)靜態(tài)連接的建立（單元X調(diào)用單元B時(shí)）(3)nX-nB36(1)nX-nB=-1,B的靜態(tài)連接＝f(0)(2)nX-nB=0,B的靜態(tài)連接＝f(1)(3)nX-nB=1,B的靜態(tài)連接＝f(2)(4)nX-nB=d,B的靜態(tài)連接＝f(d+1)因此，靜態(tài)連接算法為：D[free+2]=f(d+1)(1)nX-nB=-1,B的靜態(tài)連接＝f(0)37(1)D[free]:=ip+6（保存返回地址）(2)D[free+1]:=current（設(shè)置動(dòng)態(tài)鏈接）(3)D[free+2]:=f(d+1)（設(shè)置靜態(tài)鏈接）(4)current:=free（建立新的current） (5)free:=free+L（調(diào)整free）(6)ip:=P（轉(zhuǎn)移到P）(4)CALLP的處理(1)D[free]:=ip+6（保存返回地址38形參和實(shí)參形參(FormalParameter)：被調(diào)用單元的參數(shù)實(shí)參(ActualParameter)：調(diào)用單元的參數(shù)參數(shù)傳遞的類(lèi)型傳值、傳值得結(jié)果、傳地址第四節(jié)參數(shù)傳遞形參和實(shí)參第四節(jié)參數(shù)傳遞39參數(shù)傳遞實(shí)例proceduremainbegina,b:integer; a:=1;b:=2; print(a,b); swap(a,b); print(a,b);endprocedureswap(x,y)varx,y:intger;begin print(x,y); x:=x+y; y:=x-y; x:=x-y; print(x,y)end參數(shù)傳遞實(shí)例proceduremainprocedur40(1)傳值（單向傳遞）實(shí)參的值形參的值運(yùn)行結(jié)果：1,21,22,11,2(1)傳值（單向傳遞）41(2)傳值得結(jié)果（雙向傳遞）實(shí)參的值形參的值形參的結(jié)果值實(shí)參的結(jié)果值運(yùn)行結(jié)果：1,21,22,12,1(2)傳值得結(jié)果（雙向傳遞）42(3)傳地址（共用同一數(shù)據(jù)單元）實(shí)參的地址形參的地址運(yùn)行結(jié)果：1,21,22,12,1注意(3)和(2)的區(qū)別，如調(diào)用swap(a,a)時(shí)的運(yùn)行結(jié)果。(3)傳地址（共用同一數(shù)據(jù)單元）注意(3)和(2)的區(qū)別，43習(xí)題1.對(duì)下列程序，試描述每次調(diào)用時(shí)活動(dòng)記錄棧的狀況，直到C中調(diào)用B時(shí)。重點(diǎn)注意動(dòng)態(tài)連接和靜態(tài)連接的情況。programA; procedureB; procedureC; …callB;… endC; …callC;… endB procedureD; …callB;… endD; …callD;…endA習(xí)題1.對(duì)下列程序，試描述每次調(diào)用時(shí)活動(dòng)記錄棧的狀況，直到442.下列程序在靜態(tài)作用域規(guī)則或動(dòng)態(tài)作用域規(guī)則下會(huì)有什么輸出？programmain; varr:real; proceduref1; write(r); endf1 proceduref2; varr:real; r:=0.125;callf1; endf2 r:=0.25; callf1;callf2;write(“\n”); callf1;callf2;write(“\n”);endmain2.下列程序在靜態(tài)作用域規(guī)則或動(dòng)態(tài)作用域規(guī)則下會(huì)有什么輸出45第13章運(yùn)行時(shí)存儲(chǔ)空間的組織第13章運(yùn)行時(shí)存儲(chǔ)空間的組織46第一節(jié)程序的存儲(chǔ)空間1.代碼空間和數(shù)據(jù)空間1.1程序投入運(yùn)行的必要條件程序要投入運(yùn)行，必須在內(nèi)存中分配一定的存儲(chǔ)空間，并將程序裝入其中，包括：可運(yùn)行的代碼（代碼空間）代碼運(yùn)行的環(huán)境（數(shù)據(jù)空間）第一節(jié)程序的存儲(chǔ)空間1.代碼空間和數(shù)據(jù)空間471.2代碼空間（C）內(nèi)容：線性存放著目標(biāo)指令序列。當(dāng)前執(zhí)行的指令位置由指令指針ip指示。1.3數(shù)據(jù)空間（D）內(nèi)容：變量、常數(shù)、控制信息、描述符等。靜態(tài)分配：在運(yùn)行前就可確定數(shù)據(jù)空間的大小,在編譯時(shí)刻就能進(jìn)行的存儲(chǔ)分配。動(dòng)態(tài)分配：運(yùn)行時(shí)才能進(jìn)行的存儲(chǔ)分配。1.2代碼空間（C）482.活動(dòng)記錄程序由程序單元（函數(shù)、子程序）組成，因此程序的數(shù)據(jù)空間由相應(yīng)程序單元的數(shù)據(jù)空間組成。一個(gè)程序單元的數(shù)據(jù)空間叫做該程序單元的活動(dòng)記錄。一個(gè)程序單元在執(zhí)行過(guò)程中所需要的數(shù)據(jù)信息、管理信息都是通過(guò)它的活動(dòng)記錄來(lái)存放的。一個(gè)程序單元的每一次激活，都應(yīng)在內(nèi)存中建立相應(yīng)的活動(dòng)記錄。2.活動(dòng)記錄程序由程序單元（函數(shù)、子程序）組成，因此程序的492.1活動(dòng)記錄的內(nèi)容(1)返回地址(2)動(dòng)態(tài)連接(3)靜態(tài)連接(4)現(xiàn)場(chǎng)保護(hù)(5)參數(shù)區(qū)(6)變量區(qū)變量區(qū)參數(shù)區(qū)現(xiàn)場(chǎng)保護(hù)靜態(tài)連接動(dòng)態(tài)連接返回地址2.1活動(dòng)記錄的內(nèi)容(1)返回地址變量區(qū)參數(shù)區(qū)現(xiàn)場(chǎng)保護(hù)靜502.2活動(dòng)記錄的特點(diǎn)除了變量存儲(chǔ)區(qū)外，其余部分存儲(chǔ)長(zhǎng)度編譯時(shí)可以確定，所以變量i的地址可用下式表示： D+offset(i)其中，D是活動(dòng)記錄的首地址；offset(i)是變量i在活動(dòng)記錄中的位移。2.2活動(dòng)記錄的特點(diǎn)除了變量存儲(chǔ)區(qū)外，其余部分存儲(chǔ)長(zhǎng)度編譯512.3變量的類(lèi)型1)靜態(tài)變量編譯時(shí)可以確定活動(dòng)記錄的首地址D和變量的相對(duì)位置offset(i)。不管在程序單元的哪一次激活中，變量的存儲(chǔ)位置均為：D+offset(i)。2)半靜態(tài)變量編譯時(shí)可確定變量i的相對(duì)位置offset(i)，單元激活時(shí)可確定活動(dòng)記錄的首地址D。則每一次激活，變量對(duì)應(yīng)一個(gè)不同的存儲(chǔ)位置：D+offset(i)。2.3變量的類(lèi)型1)靜態(tài)變量523)半動(dòng)態(tài)變量編譯時(shí)不能確定變量i的相對(duì)位置offset(i)，但能確定i的存儲(chǔ)格式?？稍诨顒?dòng)記錄中為i建立一個(gè)描述符，用于記錄i在內(nèi)存中的存儲(chǔ)格式，并在描述符中建立一個(gè)指針域，用于記錄i在運(yùn)行時(shí)的具體存儲(chǔ)地址。例：動(dòng)態(tài)數(shù)組inta[1..m];intb[1..m][1..n];3)半動(dòng)態(tài)變量534)動(dòng)態(tài)變量編譯時(shí)不能確定變量i的相對(duì)位置offset(i)，也不能確定i的存儲(chǔ)格式。即描述符需要到運(yùn)行時(shí)才能確定，因此可在活動(dòng)記錄中為i設(shè)置兩個(gè)指針，一個(gè)記錄運(yùn)行時(shí)描述符的地址，另一個(gè)記錄運(yùn)行時(shí)i的地址。例： 某些語(yǔ)言中類(lèi)型可變的變量； 某些語(yǔ)言中維數(shù)可變的數(shù)組。4)動(dòng)態(tài)變量544.存儲(chǔ)分配模式4.1靜態(tài)分配可用于靜態(tài)變量的分配，變量與存儲(chǔ)區(qū)域的綁定關(guān)系在編譯時(shí)便可建立，并完成存儲(chǔ)分配；不允許遞歸調(diào)用，不允許動(dòng)態(tài)數(shù)組，不允許動(dòng)態(tài)類(lèi)型的數(shù)據(jù)對(duì)象。4.存儲(chǔ)分配模式4.1靜態(tài)分配554.2棧式分配用棧分配活動(dòng)記錄；各程序單元之間的調(diào)用遵循“后進(jìn)先出”模式；活動(dòng)記錄的建立和撤消也滿足“后進(jìn)先出”模式；分配方法：當(dāng)一個(gè)程序單元被激活時(shí),在棧頂分配其活動(dòng)記錄；當(dāng)程序單元退出時(shí)，在棧頂將其活動(dòng)記錄撤銷(xiāo)。4.2棧式分配56例子：某程序中各程序單元的調(diào)用順序?yàn)椋骸璓運(yùn)行P調(diào)用QQ調(diào)用R……R退出Q退出P退出……P的活動(dòng)記錄Q的活動(dòng)記錄R的活動(dòng)記錄.........例子：某程序中各程序單元的調(diào)用順序?yàn)椋篜的活動(dòng)記錄Q的活動(dòng)記574.3堆分配由于動(dòng)態(tài)變量的首地址、長(zhǎng)度、類(lèi)型等在編譯時(shí)無(wú)法確定，在執(zhí)行過(guò)程中也可能改變，所以不可能在棧上為這樣的對(duì)象分配存儲(chǔ)區(qū)。對(duì)于這些變量，必須分配在堆上。例如：C中通過(guò)malloc分配的變量；某些語(yǔ)言中的動(dòng)態(tài)變量等。4.3堆分配由于動(dòng)態(tài)變量的首地址、長(zhǎng)度、類(lèi)型等在編譯時(shí)無(wú)法584.4存儲(chǔ)空間的組織代碼靜態(tài)數(shù)據(jù)棧堆4.4存儲(chǔ)空間的組織代碼靜態(tài)數(shù)據(jù)棧堆59第二節(jié)棧式分配1.半靜態(tài)變量的棧式分配1.1特點(diǎn)變量及活動(dòng)記錄的長(zhǎng)度都可靜態(tài)確定；一個(gè)程序單元可能被多次激活，活動(dòng)記錄是在程序單元激活時(shí)動(dòng)態(tài)建立，并與代碼段建立聯(lián)系的。第二節(jié)棧式分配1.半靜態(tài)變量的棧式分配601.2處理方法(1)設(shè)置當(dāng)前棧指針current，表示當(dāng)前活動(dòng)記錄的開(kāi)始位置（活動(dòng)記錄首地址D）；(2)指針free表示數(shù)據(jù)存儲(chǔ)器下一個(gè)可用單元；(3)變量綁定于它在活動(dòng)記錄中的常數(shù)位移i，變量通過(guò)current變址訪問(wèn)；(4)A調(diào)用B時(shí)，在A活動(dòng)記錄的棧頂之上建立B的當(dāng)前實(shí)例的活動(dòng)記錄；(5)從B返回時(shí)，釋放其活動(dòng)記錄。1.2處理方法(1)設(shè)置當(dāng)前棧指針current，表示當(dāng)611.3動(dòng)態(tài)連接和動(dòng)態(tài)鏈動(dòng)態(tài)連接：A調(diào)用B時(shí)，B的活動(dòng)記錄中保存的A的活動(dòng)記錄地址。動(dòng)態(tài)鏈：由動(dòng)態(tài)連接組成的一個(gè)調(diào)用鏈。1.3動(dòng)態(tài)連接和動(dòng)態(tài)鏈動(dòng)態(tài)連接：A調(diào)用B時(shí)，B的活動(dòng)記錄62AEFGF例：AcallE;EcallF;FcallG;GcallF;...............AEFGF例：AcallE;EcallF;Fc631.4CALLP的翻譯(1)D[free]:=ip+5（保存返回地址）(2)D[free+1]:=current（保存current）(3)current:=free（建立新的current） (4)free:=free+L（調(diào)整free）(5)ip:=P（轉(zhuǎn)移到P）1.4CALLP的翻譯(1)D[free]:=64例子：過(guò)程A調(diào)用過(guò)程P返回地址動(dòng)態(tài)連接返回地址動(dòng)態(tài)連接A的活動(dòng)記錄P的活動(dòng)記錄currentfreefreecurrentcurrentcurrent例子：過(guò)程A調(diào)用過(guò)程P返回地址動(dòng)態(tài)連接返回地址動(dòng)態(tài)連接A的活651.5RETURN語(yǔ)句的翻譯(1)恢復(fù)free free:=current(2)恢復(fù)主調(diào)過(guò)程的current current:=D[current+1](3)返回 ip:=D[free]1.5RETURN語(yǔ)句的翻譯(1)恢復(fù)free66返回地址動(dòng)態(tài)連接返回地址動(dòng)態(tài)連接A的活動(dòng)記錄P的活動(dòng)記錄freecurrent過(guò)程P退出，返回過(guò)程Acurrentfree返回地址動(dòng)態(tài)連接返回地址動(dòng)態(tài)連接A的活動(dòng)記錄P的活動(dòng)記錄fr672.半動(dòng)態(tài)變量的棧式分配在活動(dòng)記錄中為變量i建立描述符；在活動(dòng)記錄的最后分配變量i；用描述中的指針域指向變量i的存儲(chǔ)位置。變量區(qū)……變量i的存儲(chǔ)區(qū)參數(shù)區(qū)現(xiàn)場(chǎng)保護(hù)靜態(tài)連接動(dòng)態(tài)連接返回地址currentfree2.半動(dòng)態(tài)變量的棧式分配在活動(dòng)記錄中為變量i建立描述符68(1)編譯時(shí)創(chuàng)建描述符，并產(chǎn)生在運(yùn)行時(shí)動(dòng)態(tài)修改描述符和創(chuàng)建變量存儲(chǔ)空間的指令。(2)一個(gè)單元激活后（進(jìn)入該單元），遇到變量i的說(shuō)明時(shí)，調(diào)用上述指令（填描述符，分配存儲(chǔ)空間），并調(diào)整free:=free+L。(1)編譯時(shí)創(chuàng)建描述符，并產(chǎn)生在運(yùn)行時(shí)動(dòng)態(tài)修改描述符和創(chuàng)建693.動(dòng)態(tài)變量的存儲(chǔ)分配在活動(dòng)記錄中為變量i分配兩個(gè)指針在堆上分配動(dòng)態(tài)變量的描述符和存儲(chǔ)空間用活動(dòng)記錄中的兩個(gè)指針指向上述兩個(gè)位置變量區(qū)…………返回地址currentfree變量i的描述符變量i的存儲(chǔ)區(qū)堆空間3.動(dòng)態(tài)變量的存儲(chǔ)分配在活動(dòng)記錄中為變量i分配兩個(gè)指70程序單元間通信方式是通過(guò)非局部環(huán)境和參數(shù)傳遞來(lái)實(shí)現(xiàn)的。對(duì)非局部環(huán)境的引用必須考慮變量的作用域，變量的作用域是指可訪問(wèn)該變量的程序范圍。第三節(jié)非局部環(huán)境程序單元間通信方式是通過(guò)非局部環(huán)境和參數(shù)傳遞來(lái)實(shí)現(xiàn)的。第三711.動(dòng)態(tài)作用域規(guī)則這是一種最近活動(dòng)規(guī)則，對(duì)非局部變量，引用的應(yīng)是最近的“調(diào)用外層”中說(shuō)明的變量。例：A-C-F的調(diào)用序列，F(xiàn)的直接調(diào)用外層為C、C的直接調(diào)用外層為A。2.引用方法通過(guò)“動(dòng)態(tài)鏈”找到最近的“調(diào)用外層”中說(shuō)明的變量。一、動(dòng)態(tài)作用域規(guī)則1.動(dòng)態(tài)作用域規(guī)則一、動(dòng)態(tài)作用域規(guī)則721.靜態(tài)作用域規(guī)則這是一種最近嵌套規(guī)則，對(duì)非局部變量，引用的應(yīng)是最近的“嵌套外層”中說(shuō)明的變量。

例：嵌套的層次若A是B的直接外層，則B的層次=A的層次+1。A(0)、B(1)、C(2)、D(3)、E(1)、F(2)、G(2)二、靜態(tài)作用域規(guī)則1.靜態(tài)作用域規(guī)則二、靜態(tài)作用域規(guī)則73unitA;y:int;unitB;endB;y:int;unitC;endD;endC;…...unitD;………...ABCDEFGunitA;y:int;unitB;endB;y:74endE;z:int;unitF;endG;unitG;x,y:int;…...………...unitE;z:=x+y;endF;………...endA;x:int;ABCDEFGendE;z:int;unitF;endG;unit752.引用方法通過(guò)“靜態(tài)鏈”找到最近的“嵌套外層”中說(shuō)明的變量。(1)靜態(tài)連接和靜態(tài)鏈靜態(tài)連接：指向嵌套直接外層的最新活動(dòng)記錄的指針。靜態(tài)鏈：各嵌套程序單元的活動(dòng)記錄中，靜態(tài)連接的序列構(gòu)成一個(gè)靜態(tài)鏈。2.引用方法通過(guò)“靜態(tài)鏈”找到最近的“嵌套外層”中說(shuō)明的變76AEFGF例：AcallE;EcallF;FcallG;GcallF;...............AEFGF例：AcallE;EcallF;Fc77假設(shè)當(dāng)前處在棧頂?shù)氖菃卧狟的活動(dòng)記錄，單元B中引用了單元A中的變量x。單元A的層次為nA、單元B的層次為nB。要找到變量x的存放地址，即：DA+offset(x)關(guān)鍵是要找到單元A的活動(dòng)記錄DA。(2)非局部變量x的地址的求法假設(shè)當(dāng)前處在棧頂?shù)氖菃卧狟的活動(dòng)記錄，單元B中引用了單元A中78nB-nA=0：A和B是同一層（A就是B） DA=currentnB-nA=1：A是B的直接外層（第1個(gè)外層） DA＝D[current+2]nB-nA=2：A是B的第2個(gè)外層 DA=D[D[current+2]+2]nB-nA=3：A是B的第3個(gè)外層 DA=D[D[D[current+2]＋2]＋2]DA的求法nB-nA=0：A和B是同一層（A就是B）DA的求法79令nB-nA=d，定義函數(shù)f(d)，表示從B的活動(dòng)記錄出發(fā)，沿靜態(tài)鏈搜索d步，可以到達(dá)A的活動(dòng)記錄。f(d){ if(d=0)thenreturncurrent; elsereturnD[f(d-1)+2];}令nB-nA=d，定義函數(shù)f(d)，表示從B的活動(dòng)記80(3)靜態(tài)連接的建立（單元X調(diào)用單元B時(shí)）當(dāng)前棧頂為X的活動(dòng)記錄，需要建立B的活動(dòng)記錄。(3)nX-nB=1(4)nX-nB>1(1)nX-nB=-1XBcallBBXcallBBcallBX(2)nX-nB=0BXcallB……………(3)靜態(tài)連接的建立（單元X調(diào)用單元B時(shí)）(3)nX-nB81(1)nX-nB=-1,B的靜態(tài)連接＝f(0)(2)nX-nB=0,B的靜態(tài)連接＝f(1)(3)nX-nB=1,B的靜態(tài)連接＝f(2)(4)nX-nB=d,B的靜態(tài)連接＝f(d+1)因此，靜態(tài)連接算法為：D[free+2]=f(d+1)(1)nX-nB=-1,B的靜態(tài)連接＝f(0)82(1)D[free]:=ip+6（保存返回地址）(2)D[free+1]:=current（設(shè)置動(dòng)態(tài)鏈接）(3)D[free+2]:=f(d+1)（設(shè)置靜態(tài)