第8章 运行环境 (Run-Time Enviroments),1,主要内容,绑定（Binding） 存储(Storage)组织(Organization)与分配(Allocation) 参数(Parameter)传递(Passing) 过程说明与调用 符号表(Symbol Table)管理,2,8.1 绑定（Binding）,Binding的概念 将符号名和相应目标数据(的地址)对应起来 标识符与数据目标的对应 变量名数据存储单元地址 过程名、函数名程序段入口地址 相关问题 变量和过程的作用域，决定绑定的有效期,3,4,分段式程序 Program layer Int a,b,c Begin Sub(a+b,b,a) End Subroutine sub(x,y,z) Real a,b,c Begin End,嵌套式程序 Program layer Int a,b,c Procedure sub1(x,y,z) Int x,y,z Procedure add(a,b) Real a,b Begin Real x,y,z x=a y=x*2+b z=1/y End Begin End Procedure sub2(x,y) Begin end,绑定的时机与策略,语言定义的标识符的生存期决定最终绑定的时机 全局变量：全程有效程序装入时 局部变量：分段有效进入过程或分程序时,5,变量名的绑定,静态(Static)绑定 编译时指定（相对地址） 词法分析期间在符号表中建立变量的表项 回忆：说明语句的语义分析中的字节数计算，填写变量地址（enter) 动态(Dynamic)绑定 运行时指定（具体地址/相对地址） 回忆：动态数组,6,过程/函数名的绑定,为过程指定程序代码段入口地址 静态绑定：编译时指定相对地址 （词法分析：在符号表中建立过程的表项） 语义分析：构造目标代码，填写过程的入口地址 如：函数、子程序 动态绑定 运行时指定函数名作为形式参数（formals） 如：函数指针、虚函数（C+）,7,8.2 存储组织与分配(P257),主要内容 运行时刻的内存划分(Partition) 局部数据的静态分配(Static Allocation) 局部数据的动态分配(Dynamic Allocation) 层次单元法 栈式(Stack)存储分配策略 堆式(Heap)存储分配策略,8,运行时刻的内存划分,9,局部数据区中的一个栈单元 活动记录(静态/动态分配),静态存储分配,特点 编译时刻确定存储位置 访问效率高 主要用途 子程序的目标代码段 全局数据目标（全局变量） ？用什么样的算法实现静态存储分配,10,静态存储分配策略介绍,顺序分配算法 按照程序段出现的先后顺序逐段分配,11,程序段 区域 021 2236 3754 5571 7294 95104 共需要105个存储单元,程序段之间的调用关系程序段号/所需数据空间,能用更少的空间么？,分层分配算法,允许程序段之间的覆盖（覆盖可能性分析）,12,程序段 区域 6 09 5 022 4 016 3 2340 2 1731 1 4162 共需要63个存储单元,思考：如何设计分配算法？,7/80,原始总存储需求=105个存储单元,13,嵌套过程,嵌套分程序,静态存储分配无法克服的问题1,动态数组问题 层次单元法 层次单元 进入分程序：将直接外层分程序的层次单元内容植入本层层次单元 标准单元的使用 调用语句：将本层层次单元内容送标准单元 过程说明：将标准单元内容送本层层次单元,14,上次课主要内容,S if C then S1 else S2 的翻译 C.true := newlabel; C.false := newlabel; S1.next := S2.next := S.next; S.code := C.code | gen( C.true: )| S1.code | gen( goto S.next ) | gen( C.false: ) | S2.code,15,上次课主要内容,S while C do S1翻译 S.begin := S1.next := newlabel; C.true := S1.begin := newlabel; C.false := S.next; S.code := gen( S.begin: ) | C.code | gen( C.true: ) | S1.code | gen( gotoS.begin ),16,上次课主要内容,运行环境 绑定：静态、动态 静态分配分层分配法 动态分配 层次单元法 每个分程序、过程都有一个层次单元，用来存放当前可以用于分配的地址,17,18,6+,6+,6+12+,6+12+6+3+,6+12+,6+12+*,6+12+,6+12+6+,6+12+6+,6+12+*,标准单元6+12+,*,静态存储分配无法克服的问题2,递归调用问题 栈式存储分配 特点 嵌套调用次序 先进后出 生存期限于本次调用 自动释放,19,栈（Stack）式存储分配,用途 活动记录栈单元对应一次过程调用所需存储 过程的局部数据区,20,活动记录,活动记录,活动记录,运行栈,活动记录组织示例过程数据区结构,SPn SPn-1 SP1 SP0,21,SP,SPn为第n层过程数据区首址,静态存储分配无法克服的问题3,被调用者的生存期超过调用者/局部数据需要保留（ save ） 堆式存储分配,22,堆（Heap）式存储分配,用于动态数据结构 存储空间的动态分配和释放 实现方法 将内存空间分为若干块，根据用户要求分配 无法满足时，调用无用单元收集程序将被释放的块收集起来重新分配,23,8.3 参数传递,传值调用 call-by-value 过程调用时计算实参(Actual)，将值存到活动记录 形参(Formal)与活动记录的实参绑定，运行时将形参作为局部变量使用,24,引用调用 Call-by-Reference/Address 如果实参(地址)具有左值，则存放其左值到活动记录中；否则计算出表达式的值，将此值存入一个单元，并将该单元的地址传给被调用者,25,复制恢复 Copy-Restore,将参数的左、右值同时传给被调用者，被调用者直接使用右值，并将计算结果按照左值返回给调用者,26,传名调用Call-by-Name,将被调过程的过程体复制到调用处，并将每一个形参“文字地”替换成实参 用换名子程序实现Thunk 是一种早期的语言ALGOL用的一种参数传递方式,27,子程序 P(X,Y,Z); Y:=Y+1; Z:=Z+X,传值调用： 2,传地址： X=T=5,Y=Z=A=2 A:=A+1=2+1 A:=A+T=3+5 8,换名 A:=A+1=3 A:=A+A+B=3+3+3 9,主程序 A:=2; B:=3; P(A+B, A, A); Print A,临时单元: T:A+B=5,28,8.4 过程调用,过程(procedure) 子程序(subroutine)、函数(function) 过程的定义与调用 形参和实参的结合：参数计算与传递 调用与返回,29,工作方式,调用方：当前环境的保存与恢复 被调方：构造环境，参数绑定,30,过程调用实现,简单过程调用 实在参数的计算和保存 控制转移、返回地址的保存 实在参数和形式参数的结合(多种结合方式) 局部变量的处理 返回值的处理 递归过程调用与过程参数 每层过程调用信息的保存与相应信息的查找,31,活动记录中过程所用信息,用于表达式的计算 局部数据 寄存器、程序计数器（返回地址） 保存实在参数的值或地址 存放返回值 保存调用者活动记录地址等(SP) 用于存取嵌套外层过程中的非局部名(Display),32,访问链,控制链,返回值,实在参数,机器状态,局部变量,临时变量,例子函数的活动记录,int sub( i, p ) int i; char *p; char buf32; bufi = *(p + i); return i + 1; ,33,过程说明语句的翻译,分析参数的类型、分配地址 统计参数和返回值的空间需求 与调用语句配合完成形/实参数的结合 符号表处理 完成过程名的属性登记,34,说明语句： Procedure id(X1,X2,Xn),35,过程说明语句代码结构,说明语句： Procedure id(X1,X2,Xn),代码结构 X1.code 按参数传递要求实现参数X1的传递，或者完成传递准备； X2.code 按参数传递要求实现参数X2的传递，或者完成传递准备； Xn.code 按参数传递要求实现参数Xn的传递，或者完成传递准备； 完成动态存储分配相关的工作； 进入过程体,36,过程调用语句的代码结构,过程调用语句id(E1,E2, ,En),E1.code a1:=E1.place En.code an:=En.place 动态存储分配相关工作 goto pc+n+1 param a1 param an call id.place，n,需要一个队列存放a1, a2, , an，以生成,过程调用的实现,1. 在过程 f 中调用过程 p 时 a. 对实在参数求值，将结果存入 p 的活动记录参数域 b. 在 p 的活动记录中存放返回地址和当前栈顶指针 c. 按照活动记录的大小，上移栈顶指针 d. 控制转到 p 的入口（过程体）,37,过程调用的实现,2. 进入过程p并执行P a. 初值寄存器值和其它状态信息 b. 执行过程体 3. 从过程 p 返回(对应return语句) a. p 在返回值域中保存返回值 b. 恢复原栈顶指针和其它寄存器 c. 按返回地址返回调用者,38,过程调用语句的制导翻译定义,39,产生式 语义规则 S call id ( Elist ) S.code := Elist.code |gen(goto pc+Elist.num+1)| for 队列q中的每一项 t do gen(param t ) | gen(call id.place,Elist.num) Elist E Elist.num := 1; Elist.code := E.code | t:=newtemp; gen(t:= E.place)；建立队列q，并将t 放入q Elist Elist1,E Elist.num := Elist 1.num+1; Elist.code := Elist 1.code | E.code | t:=newtemp; gen(t:= E.place);将t 放入队列q,上次课主要内容,参数传递 传值调用 引用调用 复制恢复 传名调用 文字替换,40,A,实际参数A,形参X,A的值,间址访A,A,A的地址,A,A的值,A的地址,上次课主要内容,Procedure id(X1,X2,Xn) X1.code X2.code Xn.code 动态存储分配相关 进入过程体,41,id(E1,E2, ,En) E1.code a1:=E1.place En.code an:=En.place 动态存储分配相关 goto pc+n+1 param a1 param an call id.place，n,上次课主要内容,42,产生式 语义规则 S call id ( Elist ) S.code := Elist.code |gen(goto pc+Elist.num+1