[理学]编译原理第9章 运行时存储空间组织.ppt

运行时存储空间组织 §1运行时存储空间组织基本内容 一、运行时存储空间组织的基本思想： 有些存储分配是在运行阶段进行的，但编译程序在编译阶段要为源程序中用户定义的变量与常量、临时变量、过程与函数调用时需要的连接数据、返回地址等组织好运行阶段的存储空间，为其设计好存储组织形式，并将这种组织形式通过生成的目标代码体现出来。在运行阶段，随着目标代码的运行，数据的存储组织形式便得以实现。 二、 运行时存储器的划分 一个程序在运行时刻的内存划分: 三、过程的活动与活动记录 一个过程的活动指的是该过程的一次执行。即，每次执行一个过程体，就产生该过程的一个活动。 活动记录：为了管理过程在一次执行中所需要的信息，使用一个连续的存储块记录表示该活动的相关信息，称为该过程的活动记录。 当前活动记录一般包含如下内容： 连接数据： ①返回地址 ②动态链：指向调用该过程前的运行活动记录地址的指针。运行时，使运行栈上各数据区按动态建立的次序连成链。链头为栈顶起始位置。 ③静态链：指向静态直接外层必威体育精装版活动记录地址的指针，用来访问非局部数据。 形式单元：存放相应实在参数的地址或值。 局部数据区：局部数据、内情向量、临时单元。 每个过程的活动记录内容(非嵌套语言) 每个过程的活动记录内容(嵌套语言) 每个过程的活动记录内容 四、参数的传递方式及其实现 不同语言的形实参数结合方式不同，解决的方法也不相同。常见的有四种： ①传地址（Call by reference）（类似Pascal变参） 每一个形式参数都有一个形式单元，用来存放实在参数的地址。在子程序中，对形式参数的引用都是对实参单元的引用。 实参是变量：传地址 实参是常量：值放临时单元，传临时单元地址 实参是表达式：值放临时单元，传临时单元地址 例如：有程序段： ①传地址举例： 执行了语句：x:=x+5;后 运行结果为： 8 , 8 8 ②传值（Call by value）(类似Pascal值形参) 每一个形式参数都有一个形式单元，用来存放实在参数的值。在子程序中，对形式参数的引用都是对存放值的形式单元的引用。 ③传结果（Call by result） 每一个形式参数都有两个形式单元，一个用来存放实参值的单元x，另一个用来存放实参地址的单元y。在子程序中，对形式参数的引用都是对存放值的形式单元x的引用，调用结束返回前，按y单元地址将结果写入实在参数对应的单元。 ②传值举例： 执行了语句：x:=x+5;后 运行结果为： 8 , 3 3 ③传结果举例： 执行了语句：x:=x+5;后 运行结果为： 8 , 3 8 ④传名/换名（Call by name） 过程调用的作用相当于把被调用段的过程体抄到调用出现的位置，把所有形式参数都替换成实在参数（文字替换），若替换时有同名标识符，则换名表示。这是ALGOL60所定义的一种特殊的形实结合方式。 ④传名/换名： 假设有如下示意性程序段，采用传名方式： procedure R(x , I ) begin I:=2; x:=5; I:=3; x:=I-1; end; 假设程序中，B的所有元素初值为3，且有调用： j:=2; R( B[ j*2 ] , j ) 程序运行后，被替换成： procedure R( B[ j*2 ] , j ) begin j:=2; B[ j*2 ] :=5; j:=3; B[ j*2 ] :=j-1; end; 四、存储分配策略 1、静态存储分配：在编译时就能确定目标程序运行中所需要的全部空间大小，则编译时就能安排好目标程序的全部数据空间，并能确定每个数据项的单元地址、存储空间，这种分配方法叫做静态存储分配。 例如：FORTRAN语言中，不允许递归，不含可变体积的数据对象。 ∴FORTRAN可以使用静态存储分配策略。 2、栈式存储分配：将整个存储空间设计成一个栈，每当调用一个过程时就将它的活动记录压入栈，在栈顶形成当前过程数据工作区，当过程结束时将活动记录弹出栈。（在这种分配方式下，每个过程可能有若干个不同的活动记录，每个活动记录表示了一次不同的调用）。 分为： 简单栈式存储分配（无嵌套过程） 嵌套过程的栈式存储分配 3、堆式存储分配：允许数据对象自由地分配和释放，空间的使用不一定按照“先申请后释放”的原则，这种语言通常采用堆式存储分配。 编译程序为了组织存储空间，必须考虑下面几个问题： 过程是否允许递归？ 当控制从一个过程的活动返回时，对局部名称的值如何处理？ 过程是否允许引用非局部名称？ 过程调用时如何传递参数；过程是否可以做为参数被传递和做为结果被返