编译原理存储组织教育课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译原理存储组织PPT讲座,第十章 目标程序运行时的存储组织,概述,数据空间的使用方法和管理方法,栈式存储分配的实现,参数传递,过程操作,练习,概述,一般来讲，假如编译程序从操作系统中得到一块存储区以位目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。,数据空间应包括：,用户定义的各种类型的数据对象(变量和常数)所需的存储空间、作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元、以及组织输入/输出所需的缓冲区。,运行时的存储区常常划分成：,目标区、静态数据区、栈区和堆区。,运行时存储区的典型划分,编译程序对数据空间的分配,运行时存储区的典型划分,代码(code)区用以存放目标代码，这是固定长度的，即编译时能确定的。,静态数据区(static data)用以存放编译时能确定所占用空间的数据。,堆栈区(stack and heap)用于可变数据以及管理过程活动的控制信息。,目标程序运行时存储区的典型划分,编译程序对数据空间的分配,基本原则是程序语言设计时对程序运行中存储空间的使用和管理办法的规定。,数据空间的分配：,本质上看是将程序中的每个名字与一个存储位置关联起来，该存储位置用以容纳名字的值。,在程序设计语言语义学中，使用术语environment表示将一个名字映射到一个存储位置的函数，术语state表示存储位置到值的映射。,名字到存储、到值的映射,数据空间的使用方法和管理方法,术语：,静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。,动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。,静态存储分配,动态存储分配,静态存储分配,如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，那么则称这种分配策略为静态存储分配。,示例,FORTRAN 77的示例程序,该程序中局部变量的静态存储位置,FORTRAN 77的程序,局部变量的静态存储位置,动态存储分配,如果一个程序设计语言允许递归过程、可变数组或可变数据结构，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。,分类：,栈式动态存储分配,堆式动态存储分配,栈式动态存储分配,这种分配策略是将整个程序的数据空间设计为一个栈。它适用于Pascal，C，ALGOL之类的语言的实现，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。,过程所需的数据空间包括两部分：,一部分是生存期在本过程这次活动中的数据对象，如局部变量、参数单元、临时变量等等；,另一部分则是用以管理过程活动的记录信息，即当一次过程调用出现时，调用该过程的那个过程的活动即被中断，当前机器的状态信息，诸如程序计数器(返回地址)、寄存器的值等等，也都必须保留在栈中。,当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活动重新开始。,堆式动态存储分配,如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制(如C+中的new，deletePascal的new，便是这种机制)，或者不仅有过程而且有进程的程序结构，即空间的使用未必服从“先申请后释放，后申请先释放”的原则，那么栈式的动态分配方案就不适用了。这种情况下通常使用一种称为堆式的动态存储分配方案。,假设程序运行时有一个大的存储空间，每当需要时就从这片空间中借用一块，不用时再退还，由于借还的时间先后不一，经一段运行之后，程序运行空间将被分划成许多块块，有些占用，有些空闲。那么当运行程序要求一块体积为N的空间时，需要决定应该从哪个空闲块得到这个空间。,理论上讲，应该从比N稍大一些的空间块中取出N个单元，以便位大的空闲块派更大的用场，但实现难度很大，实际中常常采用的办法是：先遇到哪块比N大就从其中取出N个单元。即使这样，也会发生找不到一块比N大的空闲块，但所有空闲块的总和比N大得多的情况，这时，有的分配管理系统采用废品回收的办法来应付。,栈式存储分配的实现,过程的活动记录,简单的栈式动态分配实现,嵌套过程语言的栈式实现,分程序结构的存储管理,过程的活动记录,过程的活动记录是一段连续的存储区用以存放过程的一次执行所需要的信息。,简单描述,简单描述,1临时工作单元，比如计算表达式过程中需存放中间结果用的临时值单元。,2局部变量，一个过程的局部变量。,3 保存机器状态，容纳该过程执行前关于机器状态信息，诸如程序计数器、寄存器的值，这些值都需要在控制从该过程返回时给予恢复。,4存取链，用以存取非局部变量，这些变量存放于其它过程活动记录中。并不是所有语言需要该信息。,5控制链，指向调用该过程的那个过程的活动记录，这也不是所有语言都需要的。,6实参，也称形式单元，由调用过程向该被说过程提供实参的值(或地址)。当然在实际编译程序中，也常常使用机器寄存器传递实参。,7返回地址，保存该被调过程返回后的地址。,简单的栈式动态分配实现,要求：,没有分程序结构,过程定义不嵌套,允许过程递归调用,示例：,程序结构,分配策略,存储分配结构图,活动记录内容,运行栈,程序结构,分配策略,运行时，每当进入一个过程，则为该过程分配一段存储区。当一个过程工作完毕返回时，它所占用的存储区则可释放。程序运行时的存储空间，(栈)中在某一时刻可能会包含某个过程的几个活动记录(某个过程递归调用的情况)；,另外，同样的一个存储位置，可能不同运行时刻分配给不同的数据对象。,存储分配结构图,若主程序调用了过程Q，Q又调用了R，在R进入运行后的存储结构如图(a)所示。,若主程序调用了过程Q，Q递归调用自己，在Q过程第二次进入运行后的存储结构如图(b)所示。,若主程序先调用过程Q，然后主程序接着调用R，且Q过程不调用Q和R，这时Q和R进入运行后的存储结构分别如图(c)和(d)所示。,活动记录内容,SP总是指向现行过程活动记录的起点。,TOP则始终指向已占用的栈顶单元。,运行栈,嵌套过程语言的栈式实现,具有嵌套过程的Pascal程序,程序中过程定义的嵌套情况,存储栈的布局,活动记录情况,在过程活动记录中增设存储链,在过程活动记录中存取非局部变量,具有嵌套过程的Pascal程序,程序中过程定义的嵌套情况,sort,readarray,exchange,quickson,partition,可将整个程序sort看成最外层的过程，readarray、exchange、quickson、partition中引用的a均不是它们的局部变量，而是过程sort的局部变量。,存储栈的布局,假如过程sort激活(调用)了过程quicksort，这时存储栈小的情形示意如下图所示，其中在quicksort过程活动记录中有一(或一些)存储单元(用斜线描绘)用以记录过程quicksort以引用sort中定义的变量a和x。,增设存储链,在活动记录过程中增设存取链，指向包含该过程的直接外层过程的最新活动记录的起始位置。,示例：,过程活动记录的内容图,过程sort调用过程quicksort的存储栈图,如果某次执行的顺序为:,sort,quicksortquicksortpartitionexchange,进入过程exchange之后的,运行栈图,。,过程活动记录的内容图,过程sort调用过程quicksort的存储栈图,进入过程exchange之后的运行栈图,存取非局部变量,存取非局部变量的办法是常用的有效办法。即每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表display。,display是一个指针数组d，也可看作是一个小栈，自顶向下每个单元依次存放着现行层，直接外层，直至最外层(0层，主程序层)等每一层过程的最新活动记录的地址。,示例：,1),sort,quicksort,；,2),sort,quicksort quicksort,；,3),sort,quicksort quicksort partition,；,4),sort,quicksortquicksortpartitionexchange,过程调用时display的建立,1的运行栈和display,2的运行栈和display,3的运行栈和display,4的运行栈和display,过程调用时display的建立,当过程P1调用过程P2而进入P2后，P2为了建立自己的display，P2必须知道它的直接外层过程(记为P0)的display。这意味着,当P1调用P2时必须把P0的display地址作为连接数据之一传给P2。,display的构造,P2是真实过程时的构造,P2是形式参数时的构造,真实过程时的构造,P0或者就是P1自身或者既是P1又是P2的直接外层(,示意图,)。不论哪一种情形，只要在进入P2后能够知道P1的display就能知道P0的display，从而可直接构造出P2的display。,事实上，只需从P1的display中自底而上地取过,l,2,个单元(,l,2,为P2的层数)再添上进入P2后新建立的SP值就构成了P2的display。也就是说，在这种情况下，只需把P1的display地址作为连接数据之一传送给P2就能够建立P2的display。,P1调用P2的两种不同嵌套示意图,形式参数时的构造,调用P2意味着调用P2当前相应的实在过程。此时的P0应是这个实在过程的直接外层过程。,假定P0的display地址可从形式单元P2所指示的地方获得。为了能在P2中获得P0的display地址，必须在P1调用P2时设法把P1的display地址作为连接数据之一(称为“全局display地址”)传送给P2。于是连接数据变为三项：,(1)老SP值；,(2)返回地址；,(3)全局display地址。,分程序结构的存储管理,概述,声明作用域遵循的原则,最近嵌套原则,分程序结构的存储管理,分程序结构的存储实现方法,视分程序为“,无参过程,”,视分程序为,完整的过程体,活动记录的内容,分程序的进入和退出时,活动记录的情况,概述,一个分程序是一个含有它自己的局部数据(变量)声明的语句。,示例：,C语言，一个分程序的语法形式是：声明 语句,C语言的一个分程序,分程序的特征是它们的嵌套结构，使用界符标明分程序的开始和结束。,界符保证一个分程序要么与别的分程序无关，要么是嵌在别的分程序中，这种嵌套性有时称作“分程序结构”,C语言的一个分程序,最近嵌套原则,1、一个分程序B中的一个声明的作用域包含在B中。,2、如果某个名字x未在分程序B中声明。那么，若B中出现的x的声明的作用域是在B的包含层B中，则应该：,(1)B中有x的声明；,(2)B与任何别的包含有x声明的分程序相比，它是最近包围B的分程序。,分程序结构的存储管理,分程序结构用栈式存储分配实现，是因为一个声明的作用域不会落在它出现的分程序之外，该声明的空间可以在分程序进入时分配。,无参过程,把分程序看成一个“无参过程”，只不过是在该分程序前调用，分程序之后返回，分程序在哪里定义就在哪里被调用。,效率低下的原因,解决效率低的办法,效率低下的原因,第一分程序不存在被调用的问题，不必要在进入一个分程序时，将连接数据(如动态链、返回地址等)和display都放进活动记录中；,第二，当从内层分程序向外转移时可能同时要结束若干个分程序，恢复所要到达的那个分程序的数据区需要顺序退出，浪费时间，降低效率。,解决效率低的办法,首先，代替原来的那个统一的栈顶指示器，让每个过程和分程序都有自己的栈顶指示器TOP，它的值保存在各自的活动记录中。这样上述第二个问题即可解决；,其次，不把分程序看作“无参过程”，而让每个分程序享用包围它的那个最小过程的display。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。每个过程被当作0层分程序，而过程体分程序(假定是一个分程序)当作是它所管辖的第一层分程序。,完整过程体,每次为一个完整的过程体分配存储，即把一个过程体中的所有分程序所需的存储一次分配好。,活动记录的内容,内容：,1过程的TOP单元，指向活动记录的栈顶位置；,2连接数据，共4项：,(1)老SP值；,(2)返回地址；,(3)全局display地址；,(4)调用时的栈顶单元地址，称作老TOP。,3参数个数和形式单元。,4display表。,5过程所管辖的各分程序的局部数据单元对每个分程序来说，它们包括：,(1)一个名为TOP的单元，当进入时它含现行栈顶地址，以后用来存放栈的新高度；,(2)分程序的局部变量、数组内情向量和临时工作单元。,示例：,程序,活动记录,ALGOL的一个程序,ALGOL的活动记录,活动记录的情况,分程序进入时,分程序退出时,分程序结构数据区变化图,分程序进入时的活动记录,每个分程序在进入时，都有它自己的一个TOP单元，刚进入时，它的TOP值是由其直接外层分程序的TOP单元的内容所赋予的。一旦定义了TOP值后，就对该分程序的所有局部数组进行地址分配。每分配一个数组区后，TOP的值随即调整指向新的栈顶位置。,过程看成0层分程序、它是通过调用而进入的，它的TOP值是调用时的栈顶地址加上它的活动记录的长度L，L是在编译时静态计算出来的。,运行中每逢进入分程序(除0层分程序外)，即执行分程序的begin语句时，只需把直接外层分程序的TOP值抄进自己的TOP单元中。由于分程序的数据区起点(分程序TOP单元所在处)可在编译时静态地确定，因此，这个抄送动作只需用两条指令就可完成。所以，进入分程序所要做的工作是非常简单的。,在进入分程序建立TOP单元的值之后，执行第一个执行句之前，如果有数组说明则应对所定义的数组分配存储空间。数组空间分配之后，TOP调整为指向新的栈顶(新分配的数组区的顶端)。,分程序退出时的活动记录,在分程序工作完毕正常退出时，即到达分程序的end语句时，无需进行任何退栈的工作。换句话说，分程序的正常出口不需要执行任何指令。,分程序结构数据区变化图,参数传递,传值,传地址,传结果,传名字,过程参数,传值,传值，即call-by-value，也称值调用，是最简单的参数传递方法。即将实参计算出它的值然后把它传给被调过程。,参数传递方法的不同主要基于实在参数是表达一个右值，一个左值，还是实在参数本身的文本(字)。“左”和“右”来自赋值语句的“左”端和“右”端。,左值：(l-value)指表达式代表的存储。,右值：(r-value)指该存储位置中含有的值。,传值的具体内容,传值的特点,传值的示例,传值的具体内容,1、形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是实参或形式单元。,2、调用过程计算实参的值，并将它们的右值(r-value)放在为形式单元开辟的空间中。,3、被调用过程执行时，就像使用局部变量一样使用这些形式单元。,传值的特点,传值或值调用的重要特点是对形式参数的任何运算不影响调用过程的活动记录中实参的值。,传值的示例,该程序的输出是：,a2，bl,如果将第3行的关键字var去掉，则是以传值方式将x和y传递给过程swap，第12行swap(a，b)调用过程将不会影响a和b的值，则该程序的输出是：,a1，b2。,传地址,当参数通过引用传递时，称作传地址，或引用调用(call-by-reference)。,调用过程传给被调过程的是指针，指向实参存储位置的指针。,1、如实参是一个名字或是具有左值的表达式，则左值本身传递过去。,2、如实参是一表达式，比方a+b或2，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址传递过去。,3、被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被处理成间接访问。,示例,传地址示例,若用实参i和ai对过程swap进行调用，即swap(i，ai)，其效果如下步骤所述：,1、将i和ai的地址(左值)拷贝到被调过程的活动记录中，比如说分别对应形参x和y的单元 arg1和arg2。,2、将局部变量temp设为由arg1所指单元的内容(即令temp等于I,0,，其中I,0,是i的初值)，这一步对应于swap定义中的第6行语句tempx。,3、将arg1所指单元的内容设为arg 2所指单元的值，即i:aI,0,，这一步对应于swap定义中第7行的x:y。,4、将arg2所指单元的内容设为等于temp的值，即，设aI,0,i，这一步对应y:temp。,传结果,传结果(call-by-value-result)：处理的每一形参，需分配两个形式单元，分别称为该形参的第一形式单元和第二形式单元，其中第二形式单元被视为过程体的局部单元。,实现这种传递的方法是：,在进行入过程时，将实参的地址送入相应形参的第一形式单元，将实参之值送入第二形式单元。,在退出过程时，再将第二形式单元中形参的终值再按第一形式单元中的实参地址赋给相应的实参，所以有时又将这种参数传递称为复写存贮连接。,传名字,传名字(call-by-name)。,这种数据传递方式是：将实在参数的名字传给过程中相应的形式参数，也就是，过程体中的形式参数都要用相应的实在参数的名字进行替换。,这种名字替换的实质是：在过程说明的目标程序中，在形式参数出现的地方都要使用相应实在参数当时的值或地址。,过程参数,一个嵌套过程(函数)可以作为参数传递。,示例：,嵌套过程代码,过程参数传递情况,嵌套过程程序代码,(1)program param(input,ouput);,(2)procedure b(fuction h(n:integer):integer);,(3)begin writeln(h(2)end b;,(4)procedure c;,(5)var m；integer;,(6)function f(n:integer):integer;,(7)begin f:=m+n end f;,(8)begin m:=0;b(f)end c;,(9)begin,(10)c,(11)end,过程参数传递情况,过程c把f作为参数传递给b，而b通过引用形参h调用f。要注意的是：函数f有一非局部量m。但m的作用域并不包括b的过程体。b中的语句writeln(h(2)激活f，是因为形参h引用f，writeln打印的是调用f(2)的结果。,过程操作,过程操作：,调用,进入,返回,示例：,四元式序列,运行时的执行,含动态数组的过程的操作,过程结束时的处理,四元式序列,par T,1,par T,2,par T,n,call P,n,运行时的执行,对于Par T,i,，(i1，2，n)的处理是：,根据par T,i,(il，2，n)中T,i,的种别而生成传送指令，或将参数的值或将参数的地址传送至新的过程的活动记录的形式单元中。,对于call p,n则:,应生成传送参数个数n的指令；,保护现行SP至新过程的活动记录(老SP)；,转子转向P的第一条指令；,定义新SP；,保护返回地址；,定义新值；,填写display或存取链内容等指令。,含动态数组的过程的操作,应生成对数组进行存储分配的指令，即生成运行时动态地建立内情向量和分配数组空间的目标指令(内情向量表区已分配在过程活动记录中)。这些指令主要完成计算各维的上下界，计算并填好内情向量的所有信息计算所需的数组空间，然后在TOP所指的位置之上留出数组所需空间，将TOP调整为指向数组区的顶端。,在过程执行语句的工作过程中，凡引用形参、局部变量或数组元素都可根据过程活动记录起点的相对位置访问。,过程结束时的处理,当过程P工作完毕要返回到调用段时，若语言有形如return(E)的返回语句，或P是个函数过程时，则可把已算好的值传送至某个特定的寄存器中，调用段将从这个持定的寄存器中获得被调过程的结果值。,然后所生成的目标指令则应完成的工作是：恢复SP；恢复TOP，按保存的返回地址实行无条件转移。,练习（一）,1名字和标识符有什么不同?,2名字的作用域是指什么?,3什么是过程?什么是局部变量?,4分程序是指什么?分程序结构关于名字作用域的规定是什么?,5过程参数的传递方式有几种?简述“传地址”和“传值”的实现原理。,6 下面的程序执行时输出的a分别是什么?若：,(1)参数的传递办法为“传值”；,(2)参数的传递办法为“传地址”。,练习（二）,练习（三）,7举例说明程序设计语言中可变数据项的特点。对这类数据一般采用什么样的存储分配策略，画图示意。,8嵌套层次显示表display的作用是什么？将display表置于过程活动记录中和独立出来各需要如何管理?,9写一过程，功能是在一个链表中插入一个表项，参数为该链表的头的指针。该过程以什么样的参数传递机制工作？,10以display代替静态链完成第2章第2题的要求。,