辽宁大学-编译原理课件part8

2023/1/141第8章

运行环境

(Run-TimeEnviroments)2023/1/142主要内容绑定（Binding）存储(Storage)组织(Organization)与分配(Allocation)参数(Parameter)传递(Passing)过程说明与调用符号表(SymbolTable)管理2023/1/1438.1绑定（Binding）Binding的概念将符号名和相应目标数据(的地址)对应起来标识符与数据目标的对应变量名──数据存储单元地址过程名、函数名──程序段入口地址相关问题变量和过程的作用域，决定绑定的有效期2023/1/144分段式程序ProgramlayerInta,b,cBegin……Sub(a+b,b,a)……EndSubroutinesub(x,y,z)Reala,b,cBegin……End嵌套式程序ProgramlayerInta,b,cProceduresub1(x,y,z)Intx,y,zProcedureadd(a,b)Reala,bBeginRealx,y,zx=ay=x*2+bz=1/yEndBegin……EndProceduresub2(x,y)……Begin……end2023/1/145绑定的时机与策略语言定义的标识符的生存期决定最终绑定的时机全局变量：全程有效——程序装入时局部变量：分段有效——进入过程或分程序时2023/1/146变量名的绑定静态(Static)绑定编译时指定（相对地址）词法分析期间——在符号表中建立变量的表项回忆：说明语句的语义分析中的字节数计算，填写变量地址（enter)动态(Dynamic)绑定运行时指定（具体地址/相对地址）回忆：动态数组2023/1/147过程/函数名的绑定为过程指定程序代码段入口地址静态绑定：编译时指定相对地址（词法分析：在符号表中建立过程的表项）语义分析：构造目标代码，填写过程的入口地址如：函数、子程序动态绑定运行时指定——函数名作为形式参数（formals）如：函数指针、虚函数（C++）2023/1/1488.2存储组织与分配(P257)主要内容运行时刻的内存划分(Partition)局部数据的静态分配(StaticAllocation)局部数据的动态分配(DynamicAllocation)层次单元法栈式(Stack)存储分配策略堆式(Heap)存储分配策略2023/1/149运行时刻的内存划分代码段全局静态数据栈堆局部数据区中的一个栈单元——活动记录(静态/动态分配)数组区临时工作单元区简单变量区形式单元区寄存器保护区返回地址2023/1/1410静态存储分配特点编译时刻确定存储位置访问效率高主要用途子程序的目标代码段全局数据目标（全局变量）？？用什么样的算法实现静态存储分配2023/1/1411静态存储分配策略介绍顺序分配算法按照程序段出现的先后顺序逐段分配1/222/153/184/176/105/23程序段区域0~2122~3637~5455~7172~9495~104共需要105个存储单元程序段之间的调用关系程序段号/所需数据空间能用更少的空间么？2023/1/1412分层分配算法允许程序段之间的覆盖（覆盖可能性分析）程序段 区域6 0~95 0~224 0~163 23~402 17~311 41~62共需要63个存储单元1/222/153/184/176/105/23思考：如何设计分配算法？7/80原始总存储需求=105个存储单元2023/1/1413beginreal

x,y,zx=ay=x*2+bz=1/y

begininta,b,c …… begin charname,from,a …… end……end……

Sub2(x,y)

……endS1S2PP4嵌套式程序programlayerinta,b,cprocedureSub1(x,y,z)intx,y,zprocedureadd(a,b)reala,bbeginRealx,y,zx=ay=x*2+bz=1/yendbegin

……endprocedureSub2(x,y)

…… begin

…… sub1(a1,a2,a3)

…… endPP3P2P1嵌套过程嵌套分程序2023/1/1414P4嵌套式程序programlayerinta,b,cprocedureSub1(x,y,z)intx,y,zprocedureadd(a,b)reala,bbeginRealx,y,zx=ay=x*2+bz=1/yendbegin

……endprocedureSub2(x,y)

…… begin

…… sub1(a1,a2,a3)

…… endPP3P2P1beginreal

x,y,zx=ay=x*2+bz=1/y

begininta,b,c …… begin charname,from,a …… end……end……

Sub2(x,y)

……endS1S2P6+6+6+12+6+12+6+3+6+12+6+12+*6+12+6+12+6+6+12+6+6+12+*标准单元6+12+*2023/1/1415《编译原理》

(PrinciplesofCompiling)主讲：周翰逊Email：guowei@QQ：26054036 2023/1/1416上次课主要内容S→ifCthenS1elseS2

的翻译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.codeC.codeS1.beginC.trueS.nextS1.codeC.falsegotoS.nextS2.code2023/1/1417上次课主要内容S→whileCdoS1翻译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('goto'S.begin)C.codeS1.codegotoS.beginC.trueS1.beginC.falseS.nextS.begin2023/1/1418上次课主要内容运行环境绑定：静态、动态静态分配——分层分配法动态分配层次单元法每个分程序、过程都有一个层次单元，用来存放当前可以用于分配的地址2023/1/1419静态存储分配无法克服的问题1动态数组问题层次单元法层次单元进入分程序：将直接外层分程序的层次单元内容植入本层层次单元标准单元的使用调用语句：将本层层次单元内容送标准单元过程说明：将标准单元内容送本层层次单元2023/1/1420静态存储分配无法克服的问题2递归调用问题栈式存储分配特点嵌套调用次序先进后出生存期限于本次调用自动释放2023/1/1421栈（Stack）式存储分配用途活动记录——栈单元对应一次过程调用所需存储过程的局部数据区活动记录活动记录活动记录运行栈2023/1/1422活动记录组织示例——过程数据区结构SPnSPn-1……SP1SP0数组存储区本过程……所辖分第临时工作单元程一序层局部数组说明存分储程局部变量区序分程序TOP本过程Display形式单元（m+1个）连主调分程序TOP接全局Display地址数返回地址据主调过程SP本过程TOPSPSPn为第n层过程数据区首址2023/1/1423静态存储分配无法克服的问题3被调用者的生存期超过调用者/局部数据需要保留（save）堆式存储分配2023/1/1424堆（Heap）式存储分配用于动态数据结构存储空间的动态分配和释放实现方法将内存空间分为若干块，根据用户要求分配无法满足时，调用无用单元收集程序将被释放的块收集起来重新分配2023/1/14258.3参数传递传值调用call-by-value过程调用时计算实参(Actual)，将值存到活动记录形参(Formal)与活动记录的实参绑定，运行时将形参作为局部变量使用调用者被调用者直接使用A实际参数A形式参数XA的值单向传值引用调用Call-by-Reference/Address如果实参(地址)具有左值，则存放其左值到活动记录中；否则计算出表达式的值，将此值存入一个单元，并将该单元的地址传给被调用者调用者被调用者间址访问实参AA实参A形参XA的地址传地址2023/1/1427复制恢复Copy-Restore将参数的左、右值同时传给被调用者，被调用者直接使用右值，并将计算结果按照左值返回给调用者调用者被调用者A实际参数A形式参数XA的值传值/传地址A的地址2023/1/1428传名调用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复制恢复：X=T=5,Y=Z=A=2Y:=Y+1=3Z:=Z+X=2+5=7Y A=3Z A=77换名A:=A+1=3A:=A+A+B=3+3+39主程序A:=2;B:=3;P(A+B,A,A);PrintA临时单元:T:A+B=52023/1/14308.4过程调用过程(procedure)子程序(subroutine)、函数(function)过程的定义与调用形参和实参的结合：参数计算与传递调用与返回2023/1/1431工作方式调用方：当前环境的保存与恢复被调方：构造环境，参数绑定Main(){Sub1(10)}Sub1(x){Sub2(x+1)}Sub2(y){Sub3()}2023/1/1432过程调用实现简单过程调用实在参数的计算和保存控制转移、返回地址的保存实在参数和形式参数的结合(多种结合方式)局部变量的处理返回值的处理递归过程调用与过程参数每层过程调用信息的保存与相应信息的查找2023/1/1433活动记录中过程所用信息用于表达式的计算局部数据寄存器、程序计数器（返回地址）保存实在参数的值或地址存放返回值保存调用者活动记录地址等(SP)用于存取嵌套外层过程中的非局部名(Display)访问链控制链返回值实在参数机器状态局部变量临时变量数组存储区本过程……所辖分第临时工作单元程一序层局部数组说明存分储程局部变量区序分程序TOP本过程Display形式单元（m+1个）连主调分程序TOP接全局Display地址数返回地址据主调过程SP本过程TOP2023/1/1434例子——函数的活动记录intsub(i,p)inti;char*p;{charbuf[32];buf[i]=*(p+i);returni+1;}临时变量:t1,t2,t3局部变量：buf[32]机器状态：R0,…,R9,SP,PC,PS参数：i,p返回值控制链Display2023/1/1435过程说明语句的翻译分析参数的类型、分配地址统计参数和返回值的空间需求与调用语句配合完成形/实参数的结合符号表处理完成过程名的属性登记说明语句：

Procedureid(X1,X2,…,Xn)2023/1/1436过程说明语句代码结构说明语句：

Procedureid(X1,X2,…,Xn)代码结构X1.code按参数传递要求实现参数X1的传递，或者完成传递准备；X2.code按参数传递要求实现参数X2的传递，或者完成传递准备；……Xn.code按参数传递要求实现参数Xn的传递，或者完成传递准备；完成动态存储分配相关的工作；进入过程体2023/1/1437过程调用语句的代码结构过程调用语句id(E1,E2,…,En)E1.codea1:=E1.place…En.codean:=En.place动态存储分配相关工作gotopc+n+1parama1…paramancallid.place，n需要一个队列存放a1,a2,…,an，以生成2023/1/1438过程调用的实现1.在过程f中调用过程p时a.对实在参数求值，将结果存入p的活动记录参数域b.在p的活动记录中存放返回地址和当前栈顶指针c.按照活动记录的大小，上移栈顶指针d.控制转到p的入口（过程体）临时变量局部变量机器状态参数返回值控制链Display2023/1/1439临时变量局部变量机器状态参数返回值控制链Display过程调用的实现2.进入过程p并执行Pa.初值寄存器值和其它状态信息b.执行过程体3.从过程p返回(对应return语句)a.p在返回值域中保存返回值b.恢复原栈顶指针和其它寄存器c.按返回地址返回调用者2023/1/1440过程调用语句的制导翻译定义产生式 语义规则S→callid(Elist){S.code:=Elist.code||gen(‘goto‘pc+Elist.num+1)|| for队列q中的每一项

tdogen(’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:=Elist1.num+1;Elist.code:=Elist1.code|| E.code||t:=newtemp;gen(t’:=’E.place);将t放入队列q}2023/1/1441t1:=a*bt2:=3+t1gotopc+3paramt2param6callf,2函数调用f(3+a*b,6)的翻译2023/1/1442函数调用f(b*c-1,x+y,x,y)的翻译t1:=b*ct2:=t1-1t3:=x+ygotopc+5paramt2paramt3paramxparamycallf,42023/1/1443赋值语句x:=a+b+f(b*c-1,x+y,x,y)的翻译t1:=a+bt2:=b*ct3:=t1-1t4:=x+ygotopc+5paramt3paramt4paramxparamycallf.place,4t5:=t1+f.valx:=t52023/1/1444请大家考虑proceduref(a,b,c,d);realf;reala,b,c,d;beginintegeri,j;i:=f(a,a+b,c+a,d)j:=i+a+b;

a:=i*jend在形/实结合中，哪些细节问题需要处理？如何处理？2023/1/14458.4符号表管理种类关键字(保留字)表、层次表、符号表(过程表、变量表、标号表)、常数表……名字信息1信息2……信息nsum1real所在层定义/引用……关键字表表项结构关键字名字(字符串，如"while"，"if")关键字标识(整数)常用的操作：intIsKeyword(charName[])关键字名字关键字标识begin112end113while1142023/1/1447层次表保存各级分程序、循环语句、条件语句的有关信息如：局部名字、转移标号等辅助实现标识符的管理标识符的作用域所在层性质起点终点直接外层本层计数2023/1/1448标识符表保存名字及其属性名字：变量名，过程名，标号名和常数名属性：种类（Kind），类型（Type），长度，作用域，标志（引用/定义），地址等种类：简单变量、数组、记录、结构、函数、常数、常量……类型：整、实、复、布尔、字符、指针、标号名字种类类型长度地址……标志2023/1/1449符号表的作用作用记录源程序中出现的各种符号的相关属性，为编译提供相应的信息：地址、类型