7编译原理之运行时刻环境ppt课件

1、第七章运转时辰环境湖南大学计算机与通讯学院软件学院编译器的一些问题变量的存储位置如何分配？名字的作用域如何实现？过程调用如何实现？参数传送如何实现？这些问题需求依托运转时环境来辅助处理。运转时辰环境运转时辰环境为数据分配安排存储位置确定访问变量时运用的机制过程之间的衔接参数传送和操作系统、输入输出设备相关的其它接口主题存储管理：栈分配、堆管理、渣滓回收对变量、数据的访问存储分配的典型方式目的程序的代码放置在代码区，通常位于存储的低端静态区、堆区、栈区分别放置不同类型生命期的数据值,实际中栈向较低地址方向增长堆向较高方向增长。图7-1编译的结果全局/静态变量共享*从如今开场要留意，为使我们能在一

2、切的例子中方便地运用正的偏移量,栈向较高地址方向增长，即顶是在最下端。0X00H0XFFFFH.静态和动态存储分配静态分配编译器在编译时辰就可以做出存储分配决议，不需求思索程序运转时辰的情形，如：静态变量言语中static变量全局变量动态分配栈式存储：过程的部分名字采用栈式存储和过程的调用/前往同步进展分配和回收，值的生命期和过程生命期一样堆heap存储：有些数据生命期比相应过程调用的生命期更长，常分配在一个可重用存储的“堆中。堆和渣滓回收堆是虚拟内存的一个区域，它允许对象或其他数据元素在被创建时获得存储空间，并在数据变得无效时释放该存储空间渣滓回收：检测出堆中无用的数据元素，释放它们的空间手

3、工进展回收程序员渣滓回收机制，如：栈式分配内容：活动树活动记录调用(代码)序列栈中的变长数据活动树过程调用过程活动在时间上总是嵌套的：后调用的先前往(LIFO)因此可以用栈式分配来处置过程活动所需求的内存空间。程序运转的一切过程活动可以用树表示每个结点对应于一个过程活动根结点对应于main过程的活动过程p的某次活动对应的结点的子结点对应于此次活动调用的各个过程活动从左向右，表示调用的先后顺序活动树的例子快速排序1活动树的例子快速排序程序：P260，图7-2过程调用前往序列和活动树的前序后序遍历对应假定当前活动对应结点N，那么一切尚未终了的结点对应于N及其祖先结点。活动记录过程调用和前往由控制栈

4、进展管理过程活动记录：当调用过程或函数时，为其部分数据动态分配的存储区活动记录按照活动的开场时间，从栈底到栈顶陈列图活动记录框架计算中间结果部分变量活动记录控制链：指向调用者的活动记录固定长度部分访问链：活动记录中指向上一级活动记录(包含嵌套的环境定义的活动记录)的指针保管的机器形状：此次调用前的机器形状信息，如：前往地址及一些存放器的值运转时辰栈的例子例：快速排序a11为全局变量main没有部分变量r有部分变量iq的部分变量i，和参数m,n。Main的活动记录调用序列调用序列(calling sequence)为活动记录分配空间，填写记录中的信息；前往序列(return sequence)恢

5、复机器形状，使调用者继续运转。调用序列会分割到调用者和被调用者中。根据源言语、目的机器、操作系统的限制，可以有不同的分割方案把代码尽能够放在被调用者中。调用/前往序列的要求数据方面可以把参数正确地传送给被调用者可以把前往值传送给调用者控制方面可以正确转到被调用者的代码的开场位置可以正确转回调用者的调用位置的下一条指令调用序列和活动记录的规划相关活动记录的规划原那么调用者和被调用者之间传送的值放在被调用者记录的开场位置固定长度的项放在中间位置控制链、访问链、机器形状字段早期不知道大小的项在活动记录尾部干脆将固定长度的部分变量也放入该段栈顶指针通常指向固定长度字段的末端top_sp调用代码序列的例

6、子Calling sequence调用序列调用者计算真实参数的值将前往地址和原top_sp控制链存放到被调用者的活动记录中。调用者添加top_sp的值越过了调用者的部分数据、暂时变量、被调用者的参数、机器形状字段被调用者保管存放器值和其他形状字段被调用者初始化部分数据、开场运转。Return sequence 前往序列被调用者将前往值放到和参数相邻的位置恢复top_sp和存放器，跳转到前往地址。栈中的变长数据假设数据对象的生命期局限于过程活动的生命期，就可以分配在运转时辰栈中。top指向实践的栈顶top_sp用于寻觅顶层记录的定长字段框架指针例 利用Euclid算法的简单递归算法，计算两个非负

7、整数的最大公约数。程序清单 C代码#include int x, y;int gcd(int u, int v) if (v=0) return u; else return gcd(v, u%v);main() scanf(“%d%d, &x, &y); printf(“%dn, gcd(x,y); return 0; 假设输入为，试画出运转的活动树试画出运转时栈变化过程main()gcd(15,10)gcd(10,5)gcd(5,0)第3个调用时的环境如图7-2所示。x:15y:10u:15v:10控制链前往地址部分变量u:10v:5控制链前往地址部分变量u:5v:0控制链前往地址部分变量

8、自在空间Top_sptop全局静态区域main的活动记录第一次调用gcd时的活动记录第二次调用gcd时的活动记录第三次调用gcd时的活动记录栈的生长方向基于栈的环境main()gcd(15,10)gcd(10,5)gcd(5,0)前往值为基于栈的运转时环境留意：同一个过程的不同活动对应的活动记录的大小完全一样；新的活动记录总是在栈顶参与；其控制链总是指向先前的活动记录的控制链；top_sp指向当前活动记录的控制链；调用前往时，将按顺序从栈中删去每个活动记录；当在main中执行printf语句时，环境中只保管了main的活动记录和全局/静态区域。7.3 栈中非部分数据的访问7.3.1无嵌套过程时

9、的数据访问无嵌套过程时的数据访问例：言语不允许嵌套过程声明，变量要么在函数内定义，要么全局地定义C言语中函数对变量的访问部分变量：在当前活动记录内，可经过top_sp指针加上相对地址来访问全局/静态变量：在静态区，地址在编译时可知C言语允许函数参数参数中只需求包括函数代码的起始地址。在函数中访问变量的方式很简单，不需求思索过程是如何激活的。C言语中活动记录中无需访问链7.3 基于栈的运转时环境1) 对称号的访问在基于栈的环境中，要访问参数和部分变量，可用当前框架指针(top_sp)的偏移量实现。在大多数的言语中，每个部分声明的偏移量可由编译程序静态地计算出来。由于过程的声明在编译时是固定的，而

10、且为每个声明分配的存储器大小也根据其数据类型而固定。例 思索C过程void f(int x, char c) int a10; double y; . . . 对f调用的活动记录ya9a1a0前往地址控制链cxx偏移量top_spc偏移量a偏移量y偏移量*此处在前往地址下省略了被保管的形状等信息整型4个字节、地址4个字节、字符1个字节、双精度浮点数8个字节，那么偏移量为：称号偏移量 x-9 c-8 a+0 y+40 ai的地址为：0+4*i+ top_sp。在基于栈的环境中，非部分的和静态的名字的地址都是固定的静态地址，可以直接访问。*留意在本章内，栈是往下面大端生长的。非部分数据的访问嵌套过

11、程PASCAL言语允许过程嵌套定义，且遵照静态作用域规那么代码运转时，对变量的访问应指向运转栈中最上层的同名变量。问题：变量不一定在当前活动记录中，如何确定其位置？思索：符号表中存储了变量的偏移量，因此只需求确定的活动记录。子问题：用嵌套层次可以完全处理这个问题吗？非部分数据的访问嵌套过程问题：用调用层次可以完全处理这个问题吗？void A()intx,y;voidB()int b;x = b+y;voidC()B(); C();B的活动记录C的活动记录A的活动记录当A调用C，C又调用B时:不能！A,B的层次差是，但B的控制链并没有直接指向A处理方法：引入访问链指向过程的定义环境7.3.3 一

12、个支持嵌套过程声明的言语最新的支持嵌套过程的典型言语之一：MLML是一种函数式言语，变量一旦声明并初始化就不会再改动有少数例外，如：数组元素可经过特殊的函数调用改动变量定义并初始化为不可更改的值的语句方式： =函数定义的语法：Fun ()=函数体(body)定义的语法：Let in end嵌套深度嵌套深度是正文概念，可根据源程序静态地确定不内嵌于任何其他过程中的过程，嵌套深度为1嵌套在深度为i的过程中的过程，深度为i+1.深度为1sort深度为2readArray，exchange，quicksort深度为3partition图7-10 一个运用嵌套函数声明的ML风格的quicksort访问链

13、显式表显式表访问链引入访问链的目的：访问非部分数据假设过程p在声明时嵌套在过程q的声明中，那么p的活动记录中的访问链指向最上层最新的q的活动记录。从栈顶活动记录开场，访问链构成了一个链路，嵌套深度逐一递减。设深度为np的过程p访问变量x，而变量x在深度为nq的过程中声明，那么从当前活动记录出发，沿访问链前进np-nq次找到活动记录其中的x就是要找的变量位置x相对于该活动记录的偏移量在编译时辰知np和-nq在编译时辰知；访问链的例子P270图7-11 用来查找非部分数据的访问链sort活动记录访问链的处置明确调用过程与声明嵌套深度的关系当过程q调用过程p时，P访问链如何设置？把p的声明嵌套深度n

14、p与nq的关系分为大于，等于，小于三种情况思索p的声明嵌套深度大于q，p必然在q中直接定义，否那么不满足作用域规那么，那么p的访问链指向当前活动记录(即父亲直接调用孩子)递归调用：p=q 。p的活动记录的访问链等于q当前记录的访问链(即本身等于本身)p的声明嵌套深度小于q的深度：此时必然有过程r，p直接在r中定义，而q嵌套在r中。此时应让p的访问链指向r的活动记录。(即q是p的侄子系的，r是p的父亲)rpq.7.3.6 过程型参数的访问链有些言语允许过程作为参数，如：言语例：tiny编译器中语义分析程序analyze.c的transverse函数声明如下：static void travers

15、e( TreeNode * t, void (* preProc) (TreeNode *), void (* postProc) (TreeNode *) )构建符号表前序遍历语法树traverse(syntaxTree,insertNode,nullProc);类型检查时后序遍历语法树traverse(syntaxTree,nullProc,checkNode);7.3.6 过程型参数的访问链当一个过程作为参数传送给另一个过程，并且随后调用了这个参数，有能够并不知道在程序中出现的上下文后果：不知道如何设置的访问链处理方法： 在传送过程指针参数时，过程型参数中不仅包含过程的代码指针(IP)，

16、还包括正确的访问链AL)。7.3.6 过程型参数的访问链图-12 运用函数参数的ML程序的概要f是一个函数参数对的援用d被用作函数参数7.3.6 过程型参数的访问链由于d在c中定义7.3.8 显示表display)用访问链访问数据时，假设嵌套深度大，那么访问的效率差。显示表：运用数组d为每个嵌套深度保管一个指针指针di指向栈中最高的对应于嵌套深度为i的的活动记录。假设程序p中访问嵌套深度为i的过程q中变量x，那么di直接指向相应的q活动记录；显示表的维护调用过程p时，在p的活动记录中保管原dnp的值，并将dnp设置为p的该次活动记录。从p前往时，恢复dnp的值。显示表举例q(1,9)调用q(1

17、,3)时，q的深度为2例： ML风格的quicksort显示表举例q(1,3)调用p，p的深度为3q调用e，e的深度为2例： ML风格的quicksort嵌套层次构造分析伪代码Display(1)main-(2)P-(3)Q-(4)R主程序的活动记录 d1display栈顶1主程序的活动记录P 的活动记录 d1d2display栈顶2栈栈主程序-P-Q-R主程序的活动记录P 的活动记录 Q 的活动记录R 的活动记录主程序的活动记录 P 的活动记录Q 的活动记录 displayd1d2d3 d1d2d3 display34栈顶栈栈栈顶堆管理堆空间用于存放生命周期不确定、或者生存到被显式删除为止的

18、数据对象，例：new生成的对象可以生存到被delete为止Malloc恳求的空间生存到被free为止存储管理器分配/回收堆区空间的子系统根据言语而定C、C+需求手动回收空间Java可以自动回收空间渣滓搜集存储管理器的根本功能分配：为每个内存恳求分配一段延续的、适当大小的堆空间。首先从空闲堆空间分配；假设没有可分配的堆空间，那么从操作系统中获得延续的虚拟内存来添加堆空间；如空间已用完，那么将空间耗尽的音讯反响给运用程序回收：把被回收的空间前往空闲空间缓冲池，以满足以后的分配恳求。期望的存储管理器特性空间效率使程序所需堆空间最小实现手段：最小化存储碎片程序效率充分利用存储子系统，提高程序运转效率在

19、存储子系统中，不同的层次访问速度不一样尽能够多的利用高访问速度的存储器件，可大幅度提高效率低开销最小化分配/收回内存的开销即破费在分配和回收上的执行时间在总运转时间中所占的比例注：分配的开销由小型恳求决议，管理大型对象的开销相对不重要 一次内存访问中，机器首先在最低层的存储中寻觅数据，假设数据不在那里那么到上一层中寻觅。程序的部分性大部分程序呈现高度的部分性即程序的大部分运转时间破费在相对较小的一部分代码时间部分性假设一个程序访问的存储位置很能够将在一个很短的时间段内被再次访问，称其具有时间部分性空间部分性假设被访问的存储位置的临近位置很能够将在一个很短的时间段内被再次访问，称其具有空间部分性

20、程序的部分性程序把90的时间用于执行10的代码，缘由如下：程序常包含许多从不被执行的指令如：运用组件和库构建的程序只运用了它们提供的一小部分功能随需求变化和程序演化，遗留系统中经常包含许多不再被运用的指令有大量容错和调试代码在正常运转时不执行执行最内层循环和最紧凑递归环破费了程序执行的大部分时间堆空间的碎片问题程序运转前，堆是一个延续的自在空间随着程序分配/回收内存，堆区逐渐被分割成空闲存储块窗口，hole和已用存储块分配内存时，通常是把一个窗口的一部分分配出去，其他部分成为更小的块。回收时，被释放的存储块被放回缓冲池。通常会把延续的窗口接合成为更大的窗口。堆空间分配方法Best-Fit最正确

21、顺应优先在满足恳求的最小窗口中分配内存优点：可将大窗口保管下来以应对更大的恳求First-Fit最先顺应优先在第一个满足恳求的窗口中分配内存优点：快，常具有较好数据部分性同一段时间内的对象分配延续空间缺陷：总体性能较差运用容器的管理方法设定不同大小的空闲块，并将同样大小的块放在容器中。较小的较常用的尺寸设置较多的容器。比如GNU的C编译器gcc运用存储管理器lea将一切存储块对齐到8字节边境。空闲块的尺寸大小：16,24,32,40,512相邻间相差8大于512的按照对数值划分(每个容器的最小尺寸是前一个容器的最小尺寸的两倍。)荒野块：可以扩展的内存块分配方法：对于小尺寸的恳求，直接在相应容器中找。大尺寸的恳求，在适当的容器中寻觅适当的空闲块。能够需求分割内存块。能够需求从荒野块中分割更多的块。管理和接合空闲空间当回收一个块时，能够可以把这个块和相邻的块接合起来，构成更大的块。有些管理方法，比如说Lea中，不一定需求进展接合。(小于512的)支持相邻块接合的数据构造需求如下两点边境标志：在每一块存储块的两端，分别设置一个free/used位(兼当边境)；相邻的位置上存放字节总数。双重链接的、嵌入式的空闲块列表：列表的指针存放在空闲块中、用双向指针的方式记录了有哪些空闲块。例子相邻的存储块A、B、C当回收B时