《编译原理-运行环境.ppt》由会员分享，可在线阅读，更多相关《编译原理-运行环境.ppt（44页珍藏版）》请在三一办公上搜索。
1、第8章 运行环境(Run-Time Enviroments),主要内容,绑定（Binding）存储(Storage)组织(Organization)与分配(Allocation)参数(Parameter)传递(Passing)过程说明与调用符号表(Symbol Table)管理,8.1 绑定（Binding）,Binding的概念将符号名和相应目标数据(的地址)对应起来标识符与数据目标的对应变量名数据存储单元地址过程名、函数名程序段入口地址相关问题变量和过程的作用域，决定绑定的有效期,分段式程序Program layerInt a,b,cBeginSub(a+b,b,a)EndSubrouti
2、ne Sub(x,y,z)Real a,b,cBeginEnd,嵌套式程序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)Beginend,绑定的时机与策略,语言定义的标识符的生存期决定最终绑定的时机全局变量：全程有效程序装入时局部变量：分段有效进入过程或分程序时,变量名的绑定,静态(Static)绑定：编译时指定（相对地址）词法分析期间在符号表
3、中建立变量的表项回忆：说明语句的语义分析：字节数计算，填写变量地址动态(Dynamic)绑定：运行时指定（具体地址/相对地址）如：动态数组,过程/函数名的绑定,为过程指定程序代码段入口地址静态绑定：编译时指定相对地址（词法分析：在符号表中建立过程的表项）语义分析：构造目标代码，填写过程的入口地址如：一般的函数、子例程动态绑定运行时指定函数名作为形式参数（formals）如：函数指针、虚函数（C+）,8.2 存储组织与分配(P257),主要内容运行时刻的内存划分(Partition)局部数据的静态分配(Static Allocation)局部数据的动态分配(Dynamic Allocation)
4、层次单元法栈式(Stack)存储分配策略堆式(Heap)存储分配策略,运行时刻的内存划分,局部数据区中的一个栈单元活动记录(静态/动态分配),静态存储分配,特点编译时刻确定存储位置访问效率高主要用途子程序的目标代码段全局数据目标（全局变量）？用什么样的算法实现静态存储分配,静态存储分配策略介绍,顺序分配算法按照程序段出现的先后顺序逐段分配,程序段 区域 021 2236 3754 5571 7294 95104共需要105个存储单元,程序段之间的调用关系程序段号/所需数据空间,能用更少的空间么？,分层分配算法,允许程序段之间的覆盖（覆盖可能性分析）,程序段 区域6095022 40163234
5、02173114162共需要63个存储单元,思考：如何设计分配算法？,7/80,原始总存储需求=105个存储单元,嵌套过程,嵌套分程序,静态存储分配无法克服的问题1,动态数组问题层次单元法层次单元标准单元的使用,静态存储分配无法克服的问题2,递归调用问题栈式存储分配,栈（Stack）式存储分配,用途过程的局部环境活动记录特点嵌套调用次序先进后出生存期限于本次调用自动释放,活动记录,活动记录,活动记录,运行栈,过程数据区结构,SPnSPn-1SP1SP0,SP,SPn为第n层过程数据区首址,静态存储分配无法克服的问题3,被调用者的生存期超过调用者/局部数据需要保留（save）堆式存储分配,堆（H
6、eap）式存储分配,用于动态数据结构存储空间的动态分配和释放实现方法：将内存空间分为若干块，根据用户要求分配无法满足时，调用无用单元收集程序将被释放的块收集起来重新分配,8.3 参数传递,传值调用 call-by-value过程调用时计算实参(Actual)，将值存到活动记录形参(Formal)绑定于活动记录的实参域,引用调用 Call-by-Reference/Address如果实在参数具有左值，则存放其左值到活动记录中；否则计算出表达式的值，将此值存入一个单元，并将该单元的地址传给被调用者。,复制恢复 Copy-Restore,将参数的左、右值同时传给被调用者，被调用者直接使用右值，并将计
7、算结果按照左值返回给调用者,传名调用Call-by-Name,将被调过程的过程体复制到调用处，并将每一个形参“文字地”替换成实参用换名子程序实现Thunk是一种早期的语言ALGOL用的一种参数传递方式,子程序P(X,Y,Z);Y:=Y+1;Z:=Z+X,传值调用：2,传地址：X=T=5,Y=Z=A=2A:=A+1=2+1A:=A+T=3+58,换名A:=A+1=3A:=A+A+B=3+3+39,主程序A:=2;B:=3;P(A+B,A,A);Print A,临时单元:T:A+B=5,8.4 过程调用,过程(procedure)子程序(subroutine)、函数(function)过程的定义与
8、调用形参和实参的结合：参数计算与传递调用与返回,工作方式,调用方：当前环境的保存与恢复被调方：构造环境，参数绑定,过程调用实现,简单过程调用实在参数的计算和保存控制转移、返回地址的保存实在参数和形式参数的结合(多种结合方式)局部变量的处理返回值的处理递归过程调用与过程参数每层过程调用信息的保存与相应信息的查找,活动记录中过程所用信息,用于表达式的计算局部数据寄存器、程序计数器（返回地址）保存实在参数的值或地址存放返回值保存调用者活动记录地址等(SP)用于存取嵌套外层过程中的非局部名(Display),访问链,控制链,返回值,实在参数,机器状态,局部变量,临时变量,例子函数的活动记录,int s
9、ub(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的传递，或者完成传递准备；完成动态
10、存储分配相关的工作；进入过程体,过程调用语句的代码结构,过程调用语句id(E1,E2,En),E1.codea1:=E1.placeEn.codean:=En.place动态存储分配相关工作goto pc+n+1param a1param ancall id.place，n,需要一个队列存放a1,a2,an，以生成,过程调用的实现,1)在过程 f 中调用过程 p 时a.f 对实在参数求值，将结果存入 p 的活动记录参数域b.在 p 的活动记录中存放返回地址和当前栈顶指针c.按照活动记录的大小，上移栈顶指针d.控制转到 p 的入口（过程体）,e.p 存放寄存器值和其它状态信息f.执行过程体2.从
11、过程 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 放入qElist Elist1,E Elis
12、t.num:=Elist 1.num+1;Elist.code:=Elist 1.code|E.code|t:=newtemp;gen(t:=E.place);将t 放入队列q,生成的目标代码t1:=3+agoto pc+3param t1param 6call f,2,函数调用 f(3+a,6)的翻译,函数调用 f(b*c-1,x+y,x,y)的翻译,t1:=b*ct2:=t1-1t3:=x+ygoto pc+5param t2param t3param xparam ycall f,4,赋值语句x:=a+b+f(b*c-1,x+y,x,y)的翻译,t1:=a+bt2:=b*ct3:=t1-
13、1t4:=x+ygoto pc+5,param t3param t4param xparam ycall f.place,4 t5:=t1+f.valx:=t5,8.4 符号表管理,种类关键字表、层次表、符号表（过程表、变量表、标号表）、常数表,关键字表,表项结构关键字标识(整数)关键字名字(字符串，如while，if)常用的操作：int IsKeyword(char Name),层次表,保存各级分程序、循环语句、条件语句的有关信息如：局部名字、转移标号等辅助实现标识符的管理标识符的作用域,符号表,保存名字及其属性名字：变量名，过程名，标号名和常数名属性：种类（Kind），类型（Type），长度，作用域，标志（引用/定义），地址等种类：简单变量、数组、记录、结构、函数、常数、常量类型：整、实、复、布尔、字符、指针、标号,符号表的作用,作用记录源程序中出现的各种符号的相关属性，为编译提供相应的信息：地址、类型建立表项以标识符为关键字,符号表的实现,实现方法：线性表、散列表（Hash）、二叉树特殊问题结构成员、函数参数、分程序结构性能优先考虑查找的效率,
