北大编译原理chapter6

1、1 第六章 运行时刻环境 序6.1 源语言中的一些问题6.2 存储组织6.3 运行时刻存储分配策略6.4 非局部名字的访问6.5 参数传递6.6 符号表2 序 计算环境 运行时的环境 计算 目标代码 源程序中的名字（常量，变量）目标机存储空间。它受命于源程序的执行语义。 源程序由一组过程按某种规则组成。过程的一次执行称作一次活动，在过程的语句序列执行之前，过程中访问的对象构成此过程的运行环境，由运行支持程序组织好。编译程序根据如何组织运行环境而生成目标代码。映射源程序36.1有关源程序中的一些问题有关源程序中的一些问题 目的： 构造运行程序的策略和方法 6.1.1 过程 6.1.2 活动树 6

2、.1.3 控制栈 6.1.4 说明的作用域 6.1.5 名字的绑定 6.1.6 构造运行程序和源程序有关的 一些问题46.1.1 过程 源程序由一组过程组成，不同的程序设计语言，由过程构成源程序的方法不同。 构成源程序的两个过程行文，要么是嵌套的，要么是不相交的。5program 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：

3、integer； begin end; procedure quicksort（m，n ： integer）； var i ： integer； begin end end； begin end.66.1.2 活动树活动树 程序执行期间的控制流： 1程序执行的控制是顺序的； 2过程的每一次执行都是从过程体的开头 开始，并最终把控制返回到紧接着该过 程被调用点的后面。 过程的一次活动: 过程体的每一次执行。 一个过程p的一次活动的生存期:在该过程体的执行中的第一步和最后一步之间的一序列步骤的执行时间，其中包括执行过程p所调用的过程的执行时间，以及这些过程所调用的过程的执行时间，如此等等。7 特点

4、： 每当控制流从过程p的活动进入到过程q的活动中后，它将返回到过程p的同一次活动中。 如果a和b是两个过程活动，那么它们的生存期要么是不重叠的，要么是嵌套的。 这种活动生存期的嵌套性质可以通过在每一个过程中插入两个打印语句来加以说明。8执行开始 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、（5，9） leave quicksort（1，9） 执行结束9 一个过程是递归的，如果同一过程的一次新的活动可以在前面活动结束以前开始。 用一颗树来描绘控制进入和离开活动的途径。这祥的树称作活动树。在一棵活动树中： 1. b的左边当且仅当a的生存期发生在b的生存期之前。 用活动树来讨论正在这个结点上的控制 。 10srq(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、进 入某一个活动时，可以直接说，控制在 这个结点上。6.1.3 控制栈 程序执行的控制流对应于从根开始，按先根次序遍历活动树。因此，用一个栈保存过程活动的生存踪迹。把它称作控制栈。 当一个活动开始执行时，把代表这个活动的结点推进栈；当这个活动结束时，把代表这个活动的结点从栈中弹出。12例6.2 栈和活动树的变化栈ssrs rq(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

7、,3)图 6.413 控制栈中的活动都是活跃的，当前控制进入的活动在栈顶，从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的结点序列： s,q（1，9），q（l，3），q（2，3） 从栈底活动到栈顶活动的活动序列表示了活动的生存期的嵌套关系。 结论结论：扩充控制栈可用来实现如pascal语言的栈式存储分配，进入一个活动，在栈顶建立这个活动所使用的存储空间；这个活动结束，从栈顶弹出其使用的存储空间。146.1.4 说明的作用域说明的作用域 1 .说明明把名字与名字的属性信息绑定在一起。 2 . 说明的作用域是一个说明起作用的范围 （源程序行文）。一个名字在源程序行文中 可能有几处

8、说明，语言的作用域规则规定： 在语句序列中引用的一个名字是在何处说 明的名字。 3 . 编译时，处理说明把名字及其属性信息填 写进符号表(add(id.entry,id.vul); 处理引用 名字时，查找这个名字的属性信息 （lookup(id),符号表管理程序根据语 言的 作用域规则，使 lookup(id)返回id的作作用域 中绑定的属性信息。156.1.5名字与存储的绑定名字与存储的绑定 名字与存储单元的绑定是指把源程序中的数据名字映射到目标机存储单元的过程。 引进两个函数，environment和state。environment把名字映射到一个存储单元上；state把存储单元映射到那

9、里所存放的值上。可以说，函数environment把一个名字映射为一个l-value（左-值）,而函数state把一个l-value（左-值）映射为一个r-value（右-值）。如图6.5所示。16名字存储单元值存储分配程序运行environmentstatel-valuer-value图6.5 从名字到值的两个阶段映射17静态概念 动态对应过程定义 过程活动名字说明 名字的绑定说明的作用域 活动的生存期186.1.6 提出的问题提出的问题 编译程序组织存储分配所采用策略和方法主要取决于对源程序中下面的问题的回答。 1过程可以是递归的吗？ 2当控制从过程的一次活动返回时，局部 名的值将发生什么

10、 变化? 3一个过程可以访问非局部名吗？ 4当调用过程时参数是怎样传递的？ 5过程可以作为参数被传递吗？ 6过程可以作为结果被返回吗？ 7. 可以在程序控制下进行动态存储分配吗？ 8. 显式的存储重新分配（指撤除分配后的分 配）是必须的吗？ 19例：函数的返回值是函数。fun times x y=x*y val times=fn: int (int int) twice=times 2fun compose(f, g)=f(g(x) compose=fn: ( ) ( )val fourtimes=compose(twice,twice)206.2 存储组织存储组织 6.2.1 运行时刻内存的

11、划分运行时刻内存的划分 运行时刻的存储空间必须划分以用来存放: 1. 生成的目标代码; 2. 数据目标; 3. 用于保存过程活动踪迹的一个控制栈。 存储空间划分的各部分：21目标代码静态数据栈堆1. 编译后知道目标代 码的大小。2. pascal主程序中的 数据,c,fortran3. 栈:pascal,c4. 堆: pascal,c226.2.2 活动记录活动记录 把过程的一个活动所需要的信息组织成一块连续的存储单元，称为活动记录。 一个活动所需要的信息的每个数据项有相同的生存期，因此，组织成一个活动记录是很自然的。 对于pascal语言来说，运行过程中，当调用一个过程时，在栈顶构筑它的活动

12、记录；当这个过程的活动执行完后，把它从栈顶弹出。 源语言不同，实现方法不同，组成活动记录的域不同。实现pascal语言的活动记录如图6.7所示。23返回值实在参数控制链访问链保存机器状态局部数据临时变量控制链:指向调用过程活动 的活动记录。访问链：指向本活动要访 问的非局部数据所在的 活动记录。保存机器状态：调用过程 活动在调用点的机器 状态，包括计数器， 各种寄存器的值。局部数据：过程中定义的 局部量。临时变量：编译产生。246.2.3 编译时刻的局部数据的设计编译时刻的局部数据的设计 局部数据域是编译时刻在分析过程中的说 明时设计的。例如： procedure sub(x,y:real);

13、 var i ,j:integer; a:array1.5 of real; e, f : real; begin f :=e+i*j; end;25符号表名字 形 类型 偏移量活动记录布局返回值(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 2826中间代码* i j t1 * (top-sp ,20) (top-s

14、p ,21) (top-sp ,29) + e t1 t2 + (top-sp ,27) (top-sp ,29) (top-sp ,30) itor t2 t3 itor (top-sp ,30) (top-sp ,31):= t3 f := (top-sp ,31) (top-sp ,28) 编译结束，知道每个过程的活动记录的长度，将其填写到相应的过程表中，运行时，调用哪个过程，就在运行栈顶，推进那个过程的活动记录（栈箭头加上活动记录长度）。276.3 运行时刻存储分配策略运行时刻存储分配策略 分配策略是： 1静态分配； 2栈式分配，或称栈式动态分配； 3堆式分配，或称堆式动态分配。 6.

15、3 .1 静态存储分配 6.3 .2 栈式存储分配 6.3 .3 堆式存储分配 采用哪种分配策略是由源语言的语义决定的。286.3 .1 静态存储分配 在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置，且这种绑定在运行时刻不再发生变化。 局部名字的值在过程活动停止后仍保留下来。 限制： 1.在编译时刻知道数据目标的大小和它们在 内存位置上 约束； 2.不能递归调用过程（一个过程的两个活动 的生存期不相交,一个过程的所有活动可以 使用同一个活动记录）； 3.不能动态地建立数据结构。29 （1）program cnsume （2） character *50 buf （3） intege

16、r next （4 character c，prduce （5） data next1，buf/ / （6） cprduce（）。 （7） buf（next：next）c （8 nextnext1 （9） if（c.ne. )goto 6 （10） write（*，(a)）buf （11） end 30(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) rea

17、d（*，（a)buffer （19） next1 （20) end if （21） prducebuffer（next：next） （22 ) nextnext1 （23 ) end 图图6.8 一个一个fortran 77程序程序 31cnsume目标代码prduce目标代码char *50 buf int next char cchar *80 buffer int next cnsume活动记录prduce活动记录目标代码静态数据326.3.2 栈式存储分配栈式存储分配 基于控制栈的原理：存储空间被组织成栈，活动记录的推入和弹出分别对应于活动的开始和结束。 与静态分配不同的是，在每次活动

18、中把局部名字和新的存储单元绑定，在活动结束时，活动记录从栈中弹出，因而局部名字的存储空间也随之消失。 例6.5 图6.11表明当控制流通过图6.3的活动树时活动记录被推人或弹出运行时刻的栈中的情况，设寄存器top标记栈顶。33ssa:arraytoprri:integertoptopq(1,9)q(1,9)i:integertopp(1,9)p(1,9)i:integertoptopq(1,3)q(1,3)i:integertop图 6.11 栈式分配活动记录在栈中的变化34 确定活动记录中局部数据的地址：假设top-sp标记一个活动记录的开始的位置， dx表示x的地址相对于top-sp的偏移

19、量。那么， x在过程的目标代码中的地址可写成 dx（top-sp）在运行时刻，当把x的活动记录筑于栈顶时，寄存器top- sp被赋于实际的地址， top- sp可以是一个寄存器。调用序列和返回序列调用序列和返回序列 通过在目标代码中生成调用序列和返回序列实现过程的调用。激活一个过程的活动是执行35过程语句的结果。过程语句 p(e1,e2,en)的目标代码（调用序列）完成任务： 1. 调用者对实在参数求值，并把它们传送给 被调用过程的活动记录的参数域。 2调用者在被调用者的活动记录中存放返 回地址和老top-sp之值。之后调用者把 top一sp之值增加到图6.12所示的位置。 3被调用者存放寄存

20、器值和其它状态信息。 4被调用者初始化其局部数据并开始执行。36返回序列，return目标代码完成的任务是： 1被调用者在自己的活动记录的返回值域 中放一个返回值。 2利用状态域中的信息，被调用者恢复 top-sp和其它寄存器，并且按返回地址转 移到调用者的代码之中。 3调用者复制返回值到自己的活动记录中。 任务的划分，根据源语言、目标机器和操 作系统等具体情况而定。 上述任务，由运行支持子程序完成，可视为虚机指令。37 可变长度的数据可变长度的数据 源程序的例子 procedure exam(l,m,n:integer); var a:array 1.l of real; b:array 1

21、.m of real; c:array 1.n of real; begin end; 编译时，不知 a,b,c的大小，仅对每个数组设置一个指针。38control linkabctop-sptoparray aarray barray ctopp的活动记录p的动态数组图6.13 动态分配的数组39活动记录的进栈和推栈 栈顶活动记录用两个指针top和top-sp指示。top-sp指向栈顶活动记录保存机器状态域的末 端，用于访问局部数据。top指向栈顶。p调用q：栈top+h:=top-sp; top-sp:=top+h; top:=top+q的活动记录长度从q的活动返回：top:=top-sp

22、q (h) top-sp:=栈top-sp40pqtop-sptop-sptoptoph416.3.3 堆式存储分配堆式存储分配 1局部名的值在活动结束时必须被保存。 2. 被调用者的活动生存期超过调用者。 用活动树不能够正确描绘这种语言的过 程之间的控制流。 new(p); dispose(p);426.4 对非局部名字的访问对非局部名字的访问 讨论基于活动记录的栈式分配。 一个语言所规定的作用域规则决定了如何处理对非局部名字的引用。 有静态和动态两种作用域规则。 静态静态:考查程序正文来决定引用的名字是哪一个名字说明,如pascal，c和ada是众多语言中使用带有“最近嵌套”规定的词法作用

23、域规则的语言 ; 动态动态:在运行时刻考查最近的活动来决定应用到一个名字上的说明,如lisp和apl。 436.4.1 块块 一个块（block）是一个含有局部数据说明的语句。 declarations statements 一个块与另一个块要么是独立的，要么 一 个块完全嵌入在另一个块之中，这种嵌套的性质有时称作块结构。 在块结构语言中，说明的作用域由最近嵌套规则给出： 1在块b中的一个说明的作用域包括b。 2如果名字x在块b中没有说明，那么，44 x在b中的出现是在一个外围块b中的x的说 明的作用域之内，并且使得： （a) b 中有x 的说明， （b) b 是包围b的，相对于其它任何具有

24、名字x 的说明且包围b 的块而言,b是 离b 最近的。 对于pascal语言来说，一个过程是一个块，一个程序是一个块结构。而对于c语言来说，每个函数是一个块结构，而函数之间是不嵌套的。45main( ) int a=0; /*b0-b2*/ int b=0; /* b0-b1 */ int b=1; /* b1-b3 */ int a=2; printf(“%d%d/n”,a,b) ; int b=3; printf(“%d%d/n”,a,b) ; printf(“%d%d/n”,a,b) ; printf(“%d%d/n”,a,b) ; b0b1b2b346a0b0b1a2 , b3 图6.

25、16 函数main局部数据 在活 动记录中的按排 块结构语言可以采用栈式分配。函数main的每个块可看成一个无参过程，块中的块可被看成一个语句。控制从块开始进入，遇块结束退出。b2和b3的生存期不相交，它们的局部数据可占用同一块存储空间。476.4.2 不含嵌套过程的词法作用域不含嵌套过程的词法作用域 c中过程定义不能嵌套 （l）int a11; （2） readarray( ) a （3） int partition（y，z） int y，z； a （4） quicksort（m，n） int m，n； . （5） main( ) .a. 图6.17 带有a的非局部出现的c程序 48目标代码

26、 int a11栈堆1.函数外的数据和函数内 的静态数据，静态分配 于静态数据域。2 .函数内的数据（out) 栈 式分配,运行进入任一 函 数，使用的 数据，要 么 在 当前的活动记录中； 要么在 静态数据域中。496.4.3 含有嵌套过程的词法作用域含有嵌套过程的词法作用域 图6.18 带有嵌套过程的一个pascal程序程序的静态嵌套结构： sort readarray exchange quicksort partition 50（1） program sort（input，output）;（2） var a： array0.10 of integer； （3） x : integer；

27、 （4） procedure readarray； （5） var i ： integer； （6） begin a end readarray; （7） procedure exchange（i，j： integer）； （8） begin （9） x：= ai ；ai:=aj; aj:x （10） end exchange; 51（11） procedure quicksort（m，n： integer）； （12） var k，v： integer； （13） function partition（y，z： integer） ： integer； （14） var i，j ： integ

28、er； （15） begin a （16） v （17） exchange（i，j）； （18） end partition; （19） begin end quicksort; （20） begin end. sort52 程序的静态嵌套结构决定程序中每个过程中访问哪些外围过程中的数据。 每个过程静态嵌套在哪些过程中，可用静态链static(p)表示: static(sort)=sort static(readarray)=sort readarray static(exchange)=sort exchange static(quichsort)=sort quichsort static

29、(partition)=sort quichsort partition 运行时，过程的数据被组织成活动记录，为了实现非局部访问，过程的活动记录之间必须维持静态链反映程序的静态嵌套结构。53 6.4.3.1 嵌套深度嵌套深度 用过程的嵌套深度过程的嵌套深度来表达一个过程在程序中的嵌套层次。令主程序的嵌套深度为1；从一个过程进入到一个被包围过程时嵌套深度加1。如图6.18中的位于（11）行上的过程quicksort的嵌套深度为2，而（13）行上的partition的嵌套深度为3。 过程表示除过程名字之外的过程定义正文。 一个名字的嵌套深度名字的嵌套深度等于说明它的过程的嵌套深度，是名字的重要属性

30、。在（15）（17）行上的partition中的a,v和i的嵌套深度分别是1，2和3。 54 6.4.3.2 存取链（access link） 栈中的活动记录应反映源程序正文中过程 之间的嵌套关系，或静态结构。为每一个活动记录增设一个称为存取链（或存取链路）的指针，如果在源程序正文中过程p直接嵌入在过程q中，那么p的一个活动记录中的存取链指向q的最近的活动记录中的存取链。从当前活动记录开始，沿着这条链，能找到访问的非局部名字。它是静态链在存储空间上的实现，也称作静态链。 程序运行过程中应维持这条链。55s s nil a , xtop-sptopr r itoptop-sptop-sptop

31、q(1,9) q(1,9) k , vtoptop-spp(1,9) p(1,9) i , jtoptop-sptop-sptop q(1,3) q(1,3) k , vtoptop-spp(1,3) p(1,3) i , jtoptop-spe(1,3) e(1,3) i , jtoptop-sp图 6.1956非局部访问非局部访问 在嵌套深度为np 的过程p中引用一个嵌套深度为na np 的非局部名字a,a的存储位置可按下面的步骤找到： 1从栈顶活动记录出发沿存取链前进npna步，到达a所在的活动记录。npna的值可在编译时刻计算出来。 2a的地址= a所在活动记录的始址+ a的偏移量。编

32、译生成过程p的目标代码中非局部名字a的地址表示为： （npna ，a在其活动记录中的偏移量) 57运行时存取链的维护运行时存取链的维护 维护存取链的代码是调用序列的一部分。 假设嵌套深度为np 的过程p调用嵌套深度为nx 的过程x。存取链的维护依赖于过程p和过程x之间的嵌套关系。 1.np nx ， nx=np+1, x 在p中定义。 被调用过程的活动记录的存取链必须指向栈中刚好在其前面的（地址码较低的）调用过程的活动记录的存取链。 58p x call xptop-sptopxtop-sptop栈top+h:=top-sp;top-sp:=top+h;top:=top+x的活动 记录长度；5

33、92. npnxxpcall x np=nxpx60 call xxpx pcall xpxnpnx61 过程p和x的嵌套深度为1，2， ,nx-1的外围过程是相同的。 从p的活动记录开始沿存取链前进np-nx+1步，可到达包围着p和x且离它们最近的过程的当前的活动记录。这个活动记录的存取链位置即是x的当前活动记录存取链应指向的位置。 np-nx+1在编译时能计算出来。62过程作为参数传递的实现 program param(input,output); procedure b(fun h(n:integer):integer); begin writeln(h(2) end; procedur

34、e c; var m: integer; function f(n:integer):integer; begin f:=m+n end; begin m:=0; b(f) end; begin c end. 63paramcm:=0b( f )存取链存取链f( 2 )如何建立存取链？ 过程要在定义它的环境中运行。过程作为实参数传递时，必须把它的存取链作为实参数的一部分传递。 在传递f时，确定f的存取链，好象在c中调用f一样。 在b中激活f的活动时，它作为f的活动记录的存取链。646.4.3.3 display表 display表是一个指针数组d，在运行过程中，若当前活动的过程的嵌套深度为i，

35、则di中存放当前的活动记录地址，di-1,di-2, ,d1 中依次存放着当前活动的过程的直接外层， , 直至最外层（主程序）等每一层过程的最新活动地址。 这样，嵌套深度为j的变量a存放在由dj所指出的活动记录中。 在运行过程中维持一个display表实现非局部访问比存取链效率要高。65display表的维护表的维护（过程不作为参数传递） 当嵌套深度为i的过程的活动记录筑在栈顶时： （1）在新的活动记录中保存di的值； （2）置di指向新的活动记录。 在一个活动结束前， di置成保存的旧值。用display表如何访问非局部量？ 1. display表是一个数组，开始地址用通用 寄存器指出； 2

36、. display表由一组寄存器实现。66ssa, xdisplayrrq(1,9)q(1,9)k, vp(1,9)p(1,9)e(1,9) e(1,9) save d2 q(1,3) q(1,3) save d2k, vp(1,3) p(1,3) save d3i, j图 6.1967设p （嵌套深度为j）调用q（嵌套深度为i）1. ji qd1d2di-1dipqpcall qsave dipcall qqdjsave dj706.4.4 动态作用域动态作用域 程序运行时，一个名字a实施其影响，直到含a的声明的一个过程开始执行时暂停，此过程停止时，该影响恢复。 设有下面的的调用序列： a

37、b c p过程p中有对x的非局部引用，沿动态链（红链）查找，最先找到的便是。71 program dynamic（input，output)； var r：real； procudure show； begin wtite（r： 5：3 ） end； procedute small； var r： real； begin r: 0.125； show end； begin r：0.25； show； small； write1n； show； small； writeln end.72 在词法作用域之下，程序的输出为 : 0.250 0.250 0.250 0.250 在动态作用域之下，输出为

38、: 0.250 0.125 0.250 0.125 实现动态作用域的方法实现动态作用域的方法: 1.深访问深访问。使用控制链在栈中搜索，以寻 找包含所需非局部名字的存储单元的第 一个活动记录（控制链又称动态链）。73 2浅访问浅访问。这种方法的思想是在静态分配 的存储空间中存放每一个名字的现行值。 当过程p开始一次新的活动时，p中的非局 部名n占用对于n静态分配的存储空间。先 前的n值可以存放在p的活动记录中并且当 p的活动记录结束时必须给以恢复。 两种方法进行比较。746.5 参数传递参数传递 实在参数和形式参数结合的方法： 传值调用（call-by-value） 引用调用（call-by-

39、reference） 复制恢复（copy-restore） 传名调用（call-by-name） ai:=aj 其中表达式aj代表一个值，而ai 则表示一个存储地址。 参数传递方法之间的区别主要基于实在参数是代表右-值（r-值）、左-值（l-值）、 或者实在参数的正文本身。756.5.1 传值调用传值调用 program reference（input，output）； var a，b ： integer； procedure swap（x，y： integer）； var temp： integer； begin temp :x； x ：y； y ：temp end; begin a：1; b：2; swap(a，b); writeln( a=，a， b= ,b ） end.76传值调用可以实现如下： 调用过程计算实在参数，并把它们的右- 值放入到形式参数的存储空间中。 使用传值的方法，调用swap（a,b）等价于下面几步： x：= a y：= b temp：= x x：= y y：= temp 776.5.2 引用调用引用调用 把实在参数的地址传递给相应的形式参数, 在目标代码中，在被调用过程中对形式参数的一