编译原理第9章

《编译原理第9章》由会员分享，可在线阅读，更多相关《编译原理第9章（52页珍藏版）》请在金锄头文库上搜索。

1、编译原理第九章 程序运行期间的存储空间组织编译原理第2页本节内容与要点 l运行时存储空间的划分l活动记录概念l存储空间分配策略1、静态存储分配2、动态存储分配简单栈式存储分配嵌套过程语言的栈式分配 l典型范例解析编译原理第3页运行时存储空间的划分 l编译程序为了使它编译后得到的目标程序能够运行， 要从操作系统中获得一块存储空间。 l对这块提供运行的空间应该进行划分以便存放：生成 的目标代码、数据对象和跟踪过程活动的控制栈。目 标代码的大小在编译时可以确定，所以编译程序可以 把它放在一个静态确定的区域。l有一些数据对象的大小在编译时也能确定，因此它们 也可以放在静态确定的区域。 编译原理第4页运

2、行时存储空间的划分（续）目 标 代 码静 态 数 据栈 堆返回编译原理第5页活动记录 l为了管理过程在一次执行中所需要的信息，使 用一个连续的存储块，这样的一个连续存储块 称为活动记录（Activation Record）。l当过程调用时，产生一个过程的新的活动，用 一个活动记录表示该活动的相关信息，并将其 压入栈。 编译原理第6页l当过程返回（活动结束）时，当前活动记录 一般包含如下内容：l连接数据1.返回地址2.动态链：指向调用该过程前的最新活动记 录地址的指针。运行时，使运行栈上各数据 区按动态建立的次序结成链。链头为栈顶起 始位置。3.静态链：指向静态直接外层最新活动记录 地址的指针，

3、用来访问非局部数据。编译原理第7页l形式单元：存放相应的实在参数的地址或值。l局部数据区：局部变量、内情向量、临时工作单元 （如存放对表达式求值的结果）。 l指针SP指向现行过程（即最新进入工作的那个过 程）的活动记录在栈里的起始位置。编译原理第8页活动记录结构图临 时 单 元 内 情 向 量局 部 变 量形 式单 元静 态 链动 态 连返 回 地 址TOPSP连接数据返回编译原理第9页存储分配策略 l静态分配策略在编译时对所有数据对象分配 固定的存储单元，且在运行时始终保持不变 。l栈式动态分配策略在运行时把存储器作为一 个栈进行管理，运行时，每当调用一个过程 ，它所需要的存储空间就动态地分

4、配于栈顶 ，一旦退出，它所占空间就予以释放。l堆式动态分配策略在运行时把存储器组织成 堆结构，以便用户关于存储空间的申请与归 还（回收），凡申请者从堆中分给一块，凡 释放者退回给堆。返回编译原理第10页一、静态分配策略 l适用范围和特点：1、程序语言不允许递归过程；2、不许含可变体积的数据项目或待定性质的 名字；3、在编译时就能够确定一个程序在运行时所 需的存贮空间大小，能够安排好目标程序运 行的全部数据空间，并能确定每个数据项的 单元地址。编译原理第11页l适于静态存贮分配的语言必须满足以下条件 ：l(1)数组的上下界必须是常数；l(2)过程调用不允许递归；l(3）不允许采用动态的数据结构（

5、即在程序运 行过程中申请和释放的数据结构）。 编译原理第12页l由于过程调用不允许递归，数据项的存贮地 址就与过程相联系。过程调用所使用的局部 数据区可以直接安排在过程的目标代码之后 ，并把各数据项的存贮地址填入相关的目标 代码中，以便在过程运行时访问这个局部数 据区。l这里，不存在对存贮区的再利用问题。在执 行目标程序时不必进行运行时的存贮空间管 理，过程的进入和退出变得极为简单。编译原理第13页例：一个程序段的局部数据区返回返回编译原理第14页二、动态分配策略l适用：程序语言允许递归过程和可变（体积的）数组， 其程序数据空间的分配需采用某种动态策略（在程序运 行时动态地进行分配）。l栈式动

6、态分配策略：目标程序可用一个栈作为动态的数 据空间。运行时，每当进入一个过程或分程序，它所需 的数据空间就动态地分配于栈顶，一旦退出，它所占用 的空间就予以释放。l堆式动态分配策略：如果程序语言允许用户动态地申请 和释放存贮空间，而且申请和释放之间不一定遵守先请 后放和后请先放的原则，此时就必须让运行程序持有一 个大存贮区（称为堆），凡申请者从堆中分给一块，凡 释放者退还给堆。 返回编译原理第15页简单的栈式存贮分配 l适用于简单程序语言的实现：语言没有分程序结构， 过程定义不允许嵌套，但允许过程的递归调用，允许 过程含有可变数组。lC语言就是这样一种语言。其局部名称的存储分配， 可以直接采用

7、栈式存储分配策略。编译原理第16页1、栈式存储分配 l使用栈式存储分配法意味着把存储组成一个栈 。l运行时，每当进入一个过程（一个新的活动开 始）时，就把它的活动记录压入栈，从而形成 过程工作时的数据区，一个过程的活动记录的 体积在编译时是可静态确定的。l当该活动结束（过程退出）时，再把它的活动 记录弹出栈，这样，它在栈顶上的数据区也随 即不复存在。 编译原理第17页C语言的程序结构全局数据说明Main ( ) Main中的数据说明void R ( ) R中的数据说明void R ( ) R中的数据说明编译原理第18页C语言程序的存储组织R的活动记录Q的活动记录Main的活动记录主程序全局数据

8、区TOPSPSP:总指向现行过程活动记录的起点，用于访问局部数据。TOP:始终指向（已占用）栈顶单元。编译原理第19页2、C的活动记录 lC的活动记录有以下四个项目。1、连接数据（两项）：(1)老SP值，即前一活动记录的起始地址；(2)返回地址。2、参数个数。 3、形式单元（存放实在参数的值或地址）。4、过程的局部变量、数组内情向量和临时工作单元。 编译原理第20页C过程的活动记录临 时 单 元 内 情 向 量简 单 变 量形 式单 元参 数 个 数返 回 地 址老 SP012SPTOP编译原理第21页3.、 过程的执行 l分为三步：l (1) 过程调用l（2）过程进入l（3）过程返回编译原理

9、第22页(1) 过程调用-par相应的目标代码 l过程调用的四元式序列为：par T1par T2par Tncall p , nl每个par Ti (i=1,2,，n)可 直接翻译成如下指令：(i+3) TOP: =Ti/*传递参数值*/ 或(i+3) TOP: =addrTi /* 传递参数地址*/ 编译原理第23页(1) 过程调用-call相应的目标代码 l四元式 call p,n 翻译成：1 TOP: =SP /*保护现行SP*/3TOP: =n *传递参数个数*/JSR P /*转子指令，转向P过程 的第一条指令*/ T2T1参数个数n现行SP值 调用过程P 的 活 动 记 录 01

10、234TOP+3TOPSP编译原理第24页(2)过程进入 l转入过程P后，首先要做的工作是定义新活动记录 的SP,保护返回地址和定义新活动记录的TOP值， 即执行下述指令：SP:TOP+1 /*定义新SP*/1 SP：=返回地址 /*保护返回地*/TOP: =TOP+L; /*定义新TOP*/lL是过程P的活动记录所需的单元数，这个数在编译 时可静态地计算出来（活动记录的体积在编译时可 静态地确定）。 编译原理第25页l对每个数组说明，相应的目标指令组将做以下 几件工作：l计算各维的上、下限；l调用数组空间分配子程序，其参数是各维的 上、下限和内情向量单元首地址。l数组空间分配子程序计算并填好

11、内情向量的所 有信息，然后在TOP所指的位置之上留出数组 所需的空间，并将TOP调整为指向数组区的顶 端。l此后，在过程段执行语句的工作过程中，凡引 用形式参数、局部变量或数组元素都是以SP为 基址进行相对访问的。编译原理第26页进入过程P后所做工作示意P的数组区返回地址SPTOP调用过程P的活动记录（ 长度为L)01编译原理第27页(3)过程返回 lC语言以及其它一些相似的语言含有return(E)的返回 语句，E为表达式。l假定E值已计算出来并已存放在某临时单元T中，可 将T只传送到某个特定寄存器（调用过程将从这个特 定的寄存器中获得P的结果）。l剩下的工作就是恢复SP和TOP为进入过程P

12、之前的原 值（即指向工作空间），并按返回地址实行无条件转 移。编译原理第28页过程P返回示意 l即执行下述指令序列：TOP:=SP-1 *恢复调用过程的TOP值*/SP: =0SP *恢复调用过程的SP值*/X: =2TOP 将返回地址送X*/UJ 0X /* 无条件转移，按X地址返回 */返回地址老SP调用过程 空间P空间SPTOP返回编译原理第29页嵌套过程语言的栈式分配l由于过程定义是嵌套的，一个过程可以引用包围它的 任一外层过程所定义的变量或数组，运行时，一个过 程Q可能引用它的任一外层过程P的最新活动记录中 的某些数据（这些数据视为过程Q的非局部量）。编译原理第30页非局部名字的访问

13、的实现l为了在活动记录中查找非局部名字所对应的存储 空间，过程Q运行时必须知道它的所有外层过程 的最新活动记录的地址。l由于允许递归性，过程的活动记录的位置（即使 是相对位置）也往往是变迁的。因此，必须设法 跟踪每个外层过程的最新活动记录的位置。l跟踪的办法很多，本节讨论两种方法：l一种是通过静态链；另一种是通过显示表（ display，）。 编译原理第31页一、静态链和活动记录 l引入一个称为静态链的指针，该指针为活动记录的一 个域，指向直接外层的最新活动记录的地址。l这就意味着在运行时栈上的数据区（活动记录）之间 又拉出一条链，这个链称为静态链，静态链是从一个 过程的当前活动记录指向其直接

14、外层的最新活动记录 。 编译原理第32页具有静态链的活动记录结构临时单 元 内情向量 简单变 量 形式参数形参个数存取链（静态链）返回地址控制链（动态链 ）：老SPSPTOP编译原理第33页l假定过程的嵌套关系如下：P;var a;Q(b);var i;R;var c,d;call R;S;var c, I;call Q; call S;编译原理第34页过程调用试运行栈的变化编译原理第35页i 形式参数：c形参个数：1静态链 ：0返回地址老SPic形参个数：0静态链 ：0返回地址老SP: 0a形参个数：0静态链 ：0返回地址0SPTOPS 过 程P 过 程Q 过 程编译原理第36页l例：请见书

15、上P258页嵌套程序。写出递 归调用时活动记录的变化。（程序见下页）编译原理第37页编译原理第38页编译原理第39页二、嵌套层次显示表(display)和活动记录 l为了提高访问非局部量的速度，还可以引用一个 指针数组，称为嵌套层次显示表。l每进入一个过程后，在建立它的活动记录区的同 时建立一张嵌套层次表display.l假定现进入的过程的层数为i，则它的display表 含有i1个单元。 l此表本身是一个小找，自顶向下每个单元依次存 放着现行层，直接外层，直至最外层（0层， 主程序层）等每一层过程的最新活动记录的基地 址。 编译原理第40页l例如，令过程R的外层为Q，Q的外层为P,则过程R

16、运行时display表的内容应为：R的现行活动记录 始址 （SP的现行值）Q的最新活动记录 地址P的活动记录 地址 012编译原理第41页l由于过程的层数可以静态确定，因此每个过程的 display表的体积在编译时即可知道。l由一个非局部量说明所在的静态层数和相对活动 记录的相对地址，就可得到绝对地址：绝对地址=display静态层数+相对地址编译原理第42页活动记录结构临时变 量 内情变量 简单变 量 display形式单元参数个数全局 display地 址 返回地址老SP0123dSPTOPd个单元第k层sp最外层过 程 sp 主程序spd+01k编译原理第43页l由于每个过程的形式单元的数目在编译时是知道的，因 此DISPLAY的相对地址d（相对于活动记录起点）在编 译时也是完全确定的。l被调用过程为了建立自己的DISPLAY,