目标程序运行时的存储组织教材

1第八章目标程序运行时的存储组织第八章目标程序运行时的存储组织v第一节第一节 数据空间的三种不同使用方法和管理方法数据空间的三种不同使用方法和管理方法v第二节第二节 栈式存储分配的实现栈式存储分配的实现v第三节第三节 参数传递参数传递v第四节第四节 过程调用、过程进入和过程返回过程调用、过程进入和过程返回28.18.1数据空间的三种不同使用方法和管理方法数据空间的三种不同使用方法和管理方法v从逻辑上看，代码生成前，编译程序必须进行目标程序从逻辑上看，代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配运行环境的设计和数据空间的分配v数据空间包括：用户定义的各种类型的数据对象（变量数据空间包括：用户定义的各种类型的数据对象（变量和常量）所需的存储空间，作为保留中间结果和传递参和常量）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，组织数的临时工作单元，调用过程时所需的连接单元，组织输入输出所需的缓冲区输入输出所需的缓冲区v运行时的存储区常常划分成：目标区、静态数据区、栈运行时的存储区常常划分成：目标区、静态数据区、栈区、堆区区、堆区3v图图8.1就是一种典型划分：就是一种典型划分：4代码区用以存放目标代码，这是固定长度的，即编译时代码区用以存放目标代码，这是固定长度的，即编译时能确定的能确定的静态数据区用以存放编译时能确定所占用空间的数据静态数据区用以存放编译时能确定所占用空间的数据堆栈区用于可变数据以及管理过程活动的控制信息堆栈区用于可变数据以及管理过程活动的控制信息v编译程序分配目标程序运行时的数据空间的基本依据是编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办程序语言设计时对程序运行中存储空间的使用和管理办法的规定法的规定v在程序设计语言语义学中，使用在程序设计语言语义学中，使用environment表示将一个表示将一个名字映射到一个存储位置的函数，名字映射到一个存储位置的函数，state表示存储位置到表示存储位置到值的映射，如图值的映射，如图8.2所示：所示：5v数据空间的使用和管理方法分成三种：数据空间的使用和管理方法分成三种：静态存储分配静态存储分配栈式动态存储分配栈式动态存储分配堆式动态存储分配堆式动态存储分配6一一.静态存储分配静态存储分配v静态存储分配：在编译时能确定目标程序运行中所需的静态存储分配：在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置全部数据空间，确定每个数据对象的存储位置v如像如像FORTRAN程序是段结构的，如图程序是段结构的，如图8.3所示：所示：7v图图8.4给出一个给出一个FORTRAN77的程序例子：的程序例子：图图8.48v图图8.5中描述了该程序中局部变量的静态存储位置：中描述了该程序中局部变量的静态存储位置：9二二.动态存储分配动态存储分配v如果一个程序设计语言允许递归过程、可变数组或允许如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储用户自由申请和释放空间，那么，就需要采用动态存储管理技术管理技术三三.栈式动态存储分配栈式动态存储分配v这种分配策略是将整个程序的数据空间设计为一个栈这种分配策略是将整个程序的数据空间设计为一个栈10四四.堆式动态存储分配堆式动态存储分配v假设程序运行时有一个大的存储空间，每当需要时就从假设程序运行时有一个大的存储空间，每当需要时就从这片空间中借用一块，不用时再退还，由于借还的时间这片空间中借用一块，不用时再退还，由于借还的时间先后不一，经一段运行之后，程序运行空间将被划分成先后不一，经一段运行之后，程序运行空间将被划分成许多块，有些占用，有些空闲。那么当运行程序要求一许多块，有些占用，有些空闲。那么当运行程序要求一块体积为块体积为N的空间时，需要决定应该从哪个空闲块得到这的空间时，需要决定应该从哪个空闲块得到这个空间个空间v理论上讲理论上讲,应该从比应该从比N稍大一些的空闲块中取出稍大一些的空闲块中取出N个单元，个单元，以便使大的空闲块派更大的用场，但实现难度很大以便使大的空闲块派更大的用场，但实现难度很大11v实际中常常采用的办法：先遇到哪块比实际中常常采用的办法：先遇到哪块比N大就从其中取出大就从其中取出N个单元个单元v即使这样，也会发生找不到一块比即使这样，也会发生找不到一块比N大的空闲块，但所有大的空闲块，但所有空闲块总和比空闲块总和比N大得多，这时，有的分配管理系统采用废大得多，这时，有的分配管理系统采用废品回收的办法来应付品回收的办法来应付128.2栈式存储分配的实现栈式存储分配的实现v过程的活动记录过程的活动记录AR(Activation Record)：是一段连续的存：是一段连续的存储区，用以存放过程的一次执行所需要的信息，这些信储区，用以存放过程的一次执行所需要的信息，这些信息如图息如图8.6所示：所示：13临时工作单元：如计算表达式过程存放的中间结果临时工作单元：如计算表达式过程存放的中间结果局部变量：一个过程的局部变量局部变量：一个过程的局部变量机器状态信息：如程序计数器、寄存器的值机器状态信息：如程序计数器、寄存器的值存取链：用以存取非局部变量存取链：用以存取非局部变量控制链：指向调用该过程的那个过程的活动记录控制链：指向调用该过程的那个过程的活动记录实参：由调用过程向该被调过程提供实参的值实参：由调用过程向该被调过程提供实参的值(或地址或地址)返回地址：保存该被调过程返回后的地址返回地址：保存该被调过程返回后的地址14一一.简单的栈式存储分配的实现简单的栈式存储分配的实现v最简单的程序设计语言结构如图最简单的程序设计语言结构如图10.7所示：所示：15v例如，图例如，图8.7的程序结构中，若主程序调用了过程的程序结构中，若主程序调用了过程Q，Q又调用了又调用了R,在在R进入运行后的存储结构如图进入运行后的存储结构如图10.8(a)所示：所示：v若主程序调用了过程若主程序调用了过程Q，Q递归调用自己，在递归调用自己，在Q过程第过程第2次次进入运行后的存储结构如图进入运行后的存储结构如图10.8(b)所示：所示：v若主程序先调用过程若主程序先调用过程Q，然后主程序接着调用，然后主程序接着调用R，且，且Q过过程没有调用程没有调用Q和和R，这时，这时Q和和R进入运行后的存储结构分进入运行后的存储结构分别如图别如图8.8(c)和和8.8(d)所示：所示：1617v常常使用两个指针指示栈最顶端的数据区：常常使用两个指针指示栈最顶端的数据区：SP：总是指向现行过程活动记录的起点：总是指向现行过程活动记录的起点TOP：始终指向已占用的栈顶单元：始终指向已占用的栈顶单元v这种语言若含有可变数组，则其过程活动记录的内容如这种语言若含有可变数组，则其过程活动记录的内容如图图8.9所示：所示：18v图图8.10表明分配数组区之后的运行栈情况，可以与图表明分配数组区之后的运行栈情况，可以与图8.8（a）对照：）对照：19二二.嵌套过程语言的栈式实现嵌套过程语言的栈式实现vPascal语言程序结构的特点是允许过程嵌套定义，如图语言程序结构的特点是允许过程嵌套定义，如图8.11所示：所示：2021v图图8.11的的Pascal程序中过程定义的嵌套情况如下：程序中过程定义的嵌套情况如下：sort readarray exchange quicksort partitionv假如过程假如过程sort激活（调用）了过程激活（调用）了过程quicksort，这时存储栈，这时存储栈中的情形如图中的情形如图8.12所示，其中在所示，其中在quicksort过程活动记录过程活动记录中有一存储单元（用斜线描绘）用以记录过程中有一存储单元（用斜线描绘）用以记录过程quicksort可以引用可以引用sort中定义的变量中定义的变量a和和x。也就是说，为了解决对。也就是说，为了解决对非局部变量的存取问题，必须设法跟踪每个外层过程的非局部变量的存取问题，必须设法跟踪每个外层过程的最新活动记录的位置最新活动记录的位置2223v一种跟踪方法是：在过程活动记录中增设存取链一种跟踪方法是：在过程活动记录中增设存取链,指向包指向包含该过程的直接外层过程的最新活动记录的起始位置。含该过程的直接外层过程的最新活动记录的起始位置。过程活动记录的内容如图过程活动记录的内容如图8.13（a）所示。图）所示。图8.12所提所提到的情况可用图到的情况可用图8.13（b）所示：）所示：24v因为因为PL/O的过程是无参过程，的过程是无参过程，PL/O也无动态数组，所以也无动态数组，所以它的过程活动记录的内容如图它的过程活动记录的内容如图8.14所示：所示：25v再回到图再回到图8.11例子，如果该程序的某次执行顺序为：例子，如果该程序的某次执行顺序为：sortquicksortquicksortpartitionexchangev图图8.158.15给出了进入过程给出了进入过程exchangeexchange之后运行栈的示意，仅之后运行栈的示意，仅标明存取链和控制链的值标明存取链和控制链的值2627v另一种跟踪方法是：每进入一个过程后，在建立它的活另一种跟踪方法是：每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表动记录的同时建立一张嵌套层次显示表displayv嵌套层次：指过程定义的层数，始终假定主程序的层数嵌套层次：指过程定义的层数，始终假定主程序的层数为为0，因此主程序称为，因此主程序称为0层过程层过程v计数过程的层数用一个计数器计数过程的层数用一个计数器Level，初值为，初值为0，每遇到过，每遇到过程说明则增程说明则增1，过程说明结束则减，过程说明结束则减1vdisplay是一个指针数组是一个指针数组d，也可看做是一个小栈，自顶向，也可看做是一个小栈，自顶向下每个单元依次存放着现行层，直接外层，下每个单元依次存放着现行层，直接外层，直至最直至最外层（外层（0 0层，主程序层）等每一层过程的最新活动记录的层，主程序层）等每一层过程的最新活动记录的地址地址28v图图8.11的程序，假定有如下四种调用情况：的程序，假定有如下四种调用情况：（a）sortquicksort（b）sortquicksort quicksort（c）sortquicksort quicksortpartition（d）sort quicksortquicksortpartition exchange图图8.16(a)-(d)8.16(a)-(d)分别说明上述四种情形的运行栈和分别说明上述四种情形的运行栈和displaydisplay293031vdisplay本身的体积在编译时可确定，它作为单独的表分配本身的体积在编译时可确定，它作为单独的表分配存储还是作为活动记录的一部分，比如置于实参的上端（存储还是作为活动记录的一部分，比如置于实参的上端（如图如图8.17所示），则取决于编译程序的设计者所示），则取决于编译程序的设计者32v当过程当过程P1调用过程调用过程P2而进入而进入P2后，后，P2应如何建立起自己的应如何建立起自己的display?当当P1P1调用调用P2P2时必须把时必须把P0P0的的displaydisplay地址作为连接数据之一传地址作为连接数据之一传给给P2P2如果如果P2P2是一个真实过程，那么是一个真实过程，那么P0P0或者就是或者就是P1P1自身或者既是自身或者既是P1P1又是又是P2P2的直接外层（图的直接外层（图8.188.18的的(a)(ba)(b)两种情形），不两种情形），不论哪一种情形，只要在进入论哪一种情形，只要在进入P2P2后能够知道后能够知道P1P1的的displaydisplay就就能知道能知道P0P0的的displaydisplay，从而可直接构造出，从而可直接构造出P2P2的的displaydisplay。也。也就是说，在这种情况下，只需所就是说，在这种情况下，只需所P1P1的的displaydisplay地址作为连地址作为连接数据之一传送给接数据之一传送给P2P2就能够建立就能够建立P2P2的的displaydisplay3334如果如果P2P2是形式参数，那么调用是形式参数，那么调用P2P2意味着调用意味着调用P2P2当前相应的当前相应的实在过程实在过程此时的此时的P0P0应是这个实在过程的直接外层过程应是这个实在过程的直接外层过程假定假定P0P0的的displaydisplay地址可从形式单元地址可从形式单元P2P2所指示的地方获得所指示的地方获得为了能在为了能在P2P2中获得中获得P0P0的的displaydisplay地址，必须在地址，必须在P1P1调用调用P2P2时设时设法把法把P1P1的的displaydisplay地址作为连接数据之一传送给地址作为连接数据之一传送给P2P2于是连接数据变为三项：于是连接数据变为三项：（1 1）老）老SPSP值；值；（2 2）返回地址；）返回地址；（3 3）全局）全局displaydisplay地址地址这样，整个活动记录的组织就如图这样，整个活动记录的组织就如图8.178.17所示所示35例：有如下示意的例：有如下示意的Pascal源程序源程序program main;var a,b,c:integer;procedure X(i,j:integer);var d,e:real;procedure Y;var f,g:real;begin.end;Yprocedure Z(k:integer);var h,i,j:real;begin.end;Zbegin.10:Y;.11:Z;.end;Xbegin.X(a,b);.end.main 并已知在运行时刻，以过程为单位对程序中的变量进行动并已知在运行时刻，以过程为单位对程序中的变量进行动态存储分配。当运行主程序而调用过程语句态存储分配。当运行主程序而调用过程语句X时，试分别时，试分别给出以下时刻的运行栈的内容和给出以下时刻的运行栈的内容和DISPLAY的内容。的内容。（1）已开始而尚未执行完毕的标号为）已开始而尚未执行完毕的标号为10的语句。的语句。（2）已开始而尚未执行完毕的标号为）已开始而尚未执行完毕的标号为11的语句。的语句。临时变量内情向量简单变量display形式单元形参个数全局display返回地址老SP36gf1660012返回地址6ed60ji22返回地址0cb a0返回地址0 解：（1）程序已开始而尚未执行完毕标号为10的语句时，运行栈的内容和Display表的内容如下图所示 0123456789101112131415161718192021222324全局display全局display全局displaydisplaydisplayTOP SP2 SP1 SP0 37(2)程序已开始而尚未执行完毕标号为11的语句时，运行栈的内容和Display表的内容如下图所示 jih1660k112返回地址6ed60ji22返回地址0cba0返回地址0全局displaydisplaydisplay全局display全局display012 34 567891011121314151617181920212223242526TOP SP2 SP1 SP0 38三三.分程序结构的存储管理（分程序结构的存储管理（自习自习）v一个分程序是一个含有它自己的局部数据（变量）声明一个分程序是一个含有它自己的局部数据（变量）声明的语句的语句v在在C语言中，一个分程序的语法形式是：语言中，一个分程序的语法形式是：声明语句声明语句v例如图例如图8.19的的C程序中的分程序程序中的分程序B0，B1，B2和和B3，分程，分程序的特征是它们的嵌套结构，使用界符标明分程序的开序的特征是它们的嵌套结构，使用界符标明分程序的开始和结束，始和结束，C语言用语言用 3940v分程序结构可以用栈式存储分配实现分程序结构可以用栈式存储分配实现一种办法是把分程序看成一个一种办法是把分程序看成一个“无参过程无参过程”，只不过是，只不过是在在该分程序入口处调用，分程序出口处返回。分程序在哪该分程序入口处调用，分程序出口处返回。分程序在哪里定义就在哪里被调用里定义就在哪里被调用另一种办法是每次为一个完整的过程体分配存储，即把另一种办法是每次为一个完整的过程体分配存储，即把一个过程体中的所有分程序所需的存储一次分配好，如一个过程体中的所有分程序所需的存储一次分配好，如图图8.19的的C程序程序,可以为这里所有声明的名字分配一块存可以为这里所有声明的名字分配一块存储，如图储，如图8.20所示：所示：4142vALGOL的结构特点是除了允许过程嵌套定义还含有分程的结构特点是除了允许过程嵌套定义还含有分程序的结构，如图序的结构，如图8.21的一个的一个ALGOL过程：过程：43v如采用将分程序看成如采用将分程序看成“无参过程无参过程”，则效率很低，因为，则效率很低，因为：第一，分程序不存在被调用的问题，不必要在进入一个第一，分程序不存在被调用的问题，不必要在进入一个分程序时，将连接数据和分程序时，将连接数据和display都放进活动记录中都放进活动记录中第二，当从内层分程序向外转移时可能同时要结束若干第二，当从内层分程序向外转移时可能同时要结束若干个分程序，那么怎样恢复所要到达的那个分程序的数据个分程序，那么怎样恢复所要到达的那个分程序的数据区呢？区呢？v克服上述缺点的办法是：克服上述缺点的办法是：首先，代替原来的那个统一的栈顶指示器，让每个过程首先，代替原来的那个统一的栈顶指示器，让每个过程和分程序都有自己的栈顶指示器和分程序都有自己的栈顶指示器TOP，它的值保存在各，它的值保存在各自的活动记录中自的活动记录中44其次，不把分程序看作其次，不把分程序看作“无参过程无参过程”，而让每个分程序，而让每个分程序享享用包围它的那个最小过程的用包围它的那个最小过程的displayv每个过程的活动记录所含的内容有：每个过程的活动记录所含的内容有：1.过程的过程的TOP单元，指向活动记录的栈顶位置单元，指向活动记录的栈顶位置2.连接数据：连接数据：(1)老老SP值值(2)返回地址返回地址(3)全局全局display地址地址(4)调用时的栈顶单元地址，称作老调用时的栈顶单元地址，称作老TOP3.参数个数和形式单元参数个数和形式单元4.display表表455.过程所管辖的各分程序的局部数据单元对每个分程序来说过程所管辖的各分程序的局部数据单元对每个分程序来说,它们包括：它们包括：(1)一个名为一个名为TOP的单元，当进入时它含现行栈顶地址，以后的单元，当进入时它含现行栈顶地址，以后用来存放栈的新高度用来存放栈的新高度(2)分程序的局部变量、数组内情向量和临时工作单元分程序的局部变量、数组内情向量和临时工作单元46v图图8.22给出了过程给出了过程A（见图（见图10.21）的活动记录的结构：）的活动记录的结构：47v下面用一个例子说明进出分程序时数据区的变化过程：下面用一个例子说明进出分程序时数据区的变化过程：图图8.23（a）表示已调用了图）表示已调用了图10.21的过程的过程A，控制已转入，控制已转入A中，但尚未开始执行过程体时栈的内容中，但尚未开始执行过程体时栈的内容图图8.23（b）反映了已进入过程体分程序（）反映了已进入过程体分程序（B1），但尚未），但尚未分配数组空间时栈的内容。分程序分配数组空间时栈的内容。分程序B1的的TOP值直接抄自值直接抄自外层分程序的外层分程序的TOP单元单元图图8.23（c）反映了分配数组）反映了分配数组B后的情形，此时后的情形，此时B1的的TOP值上升到指示新栈顶，但过程值上升到指示新栈顶，但过程A的的TOP值不动值不动图图8.23（d）反映了进入分程序）反映了进入分程序B2之后的情形之后的情形48进入分程序进入分程序B4时又抄写时又抄写B1的的TOP,并对数组并对数组C进行分配，进行分配，于是得到图于是得到图8.23（e）当进入分程序当进入分程序B5时，再次抄写直接外层的时，再次抄写直接外层的TOP值，得到值，得到图图8.23（f）49508.3参数传递参数传递v把实在参数传递给相应的形式参数方法：把实在参数传递给相应的形式参数方法：传值、传地址、传名、传结果等传值、传地址、传名、传结果等一一.传值（值调用）传值（值调用）v将实参计算出它的值，然后把它传给被调过程：将实参计算出它的值，然后把它传给被调过程：1.形式参数当作过程的局部变量处理形式参数当作过程的局部变量处理2.调用过程计算实参的值，并将它们的值放在为形式单元调用过程计算实参的值，并将它们的值放在为形式单元开辟的空间中开辟的空间中3.被调用过程执行时，就像使用局部变量一样使用这些形式被调用过程执行时，就像使用局部变量一样使用这些形式单元单元v传值的重要特点是对形式参数的任何运算不影响调用过程的活动记录中传值的重要特点是对形式参数的任何运算不影响调用过程的活动记录中实参的值实参的值v通过值调用的过程可以由非局部量或由指针而对调用过程发生影响通过值调用的过程可以由非局部量或由指针而对调用过程发生影响51二二.传地址传地址v当参数通过引用传递时，也称作传地址，或引用调用当参数通过引用传递时，也称作传地址，或引用调用v调用过程传给被调过程的是指针，指向实参存储位置的调用过程传给被调过程的是指针，指向实参存储位置的指针指针1.如实参是一个名字，则名字的地址传递过去如实参是一个名字，则名字的地址传递过去2.如实参是一个表达式，比如如实参是一个表达式，比如a+b或或2，而没有左值，则表，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址传递达式先求值，并存入某一位置，然后该位置的地址传递过去过去3.被调过程中对形式参数的任何引用和赋值都通过传递到被被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被处理成间接访问调过程的指针被处理成间接访问52二二.传名传名v当参数通过名字传递时，也称作传名调用当参数通过名字传递时，也称作传名调用v调用过程传给被调过程的是名字，实参名字代替形参名字调用过程传给被调过程的是名字，实参名字代替形参名字1.如实参是一个名字，则名字直接替代相应的形式参数如实参是一个名字，则名字直接替代相应的形式参数2.如实参是一个表达式，比如如实参是一个表达式，比如a+b，a+b替代相应的形式参数替代相应的形式参数3.被调过程中对形式参数的任何引用和赋值都通过传递名字被调过程中对形式参数的任何引用和赋值都通过传递名字到被调过程的指针被处理成间接访问到被调过程的指针被处理成间接访问53二二.传结果传结果v调用过程传给被调过程的是指针和值，每个形式参数对调用过程传给被调过程的是指针和值，每个形式参数对应两个单元，一个存实参的地址，一个存实参的值。应两个单元，一个存实参的地址，一个存实参的值。1.如实参是一个名字，则名字的地址和值传递过去如实参是一个名字，则名字的地址和值传递过去2.如实参是一个表达式，比如如实参是一个表达式，比如a+b或或2，则表达式先求值，则表达式先求值，并存入某一位置，然后该位置的地址和值传递过去并存入某一位置，然后该位置的地址和值传递过去3.调用结束前，再将执行的结果写到对应的实参单元调用结束前，再将执行的结果写到对应的实参单元54例：例：对于下面程序：对于下面程序：Procedure p(x,y,z);begin y:=y+1;z:=z+x;end;p begin a:=2;b:=3;p(a+b,a,a)print a end.若参数传递的方法分别为若参数传递的方法分别为（1）传值（）传值（2）传）传地址地址（3）传名（）传名（4）传结果）传结果。执行时所输出的执行时所输出的a分别是什分别是什么？么？55（1）传值传值.则将实参的值传递给被调用者则将实参的值传递给被调用者 p.程序运行时有（假设程序运行时有（假设a的地址的地址为为add_a,b的地址为的地址为 add_b);调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a 2 x:5 add_b 3 y:2临时单元临时单元T:5 z:2程序运行执行了语句程序运行执行了语句“y:=y+1”后有后有:调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a 2 x:5 add_b 3 y:3临时单元临时单元T:5 z:2程序运行执行了语句程序运行执行了语句“z:=z+x”后有后有:调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a 2 x:5 add_b 3 y:3临时单元临时单元T:5 z:7所以程序输出所以程序输出 2。56 （2）传地址传地址，则将实在参数的地址传递给则将实在参数的地址传递给被被调用者，调用者，p 运行时有（运行时有（假设假设a的地址为的地址为add_a,b的地址为的地址为add_b);调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a:2 x:T add_b:3 y:add_a 临时单元临时单元T:5 z:add_a(a+b)的值的值程序运行执行了语句程序运行执行了语句“y:=y+1”后，有后，有:调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a 3 x:T add_b 3 y:add_a 临时单元临时单元T:5 z:add_a 执行了语句执行了语句“z:=z+x”后有：后有：调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a 8 x:T add_b 3 y:add_a 临时单元临时单元T:5 z:add_a所以程序输出所以程序输出 8。57解：解：（3）传名传名 当执行调用当执行调用p(a+b,a,a)时，相当于被调用者被替换成时，相当于被调用者被替换成 procedure p(a+b,a,a)begin a:=a+1 a:=a+a+b end;p 调用者的数据区为：调用者的数据区为：a:2 b:3 执行语句执行语句“a:=a+1”后，调用者数据区为：后，调用者数据区为：a:3 b:3执行语句：执行语句：a:=a+a+b 后，调用者的数据区为：后，调用者的数据区为：a:9 b:3 因此程序输出为因此程序输出为9。58（2）传结果传结果，则将实在参数的地址和值传递给则将实在参数的地址和值传递给被调用者被调用者，p 运行时有（运行时有（假设假设a的的地址为地址为add_a,b的地址为的地址为add_b，临时单元，临时单元T的地址为的地址为add_T);调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a:2 x:T 5 add_b:3 y:add_a 2临时单元临时单元T:5 z:add_a(a+b)的值的值 2程序运行执行了语句程序运行执行了语句“y:=y+1”后，有后，有:调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a:2 x:T 5 add_b:3 y:add_a 3临时单元临时单元T:5 z:add_a 2 59 执行了语句执行了语句“z:=z+x”后有：后有：调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a:2 x:T 5 add_b:3 y:add_a 3临时单元临时单元T:5 z:add_a 7调用结束前，被调用者数据存放到对应的调用者数据单元调用结束前，被调用者数据存放到对应的调用者数据单元即：即：调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a:7 x:T 5 add_b:3 y:add_a 3临时单元临时单元T:5 z:add_a 7所以程序输出所以程序输出 7。608.4过程调用、过程进入和过程返回过程调用、过程进入和过程返回v对于过程调用的四元式序列：对于过程调用的四元式序列：par T1 1par T2 2par par T Tn ncall call P,nP,nv在运行时是如何执行的？在运行时是如何执行的？/par和和call产生什么相应的目标代码产生什么相应的目标代码对于对于par Ti i（i=1,2,n),n)的处理是：根据的处理是：根据par Ti i（i=1,2,n)中中Ti i的种别而生成传送指令，或将参数的值或将参数的地址传送的种别而生成传送指令，或将参数的值或将参数的地址传送至新的过程的活动记录的形式单元中至新的过程的活动记录的形式单元中（此节自习）（此节自习）61v对于对于call p,n则应生成传送参数个数则应生成传送参数个数n的指令；保护现行的指令；保护现行SP至新过程的活动记录（老至新过程的活动记录（老SP）；转子，转向）；转子，转向P的第一条指的第一条指令；定义新令；定义新SP；保护返回地址；定义新值；填写；保护返回地址；定义新值；填写display或或存取链内容等指令存取链内容等指令v如果过程含动态数组（局部），则应生成对数组进行存储如果过程含动态数组（局部），则应生成对数组进行存储分配的指令，即生成运行时动态地建立内情向量和分配数分配的指令，即生成运行时动态地建立内情向量和分配数组空间的目标指令组空间的目标指令v在过程执行语句的工作过程中，凡引用形参、局部变量或在过程执行语句的工作过程中，凡引用形参、局部变量或数组元素都可根据过程活动记录起点的相对位置访问数组元素都可根据过程活动记录起点的相对位置访问62v当过程当过程P工作完毕要返回到调用段时，若语言有形如工作完毕要返回到调用段时，若语言有形如return（E）的返回语句，或）的返回语句，或P是个函数过程时，则可把已算好的是个函数过程时，则可把已算好的值传送至某个特定的寄存器中，调用段将从这个特定的寄值传送至某个特定的寄存器中，调用段将从这个特定的寄存器中获得被调过程的结果值。然后所生成的目标指令则存器中获得被调过程的结果值。然后所生成的目标指令则应完成的工作是：恢复应完成的工作是：恢复SP；恢复；恢复TOP，按保存的返回地址，按保存的返回地址实行无条件转移实行无条件转移63【本章小结本章小结】目标代码运行时，存储区域的整体布局目标代码运行时，存储区域的整体布局,以及各区域的作用以及各区域的作用各种不同数据变量区的不同分配组织方式各种不同数据变量区的不同分配组织方式允许过程嵌套定义的语言，栈式动态分配的组织管理允许过程嵌套定义的语言，栈式动态分配的组织管理过程活动纪录的各项内容和它们的作用，以及活动纪录的过程活动纪录的各项内容和它们的作用，以及活动纪录的组织方式组织方式参数传递的不同方式及其实现参数传递的不同方式及其实现过程调用和返回时，相应目标代码以及栈式动态分配区的过程调用和返回时，相应目标代码以及栈式动态分配区的管理管理64作业作业1、下面的程序执行时输出的、下面的程序执行时输出的a分别是什么分别是什么?若若(1)参数的传递办法为参数的传递办法为传值传值；(2)参数的传递办法为参数的传递办法为“传地址传地址”。(3)参数的传递办法为参数的传递办法为“传传名名”。(4)参数的传递办法为参数的传递办法为传传结果结果。program main(input,output);procedure p(x,y,z);beginy =y+1;z =z+x;end;begina =4;b =6;p(a+b,a,a);print a end.652、下面是一个、下面是一个Pascal程序程序program PP(input,output)var K:integer;function F(N:integer):integerbeginif N=0 then F:=1else F:=N*F(N-1);end;begin K:=F(10);.end;当第二次（递归地）进入当第二次（递归地）进入F后，后，DISPLAY的内容的内容是什么？当时整个运行栈的内容是什么？是什么？当时整个运行栈的内容是什么？临时变量内情向量简单变量display形式单元形参个数全局display返回地址老SP663、如下的如下的Pascal程序，程序，program Tr(input,output);var i:integer;d:integer;procedure A(k:real);var p:char;procedure B;var c:char;begin.(1).end;Bprocedure C;var t:real;begin.(2).end;Cbegin.B;C;.end;Abeginmain.A(d);.end.并已知在运行时刻，以过程为单位对程序中的变量进行动态存储并已知在运行时刻，以过程为单位对程序中的变量进行动态存储分配。试分别给出程序执行到（分配。试分别给出程序执行到（1）和（）和（2）点时运行栈的内容和）点时运行栈的内容和DISPLAY的内容。的内容。临时变量内情向量简单变量display形式单元形参个数全局display返回地址老SP