研究生院第七章

1、1第七章第七章运行环境运行环境 源语言问题源语言问题存储组织存储组织存储分配策略存储分配策略访问非局部名字访问非局部名字参数传递参数传递2静态和动态静态和动态静态和动态的联系静态和动态的联系名字和数据对象名字和数据对象数据对象的动态表示数据对象的动态表示名字的作用域名字的作用域数据对象的存储分配数据对象的存储分配过程和活动过程和活动参数处理参数处理运行时支撑程序包运行时支撑程序包3源语言问题（源语言问题（1）过程及其执行过程及其执行过程定义：是一个声明，最简单形式是把一个标识符过程定义：是一个声明，最简单形式是把一个标识符和一个语句联系起来和一个语句联系起来该标识符称为过程名该标识符称为过程名

2、语句是过程体语句是过程体函数：返回值的过程函数：返回值的过程过程调用过程调用过程名出现在可执行语句中时，则称这个过程在这点过程名出现在可执行语句中时，则称这个过程在这点被调用被调用调用者、被调用者和调用点调用者、被调用者和调用点参数参数形式参数：与局部变量有不同形式参数：与局部变量有不同实在参数：在调用点，将其传递给被调用的过程实在参数：在调用点，将其传递给被调用的过程4源语言问题（源语言问题（2）program sort ( input, output );var a : array 0 . 10 of integer;procedure readarray; var i : integer

3、; begin for i := 1 to 9 read( ai ) end;function partition ( m , n : integer ); var i , j , x , v : integer; begin . end;procedure quicksort( m , n : integer ); var i : integer; begin if ( n m ) then begin i := partiton(m , n); quicksort( m , i 1 ); quicksort( i + 1 , n ); end end;begin a 0 := -9999;

4、 a 10 := 9999; readarray; quicksort( 1 , 9 )end.5源语言问题（源语言问题（3）过程的执行的表示：活动树过程的执行的表示：活动树控制流的假设控制流的假设v控制流是连续的控制流是连续的v过程的每次执行都从过程体的起点开始，最后控制返回过程的每次执行都从过程体的起点开始，最后控制返回到直接跟随本次调用点的位置到直接跟随本次调用点的位置过程间的控制流可以用树表示（调用树）过程间的控制流可以用树表示（调用树）活动：过程体的一次执行活动：过程体的一次执行v活动的生存期：过程体执行的第一步和最后一步之间的活动的生存期：过程体执行的第一步和最后一步之间的步序列步

5、序列包括直接或间接被这个过程调用的其它过程的时间包括直接或间接被这个过程调用的其它过程的时间v过程的活动的生存期要么是不重叠的，要么是嵌套的过程的活动的生存期要么是不重叠的，要么是嵌套的v递归：如果一个过程的前一个活动结束前，它的一个新递归：如果一个过程的前一个活动结束前，它的一个新的活动又开始的活动又开始递归的两种缘起递归的两种缘起6源语言问题（源语言问题（4）活动树描述控制进入和离开活动：活动树描述控制进入和离开活动：v每个结点代表过程的一个活动每个结点代表过程的一个活动v根结点代表主程序的活动根结点代表主程序的活动v结点结点a是结点是结点b的父结点，当且仅当控制流从的父结点，当且仅当控制

6、流从a的活动进的活动进入入bva结点处于结点处于b结点的左边，当且仅当结点的左边，当且仅当a的生存期先于的生存期先于b的生的生存期存期结点和活动是一一对应的结点和活动是一一对应的7源语言问题（源语言问题（5）s sr rq q( (1 1, ,9 9) )p p( (1 1, ,9 9) )q q( (1 1, ,3 3) )p p( (1 1, ,3 3) ) q q( (1 1, ,0 0) )q q( (2 2, ,3 3) )p p( (2 2, ,3 3) ) q q( (2 2, ,1 1) )q q( (3 3, ,3 3) )p p( (5 5, ,9 9) ) q q( (5

7、 5, ,5 5) )q q( (7 7, ,9 9) )p p( (7 7, ,9 9) ) q q( (7 7, ,7 7) )q q( (9 9, ,9 9) )q q( (5 5, ,9 9) )幻灯片幻灯片4中程序的活动树中程序的活动树8源语言问题（源语言问题（6）控制栈控制栈控制栈用于保存活跃着的过程控制栈用于保存活跃着的过程栈的内容表示活动树上到根结点的一条路径栈的内容表示活动树上到根结点的一条路径s sr rq(1,9)q(1,9)p(1,9)p(1,9)q(1,3)q(1,3)p(1,3)p(1,3)q(1,0)q(1,0) q(2,3)q(2,3)9源语言问题（源语言问题（

8、7）名字与数据对象名字与数据对象声明的作用域声明的作用域区分同名程序声明：最接近的嵌套规则区分同名程序声明：最接近的嵌套规则int a , b;int *p;int foo( int a )int b, c;char *p;p = malloc( sizeof( char ) );b = foo( 1 ); 作用域：一作用域：一个声明起作用的程序部分称为该声明的作用域局部和非局部：过程中名字的出现，如果是在该过程的一个局部和非局部：过程中名字的出现，如果是在该过程的一个声明的作用域内，则这个出现称为局部于该过程声明的作用域内，则这个出现称为局部于该过程10源语言问题（源语言问题（8）名字的结合

9、名字的结合程序中声明的名字和动态数据对象的关系程序中声明的名字和动态数据对象的关系v数据对象是保存值的存储单元数据对象是保存值的存储单元v一个名字可能代表不同的数据对象一个名字可能代表不同的数据对象环境：表示将名字映射到存储单元（即名字的左值）环境：表示将名字映射到存储单元（即名字的左值）的函数的函数状态：表示将存储单元映射到它所保存的值（即名字状态：表示将存储单元映射到它所保存的值（即名字的右值）的函数的右值）的函数赋值操作只改变状态，但不改变环境赋值操作只改变状态，但不改变环境结合：如果环境把存储单元结合：如果环境把存储单元s联系到名字联系到名字x，则称则称x结合结合到到s，这个联系本身称

10、为这个联系本身称为x的结合的结合静态概念静态概念动态概念动态概念 过程的定义过程的定义过程的活动过程的活动 名字的声明名字的声明名字的结合名字的结合 声明的作用域声明的作用域结合的生存期结合的生存期11源语言问题（源语言问题（9）名字结合要考虑的问题名字结合要考虑的问题v过程是否递归过程是否递归v当控制从过程的活动返回时，局部名字的值是否要保留当控制从过程的活动返回时，局部名字的值是否要保留v过程能否引用非局部的名字过程能否引用非局部的名字v过程调用时参数是如何传递的过程调用时参数是如何传递的v过程是否可以作为参数被传递过程是否可以作为参数被传递v过程能否作为结果值返回过程能否作为结果值返回v

11、存储区能否在程序控制下动态地分配存储区能否在程序控制下动态地分配v存储区是否必须显式地释放存储区是否必须显式地释放12存储组织（存储组织（1）运行时内存的划分运行时内存的划分程序运行时如何使用内存：程序运行时如何使用内存：目标代码的存放目标代码的存放v目标代码可以存放在静态确目标代码可以存放在静态确定的区域，其长度在编译时定的区域，其长度在编译时即可确定即可确定数据对象数据对象v可静态分配的数据对象，其可静态分配的数据对象，其地址可以编译到目标代码中地址可以编译到目标代码中v动态分配动态分配控制栈：记录过程活动控制栈：记录过程活动堆：可以存放动态分配的数据堆：可以存放动态分配的数据等，但开销要

12、比栈大等，但开销要比栈大代代 码码静静态态数数据据栈栈堆堆运运行行时时内内存存分分成成代代码码区区和和数数据据区区的的典典型型划划分分13存储组织（存储组织（2）活动记录活动记录定义：过程的一次执行所需要定义：过程的一次执行所需要的信息用一块连续的存储区来的信息用一块连续的存储区来管理，这块存储区叫做活动记管理，这块存储区叫做活动记录或帧录或帧一般的活动记录结构如右图，一般的活动记录结构如右图，但不是所有的语言或编译器都但不是所有的语言或编译器都是如此是如此寄存器的使用寄存器的使用活动记录的操作：活动记录的操作：v过程被调用时入栈过程被调用时入栈v过程返回时出栈过程返回时出栈返 回 值返 回

13、值实在参数实在参数可选的控制链可选的控制链可选的访问链可选的访问链保存的机器状态保存的机器状态局部数据局部数据临时数据临时数据一般的活动记录一般的活动记录14存储组织（存储组织（3）活动记录的各个域的作用活动记录的各个域的作用临时数据域：临时变量的存储等临时数据域：临时变量的存储等局部数据域：局部于过程执行的数据局部数据域：局部于过程执行的数据机器状态：保存过程调用前的机器状态信息机器状态：保存过程调用前的机器状态信息v返回地址返回地址可选的访问链：用于非局部数据的访问可选的访问链：用于非局部数据的访问可选的控制链：指向调用者的活动记录可选的控制链：指向调用者的活动记录实在参数域：参数个数较少

14、时，可以考虑用寄存器传实在参数域：参数个数较少时，可以考虑用寄存器传递，效率高；参数多时用用这个域传递递，效率高；参数多时用用这个域传递返回值域：用于存放被调用过程返回给调用过程的值返回值域：用于存放被调用过程返回给调用过程的值，也可以用寄存器返回（效率高，但形式受限制），也可以用寄存器返回（效率高，但形式受限制）15存储组织（存储组织（4）过程调用时，每个域的长度都可以确定，大部分域的过程调用时，每个域的长度都可以确定，大部分域的长度可以在编译时刻确定长度可以在编译时刻确定运行框架安排的设计运行框架安排的设计这个框架的设计要考虑指令集体系结构（这个框架的设计要考虑指令集体系结构（ISA）特性

15、和特性和要编译的程序语言本身的特点要编译的程序语言本身的特点有些系统提供商为他们的体系结构提供一种标准的运有些系统提供商为他们的体系结构提供一种标准的运行框架安排，使得可以实现不同的语言编写的函数间行框架安排，使得可以实现不同的语言编写的函数间的调用的调用这个运行框架的设计通常在运行时支撑系统要考虑这个运行框架的设计通常在运行时支撑系统要考虑16存储组织（存储组织（5）编译时的局部数据安排编译时的局部数据安排名字所需的存储空间的大小可以由它的类型确定名字所需的存储空间的大小可以由它的类型确定基本数据对象（字符、整数或实数）可以用几个连续基本数据对象（字符、整数或实数）可以用几个连续的字节保存的

16、字节保存聚合类型（记录、数组等）聚合类型（记录、数组等）v一块足够大的空间存放所有成分一块足够大的空间存放所有成分v连续的字节区连续的字节区局部数据域在编译过程中的声明时安排局部数据域在编译过程中的声明时安排v长度可变的数据不保存在这个区域长度可变的数据不保存在这个区域v数据对象的相对地址（偏移）是数据对象地址相对于特数据对象的相对地址（偏移）是数据对象地址相对于特定点（例如活动记录的开始点）的地址差定点（例如活动记录的开始点）的地址差数据对齐：数据对象的存储安排受目标机器寻址限制数据对齐：数据对象的存储安排受目标机器寻址限制的影响的影响v如如10个字符的数组可以被编译器分配个字符的数组可以被

17、编译器分配12个字节个字节v不用的不用的2个字节称为衬垫空白区个字节称为衬垫空白区17存储组织（存储组织（6）两个两个C编译器的数据布局形式：编译器的数据布局形式：类型类型机器1机器1机器2机器2机器1机器1机器2机器2大小（bits）大小（bits）对齐（bits）对齐（bits）8 88 88 86464charchar1616242416166464shortshort3232484832326464intint3232646432326464longlong3232646432326464floatfloat646412812832326464doubledouble323230303

18、2326464char ptchar pt3232242432326464other ptother pt= 8= 8= 64= 6432326464structersstructers18存储分配策略（存储分配策略（1）静态分配静态分配名字的结合：名字的结合：编译时实现，不需要运行时支撑程序编译时实现，不需要运行时支撑程序名字和存储的结合是固定的名字和存储的结合是固定的v允许名字的值在过程停止活动后保持允许名字的值在过程停止活动后保持根据名字的类型，编译器可以在静态时刻确定该名字根据名字的类型，编译器可以在静态时刻确定该名字所需的存储空间，效率所需的存储空间，效率局限：局限：v数据对象的长度

19、和它在内存中位置的限制必须在编译时数据对象的长度和它在内存中位置的限制必须在编译时知道知道v不允许递归过程不允许递归过程v不允许有动态数据结构不允许有动态数据结构在在FORTRAN77中，静态存储分配策略，每个过程的活动中，静态存储分配策略，每个过程的活动记录可以与它的代码放在一起记录可以与它的代码放在一起19存储分配策略（存储分配策略（2）PROGRAM CNSUMECHARACTER * 50BUFINTEGERNEXTCHARACTERC , PRDUCEDATA NEXT / 1 /, BUF / /6C = PRDUCE( )BUF( NEXT , NEXT ) = CNEXT =

20、NEXT + 1IF ( C .NE. ) GOTO 6WRITE( * , ( A ) ) BUFENDCHARACTER FUNCTION PRDUCE( )CHARACTER * 80BUFFERINTEGERNEXTSAVE BUFFER , NEXTDATA NEXT / 81 /IF ( NEXT .GT. 80 ) THENREAD(* , ( A ) ) BUFFERNEXT = 1END IFPRDUCE = BUFFER( NEXT , NEXT )NEXT = NEXT + 1END20存储分配策略（存储分配策略（3）CHARACTER*80 BUFFERCHARACTE

21、R*80 BUFFERINTEGER NEXTINTEGER NEXT一个FORTRAN77程序局部标识符的静态存储一个FORTRAN77程序局部标识符的静态存储CHARACTER*80 BUFCHARACTER*80 BUFINTEGER NEXTINTEGER NEXTCHARACTER CCHARACTER CPRDUCE的代码PRDUCE的代码CNSUME的代码CNSUME的代码PRDUCEPRDUCE的活动记录的活动记录CNSUMECNSUME的活动记录的活动记录静态数据静态数据代码代码21存储分配策略（存储分配策略（4）栈分配栈分配递归过程要求栈分配递归过程要求栈分配允许动态数据对

22、象的存在允许动态数据对象的存在满足先入后出的次序满足先入后出的次序控制栈：控制栈：活动记录和栈的关系活动记录和栈的关系局部量的存储空间包含在对应调用的活动记录中局部量的存储空间包含在对应调用的活动记录中局部量的值会随着过程调用结束而丢失局部量的值会随着过程调用结束而丢失控制栈控制栈top的变化和活动记录的长度相关的变化和活动记录的长度相关通常，局部量相对于活动记录开始点的偏移量可以记通常，局部量相对于活动记录开始点的偏移量可以记录在符号表中录在符号表中22存储分配策略（存储分配策略（5）例：活动记录在栈中的分配例：活动记录在栈中的分配栈栈上上的的活活动动记记录录活活动动树树注注解解s ss s

23、a a : : a ar rr ra ay ys s的的活活动动记记录录s sa a : : a ar rr ra ay yr ri i : : i in nt te eg ge er rr r被被激激活活s sr rs sa a : : a ar rr ra ay yq q( (1 1, ,9 9) )k k : : i in nt te eg ge er rr r的的活活动动记记录录弹弹出出栈栈，q q( (1 1, ,9 9) )的的活活动动记记录录进进栈栈s sr rq q( (1 1, ,9 9) )s sa a : : a ar rr ra ay yq q( (1 1, ,9 9)

24、 )k k : : i in nt te eg ge er r控控制制刚刚返返回回到到q q( (1 1, ,3 3) )s sr rq q( (1 1, ,9 9) )q q( (1 1, ,3 3) )k k : : i in nt te eg ge er rp p( (1 1, ,9 9) )q q( (1 1, ,3 3) )p p( (1 1, ,3 3) )q q( (1 1, ,0 0) )23存储分配策略（存储分配策略（6）例：编译时确定长度的数据对象偏移量在符号表中的存例：编译时确定长度的数据对象偏移量在符号表中的存放放f fl lo oa at t f f( ( i in

25、nt t k k ) ) f fl lo oa at t c c 1 10 0 , , b b; ;b b = = c c k k * *3 3. .1 14 4r re et tu ur rn n b b; ; 返返回回值值o of ff fs se et t = = 0 0参参数数k ko of ff fs se et t = = 4 4局局部部数数组组c c 1 10 0 o of ff fs se et t = = 8 8局局部部量量b bo of ff fs se et t = = 4 48 83 3. .1 14 4位位于于常常数数区区，不不在在活活动动记记录录中中24存储分配策略

26、（存储分配策略（7）过程调用的实现：通过过程调用序列（过程调用的实现：通过过程调用序列（calling sequences）实现，包括调用序列和返回序列实现，包括调用序列和返回序列调用序列：分配活动记录，信息的保存和填充调用序列：分配活动记录，信息的保存和填充v参数、返回地址、老的控制栈参数、返回地址、老的控制栈top、寄存器的保存寄存器的保存、局部对象的初始化等、局部对象的初始化等返回序列：恢复机器状态，是调用者继续执行返回序列：恢复机器状态，是调用者继续执行v返回值、寄存器的恢复、重置控制栈返回值、寄存器的恢复、重置控制栈top、跳转到跳转到返回地址返回地址调用序列和活动记录不是一成不变的

27、，语言、实现等调用序列和活动记录不是一成不变的，语言、实现等都会导致不同都会导致不同过程调用序列的代码分成两部分，分别由调用过程和过程调用序列的代码分成两部分，分别由调用过程和被调用过程负责，但划分的界限不是唯一的被调用过程负责，但划分的界限不是唯一的25存储分配策略（存储分配策略（8）图：调用者和被调用者间的任务划分图：调用者和被调用者间的任务划分参数和返回值参数和返回值 控制链 控制链访问链和保存的机器状态访问链和保存的机器状态临时数据和局部数据临时数据和局部数据被调用者被调用者的职责的职责调用者调用者的职责的职责调用者的调用者的活动记录活动记录. .参数和返回值参数和返回值 控制链 控制

28、链访问链和保存的机器状态访问链和保存的机器状态临时数据和局部数据临时数据和局部数据base_spbase_sptop_sptop_sp被调用者的被调用者的活动记录活动记录26存储分配策略（存储分配策略（9）调用序列（调用序列（call sequences），），过程过程p调用过程调用过程qp计算实参，依次放入计算实参，依次放入q的活动记录中（也可以利用寄的活动记录中（也可以利用寄存器传递参数），改变存器传递参数），改变top_sp的值的值p把返回地址和当前的把返回地址和当前的base_sp的值存入的值存入q的活动记录中的活动记录中，建立，建立q的访问链，增加的访问链，增加base_sp的值的值

29、q保存寄存器的值（包括保存寄存器的值（包括top_sp的值）和其它机器状态的值）和其它机器状态信息信息q增加增加top_sp的值，初始化它的局部数据，并开始执行的值，初始化它的局部数据，并开始执行27存储分配策略（存储分配策略（10）返回序列（返回序列（return sequences），），过程过程p调用过程调用过程qq把返回值置入邻近把返回值置入邻近p的活动记录的地方（也可以利用的活动记录的地方（也可以利用特定的寄存器传递返回值）特定的寄存器传递返回值）q恢复寄存器的值（包括恢复寄存器的值（包括top_sp和和base_sp）和其它机器和其它机器状态信息状态信息q根据返回地址将控制返回根据

30、返回地址将控制返回pp根据参数个数调整根据参数个数调整top_sp的值，把返回值放入自己的的值，把返回值放入自己的活动记录中活动记录中参数个数不确定？参数个数不确定？C语言中的语言中的printf保存描述参数的信息，如保存描述参数的信息，如printf首先处理的第一个变元首先处理的第一个变元（它的位置是确定的）指出了其它参数的性质（它的位置是确定的）指出了其它参数的性质28存储分配策略（存储分配策略（11）动态数组动态数组数组的界在编译时刻无法确定，只能在运行时刻确定数组的界在编译时刻无法确定，只能在运行时刻确定procedure ( n )integer n, mnend动态数组不能分配在活

31、动记录中动态数组不能分配在活动记录中在动态数组的大小确定后，在该过程的活动记录紧邻在动态数组的大小确定后，在该过程的活动记录紧邻的栈中分配空间的栈中分配空间动态数组的描述也可以考虑用内情向量的方式动态数组的描述也可以考虑用内情向量的方式29存储分配策略（存储分配策略（12）动态数组访问的示意动态数组访问的示意参参数数和和返返回回值值 控控制制链链指指向向数数组组A A的的指指针针指指向向数数组组B B的的指指针针指指向向数数组组C C的的指指针针数数组组A A数数组组B B数数组组C Cp p的的活活动动记记录录. .参参数数和和返返回回值值 控控制制链链b ba as se e_ _s sp

32、 pt to op p_ _s sp pq q的的活活动动记记录录p p的的数数组组q q的的数数组组30存储分配策略（存储分配策略（13）悬空引用悬空引用引用某个已释放的存储单元称为悬空引用引用某个已释放的存储单元称为悬空引用v这是由于存储空间可以释放这是由于存储空间可以释放v这是一个逻辑错误：在大多数语言中，释放的存储单元这是一个逻辑错误：在大多数语言中，释放的存储单元的值是没有定义的的值是没有定义的main( )int *p;p := dangle( );int * dangle( )int i = 23;return &i;函数函数dangle返回后，指针返回后，指针p指向一个

33、已释放的存储单元指向一个已释放的存储单元31存储分配策略（存储分配策略（14）堆分配堆分配栈分配的局限栈分配的局限v不能使得活动停止时，局部名字的值保持不能使得活动停止时，局部名字的值保持v被调用者的活动不能比调用者的活动活得更长（否则，被调用者的活动不能比调用者的活动活得更长（否则，活动树不能正确描绘过程间的控制流），只能满足先入活动树不能正确描绘过程间的控制流），只能满足先入后出的次序后出的次序堆分配把连续存储区域分成块堆分配把连续存储区域分成块v需要时分配（活动记录或其它对象）需要时分配（活动记录或其它对象）v释放次序任意释放次序任意堆可以与栈分配结合起来堆可以与栈分配结合起来vC+语言

34、中，基本保持栈的形式，堆用于动态对象的分语言中，基本保持栈的形式，堆用于动态对象的分配配vC、Pascal语言中的指针的动态分配等语言中的指针的动态分配等32存储分配策略（存储分配策略（15）堆中，活跃的活动记录不一定相临，可能存在空洞堆中，活跃的活动记录不一定相临，可能存在空洞栈栈上上的的活活动动记记录录活活动动树树注注解解s sr rq q( (1 1, ,9 9) )s s控控制制链链r r控控制制链链q q( (1 1, ,9 9) )控控制制链链r r的的活活动动记记录录仍仍然然存存在在33存储分配策略（存储分配策略（16）堆的释放堆的释放v不释放不释放存储空间溢出时停止存储空间溢出

35、时停止v显式释放显式释放Free（C，PL/1），），deallocation（Ada）有可能引起悬挂引用有可能引起悬挂引用v隐式释放隐式释放单引用单引用引用计数引用计数垃圾收集（垃圾收集（Garbage collection）堆的分配和释放的优化堆的分配和释放的优化34访问非局部名字（访问非局部名字（1）如何通过活动记录正确访问名字，满足作用域的要如何通过活动记录正确访问名字，满足作用域的要求？求？两种作用域两种作用域静态作用域静态作用域根据程序正文决定用于名字的声明根据程序正文决定用于名字的声明最接近的嵌套规则最接近的嵌套规则程序块程序块非局部名字的访问：访问链非局部名字的访问：访问链动态

36、作用域动态作用域在运行时，根据现行的活动来决定用于名字的声明，在运行时，根据现行的活动来决定用于名字的声明，如如Lisp等等35访问非局部名字（访问非局部名字（2）程序块程序块定义：定义：起源于起源于AlgolC语言中的定义：语言中的定义： declarations statements 允许嵌套允许嵌套最接近的嵌套规则：最接近的嵌套规则：程序块程序块B中声明的作用域包括中声明的作用域包括B如果名字如果名字x没有在没有在B中声明，则中声明，则B中中x的出现是在外围程的出现是在外围程序块序块B的的x声明的作用域中，且满足：声明的作用域中，且满足：vB有有x的声明的声明vB比其它任何含比其它任何含

37、x声明的程序块更接近被嵌套的声明的程序块更接近被嵌套的B36访问非局部名字（访问非局部名字（3）例：非局部名字的引用例：非局部名字的引用 main( )main( ) int a = 0;int a = 0;int b = 0;int b = 0; int b = 1;int b = 1; int a = 2;int a = 2;printf(“%d, %dn”, a, b);printf(“%d, %dn”, a, b); int b = 3;int b = 3;printf(“%d, %dn”, a, b);printf(“%d, %dn”, a, b); printf(“%d, %dn”

38、, a, b);printf(“%d, %dn”, a, b); printf(“%d, %dn”, a, b);printf(“%d, %dn”, a, b); B B0 0B B1 1B B2 2B B3 3声明声明作用域作用域int a = 0;int a = 0;B B0 0-B-B2 2int b = 0;int b = 0;B B0 0-B-B1 1int b = 1;int b = 1;B B1 1-B-B3 3int a = 2;int a = 2;B B2 2int b = 3;int b = 3;B B3 32 12 10 30 30 10 10 00 037访问非局部名字

39、（访问非局部名字（4）名字的存储分配：名字的存储分配：基于栈分配：基于栈分配：v声明的作用域决不超出它所在的程序块声明的作用域决不超出它所在的程序块v程序块当作无参的过程，所以活动记录可以是程序块的程序块当作无参的过程，所以活动记录可以是程序块的v这类这类“过程过程”调用不需要参数传递，控制只能沿静态正文进入调用不需要参数传递，控制只能沿静态正文进入和退出程序块和退出程序块每次为一个完整的过程体分配存储空间每次为一个完整的过程体分配存储空间v只为过程分配活动记录只为过程分配活动记录v过程内嵌套的程序块的生命所需要的存储空间由过程负责留出过程内嵌套的程序块的生命所需要的存储空间由过程负责留出v要

40、分配的变量在编译时刻确定，不考虑控制流要分配的变量在编译时刻确定，不考虑控制流v作用域不重叠的声明可以共享一个存储区域作用域不重叠的声明可以共享一个存储区域a0b0b1 a2 , b338访问非局部名字（访问非局部名字（5）无过程嵌套的静态作用域无过程嵌套的静态作用域一个过程的定义不能出现在另一个过程里面，如一个过程的定义不能出现在另一个过程里面，如C语语言言对某个过程非局部的名字（过程中程序块的非局部名对某个过程非局部的名字（过程中程序块的非局部名字的处理见前面的内容），其声明在所有函数之外字的处理见前面的内容），其声明在所有函数之外函数外声明的作用域：该声明后的所有函数体，但同函数外声明的

41、作用域：该声明后的所有函数体，但同名的局部声明的出现将掩盖全局声明的作用名的局部声明的出现将掩盖全局声明的作用例：例：int a 11 ;readarray( ) a int partition(y , z) int y , z; a quicksort(m , n) int m , n; main ( ) a 39访问非局部名字（访问非局部名字（6）存储分配比较简单：存储分配比较简单：声明在任何过程外的所有名字的存储单元静态分配，声明在任何过程外的所有名字的存储单元静态分配，其存储位置在编译时可知其存储位置在编译时可知过程中可见的名字：过程中可见的名字：v非过程局部的，则使用静态确定的地址访

42、问非过程局部的，则使用静态确定的地址访问v其它的名字，局部于栈顶的活动纪录，可以通过其它的名字，局部于栈顶的活动纪录，可以通过base_sp访问访问重要好处：程序中声明的过程可以作为参数传递和作重要好处：程序中声明的过程可以作为参数传递和作为结果返回（为结果返回（C语言中是传递过程的指针）语言中是传递过程的指针）非局部名字的访问不受过程激活方式的影响非局部名字的访问不受过程激活方式的影响40访问非局部名字（访问非局部名字（7）例：例：program pass( input , output );var m : integer;function f( n : integer ) : intege

43、r;begin f := m + n end f ;function g( n : integer ) : integer;begin g := m * n end g ;procedure b( function h( n : integer ) : integer );begin write( h (2) ) end b ;beginm := 0;b( f ) ; b( g ) ; writelnend.变量变量m对所有的过程是非局部的，可以静态分配它的对所有的过程是非局部的，可以静态分配它的存储单元存储单元执行结果是：执行结果是：2 041访问非局部名字（访问非局部名字（8）有过程嵌套的

44、静态作用域有过程嵌套的静态作用域非局部名字的访问：非局部名字的访问：寻找最接近的嵌套声明，如下面例子中函数寻找最接近的嵌套声明，如下面例子中函数partition对对a的访的访问问 program sort( input , output ); var a: array 0 . 10 of integer; x: integer; procedure readarray; var i : integer; begin a end readarray ; procedure exchange( i , j : integer ) ; begin x := ai; ai := aj; aj :=

45、x; end exchange ; procedure quicksort( m , n : integer ); var k , v : integer; function partition( y , z : integer) : integervar i , j : integer;begin a ; v ; exchange( i, j); end begin end quicksort ; begin end sort .42访问非局部名字（访问非局部名字（9）嵌套深度：嵌套深度：过程的嵌套深度过程的嵌套深度v设主程序的嵌套深度是设主程序的嵌套深度是1v从一个过程进入一个被包围的过程

46、，嵌套深度加从一个过程进入一个被包围的过程，嵌套深度加1名字的每次出现，把它的声明所在过程的嵌套深度作名字的每次出现，把它的声明所在过程的嵌套深度作为该名字的嵌套深度为该名字的嵌套深度用于实现静态作用域用于实现静态作用域访问链：访问链：为每个活动记录增加一个访问链指针，如果过程为每个活动记录增加一个访问链指针，如果过程p在源在源程序中直接嵌在程序中直接嵌在q中，则中，则p的活动记录的访问链指向最的活动记录的访问链指向最接近的那个接近的那个q的活动记录的访问链的活动记录的访问链实现过程嵌套的静态作用域实现过程嵌套的静态作用域43访问非局部名字（访问非局部名字（10）幻灯片幻灯片41程序执行时运行

47、栈的瞬像：程序执行时运行栈的瞬像：s sa , xa , xq ( 1 , 9 )q ( 1 , 9 )access linkaccess linkk , vk , vq ( 1 , 9 )q ( 1 , 9 )access linkaccess linkk , vk , vq ( 1 , 9 )q ( 1 , 9 )access linkaccess linkk , vk , vq ( 1 , 9 )q ( 1 , 9 )access linkaccess linkk , vk , vq ( 1 , 3 )q ( 1 , 3 )access linkaccess linkk , vk , v

48、q ( 1 , 3 )q ( 1 , 3 )access linkaccess linkk , vk , vq ( 1 , 3 )q ( 1 , 3 )access linkaccess linkk , vk , vp ( 1 , 3 )p ( 1 , 3 )access linkaccess linki , ji , jp ( 1 , 3 )p ( 1 , 3 )access linkaccess linki , ji , je ( 1 , 3 )e ( 1 , 3 )access linkaccess links sa , xa , xs sa , xa , xs sa , xa , x4

49、4访问非局部名字（访问非局部名字（11）静态链（访问链）和动态链（控制链）的比较：静态链（访问链）和动态链（控制链）的比较： 静态链：静态链：v指向源程序中包围本过程的直接外层过程的一个最近活指向源程序中包围本过程的直接外层过程的一个最近活动记录的访问链动记录的访问链v通过静态链实现非局部名字的访问通过静态链实现非局部名字的访问v通过静态链访问非局部名字，访问速度慢通过静态链访问非局部名字，访问速度慢动态链：动态链：v指向调用者的活动记录指向调用者的活动记录ABCDEAR of AAR of BAR of CAR of D动态动态链链静态静态链链45访问非局部名字（访问非局部名字（12）访问链

50、的建立：访问链的建立：假定过程假定过程p的嵌套深度为的嵌套深度为np，它调用一个嵌套深度为它调用一个嵌套深度为nx的过程的过程x：v如果如果np = nx ：如幻灯片：如幻灯片44的的C调用调用E过程过程x和和p的嵌套深度为的嵌套深度为1，2，nx 1的外围过程必定相的外围过程必定相同同从调用过程追踪访问链从调用过程追踪访问链 np - nx + 1次，即到达静态包围次，即到达静态包围x和和p的最内过程的最新活动记录，这个访问链就是的最内过程的最新活动记录，这个访问链就是x必须指向必须指向的访问链的访问链np - nx + 1可以在编译时计算可以在编译时计算特别地，如果特别地，如果np = n

51、x ，如幻灯片，如幻灯片44的的C调用调用D，则则D的访的访问链指向与问链指向与C的访问链指向相同的访问链指向相同46访问非局部名字（访问非局部名字（13）通过访问链访问非局部名字：通过访问链访问非局部名字：假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用一个嵌套深度为它引用一个嵌套深度为na的变量的变量a，na = np，则则a的存储单元可以如下找到：的存储单元可以如下找到：v当控制在当控制在p中时，中时，p的一个活动记录必定在栈顶的一个活动记录必定在栈顶v从栈顶追踪访问链从栈顶追踪访问链np - na次（这个次数编译时刻可以计次（这个次数编译时刻可以计算）算）v追踪访问链追踪访问链n

52、p - na次后，到达次后，到达a的声明所在过程的活动记的声明所在过程的活动记录，根据录，根据a的偏移量可以访问的偏移量可以访问v综述：过程综述：过程p中变量中变量a的地址可以如下表示：的地址可以如下表示：（ np - na ，a在活动记录中的偏移）在活动记录中的偏移）过程调用发生时，非局部名字到存储单元的结合可能过程调用发生时，非局部名字到存储单元的结合可能发生变化发生变化47访问非局部名字（访问非局部名字（14）过程作参数的处理：过程作参数的处理：作为参数传递的过程必须取它的访问链和它一起传递作为参数传递的过程必须取它的访问链和它一起传递例：例：program param ( input

53、, output );procedure b( function h( n : integer ) : integer); begin writeln( h ( 2 ) ) end b procedure c; var m : integer; function f ( n : integer ) : integer;begin f := m + n end f ; begin m := 0; b( f ) end c ;begin cend.48访问非局部名字（访问非局部名字（15）paramparamc caccess linkaccess linkm mb b access linkac

54、cess link49访问非局部名字（访问非局部名字（16）Display表：表：di通过数组存放访问链，提高对非局部名字的访问效率通过数组存放访问链，提高对非局部名字的访问效率如果当前的活动记录对应的过程如果当前的活动记录对应的过程p的嵌套深度为的嵌套深度为j，则则Display表有表有j项，前项，前j-1项指向依次嵌套在过程项指向依次嵌套在过程p外面的外面的过程的最新活动记录，第过程的最新活动记录，第j项指向过程项指向过程p的这次活动记的这次活动记录录同一个过程的不同活动记录间可以利用访问链链结，同一个过程的不同活动记录间可以利用访问链链结，在调用序列和返回序列中进行更新操作在调用序列和返

55、回序列中进行更新操作v当一个嵌套深度当一个嵌套深度i的过程被调用时，建立一个新的活动记的过程被调用时，建立一个新的活动记录录在新的活动记录中保存在新的活动记录中保存d i 的值的值令令d i 指向新的活动记录指向新的活动记录v在一个活动结束前，恢复在一个活动结束前，恢复d i 被保存的值被保存的值50访问非局部名字（访问非局部名字（17）s sq q ( ( 1 1 , , 9 9 ) )s sa av ve ed d d d 2 2 d d 1 1 d d 2 2 ( ( a a ) )s sq q ( ( 1 1 , , 9 9 ) )s sa av ve ed d d d 2 2 d d

56、 1 1 d d 2 2 ( ( b b ) )q q ( ( 1 1 , , 3 3 ) )s sa av ve ed d d d 2 2 s sq q ( ( 1 1 , , 9 9 ) )s sa av ve ed d d d 2 2 d d 1 1 d d 2 2 ( ( c c ) )q q ( ( 1 1 , , 3 3 ) )s sa av ve ed d d d 2 2 d d 3 3 p p ( ( 1 1 , , 3 3 ) )s sa av ve ed d d d 3 3 s sq q ( ( 1 1 , , 9 9 ) )s sa av ve ed d d d 2 2

57、d d 1 1 d d 2 2 ( ( d d ) )q q ( ( 1 1 , , 3 3 ) )s sa av ve ed d d d 2 2 d d 3 3 p p ( ( 1 1 , , 3 3 ) )s sa av ve ed d d d 3 3 e e ( ( 1 1 , , 3 3 ) )s sa av ve ed d d d 2 2 51访问非局部名字（访问非局部名字（18）Display表的维护表的维护如果如果 j = i ，调用者和被调用者外面包围的嵌套深度为调用者和被调用者外面包围的嵌套深度为1，2，i-1的过程是同样的，在新的活动记录中保的过程是同样的，在新的活动记录中

58、保存老的存老的d i ，置置d i 指向新的活动记录，保持指向新的活动记录，保持Display表的前表的前i 1项不变，如上页的项不变，如上页的d图图Display表的保存表的保存可以放在寄存器中，受限于寄存器个数和非局部名字可以放在寄存器中，受限于寄存器个数和非局部名字访问的频繁程度访问的频繁程度可以在编译时刻知道可以在编译时刻知道Display表的最大长度，因此也可表的最大长度，因此也可以将以将Display表存放为一个单独的表或作为活动记录的表存放为一个单独的表或作为活动记录的一部分一部分52访问非局部名字（访问非局部名字（19）动态作用域：动态作用域：当一个过程被调用时，它的非局部名字

59、到存储单元的当一个过程被调用时，它的非局部名字到存储单元的结合不会改变，即被调用过程的非局部名字结合不会改变，即被调用过程的非局部名字a和它在和它在调用过程中引用的是同样的存储单元调用过程中引用的是同样的存储单元新的结合仅为被调用过程的局部名字建立，这些名字新的结合仅为被调用过程的局部名字建立，这些名字占用新活动记录中的存储单元占用新活动记录中的存储单元在运行时，一个名字在运行时，一个名字a实施其影响，直到含实施其影响，直到含a的声明的的声明的一个过程开始执行时暂停；此过程停止时，该影响恢一个过程开始执行时暂停；此过程停止时，该影响恢复复53访问非局部名字（访问非局部名字（20）例：动态作用域

60、和静态作用域的对比例：动态作用域和静态作用域的对比program dynamic( input , output );var r : real;procedure show;begin write( r : 5 : 3 ) end;procedure small;var r : real;begin r := 0.125; show end;beginr := 0.25;show; small; writeln;show; small; writeln;end静态作用域的输出：静态作用域的输出：动态作用域的输出：动态作用域的输出：0.250 0.250 0.250 0.1250.250 0.250 0.250 0