编译原理第9章分析.ppt

第九章 运行时存储空间组织
在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。
标识符对应的内存地址都是由编译程序在编译时或由其生成的目标程序运行时进行分配。
程序中使用的存储单元都由标识符来表示。
编译原理第9章分析
第九章　运行时存储空间组织
目标程序运行时的活动（略）
运行时存储器的划分
静态存储分配（略）
简单的栈式存储分配
嵌套过程语言的栈式实现
堆式动态存储分配
编译原理第9章分析
运行时存储器的划分
一、运行时存储器的划分

（1）目标代码编译时可确定，故可放在一个静态确定的区域
（2）数据对象部分数据对象的大小在编译时可确定，故也可
放在一个静态确定的区域
（3）跟踪过程活动的控制栈
目标代码
静态数据
栈
↓
↑
堆
编译原理第9章分析

：用扩充的栈来管理过程的活动，当发生过程调用时，
中断当前活动的执行，激活新被调用过程的活动，
并把包含在这个活动生存期中的数据对象以及该活
动有关的其它信息存入栈中。当控制从调用返回时，
将所占存储空间弹出栈顶。同时，被中断的活动恢
复执行。
（heap）——存放动态数据，大小可随程序的运
行而改变。
运行时存储器的划分
编译原理第9章分析
二、活动记录
：为了管理过程在一次执行中所需要的信息，使
用一个连续的存储块，该连续的存储块叫活动记录。
当过程调用时，产生一个过程的新的活动，用一个活动记录表
示该活动的相关信息，并将其压入栈。
当过程返回时，将该活动记录从栈中弹出。
运行时存储器的划分
编译原理第9章分析

（1）连接数据
SP指向现行过程的活动记录在栈里的起始位置。
返回地址
动态链—指向调用该过程前的最新活动记录地址的指针。
静态链—指向静态直接外层最新活动记录地址的指针，
用来访问非局部数据.
（2）形式单元——存放相应的实在参数的地址或值
（3）局部数据区
局部变量——简单变量
内情向量——局部数据的内情向量，即数组元素
临时工作单元——存放对表达式求值的结果
运行时存储器的划分
编译原理第9章分析
运行时存储器的划分
三、存储分配策略

在编译时对所有数据对象分配固定的存储单元，且
在运行时始终保持不变。

在运行时把存储器作为一个栈进行管理，运行时，每当调
用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦
退出，它所占空间就予以释放。

在运行时把存储器组织成堆结构，以便用户关于存储空
间的申请与归还（回收），凡申请者从堆中分给一块，凡释放
者退回给堆.
编译原理第9章分析
简单的栈式存储分配
：假设程序语言无分程序结构，过程定义不允
许嵌套，但允许过程的递归调用。
例如：C 语言
：运行时
每当进入一个过程
——即一个新的活动开始，就把其它活动记录压入栈（置于栈顶），从而形成过程工作时的数据区.
当活动结束
——即过程退出时，再把其活动记录弹出栈，这样，它在栈顶上的数据区也随即不复存在.
编译原理第9章分析

（1）主程序调用过程Q，而Q又调用R，
在R进入运行后的存储结构.
简单的栈式存储分配
R的活动记录
Q的活动记录
Main的活动记录
全局数据
SP
TOP
静态分配
编译原理第9章分析

（2）主程序调用过程Q，Q递归调用自己，在Q过程
第二次进入运行后的存储结构.
简单的栈式存储分配
Q2的活动记录
Q1的活动记录
Main的活动记录
全局数据
编译原理第9章分析