北大编译原理讲义cha.ppt

1,第六章运行时刻环境序6.1源语言中的一些问题6.2存储组织6.3运行时刻存储分配策略6.4非局部名字的访问6.5参数传递6.6符号表,2,序计算环境运行时的环境计算目标代码源程序中的名字（常量，变量）目标机存储空间。它受命于源程序的执行语义。源程序由一组过程按某种规则组成。过程的一次执行称作一次活动，在过程的语句序列执行之前，过程中访问的对象构成此过程的运行环境，由运行支持程序组织好。编译程序根据如何组织运行环境而生成目标代码。,映射,源程序,3,6.1有关源程序中的一些问题目的：构造运行程序的策略和方法6.1.1过程6.1.2活动树6.1.3控制栈6.1.4说明的作用域6.1.5名字的绑定6.1.6构造运行程序和源程序有关的一些问题,4,6.1.1过程源程序由一组过程组成，不同的程序设计语言，由过程构成源程序的方法不同。构成源程序的两个过程行文，要么是嵌套的，要么是不相交的。,5,programsort（input，output）；vara：array0.10ofinteger；procedurereadarray；vari：integer；beginend；functionpartition（y，z：integer）:integer；vari，j，x，v：integer；beginend;procedurequicksort（m，n：integer）；vari：integer；beginendend；beginend.,6,6.1.2活动树程序执行期间的控制流：1程序执行的控制是顺序的；2过程的每一次执行都是从过程体的开头开始，并最终把控制返回到紧接着该过程被调用点的后面。过程的一次活动:过程体的每一次执行。一个过程p的一次活动的生存期:在该过程体的执行中的第一步和最后一步之间的一序列步骤的执行时间，其中包括执行过程p所调用的过程的执行时间，以及这些过程所调用的过程的执行时间，如此等等。,7,特点：每当控制流从过程p的活动进入到过程q的活动中后，它将返回到过程p的同一次活动中。如果a和b是两个过程活动，那么它们的生存期要么是不重叠的，要么是嵌套的。这种活动生存期的嵌套性质可以通过在每一个过程中插入两个打印语句来加以说明。,8,执行开始enterreadarrayleavereadarrayenterquicksort（1，9）enterpartition（1，9）leavepartition（l，9）enterquicksort（1，3）.leavequicksort（1，3)enterquicksort（5，9）.leavequicksort（5，9）leavequicksort（1，9）执行结束,9,一个过程是递归的，如果同一过程的一次新的活动可以在前面活动结束以前开始。用一颗树来描绘控制进入和离开活动的途径。这祥的树称作活动树。在一棵活动树中：1.每一个结点代表一个过程的活动;2.根结点代表主程序的活动;3.代表a的结点是b结点的父结点当且仅当控制从活动a进入活动b;4.结点a在结点b的左边当且仅当a的生存期发生在b的生存期之前。用活动树来讨论正在这个结点上的控制。,10,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一棵活动树,11,结论：一个结点代表一个唯一的活动，且每一个活动只有一个结点表示，当控制进入某一个活动时，可以直接说，控制在这个结点上。6.1.3控制栈程序执行的控制流对应于从根开始，按先根次序遍历活动树。因此，用一个栈保存过程活动的生存踪迹。把它称作控制栈。当一个活动开始执行时，把代表这个活动的结点推进栈；当这个活动结束时，把代表这个活动的结点从栈中弹出。,12,例6.2栈和活动树的变化,栈,s,s,r,Sr,q(1,9),Sq(1.9),p(1,9),Sq(1.9)p(1,9),q(1,3),Sq(1.9)q(1,3),p(1,3),Sq(1.9)q(1,3)p(1,3),q(1,0),Sq(1.9)q(1,3)q(1,0),q(2,3),Sq(1.9)q(1,3)q(2,3),图6.4,13,控制栈中的活动都是活跃的，当前控制进入的活动在栈顶，从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的结点序列：s,q（1，9），q（l，3），q（2，3）从栈底活动到栈顶活动的活动序列表示了活动的生存期的嵌套关系。结论：扩充控制栈可用来实现如Pascal语言的栈式存储分配，进入一个活动，在栈顶建立这个活动所使用的存储空间；这个活动结束，从栈顶弹出其使用的存储空间。,14,6.1.4说明的作用域1.说明把名字与名字的属性信息绑定在一起。2.说明的作用域是一个说明起作用的范围（源程序行文）。一个名字在源程序行文中可能有几处说明，语言的作用域规则规定：在语句序列中引用的一个名字是在何处说明的名字。3.编译时，处理说明把名字及其属性信息填写进符号表(add(id.entry,id.vul);处理引用名字时，查找这个名字的属性信息（lookup(id),符号表管理程序根据语言的作用域规则，使lookup(id)返回id的作用域中绑定的属性信息。,15,6.1.5名字与存储的绑定名字与存储单元的绑定是指把源程序中的数据名字映射到目标机存储单元的过程。引进两个函数，environment和state。environment把名字映射到一个存储单元上；state把存储单元映射到那里所存放的值上。可以说，函数environment把一个名字映射为一个l-value（左-值）,而函数state把一个l-value（左-值）映射为一个r-value（右-值）。如图6.5所示。,16,名字,存储单元,值,存储分配,程序运行,environment,state,l-value,r-value,图6.5从名字到值的两个阶段映射,17,静态概念动态对应过程定义过程活动名字说明名字的绑定说明的作用域活动的生存期,18,6.1.6提出的问题编译程序组织存储分配所采用策略和方法主要取决于对源程序中下面的问题的回答。1过程可以是递归的吗？2当控制从过程的一次活动返回时，局部名的值将发生什么变化?3一个过程可以访问非局部名吗？4当调用过程时参数是怎样传递的？5过程可以作为参数被传递吗？6过程可以作为结果被返回吗？7.可以在程序控制下进行动态存储分配吗？8.显式的存储重新分配（指撤除分配后的分配）是必须的吗？,19,例：函数的返回值是函数。Funtimesxy=x*yvaltimes=fn:int(intint)twice=times2funcompose(f,g)=f(g(x)compose=fn:()()valfourtimes=compose(twice,twice),20,6.2存储组织6.2.1运行时刻内存的划分运行时刻的存储空间必须划分以用来存放:1.生成的目标代码;2.数据目标;3.用于保存过程活动踪迹的一个控制栈。存储空间划分的各部分：,21,目标代码,静态数据,栈,堆,1.编译后知道目标代码的大小。2.pascal主程序中的数据,c,FORTRAN3.栈:Pascal,c4.堆:Pascal,c,22,6.2.2活动记录把过程的一个活动所需要的信息组织成一块连续的存储单元，称为活动记录。一个活动所需要的信息的每个数据项有相同的生存期，因此，组织成一个活动记录是很自然的。对于pascal语言来说，运行过程中，当调用一个过程时，在栈顶构筑它的活动记录；当这个过程的活动执行完后，把它从栈顶弹出。源语言不同，实现方法不同，组成活动记录的域不同。实现pascal语言的活动记录如图6.7所示。,23,返回值,实在参数,控制链,访问链,保存机器状态,局部数据,临时变量,控制链:指向调用过程活动的活动记录。访问链：指向本活动要访问的非局部数据所在的活动记录。保存机器状态：调用过程活动在调用点的机器状态，包括计数器，各种寄存器的值。局部数据：过程中定义的局部量。临时变量：编译产生。,24,6.2.3编译时刻的局部数据的设计局部数据域是编译时刻在分析过程中的说明时设计的。例如：PROCEDUREsub(x,y:real);VARi,j:integer;a:ARRAY1.5OFreal;e,f:real;BEGINf:=e+i*j;END;,25,符号表,名字形类型偏移量,活动记录布局,返回值,(top-sp,0),x形real1,(top-sp,1),y形real2,(top-sp,2),(top-sp,3),(top-sp,20),iint20,(top-sp,21),jint21,(top-sp,22),aarray22,(top-sp,27),ereal27,(top-sp,28),freal28,26,中间代码*ijt1*(top-sp,20)(top-sp,21)(top-sp,29)+et1t2+(top-sp,27)(top-sp,29)(top-sp,30)itort2t3itor(top-sp,30)(top-sp,31):=t3f:=(top-sp,31)(top-sp,28)编译结束，知道每个过程的活动记录的长度，将其填写到相应的过程表中，运行时，调用哪个过程，就在运行栈顶，推进那个过程的活动记录（栈箭头加上活动记录长度）。,27,6.3运行时刻存储分配策略分配策略是：1静态分配；2栈式分配，或称栈式动态分配；3堆式分配，或称堆式动态分配。6.3.1静态存储分配6.3.2栈式存储分配6.3.3堆式存储分配采用哪种分配策略是由源语言的语义决定的。,28,6.3.1静态存储分配在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置，且这种绑定在运行时刻不再发生变化。局部名字的值在过程活动停止后仍保留下来。限制：1.在编译时刻知道数据目标的大小和它们在内存位置上约束；2.不能递归调用过程（一个过程的两个活动的生存期不相交,一个过程的所有活动可以使用同一个活动记录）；3.不能动态地建立数据结构。,29,（1）PROGRAMCNSUME（2）CHARACTER*50BUF（3）INTEGERNEXT（4CHARACTERC，PRDUCE（5）DATANEXT1，BUF/（6）CPRDUCE（）。（7）BUF（NEXT：NEXT）C（8NEXTNEXT1（9）IF（C.NE.)GOTO6（10）WRITE（*，(A)）BUF（11）END,30,(12）CHARACTERFUNCTIONPRDUCE（）（13)CHARACTER*80BUFFER（14）INTEGERNEXT（15）SAVEBUFFER，NEXT(16)DATANEXT81（17）IF(NEXT.GT.80）THEN（18)READ（*，（A)BUFFER（19）NEXT1（20)ENDIF（21）PRDUCEBUFFER（NEXT：NEXT）（22)NEXTNEXT1（23)END图6.8一个Fortran77程序,31,CNSUME目标代码,PRDUCE目标代码,Char*50bufintnextcharc,Char*80bufferintnext,Cnsume活动记录,prduce活动记录,目标代码,静态数据,32,6.3.2栈式存储分配基于控制栈的原理：存储空间被组织成栈，活动记录的推人和弹出分别对应于活动的开始和结束。与静态分配不同的是，在每次活动中把局部名字和新的存储单元绑定，在活动结束时，活动记录从栈中弹出，因而局部名字的存储空间也随之消失。例6.5图6.11表明当控制流通过图6.3的活动树时活动记录被推人或弹出运行时刻的栈中的情况，设寄存器top标记栈顶。,33,s,Sa:array,top,r,ri: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栈式分配活动记录在栈中的变化,34,确定活动记录中局部数据的地址：假设top-sp标记一个活动记录的开始的位置，dx表示x的地址相对于top-sp的偏移量。那么，x在过程的目标代码中的地址可写成dx（top-sp）在运行时刻，当把x的活动记录筑于栈顶时，寄存器top-sp被赋于实际的地址，top-sp可以是一个寄存器。调用序列和返回序列通过在目标代码中生成调用序列和返回序列实现过程的调用。激活一个过程的活动是执行,35,过程语句的结果。过程语句p(e1,e2,en)的目标代码（调用序列）完成任务：1.调用者对实在参数求值，并把它们传送给被调用过程的活动记录的参数域。2调用者在被调用者的活动记录中存放返回地址和老top-sp之值。之后调用者把top一sp之值增加到图6.12所示的位置。3被调用者存放寄存器值和其它状态信息。4被调用者初始化其局部数据并开始执行。,36,返回序列，return目标代码完成的任务是：1被调用者在自己的活动记录的返回值域中放一个返回值。2利用状态域中的信息，被调用者恢复top-sp和其它寄