运行环境RunTimeEnvironm.ppt

第8章 运行环境 (Run-Time Environments),主要内容,绑定（Binding） 存储(Storage)组织(Organization)与分配(Allocation) 参数(Parameter)传递(Passing) 过程说明与调用 符号表(Symbol Table)管理,8.1 绑定（Binding）,Binding的概念 将符号名和相应目标数据(的地址)对应起来 标识符与数据目标的对应 变量名数据存储单元地址 过程名、函数名程序段入口地址 相关问题 变量和过程的作用域，决定绑定的有效期,分段式程序 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,绑定的时机与策略,语言定义的标识符的生存期决定最终绑定的时机 全局变量：全程有效程序装入时 局部变量：分段有效进入过程或分程序时,变量名的绑定,静态(Static)绑定：编译时指定（相对地址） 词法分析期间在符号表中建立变量的表项 回忆：说明语句的语义分析：字节数计算，填写变量地址 动态(Dynamic)绑定：运行时指定（具体地址/相对地址） 如：动态数组,过程/函数名的绑定,为过程指定程序代码段入口地址 静态绑定：编译时指定相对地址 （词法分析：在符号表中建立过程的表项） 语义分析：构造目标代码，填写过程的入口地址 如：一般的函数、子例程 动态绑定 运行时指定函数名作为形式参数（formals） 如：函数指针、虚函数（C+）,8.2 存储组织与分配(P257),运行时刻的内存划分(Partition) 局部数据的静态分配(Static Allocation) 局部数据的动态分配(Dynamic Allocation) 层次单元法 栈式(Stack)存储分配策略 堆式(Heap)存储分配策略,运行时刻的内存划分,局部数据区中的一个栈单元 活动记录(静态/动态分配),静态存储分配,特点 编译时刻确定存储位置 访问效率高 主要用途 子程序的目标代码段 全局数据目标（全局变量） ？用什么样的算法实现静态存储分配,静态存储分配策略介绍,顺序分配算法 按照程序段出现的先后顺序逐段分配,程序段 区域 021 2236 3754 5571 7294 95104 共需要105个存储单元,程序段之间的调用关系程序段号/所需数据空间,能用更少的空间么？,分层分配算法,允许程序段之间的覆盖（覆盖可能性分析）,程序段 区域 6 09 5 022 4 016 3 2340 2 1731 1 4162 共需要63个存储单元,思考：如何设计分配算法？,7/80,静态存储分配无法克服的问题1,动态数组问题 层次单元法 层次单元 标准单元的使用,静态存储分配无法克服的问题2,递归调用问题 栈式存储分配,栈（Stack）式存储分配,用途 过程的局部环境 活动记录 特点 嵌套调用次序 先进后出 生存期限于本次调用 自动释放,活动记录,活动记录,活动记录,运行栈,过程数据区结构,SPn SPn-1 SP1 SP0,SP,SPn为第n层过程数据区首址,静态存储分配无法克服的问题3,被调用者的生存期超过调用者/局部数据需要保留（ save ） 堆式存储分配,堆（Heap）式存储分配,用于动态数据结构 存储空间的动态分配和释放 实现方法： 将内存空间分为若干块，根据用户要求分配 无法满足时，调用无用单元收集程序将被释放的块收集起来重新分配,8.3 参数传递,传值调用 call-by-value 过程调用时计算实参(Actual)，将值存到活动记录 形参(Formal)绑定于活动记录的实参域,引用调用 Call-by-Reference/Address 如果实在参数具有左值，则存放其左值到活动记录中；否则计算出表达式的值，将此值存入一个单元，并将该单元的地址传给被调用者。,复制恢复 Copy-Restore,将参数的左、右值同时传给被调用者，被调用者直接使用右值，并将计算结果按照左值返回给调用者,传名调用Call-by-Name,将被调过程的过程体复制到调用处，并将每一个形参“文字地”替换成实参 用换名子程序实现Thunk 是一种早期的语言ALGOL用的一种参数传递方式,上次课主要内容,回填技术 S if C then S1 的翻译 C.true := newlabel; S1.next := S.next; C.false:= S.next; S.code := C.code |gen( C.true: ) |S1.code,上次课主要内容,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,上次课主要内容,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 ),上次课主要内容,运行环境 绑定：静态、动态 静态分配 动态分配 层次单元法 栈式(Stack)存储分配策略 堆式(Heap)存储分配策略,上次课主要内容,参数传递 传值调用 call-by-value 引用调用 Call-by-Reference/Address 复制恢复 Copy-Restore 传名调用Call-by-Name,子程序 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,8.4 过程调用,过程(procedure) 子程序(subroutine)、函数(function) 过程的定义与调用 形参和实参的结合：参数计算与传递 调用与返回,工作方式,调用方：当前环境的保存与恢复 被调方：构造环境，参数绑定,过程调用实现,简单过程调用 实在参数的计算和保存 控制转移、返回地址的保存 实在参数和形式参数的结合(多种结合方式) 局部变量的处理 返回值的处理 递归过程调用与过程参数 每层过程调用信息的保存与相应信息的查找,活动记录中过程所用信息,用于表达式的计算 局部数据 寄存器、程序计数器（返回地址） 保存实在参数的值或地址 存放返回值 保存调用者活动记录地址等(SP) 用于存取嵌套外层过程中的非局部名(Display),访问链,控制链,返回值,实在参数,机器状态,局部变量,临时变量,例子函数的活动记录,int sub( i, p ) int i; char *p; char buf32; bufi = *(p + i); return i + 1; ,过程说明语句的翻译,分析参数的类型、分配地址 统计参数和返回值的空间需求 与调用语句配合完成形/实参数的结合 符号表处理 完成过程名的属性登记,说明语句： Procedure id(X1,X2,Xn),过程说明语句代码结构,说明语句： Procedure id(X1,X2,Xn),代码结构 X1.code 按参数传递要求实现参数X1的传递，或者完成传递准备； X2.code 按参数传递要求实现参数X2的传递，或者完成传递准备； Xn.code 按参数传递要求实现参数Xn的传递，或者完成传递准备； 完成动态存储分配相关的工作； 进入过程体,过程调用语句的代码结构,过程调用语句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. f 对实在参数求值，将结果存入 p 的活动记录参数域 b. 在 p 的活动记录中存放返回地址和当前栈顶指针 c. 按照活动记录的大小，上移栈顶指针 d. 控制转到 p 的入口（过程体）,e. p 存放寄存器值和其它状态信息 f. 执行过程体 2. 从过程 p 返回：对应return语句 a. p 在返回值域中保存返回值 b. 恢复原栈顶指针和其它寄存器 c. 按返回地址返回调用者,过程调用语句的制导翻译定义,产生式 语义规则 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,生成的目标代码 t1 := 3 + a goto pc+3 param t1 param 6 call f, 2,函数调用 f(3+a,6)的翻译,函数调用 f(b*c-1,x+y,x,y)的翻译,t1:=b*c t2:=t1-1 t3:=x+y goto pc+5 param t2 param t3 param x param y call f, 4,赋值语句x:=a+b+ f(b*c-1,x+y,x,y)的翻译,t1:=a+b t2:=b*c t3:=t1-1 t4:=x+y goto pc+5,param t3 param t4 param x param y call f.place, 4 t5:=t1+f.val x:=t5,8.4 符号表管理,种类 关键字表、层次表、符号表（过程表、变量表、标号表）、常数表,关键字表,表项结构 关键字标识 (整数) 关键字名字 (字符串，如“while“，“if“) 常用的操作： int IsKeyword( char Name ),层次表,保存各级分程序、循环语句、条件语句的有关信息 如：局部名字、转移标号等 辅助实现标识符的管理 标识符的作用域,符号表,保存名字及其属性 名字：变量名，过程名，标号名和常数名 属性：种类（Kind），类型（Type），长度，作用域，标志（引用/定义），地址等 种类：简单变量、数组、记录、结构、函数、常数、常量 类型：整、实、复、布尔、字符、指针、标号,符号表的作用,作用 记录源程序