编译原理运行时存储空间的组织和管理 6

《编译原理运行时存储空间的组织和管理 6》由会员分享，可在线阅读，更多相关《编译原理运行时存储空间的组织和管理 6（167页珍藏版）》请在装配图网上搜索。

1、第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 过程的过程的活动活动过程的一次执行称为过程的一次活动过程的一次执行称为过程的一次活动第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 过程的过程的活动活动过程的一次执行称为过程的一次活动过程的一次执行称为过程的一次活动活动记录活动记录过程的活动需要可执行代码和存放所需信息过程的活动需要可执行代码和存放所需信息的存储空间的存储空间,后者称为活动记录后者称为活动记录第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 过程的过程的活动活动过程的一次执行称为过程的一次活动过程的一次执行称为过程的一次活

2、动活动记录活动记录过程的活动需要可执行代码和存放所需信息过程的活动需要可执行代码和存放所需信息的存储空间的存储空间,后者称为活动记录后者称为活动记录本章内容本章内容 讨论一个活动记录中的数据安排讨论一个活动记录中的数据安排第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 过程的过程的活动活动过程的一次执行称为过程的一次活动过程的一次执行称为过程的一次活动活动记录活动记录过程的活动需要可执行代码和存放所需信息过程的活动需要可执行代码和存放所需信息的存储空间的存储空间,后者称为活动记录后者称为活动记录本章内容本章内容 讨论一个活动记录中的数据安排讨论一个活动记录中的数据安排 程序

3、执行过程中，所有活动记录的组织方式程序执行过程中，所有活动记录的组织方式 第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过

4、程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问非局部变量过程能否访问非局部变量第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问非局部变量过程能否访问非局部变量 过程调用的参数传递方式过程调用的参数传递方式第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略

5、的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问非局部变量过程能否访问非局部变量 过程调用的参数传递方式过程调用的参数传递方式 过程能否作为参数被传递过程能否作为参数被传递第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问非局部变量过程能否访问非局部变量 过程调用的参数传递方式过程调用的参数

6、传递方式 过程能否作为参数被传递过程能否作为参数被传递 过程能否作为结果值传递过程能否作为结果值传递第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问非局部变量过程能否访问非局部变量 过程调用的参数传递方式过程调用的参数传递方式 过程能否作为参数被传递过程能否作为参数被传递 过程能否作为结果值传递过程能否作为结果值传递 存储块能否在程序控制下动态地分配存储块能否在程序控制下动态地分配第六章

7、第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归过程能否递归 当控制从过程的活动返回时，局部变量的值当控制从过程的活动返回时，局部变量的值是否要保留是否要保留 过程能否访问非局部变量过程能否访问非局部变量 过程调用的参数传递方式过程调用的参数传递方式 过程能否作为参数被传递过程能否作为参数被传递 过程能否作为结果值传递过程能否作为结果值传递 存储块能否在程序控制下动态地分配存储块能否在程序控制下动态地分配 存储块是否必须显式地释放存储块是否必须显式地释放6.1 局部存储分配局部存储分配6.1.1 过程过程过程定义、

8、过程定义、过程过程调用、形式参数、实在参数、调用、形式参数、实在参数、活动的活动的生存期生存期6.1 局部存储分配局部存储分配6.1.2 名字的作用域和绑定名字的作用域和绑定名字的作用域名字的作用域 一个声明起作用的程序部分称为该声明的一个声明起作用的程序部分称为该声明的作作用域用域 即使一个名字在程序中只声明一次，该名字即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象在程序运行时也可能表示不同的数据对象6.1 局部存储分配局部存储分配 从名字到值的两步映射从名字到值的两步映射名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配 从名字到值的两

9、步映射从名字到值的两步映射 环境把名字映射到左值，而状态把左值映射环境把名字映射到左值，而状态把左值映射到右值到右值名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配 从名字到值的两步映射从名字到值的两步映射 环境把名字映射到左值，而状态把左值映射环境把名字映射到左值，而状态把左值映射到右值到右值 赋值改变状态，但不改变环境赋值改变状态，但不改变环境 名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配 从名字到值的两步映射从名字到值的两步映射 环境把名字映射到左值，而状态把左值映射环境把名字映射到左值，而状态把左值映射到右值到右值 赋值改变状

10、态，但不改变环境赋值改变状态，但不改变环境 过程调用改变环境过程调用改变环境名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配 从名字到值的两步映射从名字到值的两步映射 环境把名字映射到左值，而状态把左值映射环境把名字映射到左值，而状态把左值映射到右值到右值 赋值改变状态，但不改变环境赋值改变状态，但不改变环境 过程调用改变环境过程调用改变环境 如果环境将名字如果环境将名字x映射到存储单元映射到存储单元s，我们就我们就说说x被被绑定绑定到到s名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配静态概念和动态概念的对应静态概念和动态概念的对应静静

11、 态态 概概 念念 动动 态态 对对 应应 过程的定义过程的定义 过程的活动过程的活动 6.1 局部存储分配局部存储分配静态概念和动态概念的对应静态概念和动态概念的对应静静 态态 概概 念念 动动 态态 对对 应应 过程的定义过程的定义 过程的活动过程的活动 名字的声明名字的声明 名字的绑定名字的绑定 6.1 局部存储分配局部存储分配静态概念和动态概念的对应静态概念和动态概念的对应静静 态态 概概 念念 动动 态态 对对 应应 过程的定义过程的定义 过程的活动过程的活动 名字的声明名字的声明 名字的绑定名字的绑定 声明的作用域声明的作用域 绑定的生存期绑定的生存期 6.1 局部存储分配局部存储

12、分配6.1.3 活动记录活动记录一般的活动记录的布局一般的活动记录的布局返返 回回 值值临临 时时 数数 据据参参 数数控控 制制 链链访访 问问 链链机机 器器 状状 态态局局 部部 数数 据据6.1 局部存储分配局部存储分配6.1.4 局部数据的安排局部数据的安排 字节是可编址内存的最小单位字节是可编址内存的最小单位6.1 局部存储分配局部存储分配6.1.4 局部数据的安排局部数据的安排 字节是可编址内存的最小单位字节是可编址内存的最小单位 变量所需的存储空间可以根据其类型而静态变量所需的存储空间可以根据其类型而静态确定确定6.1 局部存储分配局部存储分配6.1.4 局部数据的安排局部数据

13、的安排 字节是可编址内存的最小单位字节是可编址内存的最小单位 变量所需的存储空间可以根据其类型而静态变量所需的存储空间可以根据其类型而静态确定确定 一个过程所声明的局部变量，按这些变量声一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配明时出现的次序，在局部数据域中依次分配空间空间6.1 局部存储分配局部存储分配6.1.4 局部数据的安排局部数据的安排 字节是可编址内存的最小单位字节是可编址内存的最小单位 变量所需的存储空间可以根据其类型而静态变量所需的存储空间可以根据其类型而静态确定确定 一个过程所声明的局部变量，按这些变量声一个过程所声明的局部变量，按这些变量声明

14、时出现的次序，在局部数据域中依次分配明时出现的次序，在局部数据域中依次分配空间空间 局部数据的地址可以用相对于某个位置的地局部数据的地址可以用相对于某个位置的地址来表示址来表示6.1 局部存储分配局部存储分配6.1.4 局部数据的安排局部数据的安排 字节是可编址内存的最小单位字节是可编址内存的最小单位 变量所需的存储空间可以根据其类型而静态变量所需的存储空间可以根据其类型而静态确定确定 一个过程所声明的局部变量，按这些变量声一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配明时出现的次序，在局部数据域中依次分配空间空间 局部数据的地址可以用相对于某个位置的地局部数据的

15、地址可以用相对于某个位置的地址来表示址来表示 数据对象的存储安排还有一个对齐问题数据对象的存储安排还有一个对齐问题6.1 局部存储分配局部存储分配在在SPARC/Solaris工作站上下面两个结构的工作站上下面两个结构的size分别是分别是24和和16，为什么不一样？，为什么不一样？typedef struct _atypedef struct _bchar c1;char c1;long i;char c2;char c2;long i;double f;double f;a;b;6.1 局部存储分配局部存储分配在在SPARC/Solaris工作站上下面两个结构的工作站上下面两个结构的siz

16、e分别是分别是24和和16，为什么不一样？，为什么不一样？typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2;1char c2;8 long i;4double f;16 double f;8a;b;6.1 局部存储分配局部存储分配在在X86/Linux机器的结果和机器的结果和SPARC/Solaris工作工作站不一样，是站不一样，是20和和16。typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2;1char c2;8

17、long i;4double f;12 double f;8a;b;6.1 局部存储分配局部存储分配6.1.5 程序块程序块 本身含有局部变量声明的语句本身含有局部变量声明的语句 可以嵌套可以嵌套 最接近的嵌套最接近的嵌套作用域规则作用域规则 并列程序块不会同时活跃并列程序块不会同时活跃 并列程序块的变量可以重叠分配并列程序块的变量可以重叠分配6.1 局部存储分配局部存储分配main()/begin of B0 /int a=0;int b=0;/begin of B1 /int b=1;/begin of B2 /int a=2;/end of B2 /begin of B3 /int b=

18、3;/end of B3 /end of B1 /end of B0 /6.1 局部存储分配局部存储分配main()/begin of B0 /int a=0;int b=0;/begin of B1 /int b=1;/begin of B2 /int a=2;/end of B2 /begin of B3 /int b=3;/end of B3 /end of B1 /end of B0 /声声 明明 作作 用用 域域 int a=0;B0 B2 int b=0;B0 B1 int b=1;B1 B3 int a=2;B2int b=3;B3 6.1 局部存储分配局部存储分配main()/

19、begin of B0 /int a=0;int b=0;/begin of B1 /int b=1;/begin of B2 /int a=2;/end of B2 /begin of B3 /int b=3;/end of B3 /end of B1 /end of B0 /声声 明明 作作 用用 域域 int a=0;B0 B2 int b=0;B0 B1 int b=1;B1 B3 int a=2;B2int b=3;B3 a0b0b1a2,b3重叠分配存储单元重叠分配存储单元 6.2 全局栈式存储分配全局栈式存储分配 介绍程序运行时所需的各个活动记录在存储介绍程序运行时所需的各个活动

20、记录在存储空间的分配策略空间的分配策略6.2 全局栈式存储分配全局栈式存储分配 介绍程序运行时所需的各个活动记录在存储介绍程序运行时所需的各个活动记录在存储空间的分配策略空间的分配策略 描述过程的目标代码怎样访问绑定到局部名描述过程的目标代码怎样访问绑定到局部名字的存储单元字的存储单元6.2 全局栈式存储分配全局栈式存储分配 介绍程序运行时所需的各个活动记录在存储介绍程序运行时所需的各个活动记录在存储空间的分配策略空间的分配策略 描述过程的目标代码怎样访问绑定到局部名描述过程的目标代码怎样访问绑定到局部名字的存储单元字的存储单元 介绍三种分配策略介绍三种分配策略 静态分配策略静态分配策略6.2

21、 全局栈式存储分配全局栈式存储分配 介绍程序运行时所需的各个活动记录在存储介绍程序运行时所需的各个活动记录在存储空间的分配策略空间的分配策略 描述过程的目标代码怎样访问绑定到局部名描述过程的目标代码怎样访问绑定到局部名字的存储单元字的存储单元 介绍三种分配策略介绍三种分配策略 静态分配策略静态分配策略 栈式分配策略栈式分配策略6.2 全局栈式存储分配全局栈式存储分配 介绍程序运行时所需的各个活动记录在存储介绍程序运行时所需的各个活动记录在存储空间的分配策略空间的分配策略 描述过程的目标代码怎样访问绑定到局部名描述过程的目标代码怎样访问绑定到局部名字的存储单元字的存储单元 介绍三种分配策略介绍三

22、种分配策略 静态分配策略静态分配策略 栈式分配策略栈式分配策略 堆式分配策略堆式分配策略6.2 全局栈式存储分配全局栈式存储分配6.2.1 运行时内存的划分运行时内存的划分代代 码码静静 态态 数数 据据堆堆栈栈6.2 全局栈式存储分配全局栈式存储分配静态分配静态分配 名字在程序被编译时绑定到存储单元，不需名字在程序被编译时绑定到存储单元，不需要运行时的任何支持要运行时的任何支持6.2 全局栈式存储分配全局栈式存储分配静态分配静态分配 名字在程序被编译时绑定到存储单元，不需名字在程序被编译时绑定到存储单元，不需要运行时的任何支持要运行时的任何支持 绑定的生存期是程序的整个运行期间绑定的生存期是

23、程序的整个运行期间6.2 全局栈式存储分配全局栈式存储分配静态分配给语言带来限制静态分配给语言带来限制 递归过程不被允许递归过程不被允许6.2 全局栈式存储分配全局栈式存储分配静态分配给语言带来限制静态分配给语言带来限制 递归过程不被允许递归过程不被允许 数据对象的长度和它在内存中位置的限制，数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的必须是在编译时可以知道的6.2 全局栈式存储分配全局栈式存储分配静态分配给语言带来限制静态分配给语言带来限制 递归过程不被允许递归过程不被允许 数据对象的长度和它在内存中位置的限制，数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的

24、必须是在编译时可以知道的 数据结构不能动态建立数据结构不能动态建立6.2 全局栈式存储分配全局栈式存储分配 C语言程序的外部变量和程序中出现的常量语言程序的外部变量和程序中出现的常量都可以静态分配都可以静态分配 声明在函数外面声明在函数外面外部变量外部变量 静态分配静态分配静态外部变量静态外部变量 静态分配静态分配 声明在函数里面声明在函数里面静态局部变量静态局部变量 也是静态分配也是静态分配自动变量自动变量 不能静态分配不能静态分配6.2 全局栈式存储分配全局栈式存储分配6.2.2 活动树和运行栈活动树和运行栈活动树活动树:用树来描绘控制进入和离开活动的方式用树来描绘控制进入和离开活动的方式

25、mq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2 全局栈式存储分配全局栈式存储分配活动树的特点活动树的特点 每个结点代表某过程的一个活动每个结点代表某过程的一个活动 根结点代表主程序的活动根结点代表主程序的活动 结点结点a是结点是结点b的父结点，当且仅当控制流从的父结点，当且仅当控制流从a的活动进入的活动进入b的活动的活动 结点结点a处于结点处于结点b的左边，当且仅当的左边，当且仅当a的生存期的生存期先于先于b的生存期的生存期6.2 全局栈式

26、存储分配全局栈式存储分配当前活跃着的过程活动可以保存在一个栈中当前活跃着的过程活动可以保存在一个栈中控制栈的内容：控制栈的内容：m,q(1,9),q(1,3),q(2,3)mq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2 全局栈式存储分配全局栈式存储分配运行栈：运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）6.2 全局栈式存储分配全局栈式存储分配运行

27、栈：运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）ma:arraym6.2 全局栈式存储分配全局栈式存储分配运行栈：运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mi:integerra:arraymr6.2 全局栈式存储分配全局栈式存储分配运行栈：运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mk:integerq

28、(1,9)a:arraymq(1,9)r6.2 全局栈式存储分配全局栈式存储分配运行栈：运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mk:integerq(1,9)a:arrayq(1,3)k:integermq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)6.2 全局栈式存储分配全局栈式存储分配6.2.3 调用序列调用序列 过程调用和过程返回都需要执行一些代码来过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等管理活动记录栈，保存或恢复机器状态等6.2 全局栈

29、式存储分配全局栈式存储分配6.2.3 调用序列调用序列 过程调用和过程返回都需要执行一些代码来过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等管理活动记录栈，保存或恢复机器状态等 过程调用序列过程调用序列过程调用时执行的分配活动记录，把信息填入它的过程调用时执行的分配活动记录，把信息填入它的域中的代码域中的代码6.2 全局栈式存储分配全局栈式存储分配6.2.3 调用序列调用序列 过程调用和过程返回都需要执行一些代码来过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等管理活动记录栈，保存或恢复机器状态等 过程调用序列过程调用序列过程调用时执行的分

30、配活动记录，把信息填入它的过程调用时执行的分配活动记录，把信息填入它的域中的代码域中的代码 过程返回序列过程返回序列过程返回时执行的恢复机器状态，释放活动记录，过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够继续执行的代码使调用过程能够继续执行的代码6.2 全局栈式存储分配全局栈式存储分配 过程调用和过程返回都需要执行一些代码来过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等管理活动记录栈，保存或恢复机器状态等 过程调用序列过程调用序列过程调用时执行的分配活动记录，把信息填入它的过程调用时执行的分配活动记录，把信息填入它的域中的代码域中的代码 过程返回序列过

31、程返回序列过程返回时执行的恢复机器状态，释放活动记录，过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够继续执行的代码使调用过程能够继续执行的代码 调用序列和返回序列调用序列和返回序列常常都分成两部分，分常常都分成两部分，分处于调用过程和被调用过程中处于调用过程和被调用过程中6.2 全局栈式存储分配全局栈式存储分配 即使是同一种语言，过程调用序列、返回序即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实列和活动记录中各域的排放次序，也会因实现而异现而异 设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则返返 回回 值值临临 时时 数数 据据参参

32、数数控控 制制 链链访访 问问 链链机机 器器 状状 态态局局 部部 数数 据据6.2 全局栈式存储分配全局栈式存储分配 即使是同一种语言，过程调用序列、返回序即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实列和活动记录中各域的排放次序，也会因实现而异现而异 设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则以活动记录中间的某个以活动记录中间的某个位置作为基地址位置作为基地址返返 回回 值值临临 时时 数数 据据参参 数数控控 制制 链链访访 问问 链链机机 器器 状状 态态局局 部部 数数 据据6.2 全局栈式存储分配全局栈式存储分配 即使是同一种语

33、言，过程调用序列、返回序即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实列和活动记录中各域的排放次序，也会因实现而异现而异 设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则以活动记录中间的某个以活动记录中间的某个位置作为基地址位置作为基地址长度能较早确定的域放在长度能较早确定的域放在活动记录的中间活动记录的中间返返 回回 值值临临 时时 数数 据据参参 数数控控 制制 链链访访 问问 链链机机 器器 状状 态态局局 部部 数数 据据6.2 全局栈式存储分配全局栈式存储分配 即使是同一种语言，过程调用序列、返回序即使是同一种语言，过程调用序列、返回序列

34、和活动记录中各域的排放次序，也会因实列和活动记录中各域的排放次序，也会因实现而异现而异 设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则一般把临时数据域放在一般把临时数据域放在局部数据域的后面局部数据域的后面返返 回回 值值临临 时时 数数 据据参参 数数控控 制制 链链访访 问问 链链机机 器器 状状 态态局局 部部 数数 据据6.2 全局栈式存储分配全局栈式存储分配 即使是同一种语言，过程调用序列、返回序即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实列和活动记录中各域的排放次序，也会因实现而异现而异 设计这些序列和活动记录设计这些序列和活动记录

35、的一些原则的一些原则一般把临时数据域放在一般把临时数据域放在局部数据域的后面局部数据域的后面把参数域和可能有的返回把参数域和可能有的返回值域放在紧靠调用者活动值域放在紧靠调用者活动记录的地方记录的地方返返 回回 值值临临 时时 数数 据据参参 数数控控 制制 链链访访 问问 链链机机 器器 状状 态态局局 部部 数数 据据6.2 全局栈式存储分配全局栈式存储分配 即使是同一种语言，过程调用序列、返回序即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实列和活动记录中各域的排放次序，也会因实现而异现而异 设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则用同

36、样的代码来执行各个用同样的代码来执行各个活动的保存和恢复活动的保存和恢复返返 回回 值值临临 时时 数数 据据参参 数数控控 制制 链链访访 问问 链链机机 器器 状状 态态局局 部部 数数 据据6.2 全局栈式存储分配全局栈式存储分配调用者和被调用者之间的任务划分调用者和被调用者之间的任务划分被调用者的责任被调用者的责任调用者的责任调用者的责任调用者的调用者的活动记录活动记录被被调用者的调用者的活动记录活动记录临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链 和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数

37、据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配过程过程p调用过程调用过程q的调用序列的调用序列 p计算实参，依次放入栈顶，并在栈顶留出放计算实参，依次放入栈顶，并在栈顶留出放返回值的空间。返回值的空间。top_sp的值在此过程中被改的值在此过程中被改变变 p把返回地址和当前把返回地址和当前base_sp的值存入的值存入q的活动的活动记录中，建立记录中，建立q的访问链，增加的访问链，增加base_sp的值的值 q保存寄存器的值和其它机器状态信息保存寄存器的值和其它机器状态信息 q根据局部数据域和临时数据域的大小增加根据局部数据域

38、和临时数据域的大小增加top_sp的值，初始化它的局部数据，并开始的值，初始化它的局部数据，并开始执行过程体执行过程体6.2 全局栈式存储分配全局栈式存储分配调用者和被调用者之间的任务划分调用者和被调用者之间的任务划分被调用者的责任被调用者的责任调用者的责任调用者的责任调用者的调用者的活动记录活动记录被被调用者的调用者的活动记录活动记录临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链 和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 6.

39、2 全局栈式存储分配全局栈式存储分配过程过程p调用过程调用过程q的返回序列的返回序列 q把返回值置入邻近把返回值置入邻近p的活动记录的地方的活动记录的地方 q对应调用序列的步骤（对应调用序列的步骤（4），减小），减小top_sp的的值值 q恢复寄存器（包括恢复寄存器（包括base_sp）和机器状态，和机器状态，返回返回p p根据参数个数根据参数个数与类型和返回值类型与类型和返回值类型调整调整top_sp，然后取出返回值然后取出返回值6.2 全局栈式存储分配全局栈式存储分配调用者和被调用者之间的任务划分调用者和被调用者之间的任务划分被调用者的责任被调用者的责任调用者的责任调用者的责任调用者的调用

40、者的活动记录活动记录被被调用者的调用者的活动记录活动记录临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链 和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配过程的参数个数可变的情况过程的参数个数可变的情况 函数返回值改成用寄存器传递函数返回值改成用寄存器传递 编译器产生将这些参数逆序进栈的代码编译器产生将这些参数逆序进栈的代码 被调用函数能准确地知道第一个参数的位置被调用函数能准确地知道第一个参数的

41、位置 被调用函数根据第一个参数到栈中取第二、被调用函数根据第一个参数到栈中取第二、第三个参数等等第三个参数等等6.2 全局栈式存储分配全局栈式存储分配调用者和被调用者之间的任务划分调用者和被调用者之间的任务划分被调用者的责任被调用者的责任调用者的责任调用者的责任调用者的调用者的活动记录活动记录被被调用者的调用者的活动记录活动记录临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链 和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 6.2 全局

42、栈式存储分配全局栈式存储分配6.2.4 栈上可变长数据栈上可变长数据活动记录的长度在编译时不能确定的情况活动记录的长度在编译时不能确定的情况 局部数组的大小要等到过程激活时才能确定局部数组的大小要等到过程激活时才能确定 在活动记录中为这样的数组分别存放数组指在活动记录中为这样的数组分别存放数组指针的单元针的单元 运行时，这些指针指向分配在栈顶的存储空运行时，这些指针指向分配在栈顶的存储空间间6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组q的数组的数组q的活动记录的活动记录p的数组的数组p的活动记录的活动记录控制链控制链top_sp base_sp 数组数组A的指针

43、的指针数组数组B的指针的指针数组数组A数组数组B控制链控制链.栈栈6.2 全局栈式存储分配全局栈式存储分配6.2.5 悬空引用悬空引用悬空引用：悬空引用：引用某个已被释放的存储单元引用某个已被释放的存储单元6.2 全局栈式存储分配全局栈式存储分配6.2.5 悬空引用悬空引用悬空引用：悬空引用：引用某个已被释放的存储单元引用某个已被释放的存储单元main()|int dangle()|int q;|int j=20;q=dangle();|return&j;|6.3 非局部名字的访问非局部名字的访问本节介绍本节介绍 无过程嵌套的静态作用域（无过程嵌套的静态作用域（C语言）语言）有过程嵌套的静态作

44、用域有过程嵌套的静态作用域（Pascal语言）语言）动态作用域动态作用域（Lisp语言）语言）6.3 非局部名字的访问非局部名字的访问6.3.1 无过程嵌套的静态作用域无过程嵌套的静态作用域 过程体中的非局部引用可以直接使用静态确过程体中的非局部引用可以直接使用静态确定的地址定的地址6.3 非局部名字的访问非局部名字的访问6.3.1 无过程嵌套的静态作用域无过程嵌套的静态作用域 过程体中的非局部引用可以直接使用静态确过程体中的非局部引用可以直接使用静态确定的地址定的地址 局部变量在栈顶的活动记录中，可以通过局部变量在栈顶的活动记录中，可以通过base_sp指针来访问指针来访问6.3 非局部名字

45、的访问非局部名字的访问6.3.1 无过程嵌套的静态作用域无过程嵌套的静态作用域 过程体中的非局部引用可以直接使用静态确过程体中的非局部引用可以直接使用静态确定的地址定的地址 局部变量在栈顶的活动记录中，可以通过局部变量在栈顶的活动记录中，可以通过base_sp指针来访问指针来访问 无须深入栈中取数据，无须访问链无须深入栈中取数据，无须访问链6.3 非局部名字的访问非局部名字的访问6.3.1 无过程嵌套的静态作用域无过程嵌套的静态作用域 过程体中的非局部引用可以直接使用静态确过程体中的非局部引用可以直接使用静态确定的地址定的地址 局部变量在栈顶的活动记录中，可以通过局部变量在栈顶的活动记录中，可

46、以通过base_sp指针来访问指针来访问 无须深入栈中取数据，无须访问链无须深入栈中取数据，无须访问链 过程可以作为参数来传递，也可以作为结果过程可以作为参数来传递，也可以作为结果来返回来返回6.3 非局部名字的访问非局部名字的访问6.3.2 有过程嵌套的静态作用域有过程嵌套的静态作用域sortreadarrayexchangequicksortpartition6.3 非局部名字的访问非局部名字的访问6.3.2 有过程嵌套的静态作用域有过程嵌套的静态作用域过程过程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition36.3 非局部名字的访问非

47、局部名字的访问6.3.2 有过程嵌套的静态作用域有过程嵌套的静态作用域过程过程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition3变量的嵌套深度：它的声明所在过程的嵌套变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度深度作为该名字的嵌套深度6.3 非局部名字的访问非局部名字的访问寻找非局部名字存储单元的访问链寻找非局部名字存储单元的访问链 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

48、访问链访问链e(1,3)访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链6.3 非局部名字的访问非局部名字的访问假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度它引用嵌套深度为为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单元sort1readarray2exchange2quicksort2partition36.3 非局部名字的访问非局部名字的访问假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度它引用嵌套深度为为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单

49、元 从栈顶的活动记录开始，追踪访问链从栈顶的活动记录开始，追踪访问链np na次次6.3 非局部名字的访问非局部名字的访问假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度它引用嵌套深度为为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单元 从栈顶的活动记录开始，追踪访问链从栈顶的活动记录开始，追踪访问链np na次次 到达到达a的声明所在过程的活动记录的声明所在过程的活动记录6.3 非局部名字的访问非局部名字的访问假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度它引用嵌套深度为为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单

50、元 从栈顶的活动记录开始，追踪访问链从栈顶的活动记录开始，追踪访问链np na次次 到达到达a的声明所在过程的活动记录的声明所在过程的活动记录 访问链的追踪用间接操作就可完成访问链的追踪用间接操作就可完成6.3 非局部名字的访问非局部名字的访问访问非局部名字的存储单元访问非局部名字的存储单元 sort readarray exchange quicksort partitionsa,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)访问

51、链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链6.3 非局部名字的访问非局部名字的访问过程过程p对变量对变量a访问时，访问时，a的地址由下面的二元的地址由下面的二元组表示：组表示：（np na，a在活动记录中的偏移）在活动记录中的偏移）6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程x np nx的情况的情况sort1readarray2exchange2quicksort2partition 36.3 非局部名字的访问非局部名字的访

52、问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程x np nx的情况的情况 x肯定就声明在肯定就声明在p中中6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程x np nx的情况的情况 x肯定就声明在肯定就声明在p中中被调用过程的访问链必须指向调用过程的活动记被调用过程的访问链必须指向调用过程的活动记录的访问链录的访问链6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链sort readarray exchange qui

53、cksort partitionsa,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访问链访问链6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程x np nx的情况的情况sort1readarray2exchange2quicksort

54、2partition 36.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程x np nx的情况的情况 p和和x的嵌套深度分别为的嵌套深度分别为1，2，nx 1的外围过的外围过程肯定相同程肯定相同6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程x np nx的情况的情况 p和和x的嵌套深度分别为的嵌套深度分别为1，2，nx 1的外围过的外围过程肯定相同程肯定相同追踪访问链追踪访问链np nx+1次

55、，到达了静态包围次，到达了静态包围x和和p的且离它们最近的那个过程的最新活动记录的且离它们最近的那个过程的最新活动记录6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程x np nx的情况的情况 p和和x的嵌套深度分别为的嵌套深度分别为1，2，nx 1的外围过的外围过程肯定相同程肯定相同追踪访问链追踪访问链np nx+1次，到达了静态包围次，到达了静态包围x和和p的且离它们最近的那个过程的最新活动记录的且离它们最近的那个过程的最新活动记录所到达的活动记录就是所到达的活动记录就是x的活动记录中的访

56、问链的活动记录中的访问链应该指向的那个活动记录应该指向的那个活动记录6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链sort readarray exchange quicksort partitionsa,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访问链访问链6.3 非局部名字的访问非局部名字的访问program pa

57、ram(input,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.6.3 非局部名字的访问非局部名字的访问program param(input,output);（过程作为参数）过程作为参数）procedure b(function h(n:integ

58、er):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.过程作为参数传递时，怎样在该过程作为参数传递时，怎样在该过程被激活时建立它的访问链过程被激活时建立它的访问链6.3 非局部名字的访问非局部名字的访问program param(input,output);（过程作为参数）过程作为参数）procedure b(function h(n:integer):integ

59、er);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.过程作为参数传递时，怎样在该过程作为参数传递时，怎样在该过程被激活时建立它的访问链过程被激活时建立它的访问链 从从b的访问链难以建立的访问链难以建立f的访问链的访问链6.3 非局部名字的访问非局部名字的访问program param(input,output);（过程作为参数）过程作为参数）procedure b(functio

60、n h(begin writeln(h(2)end;procedure c;var m:integer;function f(n:integer)begin f:=m+n end f;begin m:=0;b(f)end c;begin cend.访访 问问 链链访访 问问 链链paramcmb 6.3 非局部名字的访问非局部名字的访问program ret(input,output);（过程作为返回值）过程作为返回值）var f:function(integer):integer;function a:function(integer):integer;var m:integer;funct

61、ion addm(n:integer):integer;begin return m+n end;begin m:=0;return addm end;procedure b(g:function(integer):integer);begin writeln(g(2)end;begin f:=a;b(f)end.6.3 非局部名字的访问非局部名字的访问program ret(input,output);（过程作为返回值）过程作为返回值）var f:function(integer):integer;function a:function(integer):integer;var m:inte

62、ger;function addm(n:integer):integer;begin return m+n end;begin m:=0;return addm end;procedure b(g:function(integer):integer);begin writeln(g(2)end;begin f:=a;b(f)end.retabaddm6.3 非局部名字的访问非局部名字的访问C语言的函数声明不能嵌套，函数不论在什语言的函数声明不能嵌套，函数不论在什么情况下激活，要访问的数据分成两种情况么情况下激活，要访问的数据分成两种情况:非静态局部变量（包括形式参数），它们分非静态局部变量（包

63、括形式参数），它们分配在活动记录栈顶的那个活动记录中配在活动记录栈顶的那个活动记录中 外部变量（包括定义在其它源文件中的外部外部变量（包括定义在其它源文件中的外部变量）和静态的局部变量，它们都分配在静变量）和静态的局部变量，它们都分配在静态数据区态数据区 6.3 非局部名字的访问非局部名字的访问6.3.3 动态作用域动态作用域 被调用过程的非局部名字被调用过程的非局部名字a和它在调用过程中和它在调用过程中引用的是同样的存储单元引用的是同样的存储单元6.3 非局部名字的访问非局部名字的访问6.3.3 动态作用域动态作用域 被调用过程的非局部名字被调用过程的非局部名字a和它在调用过程中和它在调用过

64、程中引用的是同样的存储单元引用的是同样的存储单元 新的绑定仅为被调用过程的局部名字建立，新的绑定仅为被调用过程的局部名字建立，这些名字在被调用过程的活动记录中占用的这些名字在被调用过程的活动记录中占用的存储单元存储单元6.3 非局部名字的访问非局部名字的访问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;begin r:=0.25;show;small;writeln;show;smal

65、l;writeln end.6.3 非局部名字的访问非局部名字的访问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;begin r:=0.25;show;small;writeln;show;small;writeln end.dynamicshowsmallsmallshowshowshow6.3 非局部名字的访问非局部名字的访问program dynamic(input,output

66、);var r:real;procedure show;begin write(r:5:3)end;procedure small;var r:real;begin r:=0.125;show end;begin静态作用域静态作用域 r:=0.25;0.250 0.250 show;small;writeln;0.250 0.250 show;small;writeln end.dynamicshowsmallsmallshowshowshow6.3 非局部名字的访问非局部名字的访问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;begin动动态作用域态作用域 r:=0.25;0.250 0.125 show;small;writeln;0.250 0.125 show;small;writeln end.dynamicshowsmallsmallshowshowshow6.3