《《编译原理实践及应用》PPT教学课件-第6章 运行时存储分配》由会员分享,可在线阅读,更多相关《《编译原理实践及应用》PPT教学课件-第6章 运行时存储分配(20页珍藏版)》请在金锄头文库上搜索。
1、运行时存储空间的组织,第六章,本章要求,主要内容:程序的静态文本与它运行时的活动之间的关系,源程序运行时各种对象的存储空间主要有三种分配方式:静态存储分配、栈式存储分配和堆式存储分配 重点掌握:源程序运行时的活动,参数传递方式,程序中名字的作用域,局部数据区的内容,存储空间的分配方式,6.1 程序执行时的活动,静态和动态的联系 名字和数据对象 数据对象的动态表示 名字的作用域 数据对象的存储分配 过程和活动 参数处理 运行时支撑程序包,过程相关的几个概念,过程定义是一个声明,它的最简单的形式是把一个标识符(过程的名字)和一段语句联系起来。 当过程名出现在可执行语句中时,则称过程在该点被调用 出
2、现在过程定义中的标识符称为形式参数(或形参) 出现在过程调用中的标识符或常数称为实在参数(或实参),一个过程的一次执行指的是从过程体的起点开始,最后退出该过程,将控制返回到该过程被调用之后的位置。 一个过程的活动指的是该过程的一次执行。就是说,每次执行一个过程体就产生该过程的一个活动。 从执行该过程体的第一步操作到最后一步操作之间的操作序列所花的时间称为该过程的一个活动的生存期,名字的作用域,语言中名字的声明是把信息与名字联系起来的语法结构。 区分同名程序声明:最接近的嵌套规则 int a , b; int *p; int foo( int a ) int b, c; char *p; p =
3、 malloc( sizeof( char ) ); b = foo( 1 ); ,作用域:一个声明起作用的程序部分称为该声明的作用域 局部和非局部:过程中名字的出现,如果是在该过程的一个声明的作用域内,则这个出现称为局部于该过程,参数的传递,传地址(常用):把实在参数的地址传递给相应的形式参数 传值(常用):调用段把实在参数的值传给被调用段。被调用段把实参值抄进形式单元中,再使用。 得结果:形式参数对应有两个单元,第一个单元放实参的地址,第二个单元放实参的值。对形式参数的任何引用或赋值都看成是对第二个单元的直接访问,过程返回前必须把第二个单元的内容存放到第一个单元所指的那个实参单元之中 传名
4、:(ALGOL60 )过程调用相当于把被调过程的过程体抄到调用出现的位置,把其中任一出现的形式参数都替换成相应的实在参数(文字替换),名字的绑定,程序中声明的名字和动态数据对象的关系 数据对象是保存值的存储单元 一个名字可能代表不同的数据对象 环境:表示将名字映射到存储单元(即名字的左值)的函数 状态:表示将存储单元映射到它所保存的值(即名字的右值)的函数 赋值操作只改变状态,但不改变环境 结合:如果环境把存储单元s联系到名字x,则称x绑定到s,这个联系本身称为x的绑定,名字绑定要考虑的问题,过程是否递归 当控制从过程的活动返回时,局部名字的值是否要保留 过程能否引用非局部的名字 过程调用时参
5、数是如何传递的 过程是否可以作为参数被传递 过程能否作为结果值返回 存储区能否在程序控制下动态地分配 存储区是否必须显式地释放,6.2 运行时内存的划分,程序运行时如何使用内存: 目标代码的存放 目标代码可以存放在静态确定的区域,其长度在编译时即可确定 数据对象 可静态分配的数据对象,其地址可以编译到目标代码中 动态分配 控制栈:记录过程活动 堆:可以存放动态分配的数据等,但开销要比栈大,局部数据区的内容,活动记录:过程的一次执行所需要的信息用一块连续的存储区来管理,这块存储区叫做活动记录或帧,当调用一个过程时,就要为其建立一个活动记录 并不是所有的语言或编译器都是如此 寄存器的使用 活动记录
6、的操作: 过程被调用时入栈 过程返回时出栈,活动记录的各个域的作用,临时数据:临时变量的存储等 局部数据:局部于过程执行的数据 机器状态:保存过程调用前的机器状态信息(返回地址) 可选的访问链:用于非局部数据的访问 可选的控制链:指向调用者的活动记录 实在参数:参数个数较少时,可以考虑用寄存器传递,效率高;参数多时用用这个域传递 返回值:用于存放被调用过程返回给调用过程的值,也可以用寄存器返回(效率高,但形式受限制),6.3 存储分配策略,静态存储分配 栈式存储分配 堆式存储分配,静态存储分配策略,名字的绑定: 编译时实现,不需要运行时支撑程序 名字和存储的绑定是固定的 允许名字的值在过程停止
7、活动后保持 根据名字的类型,编译器可以在静态时刻确定该名字所需的存储空间,效率 局限: 数据对象的长度和它在内存中位置的限制必须在编译时知道 不允许递归过程 不允许有动态数据结构 在FORTRAN77中,静态存储分配策略,每个过程的活动记录可以与它的代码放在一起,静态存储分配策略(2),PROGRAM CNSUME CHARACTER * 50 BUF INTEGER NEXT CHARACTER C , PRDUCE DATA NEXT / 1 /, BUF / / 6 C = PRDUCE( ) BUF( NEXT , NEXT ) = C NEXT = NEXT + 1 IF ( C .
8、NE. ) GOTO 6 WRITE( * , ( A ) ) BUF END CHARACTER FUNCTION PRDUCE( ) CHARACTER * 80 BUFFER INTEGER NEXT SAVE BUFFER , NEXT DATA NEXT / 81 / IF ( NEXT .GT. 80 ) THEN READ(* , ( A ) ) BUFFER NEXT = 1 END IF PRDUCE = BUFFER( NEXT , NEXT ) NEXT = NEXT + 1 END,栈式存储分配策略,递归过程要求栈分配 允许动态数据对象的存在 满足先进后出的次序 控制栈
9、: 活动记录和栈的关系 局部量的存储空间包含在对应调用的活动记录中 局部量的值会随着过程调用结束而丢失 控制栈top的变化和活动记录的长度相关 通常,局部量相对于活动记录开始点的偏移量可以记录在符号表中,栈式存储分配策略(2),例:例6.1的快速排序程序的活动记录在栈中的分配,Program s; a:的数据说明; procedure r; function p; procedure q begin patition; q(m,i-1); q(i+1,n); end; begin r(); q(1,9); ,堆式存储分配策略,栈分配的局限 不能使得活动停止时,局部名字的值保持 被调用者的活动不能比调用者的活动活得更长,只能满足先入后出的次序 堆分配把连续存储区域分成块 需要时分配(活动记录或其它对象) 释放次序任意 堆可以与栈分配结合起来 C+语言中,基本保持栈的形式,堆用于动态对象的分配 C、Pascal语言中的指针的动态分配等,堆空间的的释放 不释放 存储空间溢出是停止 显式释放 Free(C,PL/1),deallocation(Ada) 有可能引起悬挂引用 隐式释放 单引用 引用计数 垃圾收集(Garbage collection) 堆的分配和释放的优化,