《编译原理教案第九章运行时存储空间经济组织1PPT课件》由会员分享，可在线阅读，更多相关《编译原理教案第九章运行时存储空间经济组织1PPT课件（52页珍藏版）》请在金锄头文库上搜索。
1、第九章第九章 运行时存储空间组织运行时存储空间组织概述概述任务：编译程序对目标程序运行时的数据空间任务：编译程序对目标程序运行时的数据空间的组织和管理（设计运行环境和分配存储）的组织和管理（设计运行环境和分配存储） 如如 通常栈式存储分配布局可为：通常栈式存储分配布局可为： 目标代码区目标代码区 静态数据区静态数据区 Stack heap运行环境和存储分配运行环境和存储分配设计分析设计分析逻辑阶段：在目标代码生成前，作准备逻辑阶段：在目标代码生成前，作准备实质：实质： 关联（关联（Binding）将源程序的文本将源程序的文本 程序运行动作的实现程序运行动作的实现 源文件中的名字源文件中的名字N
2、 运行时的存储运行时的存储S S在语义学中，使用术语在语义学中，使用术语environment函数表示函数表示env: NS (NS (N到到S S的映射的映射) )术语术语静态：如果一个名字的性质通过说明语句静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是或隐或显规则而定义，则称这种性质是“静静态态”确定的。确定的。动态：如果名字的性质只有在程序运行时动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为才能知道，则称这种性质为“动态动态”确定的。确定的。可变可变 (动态动态)数组：数组： 若一个数组所需的存储空间的大小在编若一个数组所需的存储空间的大小在编译时就
3、已知道，则称它为确定数组，否则译时就已知道，则称它为确定数组，否则称为可变称为可变(动态动态)数组。数组。例例 procedure A(m,n:integer); begin real z; array Bm:n; begin end; end; 简单的栈式分配方案简单的栈式分配方案程序结构特点程序结构特点:过程定义不嵌套，过程可过程定义不嵌套，过程可递归调用，含可变数组递归调用，含可变数组; 例例: main 全局变量的说明全局变量的说明proc Rend R;proc Q end Q;主程序执行语句主程序执行语句 end main 嵌套过程语言的栈式嵌套过程语言的栈式分配方案分配方案l主要
4、特点主要特点：（语言）一个过程可以引用包围它的任（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，一外层过程所定义的标识符（如变量，数组或过程等）。数组或过程等）。（实现）一个过程可以引用它的任一外（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。层过程的最新活动记录中的某些数据。 关键技术：解决对非局部量的引用（存关键技术：解决对非局部量的引用（存取）。取）。设法跟踪每个外层过程的最新活动记录设法跟踪每个外层过程的最新活动记录AR的位置。的位置。跟踪办法：跟踪办法： 1. 用静态链（如用静态链（如PL/0的的SL）。）。 2. 用用DISPLAY表。表。用
5、用Display表的方案表的方案(1)主程序主程序-(2)P-(3)Q-(4)R P 的的活动记录活动记录主程序的主程序的活动记录活动记录 d1d0displaysptop主程序的主程序的活动记录活动记录 d0spdisplaytop（1）（2）用用Display表的方案表的方案主程序主程序-P-Q-RR 的的活动记录活动记录 Q 的的活动记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录Q 的的活动记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录 displayd2d1d0 d1d0 displaysptoptopsp（3）（4）DISPLAY表的维
6、护和建立表的维护和建立 DISPLAY表表d 运行栈运行栈 0 主程活动记录地址主程活动记录地址 1 R活动记录地址活动记录地址 . 当过程的层次为当过程的层次为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:beg
7、in array C1:m; 1 B5:begin real e; L6: 5 4 end; end; L8:end; 分程序结构的存储分程序结构的存储分配方案分配方案 处理分程序结构存储分配方案的一处理分程序结构存储分配方案的一种简单办法是，把分程序看成种简单办法是，把分程序看成 “无参过无参过 程程”，它在哪里定义就在哪里被调用。因，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效处理分程序中。但这种做法是极为低效的。的。 一则，每逢进入一则，每逢进入 一个分程序，就照样建一个分程序，就照样建立连接数据和立
8、连接数据和DISPLAY表表,这是不必要的。这是不必要的。 二则二则 ，当从内层分程序向外层转移时，当从内层分程序向外层转移时，可能同时要结束若干个分程序。可能同时要结束若干个分程序。 按照过程处理办法，意味着必须一层按照过程处理办法，意味着必须一层一层地通过一层地通过“返回返回” 来恢复所要到达的那来恢复所要到达的那个分程序的数据区，但不能直接到达。个分程序的数据区，但不能直接到达。例如：如果有一个从第例如：如果有一个从第5层分程序转出到达层分程序转出到达第第1层分程序的标号层分程序的标号L，虽然在第，虽然在第5层分程层分程序工作时知道序工作时知道L所属的层数，我们极易从所属的层数，我们极易
9、从DISPLAY中获得第中获得第1层分程序的活动记录层分程序的活动记录基址（基址（SP），但是怎么知道第），但是怎么知道第1层分程序层分程序进入时的进入时的TOP呢？唯一的办法是从呢？唯一的办法是从 5,4,3和和2各层顺序退出。但这种办法是很浪费各层顺序退出。但这种办法是很浪费时间的。时间的。 为了解决上述问题，可采取两种措施。第为了解决上述问题，可采取两种措施。第一，对每个过程或分程序都建立有自己一，对每个过程或分程序都建立有自己的栈顶指示器的栈顶指示器TOP，代替原来仅有过程，代替原来仅有过程的栈顶指示器的栈顶指示器, 每个每个TOP的值保存在各自的值保存在各自活动记录中。这样，上述的第
10、二个问题活动记录中。这样，上述的第二个问题便可解决。第二，不把分程序看作便可解决。第二，不把分程序看作“无参无参过程过程”，每个分程序享用包围它的那个最，每个分程序享用包围它的那个最近过程的近过程的DISPLAY。每个分程序都隶属。每个分程序都隶属于某个确定的过程，分程序的层次是相于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。对于它所属的那个过程进行编号的。： 每个过程被当作是每个过程被当作是0层分程序。而过程体层分程序。而过程体分程序（假定是一个分程序）当作是它分程序（假定是一个分程序）当作是它所管辖的第所管辖的第1层分程序。层分程序。这样，每个过程的活动记录所含的内容有
11、：这样，每个过程的活动记录所含的内容有：1.过程的过程的TOP值，它指向过程活动记录的值，它指向过程活动记录的栈顶位置。栈顶位置。2.连接数据，共四项：连接数据，共四项： （1)老老SP值；值；（2)返回地址；返回地址； (3)全局全局DISPAY地址；地址；（4)调用时的栈顶单元地址，老调用时的栈顶单元地址，老TOP。 3. 参数个数和形式单元参数个数和形式单元 4. DISPAY表。表。5. 过程所辖的各分程序的局部数据单元。过程所辖的各分程序的局部数据单元。 对于每个分程序来说，它们包括：对于每个分程序来说，它们包括：（1)分程序的分程序的TOP值。当进入分程序时它值。当进入分程序时它含
12、现行栈顶地址，以后，用来定义栈的含现行栈顶地址，以后，用来定义栈的新高度（分程序的新高度（分程序的TOP值）；值）；（2)分程序的局部变量，分程序的局部变量， 数组内情向量和数组内情向量和临时工作单元。临时工作单元。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; 参数传递参
13、数传递(1)procedure exchangel(i,j:integer);(2) var x:integer;(3) begin;(4) x:=ai; ai:=aj; aj:=x(5) end; 带有非局部变量和形参的带有非局部变量和形参的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)
14、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=,b)(14)end. 带有过程带有过程swap的的PASCAL程序程序 传地址（变量参数）传地址（变量参数） 例如：过程例如：过程 swap(var x,y:integer); swap(a,b）；（）；（ a,b为调用时的为调用时的实参实参 ） 调用结果调用结果a,b的值被改变。的值被改变。传值（值调用）传值（值调用）特点是对形式参数的任何运算不影响实参的值。特点
15、是对形式参数的任何运算不影响实参的值。 例如：过程例如：过程 swap(x,y:integer); swap(a,b）；）；其结果：其结果： a,b调用前的值不改变。调用前的值不改变。传值传值的实现的实现1.形式参数当作过程的局部变量处理，即形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。的形式单元（用以存放实参）。2.调用过程计算实参的值，并将其放在对调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。应形式单元开辟的空间中。3.被调用过
16、程执行时，就像使用局部变量被调用过程执行时，就像使用局部变量一样使用这些形式单元。一样使用这些形式单元。procedure swap( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp 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) 把实在参数的地址传递给相应的形参，
17、即把实在参数的地址传递给相应的形参，即 调用过程把一个指向实参的存储地址的指针传调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：递给被调用过程相应的形参：1实在参数是一个名字，或具有左值的表达式实在参数是一个名字，或具有左值的表达式-传递左值传递左值2实在参数是无左值的表达式实在参数是无左值的表达式-计算值，放入一计算值，放入一存储单元，传此存储单元地址存储单元，传此存储单元地址3目标代码中，被调用过程对形参的引用变成对目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用传递给被调用过程的指针的间接引用procedure swap( x,y:integer
18、); 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所指单元的内容置为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;(
19、8) swap(&a,&b);(9) printf(“a is now %d,b is now %dn”,a,b);(10) 在一个值调用过程中使用指针的在一个值调用过程中使用指针的C程序程序在在C程序中无传地址所以用指针实现。程序中无传地址所以用指针实现。过程调用的四元式序列过程调用的四元式序列 S call id() ,E Epar T1par T2par Tncall id,n 过程作为参数传递三种环境：词法环境 传递环境 活动环境 program param(input,output); procedure b(function h(n:integer):integer);(*) va
20、r 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,output);(2)procedure b(function h(n:integer):integer);(3) begin writeln(h(2) endb;(4)procedure c;(5) var m:integer
21、;(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 嵌套过程作为参数传递各种数据对象的存储分配数据对象 name 名字，名称 type 类型 location 内存地址 value 值 component 成分 建立内情向量，问配内存的目标代码（n维可变数组, type-每个元素占一个字）begin k:=1;n:=1;c:=0; while k=n do begin di:=ui-li+ 1; m:=m*di; c:=c
22、*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(); | .class 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*/
