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

第七章运行时刻环境湖南大学计算机与通信学院（软件学院）编译器的一些问题•变量的存储位置如何分配？•名字的作用域如何实现？•过程调用如何实现？•参数传递如何实现？•……•这些问题需要依靠运行时环境来辅助解决。运行时刻环境•运行时刻环境–为数据分配安排存储位置–确定访问变量时使用的机制–过程之间的连接–参数传递–和操作系统、输入输出设备相关的其它接口•主题–存储管理：栈分配、堆管理、垃圾回收–对变量、数据的访问存储分配的典型方式•目标程序的代码放置在代码区，通常位于存储的低端•静态区、堆区、栈区分别放置不同类型生命期的数据值,实践中栈向较低地址方向增长堆向较高方向增长。图7-1编译的结果全局/静态变量……共享*从现在开始要注意，为使我们能在所有的例子中方便地使用正的偏移量,栈向较高地址方向增长，即顶是在最下端。0X00H0XFFFFH...静态和动态存储分配•静态分配–编译器在编译时刻就可以做出存储分配决定，不需要考虑程序运行时刻的情形，如：静态变量（ｃ语言中static变量）–全局变量•动态分配–栈式存储：过程的局部名字采用栈式存储•和过程的调用/返回同步进行分配和回收，值的生命期和过程生命期相同–堆heap存储：有些数据生命期比相应过程调用的生命期更长，常分配在一个可重用存储的“堆”中。堆和垃圾回收•堆是虚拟内存的一个区域，它允许对象或其他数据元素在被创建时获得存储空间，并在数据变得无效时释放该存储空间•垃圾回收：检测出堆中无用的数据元素，释放它们的空间–手工进行回收（程序员）–垃圾回收机制，如：Ｊａｖａ栈式分配•内容：–活动树–活动记录–调用(代码)序列–栈中的变长数据活动树•过程调用（过程活动）在时间上总是嵌套的：–后调用的先返回(LIFO)–因此可以用栈式分配来处理过程活动所需要的内存空间。•程序运行的所有过程活动可以用树表示–每个结点对应于一个过程活动–根结点对应于main过程的活动–过程p的某次活动对应的结点的子结点对应于此次活动调用的各个过程活动（从左向右，表示调用的先后顺序）活动树的例子－快速排序（1）活动树的例子－快速排序（２）•程序：P260，图7-2•过程调用（返回）序列和活动树的前序（后序）遍历对应•假定当前活动对应结点N，那么所有尚未结束的结点对应于N及其祖先结点。活动记录•过程调用和返回由控制栈进行管理•过程活动记录：当调用过程或函数时，为其局部数据动态分配的存储区•活动记录按照活动的开始时间，从栈底到栈顶排列图７－５活动记录框架计算中间结果局部变量活动记录•控制链：指向调用者的活动记录（固定长度部分）•访问链：活动记录中指向上一级活动记录(包含嵌套的环境定义的活动记录)的指针•保存的机器状态：此次调用前的机器状态信息，如：返回地址及一些寄存器的值运行时刻栈的例子•例：快速排序•a[11]为全局变量•main没有局部变量•r有局部变量i•q的局部变量i，和参数m,n。Main的活动记录调用序列•调用序列(callingsequence)为活动记录分配空间，填写记录中的信息；•返回序列(returnsequence)恢复机器状态，使调用者继续运行。•调用序列会分割到调用者和被调用者中。–根据源语言、目标机器、操作系统的限制，可以有不同的分割方案–把代码尽可能放在被调用者中。调用/返回序列的要求•数据方面–能够把参数正确地传递给被调用者–能够把返回值传递给调用者•控制方面–能够正确转到被调用者的代码的开始位置–能够正确转回调用者的调用位置（的下一条指令）•调用序列和活动记录的布局相关活动记录的布局原则•调用者和被调用者之间传递的值放在被调用者记录的开始位置•固定长度的项放在中间位置–控制链、访问链、机器状态字段•早期不知道大小的项在活动记录尾部（干脆将固定长度的局部变量也放入该段）•栈顶指针通常指向固定长度字段的末端top_sp调用代码序列的例子•Callingsequence（调用序列）–调用者计算实在参数的值–将返回地址和原top_sp（控制链）存放到被调用者的活动记录中。调用者增加top_sp的值（越过了调用者的局部数据、临时变量、被调用者的参数、机器状态字段）–被调用者保存寄存器值和其他状态字段–被调用者初始化局部数据、开始运行。•Returnsequence（返回序列）–被调用者将返回值放到和参数相邻的位置–恢复top_sp和寄存器，跳转到返回地址。栈中的变长数据•如果数据对象的生命期局限于过程活动的生命期，就可以分配在运行时刻栈中。•top指向实际的栈顶•top_sp用于寻找顶层记录的定长字段（框架指针）例利用Euclid算法的简单递归算法，计算两个非负整数的最大公约数。程序清单C代码#includestdio.hintx,y;intgcd(intu,intv){if(v==0)returnu;elsereturngcd(v,u%v);}main(){scanf(“%d%d”,&x,&y);printf(“%d\n”,gcd(x,y));return0;}若输入为１５，１０，（１）试画出运行的活动树（２）试画出运行时栈变化过程main()gcd(15,10)gcd(10,5)gcd(5,0)•第3个调用时的环境如图7-2所示。x:15y:10u:15v:10控制链返回地址局部变量u:10v:5控制链返回地址局部变量u:5v:0控制链返回地址局部变量自由空间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无嵌套过程时的数据访问•无嵌套过程时的数据访问–例：Ｃ语言•不允许嵌套过程声明，变量要么在函数内定义，要么全局地定义–C语言中函数对变量的访问•局部变量：在当前活动记录内，可通过top_sp指针加上相对地址来访问•全局/静态变量：在静态区，地址在编译时可知–C语言允许函数参数•参数中只需要包括函数代码的起始地址。•在函数中访问变量的模式很简单，不需要考虑过程是如何激活的。C语言中活动记录中无需访问链7.3基于栈的运行时环境1)对名称的访问•在基于栈的环境中，要访问参数和局部变量，可用当前框架指针(top_sp)的偏移量实现。•在大多数的语言中，每个局部声明的偏移量可由编译程序静态地计算出来。因为过程的声明在编译时是固定的，而且为每个声明分配的存储器大小也根据其数据类型而固定。•例考虑C过程voidf(intx,charc){inta[10];doubley;...}对f调用的活动记录ya[9]……a[1]a[0]返回地址控制链cxx偏移量top_spc偏移量a偏移量y偏移量*此处在返回地址下省略了被保存的状态等信息•整型4个字节、地址4个字节、字符1个字节、双精度浮点数8个字节，则偏移量为：名称偏移量x-9c-8a+0y+40•a[i]的地址为：0+4*i+top_sp。•在基于栈的环境中，非局部的和静态的名字的地址都是固定的静态地址，可以直接访问。*注意在本章内，栈是往下面大端生长的。非局部数据的访问（嵌套过程）•PASCAL语言允许过程嵌套定义，且遵循静态作用域规则–代码运行时，对变量ｘ的访问应指向运行栈中最上层的同名变量。•问题：变量ｘ不一定在当前活动记录中，如何确定其位置？•思考：符号表中存储了变量ｘ的偏移量，因此只需要确定ｘ的活动记录。•子问题：用嵌套层次可以完全解决这个问题吗？非局部数据的访问（嵌套过程）•问题：用调用层次可以完全解决这个问题吗？voidA(){intx,y;voidB(){intb;x=b+y;}voidC(){B();}C();}B的活动记录C的活动记录A的活动记录当A调用C，C又调用B时:不能！A,B的层次差是１，但B的控制链并没有直接指向A•解决方法：引入访问链–指向过程的定义环境7.3.3一个支持嵌套过程声明的语言•最新的支持嵌套过程的典型语言之一：ML•ML是一种函数式语言，变量一旦声明并初始化就不会再改变–有少数例外，如：数组元素可通过特殊的函数调用改变•变量定义并初始化为不可更改的值的语句形式：–Ｖａｌname=expression•函数定义的语法：–Funname(arguments)=body•函数体(body)定义的语法：–Letlistofdefinitionsinstatementsend嵌套深度•嵌套深度是正文概念，可根据源程序静态地确定–不内嵌于任何其他过程中的过程，嵌套深度为1–嵌套在深度为i的过程中的过程，深度为i+1.深度为1sort深度为2readArray，exchange，quicksort深度为3partition图7-10一个使用嵌套函数声明的ML风格的quicksort访问链显式表１显式表２访问链•引入访问链的目的：访问非局部数据•如果过程p在声明时嵌套在过程q的声明中，那么p的活动记录中的访问链指向最上层（最新）的q的活动记录。•从栈顶活动记录开始，访问链形成了一个链路，嵌套深度逐一递减。•设深度为np的过程p访问变量x，而变量x在深度为nq的过程中声明，那么–从当前活动记录出发，沿访问链前进np-nq次找到活动记录（其中的x就是要找的变量位置）–x相对于该活动记录的偏移量在编译时刻已知–np和-nq在编译时刻已知；访问链的例子P270图7-11用来查找非局部数据的访问链sort活动记录访问链的处理（明确调用过程与声明嵌套深度的关系）•当过程q调用过程p时，P访问链如何设置？把p的声明嵌套深度np与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函数声明如下：staticvoidtraverse(TreeNode*t,void(*preProc)(TreeNode*),void(*postProc)(TreeNode*))构建符号表前序遍历语法树traverse(syntaxTree,insertNode,nullProc);类型检查时后序遍历语法树traverse(syntaxTree,nullProc,checkNode);7.3.6过程型参数的访问链•当一个过程ｐ作为参数传递给另一个过程ｑ，并且ｑ随后调用了这个参数，有可能ｑ并不知道ｐ在程序中出现的上下文–后果：不知道如何设置ｐ的访问链•解决办法：在传递过程指针参数时，过程型参数中不仅包含过程的代码指针(IP)，还包括正确的访问链（AL)。7.3.6过程型参数的访问链图７-12使用函数参数的ML程序的概要f是一个函数参数对ｆ的引用d被用作函数参数7.3.6过程型参数的访问链因为d在c中定义7.3.8显示表（display)•用访问链访问数据时，如果嵌套深度大，则访问的效率差。•显示表：使用数组d为每个嵌套深度保留一个指针–指针d[i]指向栈中最高的对应