您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 企业文化 > 编译原理运行时环境.
第七章运行时环境学习内容源语言语义存储组织存储分配策略对非局部名字的访问参数传递符号表动态内存分配7.1源语言相关问题7.1.1过程(函数),procedure——静态活动,activation——动态过程定义,proceduredefinition过程名,procedurename过程体,procedurebody函数,function调用,call形式参数,formalparameters实际参数,actualparametersPascal源码示例programsort(input,output);vara:array[0..10]ofinteger;procedurereadarray;vari:integer;beginfori:=1to9doread(a[i]);end;functionpartition(y,z:integer):integer;vari,j,x,v:integer;begin…end;过程定义过程名形式参数函数定义过程体Pascal源码示例(续)procedurequicksort(m,n:integer);vari:integer;beginif(nm)thenbegini:=partition(m,n);quicksort(m,i-1);quicksort(i+1,n)endend;调用实际参数Pascal源码示例(续)begina[0]:=-9999;a[10]:=9999;readarray;quicksort(1,9);end.7.1.2活动树(activationtree)控制流顺序性:程序的执行一组操作步骤序列,在每个步骤,控制流开始于程序的特定位置过程的执行:起始于过程体开始,最终控制权返回到过程调用点之后活动树表示活动:一次执行(execution)过程P的生存期,lifetime:过程体执行的第一步操作到最后一步操作的操作序列,包括P调用其他过程的时间过程的活动p调用q,控制最终会返回p——每次控制流从p转移到q,总会返回到p过程的生命期或者不重叠、或者嵌套——b在a退出之前进入,则必在a之前退出利用输出语句演示嵌套executionbegin……enterreadarrayleavequicksort(1,3)leavereadarrayenterquicksort(5,9)enterquicksort(1,9)…enterpartition(1,9)leavequicksort(5,9)leavepartition(1,9)leavequicksort(1,9)enterquicksort(1,3)executionterminated.递归过程p的某个活动尚未结束,可以开始它的一个新的活动间接递归活动树1.结点——过程的活动2.根结点——主程序的活动3.a是b的父结点控制流从a到b4.a在b的左边a的生存期在b之前例7.17.1.3控制栈(controlstack)活动树深度优先遍历控制流变化控制栈当活动开始,对应结点入栈结束后,将其弹出当前栈内容——到根结点的路径例7.27.1.4作用域声明(declaration):规定名字的含义显式声明、隐式声明(Fortran)同一名字在程序不同位置的不同声明作用域(scope):声明起作用的范围局部的(local)、非局部的(nonlocal)作用域规则确定声明起作用的范围名字对应哪个声明利用符号表6.1.5名字的绑定(binding)名字只声明一次,运行时也可能指向不同数据对象环境(environment):函数名字存储位置,名字l-value状态(state):函数存储位置存储数据,l-valuer-value环境和状态赋值语句改变状态,但不改变环境对某个环境,若名字x对应存储位置sx绑定到s,s是x的一个绑定绑定——声明的动态概念Pascal过程的局部名字,不同活动不同存储位置过程的定义过程的活动名字的声明名字的绑定声明的作用域绑定的生存期静态概念动态概念7.1.6影响存储组织的几个问题1.过程可否递归?2.过程活动结束时,局部名字值如何处理3.过程可否访问非局部名字?4.过程被调用时,参数如何传递5.过程可否作为参数6.过程可否作为返回类型7.程序可否动态控制存储分配8.存储是否必须显式释放?7.2存储组织7.2.1运行时存储细化存储目标代码——大小固定存储数据对象——部分固定控制栈——保存过程的活动信息活动信息的保存过程调用当前过程活动终止状态信息(寄存器、PC)控制栈调用返回从控制栈恢复状态信息停止的过程活动重新开始局部数据对象控制栈堆动态内存分配也可能保存活动信息7.2.2活动记录(activationrecord)存放被调用函数传递给调用函数的返回结果调用函数向被调用函数传递实际参数的区域调用函数(父函数)活动记录的指针用来访问哪些保存在其他活动记录中的非局部数据函数调用前时刻机器状态相关的一些信息:程序计数器、寄存器…保存局部数据保存临时数据:表达式计算中间结果…7.2.3局部数据布局例7.3类型占用空间对齐(align),补丁(padding),压缩(pack)chara;shortb;机器1:4字节,a之后1字节补丁机器2:16字节7.3内存分配策略1.静态分配(static)在编译时(运行之前)确定所有数据的内存分布2.栈分配(stack)利用栈管理运行时存储3.堆分配(heap)允许用户在运行时动态地在堆之上分配、释放内存7.3.1静态分配策略局限性1.数据对象的大小和对其内存位置的限制,必须在编译时已知2.不允许递归对过程的多次活动,局部名字都绑定到相同的存储位置——局部名字的值在多次调用间会得到保持(retain)3.不允许动态数据分配例7.4Fortran的静态分配PROGRAMCNSUNCHARACTER*50BUFINTEGERNEXTCHARACTERC,PRDUCEDATANEXT/1/,BUF/‘’/6C=PRDUCE()BUF(NEXT:NEXT)=CNEXT=NEXT+1IF(C.NE.‘’)GOTO6WRITE(*,‘(A)’)BUFEND赋初值例7.4Fortran的静态分配(续)CHARACTERFUNCTIONPRDUCE()CHARACTER*80BUFFERINTEGERNEXTSAVEBUFFER,NEXTDATANEXT/81/IF(NEXT.GT.80)THENREAD(*,‘(A)’)BUFFERNEXT=1ENDIFPRDUCE=BUFFER(NEXT:NEXT)NEXT=NEXT+1END“保持”例7.4Fortran的静态分配(续)例7.4Fortran的静态分配(续)用户输入“helloworld”PRDUCE常态:缓冲区字符CNSUME,NEXT加1缓冲区用完(NEXT80),重新读取用户输入第一次调用:NEXT=81,用户输入BUFFER,NEXT1,‘h’CNSUME,NEXT加1第二次,BUFFER未变,NEXT未变=2,‘e’CNSUME,NEXT加1…7.3.2栈分配策略过程调用——push活动记录过程返回——pop活动记录每次过程活动,局部名字都绑定到新的位置过程结束,局部名字空间被释放——值丢失例7.5快速排序执行过程调用序列(callingsequence)创建活动记录,填写相关信息的代码返回序列,returnsequence划分到调用函数和被调用函数两部分较早确定大小的信息放在活动记录中部控制链接、访问链接、机器状态信息临时单元实际参数、返回值局部数据,Pascal局部数组大小确定早晚调用序列(续)1.调用者计算实际参数2.调用者存储返回地址(被调用函数返回后继续运行的代码位置)和top_sp旧值,然后将top_sp调整到上图位置——要跨过调用者的局部数据和临时单元以及被调用者的实际参数和状态区3.被调用者保存寄存器值和其他状态信息4.被调用者初始化局部数据开始运行调用序列(续)返回序列1.被调用者设置返回值(位于栈底,与调用者活动记录相邻)2.利用保存的状态信息,被调用者恢复top_sp和其他寄存器,然后跳转到返回地址3.调用者复制返回值可变长度数据top_sptop7.3.3空悬(dangling)引用例7.6:内存空间已释放,但还存在指向它的引用——程序员的错误!int*dangle(){inti=23;return&i;}main(){int*p;p=dangle();}7.3.4堆分配策略栈分配策略的局限,不能处理下列情况局部名字的值在活动结束后能够保持被调用函数的活动生存期比调用者长——可用活动树表示控制流的语言无法实现对小的(或大小已知的)活动记录1.为若干可能大小,创建空闲块链表(静态)2.为大小为s的活动记录分配空间,尽量使用s’的空闲块表,s’为大于等于s的最小值。空间释放时,将块退回空闲块链表3.对大块内存分配,利用堆管理器堆分配策略(续)r的活动记录得到保持7.4访问非局部名字栈词法/静态作用域规则lexical-,static-scoperuleC、Pascal、Ada嵌套问题动态作用域规则dynamic-scoperuleLisp、APL、Snobol7.4.1程序块(block)语句块+它的局部数据声明{声明语句}特性:嵌套结构、不会交叉“最近嵌套规则”,mostcloselynestedrule对于块B中的声明,其作用域包括B块B中未声明名字x,则B中对x的引用由某个外层块B’中x的声明所确定,B’满足:在包围B的,且有x的声明的外层块中,B’是距离B最近的那个嵌套块作用域示例main(){inta=0;intb=0;{intb=1;{inta=2;printf(“%d%d\n”,a,b);}{intb=3;printf(“%d%d\n”,a,b);}printf(“%d%d\n”,a,b);}printf(“%d%d\n”,a,b);}B0B1B2B3声明作用域inta=0;B0-B2intb=0;B0-B1intb=1;B1-B3inta=2;B2intb=3;B3运行结果21030100实现方法栈实现,将块看作过程过程内实现7.4.2无过程嵌套的静态作用域C局部名字——栈任何过程之外的名字——静态分配非局部——全局概念过程可作为参数和返回值非局部名字都可用静态地址访问到过程作为参数——无嵌套情况programpass(input,output);varm:integer;functionf(n:integer):integer;beginf:=m+nend;functiong(n:integer):integer;beging:=m*nend;procedureb(functionh(n:integer):integer);beginwrite(h(2))end;beginm:=0;b(f);b(g);writelnend.运行结果:207.4.3包含过程嵌套的静态作用域Pascal,最近嵌套规则programsort(input,output);vara:array[0..10]ofinteger;x:integer;procedurereadarray;vari:integer;begin…a…end{readarray};procedureexchange(i,j:integer);beginx:=a[i];a[i]:=a[j];a[j]:=xend{exchange};procedurequicksort(m,n:integer);vark,v:integer;functionpartition(y,z:integer):integer;vari,j:integer;begin…a……v…end{
本文标题:编译原理运行时环境.
链接地址:https://www.777doc.com/doc-2069064 .html