山東大學(xué)編譯原理Chapter7-RuntimeEnvironments

1、Chapter 7 Runtime Environments一個程序要運行，至少應(yīng)有這樣兩個存儲空間：(1) 代碼空間這是經(jīng)翻譯后生成的目標(biāo)代碼的存儲區(qū)域，線性存放著目標(biāo)指令序列。對三地址代碼來說，當(dāng)前執(zhí)行的指令位置由指令指針ip指示。因此，只要將ip指向程序的第一個語句，程序便處于開始執(zhí)行的狀態(tài)，以后每執(zhí)行一個語句，ip便加4(我們約定，三地址代碼的每個語句占4個字節(jié))，指向下個語句。要改變程序控制順序，只要將轉(zhuǎn)向點賦給ip即可。(2) 數(shù)據(jù)空間每個程序都定義一定數(shù)量的各種類型的變量和常數(shù)，翻譯程序必須為之分配相應(yīng)的存儲空間。初等類型的數(shù)據(jù)，如邏輯、整型、實型變量，通常以存儲器的基本存儲單元

2、如字節(jié)、字、雙字來存儲。Chapter 7 Runtime Environments 7.1 Source Language IssuesProgram vs program execution A program consists of several procedures (functions) An execution of a program is called as a process An execution of a program would cause the activation of the related procedures A name (e.g, a variab

3、le name)in a procedure would be related to different data objectsNotes: An activation may manipulate data objects allocated for its use.Chapter 7 Runtime Environments 7.1 Source Language Issues Allocation and de-allocation of data objects Managed by the run-time support package Allocation of a data

4、object is just to allocate storage space to the data object relating to the name in the procedure Notes: The representation of a data object at run time is determined by its type.Chapter 7 Runtime Environments 7.1 Source Language Issues A procedure is activated when called The lifetime of an activat

5、ion of a procedure is the sequence of steps between the first and last steps in the execution of the procedure body A procedure is recursive if a new activation can begin before an earlier activation of the same procedure has endedChapter 7 Runtime Environments 7.1 Source Language Issues3.Activation

6、 Trees A tree to depict the control flow enters and leaves activation of a procedure f(4) f(3) f(2) f(2) f(1) f(1) f(0) f(1) f(0) Enter f(4)Enter f(3)Enter f(2)Enter f(1)Leave f(1)Enter f(0)Leave f(0)Leave f(2)Enter f(1)Leave f(1)Leave f(3)Enter f(2)Enter f(1)Leave f(1)Enter f(0)Leave f(0)Leave f(2)

7、Leave f(4)Procedure Activations: Exampleprogram sort(input, output) var a : array 0.10 of integer; procedure readarray; var i : integer; begin for 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

8、: integer; begin if (n m) then begin i := partition(m, n); quicksort(m, i - 1); quicksort(i + 1, n) end end; begin a0 := -9999; a10 := 9999; readarray; quicksort(1, 9) end.Activations:begin sort enter readarray leave readarray enter quicksort(1,9) enter partition(1,9) leave partition(1,9) enter quic

9、ksort(1,3) leave quicksort(1,3) enter quicksort(5,9) leave quicksort(5,9) leave quicksort(1,9)end sort.Activation Trees: Examplesq(1,9)q(1,3)p(1,3)q(1,0) q(2,3)q(2,1)p(2,3)q(3,3)p(1,9)rq(5,9)p(5,9)q(5,5) q(7,9)q(7,7)p(7,9)q(9,9)Activation tree for the sort programNote: also referred to as the dynami

10、c call graphChapter 7 Runtime Environments 7.1 Source Language Issues4.Control stacks A stack to keep track of live procedure activationsChapter 7 Runtime Environments 7.1 Source Language Issues Control Stacksq(1,9)q(1,3)p(1,3)q(1,0) q(2,3)p(1,9)rActivations:begin sort enter readarray leave readarra

11、y enter quicksort(1,9) enter partition(1,9) leave partition(1,9) enter quicksort(1,3) enter partition(1,3) leave partition(1,3) enter quicksort(1,0) leave quicksort(1,0) enter quicksort(2,3) Controlstack:Activation tree:sq(1,9)q(1,3)q(2,3)Scope Rules Environment determines name-to-object bindings: w

12、hich objects are in scope?program prg; var y : real;function x(a : real) : real; begin end;procedure p; var x : integer; begin x := 1; end;begin y := x(0.0); end.Variable x locally declared in pA function xChapter 7 Runtime Environments 7.1 Source Language IssuesBindings of Names When an environment

13、 associates storage location s with a name x, we say that x is bound to s; the association itself is referred to as a binding of x. Notes: 1)Even each name is declared once in a program, the same name may denote different object at run time 2)The “ data object” corresponds to a storage location that

14、 can hold valuesChapter 7 Runtime EnvironmentsBindings of NamesNotes: 3)In programming language semantics, the term “environment” refers to a function that maps a name to a storage location, and term “state” refers to a function that maps a storage location to the value held there. environment state

15、 name storage value Chapter 7 Runtime Environments5.Bindings of NamesNotes: 4)Environments and states are different; an assignment changes the state, but not the environment 5)If x is not of a basic type, the storage s for x may be a collection of memory words 6)A binding is the dynamic counterpart

16、of a declarationChapter 7 Runtime Environments6.Factors that determines the run time environment of a program Recursive definition Local name storage space allocation strategy global name storage space allocation strategy Parameter passing mechanism A function is whether allowed to be a parameter of

17、 or return value of a functionChapter 7 Runtime Environments 7.2Storage organization1.Subdivision of Runtime MemoryTypical subdivision of runtime memory into code and data areascodeStatic datastackheapThe generated target code;Data objects;A counterpart of the control stack to keep track of procedur

18、e activations Chapter 7 Runtime Environments 7.2Storage organization2.Activation Records/Frames1) Definition A contiguous block of storage that stores information needed by a single execution of a procedureChapter 7 Runtime Environments 7.2Storage organization2.Activation Records2) A general activat

19、ion recordReturned valueActual parametersOptional control linkOptional access linkSaved machine statusLocal datatemporariesControl LinksfpspControl linkStackgrowthCallees activation recordCallers activation recordThe control link is the old value of the fp活動記錄活動記錄（1）臨時數(shù)據(jù)域臨時數(shù)據(jù)域 如計算表達(dá)式出現(xiàn)的中間結(jié)果，若如計算表達(dá)式出

20、現(xiàn)的中間結(jié)果，若寄存器不足以存放所有這些中間結(jié)果時，可以把它寄存器不足以存放所有這些中間結(jié)果時，可以把它們存放在臨時數(shù)據(jù)域中。們存放在臨時數(shù)據(jù)域中。（2）局部數(shù)據(jù)域局部數(shù)據(jù)域 保存局部于過程執(zhí)行的數(shù)據(jù)，這保存局部于過程執(zhí)行的數(shù)據(jù)，這個域的布局在下面討論。個域的布局在下面討論。（3）機器狀態(tài)域機器狀態(tài)域 保存剛好在過程調(diào)用前的機器狀保存剛好在過程調(diào)用前的機器狀態(tài)信息，包括程序計數(shù)器的值和控制從這個過程返態(tài)信息，包括程序計數(shù)器的值和控制從這個過程返回時必須恢復(fù)的機器寄存器的值?；貢r必須恢復(fù)的機器寄存器的值。（4）訪問鏈訪問鏈 Pascal語言需要用訪問鏈來訪問非局語言需要用訪問鏈來訪問非局部數(shù)據(jù)，

21、我們在部數(shù)據(jù)，我們在6.3節(jié)介紹。像節(jié)介紹。像Fortran和和C這樣的語這樣的語言不需要訪問鏈，因為全局?jǐn)?shù)據(jù)保存在固定的地方。言不需要訪問鏈，因為全局?jǐn)?shù)據(jù)保存在固定的地方。訪問鏈也稱為靜態(tài)鏈。訪問鏈也稱為靜態(tài)鏈?；顒佑涗浕顒佑涗洠?）控制鏈控制鏈 用來指向調(diào)用者的活動記錄。用來指向調(diào)用者的活動記錄。控制鏈也稱為動態(tài)鏈。控制鏈也稱為動態(tài)鏈。（6）參數(shù)域參數(shù)域 用于存放調(diào)用過程提供的實在用于存放調(diào)用過程提供的實在參數(shù)。為提高效率，實際上常常用寄存器傳參數(shù)。為提高效率，實際上常常用寄存器傳遞參數(shù)。遞參數(shù)。（7）返回值域返回值域 用于存放被調(diào)用過程返回給用于存放被調(diào)用過程返回給調(diào)用過程的值。為提高效

22、率，這個值也常常調(diào)用過程的值。為提高效率，這個值也常常用寄存器返回。用寄存器返回。 編譯時局部數(shù)據(jù)的安排編譯時局部數(shù)據(jù)的安排 字節(jié)是可編址內(nèi)存的最小單位。字節(jié)是可編址內(nèi)存的最小單位。 變量所需的存儲空間可以根據(jù)其類型而靜態(tài)變量所需的存儲空間可以根據(jù)其類型而靜態(tài)確定。確定。 一個過程所聲明的局部變量，按這些變量聲一個過程所聲明的局部變量，按這些變量聲明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間?？臻g。 局部數(shù)據(jù)的地址可以用相對于某個位置的地局部數(shù)據(jù)的地址可以用相對于某個位置的地址來表示。址來表示。 數(shù)據(jù)對象的存儲安排還有一個對齊問題。數(shù)據(jù)對象的存儲安排還有一個

23、對齊問題。Chapter 7 Runtime Environments 7.3 Storage allocation strategies1.Storage allocation strategies Static allocation Lays out storage for all data objects at compile time. Stack allocation Manages the run-time storage as a stack. Heap allocation Allocates and de-allocates storage as needed at run

24、time from a heap.Chapter 7 Runtime Environments 7.3 Storage allocation strategies2.Static allocation The size of a data object and constraints on its position in memory must be known at compile time. Recursive procedures are restricted. Data structures cannot be created dynamically. Fortran permits

25、static storage allocationStatic allocation(1)(1)program consumeprogram consume(2)(2)charactercharacter 50 buffer50 buffer(3)(3)integer nextinteger next(4)(4)character c, producecharacter c, produce(5)(5)data next /1/, buffer / /data next /1/, buffer / /(6) 6(6) 6c = produce ()c = produce ()(7)(7)buf

26、fer(next : next) = cbuffer(next : next) = c(8)(8)next = next + 1next = next + 1(9)(9)if (c .ne. ) goto 6if (c .ne. ) goto 6(10)(10)write(write( , (A) buffer, (A) buffer(11)(11)endendStatic allocation(12)(12)character function produce()character function produce()(13)(13)charactercharacter 80 buffer8

27、0 buffer(14)(14)integer nextinteger next(15)(15)save buffer, nextsave buffer, next(16)(16)data next /81/data next /81/(17)(17)if (next .gt. 80) thenif (next .gt. 80) then(18)(18)read (read ( , (A) buffer, (A) buffer(19)(19)next = 1next = 1(20)(20)end ifend if(21)(21)produce = buffer(next : next)prod

28、uce = buffer(next : next)(22)(22)next = next + 1next = next + 1(23)(23) endendStatic allocationFortran語言被設(shè)計成允許靜態(tài)存儲分配語言被設(shè)計成允許靜態(tài)存儲分配consume的代碼的代碼produce的代碼的代碼character 50 bufferinteger nextcharacter ccharacter 80 bufferinteger nextproduce的活動記錄的活動記錄consume的活動記錄的活動記錄靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)代碼代碼Chapter 7 Runtime Environ

29、ments 7.3 Storage allocation strategies3.Heap allocation A separate area of run-time memory, called a heap. Heap allocation parcels out pieces of contiguous storage, as needed for activation records or other objects. Pieces may be de-allocated in any order.Chapter 7 Runtime Environments 7.3 Storage

30、allocation strategies4. Stack allocation1)Main idea Based on the idea of a control stack; storage is organized as a stack, and activation records are pushed and popped as activations begin and end, respectively. Storage for the locals in each call of a procedure is contained in the activation record

31、 for that call. Locals are bound to fresh storage in each activationChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation2)Calling sequences A call sequence allocates an activation record and enters information into its fields A return sequence restores the state of the

32、 machine so the calling procedure can continue execution.e.g. the calling sequence is like the following:main () q( ); p( ) q( ) p( ); Activation record for mainActivation record for QActivation record for PTOPTop-SPChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation2

33、)Calling sequencesSteps: (1)The caller evaluates actual parameters.(2)The caller stores a return address and the old value of top-sp into the callees activation record.(3)The callee saves register values and other status information(4)the callee initializes its local data and begins execution.Chapte

34、r 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation2)calling sequencesA possible return sequence : (1)The callee places a return value next to the activation record of the caller (2)Using the information in the status field, the callee restores top-sp and other registers an

35、d branches to a return address in the callers code. (3)Although top-sp has been decremented, the caller can copy the returned value into its own activation record and use it to evaluate an expression.Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation3)Stack allocatio

36、n for non-nested procedure Stack allocation for C When entering a procedure, the activation record of the procedure is set up on the top of the stack Initially, put the global(static) variables and the activation record of the Main functionChapter 7 Runtime Environments 7.3 Storage allocation strate

37、gies4. Stack allocation3)Stack allocation for non-nested procedureMain AR Q ARP ARTOPSPglobal VarChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation3)Stack allocation for non-nested procedureCallers SPCalling Return addressAmount of parametersFormal parametersLocal da

38、ta Array dataTemporariesReturned valueChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation3)Stack allocation for non-nested procedure #include int i,j; void main() int k,l; cinl; k=p(l); coutk; Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack al

39、location3)Stack allocation for non-nested procedure #include int i,j; int p(int m) int t; if (m=0 | m=1) return(1); else t=m*p(m-1); return(t); Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(1) the nesting of procedure defi

40、nitions in the Pascal programP0P1P2Call P2Call P1P0P1P2Call P2Call P1Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(2) nesting depthi1P0Pi-1Pii0Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack alloca

41、tion4)Stack allocation for nested procedures(3) access linksP0P1P2Call P2Call P1TOPTop-SPP2P1P0Access linkAccess linkAccess linkChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(3) access linksTOPTop-SPP2P1P0Access linkAccess

42、linkAccess linkP0P1P2Call P2Call P1Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(4) displays Faster access to global than with access links can be obtained using an array d of pointers to activation records, called a displ

43、ay.Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(4) displays Suppose control is in an activation of a procedure pj at nesting depth j, then the display of activation of pj is:j1Sp for p0Sp for pj-1Sp for pjj0dj+1Chapter 7

44、Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(4) displays When a new activation record for a procedure at nesting depth i is setup, we A) save the value of di in the new activation record; B) set di to point to the new activation re

45、cord.Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(5) non-displays non-display of current procedure =non-display of caller+start address of current local activation recordChapter 7 Runtime Environments 7.3 Storage allocati

46、on strategies4. Stack allocation4)Stack allocation for nested proceduresCallers SPCalling Return addressAmount of parametersFormal parametersLocal data Array dataTemporariesReturned valueLocal displayglobal displayChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)S

47、tack allocation for nested proceduresProgram M; var A,B:integer function F(N:integer):integer; if N=2 then teturn(N) else return (N*F(N-1); begin read(A); /*Let A=5*/ B:=F(A); write (B); end.K+11K+6Local D+12Returned value from F+13K+6(SP1)+14Returned address+15K+11Global D+161Number of P+174Formal

48、P N+18K+19K+14Loc D+20Returned value from F+21Global D4K5K+1D+2A+3B+4Returned value from F+5K(SP0)+6Returned address+7K+2+81Number of P+9Formal P N+10Chapter 7 Runtime Environments 7.4 Access to Nonlocal Names語言的作用域規(guī)則規(guī)定了如何處理非局部名字語言的作用域規(guī)則規(guī)定了如何處理非局部名字的訪問。一種常用的規(guī)則叫做的訪問。一種常用的規(guī)則叫做詞法作用域詞法作用域或或靜態(tài)作用域靜態(tài)作用域規(guī)則，

49、它僅根據(jù)程序正文靜態(tài)地規(guī)則，它僅根據(jù)程序正文靜態(tài)地確定用于名字的聲明。許多語言，如確定用于名字的聲明。許多語言，如PascalPascal，C C和和AdaAda，都使用靜態(tài)作用域規(guī)則。我們首先，都使用靜態(tài)作用域規(guī)則。我們首先考慮考慮C C語言那樣的非局部名字。由于語言那樣的非局部名字。由于C C語言不語言不允許嵌套的過程聲明，因此所有的非局部名允許嵌套的過程聲明，因此所有的非局部名字都可以靜態(tài)地綁定到所分配的存儲單元。字都可以靜態(tài)地綁定到所分配的存儲單元。 Chapter 7 Runtime Environments 7.4 Access to Nonlocal Names7.4.1 程序塊

50、程序塊有局部數(shù)據(jù)的語句有局部數(shù)據(jù)的語句7.4.2 無過程嵌套的靜態(tài)作用域無過程嵌套的靜態(tài)作用域 過程體中的非局部引用可以直接使用靜態(tài)確過程體中的非局部引用可以直接使用靜態(tài)確定的地址定的地址 局部變量在棧頂?shù)幕顒佑涗浿校梢酝ㄟ^局部變量在棧頂?shù)幕顒佑涗浿?，可以通過basebase_ _spsp指針來訪問指針來訪問 無須深入棧中取數(shù)據(jù)，無須訪問鏈無須深入棧中取數(shù)據(jù)，無須訪問鏈 過程可以作為參數(shù)來傳遞，也可以作為結(jié)果過程可以作為參數(shù)來傳遞，也可以作為結(jié)果來返回來返回7.4 Access to Nonlocal NamesC語言的函數(shù)聲明不能嵌套，函數(shù)不論在什語言的函數(shù)聲明不能嵌套，函數(shù)不論在什么情況

51、下激活，要訪問的數(shù)據(jù)分成兩種情況么情況下激活，要訪問的數(shù)據(jù)分成兩種情況: : 非靜態(tài)局部變量（包括形式參數(shù)），它們分非靜態(tài)局部變量（包括形式參數(shù)），它們分配在活動記錄棧頂?shù)哪莻€活動記錄中配在活動記錄棧頂?shù)哪莻€活動記錄中 外部變量（包括定義在其它源文件中的外部外部變量（包括定義在其它源文件中的外部變量）和靜態(tài)的局部變量，它們都分配在靜變量）和靜態(tài)的局部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)態(tài)數(shù)據(jù)區(qū) 全局?jǐn)?shù)據(jù)說明全局?jǐn)?shù)據(jù)說明Main( ) Main中的數(shù)據(jù)說明中的數(shù)據(jù)說明 void R( ) R中的數(shù)據(jù)說明中的數(shù)據(jù)說明void Q( ) Q中的數(shù)據(jù)說明中的數(shù)據(jù)說明 主程序主程序過程過程Q 過程過程RQ的活動

52、記錄的活動記錄主程序活動記錄主程序活動記錄TOPR的活動記錄的活動記錄SP參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老老SP臨時單元臨時單元全局?jǐn)?shù)據(jù)區(qū)全局?jǐn)?shù)據(jù)區(qū) 每個過程的活動記錄內(nèi)容如圖每個過程的活動記錄內(nèi)容如圖:對任何局部變量對任何局部變量X的的引用可表示為變址訪引用可表示為變址訪問問: dxSP dx: 變量變量X相對于活相對于活動記錄起點的地址，動記錄起點的地址，在編譯時可確定。在編譯時可確定。參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元臨時單元臨時單元內(nèi)情向量內(nèi)情向量局部變量局部變量SP 012老老SPTOP 9.4.2 C的活動記錄的活動記

53、錄 過程調(diào)用的四元式序列過程調(diào)用的四元式序列:par T1par T2 par Tncall P，n9.4.2 C的過程調(diào)用、過程進(jìn)入、數(shù)組空的過程調(diào)用、過程進(jìn)入、數(shù)組空間分配和過程返回間分配和過程返回 1) 每個每個par Ti(i=1,2,n)可直接翻譯成如下指令可直接翻譯成如下指令:(i+3)TOP:= Ti (傳值傳值)(i+3)TOP:=addr(Ti) (傳地址傳地址)2) call P，n 被翻譯成被翻譯成:1TOP:=SP (保護(hù)現(xiàn)行保護(hù)現(xiàn)行SP)3TOP:=n (傳遞參數(shù)個數(shù)傳遞參數(shù)個數(shù))JSR P (轉(zhuǎn)子指令轉(zhuǎn)子指令)參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量

54、內(nèi)情向量局部變量局部變量老老SP臨時單元臨時單元對于對于par和和call產(chǎn)生的目標(biāo)代碼如下產(chǎn)生的目標(biāo)代碼如下:TOP SP 調(diào)用過程的調(diào)用過程的活動記錄活動記錄形式單元形式單元老老SP參數(shù)個數(shù)參數(shù)個數(shù)3) 轉(zhuǎn)進(jìn)過程轉(zhuǎn)進(jìn)過程P后，首先應(yīng)執(zhí)行下述指令后，首先應(yīng)執(zhí)行下述指令:SP:=TOP+1 (定義新的定義新的SP)1SP:=返回地址返回地址 (保護(hù)返回地址保護(hù)返回地址)TOP:=TOP+L (新新TOP) L：過程過程P的活動記錄所需單元數(shù)，的活動記錄所需單元數(shù)， 在編譯時可確定。在編譯時可確定。 參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老老SP臨時單元

55、臨時單元TOP 調(diào)用過程的活動記錄調(diào)用過程的活動記錄返回地址返回地址TOPSP4) 過程返回時，應(yīng)執(zhí)行下列指令過程返回時，應(yīng)執(zhí)行下列指令:TOP:=SP-1 (恢復(fù)調(diào)用前恢復(fù)調(diào)用前TOP)SP:=0SP (恢復(fù)調(diào)用前恢復(fù)調(diào)用前SP)X:=2TOP (把返回地址取到把返回地址取到X中中)UJ 0X (按按X返回返回)參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量內(nèi)情向量局部變量局部變量老老SP臨時單元臨時單元調(diào)用過程的活動記錄調(diào)用過程的活動記錄TOPSPSPTOP7.4.3 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域(1)program sort(input, output);(2)

56、var a: array0.10 of integer;(3)x: integer;(4)procedure readarray;(5)var i: integer;(6)begin a endreadarray;(7)procedure exchange(i, j : integer);(8)begin(9)x := ai; ai := aj; aj := x(10)endexchange;7.4.3 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域(11)procedurequicksort(m,n: integer);(12)var k, v: integer;(13)function pa

57、rtition(y, z: integer): integer;(14)var i, j: integer;(15)begin a (16) v ( 1 7 ) exchange(i, j); (18)endpartition;(19)begin endquicksort;(20)begin endsort.7.4.3 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域7.4.3.1 7.4.3.1 過程過程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition3變量的嵌套深度：它的聲明所在過程的嵌套深變量的嵌套深度：它的聲明所在過程的嵌套深度作為該名

58、字的嵌套深度度作為該名字的嵌套深度7.4.3 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域7.4.3.2 7.4.3.2 尋找非局部名字存儲單元的訪問鏈尋找非局部名字存儲單元的訪問鏈 sa, xq (1, 9)k, v訪問鏈訪問鏈sa, xq (1, 3)k, v訪問鏈訪問鏈q (1, 9)k, v訪問鏈訪問鏈sa, xq (1, 3)k, v訪問鏈訪問鏈q (1, 9)k, v訪問鏈訪問鏈p (1, 3)i, j訪問鏈訪問鏈e (1, 3)訪問鏈訪問鏈sa, xq (1, 3)k, v訪問鏈訪問鏈q (1, 9)k, v訪問鏈訪問鏈p (1, 3)i, j訪問鏈訪問鏈7.4.3.2 7.4.

59、3.2 訪問鏈訪問鏈假定過程假定過程p的嵌套深度為的嵌套深度為np，它引用嵌套深度為，它引用嵌套深度為na的變量的變量a，na np。如何訪問。如何訪問a的存儲單元？的存儲單元？ 從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈np na次。次。 到達(dá)到達(dá)a的聲明所在過程的活動記錄。的聲明所在過程的活動記錄。 訪問鏈的追蹤用間接操作就可完成。訪問鏈的追蹤用間接操作就可完成。7.4.3.2 7.4.3.2 訪問鏈訪問鏈訪問非局部名字的存儲單元訪問非局部名字的存儲單元 sa, xq (1, 9)k, v訪問鏈訪問鏈sa, xq (1, 3)k, v訪問鏈訪問鏈q (1, 9)k,

60、v訪問鏈訪問鏈sa, xq (1, 3)k, v訪問鏈訪問鏈q (1, 9)k, v訪問鏈訪問鏈p (1, 3)i, j訪問鏈訪問鏈e (1, 3)訪問鏈訪問鏈sa, xq (1, 3)k, v訪問鏈訪問鏈q (1, 9)k, v訪問鏈訪問鏈p (1, 3)i, j訪問鏈訪問鏈sort readarray exchange quicksort partition7.4.3.2 7.4.3.2 訪問鏈訪問鏈過程過程p對變量對變量a訪問時，訪問時，a的地址由下面的二元的地址由下面的二元組表示：組表示：（np na，a在活動記錄中的偏移）在活動記錄中的偏移）7.4.3.2 7.4.3.2 訪問鏈訪問