北大编译原理chapter6ppt课件

1、 第六章 运行时刻环境 序6.1 源语言中的一些问题6.2 存储组织6.3 运行时刻存储分配策略6.4 非局部名字的访问6.5 参数传递6.6 符号表 序 计算环境 运行时的环境 计算 目标代码 源程序中的名字常量，变量）目标机存储空间。它受命于源程序的执行语义。 源程序由一组过程按某种规则组成。过程的一次执行称作一次活动，在过程的语句序列执行之前，过程中访问的对象构成此过程的运行环境，由运行支持程序组织好。编译程序根据如何组织运行环境而生成目标代码。映射源程序6.1有关源程序中的一些问题有关源程序中的一些问题 目的：目的： 构造运行程序的策略和方法构造运行程序的策略和方法 6.1.1 过程过

2、程 6.1.2 活动树活动树 6.1.3 控制栈控制栈 6.1.4 说明的作用域说明的作用域 6.1.5 名字的绑定名字的绑定 6.1.6 构造运行程序和源程序有关的构造运行程序和源程序有关的 一些问题一些问题6.1.1 过程 源程序由一组过程组成，不同的程序设计语言，由过程构成源程序的方法不同。 构成源程序的两个过程行文，要么是嵌套的，要么是不相交的。program sortinput，output）； var a ： array0.10 of integer； procedure readarray； var i ： integer； begin end； function partiti

3、on （y ，z ： integer ）:integer； var i，j ，x，v： integer； begin end; procedure quicksortm，n ： integer）； var i ： integer； begin end end； begin end.6.1.2 活动树活动树 程序执行期间的控制流：程序执行期间的控制流： 1程序执行的控制是顺序的；程序执行的控制是顺序的； 2过程的每一次执行都是从过程体的开过程的每一次执行都是从过程体的开头头 开场，并最终把控制返回到紧接着该开场，并最终把控制返回到紧接着该过过 程被调用点的后面。程被调用点的后面。过程的一次活动过

4、程的一次活动: 过程体的每一次执行。过程体的每一次执行。 一个过程一个过程p的一次活动的生存期的一次活动的生存期:在该过程在该过程体的执行中的第一步和最后一步之间的一序体的执行中的第一步和最后一步之间的一序列步骤的执行时间，其中包括执行过程列步骤的执行时间，其中包括执行过程p所调所调用的过程的执行时间，以及这些过程所调用用的过程的执行时间，以及这些过程所调用的过程的执行时间，如此等等。的过程的执行时间，如此等等。 特点： 每当控制流从过程p的活动进入到过程q的活动中后，它将返回到过程p的同一次活动中。 如果a和b是两个过程活动，那么它们的生存期要么是不重叠的，要么是嵌套的。 这种活动生存期的嵌

5、套性质可以通过在每一个过程中插入两个打印语句来加以说明。执行开始 enter readarray leave readarray enter quicksort1，9） enter partition1，9） leave partitionl，9） enter quicksort1，3） . leave quicksort1，3) enter quicksort5，9） . leave quicksort5，9） leave quicksort1，9） 执行结束 一个过程是递归的，如果同一过程的一次新的活动可以在前面活动结束以前开始。 用一颗树来描绘控制进入和离开活动的途径。这祥的树称作活动树

6、。在一棵活动树中： 1. b的左边当且仅当a的生存期发生在b的生存期之前。 用活动树来讨论正在这个结点上的控制 。 srq(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 一棵活动树结论：一个结点代表一个唯一的活动， 且每 一个活动只有一个结点表示，当控制进 入某一个活动时，可以直接说，控制在 这个结点上。6.1.3 控制栈 程序执行的控制流对应于从根开始，按先根次序遍历活动树。因此，用一个栈保存过程活动的生存踪迹。把它称作控制栈。 当一个活动开始执行时，把

7、代表这个活动的结点推进栈；当这个活动结束时，把代表这个活动的结点从栈中弹出。例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.4 控制栈中的活动都是活跃的，当前控制进入的活动在栈顶，从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的结点序列： s,q1，9），ql，3），q2，3） 从栈底活动到栈顶活动的

8、活动序列表示了活动的生存期的嵌套关系。 结论：扩充控制栈可用来实现如Pascal语言的栈式存储分配，进入一个活动，在栈顶建立这个活动所使用的存储空间；这个活动结束，从栈顶弹出其使用的存储空间。6.1.4 说明的作用域说明的作用域 1 .说明把名字与名字的属性信息绑定在一说明把名字与名字的属性信息绑定在一起。起。 2 . 说明的作用域是一个说明起作用的范围说明的作用域是一个说明起作用的范围 （源程序行文）。一个名字在源程序行文（源程序行文）。一个名字在源程序行文中中 可能有几处说明，语言的作用域规则规可能有几处说明，语言的作用域规则规定：定： 在语句序列中引用的一个名字是在何处在语句序列中引用的

9、一个名字是在何处说说 明的名字。明的名字。 3 . 编译时，处理说明把名字及其属性信息编译时，处理说明把名字及其属性信息填填 写进符号表写进符号表(add(id.entry,id.vul); 处处理引用理引用 名字时，查找这个名字的属性信息名字时，查找这个名字的属性信息 （lookup(id),符号表管理程序根据语符号表管理程序根据语 言的言的 作用域规则，使作用域规则，使 lookup(id)返回返回id的的作用域作用域 中绑定的属性信息。中绑定的属性信息。6.1.5名字与存储的绑定名字与存储的绑定 名字与存储单元的绑定是指把源程序中名字与存储单元的绑定是指把源程序中的数据名字映射到目标机存

10、储单元的过程。的数据名字映射到目标机存储单元的过程。 引进两个函数，引进两个函数，environment和和state。environment把名字映射到一个存储单元把名字映射到一个存储单元上；上；state把存储单元映射到那里所存放的把存储单元映射到那里所存放的值上。值上。可以说，函数可以说，函数environment把一个名字映把一个名字映射为一个射为一个l-value左左-值）值）,而函数而函数state把把一个一个l-value左左-值映射为一个值映射为一个r-value右右-值）。如图值）。如图6.5所示。所示。名字存储单元值存储分配程序运行environmentstatel-val

11、uer-value图6.5 从名字到值的两个阶段映射静态概念 动态对应过程定义 过程活动名字说明 名字的绑定说明的作用域 活动的生存期6.1.6 提出的问题提出的问题 编译程序组织存储分配所采用策略和方法主编译程序组织存储分配所采用策略和方法主要取决于对源程序中下面的问题的回答。要取决于对源程序中下面的问题的回答。 1过程可以是递归的吗？过程可以是递归的吗？ 2当控制从过程的一次活动返回时，部分当控制从过程的一次活动返回时，部分 名的值将发生什么名的值将发生什么 变化变化? 3一个过程可以访问非局部名吗？一个过程可以访问非局部名吗？ 4当调用过程时参数是怎样传递的？当调用过程时参数是怎样传递的

12、？ 5过程可以作为参数被传递吗？过程可以作为参数被传递吗？ 6过程可以作为结果被返回吗？过程可以作为结果被返回吗？ 7. 可以在程序控制下进行动态存储分配可以在程序控制下进行动态存储分配吗？吗？ 8. 显式的存储重新分配指撤除分配后显式的存储重新分配指撤除分配后的分的分 配是必须的吗？配是必须的吗？ 例：函数的返回值是函数。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)

13、6.2 存储组织存储组织 6.2.1 运行时刻内存的划分运行时刻内存的划分 运行时刻的存储空间必须划分以用来存运行时刻的存储空间必须划分以用来存放放: 1. 生成的目标代码生成的目标代码; 2. 数据目标数据目标; 3. 用于保存过程活动踪迹的一个控制栈。用于保存过程活动踪迹的一个控制栈。 存储空间划分的各部分：存储空间划分的各部分：目标代码静态数据栈堆1. 编译后知道目标代 码的大小。2. pascal主程序中的 数据,c,FORTRAN3. 栈:Pascal,c4. 堆: Pascal,c6.2.2 活动记录活动记录 把过程的一个活动所需要的信息组织成一把过程的一个活动所需要的信息组织成一

14、块连续的存储单元，称为活动记录。块连续的存储单元，称为活动记录。 一个活动所需要的信息的每个数据项有相一个活动所需要的信息的每个数据项有相同的生存期，因此，组织成一个活动记录是同的生存期，因此，组织成一个活动记录是很自然的。很自然的。 对于对于pascal语言来说，运行过程中，当语言来说，运行过程中，当调用一个过程时，在栈顶构筑它的活动记录；调用一个过程时，在栈顶构筑它的活动记录；当这个过程的活动执行完后，把它从栈顶弹当这个过程的活动执行完后，把它从栈顶弹出。出。 源语言不同，实现方法不同，组成活动源语言不同，实现方法不同，组成活动记录的域不同。实现记录的域不同。实现pascal语言的活动记录

15、语言的活动记录如如图图6.7所示。所示。返回值实在参数控制链访问链保存机器状态局部数据临时变量控制链:指向调用过程活动 的活动记录。访问链：指向本活动要访 问的非局部数据所在的 活动记录。保存机器状态：调用过程 活动在调用点的机器 形状，包括计数器， 各种寄存器的值。局部数据：过程中定义的 局部量。临时变量：编译产生。6.2.3 编译时刻的局部数据的设计编译时刻的局部数据的设计 局部数据域是编译时刻在分析过程中的局部数据域是编译时刻在分析过程中的说说 明时设计的。例如：明时设计的。例如： PROCEDURE sub(x,y:real); VAR i ,j:integer; a:ARRAY1.5

16、 OF real; e, f : real; BEGIN f :=e+i*j; END;符号表名字 形 类型 偏移量活动记录布局返回值(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 28中间代码* i j t1 * (top-sp ,20) (top-sp ,21) (top-sp ,29) + e t1 t2 + (

17、top-sp ,27) (top-sp ,29) (top-sp ,30) itor t2 t3 itor (top-sp ,30) (top-sp ,31):= t3 f := (top-sp ,31) (top-sp ,28) 编译结束，知道每个过程的活动记录的长度，将其填写到相应的过程表中，运行时，调用哪个过程，就在运行栈顶，推进那个过程的活动记录栈箭头加上活动记录长度）。6.3 运行时刻存储分配策略运行时刻存储分配策略 分配策略是：分配策略是： 1静态分配；静态分配； 2栈式分配，或称栈式动态分配；栈式分配，或称栈式动态分配； 3堆式分配，或称堆式动态分配。堆式分配，或称堆式动态分配。

18、 6.3 .1 静态存储分配静态存储分配 6.3 .2 栈式存储分配栈式存储分配 6.3 .3 堆式存储分配堆式存储分配 采用哪种分配策略是由源语言的语义决采用哪种分配策略是由源语言的语义决定的。定的。6.3 .1 静态存储分配静态存储分配 在编译时刻为每个数据项目确定出在运行在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置，且这种绑定在运行时刻的存储空间中的位置，且这种绑定在运行时刻不再发生变化。时刻不再发生变化。 局部名字的值在过程活动停止后仍保留下局部名字的值在过程活动停止后仍保留下来。来。 限制：限制： 1.在编译时刻知道数据目标的大小和它们在在编译时刻知道数据目标的大小和它

19、们在 内存位置上内存位置上 约束；约束； 2.不能递归调用过程一个过程的两个活动不能递归调用过程一个过程的两个活动 的生存期不相交的生存期不相交,一个过程的所有活动可一个过程的所有活动可以以 使用同一个活动记录）；使用同一个活动记录）； 3.不能动态地建立数据结构。不能动态地建立数据结构。 （1PROGRAM CNSUME （2）CHARACTER *50 BUF （3）INTEGER NEXT （4CHARACTER C，PRDUCE （5）DATA NEXT1，BUF/ / （6）CPRDUCE（）。 （7）BUFNEXT：NEXT）C （8NEXTNEXT1 （9）IFC.NE. )GO

20、TO 6 （10）WRITE（*，(A)）BUF （11） END (12CHARACTER FUNCTION PRDUCE（） （13)CHARACTER * 80 BUFFER （14）INTEGER NEXT （15）SAVE BUFFER，NEXT (16) DATA NEXT81 （17）IF(NEXT.GT.80THEN （18)READ（*，（A)BUFFER （19）NEXT1 （20) END IF （21）PRDUCEBUFFERNEXT：NEXT） （22 ) NEXTNEXT1 （23)END 图6.8 一个Fortran 77程序 CNSUME目标代码PRDUCE目标

21、代码Char *50 buf int next char cChar *80 buffer int next Cnsume活动记录prduce活动记录目标代码静态数据6.3.2 栈式存储分配栈式存储分配 基于控制栈的原理：基于控制栈的原理：存储空间被组织成存储空间被组织成栈，活动记录的推入和弹出分别对应于活动栈，活动记录的推入和弹出分别对应于活动的开始和结束。的开始和结束。 与静态分配不同的是，在每次活动中把与静态分配不同的是，在每次活动中把局部名字和新的存储单元绑定，在活动结束局部名字和新的存储单元绑定，在活动结束时，活动记录从栈中弹出，因而局部名字的时，活动记录从栈中弹出，因而局部名字的存

22、储空间也随之消失。存储空间也随之消失。 例例6.5 图图6.11表明当控制流通过图表明当控制流通过图6.3的活动树时活动记录被推人或弹出运行时刻的活动树时活动记录被推人或弹出运行时刻的栈中的情况，设寄存器的栈中的情况，设寄存器top标记栈顶。标记栈顶。sSa:arraytoprri:integertoptopq(1,9)q(1,9)i:integertopp(1,9)p(1,9)i:integertoptopq(1,3)q(1,3)i:integertop图 6.11 栈式分配活动记录在栈中的变化 确定活动记录中局部数据的地址：假设top-sp标记一个活动记录的开始的位置， dx表示x的地址相

23、对于top-sp的偏移量。那么， x在过程的目标代码中的地址可写成 dxtop-sp）在运行时刻，当把x的活动记录筑于栈顶时，寄存器top- sp被赋于实际的地址， top- sp可以是一个寄存器。调用序列和返回序列 通过在目标代码中生成调用序列和返回序列实现过程的调用。激活一个过程的活动是执行过程语句的结果。过程语句 p(e1,e2,en)的目标代码调用序列完成任务： 1. 调用者对实在参数求值，并把它们传送给 被调用过程的活动记录的参数域。 2调用者在被调用者的活动记录中存放返 回地址和老top-sp之值。之后调用者把 top一sp之值增加到图6.12所示的位置。 3被调用者存放寄存器值和

24、其它状态信息。 4被调用者初始化其局部数据并开始执行。返回序列，return目标代码完成的任务是： 1被调用者在自己的活动记录的返回值域 中放一个返回值。 2利用状态域中的信息，被调用者恢复 top-sp和其它寄存器，并且按返回地址转 移到调用者的代码之中。 3调用者复制返回值到自己的活动记录中。 任务的划分，根据源语言、目标机器和操 作系统等具体情况而定。 上述任务，由运行支持子程序完成，可视为虚机指令。可变长度的数据可变长度的数据源程序的例子源程序的例子PROCEDUREexam(l,m,n:integer);VARa:array1.lofreal;b:array1.mofreal;c:a

25、rray1.nofreal;BEGINEND;编译时，不知编译时，不知a,b,c的大小，仅对每个数组设的大小，仅对每个数组设置一个指针。置一个指针。Control linkabcTop-sptopArray aArray bArray ctopP的活动记录P的动态数组图6.13 动态分配的数组活动记录的进栈和推栈 栈顶活动记录用两个指针top和top-sp指示。top-sp指向栈顶活动记录保存机器状态域的末 端，用于访问局部数据。top指向栈顶。P调用q：栈top+h:=top-sp; top-sp:=top+h; top:=top+q的活动记录长度从q的活动返回：top:=top-spq (

26、h) top-sp:=栈top-sppqtop-sptop-sptoptoph6.3.3 堆式存储分配堆式存储分配 1局部名的值在活动结束时必须被保存。局部名的值在活动结束时必须被保存。 2. 被调用者的活动生存期超过调用者。被调用者的活动生存期超过调用者。 用活动树不能够正确描绘这种语言的用活动树不能够正确描绘这种语言的过过 程之间的控制流。程之间的控制流。 new(p); dispose(p);6.4 对非局部名字的访问对非局部名字的访问 讨论基于活动记录的栈式分配。讨论基于活动记录的栈式分配。 一个语言所规定的作用域规则决定了一个语言所规定的作用域规则决定了如何处理对非局部名字的引用。如

27、何处理对非局部名字的引用。 有静态和动态两有静态和动态两种作用域规则。种作用域规则。 静态静态:考查程序正文来决定引用的名字考查程序正文来决定引用的名字是哪一个名字说明是哪一个名字说明,如如Pascal，C和和Ada是是众多语言中使用带有众多语言中使用带有“最近嵌套规定的词最近嵌套规定的词法作用域规则的语言法作用域规则的语言 ; 动态动态:在运行时刻考查最近的活动来决在运行时刻考查最近的活动来决定应用到一个名字上的说明定应用到一个名字上的说明,如如LISP和和APL。 6.4.1 块块 一个块一个块Block是一个含有局部数据是一个含有局部数据说明的语句。说明的语句。 declarations

28、statements 一个块与另一个块要么是独立的，要么一个块与另一个块要么是独立的，要么 一一 个块完全嵌入在另一个块之中，这种嵌套个块完全嵌入在另一个块之中，这种嵌套的性质有时称作块结构。的性质有时称作块结构。 在块结构语言中，说明的作用域由最近嵌在块结构语言中，说明的作用域由最近嵌套规则给出：套规则给出： 1在块在块B中的一个说明的作用域包括中的一个说明的作用域包括B。 2如果名字如果名字x在块在块B中没有说明，那么，中没有说明，那么， x在B中的出现是在一个外围块B中的x的说 明的作用域之内，并且使得： （a) B 中有x 的说明， （b) B 是包围B的，相对于其它任何具有 名字x

29、的说明且包围B 的块而言,B是 离B 最近的。 对于pascal语言来说，一个过程是一个块，一个程序是一个块结构。而对于c语言来说，每个函数是一个块结构，而函数之间是不嵌套的。main( ) int a=0; /*B0-B2*/ int b=0; /* B0-B1 */ int b=1; /* B1-B3 */ 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) ; B0 B1B2B3a0b0b1a2 , b3 图6.16 函数ma

30、in局部数据 在活 动记录中的按排 块结构语言可以采用栈式分配。函数main的每个块可看成一个无参过程，块中的块可被看成一个语句。控制从块开始进入，遇块结束退出。B2和B3的生存期不相交，它们的局部数据可占用同一块存储空间。6.4.2 不含嵌套过程的词法作用域不含嵌套过程的词法作用域 C中过程定义不能嵌套中过程定义不能嵌套 （lint a11; （2） readarray( ) a （3） int partitiony，z） int y，z； a （4） quicksortm，n） int m，n； . （5） main( ) .a. 图图6.17 带有带有a的非局部出现的的非局部出现的C程序

31、程序 目标代码 int a11栈堆1.函数外的数据和函数内 的静态数据，静态分配 于静态数据域。2 .函数内的数据out) 栈 式分配,运行进入任一 函 数，使用的 数据，要 么 在 当前的活动记录中； 要么在 静态数据域中。6.4.3 含有嵌套过程的词法作用域含有嵌套过程的词法作用域 图图6.18 带有嵌套过程的一个带有嵌套过程的一个Pascal程序程序程序的静态嵌套结构：程序的静态嵌套结构： sort readarray exchange quicksort partition （1） program sortinput，output）;（2） var a： array0.10 of in

32、teger； （3） x : integer； （4） procedure readarray； （5） var i ： integer； （6） begin a end readarray; （7） procedure exchangei，j： integer）； （8） begin （9） x：= ai ；ai:=aj; aj:x （10） end exchange; （11） procedure quicksortm，n： integer）； （12） var k，v： integer； （13） function partitiony，z： integer） ： integer； （1

33、4） var i，j ： integer； （15） begin a （16） V （17） exchangei，j）； （18） end partition; （19） begin end quicksort; （20） begin end. sort 程序的静态嵌套结构决定程序中每个过程中访问哪些外围过程中的数据。 每个过程静态嵌套在哪些过程中，可用静态链static(p)表示: static(sort)=sort static(readarray)=sort readarray static(exchange)=sort exchange static(quichsort)=sort q

34、uichsort static(partition)=sort quichsort partition 运行时，过程的数据被组织成活动记录，为了实现非局部访问，过程的活动记录之间必须维持静态链反映程序的静态嵌套结构。6.4.3.1嵌套深度嵌套深度用过程的嵌套深度来表达一个过程在程序用过程的嵌套深度来表达一个过程在程序中的嵌套层次。令主程序的嵌套深度为中的嵌套层次。令主程序的嵌套深度为1；从；从一个过程进入到一个被包围过程时嵌套深度一个过程进入到一个被包围过程时嵌套深度加加1。如图。如图6.18中的位于中的位于11行上的过程行上的过程quicksort的嵌套深度为的嵌套深度为2，而，而13行上的

35、行上的partition的嵌套深度为的嵌套深度为3。过程表示除过程名字之外的过程定义正文。过程表示除过程名字之外的过程定义正文。一个名字的嵌套深度等于说明它的过程的一个名字的嵌套深度等于说明它的过程的嵌套深度，是名字的重要属性。在嵌套深度，是名字的重要属性。在15）（17行上的行上的partition中的中的a,v和和i的嵌套深度的嵌套深度分别是分别是1，2和和3。6.4.3.2存取链存取链accesslink）栈中的活动记录应反映源程序正文中过程栈中的活动记录应反映源程序正文中过程之间的嵌套关系，或静态结构。为每一个活动之间的嵌套关系，或静态结构。为每一个活动记录增设一个称为存取链或存取链路

36、的指记录增设一个称为存取链或存取链路的指针，如果在源程序正文中过程针，如果在源程序正文中过程p直接嵌入在过直接嵌入在过程程q中，那么中，那么p的一个活动记录中的存取链指向的一个活动记录中的存取链指向q的最近的活动记录中的存取链。从当前活动的最近的活动记录中的存取链。从当前活动记录开始，沿着这条链，能找到访问的非局部记录开始，沿着这条链，能找到访问的非局部名字。它是静态链在存储空间上的实现，也称名字。它是静态链在存储空间上的实现，也称作静态链。作静态链。程序运行过程中应维持这条链。程序运行过程中应维持这条链。S S nil a , xtop-sptopr r itoptop-sptop-spto

37、p q(1,9) q(1,9) k , vtoptop-spp(1,9) p(1,9) i , jtoptop-sptop-sptop q(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.19非局部访问非局部访问在嵌套深度为在嵌套深度为np的过程的过程p中引用一个嵌套深中引用一个嵌套深度为度为nanp的非局部名字的非局部名字a,a的存储位置可按的存储位置可按下面的步骤找到：下面的步骤找到：1从栈顶活动记录出发沿存取链前进从栈顶活动记录出发沿存取链前进npna步，到达步，到

38、达a所在的活动记录。所在的活动记录。npna的值可的值可在编译时刻计算出来。在编译时刻计算出来。2a的地址的地址=a所在活动记录的始址所在活动记录的始址+a的偏的偏移量。编译生成过程移量。编译生成过程p的目标代码中非局部名的目标代码中非局部名字字a的地址表示为：的地址表示为：（npna，a在其活动记录中的偏移量在其活动记录中的偏移量)运行时存取链的维护运行时存取链的维护维护存取链的代码是调用序列的一部分。维护存取链的代码是调用序列的一部分。假设嵌套深度为假设嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程x。存取链的维护依赖于过程。存取链的维护依赖于过程p和过和过程程x

39、之间的嵌套关系。之间的嵌套关系。1.npnx，nx=np+1,x在在p中定义。中定义。被调用过程的活动记录的存取链必须指向被调用过程的活动记录的存取链必须指向栈中刚好在其前面的地址码较低的调用栈中刚好在其前面的地址码较低的调用过程的活动记录的存取链。过程的活动记录的存取链。p x call xptop-sptopxtop-sptop栈top+h:=top-sp;top-sp:=top+h;top:=top+x的活动 记录长度；2. npnxxPcall x np=nxpx call xxpxpcallxpxnpnx 过程p和x的嵌套深度为1，2， ,nx-1的外围过程是相同的。 从p的活动记录

40、开始沿存取链前进np-nx+1步，可到达包围着p和x且离它们最近的过程的当前的活动记录。这个活动记录的存取链位置即是x的当前活动记录存取链应指向的位置。 np-nx+1在编译时能计算出来。过程作为参数传递的实现 PROGRAM param(input,output); 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; BE

41、GIN c END. paramcm:=0b( f )存取链f( 2 )如何建立存取链？ 过程要在定义它的环境中运行。过程作为实参数传递时，必须把它的存取链作为实参数的一部分传递。 在传递f时，确定f的存取链，好象在c中调用f一样。 在b中激活f的活动时，它作为f的活动记录的存取链。6.4.3.3 Display表表 Display表是一个指针数组表是一个指针数组d，在运行过，在运行过程中，若当前活动的过程的嵌套深度为程中，若当前活动的过程的嵌套深度为i，则，则di中存放当前的活动记录地址，中存放当前的活动记录地址，di-1,di-2, ,d1 中依次存放着当前活动中依次存放着当前活动的过程的

42、直接外层，的过程的直接外层， , 直至最外层主程直至最外层主程序等每一层过程的最新活动地址。序等每一层过程的最新活动地址。 这样，嵌套深度为这样，嵌套深度为j的变量的变量a存放在由存放在由dj所指出的活动记录中。所指出的活动记录中。 在运行过程中维持一个在运行过程中维持一个Display表实现表实现非局部访问比存取链效率要高。非局部访问比存取链效率要高。Display表的维护过程不作为参数传递）表的维护过程不作为参数传递） 当嵌套深度为当嵌套深度为i的过程的活动记录筑在栈顶的过程的活动记录筑在栈顶时：时： （1在新的活动记录中保存在新的活动记录中保存di的值；的值； （2置置di指向新的活动记

43、录。指向新的活动记录。 在一个活动结束前，在一个活动结束前， di置成保存的旧置成保存的旧值。值。用用Display表如何访问非局部量？表如何访问非局部量？ 1. Display表是一个数组，开始地址用表是一个数组，开始地址用通用通用 寄存器指出；寄存器指出； 2. Display表由一组寄存器实现。表由一组寄存器实现。sSa, xdisplayrrq(1,9)q(1,9)k, vp(1,9)p(1,9)e(1,9) e(1,9) save d2 q(1,3) q(1,3) save d2k, vp(1,3) p(1,3) save d3i, j图 6.19设p （嵌套深度为j调用q嵌套深度为

44、i）1. ji qd1d2di-1diPqpcall qSave diPcall qqdjSave dj6.4.4 动态作用域动态作用域 程序运行时，一个名字程序运行时，一个名字a实施其影响，实施其影响，直到含直到含a的声明的一个过程开始执行时暂停，的声明的一个过程开始执行时暂停，此过程停止时，该影响恢复。此过程停止时，该影响恢复。 设有下面的的调用序列：设有下面的的调用序列： A B C P过程过程P中有对中有对x的非局部引用，沿动态链红的非局部引用，沿动态链红链查找，最先找到的便是。链查找，最先找到的便是。programdynamicinput，output)；varr：real；proc

45、udureshow；beginwtiter：5：3）end；procedutesmall；varr：real；beginr:0.125；showend；beginr：0.25；show；small；write1n；show；small；writelnend. 在词法作用域之下，程序的输出为 : 0.250 0.250 0.250 0.250 在动态作用域之下，输出为: 0.250 0.125 0.250 0.125 实现动态作用域的方法: 1.深访问。使用控制链在栈中搜索，以寻 找包含所需非局部名字的存储单元的第 一个活动记录控制链又称动态链）。 2浅访问。这种方法的思想是在静态分配 的存储空

46、间中存放每一个名字的现行值。 当过程p开始一次新的活动时，p中的非局 部名n占用对于n静态分配的存储空间。先 前的n值可以存放在p的活动记录中并且当 p的活动记录结束时必须给以恢复。 两种方法进行比较。6.5 参数传递参数传递 实在参数和形式参数结合的方法：实在参数和形式参数结合的方法： 传值调用传值调用call-by-value） 引用调用引用调用call-by-reference） 复制恢复复制恢复copy-restore） 传名调用传名调用call-by-name） ai:=aj 其中表达式其中表达式aj代表一个值，而代表一个值，而ai 则则表示一个存储地址。表示一个存储地址。 参数传递

47、方法之间的区别主要基于实在参数传递方法之间的区别主要基于实在参数是代表右参数是代表右-值值r-值）、左值）、左-值值l-值）、值）、 或者实在参数的正文本身。或者实在参数的正文本身。6.5.1 传值调用传值调用 program referenceinput，output）；）； var a，b ： integer； procedure swapx，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.传值调用可以实现如下： 调用过程计算实在参数，并把它们的右- 值放入到形式参数的存储空间中。 使用传值的方法，调用swapa,b等价于下面几步： x：= a y：= b temp：= x x：= y y：= temp 6.5.2 引用调用引用调用