1、第九章第九章 运行时存储空间组织运行时存储空间组织概述概述任务：编译程序对目标程序运行时的数据空间任务：编译程序对目标程序运行时的数据空间的组织和管理（设计运行环境和分配存储）的组织和管理（设计运行环境和分配存储）如如 通常栈式存储分配布局可为：通常栈式存储分配布局可为：目标代码区目标代码区 静态数据区静态数据区 Stack heap运行环境和存储分配运行环境和存储分配设计分析设计分析逻辑阶段：在目标代码生成前，作准备逻辑阶段：在目标代码生成前，作准备实质：实质：关联（关联（Binding）将源程序的文本将源程序的文本 程序运行动作的实现程序运行动作的实现 源文件中的名字源文件中的名字N 运行
2、时的存储运行时的存储S S在语义学中，使用术语在语义学中，使用术语environment函数表示函数表示env:NS (NS (N到到S S的映射的映射)静静态态文文本本中中 运运行行时时动动作作及及为为实实现现其其动动作作的的准准备备 （与与运运行行时时数数据据对对象象的的表表示示有有关关）过过程程定定义义 过过程程名名执执行行过过程程体体 过过程程体体 控控制制数数据据对对象象的的分分配配，为为执执行行过过程程体体使使用用源源文文本本中中同同样样的的名名字字 目目标标程程序序中中不不同同的的数数据据空空间间因因为为一一个个过过程程可可以以是是递递归归的的，这这时时同同一一个个名名字字在在不
3、不同同的的时时间间可可能能代代表表不不同同的的存存储储单单元元决定存储管理复杂程度的因素源语言本身决定存储管理复杂程度的因素源语言本身1.允许的数据类型的多少允许的数据类型的多少2语言中允许的数据项是语言中允许的数据项是 静态确定静态确定 动态确定动态确定3程序结构程序结构 决定名字的作用域的规则和结构决定名字的作用域的规则和结构A 段结构段结构B 过程定义不嵌套，只允许过程递归调用过程定义不嵌套，只允许过程递归调用C 分程序结构分程序结构分程序嵌套分程序嵌套过程定义嵌套过程定义嵌套存储分配方案策略：存储分配方案策略：静态存储分配静态存储分配 动态存储分配栈式动态存储分配栈式 堆式堆式声明的作
4、用域声明的作用域 词法作用域词法作用域 动态作用域动态作用域例：例：（1）program dynamic(i,0);(2)var r:real(3)procedure show;(4)begin write(r:5:3)end;(5)procedrue small;(6)var r:real;(7)begin r:=0.125;show end;(8)begin(9)r:=0.25;(10)show;small;write/n;(11)show;small;write/n;(12)end.lexical scope0.250 0.2500.250 0.250dynamic scope0.250
5、 0.1250.250 0.125术语术语 静态：如果一个名字的性质通过说明语句静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是或隐或显规则而定义，则称这种性质是“静态静态”确定的。确定的。动态：如果名字的性质只有在程序运行时动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为才能知道，则称这种性质为“动态动态”确定确定的。的。可变可变(动态动态)数组：数组：若一个数组所需的存储空间的大小在编若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则译时就已知道，则称它为确定数组，否则称为可变称为可变(动态动态)数组。数组。例例 procedure A
6、(m,n:integer);begin real z;array Bm:n;begin end;end;数组内情向量数组内情向量:编译中，将数组的有关信息记录在一些单元中，称为编译中，将数组的有关信息记录在一些单元中，称为“内“内情向量”，确定数组，放在符号表中；可变数组，运行时建立情向量”，确定数组，放在符号表中；可变数组，运行时建立相应的内情向量。相应的内情向量。Al 1:u 1,l 2:u 2,l ln n :u un n l1 u1 l2 u2 :type a（首地址）（首地址）n C 过程活动记录过程活动记录 AR:为说明方便，假定程序是由过程组成，过程区分为源文本，为说明方便，假定
7、程序是由过程组成，过程区分为源文本，运行时称作过程的激活。运行时称作过程的激活。一个过程的一次执行所需要的信息使用一个连续的存储区来一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区管理，这个区（块）叫做一个活动记录或（块）叫做一个活动记录或 frame（帧帧）一般这个段要记录：一般这个段要记录：临时值，如计算表达式时的中间工作单元。临时值，如计算表达式时的中间工作单元。局部变量局部变量（数据）（数据）保存运行过程前的状态保存运行过程前的状态（返回地址，寄存器值）（返回地址，寄存器值）存取链存取链（可选）（可选）对于非局部量的引用。对于非局部量的引用。控制链控制链（可选）（可选）
8、指向调用者的活动记录，释放栈。指向调用者的活动记录，释放栈。实参实参（形式单元）（形式单元）返回值返回值（对函数）（对函数）（有时可使用寄存器存放返回值）（有时可使用寄存器存放返回值）简单的栈式分配方案简单的栈式分配方案 程序结构特点程序结构特点:过程定义不嵌套，过程可过程定义不嵌套，过程可递归调用，含可变数组递归调用，含可变数组;例例:main 全局变量的说明全局变量的说明 proc R end R;proc Q end Q;主程序执行语句主程序执行语句 end mainMain-Q-R Main-Q-Q TOP-R 的活动记录的活动记录 Q 的活动记录的活动记录 SP-Q 的活动记录的活动
9、记录 Q 的活动记录的活动记录 主程序全局主程序全局 主程序全局主程序全局 数据区数据区 数据区数据区TOP-临时工作单元临时工作单元 局部简单变量局部简单变量 局部数组的内情向量局部数组的内情向量 保存运保存运 行过程前的状态行过程前的状态（返回地址，寄存器值）（返回地址，寄存器值）实参实参（形式单元）和参数个数（形式单元）和参数个数 SP-控制链控制链（老（老 SP）TOP R 的数组区的数组区 SP R 的活动记录的活动记录 Q 的活动记录的活动记录 主程序全局主程序全局 数据区数据区 嵌套过程语言的栈式嵌套过程语言的栈式分配方案分配方案主要特点主要特点：（语言）一个过程可以引用包围它的
10、任（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，一外层过程所定义的标识符（如变量，数组或过程等）。数组或过程等）。（实现）一个过程可以引用它的任一外（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。层过程的最新活动记录中的某些数据。关键技术：解决对非局部量的引用（存关键技术：解决对非局部量的引用（存取）。取）。设法跟踪每个外层过程的最新活动记录设法跟踪每个外层过程的最新活动记录AR的位置。的位置。跟踪办法：跟踪办法：1.用静态链（如用静态链（如PL/0的的SL）。）。2.用用DISPLAY表。表。例：例：program main(i,0);程序结构图程序
11、结构图 proc R(c,d);R end /*R*/proc P (a);主主 proc Q(b);P Q call R R(x,y);end /*Q*/call Q Q(z);call P end /*P*/call R P（W）；）；R（U，V）；）；end /*main*/用用Display表的方案表的方案(1)主程序主程序-(2)P-(3)Q-(4)R P 的的活动记录活动记录主程序的主程序的活动记录活动记录 d1d0displaysptop主程序的主程序的活动记录活动记录 d0spdisplaytop（1）（2）用用Display表的方案表的方案 主程序主程序-P-Q-RR 的的活
12、动记录活动记录 Q 的的活动记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录Q 的的活动记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录 displayd2d1d0 d1d0 displaysptoptopsp（3）（4）DISPLAY表的维护和建立表的维护和建立 DISPLAY表表d 运行栈运行栈 0 主程活动记录地址主程活动记录地址 1 R活动记录地址活动记录地址 .0 老老 SP 1 返回地址返回地址 2 全局全局 DISPLAY地址地址 3 参数个数参数个数 4形式单元形式单元 .d DISPLAY .简单变量简单变量 数组内情向量数组内情向
13、量 临时变量临时变量 当过程的层次为当过程的层次为n，它的它的 display为为n+1个个值。值。一个过程被调用时，一个过程被调用时，从调用过程的从调用过程的DISPLAY表中自下向表中自下向上抄录上抄录n个个SP值，再加值，再加上本层的上本层的SP值。值。全局全局DISPLAY地址地址 Procedure A(m,n);integer m,n;B1:begin real z;array Bm:n;B2:begin real d,e;L3:2 end;B4:begin array C1:m;1 B5:begin real e;L6:5 4 end;end;L8:end;分程序结构的存储分程序
14、结构的存储分配方案分配方案 处理分程序结构存储分配方案的一处理分程序结构存储分配方案的一种简单办法是，把分程序看成种简单办法是，把分程序看成“无参过无参过 程程”，它在哪里定义就在哪里被调用。，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用因此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低到处理分程序中。但这种做法是极为低效的。效的。一则，每逢进入一则，每逢进入 一个分程序，就照样建一个分程序，就照样建立连接数据和立连接数据和DISPLAY表表,这是不必要的。这是不必要的。二则二则，当从内层分程序向外层转移时，当从内层分程序向外层转移时，可能同时要结束若干个分
15、程序。可能同时要结束若干个分程序。按照过程处理办法，意味着必须一层按照过程处理办法，意味着必须一层一层地通过一层地通过“返回返回”来恢复所要到达的来恢复所要到达的那个分程序的数据区，但不能直接到达。那个分程序的数据区，但不能直接到达。例如：如果有一个从第例如：如果有一个从第5层分程序转出到达层分程序转出到达第第1层分程序的标号层分程序的标号L，虽然在第，虽然在第5层分程层分程序工作时知道序工作时知道L所属的层数，我们极易从所属的层数，我们极易从DISPLAY中获得第中获得第1层分程序的活动记层分程序的活动记录基址（录基址（SP），但是怎么知道第），但是怎么知道第1层分程层分程序进入时的序进入时
16、的TOP呢？唯一的办法是从呢？唯一的办法是从 5,4,3和和2各层顺序退出。但这种办法是很各层顺序退出。但这种办法是很浪费时间的。浪费时间的。为了解决上述问题，可采取两种措施。第为了解决上述问题，可采取两种措施。第一，对每个过程或分程序都建立有自己一，对每个过程或分程序都建立有自己的栈顶指示器的栈顶指示器TOP，代替原来仅有过程，代替原来仅有过程的栈顶指示器的栈顶指示器,每个每个TOP的值保存在各自的值保存在各自活动记录中。这样，上述的第二个问题活动记录中。这样，上述的第二个问题便可解决。第二，不把分程序看作便可解决。第二，不把分程序看作“无无参过程参过程”，每个分程序享用包围它的那，每个分程
17、序享用包围它的那个最近过程的个最近过程的DISPLAY。每个分程序都。每个分程序都隶属于某个确定的过程，分程序的层次隶属于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。是相对于它所属的那个过程进行编号的。：每个过程被当作是每个过程被当作是0层分程序。而过程体层分程序。而过程体分程序（假定是一个分程序）当作是它分程序（假定是一个分程序）当作是它所管辖的第所管辖的第1层分程序。层分程序。这样，每个过程的活动记录所含的内容有：这样，每个过程的活动记录所含的内容有：1.过程的过程的TOP值，它指向过程活动记录的值，它指向过程活动记录的栈顶位置。栈顶位置。2.连接数据，共四项：连接数据
18、，共四项：（1)老老SP值；值；（2)返回地址；返回地址；(3)全局全局DISPAY地址；地址；（4)调用时的栈顶单元地址，老调用时的栈顶单元地址，老TOP。3.参数个数和形式单元参数个数和形式单元 4.DISPAY表。表。5.过程所辖的各分程序的局部数据单元。过程所辖的各分程序的局部数据单元。对于每个分程序来说，它们包括：对于每个分程序来说，它们包括：（1)分程序的分程序的TOP值。当进入分程序时它值。当进入分程序时它含现行栈顶地址，以后，用来定义栈的含现行栈顶地址，以后，用来定义栈的新高度（分程序的新高度（分程序的TOP值）；值）；（2)分程序的局部变量，分程序的局部变量，数组内情向量和数
19、组内情向量和临时工作单元。临时工作单元。变 量 e B5 的 T O P 数 组 C 的 内 情 向 量 变 量 e 和 d B4 的 T O PB2的 TOP 数 组 B 的 内 情 向 量 变 量 zKB1 的 T O PDD I S P L A Y6形 式 单 元 m,n5参 数 个 数：24调 用 时 的 栈 顶 地 址（老 T O P）3全 局 D I S P L A Y 地 址2返 回 地 址1老 S P0过 程 的 T O P，指 向 活 动 记 录 之 顶B的 内 情 向 量 Z B1的 T O PD I S P L A YD I S P L A Y 形 式 单 元 m ,n
20、2 形 式 单 元 m ,n 2连 接 数 据连 接 数 据 A 的 T O PA的 T O P (a)(b)(a)到 达 标 号 B1处 ;(b)进 入 分 程 序 B1;B Z B1T O 数 组 B 数 组 B e dB22的 T O PB 的 内 情 向 量B 的 内 情 向 量 z zB1 的 T O PB1的 T O PD I S P L A YD I S P L A Y 形式单元 m,n 2 形式单元 m,n 2连 接 数 据连接 数 据A 的 T O PA 的 T O P (c)(d)(c)数组 B 分配之后；（d）进入分程序 B22;数 组C 数 组 C 数 组B 数 组 B
21、 C的 向 量 内 情 eB5的T O PC 的 内 情 向 量B4的T O PB4的T O PB 的 内 情 向 量B的 内 情 向 量 z ZB1的T O PB1 的T O PD I S P L A YD I S P L A Y 形式单元 m,n 2 形式单元 m,n 2连接数据连 接 数 据A的T O PA的T O P (e)(f)(e)进入分程序B4分配数组C之后；(f)进入分程序B5。参数传递参数传递(1)procedure exchangel(i,j:integer);(2)var x:integer;(3)begin;(4)x:=ai;ai:=aj;aj:=x(5)end;带有非
22、局部变量和形参的带有非局部变量和形参的PASCAL过程过程非局变量非局变量ai和和aj的值进行交换，的值进行交换，i,j为形参（在为形参（在这里是传值）这里是传值）(1)program reference(input,output);(2)var a,b:integer;(3)procedure swap(var x,y:integer);(4)var temp:integer;(5)begin (6)temp:=x;(7)x:=y;(8)y:=temp(9)end;(10)begin(11)a:=1;b:=2;(12)swap(a,b);(13)writeln(a=,a);writeln(b
23、=,b)(14)end.带有过程带有过程swap的的PASCAL程序程序 传地址（变量参数）传地址（变量参数）例如：过程例如：过程 swap(var x,y:integer);swap(a,b）；（）；（a,b为调用时的为调用时的实参实参）调用结果调用结果a,b的值被改变。的值被改变。传值（值调用）传值（值调用）特点是对形式参数的任何运算不影响实参的值。特点是对形式参数的任何运算不影响实参的值。例如：过程例如：过程 swap(x,y:integer);swap(a,b）；）；其结果：其结果：a,b调用前的值不改变。调用前的值不改变。传值传值的实现的实现 1.形式参数当作过程的局部变量处理，即形
24、式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。的形式单元（用以存放实参）。2.调用过程计算实参的值，并将其放在对调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。应形式单元开辟的空间中。3.被调用过程执行时，就像使用局部变量被调用过程执行时，就像使用局部变量一样使用这些形式单元。一样使用这些形式单元。procedure swap(x,y:integer);var temp:integer;begin temp:=x;x:=y；y:=tem
25、p end；调用swap(a,b)过程将不会影响a和b的值。其结果等价于执行下列运算：x:=a；y:=b；temp:=x；x:=y；y:=temp传地址传地址的实现的实现（call-by-reference)(call-by-address)(call-by-location)把实在参数的地址传递给相应的形参，即把实在参数的地址传递给相应的形参，即 调用过程把一个指向实参的存储地址的指针传调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：递给被调用过程相应的形参：1实在参数是一个名字，或具有左值的表达式实在参数是一个名字，或具有左值的表达式-传递左值传递左值2实在参数是无左值的
26、表达式实在参数是无左值的表达式-计算值，放入一计算值，放入一存储单元，传此存储单元地址存储单元，传此存储单元地址3目标代码中，被调用过程对形参的引用变成对目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用传递给被调用过程的指针的间接引用procedure swap(x,y:integer);var temp:integer;begin temp:=x;x:=y；y:=temp end；调用swap(i,ai)其结果等价于执行下列运算：1把 I和ai的地址分别放到x和y相应的单元a1,a2 2(temp:=x；)temp的内容置为a1所指单元中存的内容 3(x:=y;)a1
27、所指单元的内容置为a2所指单元值4(y:=temp)a2所指单元的内容置为temp的值(1)swap(x,y)(2)int *x,*y;(3)int temp;(4)temp=*x;*x=*y;*y=temp;(5)(6)main()(7)int a=1,b=2;(8)swap(&a,&b);(9)printf(“a is now%d,b is now%dn”,a,b);(10)在一个值调用过程中使用指针的在一个值调用过程中使用指针的C程序程序在在C程序中无传地址所以用指针实现。程序中无传地址所以用指针实现。过程调用的四元式序列过程调用的四元式序列 S call id(),E Epar T1p
28、ar T2par Tncall id,n 过程作为参数传递三种环境：词法环境 传递环境 活动环境 program param(input,output);procedure b(function h(n:integer):integer);(*)var m:integer;begin m:=3;writeln(h(2)endb;procedure c;(*)var m:integer;function f(n:integer):integr;(&)begin f:=m+n endf;begin m:=0;b(f)end c begin c end.(1)program param(input,
29、output);(2)procedure b(function h(n:integer):integer);(3)begin writeln(h(2)endb;(4)procedure c;(5)var m:integer;(6)function f(n:integer):integr;(7)begin f:=m+n endf;(8)begin m:=0;b(f)end c;(9)begin(10)c(11)end 图10-27 嵌套过程作为参数传递 param c 存取链 m b 存取链图 10-28 连同存取链一起 传递过程实参各种数据对象的存储分配数据对象 name 名字，名称 type
30、 类型 location 内存地址 value 值 component 成分 例：按行例：按行 A是是 10 20 的二维数组的二维数组A1,1A1,2.第一行第一行.A1,20A2,1.第二行第二行.A10,20 第十行第十行数组元素的地址计算数组元素的地址计算设设 A1，1的地址为的地址为 a，每个元素占一个字，每个元素占一个字Ai，j的地址：的地址：a+（i-1）20+（j-1）=（a-21）+（20i+j）一般：一般：arrayAl1：u1，l2：u2，ln：un令令 di=ui-li+1元素元素 Ai1，i2，in的地址的地址 D D=a+（i1-l1）d2d3dn+（i2-l2）d
31、3d4dn+（in-1-l n-1）dn+（in-ln）经因子分解后得经因子分解后得 D=CONSPART+VARPART其中其中 CONSPART=a-C C=（l1d2+l2）d3+l3）d4+l n-1）dn+ln VARPART=（i1d2+i2）d3+i3）d4+i n-1）dn+in四元式四元式 两组两组 VARPART T CONSPARTT1T1 T表示数组元素的地址表示数组元素的地址数组元素引用：数组元素引用：X：=T1 T对数组元素赋值：对数组元素赋值：T1 T：=X建立内情向量，问配内存的目标代码（n维可变数组,type-每个元素占一个字）begin k:=1;n:=1;
32、c:=0;while k=n do begin di:=ui-li+1;m:=m*di;c:=c*di+li;把li,ui和di填进内情向量表区；k:=k+1 end;申请m个空间,令首地址为a;把n,c,type,a填进内情 向量表区end赋值中数组元素的翻译A V:=EV id|id ,E|EV|id ,E|id E结构（记录），抽象数据类型对象类实例变量的存储结构(CIR)class parent|class parent public int a,b,c;|public a,b,c;public void draw().;|public virtual void draw();|.cl
33、ass child:public parent|public d,e;|public void sift();|void draw();？分程序，栈式，pl/0 符号表变量地址Proc(parameters);int i,j;/*statement*/int k,l;/*statement*/int m,n;/*statement*/int x;/*statement*/int y;/*statement*/？语言解释系统的内存布局9、春去春又回，新桃换旧符。在那桃花盛开的地方，在这醉人芬芳的季节，愿你生活像春天一样阳光，心情像桃花一样美丽，日子像桃子一样甜蜜。23.8.2023.8.20Su
34、nday,August 20,202310、人的志向通常和他们的能力成正比例。11:34:2811:34:2811:348/20/2023 11:34:28 AM11、夫学须志也，才须学也，非学无以广才，非志无以成学。23.8.2011:34:2811:34Aug-2320-Aug-2312、越是无能的人，越喜欢挑剔别人的错儿。11:34:2811:34:2811:34Sunday,August 20,202313、志不立，天下无可成之事。23.8.2023.8.2011:34:2811:34:28August 20,202314、Thank you very much for taking
35、me with you on that splendid outing to London.It was the first time that I had seen the Tower or any of the other famous sights.If Id gone alone,I couldnt have seen nearly as much,because I wouldnt have known my way about.。2023年8月20日星期日上午11时34分28秒11:34:2823.8.2015、会当凌绝顶，一览众山小。2023年8月上午11时34分23.8.2011:34August 20,202316、如果一个人不知道他要驶向哪头，那么任何风都不是顺风。2023年8月20日星期日11时34分28秒11:34:2820 August 202317、一个人如果不到最高峰，他就没有片刻的安宁，他也就不会感到生命的恬静和光荣。上午11时34分28秒上午11时34分11:34:2823.8.20谢谢观看THE END
