北大编译原理讲义chapter6_1

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第六章 运行时刻环境,序,6.1 源语言中的一些问题,6.2 存储组织,6.3 运行时刻存储分配策略,6.4 非局部名字的访问,6.5 参数传递,6.6 符号表,1,序,计算环境 运行时的环境,计算 目标代码,源程序中的名字（常量，变量）,目标机存储空间。它受命于源程序的执行语义。,源程序由一组过程按某种规则组成。过程的一次执行称作一次活动，在过程的语句序列执行之前，过程中访问的对象构成此过程的运行环境，由运行支持程序组织好。编译程序根据如何组织运行环境而生成目标代码。,映射,源程序,2,6.1有关源程序中的一些问题,目的：,构造运行程序的策略和方法,6.1.1,过程,6.1.2 活动树,6.1.3 控制栈,6.1.4 说明的作用域,6.1.5 名字的绑定,6.1.6 构造运行程序和源程序有关的,一些问题,3,6.1.1,过程,源程序由一组,过程组成，不同的程序设计语言，,由,过程构成,源程序的方法不同。,构成,源程序,的,两个,过程行文，要么是嵌套的，要么是不相交的。,4,program sort,（,input,，,output,）；,var,a,：,array,0.10 of integer,；,procedure,readarray,；,var,i,：,integer,；,begin,end,；,function partition,（,y,，,z,：,integer,）,:integer,；,var,i,，,j,，,x,，,v,：,integer,；,begin,end;,procedure,quicksort,（,m,，,n,：,integer,）；,var,i,：,integer,；,begin,end,end,；,begin,end,.,5,6.1.2,活动树,程序执行期间的控制流：,1,程序执行的控制是顺序的；,2,过程的每一次执行都是从过程体的开头,开始，并最终把控制返回到紧接着该过,程被调用点的后面。,过程的一次活动:过程体的每一次执行。,一个过程,p,的一次活动的生存期:在该过程体的执行中的第一步和最后一步之间的一序列步骤的执行时间，其中包括执行过程,p,所调用的过程的执行时间，以及这些过程所调用的过程的执行时间,，,如此等等。,6,特点：,每当控制流从过程,p,的活动进入到过程,q,的,活动中后，它将返回到过程,p,的同一次活动,中。如果,a,和,b,是两个过程活动，那么它们的生,存期要么是不重叠的，要么是嵌套的。,这种活动生存期的嵌套性质可以通过在每,一个过程中插入两个打印语句来加以说明。,7,执行开始,enter,readarray,leave,readarray,enter,quicksort,（,1,，,9,）,enter partition,（,1,，,9,）,leave partition,（,l,，,9,）,enter,quicksort,（,1,，,3,）,.leave,quicksort,（,1,，,3),enter,quicksort,（,5,，,9,）,.leave,quicksort,（,5,，,9,）,leave,quicksort,（,1,，,9,）,执行结束,8,一个过程是递归的，如果同一过程的一次新的活动可以在前面活动结束以前开始。,用一颗树来描绘控制进入和离开活动的途径。这祥的树称作活动树。在一棵活动树中：,1.,每一个结点代表一个过程的活动,;2.,根结点代表主程序的活动,;3.,代表,a,的结点是,b,结点的父结点当且仅当控,制从活动,a,进入活动,b;4.,结点,a,在结点,b,的左边当且仅当,a,的生存期,发生在,b,的生存期之前。,用活动树来讨论正在这个结点上的控制,。,9,s,r,q(1,9),p(1,9),q(1,3),p(1,3),q(1,0),q(2,3),p(2,3),q(2,1),q(3,3),q(5,9),p(5,9),q(5,5),q(7,9),p(7,9),q(7,7),图,6.3 一棵活动树,10,结论：一个结点代表一个唯一的活动，且每,一个活动只有一个结点表示，当控制进,入某一个活动时，可以直接说，控制在,这个结点上。,6.1.3 控制栈,程序执行的控制流对应于从根开始，按先根次序遍历活动树。因此，用一个栈保存过程活动的生存踪迹。把它称作控制栈。,当一个活动开始执行时，把代表这个活动的结点推进栈；当这个活动结束时，把代表这个活动的结点从栈中弹出。,11,例,6.2 栈和活动树的变化,栈,s,s,r,S r,q(1,9),S q(1.9),p(1,9),S q(1.9)p(1,9),q(1,3),S q(1.9)q(1,3),p(1,3),S q(1.9)q(1,3)p(1,3),q(1,0),S q(1.9)q(1,3)q(1,0),q(2,3),S q(1.9)q(1,3)q(2,3),图 6.4,12,控制栈中的活动都是活跃的，当前控制进入的活动在栈顶，从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的,结点序列：,s,q,（,1,，,9,），,q,（,l,，,3,），,q,（,2,，,3,）,从栈底活动到栈顶活动的活动序列表示了活动的生存期的嵌套关系。,结论,：扩充控制栈可用来实现如,Pascal,语言的栈式存储分配，进入一个活动，在栈顶建立这个活动所使用的存储空间；这个活动结束，从栈顶弹出其使用的存储空间。,13,6.1.4,说明的作用域,1,.,说,明,把名字与名字的属性信息绑定在一起。,2,.,说明的作用域是一个说明起作用的范围,（源程序行文）。一个名字在源程序行文中,可能有几处说明，语言的作用域规则规定：,在语句序列中引用的一个名字是在何处说,明的名字。,3,.,编译时，处理说明把名字及其属性信息填,写进符号表(,add(id.entry,id.,vul,);,处理引用,名字时，查找这个名字的属性信息,（,lookup(id),符号表管理程序根据语 言的,作用域规则，使,lookup(id),返,回,id,的,作,用域,中绑定的属性信息。,14,6.1.5,名字与存储的绑定,名字与存储单元的绑定是指把源程序中的数据名字映射到目标机存储单元的过程。,引进两个函数，,environment,和,state,。,environment,把名字映射到一个存储单元上；,state,把存储单元映射到那里所存放的值上。,可以说，函数,environment,把一个名字映射为一个,l-value,（,左,-,值）,而函数,state,把一个,l-value,（,左,-,值）映射为一个,r-value,（,右,-,值）。如图,6.5,所示。,15,名字,存储单元,值,存储分配,程序运行,environment,state,l-value,r-value,图,6.5 从名字到值的两个阶段映射,16,静态概念 动态对应,过程定义 过程活动,名字说明 名字的绑定,说明的作用域 活动的生存期,17,6.1.6,提出的问题,编译程序组织存储分配所采用策略和方法主要取决于对源程序中下面的问题的回答。,1,过程可以是递归的吗？,2,当控制从过程的一次活动返回时，局部,名的值将发生什么 变化,?3,一个过程可以访问非局部名吗？,4,当调用过程时参数是怎样传递的？,5,过程可以作为参数被传递吗？,6,过程可以作为结果被返回吗？,7.,可以在程序控制下进行动态存储分配吗？,8.,显式的存储重新分配（指撤除分配后的分,配）是必须的吗？,18,例：函数的返回值是函数。,Fun times x y=x*y,val,times=,fn,:,int,(,int,int,),twice=times 2,fun compose(f,g)=f(g(x),compose=,fn,:(,)(),val,fourtimes,=compose(twice,twice),19,6.2,存储组织,6.2.1 运行时刻内存的划分,运行时刻的存储空间必须划分以用来存放:,1.,生成的目标代码;,2.,数据目标;,3,.用于保存过程活动踪迹的一个控制栈。,存储空间划分的各部分：,20,目标代码,静态数据,栈,堆,1.编译后知道目标代,码的大小。,2.,pascal,主程序中的,数据,c,FORTRAN,3.栈:,Pascal,c,4.,堆:,Pascal,c,21,6.2.2,活动记录,把过程的一个活动所需要的信息组织成一块连续的存储单元，称为活动记录。,一个活动所需要的信息的每个数据项有相同的生存期，因此，组织成一个活动记录是很自然的。,对于,pascal,语言来说，运行过程中，当调用一个过程时，在栈顶构筑它的活动记录；当这个过程的活动执行完后，把它从栈顶弹出。,源语言不同，实现方法不同，组成活动记录的域不同。实现,pascal,语言的活动记录如,图6.7所示。,22,返回值,实在参数,控制链,访问链,保存机器状态,局部数据,临时变量,控制链:指向调用过程活动,的活动记录。,访问链：指向本活动要访,问的非局部数据所在的,活动记录。,保存机器状态：调用过程,活动在调用点的机器,状态，包括计数器，,各种寄存器的值。,局部数据：过程中定义的,局部量。,临时变量：编译产生。,23,6.2.3,编译时刻的局部数据的设计,局部数据域是编译时刻在分析过程中的说 明时设计的。例如：,PROCEDURE sub(x,y:real);,VAR,i,j:integer;,a:ARRAY1.5 OF real;,e,f:real;,BEGIN,f:=e+i*j;,END;,24,符号表,名字 形 类型 偏移量,活动记录布局,返回值,(,top-,sp,0),x,形,real 1,(,top-,sp,1),y,形,real 2,(,top-,sp,2),(,top-,sp,3),(,top-,sp,20),i,int,20,(,top-,sp,21),j,int,21,(,top-,sp,22),a,array,22,(,top-,sp,27),e,real,27,(,top-,sp,28),f,real,28,25,中间代码,*,i j t,1,*,(top-,sp,20)(top-,sp,21),(top-,sp,29),+e t,1,t,2,+,(top-,sp,27)(top-,sp,29),(top-,sp,30),itor,t,2,t,3,itor,(top-,sp,30),(top-,sp,31),:=,t,3,f :=,(top-,sp,31),(top-,sp,28),编译结束，知道每个过程的活动记录的长度，将其填写到相应的过程表中，运行时，调用哪个过程，就在运行栈顶，推进那个过程的活动记录（栈箭头加上活动记录长度）。,26,6.3,运行时刻存储分配策略,分配策略是：,1,静态分配；,2,栈式分配，或称栈式动态分配；,3,堆式分配，或称堆式动态分配。,6.3,.,1,静态存储分配,6.3,.,2,栈式存储分配,6.3,.,3,堆式存储分配,采用哪种分配策略是由源语言的语义决定的。,27,6.3,.,1,静态存储分配,在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置，且这种绑定在运行时刻不再发生变化。,局部名字的值在过程活动停止后仍保留下来。,限制：,1.,在编译时刻知道数据目标的大小和它们在,内存位置上 约束；,2.,不能递归调用过程（一个过程的两个活动,的生存期不相交,一个过程的所有活动可以,使用同一个活动记录）；,3.,不能动态地建立数据结构。,28,（1,）,PROGRAM,CNSUME,（,2,）,CHARACTER *50 BUF,（,3,）,INTEGER NEXT,（,4,CHARACTER C,，,PRDUCE,（,5,）,DATA NEXT,1,，,BUF/,（,6,）,C,PRDUCE,（）。（,7,）,BUF,（,NEXT,：,NEXT,