北大编译原理讲义chapter61

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第六章 运行时刻环境,序,6.1 源语言中的一些问题,6.2 存储组织,6.3 运行时刻存储分配策略,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 ： array0.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 （4CHARACTER C，PRDUCE （5）DATA NEXT1，BUF/ / （6）CPRDUCE（）。 （7）BUF（NEXT：NEXT）C （8NEXTNEXT1 （9）IF（C.NE. )GOTO 6 （10）WRITE（*，(A)）BUF （11） END,29,(12）CHARACTER FUNCTION PRDUCE（）,（13)CHARACTER * 80 BUFFER （14）INTEGER NEXT （15）SAVE BUFFER，NEXT (16) DATA NEXT81 （17）IF(NEXT.GT.80）THEN （18)READ（*，（A)BUFFER,（19）NEXT1 （20) END IF （21）PRDUCEBUFFER（NEXT：NEXT） （22 ) NEXTNEXT1 （23)END,图6.8 一个,Fortran 77,程序,30,CNSUME,目标代码,PRDUCE,目标代码,Char *50 buf,int next,char c,Char *80 buffer,int next,Cnsume,活动记录,prduce,活动记录,目标代码,静态数据,31,6.3.2 栈式存储分配,基于控制栈的原理：存储空间被组织成栈，活动记录的推人和弹出分别对应于活动的开始和结束。,与静态分配不同的是，在每次活动中把局部名字和新的存储单元绑定，在活动结束时，活动记录从栈中弹出，因而局部名字的存储空间也随之消失。,例6.5 图6.11表明当控制流通过图6.3的活动树时活动记录被推人或弹出运行时刻的栈中的情况，设寄存器,top,标记栈顶。,32,s,S,a:array,top,r,r,i:integer,top,top,q(1,9),q(1,9),i:integer,top,p(1,9),p(1,9),i:integer,top,top,q(1,3),q(1,3),i:integer,top,图 6.11 栈式分配活动记录在栈中的变化,33,确定活动记录中局部数据的地址：假设,top-sp,标记一个活动记录的开始的位置，,dx,表,示,x,的地址相对于,top-sp,的偏移量。那么，,x,在,过程的目标代码中的地址可写成,dx（top-sp）,在运行时刻，当把,x,的活动记录筑于栈顶时，寄,存器,top- sp,被赋于实际的地址，,top- sp,可以是,一个寄存器。,调用序列和返回序列,通过在目标代码中生成调用序列和返回序列,实现过程的调用,。,激活一个过程的活动是执行,34,过程语句的结果。过程语句,p(e,1,e,2,e,n,),的目标代码（调用序列）完成任务：,1. 调用者对实在参数求值，并把它们传送给,被调用过程的活动记录的参数域。 2调用者在被调用者的活动记录中存放返,回地址和老,top-sp,之值。之后调用者把,top,一,sp,之值增加到图6.12所示的位置。 3被调用者存放寄存器值和其它状态信息。 4被调用者初始化其局部数据并开始执行。,35,返回序列，,return,目标代码完成的任务是： 1被调用者在自己的活动记录的返回值域,中放一个返回值。 2利用状态域中的信息，被调用者恢复,top,-,sp,和其它寄存器，并且按返回地址转,移到调用者的代码之中。 3调用者复制返回值到自己的活动记录中。,任务的划分，根据源语言、目标机器和操,作系统等具体情况而定。,上述任务，由运行支持子程序完成，可视为虚机指令。,36,可变长度的数据,源程序的例子,PROCEDURE exam(l,m,n:integer);,VAR,a:array 1.l of real;,b:array 1.m of real;,c:array 1.n of real;,BEGIN,END;,编译时，不知 a,b,c,的,大小，仅对每个数组设置一个指针。,37,Control link,a,b,c,Top-sp,top,Array a,Array b,Array c,top,P,的活动记录,P,的动态数组,图6.13,动态分配的数组,38,活动记录的进栈和推栈,栈顶活动记录用两个指针top和,top-sp,指示。,top-sp,指向栈顶活动记录保存机器状态域的末,端，用于访问局部数据。,top指向栈顶。,P调用q：,栈top+h:=top-sp;,top-sp:=top+h;,top:=top+q的活动记录长度,从,q,的活动返回：,top:=top-spq (h),top-sp:=栈top-sp,39,p,q,top-sp,top-sp,top,top,h,40,6.3.3 堆式存储分配,1局部名的值在活动结束时必须被保存。 2. 被调用者的活动生存期超过调用者。,用活动树不能够正确描绘这种语言的过,程之间的控制流。,new(p);,dispose(p);,41,