运行时的存储组织及管理资料教学课件

运行时的存储组织及管理运行时的存储组织及管理7/26/20241编译器的应用模型编译器的应用模型出出错错处处理理语法分析程序语法分析程序语义分析程序语义分析程序目标代码生成程序目标代码生成程序词法分析程序词法分析程序中间代码生成程序中间代码生成程序代码优化程序代码优化程序表表格格管管理理编译的前端编译的前端（FrontEnd）编译的后端编译的后端（BackEnd）7/26/20242编译原理编译原理运行时的存储组织及管理运行时的存储组织及管理概述概述存储组织存储组织运行时的存储分配策略运行时的存储分配策略静态存储分配静态存储分配动态存储分配动态存储分配对非局部名字的访问对非局部名字的访问参数传递参数传递7/26/20243编译原理编译原理运行时的存储组织及管理运行时的存储组织及管理 计算环境 运行时的环境 计算 目标代码当词法分析扫描得到标识符，并将它填入符号表的当词法分析扫描得到标识符，并将它填入符号表的过程中需要给识别出来的标识符分配内存空间。过程中需要给识别出来的标识符分配内存空间。源程序由一组源程序由一组过程过程过程过程按某种规则组成。按某种规则组成。过程的一次执行称作一次过程的一次执行称作一次活动活动活动活动。在过程的语句序列执行之前，过程中访问的对象构在过程的语句序列执行之前，过程中访问的对象构成此过程的运行环境，由运行支持程序组织好。成此过程的运行环境，由运行支持程序组织好。编译程序根据如何组织运行环境而生成目标代码。编译程序根据如何组织运行环境而生成目标代码。映射源程序7/26/20244编译原理编译原理运行时环境的作用运行时环境的作用目标程序运行时所需存储空间的组织与管理以及源目标程序运行时所需存储空间的组织与管理以及源程序中变量存储空间的分配。程序中变量存储空间的分配。7/26/20245编译原理编译原理有关源程序中的一些问题有关源程序中的一些问题问题的提出：如何问题的提出：如何构造运行程序的策略和方法构造运行程序的策略和方法过程过程活动树活动树控制栈控制栈说明的作用域说明的作用域名字的绑定名字的绑定构造运行程序和源程序有关的一些问题构造运行程序和源程序有关的一些问题7/26/20246编译原理编译原理过程过程源程序由一组过程组成，不同的程序设计语言，由源程序由一组过程组成，不同的程序设计语言，由过程构成源程序的方法不同。过程构成源程序的方法不同。构成源程序的两个过程行文，要么是嵌套的，要么构成源程序的两个过程行文，要么是嵌套的，要么是不相交的。是不相交的。7/26/20247编译原理编译原理programsort(input,output);vara:array0.10ofinteger;procedurereadarry;vari:integer;beginfori:=1to9doread(ai)end;functionpartition(y,z:integer):integer;vari,j,x,v:integer;beginend;procedurequicksort(m,n:integer)vari:integer;beginif(nm)thenbegini:=partition(m,n);quicksort(m,i-1);quicksort(i+1,n)endendbegina0:=-9999;a10:=9999;readarray;quicksort(1,9)end7/26/20248编译原理编译原理活动树活动树程序执行期间的控制流：程序执行期间的控制流：程序执行的控制是连续的：在任何一步，控制都处于程序的某程序执行的控制是连续的：在任何一步，控制都处于程序的某一点一点过程的每一次执行都是从过程体的开头过程的每一次执行都是从过程体的开头开始，并最终把控制返开始，并最终把控制返回到紧接着该过程被调用点的后面。回到紧接着该过程被调用点的后面。过程的一次活动过程的一次活动:过程体的每一次执行。过程体的每一次执行。过程过程p的一次活动的的一次活动的生存期生存期生存期生存期:在该过程体的执行中的第一步和在该过程体的执行中的第一步和最后一步之间的一序列步骤的最后一步之间的一序列步骤的执行时间执行时间执行时间执行时间，其中包括执行过程，其中包括执行过程p所调用的过程的执行时间，以及这些过程所调用的过程的所调用的过程的执行时间，以及这些过程所调用的过程的执执执执行时间行时间行时间行时间，如此等等。，如此等等。一个过程是递归的，如果同一过程的一次新的活动可以在前一个过程是递归的，如果同一过程的一次新的活动可以在前面活动结束以前开始。面活动结束以前开始。7/26/20249编译原理编译原理活动树活动树为什么过程的活动可以用树形结构描述？为什么过程的活动可以用树形结构描述？过程活动的特点：过程活动的特点：每当控制流从过程每当控制流从过程p的活动进入到过程的活动进入到过程q的活动中后，的活动中后，它将返回到过程它将返回到过程p的同一次活动中。的同一次活动中。也就是说，如果也就是说，如果a和和b是两个过程活动，那么它们的生是两个过程活动，那么它们的生存期要么是不重叠的，要么是嵌套的。存期要么是不重叠的，要么是嵌套的。在树形结构中，节点间的关系就反映了过程之间的在树形结构中，节点间的关系就反映了过程之间的关系：关系：父子关系：嵌套父子关系：嵌套兄弟关系：先后兄弟关系：先后7/26/202410编译原理编译原理活动树活动树用一颗树来描绘控制进入和离开活动的途径。这祥用一颗树来描绘控制进入和离开活动的途径。这祥的树称作活动树。的树称作活动树。每个节点代表过程的一个活动每个节点代表过程的一个活动根节点代表主程序的活动根节点代表主程序的活动当且仅当控制流从活动当且仅当控制流从活动a进入活动进入活动b时，节点时，节点a是是b的父的父节点节点当且仅当当且仅当a的生存期先于的生存期先于b的生存期时，的生存期时，a节点处于节点处于b结结点的左边点的左边一个结点代表一个唯一的活动，一个结点代表一个唯一的活动，且每一个活动只有且每一个活动只有一个结点表示，当控制进入某一个活动时，可以直一个结点表示，当控制进入某一个活动时，可以直接说，控制在这个结点上。接说，控制在这个结点上。7/26/202411编译原理编译原理programsort(input,output);vara:array0.10ofinteger;procedurereadarry;vari:integer;beginfori:=1to9doread(ai)end;functionpartition(y,z:integer):integer;vari,j,x,v:integer;beginend;procedurequicksort(m,n:integer)vari:integer;beginif(nm)thenbegini:=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)7/26/202412编译原理编译原理控制栈控制栈程序的控制流对应于从活动树根节点开始的深度优先遍历。程序的控制流对应于从活动树根节点开始的深度优先遍历。（从左至右）（从左至右）活动树表示了完整的程序控制的先后顺序。在真正运行过程活动树表示了完整的程序控制的先后顺序。在真正运行过程中，活动树并不是真实存在的数据结构。中，活动树并不是真实存在的数据结构。在程序运行过程中，我们只需要保存那些在程序运行过程中，我们只需要保存那些活跃着的过程活跃着的过程活跃着的过程活跃着的过程。控制栈控制栈控制栈的基本思想：控制栈的基本思想：当一个活动开始执行时，把代表这个活动的结点推进栈；当这当一个活动开始执行时，把代表这个活动的结点推进栈；当这个活动结束时，把代表这个活动的结点从栈中弹出。个活动结束时，把代表这个活动的结点从栈中弹出。控制栈只能表示活动树的一部分控制栈只能表示活动树的一部分活动树只是逻辑上存在的活动树只是逻辑上存在的类似于语法分析树类似于语法分析树7/26/202413编译原理编译原理栈和活动树的变化栈和活动树的变化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)7/26/202414编译原理编译原理控制栈控制栈控制栈中的活动都是活跃的，当前控制进入的活动控制栈中的活动都是活跃的，当前控制进入的活动在栈顶，从栈顶活动到栈底活动的活动序列是从活在栈顶，从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的结点序列。动树上当前结点通向根的路径上的结点序列。从栈底活动到栈顶活动的活动序列表示了活动的生从栈底活动到栈顶活动的活动序列表示了活动的生存期的存期的嵌套关系。嵌套关系。嵌套关系。嵌套关系。结论：扩充控制栈可用来实现如结论：扩充控制栈可用来实现如Pascal语言的栈式语言的栈式存储分配。（控制栈中存储活动记录）存储分配。（控制栈中存储活动记录）7/26/202415编译原理编译原理声明的作用域声明的作用域声明语句是把名字与名字的属性信息绑定在一起的语法结构。声明语句是把名字与名字的属性信息绑定在一起的语法结构。说明的作用域是一个说明起作用的范围说明的作用域是一个说明起作用的范围(源程序行文源程序行文)。一个名字在源程序行文中可能有几处说明，语言的一个名字在源程序行文中可能有几处说明，语言的作用域规作用域规作用域规作用域规则则则则规定了在语句序列中引用的一个名字是在何处说明的名字。规定了在语句序列中引用的一个名字是在何处说明的名字。编译时，处理说明时，把名字及其属性信息填写进符号表；编译时，处理说明时，把名字及其属性信息填写进符号表；处理引用时，查找这个名字的属性信息，符号表管理程序根处理引用时，查找这个名字的属性信息，符号表管理程序根据语言的作用域规则，返回其作用域中绑定的属性信息。据语言的作用域规则，返回其作用域中绑定的属性信息。7/26/202416编译原理编译原理名字与存储的绑定名字与存储的绑定名字与存储单元的绑定是指把源程序中的名字与存储单元的绑定是指把源程序中的数据名字数据名字数据名字数据名字映射到映射到目标机存储单元目标机存储单元目标机存储单元目标机存储单元的过程。的过程。环境环境环境环境把名字映射到一个存储单元上；把名字映射到一个存储单元上；状态状态状态状态把存储单把存储单元映射到那里所存放的值上。元映射到那里所存放的值上。或者说，环境把一个名字映射为一个左值，而状态或者说，环境把一个名字映射为一个左值，而状态把一个左值映射为一个右值。把一个左值映射为一个右值。7/26/202417编译原理编译原理名字与存储的绑定名字与存储的绑定名字名字存存储单储单元元值值存存储储分配分配程序运行程序运行环环境境状状态态l-valuer-value7/26/202418编译原理编译原理静静态态概念概念动态对应动态对应过过程定程定义义过过程活程活动动名字名字说说明明名字的名字的绑绑定定说说明的作用域明的作用域活活动动的生存期的生存期7/26/202419编译原理编译原理存储组织存储组织运行时刻内存的划分：假定编译器从操作系统得到运行时刻内存的划分：假定编译器从操作系统得到一块存储区，运行时的存储空间要划分成块一块存储区，运行时的存储空间要划分成块:生成的目标代码生成的目标代码;数据对象数据对象;记录过程活动的控制栈对应的数据结构记录过程活动的控制栈对应的数据结构7/26/202420编译原理编译原理目目标标代代码码静静态态数据数据栈栈堆堆1.编译编译后知道目后知道目标标代代码码的大小。的大小。放入静放入静态态确定的区域中确定的区域中2.某些数据某些数据对对象的象的长长度也可以在度也可以在编译编译时时知道，也可以放在静知道，也可以放在静态态区域中。主区域中。主程序中的数据：程序中的数据：c,FORTRAN3.栈栈控制控制栈栈：Pascal,c4.堆堆开开销销比比栈栈大大(分配和分配和释释放方放方式式)：Pascal,c7/26/202421编译原理编译原理活动记录活动记录把过程的一个活动所需要的信息组织成一块连续的把过程的一个活动所需要的信息组织成一块连续的存储单元，称为活动记录。存储单元，称为活动记录。一个活动所需要的信息的每个数据项有相同的生存一个活动所需要的信息的每个数据项有相同的生存期，因此，组织成一个活动记录是很自然的。期，因此，组织成一个活动记录是很自然的。对于对于pascal语言来说，运行过程中，当调用一个过程语言来说，运行过程中，当调用一个过程时，在栈顶构筑它的活动记录；当这个过程的活动时，在栈顶构筑它的活动记录；当这个过程的活动执行完后，把它从栈顶弹出。执行完后，把它从栈顶弹出。7/26/202422编译原理编译原理活动记录活动记录控制链控制链:指向调用过程活动的活动指向调用过程活动的活动记录。记录。访问链：指向本活动要访问的非访问链：指向本活动要访问的非局部数据所在的活动记录。局部数据所在的活动记录。保存机器状态：调用过程活动在保存机器状态：调用过程活动在调用点的机器状态，包括计数器，调用点的机器状态，包括计数器，各种寄存器的值。各种寄存器的值。局部数据：过程中定义的局部量。局部数据：过程中定义的局部量。临时变量：编译产生。临时变量：编译产生。返回返回值值实实在参数在参数控制控制链链访问链访问链保存机器状保存机器状态态局部数据局部数据临时变临时变量量7/26/202423编译原理编译原理编译时刻的局部数据的设计编译时刻的局部数据的设计PROCEDUREsub(x,y:real);VARi,j:integer;a:ARRAY1.5OFreal;e,f:real;BEGINf:=e+i*j;END;名字名字形形类类型型偏移量偏移量x形形real1y形形real2iint20jint21a array22ereal27freal28符号表符号表7/26/202424编译原理编译原理中间代码中间代码编译结束，知道每个过程的活动记录的长度，将其编译结束，知道每个过程的活动记录的长度，将其填写到相应的过程表中，运行时，调用哪个过程，填写到相应的过程表中，运行时，调用哪个过程，就在运行栈顶，推进那个过程的活动记录（栈箭头就在运行栈顶，推进那个过程的活动记录（栈箭头加上活动记录长度）。加上活动记录长度）。f:=e+i*j;*ijt1+et1t2:=t2f7/26/202425编译原理编译原理运行时刻存储分配策略运行时刻存储分配策略分配策略是：分配策略是：静态分配；静态分配；栈式分配，或称栈式动态分配；栈式分配，或称栈式动态分配；堆式分配，或称堆式动态分配。堆式分配，或称堆式动态分配。采用哪种分配策略是由源语言的语义决定的。采用哪种分配策略是由源语言的语义决定的。7/26/202426编译原理编译原理静态存储分配静态存储分配静态存储分配：在静态存储分配：在编译阶段编译阶段编译阶段编译阶段由由编译程序编译程序编译程序编译程序实现对存储实现对存储空间的管理和为源程序中的变量分配存储的方法。空间的管理和为源程序中的变量分配存储的方法。静态存储分配的条件静态存储分配的条件如果在编译时能够确定源程序中变量在运行时的数据如果在编译时能够确定源程序中变量在运行时的数据空间大小，且运行时不改变，那么就可以采用静态存空间大小，且运行时不改变，那么就可以采用静态存储分配方法。储分配方法。允许局部名字的值在过程停止活动后仍然保持，也允许局部名字的值在过程停止活动后仍然保持，也就是当控制再次进入程序时，局部名字的值同控制就是当控制再次进入程序时，局部名字的值同控制上次离开时一样。上次离开时一样。还能用控制栈进还能用控制栈进行控制吗？行控制吗？7/26/202427编译原理编译原理静态存储分配的局限静态存储分配的局限在编译时刻知道数据目标的大小和它们在内存位置在编译时刻知道数据目标的大小和它们在内存位置上的约束；上的约束；不能递归调用过程（一个过程的两个活动的生存期不能递归调用过程（一个过程的两个活动的生存期不相交不相交,一个过程的所有活动可以使用同一个活动记一个过程的所有活动可以使用同一个活动记录）；录）；不能动态地建立数据结构。不能动态地建立数据结构。7/26/202428编译原理编译原理静态存储分配策略静态存储分配策略CNSUME目目标代代码PRDUCE目目标代代码Char*50bufintnextcharcChar*80bufferintnextCnsume活活动记录prduce活活动记录目目标标代代码码静静态态数据数据7/26/202429编译原理编译原理静态存储分配策略静态存储分配策略由于每个变量所需空间的大小在编译时已知，因此由于每个变量所需空间的大小在编译时已知，因此可以用简单的方法给变量分配目标地址。可以用简单的方法给变量分配目标地址。开辟一数据区。（首地址在加载时定）开辟一数据区。（首地址在加载时定）按编译顺序给每个模块分配存储空间。按编译顺序给每个模块分配存储空间。在模块内部按顺序给模块的变量分配存储，一般用相在模块内部按顺序给模块的变量分配存储，一般用相对地址，所占数据区的大小由变量类型决定。对地址，所占数据区的大小由变量类型决定。目标地址填入变量的符号表中。目标地址填入变量的符号表中。7/26/202430编译原理编译原理7/26/202431编译原理编译原理动态存储分配动态存储分配在在目标程序运行阶段目标程序运行阶段目标程序运行阶段目标程序运行阶段由由目标程序目标程序目标程序目标程序实现对存储空间的实现对存储空间的组织与管理，和为源程序中的变量分配存储的方法。组织与管理，和为源程序中的变量分配存储的方法。特点特点编译时不能具体确定程序所需数据空间编译时不能具体确定程序所需数据空间编译程序生成有关存储分配的目标代码编译程序生成有关存储分配的目标代码实际上的分配要在目标程序运行时进行实际上的分配要在目标程序运行时进行分程序结构，且允许递归调用的语言：分程序结构，且允许递归调用的语言：栈式动态存栈式动态存栈式动态存栈式动态存储分配储分配储分配储分配7/26/202432编译原理编译原理栈式存储分配策略栈式存储分配策略基于控制栈的原理：基于控制栈的原理：存储空间被组织成栈，活动记存储空间被组织成栈，活动记录的录的推入和弹出推入和弹出推入和弹出推入和弹出分别对应于活动的分别对应于活动的开始和结束开始和结束开始和结束开始和结束。与静态分配不同的是，在每次活动中把局部名字和与静态分配不同的是，在每次活动中把局部名字和新的存储单元绑定，在活动结束时，活动记录从栈新的存储单元绑定，在活动结束时，活动记录从栈中弹出，因而局部名字的存储空间也随之消失。中弹出，因而局部名字的存储空间也随之消失。分配策略分配策略:整个数据区为一个堆栈，整个数据区为一个堆栈，当进入一个过程时，在栈顶为其分配一个数据区。当进入一个过程时，在栈顶为其分配一个数据区。退出时，撤消过程数据区。退出时，撤消过程数据区。7/26/202433编译原理编译原理7/26/202434编译原理编译原理7/26/202435编译原理编译原理Thanks for your time!Questions&Answers7/26/202436编译原理编译原理谢谢你的阅读v知识就是财富v丰富你的人生