1、 第六章 運行時刻環(huán)境 序6.1 源語言中的一些問題6.2 存儲組織6.3 運行時刻存儲分配策略6.5 參數(shù)傳遞6.6 符號表1 序 計算環(huán)境 運行時的環(huán)境 計算 目標(biāo)代碼 源程序中的名字（常量，變量）目標(biāo)機存儲空間。它受命于源程序的執(zhí)行語義。 源程序由一組過程按某種規(guī)則組成。過程的一次執(zhí)行稱作一次活動，在過程的語句序列執(zhí)行之前，過程中訪問的對象構(gòu)成此過程的運行環(huán)境，由運行支持程序組織好。編譯程序根據(jù)如何組織運行環(huán)境而生成目標(biāo)代碼。映射源程序26.1有關(guān)源程序中的一些問題 目的： 構(gòu)造運行程序的策略和方法 6.1.1 過程 6.1.2 活動樹 6.1.3 控制棧 6.1.4 說明的作用域 6.

2、1.5 名字的綁定 6.1.6 構(gòu)造運行程序和源程序有關(guān)的 一些問題36.1.1 過程 源程序由一組過程組成，不同的程序設(shè)計語言，由過程構(gòu)成源程序的方法不同。 構(gòu)成源程序的兩個過程行文，要么是嵌套的，要么是不相交的。4program sort（input，output）； var a ： array0.10 of integer； procedure readarray； var i ： integer； begin end； function partition （y ，z ： integer ）:integer； var i，j ，x，v： integer； begin end; proc

3、edure quicksort（m，n ： integer）； var i ： integer； begin end end； begin end.56.1.2 活動樹 程序執(zhí)行期間的控制流： 1程序執(zhí)行的控制是順序的； 2過程的每一次執(zhí)行都是從過程體的開頭 開始，并最終把控制返回到緊接著該過 程被調(diào)用點的后面。過程的一次活動: 過程體的每一次執(zhí)行。 一個過程p的一次活動的生存期:在該過程體的執(zhí)行中的第一步和最后一步之間的一序列步驟的執(zhí)行時間，其中包括執(zhí)行過程p所調(diào)用的過程的執(zhí)行時間，以及這些過程所調(diào)用的過程的執(zhí)行時間，如此等等。6特點： 每當(dāng)控制流從過程p的活動進入到過程q的活動中后，它將返

4、回到過程p的同一次活動中。 如果a和b是兩個過程活動，那么它們的生存期要么是不重疊的，要么是嵌套的。這種活動生存期的嵌套性質(zhì)可以通過在每一個過程中插入兩個打印語句來加以說明。7執(zhí)行開始 enter readarray leave readarray enter quicksort（1，9） enter partition（1，9） leave partition（l，9） enter quicksort（1，3） . leave quicksort（1，3) enter quicksort（5，9） . leave quicksort（5，9） leave quicksort（1，9） 執(zhí)行結(jié)

5、束8 一個過程是遞歸的，如果同一過程的一次新的活動可以在前面活動結(jié)束以前開始。 用一顆樹來描繪控制進入和離開活動的途徑。這祥的樹稱作活動樹。在一棵活動樹中： 1. b的左邊當(dāng)且僅當(dāng)a的生存期發(fā)生在b的生存期之前。 用活動樹來討論正在這個結(jié)點上的控制。9srq(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)p(5,9)q(5,5)q(7,9)p(7,9)q(7,7)圖6.3 一棵活動樹10結(jié)論：一個結(jié)點代表一個唯一的活動， 且每 一個活動只有一個結(jié)點表示，當(dāng)控制進 入某一個活動時，可以直接說，控制在 這個結(jié)點上。6.1.3 控

6、制棧 程序執(zhí)行的控制流對應(yīng)于從根開始，按先根次序遍歷活動樹。因此，用一個棧保存過程活動的生存蹤跡。把它稱作控制棧。 當(dāng)一個活動開始執(zhí)行時，把代表這個活動的結(jié)點推進棧；當(dāng)這個活動結(jié)束時，把代表這個活動的結(jié)點從棧中彈出。11例6.2 棧和活動樹的變化棧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)圖 6.412 控制棧中的活動都是活躍的，當(dāng)前控制進入的活動

7、在棧頂，從棧頂活動到棧底活動的活動序列是從活動樹上當(dāng)前結(jié)點通向根的路徑上的結(jié)點序列： s,q（1，9），q（l，3），q（2，3） 從棧底活動到棧頂活動的活動序列表示了活動的生存期的嵌套關(guān)系。 結(jié)論：擴充控制棧可用來實現(xiàn)如Pascal語言的棧式存儲分配，進入一個活動，在棧頂建立這個活動所使用的存儲空間；這個活動結(jié)束，從棧頂彈出其使用的存儲空間。136.1.4 說明的作用域 1 .說明把名字與名字的屬性信息綁定在一起。 2 . 說明的作用域是一個說明起作用的范圍 （源程序行文）。一個名字在源程序行文中 可能有幾處說明，語言的作用域規(guī)則規(guī)定： 在語句序列中引用的一個名字是在何處說 明的名字。 3

8、. 編譯時，處理說明把名字及其屬性信息填 寫進符號表(add(id.entry,id.vul); 處理引用 名字時，查找這個名字的屬性信息 （lookup(id),符號表管理程序根據(jù)語 言的 作用域規(guī)則，使 lookup(id)返回id的作用域 中綁定的屬性信息。146.1.5名字與存儲的綁定 名字與存儲單元的綁定是指把源程序中的數(shù)據(jù)名字映射到目標(biāo)機存儲單元的過程。 引進兩個函數(shù)，environment和state。environment把名字映射到一個存儲單元上；state把存儲單元映射到那里所存放的值上?？梢哉f，函數(shù)environment把一個名字映射為一個l-value（左-值）,而函數(shù)

9、state把一個l-value（左-值）映射為一個r-value（右-值）。如圖6.5所示。15名字存儲單元值存儲分配程序運行environmentstatel-valuer-value圖6.5 從名字到值的兩個階段映射16靜態(tài)概念 動態(tài)對應(yīng)過程定義 過程活動名字說明 名字的綁定說明的作用域 活動的生存期176.1.6 提出的問題 編譯程序組織存儲分配所采用策略和方法主要取決于對源程序中下面的問題的回答。 1過程可以是遞歸的嗎？ 2當(dāng)控制從過程的一次活動返回時，局部 名的值將發(fā)生什么 變化? 3一個過程可以訪問非局部名嗎？ 4當(dāng)調(diào)用過程時參數(shù)是怎樣傳遞的？ 5過程可以作為參數(shù)被傳遞嗎？ 6過程

10、可以作為結(jié)果被返回嗎？ 7. 可以在程序控制下進行動態(tài)存儲分配嗎？ 8. 顯式的存儲重新分配（指撤除分配后的分 配）是必須的嗎？ 18例：函數(shù)的返回值是函數(shù)。Fun times x y=x*y val times=fn: int (int int) twice=times 2fun compose(f, g)=f(g(x) compose=fn: ( ) ( )val fourtimes=compose(twice,twice)196.2 存儲組織 6.2.1 運行時刻內(nèi)存的劃分 運行時刻的存儲空間必須劃分以用來存放: 1. 生成的目標(biāo)代碼; 2. 數(shù)據(jù)目標(biāo); 3. 用于保存過程活動蹤跡的一個

11、控制棧。 存儲空間劃分的各部分：20目標(biāo)代碼靜態(tài)數(shù)據(jù)棧堆1. 編譯后知道目標(biāo)代 碼的大小。2. pascal主程序中的 數(shù)據(jù),c,FORTRAN3. 棧:Pascal,c4. 堆: Pascal,c216.2.2 活動記錄 把過程的一個活動所需要的信息組織成一塊連續(xù)的存儲單元，稱為活動記錄。 一個活動所需要的信息的每個數(shù)據(jù)項有相同的生存期，因此，組織成一個活動記錄是很自然的。 對于pascal語言來說，運行過程中，當(dāng)調(diào)用一個過程時，在棧頂構(gòu)筑它的活動記錄；當(dāng)這個過程的活動執(zhí)行完后，把它從棧頂彈出。 源語言不同，實現(xiàn)方法不同，組成活動記錄的域不同。實現(xiàn)pascal語言的活動記錄如圖6.7所示。2

12、2返回值實在參數(shù)控制鏈訪問鏈保存機器狀態(tài)局部數(shù)據(jù)臨時變量控制鏈:指向調(diào)用過程活動 的活動記錄。訪問鏈：指向本活動要訪 問的非局部數(shù)據(jù)所在的 活動記錄。保存機器狀態(tài)：調(diào)用過程 活動在調(diào)用點的機器 狀態(tài)，包括計數(shù)器， 各種寄存器的值。局部數(shù)據(jù)：過程中定義的 局部量。臨時變量：編譯產(chǎn)生。236.2.3 編譯時刻的局部數(shù)據(jù)的設(shè)計 局部數(shù)據(jù)域是編譯時刻在分析過程中的說 明時設(shè)計的。例如： PROCEDURE sub(x,y:real); VAR i ,j:integer; a:ARRAY1.5 OF real; e, f : real; BEGIN f :=e+i*j; END;24符號表名字 形 類型

13、 偏移量活動記錄布局返回值(top-sp,0) x 形 real 1(top-sp,1) y 形 real 2(top-sp,2)(top-sp,3)(top-sp,20) i int 20(top-sp,21) j int 21(top-sp,22) a array 22(top-sp,27) e real 27(top-sp,28) f real 2825中間代碼* i j t1 * (top-sp ,20) (top-sp ,21) (top-sp ,29) + e t1 t2 + (top-sp ,27) (top-sp ,29) (top-sp ,30) itor t2 t3 ito

14、r (top-sp ,30) (top-sp ,31):= t3 f := (top-sp ,31) (top-sp ,28) 編譯結(jié)束，知道每個過程的活動記錄的長度，將其填寫到相應(yīng)的過程表中，運行時，調(diào)用哪個過程，就在運行棧頂，推進那個過程的活動記錄（棧箭頭加上活動記錄長度）。266.3 運行時刻存儲分配策略 分配策略是： 1靜態(tài)分配； 2棧式分配，或稱棧式動態(tài)分配； 3堆式分配，或稱堆式動態(tài)分配。 6.3 .1 靜態(tài)存儲分配 6.3 .2 棧式存儲分配 6.3 .3 堆式存儲分配 采用哪種分配策略是由源語言的語義決定的。276.3 .1 靜態(tài)存儲分配 在編譯時刻為每個數(shù)據(jù)項目確定出在運行時

15、刻的存儲空間中的位置，且這種綁定在運行時刻不再發(fā)生變化。 局部名字的值在過程活動停止后仍保留下來。 限制： 1.在編譯時刻知道數(shù)據(jù)目標(biāo)的大小和它們在 內(nèi)存位置上 約束； 2.不能遞歸調(diào)用過程（一個過程的兩個活動 的生存期不相交,一個過程的所有活動可以 使用同一個活動記錄）； 3.不能動態(tài)地建立數(shù)據(jù)結(jié)構(gòu)。28 （1）PROGRAM CNSUME （2）CHARACTER *50 BUF （3）INTEGER NEXT （4CHARACTER C，PRDUCE （5）DATA NEXT1，BUF/ / （6）CPRDUCE（）。 （7）BUF（NEXT：NEXT）C （8NEXTNEXT1 （9）

16、IF（C.NE. )GOTO 6 （10）WRITE（*，(A)）BUF （11） END 29(12）CHARACTER FUNCTION PRDUCE（） （13)CHARACTER * 80 BUFFER （14）INTEGER NEXT （15）SAVE BUFFER，NEXT (16) DATA NEXT81 （17）IF(NEXT.GT.80）THEN （18)READ（*，（A)BUFFER （19）NEXT1 （20) END IF （21）PRDUCEBUFFER（NEXT：NEXT） （22 ) NEXTNEXT1 （23)END 圖6.8 一個Fortran 77程序 3

17、0CNSUME目標(biāo)代碼PRDUCE目標(biāo)代碼Char *50 buf int next char cChar *80 buffer int next Cnsume活動記錄prduce活動記錄目標(biāo)代碼靜態(tài)數(shù)據(jù)316.3.2 棧式存儲分配 基于控制棧的原理：存儲空間被組織成棧，活動記錄的推入和彈出分別對應(yīng)于活動的開始和結(jié)束。 與靜態(tài)分配不同的是，在每次活動中把局部名字和新的存儲單元綁定，在活動結(jié)束時，活動記錄從棧中彈出，因而局部名字的存儲空間也隨之消失。 例6.5 圖6.11表明當(dāng)控制流通過圖6.3的活動樹時活動記錄被推人或彈出運行時刻的棧中的情況，設(shè)寄存器top標(biāo)記棧頂。32sSa:arrayto

18、prri:integertoptopq(1,9)q(1,9)i:integertopp(1,9)p(1,9)i:integertoptopq(1,3)q(1,3)i:integertop圖 6.11 棧式分配活動記錄在棧中的變化33 確定活動記錄中局部數(shù)據(jù)的地址：假設(shè)top-sp標(biāo)記一個活動記錄的開始的位置， dx表示x的地址相對于top-sp的偏移量。那么， x在過程的目標(biāo)代碼中的地址可寫成 dx（top-sp）在運行時刻，當(dāng)把x的活動記錄筑于棧頂時，寄存器top- sp被賦于實際的地址， top- sp可以是一個寄存器。調(diào)用序列和返回序列 通過在目標(biāo)代碼中生成調(diào)用序列和返回序列實現(xiàn)過程的調(diào)

19、用。激活一個過程的活動是執(zhí)行34過程語句的結(jié)果。過程語句 p(e1,e2,en)的目標(biāo)代碼（調(diào)用序列）完成任務(wù)： 1. 調(diào)用者對實在參數(shù)求值，并把它們傳送給 被調(diào)用過程的活動記錄的參數(shù)域。 2調(diào)用者在被調(diào)用者的活動記錄中存放返 回地址和老top-sp之值。之后調(diào)用者把 top一sp之值增加到圖6.12所示的位置。 3被調(diào)用者存放寄存器值和其它狀態(tài)信息。 4被調(diào)用者初始化其局部數(shù)據(jù)并開始執(zhí)行。35返回序列，return目標(biāo)代碼完成的任務(wù)是： 1被調(diào)用者在自己的活動記錄的返回值域 中放一個返回值。 2利用狀態(tài)域中的信息，被調(diào)用者恢復(fù) top-sp和其它寄存器，并且按返回地址轉(zhuǎn) 移到調(diào)用者的代碼之中

20、。 3調(diào)用者復(fù)制返回值到自己的活動記錄中。 任務(wù)的劃分，根據(jù)源語言、目標(biāo)機器和操 作系統(tǒng)等具體情況而定。 上述任務(wù)，由運行支持子程序完成，可視為虛機指令。36可變長度的數(shù)據(jù) 源程序的例子 PROCEDURE exam(l,m,n:integer); VAR a:array 1.l of real; b:array 1.m of real; c:array 1.n of real; BEGIN END; 編譯時，不知 a,b,c的大小，僅對每個數(shù)組設(shè)置一個指針。37Control linkabcTop-sptopArray aArray bArray ctopP的活動記錄P的動態(tài)數(shù)組圖6.13

21、動態(tài)分配的數(shù)組38活動記錄的進棧和推棧 棧頂活動記錄用兩個指針top和top-sp指示。top-sp指向棧頂活動記錄保存機器狀態(tài)域的末 端，用于訪問局部數(shù)據(jù)。top指向棧頂。P調(diào)用q：棧top+h:=top-sp; top-sp:=top+h; top:=top+q的活動記錄長度從q的活動返回：top:=top-spq (h) top-sp:=棧top-sp39pqtop-sptop-sptoptoph406.3.3 堆式存儲分配 1局部名的值在活動結(jié)束時必須被保存。 2. 被調(diào)用者的活動生存期超過調(diào)用者。 用活動樹不能夠正確描繪這種語言的過 程之間的控制流。 new(p); dispose(

22、p);416.4 對非局部名字的訪問 討論基于活動記錄的棧式分配。 一個語言所規(guī)定的作用域規(guī)則決定了如何處理對非局部名字的引用。 有靜態(tài)和動態(tài)兩種作用域規(guī)則。 靜態(tài):考查程序正文來決定引用的名字是哪一個名字說明,如Pascal，C和Ada是眾多語言中使用帶有“最近嵌套”規(guī)定的詞法作用域規(guī)則的語言 ; 動態(tài):在運行時刻考查最近的活動來決定應(yīng)用到一個名字上的說明,如LISP和APL。 426.4.1 塊 一個塊（Block）是一個含有局部數(shù)據(jù)說明的語句。 declarationsstatements 一個塊與另一個塊要么是獨立的，要么 一 個塊完全嵌入在另一個塊之中，這種嵌套的性質(zhì)有時稱作塊結(jié)構(gòu)。

23、 在塊結(jié)構(gòu)語言中，說明的作用域由最近嵌套規(guī)則給出： 1在塊B中的一個說明的作用域包括B。 2如果名字x在塊B中沒有說明，那么，43 x在B中的出現(xiàn)是在一個外圍塊B中的x的說 明的作用域之內(nèi)，并且使得： （a) B 中有x 的說明， （b) B 是包圍B的，相對于其它任何具有 名字x 的說明且包圍B 的塊而言,B是 離B 最近的。 對于pascal語言來說，一個過程是一個塊，一個程序是一個塊結(jié)構(gòu)。而對于c語言來說，每個函數(shù)是一個塊結(jié)構(gòu)，而函數(shù)之間是不嵌套的。44main( ) int a=0; /*B0-B2*/ int b=0; /* B0-B1 */ int b=1; /* B1-B3 */

24、 int a=2; printf(“%d%d/n”,a,b) ; int b=3; printf(“%d%d/n”,a,b) ; printf(“%d%d/n”,a,b) ; printf(“%d%d/n”,a,b) ; B0B1B2B345a0b0b1a2 , b3 圖6.16 函數(shù)main局部數(shù)據(jù) 在活 動記錄中的按排 塊結(jié)構(gòu)語言可以采用棧式分配。函數(shù)main的每個塊可看成一個無參過程，塊中的塊可被看成一個語句?？刂茝膲K開始進入，遇塊結(jié)束退出。B2和B3的生存期不相交，它們的局部數(shù)據(jù)可占用同一塊存儲空間。466.4.2 不含嵌套過程的詞法作用域 C中過程定義不能嵌套 （l）int a11;

25、 （2） readarray( ) a （3） int partition（y，z） int y，z； a （4） quicksort（m，n） int m，n； . （5） main( ) .a. 圖6.17 帶有a的非局部出現(xiàn)的C程序 47目標(biāo)代碼 int a11棧堆1.函數(shù)外的數(shù)據(jù)和函數(shù)內(nèi) 的靜態(tài)數(shù)據(jù)，靜態(tài)分配 于靜態(tài)數(shù)據(jù)域。2 .函數(shù)內(nèi)的數(shù)據(jù)（out) 棧 式分配,運行進入任一 函 數(shù)，使用的 數(shù)據(jù)，要 么 在 當(dāng)前的活動記錄中； 要么在 靜態(tài)數(shù)據(jù)域中。486.4.3 含有嵌套過程的詞法作用域 圖6.18 帶有嵌套過程的一個Pascal程序程序的靜態(tài)嵌套結(jié)構(gòu)： sort readarr

26、ay exchange quicksort partition 49（1） program sort（input，output）;（2） var a： array0.10 of integer； （3） x : integer； （4） procedure readarray； （5） var i ： integer； （6） begin a end readarray; （7） procedure exchange（i，j： integer）； （8） begin （9） x：= ai ；ai:=aj; aj:x （10） end exchange; 50（11） procedure qui

27、cksort（m，n： integer）； （12） var k，v： integer； （13） function partition（y，z： integer） ： integer； （14） var i，j ： integer； （15） begin a （16） V （17） exchange（i，j）； （18） end partition; （19） begin end quicksort; （20） begin end. sort51 程序的靜態(tài)嵌套結(jié)構(gòu)決定程序中每個過程中訪問哪些外圍過程中的數(shù)據(jù)。 每個過程靜態(tài)嵌套在哪些過程中，可用靜態(tài)鏈static(p)表示: static(

28、sort)=sort static(readarray)=sort readarray static(exchange)=sort exchange static(quichsort)=sort quichsort static(partition)=sort quichsort partition 運行時，過程的數(shù)據(jù)被組織成活動記錄，為了實現(xiàn)非局部訪問，過程的活動記錄之間必須維持靜態(tài)鏈反映程序的靜態(tài)嵌套結(jié)構(gòu)。52 6.4.3.1 嵌套深度 用過程的嵌套深度來表達一個過程在程序中的嵌套層次。令主程序的嵌套深度為1；從一個過程進入到一個被包圍過程時嵌套深度加1。如圖6.18中的位于（11）行上的

29、過程quicksort的嵌套深度為2，而（13）行上的partition的嵌套深度為3。 過程表示除過程名字之外的過程定義正文。 一個名字的嵌套深度等于說明它的過程的嵌套深度，是名字的重要屬性。在（15）（17）行上的partition中的a,v和i的嵌套深度分別是1，2和3。 53 6.4.3.2 存取鏈（access link） 棧中的活動記錄應(yīng)反映源程序正文中過程之間的嵌套關(guān)系，或靜態(tài)結(jié)構(gòu)。為每一個活動記錄增設(shè)一個稱為存取鏈（或存取鏈路）的指針，如果在源程序正文中過程p直接嵌入在過程q中，那么p的一個活動記錄中的存取鏈指向q的最近的活動記錄中的存取鏈。從當(dāng)前活動記錄開始，沿著這條鏈，能找

30、到訪問的非局部名字。它是靜態(tài)鏈在存儲空間上的實現(xiàn)，也稱作靜態(tài)鏈。 程序運行過程中應(yīng)維持這條鏈。54S S nil a , xtop-sptopr r itoptop-sptop-sptopq(1,9) q(1,9) k , vtoptop-spp(1,9) p(1,9) i , jtoptop-sptop-sptopq(1,3) q(1,3) k , vtoptop-spp(1,3) p(1,3) i , jtoptop-spe(1,3) e(1,3) i , jtoptop-sp圖 6.1955非局部訪問 在嵌套深度為np 的過程p中引用一個嵌套深度為na np 的非局部名字a,a的存儲位置

31、可按下面的步驟找到： 1從棧頂活動記錄出發(fā)沿存取鏈前進npna步，到達a所在的活動記錄。npna的值可在編譯時刻計算出來。 2a的地址= a所在活動記錄的始址+ a的偏移量。編譯生成過程p的目標(biāo)代碼中非局部名字a的地址表示為： （npna ，a在其活動記錄中的偏移量) 56運行時存取鏈的維護 維護存取鏈的代碼是調(diào)用序列的一部分。 假設(shè)嵌套深度為np 的過程p調(diào)用嵌套深度為nx 的過程x。存取鏈的維護依賴于過程p和過程x之間的嵌套關(guān)系。 1.np nx ， nx=np+1, x 在p中定義。 被調(diào)用過程的活動記錄的存取鏈必須指向棧中剛好在其前面的（地址碼較低的）調(diào)用過程的活動記錄的存取鏈。 57

32、p x call xptop-sptopxtop-sptop棧top+h:=top-sp;top-sp:=top+h;top:=top+x的活動 記錄長度；582. npnxxPcall x np=nxpx59call xxpx pcall xpxnpnx60 過程p和x的嵌套深度為1，2， ,nx-1的外圍過程是相同的。 從p的活動記錄開始沿存取鏈前進np-nx+1步，可到達包圍著p和x且離它們最近的過程的當(dāng)前的活動記錄。這個活動記錄的存取鏈位置即是x的當(dāng)前活動記錄存取鏈應(yīng)指向的位置。 np-nx+1在編譯時能計算出來。61過程作為參數(shù)傳遞的實現(xiàn) PROGRAM param(input,ou

33、tput); PROCEDURE b(FUN h(n:integer):integer); BEGIN writeln(h(2) END; PROCEDURE c; VAR m: integer; FUNCTION f(n:integer):integer; BEGIN f:=m+n END; BEGIN m:=0; b(f) END; BEGIN c END. 62paramcm:=0b( f )存取鏈f( 2 )如何建立存取鏈？ 過程要在定義它的環(huán)境中運行。過程作為實參數(shù)傳遞時，必須把它的存取鏈作為實參數(shù)的一部分傳遞。 在傳遞f時，確定f的存取鏈，好象在c中調(diào)用f一樣。 在b中激活f的活動

34、時，它作為f的活動記錄的存取鏈。636.4.3.3 Display表 Display表是一個指針數(shù)組d，在運行過程中，若當(dāng)前活動的過程的嵌套深度為i，則di中存放當(dāng)前的活動記錄地址，di-1,di-2, ,d1 中依次存放著當(dāng)前活動的過程的直接外層， , 直至最外層（主程序）等每一層過程的最新活動地址。 這樣，嵌套深度為j的變量a存放在由dj所指出的活動記錄中。 在運行過程中維持一個Display表實現(xiàn)非局部訪問比存取鏈效率要高。64Display表的維護（過程不作為參數(shù)傳遞） 當(dāng)嵌套深度為i的過程的活動記錄筑在棧頂時： （1）在新的活動記錄中保存di的值； （2）置di指向新的活動記錄。 在

35、一個活動結(jié)束前， di置成保存的舊值。用Display表如何訪問非局部量？ 1. Display表是一個數(shù)組，開始地址用通用 寄存器指出； 2. Display表由一組寄存器實現(xiàn)。65sSa, xdisplayrrq(1,9)q(1,9)k, vp(1,9)p(1,9)e(1,9) e(1,9) save d2q(1,3) q(1,3) save d2k, vp(1,3) p(1,3) save d3i, j圖 6.1966設(shè)p （嵌套深度為j）調(diào)用q（嵌套深度為i）1. ji qd1d2di-1diPqpcall qSave diPcall qqdjSave dj696.4.4 動態(tài)作用域

36、程序運行時，一個名字a實施其影響，直到含a的聲明的一個過程開始執(zhí)行時暫停，此過程停止時，該影響恢復(fù)。 設(shè)有下面的的調(diào)用序列： A B C P過程P中有對x的非局部引用，沿動態(tài)鏈（紅鏈）查找，最先找到的便是。70 program dynamic（input，output)； var r：real； procudure show； begin wtite（r： 5：3 ） end； procedute small； var r： real； begin r: 0.125； show end； begin r：0.25； show； small； write1n； show； small； writ

37、eln end.71 在詞法作用域之下，程序的輸出為 : 0.250 0.250 0.250 0.250 在動態(tài)作用域之下，輸出為: 0.250 0.125 0.250 0.125 實現(xiàn)動態(tài)作用域的方法: 1.深訪問。使用控制鏈在棧中搜索，以尋 找包含所需非局部名字的存儲單元的第 一個活動記錄（控制鏈又稱動態(tài)鏈）。722淺訪問。這種方法的思想是在靜態(tài)分配 的存儲空間中存放每一個名字的現(xiàn)行值。 當(dāng)過程p開始一次新的活動時，p中的非局 部名n占用對于n靜態(tài)分配的存儲空間。先 前的n值可以存放在p的活動記錄中并且當(dāng) p的活動記錄結(jié)束時必須給以恢復(fù)。 兩種方法進行比較。736.5 參數(shù)傳遞 實在參數(shù)和

38、形式參數(shù)結(jié)合的方法： 傳值調(diào)用（call-by-value） 引用調(diào)用（call-by-reference） 復(fù)制恢復(fù)（copy-restore） 傳名調(diào)用（call-by-name） ai:=aj 其中表達式aj代表一個值，而ai 則表示一個存儲地址。 參數(shù)傳遞方法之間的區(qū)別主要基于實在參數(shù)是代表右-值（r-值）、左-值（l-值）、 或者實在參數(shù)的正文本身。746.5.1 傳值調(diào)用 program reference（input，output）； var a，b ： integer； procedure swap（x，y： integer）； var temp： integer； begin temp :x； x ：y； y ：temp end; begin a：1; b：2; swap(a，b); writeln( a=，a， b= ,b ） end.75傳值調(diào)用可以實現(xiàn)如下： 調(diào)用過程計算實在參數(shù)，并把它們的右- 值放入到形式參數(shù)的存儲空間中。 使用傳值的方法，調(diào)用swap（a,b）等價于下面幾步： x：= a y：= b temp：= x x：= y y：= temp 766.5.2 引用調(diào)用 把實在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù), 在目標(biāo)代碼中，在被調(diào)用過程中對形式參數(shù)的一次引用就成為對傳遞給被調(diào)用過程的指