运行时的存储组织及管理

《运行时的存储组织及管理》由会员分享，可在线阅读，更多相关《运行时的存储组织及管理（37页珍藏版）》请在装配图网上搜索。

1、运行时的存储组织及管理运行时的存储组织及管理10/7/20222004年12月28日1编译器的应用模型编译器的应用模型出出错错处处理理语法分析程序语法分析程序语义分析程序语义分析程序目标代码生成程序目标代码生成程序词法分析程序词法分析程序中间代码生成程序中间代码生成程序代码优化程序代码优化程序表表格格管管理理编译的前端编译的前端（Front End）编译的后端编译的后端（Back End）10/7/20222编译原理编译原理运行时的存储组织及管理运行时的存储组织及管理概述概述存储组织存储组织运行时的存储分配策略运行时的存储分配策略静态存储分配静态存储分配动态存储分配动态存储分配对非局部名字的访

2、问对非局部名字的访问参数传递参数传递10/7/20223编译原理编译原理运行时的存储组织及管理运行时的存储组织及管理 计算环境 运行时的环境 计算 目标代码当词法分析扫描得到标识符，并将它填入符号表的当词法分析扫描得到标识符，并将它填入符号表的过程中需要给识别出来的标识符分配内存空间。过程中需要给识别出来的标识符分配内存空间。源程序由一组源程序由一组按某种规则组成。按某种规则组成。过程的一次执行称作一次过程的一次执行称作一次。在过程的语句序列执行之前，过程中访问的对象构在过程的语句序列执行之前，过程中访问的对象构成此过程的运行环境，由运行支持程序组织好。成此过程的运行环境，由运行支持程序组织好

3、。编译程序根据如何组织运行环境而生成目标代码。编译程序根据如何组织运行环境而生成目标代码。映射源程序10/7/20224编译原理编译原理运行时环境的作用运行时环境的作用目标程序运行时所需存储空间的组织与管理以及源目标程序运行时所需存储空间的组织与管理以及源程序中变量存储空间的分配。程序中变量存储空间的分配。10/7/20225编译原理编译原理有关源程序中的一些问题有关源程序中的一些问题问题的提出：如何问题的提出：如何构造运行程序的策略和方法构造运行程序的策略和方法过程过程活动树活动树控制栈控制栈说明的作用域说明的作用域名字的绑定名字的绑定构造运行程序和源程序有关的一些问题构造运行程序和源程序有

4、关的一些问题10/7/20226编译原理编译原理过程过程源程序由一组过程组成，不同的程序设计语言，由源程序由一组过程组成，不同的程序设计语言，由过程构成源程序的方法不同。过程构成源程序的方法不同。构成源程序的两个过程行文，要么是嵌套的，要么构成源程序的两个过程行文，要么是嵌套的，要么是不相交的。是不相交的。10/7/20227编译原理编译原理program sort(input,output);var a:array0.10 of integer;procedure readarry;var i:integer;beginfor i:=1 to 9 do read(ai)end;functio

5、n partition(y,z:integer):integer;var i,j,x,v:integer;begin end;procedure quicksort(m,n:integer)var i:integer;beginif(nm)then begini:=partition(m,n);quicksort(m,i-1);quicksort(i+1,n)endendbegina0:=-9999;a10:=9999;readarray;quicksort(1,9)end10/7/20228编译原理编译原理活动树活动树程序执行期间的控制流：程序执行期间的控制流：程序执行的控制是连续的：在任何

6、一步，控制都处于程序的某程序执行的控制是连续的：在任何一步，控制都处于程序的某一点一点过程的每一次执行都是从过程体的开头过程的每一次执行都是从过程体的开头 开始，并最终把控制返开始，并最终把控制返回到紧接着该过程被调用点的后面。回到紧接着该过程被调用点的后面。过程的一次活动过程的一次活动:过程体的每一次执行。过程体的每一次执行。过程过程p的一次活动的的一次活动的:在该过程体的执行中的第一步和在该过程体的执行中的第一步和最后一步之间的一序列步骤的最后一步之间的一序列步骤的，其中包括执行过程，其中包括执行过程p所调用的过程的执行时间，以及这些过程所调用的过程的所调用的过程的执行时间，以及这些过程所

7、调用的过程的，如此等等。，如此等等。一个过程是递归的，如果同一过程的一次新的活动可以在前一个过程是递归的，如果同一过程的一次新的活动可以在前面活动结束以前开始。面活动结束以前开始。10/7/20229编译原理编译原理活动树活动树为什么过程的活动可以用树形结构描述？为什么过程的活动可以用树形结构描述？过程活动的特点：过程活动的特点：每当控制流从过程每当控制流从过程p的活动进入到过程的活动进入到过程q的活动中后，的活动中后，它将返回到过程它将返回到过程p的同一次活动中。的同一次活动中。也就是说，如果也就是说，如果a和和b是两个过程活动，那么它们的生是两个过程活动，那么它们的生存期要么是不重叠的，要

8、么是嵌套的。存期要么是不重叠的，要么是嵌套的。在树形结构中，节点间的关系就反映了过程之间的在树形结构中，节点间的关系就反映了过程之间的关系：关系：父子关系：嵌套父子关系：嵌套兄弟关系：先后兄弟关系：先后10/7/202210编译原理编译原理活动树活动树用一颗树来描绘控制进入和离开活动的途径。这祥用一颗树来描绘控制进入和离开活动的途径。这祥的树称作活动树。的树称作活动树。每个节点代表过程的一个活动每个节点代表过程的一个活动根节点代表主程序的活动根节点代表主程序的活动当且仅当控制流从活动当且仅当控制流从活动a进入活动进入活动b时，节点时，节点a是是b的父的父节点节点当且仅当当且仅当a的生存期先于的

9、生存期先于b的生存期时，的生存期时，a节点处于节点处于b结结点的左边点的左边一个结点代表一个唯一的活动，一个结点代表一个唯一的活动，且每一个活动只有且每一个活动只有一个结点表示，当控制进入某一个活动时，可以直一个结点表示，当控制进入某一个活动时，可以直接说，控制在这个结点上。接说，控制在这个结点上。10/7/202211编译原理编译原理program sort(input,output);var a:array0.10 of integer;procedure readarry;var i:integer;beginfor i:=1 to 9 do read(ai)end;function p

10、artition(y,z:integer):integer;var i,j,x,v:integer;begin end;procedure quicksort(m,n:integer)var i:integer;beginif(nm)then begini:=partition(m,n);quicksort(m,i-1);quicksort(i+1,n)endendbegina0:=-9999;a10:=9999;readarray;quicksort(1,9)endsrq(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)10

11、/7/202212编译原理编译原理控制栈控制栈程序的控制流对应于从活动树根节点开始的深度优先遍历。程序的控制流对应于从活动树根节点开始的深度优先遍历。（从左至右）（从左至右）活动树表示了完整的程序控制的先后顺序。在真正运行过程活动树表示了完整的程序控制的先后顺序。在真正运行过程中，活动树并不是真实存在的数据结构。中，活动树并不是真实存在的数据结构。在程序运行过程中，我们只需要保存那些在程序运行过程中，我们只需要保存那些。控制栈控制栈控制栈的基本思想：控制栈的基本思想：当一个活动开始执行时，把代表这个活动的结点推进栈；当这当一个活动开始执行时，把代表这个活动的结点推进栈；当这个活动结束时，把代表

12、这个活动的结点从栈中弹出。个活动结束时，把代表这个活动的结点从栈中弹出。控制栈只能表示活动树的一部分控制栈只能表示活动树的一部分活动树只是逻辑上存在活动树只是逻辑上存在的的类似于语法分析树类似于语法分析树10/7/202213编译原理编译原理栈和活动树的变化栈和活动树的变化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,3)10/7/202214编译原理编译原理控制栈控制栈

13、控制栈中的活动都是活跃的，当前控制进入的活动控制栈中的活动都是活跃的，当前控制进入的活动在栈顶，从栈顶活动到栈底活动的活动序列是从活在栈顶，从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的结点序列。动树上当前结点通向根的路径上的结点序列。从栈底活动到栈顶活动的活动序列表示了活动的生从栈底活动到栈顶活动的活动序列表示了活动的生存期的存期的 结论：扩充控制栈可用来实现如结论：扩充控制栈可用来实现如Pascal语言的栈式语言的栈式存储分配。（控制栈中存储活动记录）存储分配。（控制栈中存储活动记录）10/7/202215编译原理编译原理声明的作用域声明的作用域声明语句是把名字与名字的

14、属性信息绑定在一起的语法结声明语句是把名字与名字的属性信息绑定在一起的语法结构。构。说明的作用域是一个说明起作用的范围说明的作用域是一个说明起作用的范围(源程序行文源程序行文)。一个名字在源程序行文中可能有几处说明，语言的一个名字在源程序行文中可能有几处说明，语言的规定了在语句序列中引用的一个名字是在何处说明的名规定了在语句序列中引用的一个名字是在何处说明的名字。字。编译时，处理说明时，把名字及其属性信息填写进符号表；编译时，处理说明时，把名字及其属性信息填写进符号表；处理引用时，查找这个名字的属性信息，符号表管理程序根处理引用时，查找这个名字的属性信息，符号表管理程序根据语言的作用域规则，返

15、回其作用域中绑定的属性信息。据语言的作用域规则，返回其作用域中绑定的属性信息。10/7/202216编译原理编译原理名字与存储的绑定名字与存储的绑定名字与存储单元的绑定是指把源程序中的名字与存储单元的绑定是指把源程序中的映射到映射到的过程。的过程。把名字映射到一个存储单元上；把名字映射到一个存储单元上；把存储单把存储单元映射到那里所存放的值上。元映射到那里所存放的值上。或者说，环境把一个名字映射为一个左值，而状态或者说，环境把一个名字映射为一个左值，而状态把一个左值映射为一个右值。把一个左值映射为一个右值。10/7/202217编译原理编译原理名字与存储的绑定名字与存储的绑定名字名字存储单元存

16、储单元值值存储分配存储分配程序运行程序运行环境环境状态状态l-valuer-value10/7/202218编译原理编译原理静态概念静态概念 动态对应动态对应过程定义过程定义 过程活动过程活动名字说明名字说明 名字的绑定名字的绑定说明的作用域说明的作用域 活动的生存期活动的生存期10/7/202219编译原理编译原理存储组织存储组织运行时刻内存的划分：假定编译器从操作系统得到运行时刻内存的划分：假定编译器从操作系统得到一块存储区，运行时的存储空间要划分成块一块存储区，运行时的存储空间要划分成块:生成的目标代码生成的目标代码;数据对象数据对象;记录过程活动的控制栈对应的数据结构记录过程活动的控制

17、栈对应的数据结构10/7/202220编译原理编译原理目标代码目标代码静态数据静态数据栈栈堆堆1.编译后知道目标代码的大小。编译后知道目标代码的大小。放入静态确定的区域中放入静态确定的区域中2.某些数据对象的长度也可以在编译某些数据对象的长度也可以在编译时知道，也可以放在静态区域中。主时知道，也可以放在静态区域中。主程序中的数据：程序中的数据：c,FORTRAN3.栈栈控制栈：控制栈：Pascal,c4.堆堆开销比栈大开销比栈大(分配和释放方分配和释放方式式)：Pascal,c10/7/202221编译原理编译原理活动记录活动记录把过程的一个活动所需要的信息组织成一块连续的把过程的一个活动所需

18、要的信息组织成一块连续的存储单元，称为活动记录。存储单元，称为活动记录。一个活动所需要的信息的每个数据项有相同的生存一个活动所需要的信息的每个数据项有相同的生存期，因此，组织成一个活动记录是很自然的。期，因此，组织成一个活动记录是很自然的。对于对于pascal语言来说，运行过程中，当调用一个过程语言来说，运行过程中，当调用一个过程时，在栈顶构筑它的活动记录；当这个过程的活动时，在栈顶构筑它的活动记录；当这个过程的活动执行完后，把它从栈顶弹出。执行完后，把它从栈顶弹出。10/7/202222编译原理编译原理活动记录活动记录控制链控制链:指向调用过程活动的活动指向调用过程活动的活动记录。记录。访问

19、链：指向本活动要访问的非访问链：指向本活动要访问的非局部数据所在的活动记录。局部数据所在的活动记录。保存机器状态：调用过程活动在保存机器状态：调用过程活动在调用点的机器状态，包括计数调用点的机器状态，包括计数器，各种寄存器的值。器，各种寄存器的值。局部数据：过程中定义的局部局部数据：过程中定义的局部量。量。临时变量：编译产生。临时变量：编译产生。返回值返回值实在参数实在参数控制链控制链访问链访问链保存机器状态保存机器状态局部数据局部数据临时变量临时变量10/7/202223编译原理编译原理编译时刻的局部数据的设计编译时刻的局部数据的设计PROCEDURE sub(x,y:real);VAR i

20、,j:integer;a:ARRAY1.5 OF real;e,f:real;BEGINf:=e+i*j;END;名字名字 形形 类型类型 偏移量偏移量 x 形形 real 1 y 形形 real 2 i int 20 j int 21 a array 22 e real 27 f real 28符号表符号表10/7/202224编译原理编译原理中间代码中间代码编译结束，知道每个过程的活动记录的长度，将其编译结束，知道每个过程的活动记录的长度，将其填写到相应的过程表中，运行时，调用哪个过程，填写到相应的过程表中，运行时，调用哪个过程，就在运行栈顶，推进那个过程的活动记录（栈箭头就在运行栈顶，推

21、进那个过程的活动记录（栈箭头加上活动记录长度）。加上活动记录长度）。f:=e+i*j;*ijt1+et1t2:=t2f10/7/202225编译原理编译原理运行时刻存储分配策略运行时刻存储分配策略分配策略是：分配策略是：静态分配；静态分配；栈式分配，或称栈式动态分配；栈式分配，或称栈式动态分配；堆式分配，或称堆式动态分配。堆式分配，或称堆式动态分配。采用哪种分配策略是由源语言的语义决定的。采用哪种分配策略是由源语言的语义决定的。10/7/202226编译原理编译原理静态存储分配静态存储分配静态存储分配：在静态存储分配：在由由实现对存储实现对存储空间的管理和为源程序中的变量分配存储的方法。空间的

22、管理和为源程序中的变量分配存储的方法。静态存储分配的条件静态存储分配的条件如果在编译时能够确定源程序中变量在运行时的数据如果在编译时能够确定源程序中变量在运行时的数据空间大小，且运行时不改变，那么就可以采用静态存空间大小，且运行时不改变，那么就可以采用静态存储分配方法。储分配方法。允许局部名字的值在过程停止活动后仍然保持，也允许局部名字的值在过程停止活动后仍然保持，也就是当控制再次进入程序时，局部名字的值同控制就是当控制再次进入程序时，局部名字的值同控制上次离开时一样。上次离开时一样。还能用控制栈进还能用控制栈进行控制吗？行控制吗？10/7/202227编译原理编译原理静态存储分配的局限静态存

23、储分配的局限在编译时刻知道数据目标的大小和它们在内存位置在编译时刻知道数据目标的大小和它们在内存位置上的约束；上的约束；不能递归调用过程（一个过程的两个活动的生存期不能递归调用过程（一个过程的两个活动的生存期不相交不相交,一个过程的所有活动可以使用同一个活动记一个过程的所有活动可以使用同一个活动记录）；录）；不能动态地建立数据结构。不能动态地建立数据结构。10/7/202228编译原理编译原理静态存储分配策略静态存储分配策略CNSUME目标代码目标代码PRDUCE目标代码目标代码Char *50 buf int next char cChar *80 buffer int nextCnsume

24、活动记录活动记录prduce活动记录活动记录目标代码目标代码静态数据静态数据10/7/202229编译原理编译原理静态存储分配策略静态存储分配策略由于每个变量所需空间的大小在编译时已知，因此由于每个变量所需空间的大小在编译时已知，因此可以用简单的方法给变量分配目标地址。可以用简单的方法给变量分配目标地址。开辟一数据区。（首地址在加载时定）开辟一数据区。（首地址在加载时定）按编译顺序给每个模块分配存储空间。按编译顺序给每个模块分配存储空间。在模块内部按顺序给模块的变量分配存储，一般用相在模块内部按顺序给模块的变量分配存储，一般用相对地址，所占数据区的大小由变量类型决定。对地址，所占数据区的大小由

25、变量类型决定。目标地址填入变量的符号表中。目标地址填入变量的符号表中。10/7/202230编译原理编译原理10/7/202231编译原理编译原理动态存储分配动态存储分配在在由由实现对存储空间的实现对存储空间的组织与管理，和为源程序中的变量分配存储的方组织与管理，和为源程序中的变量分配存储的方法。法。特点特点编译时不能具体确定程序所需数据空间编译时不能具体确定程序所需数据空间编译程序生成有关存储分配的目标代码编译程序生成有关存储分配的目标代码实际上的分配要在目标程序运行时进行实际上的分配要在目标程序运行时进行分程序结构，且允许递归调用的语言：分程序结构，且允许递归调用的语言：10/7/2022

26、32编译原理编译原理栈式存储分配策略栈式存储分配策略基于控制栈的原理：基于控制栈的原理：存储空间被组织成栈，活动记存储空间被组织成栈，活动记录的录的分别对应于活动的分别对应于活动的。与静态分配不同的是，在每次活动中把局部名字和与静态分配不同的是，在每次活动中把局部名字和新的存储单元绑定，在活动结束时，活动记录从栈新的存储单元绑定，在活动结束时，活动记录从栈中弹出，因而局部名字的存储空间也随之消失。中弹出，因而局部名字的存储空间也随之消失。分配策略分配策略:整个数据区为一个堆栈，整个数据区为一个堆栈，当进入一个过程时，在栈顶为其分配一个数据区。当进入一个过程时，在栈顶为其分配一个数据区。退出时，

27、撤消过程数据区。退出时，撤消过程数据区。10/7/202233编译原理编译原理10/7/202234编译原理编译原理10/7/202235编译原理编译原理 10/7/202236编译原理编译原理9、静夜四无邻，荒居旧业贫。22.10.722.10.7Friday,October 07,202210、雨中黄叶树，灯下白头人。5:10:465:10:465:1010/7/2022 5:10:46 AM11、以我独沈久，愧君相见频。22.10.75:10:465:10Oct-227-Oct-2212、故人江海别，几度隔山川。5:10:465:10:465:10Friday,October 07,20

28、2213、乍见翻疑梦，相悲各问年。22.10.722.10.75:10:465:10:46October 7,202214、他乡生白发，旧国见青山。2022年10月7日星期五上午5时10分46秒5:10:4622.10.715、比不了得就不比，得不到的就不要。2022年10月上午5时10分22.10.75:10October 7,202216、行动出成果，工作出财富。2022年10月7日星期五5时10分46秒5:10:467 October 202217、做前，能够环视四周；做时，你只能或者最好沿着以脚为起点的射线向前。上午5时10分46秒上午5时10分5:10:4622.10.79、没有失败

29、，只有暂时停止成功！。22.10.722.10.7Friday,October 07,202210、很多事情努力了未必有结果，但是不努力却什么改变也没有。5:10:465:10:465:1010/7/2022 5:10:46 AM11、成功就是日复一日那一点点小小努力的积累。22.10.75:10:465:10Oct-227-Oct-2212、世间成事，不求其绝对圆满，留一份不足，可得无限完美。5:10:465:10:465:10Friday,October 07,202213、不知香积寺，数里入云峰。22.10.722.10.75:10:465:10:46October 7,202214、意

30、志坚强的人能把世界放在手中像泥块一样任意揉捏。2022年10月7日星期五上午5时10分46秒5:10:4622.10.715、楚塞三湘接，荆门九派通。2022年10月上午5时10分22.10.75:10October 7,202216、少年十五二十时，步行夺得胡马骑。2022年10月7日星期五5时10分46秒5:10:467 October 202217、空山新雨后，天气晚来秋。上午5时10分46秒上午5时10分5:10:4622.10.79、杨柳散和风，青山澹吾虑。22.10.722.10.7Friday,October 07,202210、阅读一切好书如同和过去最杰出的人谈话。5:10:4

31、65:10:465:1010/7/2022 5:10:46 AM11、越是没有本领的就越加自命不凡。22.10.75:10:465:10Oct-227-Oct-2212、越是无能的人，越喜欢挑剔别人的错儿。5:10:465:10:465:10Friday,October 07,202213、知人者智，自知者明。胜人者有力，自胜者强。22.10.722.10.75:10:465:10:46October 7,202214、意志坚强的人能把世界放在手中像泥块一样任意揉捏。2022年10月7日星期五上午5时10分46秒5:10:4622.10.715、最具挑战性的挑战莫过于提升自我。2022年10月

32、上午5时10分22.10.75:10October 7,202216、业余生活要有意义，不要越轨。2022年10月7日星期五5时10分46秒5:10:467 October 202217、一个人即使已登上顶峰，也仍要自强不息。上午5时10分46秒上午5时10分5:10:4622.10.7MOMODA POWERPOINTLorem ipsum dolor sit,eleifend nulla ac,fringilla purus.Nulla iaculis tempor felis amet,consectetur adipiscing elit.Fusce id urna blanditut cursus.感 谢 您 的 下 载 观 看感 谢 您 的 下 载 观 看专家告诉