运行时存储空间的组织和管理教材(PPT 97页)

*,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 运行时存储空间的 组织和管理,编译程序在完成词法、语法和语义分析后，在生成目标代码之前，需要把程序的静态正文和实现这个程序的运行时的活动联系起来弄清楚将来在代码运行时刻，源代码中的各种变量、常量等用户定义的量是如何存放的，如何去访问它们。,在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。在程序语言中，程序使用的存储单元都是由标识符来表示的。它们对应的内存地址都是由编译程序在编译时或由其生成的目标程序运行时进行分配。所以对于编译程序来说存储组织与管理是一个复杂而又十分重要的问题,。,本,章,章,内,内,容,容:,讨,论,论,一,一,个,个,活,活,动,动,记,记,录,录,中,中,的,的,数,数,据,据,安,安,排,排,程序执行,过,过程中，,所,所有活动,记,记录的组,织,织方式,存储器的,组,组织与存,储,储分配的,策,策略,非局部名,称,称的访问,参数传递,6.1,局,局部存储,分,分配策略,过程的每,一,一次运行,称,称为一次活动（activation）,。,。活动是,一,一个动态,的,的概念，,它,它有有限,的,的生存期,。,。,活动的生,存,存期是指从进,入,入活动的,第,第一条指,令,令执行到,离,离开此活,动,动前的最,后,后一条指,令,令执行的,这,这段时间,，,，其中包,括,括调用其,它,它过程时,其,其它活动,的,的生存期,。,。,6.1.2 名字,的,的作用域,和,和绑定,名字的作,用,用域,一个声明,起,起作用的,程,程序部分,称,称为该声,明,明的,作用域。,即使一个,名,名字在程,序,序中只声,明,明一次，,该,该名字在,程,程序运行,时,时也可能,表,表示不同,的,的数据对,象,象。,名字的绑,定,定,运行时为,名,名字X分,配,配存储空,间,间S，这,一,一过程称,为,为绑定,（binding,）,）。,换句话说,，,，绑定是,名,名字X与,存,存储空间S的结合,。,。,X是一个,对,对象,：,既可以是,数,数据对象,，,，如变量,，,，与之结,合,合的是一,个,个存储单,元,元；,也可以是,操,操作对象,，,，如过程,，,，与之结,合,合的是可,执,执行的代,码,码。,我们的讨,论,论仅限于X是一个,数据对象,。,名字的声,明,明与名字,的,的绑定均,需,需要有对,应,应的存储,空,空间，而,存,存储空间,的,的对应方,式,式，一个,是,是静态的,，,，一个是,动,动态的。,声明时关,心,心的是声,明,明的作用,域,域，即当,一,一个名字,被,被引用时,，,，在不同,的,的作用域,中,中与该名,字,字的不同,声,声明结合,；,；,绑定时关,心,心的是绑,定,定的生存,期,期，即当,一,一个名字,在,在运行时,被,被实际分,配,配的存储,单,单元，名,字,字与存储,单,单元结合,的,的这段时,间,间被称为,绑,绑定的生,存,存期，显,然,然此生存,期,期应该和,名,名字的生,存,存期一致,。,。,静 态,动,动 态,过程的定,义,义,过,过程的活,动,动,名字的声,明,明,名,名字的绑,定,定,声明的作,用,用域,绑,绑定的生,存,存期,符号表,活,活动,记,记录,静态与动,态,态,变量与值,的,的两步映,射,射,环境改变,存,存储，状,态,态改变值,。,。,例5.3若有变量,声,声明x:real和常量,声,声明constpi=3.14，,则,则赋值句,中,中变量和,常,常量的映,射,射关系：,常量没有,左,左值（存,储,储空间）,，,，所以不,能,能被赋值,。,。,6.1.3 活,动,动记录,为了管理,过,过程在一,次,次执行中,所,所需要的,信,信息，使,用,用一个连,续,续的存储,块,块，我们,把,把这样的,一,一个连续,存,存储块称,为,为活动纪,录,录。,返 回 值,临 时 数 据,参 数,控 制 链,访 问 链,机 器 状 态,局 部 数 据,返回值,实在参,数,数,控制链,访问链,保存机,器,器状态,局部数,据,据,临时变,量,量,控制链:指向调,用,用过程,活,活动的,活,活动记,录,录。,访问链：指向,本,本活动,要,要访,问的非,局,局部数,据,据所在,的,的活动,记,记录。,保存机,器,器状态：调用,过,过程,活动在,调,调用点,的,的机器,状,状态，,包,包括计,数,数器，,各,各种寄,存,存器的,值,值。,局部数,据,据：过程,中,中定义,的,的,局部量,。,。,临时变,量,量：编译,产,产生。,6.1.4,局,局部数,据,据的安,排,排,字节是,可,可编址,内,内存的,最,最小单,位,位。,6.1.4,局,局部数,据,据的安,排,排,字节是,可,可编址,内,内存的,最,最小单,位,位。,变量所,需,需的存,储,储空间,可,可以根,据,据其类,型,型而静,态,态确定,。,。,6.1.4,局,局部数,据,据的安,排,排,字节是,可,可编址,内,内存的,最,最小单,位,位。,变量所,需,需的存,储,储空间,可,可以根,据,据其类,型,型而静,态,态确定,。,。,一个过,程,程所声,明,明的局,部,部变量,，,，按这,些,些变量,声,声明时,出,出现的,次,次序，,在,在局部,数,数据域,中,中依次,分,分配空,间,间。,6.1.4,局,局部数,据,据的安,排,排,字节是,可,可编址,内,内存的,最,最小单,位,位。,变量所,需,需的存,储,储空间,可,可以根,据,据其类,型,型而静,态,态确定,。,。,一个过,程,程所声,明,明的局,部,部变量,，,，按这,些,些变量,声,声明时,出,出现的,次,次序，,在,在局部,数,数据域,中,中依次,分,分配空,间,间。,局部数,据,据的地,址,址可以,用,用相对,于,于某个,位,位置的,地,地址来,表,表示。,6.1.4,局,局部数,据,据的安,排,排,字节是,可,可编址,内,内存的,最,最小单,位,位。,变量所,需,需的存,储,储空间,可,可以根,据,据其类,型,型而静,态,态确定,。,。,一个过,程,程所声,明,明的局,部,部变量,，,，按这,些,些变量,声,声明时,出,出现的,次,次序，,在,在局部,数,数据域,中,中依次,分,分配空,间,间。,局部数,据,据的地,址,址可以,用,用相对,于,于某个,位,位置的,地,地址来,表,表示。,数据对,象,象的存,储,储安排,还,还有一,个,个对齐,问,问题。,6.1.5程序块,本身含,有,有局部,变,变量声,明,明的语,句,句,可以嵌,套,套,最接近,的,的嵌套,作用域,规,规则,并列程,序,序块不,会,会同时,活,活跃,并列程,序,序块的,变,变量可,以,以重叠,分,分配,main(), /,beginof,B,0,/,inta= 0;,intb= 0;, /,beginof,B,1,/,intb= 1;,/,beginof,B,2,/,inta= 2;,/,endof,B,2,/,/,beginof,B,3,/,intb= 3;,/,endof,B,3,/,/,endof,B,1,/,/,endof,B,0,/,main(), /,beginof,B,0,/,inta= 0;,intb= 0;, /,beginof,B,1,/,intb= 1;,/,beginof,B,2,/,inta= 2;,/,endof,B,2,/,/,beginof,B,3,/,intb= 3;,/,endof,B,3,/,/,endof,B,1,/,/,endof,B,0,/,声,明,作,用,域,int a = 0;,B,0,B,2,int b = 0;,B,0,B,1,int b = 1;,B,1,B,3,int a = 2;,B,2,int b = 3;,B,3,main(), /,beginof,B,0,/,inta= 0;,intb= 0;, /,beginof,B,1,/,intb= 1;,/,beginof,B,2,/,inta= 2;,/,endof,B,2,/,/,beginof,B,3,/,int b= 3;,/,end of,B,3,/,/,end of,B,1,/,/,end of,B,0,/,声,明,作,用,域,int a = 0;,B,0,B,2,int b = 0;,B,0,B,1,int b = 1;,B,1,B,3,int a = 2;,B,2,int b = 3;,B,3,a,0,b,0,b,1,a,2, b,3,重叠分配存储单元,6.2 全,局,局存储分配,策,策略,介绍程序运,行,行时所需的,各,各个活动记,录,录在存储空,间,间的分配策,略,略,6.2 全,局,局存储分配,策,策略,介绍程序运,行,行时所需的,各,各个活动记,录,录在存储空,间,间的分配策,略,略,描述过程的,目,目标代码怎,样,样访问绑定,到,到局部名字,的,的存储单元,6.2 全,局,局存储分配,策,策略,介绍程序运,行,行时所需的,各,各个活动记,录,录在存储空,间,间的分配策,略,略,描述过程的,目,目标代码怎,样,样访问绑定,到,到局部名字,的,的存储单元,介绍三种分,配,配策略,静态分配策,略,略,6.2 全,局,局存储分配,策,策略,介绍程序运,行,行时所需的,各,各个活动记,录,录在存储空,间,间的分配策,略,略,描述过程的,目,目标代码怎,样,样访问绑定,到,到局部名字,的,的存储单元,介绍三种分,配,配策略,静态分配策,略,略,栈式分配策,略,略,6.2 全,局,局存储分配,策,策略,介绍程序运,行,行时所需的,各,各个活动记,录,录在存储空,间,间的分配策,略,略,描述过程的,目,目标代码怎,样,样访问绑定,到,到局部名字,的,的存储单元,介绍三种分,配,配策略,静态分配策,略,略,栈式分配策,略,略,堆式分配策,略,略,静态分配策略在编译,是,是对所有对,象,象分配固定,的,的存储单元,。,。且在运行,是,是保持不变,。,。,栈式动态分,配,配策略在运行时把,存,存储器作为,一,一个栈进行,管,管理，运行,时,时，每当调,用,用一个过程,，,，它所需要,的,的存储空间,就,就动态的分,配,配于栈顶，,一,一旦退出，,它,它所占空间,就,就予以释放,。,。,堆式动态存,储,储策略在运行时把,存,存储器组织,成,成堆结构，,以,以便用户关,于,于存储空间,的,的申请与归,还,还（回收）,，,，凡申请者,分,分给一块，,凡,凡释放者退,回,回给堆。,6.2.1运行时内存,的,的划分,代 码,静 态 数 据,栈,堆,6.2.2,静,静态存储,分,分配,如果在编译,时,时就能够确,定,定一个程序,在,在运行时所,需,需要的存储,空,空间的大小,，,，则在编译,时,时就能够安,排,排好目标程,序,序运行时的,全,全部数据空,间,间，并能确,定,定每个数据,项,项的单元地,址,址。存储空,间,间的这种分,配,配方法叫做静,态,态,分,分,配,配。,特,点,点,：,：绑,定,定,是,是,1,对,对1,的,映,映,射,射,。,。,名,名,字,字,在,在,程,程,序,序,编,编,译,译,时,时,与,与,存,存,储,储,空,空,间,间,结,结,合,合,，,，,每,每,次,次,过,过,程,程,活,活,动,动,时,时,，,，,它,它,的,的,名,名,字,字,映,映,射,射,到,到,同,同,一,一,存,存,储,储,单,单,元,元,。,。,程,程,序,序,运,运,行,行,时,时,不,不,再,再,有,有,对,对,存,存,储,储,空,空,间,间,的,的,分,分,配,配,。,。,静,态,态,分,分,配,配,的,的,限,限,制,制,：,：,数,数,据,据,对,对,象,象,的,的,大,大,小,小,和,和,它,它,在,在,内,内,存,存,中,中,位,位,置,置,的,的,限,限,制,制,必,必,须,须,在,在,编,编,译,译,时,时,确,确,定,定,，,，,如,如,数,数,组,组,的,的,大,大,小,小,不,不,能,能,是,是,动,动,态,态,的,的,；,；,不,不,允,允,许,许,程,程,序,序,递,递,归,归,，,，,因,因,为,为,一,一,个,个,过,过,程,程,的,的,所,所,有,有,活,活,动,动,使,使,用,用,同,同,样,样,的,的,名,名,字,字,绑,绑,定,定,，,，,即,即,绑,绑,定,定,是,是,一,一,对,对,一,一,的,的,；,；,不,不,能,能,动,动,态,态,生,生,成,成,或,或,撤,撤,消,消,数,数,据,据,，,，,因,因,为,为,运,运,行,行,时,时,没,没,有,有,存,存,储,储,分,分,配,配,机,机,制,制,。,。,完,全,全,采,采,用,用,静,静,态,态,分,分,配,配,的,的,语,语,言,言,：,：,早,早,期,期,的,的FORTRAN,。,。,允,许,许,分,分,别,别,编,编,译,译,的,的,数,数,据,据,定,定,义,义,模,模,块,块,（,（,如,如,全,全,程,程,引,引,用,用,的,的,数,数,据,据,）,）,，,，,也,也,可,可,以,以,采,采,用,用,静,静,态,态,分,分,配,配,，,，,因,因,为,为,它,它,们,们,一,一,般,般,在,在,整,整,个,个,程,程,序,序,运,运,行,行,的,的,期,期,间,间,是,是,被,被,共,共,享,享,的,的,。,。,6.2.3,栈,栈,式,式,存,存,储,储,分,分,配,配,存,储,储,空,空,间,间,被,被,组,组,织,织,成,成,栈,栈,，,，,活,活,动,动,记,记,录,录,的,的,推,推,入,入,和,和,弹,弹,出,出,分,分,别,别,对,对,应,应,于,于,活,活,动,动,的,的,开,开,始,始,和,和,结,结,束,束,。,。,与,静,静,态,态,分,分,配,配,不,不,同,同,的,的,是,是，,在,在,每,每,次,次,活,活,动,动,中,中,把,把,局,局,部,部,名,名,字,字,和,和,新,新,的,的,存,存,储,储,单,单,元,元,绑,绑,定,定,，,，,在,在,活,活,动,动,结,结,束,束,时,时,，,，,活,活,动,动,记,记,录,录,从,从,栈,栈,中,中,弹,弹,出,出,，,，,因,因,而,而,局,局,部,部,名,名,字,字,的,的,存,存,储,储,空,空,间,间,也,也,随,随,之,之,消,消,失,失,。,。,6.2.3 栈,式,式分配,活动树:用树来,描,描绘控制进入和,离,离开活动的方式,s,q(1,9),r,p(1,9),q(1,3),q(1,0),p(1,3),q(2,3),q(2,1),q(3,3),p(2,3),q(5,9),q(5,5),p(5,9),q(7,9),q(7,7),q(9,9),p(7,9),活动树的特点：,每个结点代表某,过,过程的一个活动,根结点代表主程,序,序的活动,结点,a,是结点,b,的父结点，当且,仅,仅当控制流从,a,的活动进入,b,的活动,结点,a,处于结点,b,的左边，当且仅,当,当,a,的生存期先于,b,的生存期,活动树上各节点,之,之间具有下述关,系,系：,同一层次的活动,生,生存期不交；,任一时刻，处在,生,生存期的活动构,成,成一条从根到某,节,节 点的路径,；,；,路径上各节点生,存,存期是嵌套的（,后,后进先出）。,当前活跃着的过,程,程活动可以保存,在,在一个栈中,控制栈的内容：s, q (1, 9), q(1, 3), q (2,3),s,q(1,9),r,p(1,9),q(1,3),q(1,0),p(1,3),q(2,3),q(2,1),q(3,3),p(2,3),q(5,9),q(5,5),p(5,9),q(7,9),q(7,7),q(9,9),p(7,9),运行栈：,把控制栈中的信,息,息拓广到包括过,程,程活动所需的所,有,有局部信息（即,活,活动记录）,运行栈：,把控制栈中的信,息,息拓广到包括过,程,程活动所需的所,有,有局部信息（即,活,活动记录）,s,a : array,s,运行栈：,把控制栈中的信,息,息拓广到包括过,程,程活动所需的所,有,有局部信息（即,活,活动记录）,s,i: integer,r,a : array,s,r,运行栈：,把控制栈中的信,息,息拓广到包括过,程,程活动所需的所,有,有局部信息（即,活,活动记录）,s,k: integer,q (1, 9),a : array,s,q(1,9),r,运行栈：把控制栈中的信,息,息拓广到包括过,程,程活动所需的所,有,有局部信息（即,活,活动记录）,s,k: integer,q (1, 9),a : array,q (1, 3),k: integer,s,q(1,9),r,p(1,9),q(1,3),q(1,0),p(1,3),过程调用和过程,返,返回都需要执行,一,一些代码来管理,活,活动记录栈，保,存,存或恢复机器状,态,态等,过程调用和过程,返,返回都需要执行,一,一些代码来管理,活,活动记录栈，保,存,存或恢复机器状,态,态等,过程调用序列,过程调用时执行,的,的分配活动记录,，,，把信息填入它,的,的域中的代码,过程调用和过程,返,返回都需要执行,一,一些代码来管理,活,活动记录栈，保,存,存或恢复机器状,态,态等,过程调用序列,过程调用时执行,的,的分配活动记录,，,，把信息填入它,的,的域中的代码,过程返回序列,过程返回时执行,的,的恢复机器状态,，,，释放活动记录,，,，使调用过程能,够,够继续执行的代,码,码,过程调用和过程,返,返回都需要执行,一,一些代码来管理,活,活动记录栈，保,存,存或恢复机器状,态,态等,过程调用序列,过程调用时执行,的,的分配活动记录,，,，把信息填入它,的,的域中的代码,过程返回序列,过程返回时执行,的,的恢复机器状态,，,，释放活动记录,，,，使调用过程能,够,够继续执行的代,码,码,调用序列和返回,序,序列常常都分成,两,两部分，分处于,调,调用过程和被调,用,用过程中,调用者和被调用,者,者之间的任务划,分,分,返回值和参数,控制链,访问链和机器状态,局部数据临时数据,返回值和参数,局部数据临时数据,控制链,访问链和机器状态,top_sp,base_sp,被调用者的责任,调用者的责任,被调用者的活动记录,调用者的,活动记录,栈,过程,p,调用过程,q,的调用序列,p计算实参，依,次,次放入栈顶，并,在,在栈顶留出放返,回,回值的空间。,top,_,sp,的值在此过程中,被,被改变,p把返回地址和,当,当前,base,_,sp,的值存入q的活,动,动记录中，建立q的访问链，增,加,加,base,_,sp,的值,q,保存寄存器的值,和,和其它机器状态,信,信息,q,根据局部数据域,和,和临时数据域的,大,大小增加,top,_,sp,的值，初始化它,的,的局部数据，并,开,开始执行过程体,调用者和被调用,者,者之间的任务划,分,分,返回值和参数,控制链,访问链和机器状态,局部数据临时数据,返回值和参数,局部数据临时数据,控制链,访问链和机器状态,top_sp,base_sp,被调用者的责任,调用者的责任,被调用者的活动记录,调用者的,活动记录,栈,过程,p,调用过程,q,的返回序列,q,把返回值置入邻,近,近,p,的活动记录的地,方,方,q,对应调用序列的,步,步骤（,4,），减小,top,_,sp,的值,q,恢复寄存器（包,括,括,base,_,sp,）和机器状态，,返,返回,p,p根据参数个数,与类型和返回值,类,类型,调整,top,_,sp,，然后取出返回,值,值,调用者和被调用,者,者之间的任务划,分,分,返回值和参数,控制链,访问链和机器状态,局部数据临时数据,返回值和参数,局部数据临时数据,控制链,访问链和机器状态,top_sp,base_sp,被调用者的责任,调用者的责任,被调用者的活动记录,调用者的,活动记录,栈,过程的参数个数,可,可变的情况,函数返回值改成,用,用寄存器传递,编译器产生将这,些,些参数逆序进栈,的,的代码,被调用函数能准,确,确地知道第一个,参,参数的位置,被调用函数根据,第,第一个参数到栈,中,中取第二、第三,个,个参数等等,调用者和被调用,者,者之间的任务划,分,分,返回值和参数,控制链,访问链和机器状态,局部数据临时数据,返回值和参数,局部数据临时数据,控制链,访问链和机器状态,top_sp,base_sp,被调用者的责任,调用者的责任,被调用者的活动记录,调用者的,活动记录,栈,活动记录的长度,在,在编译时不能确,定,定的情况,局部数组的大小,要,要等到过程激活,时,时才能确定,在活动记录中为,这,这样的数组分别,存,存放数组指针的,单,单元,运行时，这些指,针,针指向分配在栈,顶,顶的存储空间,访问动态分配的数组,q的数组,q的活动记录,p的数组,控制链,top_sp,base_sp,p的活动记录,数组A的指针,数组B的指针,数组A,数组B,控制链,悬空引用：,引用某个已被释,放,放的存储单元,悬空引用：,引用某个已被释,放,放的存储单元,main()|int,dangle( ),|,int,q;|int j =20;,q = dangle ( );|return ,|,6.3.3 堆,式,式存储分配,1局部名的值,在,在活动结束时必,须,须被保存。2. 被调用者,的,的活动生存期超,过,过调用者。,用活动树不能够,正,正确描绘这种语,言,言的过,程之,间,间的,控,控制,流,流。,new(p);,dispose(p);,6.3,非,非局,部,部名,字,字的,访,访问,本节,介,介绍,无过,程,程嵌,套,套的,静,静态,作,作用,域,域（C语,言,言）,有过,程,程嵌,套,套的,静,静态,作,作用,域,域（Pascal,语,语言,）,）,动态,作,作用,域,域（Lisp,语,语言,）,）,6.3.1,无过,程,程嵌,套,套的,静,静态,作,作用,域,域,过程,体,体中,的,的非,局,局部,引,引用,可,可以,直,直接,使,使用,静,静态,确,确定,的,的地,址,址,局部,变,变量,在,在栈,顶,顶的,活,活动,记,记录,中,中，,可,可以,通,通过,base,_,sp,指针,来,来访,问,问,无须,深,深入,栈,栈中,取,取数,据,据，,无,无须,访,访问,链,链,过程,可,可以,作,作为,参,参数,来,来传,递,递，,也,也可,以,以作,为,为结,果,果来,返,返回,6.3.2有过,程,程嵌,套,套的,静,静态,作,作用,域,域,过程,嵌套,深,深度,sort1,readarray2,exchange2,quicksort2,partition3,6.3.2有过,程,程嵌,套,套的,静,静态,作,作用,域,域,过程,嵌套,深,深度,sort1,readarray2,exchange2,quicksort2,partition3,变量,的,的嵌,套,套深,度,度：,它,它的,声,声明,所,所在,过,过程,的,的嵌,套,套深,度,度作,为,为该,名,名字,的,的嵌,套,套深,度,度,6.3,非局,部,部名,字,字的,访,访问,寻找,非,非局,部,部名,字,字存,储,储单,元,元的,访,访问,链,链,s,a, x,q (1, 9),k, v,访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,p (1, 3),i, j,访问链,e (1, 3),访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,p (1, 3),i, j,访问链,6.3,非局,部,部名,字,字的,访,访问,假定,过,过程p的,嵌,嵌套,深,深度,为,为,n,p,，它引用嵌,套,套深度为,n,a,的变量a，,n,a,n,p,。如何访问a的存储单,元,元？,sort1,readarray2,exchange2,quicksort2,partition3,6.3,非局部名字,的,的访问,假定过程p,的,的嵌套深度,为,为,n,p,，它引用嵌,套,套深度为,n,a,的变量a，,n,a,n,p,。如何访问a的存储单,元,元？,从栈顶的活,动,动记录开始,，,，追踪访问,链,链,n,p,n,a,次。,6.3,非局部名字,的,的访问,假定过程p,的,的嵌套深度,为,为,n,p,，它引用嵌,套,套深度为,n,a,的变量a，,n,a,n,p,。如何访问a的存储单,元,元？,从栈顶的活,动,动记录开始,，,，追踪访问,链,链,n,p,n,a,次。,到达,a,的声明所在,过,过程的活动,记,记录。,6.3,非局部名字,的,的访问,假定过程p,的,的嵌套深度,为,为,n,p,，它引用嵌,套,套深度为,n,a,的变量a，,n,a,n,p,。如何访问a的存储单,元,元？,从栈顶的活,动,动记录开始,，,，追踪访问,链,链,n,p,n,a,次。,到达,a,的声明所在,过,过程的活动,记,记录。,访问链的追,踪,踪用间接操,作,作就可完成,。,。,6.3,非局部名字,的,的访问,访问非局部,名,名字的存储,单,单元,s,a, x,q (1, 9),k, v,访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,p (1, 3),i, j,访问链,e (1, 3),访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,p (1, 3),i, j,访问链,sort,readarray,exchange,quicksort,partition,6.3,非局部名字,的,的访问,过程,p,对变量,a,访问时，,a,的地址由下,面,面的二元组,表,表示：,（,n,p,n,a,，,a,在活动记录,中,中的偏移）,6.3,非局部名字,的,的访问,建立访问链,假定嵌套深,度,度为,n,p,的过程,p,调用嵌套深,度,度为,n,x,的,过程,x,n,p,n,x,的情况,sort1,readarray2,exchange2,quicksort2,partition3,6.3,非局部名字,的,的访问,建立访问链,假定嵌套深,度,度为,n,p,的过程,p,调用嵌套深,度,度为,n,x,的,过程,x,n,p,n,x,的情况,x肯定就声,明,明在p中,6.3,非局部名字,的,的访问,建立访问链,假定嵌套深,度,度为,n,p,的过程,p,调用嵌套深,度,度为,n,x,的,过程,x,n,p,n,x,的情况,x肯定就声,明,明在p中,被调用过程,的,的访问链必,须,须指向调用,过,过程的活动,记,记录的访问,链,链,6.3,非局部名字,的,的访问,建立访问链,s,a, x,q (1, 9),k, v,访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,p (1, 3),i, j,访问链,e (1, 3),访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,p (1, 3),i, j,访问链,sort,readarray,exchange,quicksort,partition,6.3,非局部名字,的,的访问,建立访问链,假定嵌套深,度,度为,n,p,的过程,p,调用嵌套深,度,度为,n,x,的,过程,x,n,p,n,x,的情况,sort1,readarray2,exchange2,quicksort2,partition3,6.3,非局部名字,的,的访问,建立访问链,假定嵌套深,度,度为,n,p,的过程,p,调用嵌套深,度,度为,n,x,的,过程,x,n,p,n,x,的情况,p和x,的嵌套深度,分,分别为,1，2,，,n,x,1,的外围过程,肯,肯定相同,6.3,非局部名字,的,的访问,建立访问链,假定嵌套深,度,度为,n,p,的过程,p,调用嵌套深,度,度为,n,x,的,过程,x,n,p,n,x,的情况,p和x,的嵌套深度,分,分别为,1,，,2,，,n,x,1,的外围,过,过程肯,定,定相同,追踪访,问,问链,n,p,n,x,+ 1,次，到,达,达了静,态,态包围,x和p,的且离,它,它们最,近,近的那,个,个过程,的,的最新,活,活动记,录,录,6.3,非局部,名,名字的,访,访问,建立访,问,问链,假定嵌,套,套深度,为,为,n,p,的过程,p,调用嵌,套,套深度,为,为,n,x,的,过程,x,n,p,n,x,的情况,p和x,的嵌套,深,深度分,别,别为,1，2,，,，,n,x,1,的外围,过,过程肯,定,定相同,追踪访,问,问链,n,p,n,x,+ 1,次，到,达,达了静,态,态包围,x和p,的且离,它,它们最,近,近的那,个,个过程,的,的最新,活,活动记,录,录,所到达,的,的访问,链,链就是,x,的活动,记,记录中,的,的访问,链,链应该,指,指向的,那,那个访,问,问链,6.3,非局部,名,名字的,访,访问,建立访,问,问链,s,a, x,q (1, 9),k, v,访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,p (1, 3),i, j,访问链,e (1, 3),访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,p (1, 3),i, j,访问链,sort,readarray,exchange,quicksort,partition,6.3,非局部,名,名字的,访,访问,program param(input,output);（,过,过程作,为,为参数,）,）,procedureb(functionh(n: integer):integer);,beginwriteln(h(2) endb;,procedurec;,varm:integer;,functionf(n: integer):integer;,beginf := m+nendf;,beginm := 0; b(f)end c;,begin,c,end.,6.3,非局部,名,名字的,访,访问,program param(input,output);（,过,过程作,为,为参数,）,）,procedureb(functionh(n: integer):integer);,beginwriteln(h(2) endb;,procedurec;,varm:integer;,functionf(n: integer):integer;,beginf := m+nendf;,beginm := 0; b(f)end c;,begin,c,end.,过程作,为,为参数,传,传递时,，,，怎样,在,在该过,程,程被激,活,活时建,立,立它的,访,访问链,。,。,6.3,非局部,名,名字的,访,访问,program param(input,output);（,过,过程作,为,为参数,）,）,procedureb(functionh(n: integer):integer);,beginwriteln(h(2) endb;,procedurec;,varm:integer;,functionf(n: integer):integer;,beginf := m+nendf;,beginm := 0; b(f)end c;,begin,c,end.,过程作,为,为参数,传,传递时,，,，怎样,在,在该过,程,程被激,活,活时建,立,立它的,访,访问链,从,b,的访问,链,链难以,建,建立,f,的访问,链,链,6.3,非局部,名,名字的,访,访问,program param(input,output);（,过,过程作,为,为参数,）,）,procedureb(functionh(,beginwriteln(h(2) end;,procedurec;,varm:integer;,functionf(n: integer),beginf := m+nendf;,beginm := 0; b(f)end c;,begin,c,end.,访 问 链,访 问 链,param,c,m,b,6.3,非局部,名,名字的,访,访问,program ret(input, output);（过,程,程作为,返,返回值,）,）,varf:function(integer):integer;,functiona:function(integer): integer;,varm:integer;,functionaddm (n:integer):integer;,beginreturnm+n end;,beginm:=0;return addmend;,procedureb(g:function(integer):integer);,beginwriteln (g(2)end;,begin,f := a; b(f),end.,6.3,非局部名字的,访,访问,program ret(input, output);（过,程,程作为返回值,）,）,var f:function (integer): integer;,function a:function (integer): integer;,var m:integer;,function addm (n:integer): integer;,beginreturnm+n end;,beginm:= 0;return addmend;,procedure b(g: function(integer):integer);,beginwriteln ( g(2) end;,begin,f := a; b(f),end.,ret,a,b,addm,6.3,非局部名字的,访,访问,C,语言的函数声,明,明不能嵌套，,函,函数不论在什,么,么情况下激活,，,，要访问的数,据,据分成两种情,况,况:,非静态局部变,量,量（包括形式,参,参数），它们,分,分配在活动记,录,录栈顶的那个,活,活动记录中,外部变量（包,括,括定义在其它,源,源文件中的外,部,部变量）和静,态,态的局部变量,，,，它们都分配,在,在静态数据区,6.3,非局部名字的,访,访问,6.3.3动态作用域,被调用过程的,非,非局部名字,a,和它在调用过,程,程中引用的是,同,同样的存储单,元,元。,6.3,非局部名字的,访,访问,6.3.3动态作用域,被调用过程的,非,非局部名字,a,和它在调用过,程,程中引用的是,同,同样的存储单,元,元。,新的绑定仅为,被,被调用过程的,局,局部名字建立,，,，这些名字在,被,被调用过程的,活,活动记录中占,用,用的存储单元,。,。,6.3,非局部名字的,访,访问,program dynamic(input, output);,var r:real;,procedure show;,beginwrite(r: 5:3) end;,procedure small;,var r:real;,beginr := 0.125;show end;,begin,r := 0.25;,show;small;writeln;,show;small;writeln,end.,6.3,非局部名字的,访,访问,program dynamic(input, output);,var r:real;,procedure show;,beginwrite(r: 5:3) end;,procedure small;,var r:real;,beginr := 0.125;show end;,begin,r := 0.25;,show;small;writeln;,show;small;writeln,end.,dynamic,show,small,small,show,show,show,6.3,非局部名字的,访,访问,program dynamic(input, output);,var r:real;,procedure show;,beginwrite(r: 5:3) end;,procedure small;,var r:real;,beginr := 0.125;show end;,begin,静态作用域,r := 0.25;0.2500.250,show;small;writeln;0.2500.250,show;small;writeln,end.,dynamic,show,small,small,show,show,show,6.3,非局部名字的,访,访问,program dynamic(input, output);,var r:real;,procedure show;,beginwrite(r: 5:3) end;,procedure small;,var r:real;,beginr := 0.125;show end;,begin,动,动,态作用域,r := 0.25;0.250 0.125,show;small;writeln;0.2500.125,show;small;writeln,end.,dynamic,show,small,small,show,show,show,6.3,非局部名字,的,的访问,实现动态作,用,用域的方法,深访问,用控制链搜,索,索运行栈，,寻,寻找包含该,非,非局部名字,的,的第一个活,动,动记录,浅访问,为每个名字,在,在静态分配,的,的存储空间,中,中保存它的,当,当前值,当,过程p的新,活,活动出现时,，,，p的局部,名,名字,n,使用在静态,数,数据区分配,给,给,n,的存储单元,。,。,n,的先前值可,以,以保存在p,的,的活动记录,中,中，当p的,活,活动结束时,再,再恢复,6.4,参 数 传,递,递,6.4.1,值,值调用,实参的右值,传,传给被调用,过,过程,值调用可以,如,如下实现,把形参当作,所,所在过程的,局,局部名看待,，,，形参的存,储,储单元在该,过,过程的活动,记,记录中。,6.4,参 数 传,递,递,6.4.1,值,值调用,实参的右值,传,传给被调用,过,过程,值调用可以,如,如下实现,把形参当作,所,所在过程的,局,局部名看待,，,，形参的存,储,储单元在该,过,过程的活动,记,记录中。,调用过程计,算,算实参，并,把,把右值放入,形,形参的存储,单,单元中。,6.4,参 数 传,递,递,6.4.2,引,引用调用,实参的左值,传,传给被调用,过,过程,引用调用可,以,以如下实现,：,：,把实参的左,值,值放入形参,的,的存储单元,。,。,6.4,参 数 传,递,递,6.4.2,引,引用调用,实参的左值,传,传给被调用,过,过程,引用调用可,以,以如下实现,：,：,把实参的左,值,值放入形参,的,的存储单元,。,。,在被调用过,程,程的目标代,码,码中，任何,对,对形参的引,用,用都是通过,传,传给该过程,的,的指针来间,接,接引用实参,的,的。,6.4,参 数 传,递,递,6.4.3,复写-恢复,调,调用,值调用和引,用,用调用的混,合,合,复写-恢复,调用可以如,下,下实现：,实参的右值,和,和左值同时,传,传给被调用,过,过程。,6.4,参 数 传,递,递,6.4.3,复写-恢复,调,调用,值调用和引,用,用调用的混,合,合,复写-恢复,调用可以如,下,下实现：,实参的右值,和,和左值同时,传,传给被调用,过,过程。,在被调用过,程,程中，像值,调,调用那样使,用,用实参的右,值,值。,6.4,参 数 传,递,递,6.4.3,复写-恢复,调,调用,值调用和引,用,用调用的混,合,合,复写-恢复,调用可以如,下,下实现：,实参的右值,和,和左值同时,传,传给被调用,过,过程。,在被调用过,程,程中，像值,调,调用那样使,用,用实参的右,值,值。,当控制返回,调,调用过程时,，,，根据传递,来,来的实参的,左,左值，将形,参,参当前的值,复,复写到实参,存,存储单元。,6.4,参 数 传,递,递,6.4.4,换,换名调用,用实参表达,式,式对形参进,行,行正文替换,。,。,procedureswap(var x, y:integer);,var temp:integer;,begin,temp:= x;,x :=y;,y :=temp,end,6.4,参 数 传,递,递,6.4.4,换,换名调用,用实参表达,式,式对形参进,行,行正文替换,。,。,procedureswap(var x, y:integer);,var temp:integer;,begin,调用,swap(i, ai),temp:= x;,x :=y;,y :=temp,end,6.4,参 数 传,递,递,6.4.4,换,换名调用,用实参表达,式,式对形参进,行,行正文替换,。,。,procedureswap(var x, y:integer);,var temp:integer;,begin,调用,swap(i, ai),temp:= x;temp:= i;,x :=y;i :=ai;,y :=tempai:= temp,end,本 章,要,要 点,影响存储分,配,配策略的语,言,言特征,各种存储分,配,配策略，主,要,要了解静态,分,分配和动态,栈,栈式分配,活动记录中,各,各种数据域,的,的作用和安,排,排,非局部数据,访,访问的实现,方,方法,各种参数传,递,递方式及其,实,实现,