北大编译原理讲义chapter6_1.ppt

《北大编译原理讲义chapter6_1.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、构造运行程序和源程序有关的一些问题36.1.1过程源程序由一组过程组成，不同的程序设计语言，由过程构成源程序的方法不同。构成源程序的两个过程行文，要么是嵌套的，要么是不相交的。4programsort（input，output）；vara：array［0..10]ofinteger；procedurereadarray；vari：integer；begin…end；functionpartition（y，z：integer）:integer；vari，j，x，v：integer；begin…end;procedurequicksort（m，n：integer）；vari：integer；be

3、ginend…end；begin…end.56.1.2活动树程序执行期间的控制流：1．程序执行的控制是顺序的；2．过程的每一次执行都是从过程体的开头开始，并最终把控制返回到紧接着该过程被调用点的后面。过程的一次活动:过程体的每一次执行。一个过程p的一次活动的生存期:在该过程体的执行中的第一步和最后一步之间的一序列步骤的执行时间，其中包括执行过程p所调用的过程的执行时间，以及这些过程所调用的过程的执行时间，如此等等。6特点：每当控制流从过程p的活动进入到过程q的活动中后，它将返回到过程p的同一次活动中。    如果a和b是两个过程活动，那么它们的生存期要么是不重叠的，要么是嵌套的。这种活动生

4、存期的嵌套性质可以通过在每一个过程中插入两个打印语句来加以说明。7执行开始enterreadarrayleavereadarrayenterquicksort（1，9）enterpartition（1，9）leavepartition（l，9）enterquicksort（1，3）................   leavequicksort（1，3)enterquicksort（5，9）................   leavequicksort（5，9）leavequicksort（1，9）执行结束8一个过程是递归的，如果同一过程的一次新的活动可以在前面活动结束以前开始。用

5、一颗树来描绘控制进入和离开活动的途径。这祥的树称作活动树。在一棵活动树中：1.每一个结点代表一个过程的活动;   2.根结点代表主程序的活动;   3.代表a的结点是b结点的父结点当且仅当控制从活动a进入活动b;   4.结点a在结点b的左边当且仅当a的生存期发生在b的生存期之前。用活动树来讨论正在这个结点上的控制。9srq(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、控制进入某一个活动时，可以直接说，控制在这个结点上。6.1.3控制栈程序执行的控制流对应于从根开始，按先根次序遍历活动树。因此，用一个栈保存过程活动的生存踪迹。把它称作控制栈。当一个活动开始执行时，把代表这个活动的结点推进栈；当这个活动结束时，把代表这个活动的结点从栈中弹出。11例6.2栈和活动树的变化栈ssrSrq(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.412控制栈中的活动都是

7、活跃的，当前控制进入的活动在栈顶，从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的结点序列：s,q（1，9），q（l，3），q（2，3）从栈底活动到栈顶活动的活动序列表示了活动的生存期的嵌套关系。结论：扩充控制栈可用来实现如Pascal语言的栈式存储分配，进入一个活动，在栈顶建立这个活动所使用的存储空间；这个活动结束，从栈顶弹出其使用的存储空间。136.1.4说明的作用域1.说明把名字与名字