编译原理课件第十章目标程序运行时的存储组织.ppt

第十章 目标程序运行时的存储组织,第一节 数据空间的三种不同使用方法和管理方法,第二节 栈式存储分配的实现,第三节 参数传递,第四节 过程调用、过程进入和过程返回,知识结构,8.1 概述 8.2 静态存储分配 8.3 栈式存储分配 8.4 堆式存储分配 8.5 本章小结,第八章 运行时的存储组织与管理,8.1 概述,从逻辑上看，代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配 所谓运行时的环境是指目标计算机的寄存器和存储器的结构，以及用来管理存储器并保存执行过程所需要的信息。 几乎所有的程序设计语言都使用3种类型的存储环境：完全静态环境、基于栈的存储环境和基于堆的存储环境中的一种或几种。,8.1 概述,从逻辑上看，代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配 数据空间包括：用户定义的各种类型的数据对象（变量和常量）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，组织输入/输出所需的缓冲区。,8.1 概述,存储管理复杂度取决于源语言本身，具体包括： 允许的数据类型的多少 语言中允许的数据项是 静态确定 动态确定 程序决定名字的作用域的规则和结构 段结构 过程定义不嵌套，只允许过程递归调用 分程序结构 分程序嵌套 过程定义嵌套,存储区划分成：目标区、静态数据区、栈区、堆区： 目标代码区用以存放目标代码，这是固定长度的，即编译时能确定的 全程/静态数据区用以存放编译时能确定所占用空间的数据 堆/栈区用于可变数据以及管理过程活动的控制信息,8.1 运行时存储空间的划分,过程的活动记录,过程的活动记录是一段连续的存储区，用来存放过程的一次执行所需要的信息。,8.2 过程活动记录,编译程序分配目标程序运行时的数据空间的基本依据是 程序语言设计时对程序运行中存储空间的使用和管理办 法的规定 在程序设计语言语义学中，使用environment表示将一个 名字映射到一个存储位置的函数，state表示存储位置到 值的映射，如图10.2所示：,数据空间的使用和管理方法分成三种： 静态存储分配 栈式动态存储分配 堆式动态存储分配,静态存储分配：在编译时能确定目标程序运行中所需的 全部数据空间的大小，编译时安排好目标程序运行时的 全部数据空间，确定每个数据对象的存储位置 如像FORTRAN程序是段结构的，如图10.3所示：,8.2 静态存储分配,图10.4给出一个FORTRAN77的程序例子： PROGRAM CNSUME CHARACTER * 50 BUF /程序体所拥有的静态量BUF INTEGER NEXT /程序体所拥有的静态量NEXT CHARACTER C, PRDUCE /程序体所拥有的静态量C DATA NEXT /1/, BUF / / C=PRDUCE() BUF(NEXT:NEXT)=C NEXT=NEXT+1 IF(C .EN. )GOTO 6 WRITE ( *, (A) )BUF (11) END,(12) CHARACTER FUNCTION PRDUCE() CHARACTER * 80 BUFFER INTEGER NEXT SAVE BUFFER, NEXT /PRDUCE函数体所拥有的静态量BUFFER, NEXT (16) DATA NEXT /81/ (17) IF (NEXT .GT.80)THEN (18) READ ( *, (A) )BUFFER (19) NEXT=1 (20) END IF (21) PRDUCE=BUFFER(NEXT:NEXT) (22) NEXT=NEXT+1 (23) END,图10.5中描述了该程序中局部变量的静态存储位置：,动态存储分配,如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术,8.3 栈式动态存储分配,这种分配策略是将整个程序的数据空间设计为一个栈,10.2 栈式存储分配的实现,过程的活动记录AR(Activation Record)：是一段连续的存 储区，用以存放过程的一次执行所需要的信息，这些信 息如图10.6所示：,临时工作单元：如计算表达式过程存放的中间结果 局部变量：一个过程的局部变量 机器状态信息：如程序计数器、寄存器的值 存取链：用以存取非局部变量 控制链：指向调用该过程的那个过程的活动记录 实参：由调用过程向该被调过程提供实参的值(或地址) 返回地址：保存该被调过程返回后的地址,一.简单的栈式存储分配的实现 最简单的程序设计语言结构如图10.7所示： program main; /主程序头 全局变量或数组的说明； proc R; /过程R的头 /过程R的体 end (R); /过程R的尾 proc Q; /过程Q的头 /过程Q的体 end (Q); /过程Q的尾 主程序执行语句 /主程序体 end.(main) /主程序尾,例如，图10.7的程序结构中，若主程序调用了过程Q，Q 又调用了R,在R进入运行后的存储结构如图10.8(a)所示： 若主程序调用了过程Q，Q递归调用自己，在Q过程第2次 进入运行后的存储结构如图10.8(b)所示： 若主程序先调用过程Q，然后主程序接着调用R，且Q过 程没有调用Q和R，这时Q和R进入运行后的存储结构分 别如图10.8(c)和10.8(d)所示：,常常使用两个指针指示栈最顶端的数据区： SP：总是指向现行过程活动记录的起点 TOP：始终指向已占用的栈顶单元,这种语言若含有可变数组，则其过程活动记录的内容如 图10.9所示：,图10.10表明分配数组区之后的运行栈情况，可以与图 10.8（a）对照：,二.嵌套过程语言的栈式实现 Pascal语言程序结构的特点是允许过程嵌套定义，如图 10.11所示：,图10.11的Pascal程序中过程定义的嵌套情况如下： sort readarray exchange quicksort partition,假如过程sort激活（调用）了过程quicksort，这时存储栈 中的情形如图10.12所示，其中在quicksort过程活动记录 中有一存储单元（用斜线描绘）用以记录过程quicksort 可以引用sort中定义的变量a和x。也就是说，为了解决对 非局部变量的存取问题，必须设法跟踪每个外层过程的 最新活动记录的位置,一种跟踪方法是：在过程活动记录中增设存取链,指向包 含该过程的直接外层过程的最新活动记录的起始位置。 过程活动记录的内容如图10.13（a）所示。图10.12所提 到的情况可用图10.13（b）所示：,因为PL/O的过程是无参过程，PL/O也无动态数组，所以 它的过程活动记录的内容如图10.14所示：,再回到图10.11例子，如果该程序的某次执行顺序为： sort quicksort quicksort partition exchange 图10.15给出了进入过程exchange之后运行栈的示意，仅 标明存取链和控制链的值,另一种跟踪方法是：每进入一个过程后，在建立它的活 动记录的同时建立一张嵌套层次显示表display 嵌套层次：指过程定义的层数，始终假定主程序的层数 为0，因此主程序称为0层过程,计数过程的层数用一个计数器Level，初值为0，每遇到过 程说明则增1，过程说明结束则减1 display是一个指针数组d，也可看做是一个小栈，自顶向 下每个单元依次存放着现行层，直接外层，直至最 外层（0层，主程序层）等每一层过程的最新活动记录的 地址,图10.11的程序，假定有如下四种调用情况： （a）sort quicksort （b）sort quicksort quicksort （c） sort quicksort quicksort partition （d） sort quicksort quicksort partition exchange 图10.16(a)-(d)分别说明上述四种情形的运行栈和display,display本身的体积在编译时可确定，它作为单独的表分配 存储还是作为活动记录的一部分，比如置于实参的上端（ 如图10.17所示），则取决于编译程序的设计者,当过程P1调用过程P2而进入P2后，P2应如何建立起自己的 display? 当P1调用P2时必须把P0的display地址作为连接数据之一传 给P2,如果P2是一个真实过程，那么P0或者就是P1自身或者既是 P1又是P2的直接外层（图10.18的(a)(b)两种情形），不 论哪一种情形，只要在进入P2后能够知道P1的display就 能知道P0的display，从而可直接构造出P2的display。也 就是说，在这种情况下，只需所P1的display地址作为连 接数据之一传送给P2就能够建立P2的display,如果P2是形式参数，那么调用P2意味着调用P2当前相应的 实在过程 此时的P0应是这个实在过程的直接外层过程 假定P0的display地址可从形式单元P2所指示的地方获得 为了能在P2中获得P0的display地址，必须在P1调用P2时设 法把P1的display地址作为连接数据之一传送给P2,于是连接数据变为三项： （1）老SP值； （2）返回地址； （3）全局display地址 这样，整个活动记录的组织就如图10.17所示,三.分程序结构的存储管理 一个分程序是一个含有它自己的局部数据（变量）声明 的语句 在C语言中，一个分程序的语法形式是： 声明 语句 例如图10.19的C程序中的分程序B0，B1，B2和B3，分程 序的特征是它们的嵌套结构，使用界符标明分程序的开 始和结束，C语言用 ,分程序结构可以用栈式存储分配实现 一种办法是把分程序看成一个“无参过程”，只不过是在 该分程序入口处调用，分程序出口处返回。分程序在哪 里定义就在哪里被调用 另一种办法是每次为一个完整的过程体分配存储，即把 一个过程体中的所有分程序所需的存储一次分配好，如 图10.19的C程序,可以为这里所有声明的名字分配一块存 储，如图10.20所示：,ALGOL的结构特点是除了允许过程嵌套定义还含有分程 序的结构，如图10.21的一个ALGOL过程：,如采用将分程序看成“无参过程”，则效率很低，因为： 第一，分程序不存在被调用的问题，不必要在进入一个 分程序时，将连接数据和display都放进活动记录中 第二，当从内层分程序向外转移时可能同时要结束若干 个分程序，那么怎样恢复所要到达的那个分程序的数据 区呢？,克服上述缺点的办法是： 首先，代替原来的那个统一的栈顶指示器，让每个过程 和分程序都有自己的栈顶指示器TOP，它的值保存在各 自的活动记录中 其次，不把分程序看作“无参过程”，而让每个分程序享 用包围它的那个最小过程的display,每个过程的活动记录所含的内容有： 1.过程的TOP单元，指向活动记录的栈顶位置 2.连接数据： (1)老SP值 (2)返回地址 (3)全局display地址 (4)调用时的栈顶单元地址，称作老TOP 3.参数个数和形式单元 4.display表,5.过程所管辖的各分程序的局部数据单元对每个分程序来说, 它们包括： (1)一个名为TOP的单元，当进入时它含现行栈顶地址，以后 用来存放栈的新高度 (2)分程序的局部变量、数组内情向量和临时工作单元,图10.22给出了过程A（见图10.21）的活动记录的结构：,下面用一个例子说明进出分程序时数据区的变化过程： 图10.23（a）表示已调用了图10.21的过程A，控制已转入 A中，但尚未开始执行过程体时栈的内容 图10.23（b）反映了已进入过程体分程序（B1），但尚未 分配数组空间时栈的内容。分程序B1的TOP值直接抄自 外层分程序的TOP单元 图10.23（c）反映了分配数组B后的情形，此时B1的TOP 值上升到指示新栈顶，但过程A的TOP值不动 图10.23（d）反映了进入分程序B2之后的情形,进入分程序B4时又抄写B1的TOP,并对数组C进行分配， 于是得到图10.23（e） 当进入分程序B5时，再次抄写直接外层的TOP值，得到 图10.23（f）,10.3 参数传递,当一个过程调用其他过程时，调用过程和被调过程之间的 通信经由非局部量或者经由参数传递,如图10.24的过程exchange1既使用了非局部量数组a，又使 用了形式参数i和j，将ai和aj的值进行交换 （1）procedure exchange1(i , j:integer); （2） var x:integer; （3） begin; （4） x:=ai;ai:=aj;aj:=x; （5） end; 图10.24 带有非局部变量和形参的Pascal过程,把实在参数传递给相应的形式参数方法： 传值、传地址、传名、宏扩展等 观察图10.25的Pascal程序，程序的输出是a=2,b=1，如果将 第3行的关键字var 去掉，则该程序的输入是a=1,b=2,一.传值call-by-value（值调用） 将实参计算出它的值，然后把它传给被调过程： 1.形式参数当作过程的局部变量处理 2.调用过程计算实参的值，并将它们的右值放在为形式单元 开辟的空间中,3.被调用过程执行时，就像使用局部变量一样使用这些形式 单元 传值的重要特点是对形式参数的任何运算不影响调用过 程的活动记录中实参的值 通过值调用的过程可以由非局部量或由指针而对调用过 程发生影响,比如图10.26的C程序中，x和y声明为整型指针，第8行调用 swap(&a,&b)中的操作符导致将指向a和b的指针传给过 程swap。该程序的输出为：a is now 2, b is now 1,二.传地址 当参数通过引用传递时，也称作传地址，或引用调用 调用过程传给被调过程的是指针，指向实参存储位置的 指针 1.如实参是一个名字或是具有左值的表达式，则左值本身传 递过去 2.如实参是一个表达式，比如a+b或2，而没有左值，则表 达式先求值，并存入某一位置，然后该位置的地址传递 过去 3.被调过程中对形式参数的任何引用和赋值都通过传递到被 调过程的指针被处理成间接访问,例如，在图10.25的程序中，若用实参i和ai对过程swap进 行调用，即swap(i,ai)，其效果如下步骤所述： 1.将i和ai的地址（左值）拷贝到被调过程的活动记录中，比 如说分别对应形参x和y的单元arg1和arg2 2.将局部变量temp设为由arg1所指单元的内容（即令temp等 于I0，其中I0是i的初值），这一步对应于swap定义中的第 6行语句：temp:=x 3.将arg1所指单元的内容设为等于temp的值，即设aI0=i ,这 一步对应swap中第7行的x:=y 4.将arg2所指单元的内容设为等于temp的值，即设aI0=i， 这一步对应y:=temp,三.过程参数 一个嵌套过程（函数）可以作为参数传递，比如图10.27 的PASCAL程序中，过程c把f作为参数传递给b，而b通 过引用形参h调用f,图10.28说明了这点，当过程c传递f时，c可以决定f的存取 链，或者说f的存取链或display可以根据c的存取链或 display来建立：,10.4 过程调用、过程进入和过程返回,对于过程调用的四元式序列： par T1 par T2 par Tn call P,n,在运行时是如何执行的？/par和call产生什么相应的目标 代码 对于par Ti（i=1,2,n)的处理是：根据par Ti （i=1,2,n)中Ti的种别而生成传送指令，或将参数的值 或将参数的地址传送至新的过程的活动记录的形式单元中,对于call p,n则应生成传送参数个数n的指令；保护现行SP 至新过程的活动记录（老SP）；转子，转向P的第一条指 令；定义新SP；保护返回地址；定义新值；填写display或 存取链内容等指令 如果过程含动态数组（局部），则应生成对数组进行存储 分配的指令，即生成运行时动态地建立内情向量和分配数 组空间的目标指令 在过程执行语句的工作过程中，凡引用形参、局部变量或 数组元素都可根据过程活动记录起点的相对位置访问,当过程P工作完毕要返回到调用段时，若语言有形如return （E）的返回语句，或P是个函数过程时，则可把已算好的 值传送至某个特定的寄存器中，调用段将从这个特定的寄 存器中获得被调过程的结果值。然后所生成的目标指令则 应完成的工作是：恢复SP；恢复TOP，按保存的返回地址 实行无条件转移,8.4 堆式动态存储分配,假设程序运行时有一个大的存储空间，每当需要时就从这片空间中借用一块，不用时再退还，由于借还的时间先后不一，经一段运行之后，程序运行空间将被划分成许多块，有些占用，有些空闲。那么当运行程序要求一块体积为N的空间时，需要决定应该从哪个空闲块得到这个空间。 理论上讲,应该从比N稍大一些的空闲块中取出N个单元，以便使大的空闲块派更大的用场，但实现难度很大,实际中常常采用的办法：先遇到哪块比N大就从其中取出 N个单元 即使这样，也会发生找不到一块比N大的空闲块，但所有 空闲块总和比N大得多，这时，有的分配管理系统采用废 品回收的办法来应付,8.5 临时变量的存储分配,产生中间代码时，为了暂存中间结果，编译程。序会大量引进临时变量名，其属性简单，不登记到符号表，只在它们出现的地方加上类型信息皆可。 一般的分配原则：如果两个临时变量名的作用域不相交，则它们可以分到同一单元种。一个临时变量名自第一次赋值的地方器至最后一次被引用的地方止，这区间的程序所能达到的全体四元式构成它的作用域。,8.5 临时变量的存储分配,临时变量的存储分配的简单实现： 令临时变量名均分配在局部数据区中，若某一单元已分配给某些临时变量，则把这些名字的作用域（它们必须是互不相交的）作为单元的分配信息记录下来。每当要对新临时变量名进行分配时，首先要求求出该变量名的作用域，若它的作用域与某个单元所记录的全部作用域均不相交，就把这个单元分配给这个新名，同时把它的作用域也添加到该单元的分配信息之中。如果新临时变量的作用域和所有已分配单元的作用域均有冲突，就分配给它一个新的单元，同时把新名的作用域作为此单元的分配信息。,【本章小结】 目标代码运行时，存储区域的整体布局,以及各区域的作用 各种不同数据变量区的不同分配组织方式 允许过程嵌套定义的语言，栈式动态分配的组织管理 过程活动纪录的各项内容和它们的作用，以及活动纪录的 组织方式 参数传递的不同方式及其实现 过程调用和返回时，相应目标代码以及栈式动态分配区的 管理,第10章 习题 第1题： 下面的程序执行时输出的a分别是什么?若 (1) 参数的传递办法为“传值“； (2) 参数的传递办法为“传地址“。 program main (input,output); procedure p(x,y,z); begin y=y+1; z=z+x; end; begin a=2; b=3; p(a+b,a,a); print a end.,第2题：过程参数的传递方