编译原理第10章 存储组织课件

编译原理之

存储组织编译原理第10章存储组织第十章目标程序运行时的存储组织概述数据空间的使用方法和管理方法栈式存储分配的实现参数传递过程操作练习编译原理第10章存储组织概述一般来讲，假如编译程序从操作系统中得到一块存储区以位目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。数据空间应包括：用户定义的各种类型的数据对象(变量和常数)所需的存储空间、作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元、以及组织输入/输出所需的缓冲区。运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区。运行时存储区的典型划分编译程序对数据空间的分配编译原理第10章存储组织运行时存储区的典型划分代码(code)区用以存放目标代码，这是固定长度的，即编译时能确定的。静态数据区(staticdata)用以存放编译时能确定所占用空间的数据。堆栈区(stackandheap)用于可变数据以及管理过程活动的控制信息。目标程序运行时存储区的典型划分编译原理第10章存储组织编译程序对数据空间的分配基本原则是程序语言设计时对程序运行中存储空间的使用和管理办法的规定。数据空间的分配：本质上看是将程序中的每个名字与一个存储位置关联起来，该存储位置用以容纳名字的值。在程序设计语言语义学中，使用术语environment表示将一个名字映射到一个存储位置的函数，术语state表示存储位置到值的映射。名字到存储、到值的映射编译原理第10章存储组织数据空间的使用方法和管理方法术语：静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。静态存储分配动态存储分配编译原理第10章存储组织静态存储分配如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，那么则称这种分配策略为静态存储分配。示例FORTRAN77的示例程序该程序中局部变量的静态存储位置编译原理第10章存储组织FORTRAN77的程序编译原理第10章存储组织局部变量的静态存储位置编译原理第10章存储组织动态存储分配如果一个程序设计语言允许递归过程、可变数组或可变数据结构，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。分类：栈式动态存储分配堆式动态存储分配编译原理第10章存储组织栈式动态存储分配这种分配策略是将整个程序的数据空间设计为一个栈。它适用于Pascal，C，ALGOL之类的语言的实现，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。过程所需的数据空间包括两部分：一部分是生存期在本过程这次活动中的数据对象，如局部变量、参数单元、临时变量等等；另一部分则是用以管理过程活动的记录信息，即当一次过程调用出现时，调用该过程的那个过程的活动即被中断，当前机器的状态信息，诸如程序计数器(返回地址)、寄存器的值等等，也都必须保留在栈中。当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活动重新开始。编译原理第10章存储组织堆式动态存储分配如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制(如C++中的new，delete．Pascal的new，便是这种机制)，或者不仅有过程而且有进程的程序结构，即空间的使用未必服从“先申请后释放，后申请先释放”的原则，那么栈式的动态分配方案就不适用了。这种情况下通常使用一种称为堆式的动态存储分配方案。假设程序运行时有一个大的存储空间，每当需要时就从这片空间中借用一块，不用时再退还，由于借还的时间先后不一，经一段运行之后，程序运行空间将被分划成许多块块，有些占用，有些空闲。那么当运行程序要求一块体积为N的空间时，需要决定应该从哪个空闲块得到这个空间。理论上讲，应该从比N稍大一些的空间块中取出N个单元，以便位大的空闲块派更大的用场，但实现难度很大，实际中常常采用的办法是：先遇到哪块比N大就从其中取出N个单元。即使这样，也会发生找不到一块比N大的空闲块，但所有空闲块的总和比N大得多的情况，这时，有的分配管理系统采用废品回收的办法来应付。编译原理第10章存储组织栈式存储分配的实现过程的活动记录简单的栈式动态分配实现嵌套过程语言的栈式实现分程序结构的存储管理编译原理第10章存储组织过程的活动记录过程的活动记录是一段连续的存储区．用以存放过程的一次执行所需要的信息。简单描述编译原理第10章存储组织简单描述1．临时工作单元，比如计算表达式过程中需存放中间结果用的临时值单元。2．局部变量，一个过程的局部变量。3．保存机器状态，容纳该过程执行前关于机器状态信息，诸如程序计数器、寄存器的值，这些值都需要在控制从该过程返回时给予恢复。4．存取链，用以存取非局部变量，这些变量存放于其它过程活动记录中。并不是所有语言需要该信息。5．控制链，指向调用该过程的那个过程的活动记录，这也不是所有语言都需要的。6．实参，也称形式单元，由调用过程向该被说过程提供实参的值(或地址)。当然在实际编译程序中，也常常使用机器寄存器传递实参。7．返回地址，保存该被调过程返回后的地址。编译原理第10章存储组织简单的栈式动态分配实现要求：没有分程序结构过程定义不嵌套允许过程递归调用示例：程序结构分配策略存储分配结构图活动记录内容运行栈编译原理第10章存储组织程序结构编译原理第10章存储组织分配策略运行时，每当进入一个过程，则为该过程分配一段存储区。当一个过程工作完毕返回时，它所占用的存储区则可释放。程序运行时的存储空间，(栈)中在某一时刻可能会包含某个过程的几个活动记录(某个过程递归调用的情况)；另外，同样的一个存储位置，可能不同运行时刻分配给不同的数据对象。编译原理第10章存储组织存储分配结构图若主程序调用了过程Q，Q又调用了R，在R进入运行后的存储结构如图(a)所示。若主程序调用了过程Q，Q递归调用自己，在Q过程第二次进入运行后的存储结构如图(b)所示。若主程序先调用过程Q，然后主程序接着调用R，且Q过程不调用Q和R，这时Q和R进入运行后的存储结构分别如图(c)和(d)所示。编译原理第10章存储组织活动记录内容SP总是指向现行过程活动记录的起点。TOP则始终指向已占用的栈顶单元。编译原理第10章存储组织运行栈编译原理第10章存储组织嵌套过程语言的栈式实现具有嵌套过程的Pascal程序程序中过程定义的嵌套情况存储栈的布局活动记录情况在过程活动记录中增设存储链在过程活动记录中存取非局部变量编译原理第10章存储组织具有嵌套过程的Pascal程序编译原理第10章存储组织程序中过程定义的嵌套情况sortreadarrayexchangequicksonpartition可将整个程序sort看成最外层的过程，readarray、exchange、quickson、partition中引用的a均不是它们的局部变量，而是过程sort的局部变量。编译原理第10章存储组织存储栈的布局假如过程sort激活(调用)了过程quicksort，这时存储栈小的情形示意如下图所示，其中在quicksort过程活动记录中有一(或一些)存储单元(用斜线描绘)用以记录过程quicksort以引用sort中定义的变量a和x。编译原理第10章存储组织增设存储链在活动记录过程中增设存取链，指向包含该过程的直接外层过程的最新活动记录的起始位置。示例：过程活动记录的内容图过程sort调用过程quicksort的存储栈图如果某次执行的顺序为:sort→quicksort→quicksort→partition→exchange→⋯进入过程exchange之后的运行栈图。编译原理第10章存储组织过程活动记录的内容图编译原理第10章存储组织过程sort调用过程quicksort的存储栈图编译原理第10章存储组织进入过程exchange之后的运行栈图编译原理第10章存储组织存取非局部变量存取非局部变量的办法是常用的有效办法。即每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表display。display是一个指针数组d，也可看作是一个小栈，自顶向下每个单元依次存放着现行层，直接外层，……直至最外层(0层，主程序层)等每一层过程的最新活动记录的地址。示例：1)sort→quicksort⋯；2)sort→quicksort→quicksort⋯

；3)sort→quicksort→quicksort→partition⋯

；4)sort→quicksort→quicksort→partition→exchange⋯

过程调用时display的建立编译原理第10章存储组织1的运行栈和display编译原理第10章存储组织2的运行栈和display编译原理第10章存储组织3的运行栈和display编译原理第10章存储组织4的运行栈和display编译原理第10章存储组织过程调用时display的建立当过程P1调用过程P2而进入P2后，P2为了建立自己的display，P2必须知道它的直接外层过程(记为P0)的display。这意味着,当P1调用P2时必须把P0的display地址作为连接数据之一传给P2。display的构造P2是真实过程时的构造P2是形式参数时的构造编译原理第10章存储组织真实过程时的构造P0或者就是P1自身或者既是P1又是P2的直接外层(示意图)。不论哪一种情形，只要在进入P2后能够知道P1的display就能知道P0的display，从而可直接构造出P2的display。事实上，只需从P1的display中自底而上地取过l2个单元(l2为P2的层数)再添上进入P2后新建立的SP值就构成了P2的display。也就是说，在这种情况下，只需把P1的display地址作为连接数据之一传送给P2就能够建立P2的display。编译原理第10章存储组织P1调用P2的两种不同嵌套示意图编译原理第10章存储组织形式参数时的构造调用P2意味着调用P2当前相应的实在过程。此时的P0应是这个实在过程的直接外层过程。假定P0的display地址可从形式单元P2所指示的地方获得。为了能在P2中获得P0的display地址，必须在P1调用P2时设法把P1的display地址作为连接数据之一(称为“全局display地址”)传送给P2。于是连接数据变为三项：(1)老SP值；(2)返回地址；(3)全局display地址。编译原理第10章存储组织分程序结构的存储管理概述声明作用域遵循的原则——最近嵌套原则分程序结构的存储管理分程序结构的存储实现方法视分程序为“无参过程”视分程序为完整的过程体活动记录的内容分程序的进入和退出时活动记录的情况编译原理第10章存储组织概述一个分程序是一个含有它自己的局部数据(变量)声明的语句。示例：C语言，一个分程序的语法形式是：{声明语句}C语言的一个分程序分程序的特征是它们的嵌套结构，使用界符标明分程序的开始和结束。界符保证一个分程序要么与别的分程序无关，要么是嵌在别的分程序中，这种嵌套性有时称作“分程序结构”编译原理第10章存储组织C语言的一个分程序编译原理第10章存储组织最近嵌套原则1、一个分程序B中的一个声明的作用域包含在B中。2、如果某个名字x未在分程序B中声明。那么，若B中出现的x的声明的作用域是在B的包含层B’中，则应该：(1)B’中有x的声明；(2)B’与任何别的包含有x声明的分程序相比，它是最近包围B的分程序。编译原理第10章存储组织分程序结构的存储管理分程序结构用栈式存储分配实现，是因为一个声明的作用域不会落在它出现的分程序之外，该声明的空间可以在分程序进入时分配。编译原理第10章存储组织无参过程把分程序看成一个“无参过程”，只不过是在该分程序前调用，分程序之后返回，分程序在哪里定义就在哪里被调用。效率低下的原因解决效率低的办法编译原理第10章存储组织效率低下的原因第一分程序不存在被调用的问题，不必要在进入一个分程序时，将连接数据(如动态链、返回地址等)和display都放进活动记录中；第二，当从内层分程序向外转移时可能同时要结束若干个分程序，恢复所要到达的那个分程序的数据区需要顺序退出，浪费时间，降低效率。编译原理第10章存储组织解决效率低的办法首先，代替原来的那个统一的栈顶指示器，让每个过程和分程序都有自己的栈顶指示器TOP，它的值保存在各自的活动记录中。这样上述第二个问题即可解决；其次，不把分程序看作“无参过程”，而让每个分程序享用包围它的那个最小过程的display。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。每个过程被当作0层分程序，而过程体分程序(假定是一个分程序)当作是它所管辖的第一层分程序。编译原理第10章存储组织完整过程体每次为一个完整的过程体分配存储，即把一个过程体中的所有分程序所需的存储一次分配好。编译原理第10章存储组织活动记录的内容内容：1．过程的TOP单元，指向活动记录的栈顶位置；2．连接数据，共4项：(1)老SP值；(2)返回地址；(3)全局display地址；(4)调用时的栈顶单元地址，称作老TOP。3．参数个数和形式单元。4．display表。5．过程所管辖的各分程序的局部数据单元对每个分程序来说，它们包括：(1)一个名为TOP的单元，当进入时它含现行栈顶地址，以后用来存放栈的新高度；(2)分程序的局部变量、数组内情向量和临时工作单元。示例：程序活动记录编译原理第10章存储组织ALGOL的一个程序编译原理第10章存储组织ALGOL的活动记录编译原理第10章存储组织活动记录的情况分程序进入时分程序退出时分程序结构数据区变化图编译原理第10章存储组织分程序进入时的活动记录每个分程序在进入时，都有它自己的一个TOP单元，刚进入时，它的TOP值是由其直接外层分程序的TOP单元的内容所赋予的。一旦定义了TOP值后，就对该分程序的所有局部数组进行地址分配。每分配一个数组区后，TOP的值随即调整指向新的栈顶位置。过程看成0层分程序、它是通过调用而进入的，它的TOP值是调用时的栈顶地址加上它的活动记录的长度L，L是在编译时静态计算出来的。运行中每逢进入分程序(除0层分程序外)，即执行分程序的begin语句时，只需把直接外层分程序的TOP值抄进自己的TOP单元中。由于分程序的数据区起点(分程序TOP单元所在处)可在编译时静态地确定，因此，这个抄送动作只需用两条指令就可完成。所以，进入分程序所要做的工作是非常简单的。在进入分程序建立TOP单元的值之后，执行第一个执行句之前，如果有数组说明则应对所定义的数组分配存储空间。数组空间分配之后，TOP调整为指向新的栈顶(新分配的数组区的顶端)。编译原理第10章存储组织分程序退出时的活动记录在分程序工作完毕正常退出时，即到达分程序的end语句时，无需进行任何退栈的工作。换句话说，分程序的正常出口不需要执行任何指令。编译原理第10章存储组织分程序结构数据区变化图编译原理第10章存储组织参数传递传值传地址传结果传名字过程参数编译原理第10章存储组织传值传值，即call-by-value，也称值调用，是最简单的参数传递方法。即将实参计算出它的值．然后把它传给被调过程。参数传递方法的不同主要基于实在参数是表达一个右值，一个左值，还是实在参数本身的文本(字)。“左”和“右”来自赋值语句的“左”端和“右”端。左值：(l-value)指表达式代表的存储。右值：(r-value)指该存储位置中含有的值。传值的具体内容传值的特点传值的示例编译原理第10章存储组织传值的具体内容1、形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是实参或形式单元。2、调用过程计算实参的值，并将它们的右值(r-value)放在为形式单元开辟的空间中。3、被调用过程执行时，就像使用局部变量一样使用这些形式单元。编译原理第10章存储组织传值的特点传值或值调用的重要特点是对形式参数的任何运算不影响调用过程的活动记录中实参的值。编译原理第10章存储组织传值的示例该程序的输出是：a＝2，b＝l如果将第3行的关键字var去掉，则是以传值方式将x和y传递给过程swap，第12行swap(a，b)调用过程将不会影响a和b的值，则该程序的输出是：a＝1，b＝2。编译原理第10章存储组织传地址当参数通过引用传递时，称作传地址，或引用调用(call-by-reference)。调用过程传给被调过程的是指针，指向实参存储位置的指针。1、如实参是一个名字或是具有左值的表达式，则左值本身传递过去。2、如实参是一表达式，比方a+b或2，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址传递过去。3、被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被处理成间接访问。示例编译原理第10章存储组织传地址示例若用实参i和a[i]对过程swap进行调用，即swap(i，a[i])，其效果如下步骤所述：1、将i和a[i]的地址(左值)拷贝到被调过程的活动记录中，比如说分别对应形参x和y的单元arg1和arg2。2、将局部变量temp设为由arg1所指单元的内容(即令temp等于I0

，其中I0是i的初值)，这一步对应于swap定义中的第6行语句temp＝x。3、将arg1所指单元的内容设为arg2所指单元的值，即i:＝a[I0]，这一步对应于swap定义中第7行的x:＝y。4、将arg2所指单元的内容设为等于temp的值，即，设a[I0]＝i，这一步对应y:＝temp。编译原理第10章存储组织传结果传结果(call-by-value-result)：处理的每一形参，需分配两个形式单元，分别称为该形参的第一形式单元和第二形式单元，其中第二形式单元被视为过程体的局部单元。实现这种传递的方法是：在进行入过程时，将实参的地址送入相应形参的第一形式单元，将实参之值送入第二形式单元。在退出过程时，再将第二形式单元中形参的终值再按第一形式单元中的实参地址赋给相应的实参，所以有时又将这种参数传递称为复写存贮连接。编译原理第10章存储组织传名字传名字(call-by-name)。这种数据传递方式是：将实在参数的名字传给过程中相应的形式参数，也就是，过程体中的形式参数都要用相应的实在参数的名字进行替换。这种名字替换的实质是：在过程说明的目标程序中，在形式参数出现的地方都要使用相应实在参数当时的值或地址。编译原理第10章存储组织过程参数一个嵌套过程(函数)可以作为参数传递。示例：嵌套过程代码过程参数传递情况编译原理第10章存储组织嵌套过程程序代码(1)programparam(input,ouput);(2)procedureb(fuctionh(n:integer):integer);(3)beginwriteln(h(2))end{b};(4)procedurec;(5)varm；integer;(6)functionf(n:integer):integer;(7)beginf:=m+nend{f};(8)beginm:=0;b(f)end{c};(9)begin(10)c(11)end编译原理第10章存储组织过程参数传递情况过程c把f作为参数传递给b，而b通过引用形参h调用f。要注意的是：函数f有一非局部量m。但m的作用域并不包括b的过程体。b中的语句writeln(h(2))激活f，是因为形参h引用f，writeln打印的是调用f(2)的结果。编译原理第10章存储组织过程操作过程操作：调用进入返回示例：四元式序列运行时的执行含动态数组的过程的操作过程结束时的处理编译原理第10章存储组织四元式序列parT1parT2…parTncallP,n编译原理第10章存储组织运行时的执行对于ParTi，(i＝1，2，…，n)的处理是：根据parTi(i＝l，2，…，