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

1、2022-5-11第第8 8章章 运行环境运行环境 2022-5-12 绑定（绑定（BindingBinding） 存储存储( (Storage)Storage)组织组织( (Organization)Organization)与分配与分配( (Allocation)Allocation) 参数参数( (Parameter)Parameter)传递传递( (Passing)Passing) 过程说明与调用过程说明与调用 符号表符号表( (Symbol Table)Symbol Table)管理管理2022-5-13 BindingBinding的概念的概念 将符号名和相应目标数据将符号名和相应

2、目标数据( (的地址的地址) )对应起来对应起来 标识符与数据目标的对应标识符与数据目标的对应 变量名变量名数据存储单元地址数据存储单元地址 过程名、函数名过程名、函数名程序段入口地址程序段入口地址 相关问题相关问题 变量和过程的作用域，决定绑定的有效期变量和过程的作用域，决定绑定的有效期2022-5-14分段式程序分段式程序Program layerInt a,b,cBeginSub(a+b,b,a)EndSubroutine sub(x,y,z)Real a,b,cBeginEnd嵌套式程序嵌套式程序Program layer Int a,b,c Procedure sub1(x,y,z)

3、 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) Beginend2022-5-15 语言定义的标识符的生存期决定最终绑语言定义的标识符的生存期决定最终绑定的时机定的时机 全局变量：全程有效全局变量：全程有效程序装入时程序装入时 局部变量：分段有效局部变量：分段有效进入过程或分程序进入过程或分程序时时2022-5-16变量名的绑定变量名的绑定 静态静态( (Static)Static)绑定绑定 编译时指定（相对地址）编译时指定（相

4、对地址） 词法分析期间词法分析期间在符号表中建立变量的表项在符号表中建立变量的表项 回忆：说明语句的语义分析中的字节数计算，填写变量回忆：说明语句的语义分析中的字节数计算，填写变量地址（地址（enter)enter) 动态动态( (Dynamic)Dynamic)绑定绑定 运行时指定（具体地址运行时指定（具体地址/ /相对地址）相对地址） 回忆：动态数组回忆：动态数组2022-5-17 为过程指定程序代码段入口地址为过程指定程序代码段入口地址 静态绑定：编译时指定相对地址静态绑定：编译时指定相对地址 （词法分析：在符号表中建立过程的表项）（词法分析：在符号表中建立过程的表项） 语义分析：构造目

5、标代码，填写过程的入口地址语义分析：构造目标代码，填写过程的入口地址 如：函数、子程序如：函数、子程序 动态绑定动态绑定 运行时指定运行时指定函数名作为形式参数（函数名作为形式参数（formalsformals） 如：函数指针、虚函数（如：函数指针、虚函数（C+C+）2022-5-18 主要内容主要内容 运行时刻的内存划分运行时刻的内存划分( (Partition)Partition) 局部数据的静态分配局部数据的静态分配( (Static Allocation)Static Allocation) 局部数据的动态分配局部数据的动态分配( (Dynamic Allocation)Dynamic

6、 Allocation) 层次单元法层次单元法 栈式栈式( (Stack)Stack)存储分配策略存储分配策略 堆式堆式( (Heap)Heap)存储分配策略存储分配策略2022-5-19运行时刻的内存划分运行时刻的内存划分代码段代码段全局静态数据全局静态数据栈栈堆堆局部数据区中的一个栈单元局部数据区中的一个栈单元活动记录活动记录( (静态静态/ /动态分配动态分配) )数组区数组区临时工作单元区临时工作单元区简单变量区简单变量区形式单元区形式单元区寄存器保护区寄存器保护区返回地址返回地址2022-5-110 特点特点 编译时刻确定存储位置编译时刻确定存储位置 访问效率高访问效率高 主要用途主

7、要用途 子程序的目标代码段子程序的目标代码段 全局数据目标（全局变量）全局数据目标（全局变量） ？用什么样的算法实现静态存储分配？用什么样的算法实现静态存储分配2022-5-111 顺序分配算法顺序分配算法 按照程序段出现的先后顺序逐段分配按照程序段出现的先后顺序逐段分配1/222/153/184/176/105/23程序段程序段 区域区域 021 021 2236 2236 3754 3754 5571 5571 7294 7294 95104 95104共需要共需要105105个存储单元个存储单元程序段之间的调用关系程序段之间的调用关系程序段号程序段号/ /所需数据空间所需数据空间能用更少

8、的空间么？能用更少的空间么？2022-5-112分层分配算法分层分配算法 允许程序段之间的覆盖（覆盖可能性分析）允许程序段之间的覆盖（覆盖可能性分析）程序段程序段 区域区域6095022 4016323402173114162共需要共需要6363个存储单元个存储单元1/222/153/184/176/105/23思考：如何设计分配算法？思考：如何设计分配算法？原始总存储需求原始总存储需求=105=105个存储单元个存储单元2022-5-113begin real x,y,z x=a y=x*2+b z=1/y begin int a,b,c beginchar name,from,a end

9、end Sub2(x,y)endS1S2PP4嵌套式程序嵌套式程序program layerprogram layer int a,b,c int a,b,c procedure Sub1(x,y,z) procedure Sub1(x,y,z) int x,y,z int x,y,z procedure add(a,b) procedure add(a,b) real a,b real a,b begin begin Real x,y,z Real x,y,z x=a x=a y=x y=x* *2+b2+b z=1/y z=1/y end end begin begin end end p

10、rocedure procedure Sub2(x,y)Sub2(x,y) beginbeginsub1(a1,a2,a3)sub1(a1,a2,a3)endendPP3P2P1嵌套过程嵌套过程嵌套分程序嵌套分程序2022-5-114P4嵌套式程序嵌套式程序program layerprogram layer int a,b,c int a,b,c procedure Sub1(x,y,z) procedure Sub1(x,y,z) int x,y,z int x,y,z procedure add(a,b) procedure add(a,b) real a,b real a,b begi

11、n begin Real x,y,z Real x,y,z x=a x=a y=x y=x* *2+b2+b z=1/y z=1/y end end begin begin end end procedure procedure Sub2(x,y)Sub2(x,y) beginbeginsub1(a1,a2,a3)sub1(a1,a2,a3)endendPP3P2P1begin real x,y,z x=a y=x*2+b z=1/y begin int a,b,c beginchar name,from,a end end Sub2(x,y)endS1S2P6+6+6+12+6+12+6+3

12、+6+12+6+12+*6+12+6+12+6+6+12+6+6+12+*标准单元标准单元6+12+6+12+*2022-5-115编译原理编译原理(Principles of Compiling)n主讲：周翰逊主讲：周翰逊nEmailEmail：nQQQQ：26054036260540362022-5-116上次课主要内容上次课主要内容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

13、 ) |gen( C.false: ) | S2.codeC.codeS1.beginC.trueS.nextS1.codeC.false2022-5-117上次课主要内容上次课主要内容S.begin := SS.begin := S1 1. .next next := newlabel;:= newlabel;C.true := SC.true := S1 1.begin := newlabel;.begin := newlabel; C.false := S.next; C.false := S.next; S.code := gen( S.begin: ) |S.code := gen(

14、 S.begin: ) | C.code | C.code |gen( C.true: ) | Sgen( C.true: ) | S1 1.code | .code | gen( gotoS.begin )gen( gotoS.begin )C.codeS1.codegoto S.beginC.trueS1.beginC.falseS.nextS.begin2022-5-118上次课主要内容上次课主要内容 运行环境运行环境 绑定：静态、动态绑定：静态、动态 静态分配静态分配分层分配法分层分配法 动态分配动态分配 层次单元法层次单元法 每个分程序、过程都有一个层次单元，用来存每个分程序、过程都

15、有一个层次单元，用来存放当前可以用于分配的地址放当前可以用于分配的地址2022-5-119静态存储分配无法克服的问题静态存储分配无法克服的问题1 1 动态数组问题动态数组问题 层次单元法层次单元法 层次单元层次单元 进入分程序：将直接外层分程序的层次单元内容植入本层层进入分程序：将直接外层分程序的层次单元内容植入本层层次单元次单元 标准单元的使用标准单元的使用 调用语句：将本层层次单元内容送标准单元调用语句：将本层层次单元内容送标准单元 过程说明：将标准单元内容送本层层次单元过程说明：将标准单元内容送本层层次单元2022-5-120静态存储分配无法克服的问题静态存储分配无法克服的问题2 2 递

16、归调用问题递归调用问题 栈式存储分配栈式存储分配 特点特点 嵌套调用次序嵌套调用次序 先进后出先进后出 生存期限于本次调用生存期限于本次调用 自动释放自动释放2022-5-121 用途用途 活动记录活动记录栈单元栈单元对应一次过程调用所对应一次过程调用所需存储需存储 过程的局部数据区过程的局部数据区活动记录活动记录活动记录活动记录活动记录活动记录运行栈运行栈2022-5-122活动记录组活动记录组织示例织示例过程数据区过程数据区结构结构SPSPn nSPSPn-1n-1SPSP1 1SPSP0 0数组存储区数组存储区本本过过程程 所所辖辖分分 第第 临时工作单元临时工作单元程程 一一序序 层层

17、 局部数组说明局部数组说明存存 分分储储 程程 局部变量局部变量区区 序序 分程序分程序TOPTOP本过程本过程DisplayDisplay形式单元（形式单元（m+1m+1个）个）连连 主调分程序主调分程序TOPTOP接接 全局全局DisplayDisplay地址地址数数 返回地址返回地址据据 主调过程主调过程SPSP本过程本过程TOPTOPSPSPSPn n为第为第n n层过程数层过程数据区首址据区首址2022-5-123静态存储分配无法克服的问题静态存储分配无法克服的问题3 3 被调用者的生存期超过调用者被调用者的生存期超过调用者/ /局部数据需局部数据需要保留（要保留（ save sav

18、e ） 堆式存储分配堆式存储分配2022-5-124 用于动态数据结构用于动态数据结构 存储空间的动态分配和释放存储空间的动态分配和释放 实现方法实现方法 将内存空间分为若干块，根据用户要求分配将内存空间分为若干块，根据用户要求分配 无法满足时，调用无用单元收集程序将被释无法满足时，调用无用单元收集程序将被释放的块收集起来重新分配放的块收集起来重新分配2022-5-125 传值调用传值调用 call-by-valuecall-by-value 过程调用时计算实参过程调用时计算实参( (Actual)Actual)，将值存到活动记录将值存到活动记录 形参形参( (Formal)Formal)与活

19、动记录的实参绑定，运行时将形与活动记录的实参绑定，运行时将形参作为局部变量使用参作为局部变量使用调用者调用者被调用者被调用者直接使用直接使用A A实际参数实际参数A A形式参数形式参数X XA A的值的值单向传值单向传值 引用调用引用调用 Call-by-Reference/AddressCall-by-Reference/Address 如果实参如果实参( (地址地址) )具有左值，则存放其左值到活动具有左值，则存放其左值到活动记录中；否则计算出表达式的值，将此值存入一记录中；否则计算出表达式的值，将此值存入一个单元，并将该单元的地址传给被调用者个单元，并将该单元的地址传给被调用者调用者调用

20、者被调用者间址访问实参被调用者间址访问实参A AA A实参实参A A形参形参X XA A的地址的地址传地址传地址2022-5-127复制恢复复制恢复 Copy-RestoreCopy-Restore 将参数的左、右值同时传给被调用者，将参数的左、右值同时传给被调用者，被调用者直接使用右值，并将计算结果被调用者直接使用右值，并将计算结果按照左值返回给调用者按照左值返回给调用者调用者调用者被调用者被调用者A A实际参数实际参数A A形式参数形式参数X XA A的值的值传值传值/ /传地址传地址A A的地址的地址2022-5-128传名调用传名调用Call-by-NameCall-by-Name 将

21、被调过程的过程体复制到调用处，并将被调过程的过程体复制到调用处，并将每一个形参将每一个形参“文字地文字地”替换成实参替换成实参 用换名子程序实现用换名子程序实现ThunkThunk 是一种早期的语言是一种早期的语言ALGOLALGOL用的一种参用的一种参数传递方式数传递方式子程序子程序P(X,Y,Z);P(X,Y,Z);Y:=Y+1;Y:=Y+1; Z:=Z+X Z:=Z+X传值调用：传值调用：2 2传地址：传地址：X=T=5,Y=Z=AX=T=5,Y=Z=A=2=2A:=A+1=2+1A:=A+1=2+1A:=A+T=3+5A:=A+T=3+58 8复制恢复：复制恢复：X=T=5,Y=Z=A

22、=2X=T=5,Y=Z=A=2Y:=Y+1=3Y:=Y+1=3Z:=Z+X=2+5=7Z:=Z+X=2+5=7Y Y A=3 A=3Z Z A=7 A=77 7换名换名A:=A+1=3A:=A+1=3A:=A+A+B=3+3A:=A+A+B=3+3+3+39 9主程序主程序A:=2; B:=3;A:=2; B:=3;P(A+B, A, A);P(A+B, A, A);Print APrint A临时单元临时单元: : T:A+B=5T:A+B=52022-5-130 过程过程( (procedure)procedure) 子程序子程序( (subroutine)subroutine)、函数函数

23、( (function)function) 过程的定义与调用过程的定义与调用 形参和实参的结合：参数计算与传递形参和实参的结合：参数计算与传递 调用与返回调用与返回2022-5-131 调用方：当前环境的保存与恢复调用方：当前环境的保存与恢复 被调方：构造环境，参数绑定被调方：构造环境，参数绑定Main( ) Sub1( 10 )Sub1( x ) Sub2( x + 1 )Sub2( y ) Sub3( )2022-5-132 简单过程调用简单过程调用 实在参数的计算和保存实在参数的计算和保存 控制转移、返回地址的保存控制转移、返回地址的保存 实在参数和形式参数的结合实在参数和形式参数的结合

24、( (多种结合方式多种结合方式) ) 局部变量的处理局部变量的处理 返回值的处理返回值的处理 递归过程调用与过程参数递归过程调用与过程参数 每层过程调用信息的保存与相应信息的查找每层过程调用信息的保存与相应信息的查找2022-5-133用于表达式的计算用于表达式的计算局部数据局部数据寄存器、程序计数器寄存器、程序计数器（返回地址）（返回地址）保存实在参数的值或保存实在参数的值或地址地址存放返回值存放返回值保存调用者活动记录保存调用者活动记录地址等地址等( (SP)SP)用于存取嵌套外层过用于存取嵌套外层过程中的非局部名程中的非局部名( (DisplayDisplay) )访问链访问链控制链控制

25、链返回值返回值实在参数实在参数机器状态机器状态局部变量局部变量临时变量临时变量数组存储区数组存储区本本过过程程 所所辖辖分分 第第 临时工作单元临时工作单元程程 一一序序 层层 局部数组说明局部数组说明存存 分分储储 程程 局部变量局部变量区区 序序 分程序分程序TOPTOP本过程本过程DisplayDisplay形式单元（形式单元（m+1m+1个）个）连连 主调分程序主调分程序TOPTOP接接 全局全局DisplayDisplay地址地址数数 返回地址返回地址据据 主调过程主调过程SPSP本过程本过程TOPTOP2022-5-134int sub( i, p )int sub( i, p )

26、int i;int i;char char * *p;p; char buf32; char buf32; bufi = bufi = * *(p + i);(p + i); return i + 1; return i + 1; 临时变量临时变量: : t t1 1,t ,t2 2,t ,t3 3局部变量：局部变量：buf32buf32机器状态：机器状态：R R0 0, , , , R R9 9, SP, PC, PS, SP, PC, PS参数：参数：i, pi, p返回值返回值控制链控制链DisplayDisplay2022-5-135 分析参数的类型、分配地址分析参数的类型、分配地址

27、统计参数和返回值的空间需求统计参数和返回值的空间需求 与调用语句配合完成形与调用语句配合完成形/ /实参数的结合实参数的结合 符号表处理符号表处理 完成过程名的属性登记完成过程名的属性登记说明语句：说明语句： Procedure id(X1,X2,Xn)2022-5-136过程说明语句代码结构过程说明语句代码结构说明语句：说明语句： Procedure id(XProcedure id(X1 1,X,X2 2, ,X,Xn n) )代码结构代码结构X X1 1.code .code 按参数传递要求实现参数按参数传递要求实现参数X X1 1的传递，或者完成传递准备；的传递，或者完成传递准备；X

28、X2 2.code .code 按参数传递要求实现参数按参数传递要求实现参数X2X2的传递，或者完成传递准备；的传递，或者完成传递准备；X Xn n.code .code 按参数传递要求实现参数按参数传递要求实现参数XnXn的传递，或者完成传递准备；的传递，或者完成传递准备；完成动态存储分配相关的工作；完成动态存储分配相关的工作；进入过程体进入过程体2022-5-137过程调用语句的代码结构过程调用语句的代码结构过程调用语句过程调用语句id(Eid(E1 1,E,E2 2, , ,E ,En n) )E1.codea1:=E1.placeEn.codean:=En.place动态存储分配相关工

29、作动态存储分配相关工作goto pc+n+1param a1param ancall id.place，n需要一个队列需要一个队列存放存放a a1 1, a, a2 2, , , , a an n，以生成以生成2022-5-1381 1. . 在过程在过程 f f 中调用过程中调用过程 p p 时时a. a. 对实在参数求值，将结果存入对实在参数求值，将结果存入 p p 的活动记录参数域的活动记录参数域b. b. 在在 p p 的活动记录中存放返回地址的活动记录中存放返回地址和当前栈顶指针和当前栈顶指针c. c. 按照活动记录的大小，上移栈顶按照活动记录的大小，上移栈顶指针指针d. d. 控制

30、转到控制转到 p p 的入口（过程体）的入口（过程体）临时变量临时变量局部变量局部变量机器状态机器状态参数参数返回值返回值控制链控制链Display2022-5-139临时变量临时变量局部变量局部变量机器状态机器状态参数参数返回值返回值控制链控制链Display2. 2. 进入过程进入过程p p并执行并执行P Pa. a. 初值寄存器值和其它状态信息初值寄存器值和其它状态信息b. b. 执行过程体执行过程体3. 3. 从过程从过程 p p 返回返回( (对应对应returnreturn语句语句) )a. p a. p 在返回值域中保存返回值在返回值域中保存返回值b. b. 恢复原栈顶指针和其它

31、寄存器恢复原栈顶指针和其它寄存器c. c. 按返回地址返回调用者按返回地址返回调用者2022-5-140产生式产生式语义规则语义规则S call id ( Elist ) S.code := Elist.code |gen(goto pc+Elist.num+1)|for 队列队列q 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 q，并将并将t t

32、放入放入qElist Elist1,E Elist.num := Elist 1.num+1; Elist.code := Elist 1.code | E.code | t:=newtemp; gen(t:= E.place);将将t t 放入队列放入队列q2022-5-1412022-5-142t1:=bt1:=b* *c ct2:=t1-1t2:=t1-1t3:=x+yt3:=x+ygoto pc+5goto pc+5param t2param t2param t3param t3param xparam xparam yparam ycall f, 4call f, 42022-5-1

33、43赋值语句赋值语句x:=a+b+ x:=a+b+ t1:=a+bt1:=a+bt2:=bt2:=b* *c ct3:=t1-1t3:=t1-1t4:=x+yt4:=x+ygoto pc+5goto pc+52022-5-144procedure f(a,b,c,d);real f;real a,b,c,d;begin integer i,j; i:=f(a,a+b,c+a,d) j:=i+a+b; a:=i*jend在形在形/实结合实结合中，哪些细节中，哪些细节问题需要处理？问题需要处理？如何处理？如何处理？2022-5-145 种类种类关键字关键字( (保留字保留字) )表、层次表、符号表

34、表、层次表、符号表( (过过程表、变量表、标号表程表、变量表、标号表) )、常数表、常数表名字名字信息信息1 1信息信息2 2信息信息n nsum1sum1real real 所在层所在层定义定义/ /引用引用关键字表关键字表 表项结构表项结构 关键字名字关键字名字 ( (字符串，如字符串，如 whilewhile，if)if) 关键字标识关键字标识 ( (整数整数) ) 常用的操作：常用的操作： int IsKeyword( char Name )int IsKeyword( char Name )关键字名字关键字名字 关键字标识关键字标识beginbegin112112endend1131

35、13whilewhile1141142022-5-147 保存各级分程序、循环语句、条件语句的保存各级分程序、循环语句、条件语句的有关信息有关信息 如：局部名字、转移标号等如：局部名字、转移标号等 辅助实现标识符的管理辅助实现标识符的管理 标识符的作用域标识符的作用域所在层所在层 性质性质起点起点终点终点直接外层直接外层本层计数本层计数2022-5-148 保存名字及其属性保存名字及其属性 名字：变量名，过程名，标号名和常数名名字：变量名，过程名，标号名和常数名 属性：种类（属性：种类（KindKind），），类型（类型（TypeType），），长度，长度，作用域，标志（引用作用域，标志（引用/ /定义），地址等定义），地址等 种类：简单变量、数组、记录、结构、函种类：简单变量、数组、记录、结构、函数、常数、常量数、常数、常量 类型：整、实、复、布尔、字符、指针、类型：整、实、复、布尔、字符、指针、标号标号名字名字种类种类类型类型长度长度地址地址标志标志2022-5-149 作用作用 记录源程序中出现的各种符号的相关属性，记录源程序中出现的各种符号的相关属性，为编译提供相应的信息：地址、类型为编译提供相应的信息：地址、类型 建立表项（元组）建立表项（元组） 以标识符为关键字以标识符为关键字2022-5-150 实现