北大编译原理讲义

1、北大编译原理讲义北大编译原理讲义2 序 计算环境 运行时的环境 计算 目标代码 源程序中的名字（常量，变量）目标机存储空间。它受命于源程序的执行语义。 源程序由一组过程按某种规则组成。过程的一次执行称作一次活动，在过程的语句序列执行之前，过程中访问的对象构成此过程的运行环境，由运行支持程序组织好。编译程序根据如何组织运行环境而生成目标代码。映射源程序3 目的： 构造运行程序的策略和方法 6.1.1 过程 6.1.2 活动树 6.1.3 控制栈 6.1.4 说明的作用域 6.1.5 名字的绑定 6.1.6 构造运行程序和源程序有关的 一些问题46.1.1 过程 源程序由一组过程组成，不同的程序设

2、计语言，由过程构成源程序的方法不同。 构成源程序的两个过程行文，要么是嵌套的，要么是不相交的。5program sort（input，output）； var a ： array0.10 of integer； procedure readarray； var i ： integer； begin end； function partition （y ，z ： integer ）:integer； var i，j ，x，v： integer； begin end; procedure quicksort（m，n ： integer）； var i ： integer； begin end en

3、d； begin end.66.1.2 活动树活动树 程序执行期间的控制流： 1程序执行的控制是顺序的； 2过程的每一次执行都是从过程体的开头 开始，并最终把控制返回到紧接着该过 程被调用点的后面。 过程的一次活动: 过程体的每一次执行。 一个过程p的一次活动的生存期:在该过程体的执行中的第一步和最后一步之间的一序列步骤的执行时间，其中包括执行过程p所调用的过程的执行时间，以及这些过程所调用的过程的执行时间，如此等等。7 特点： 每当控制流从过程p的活动进入到过程q的活动中后，它将返回到过程p的同一次活动中。 如果a和b是两个过程活动，那么它们的生存期要么是不重叠的，要么是嵌套的。 这种活动生

4、存期的嵌套性质可以通过在每一个过程中插入两个打印语句来加以说明。8执行开始 enter readarray leave readarray enter quicksort（1，9） enter partition（1，9） leave partition（l，9） enter quicksort（1，3） . leave quicksort（1，3) enter quicksort（5，9） . leave quicksort（5，9） leave quicksort（1，9） 执行结束9 一个过程是递归的，如果同一过程的一次新的活动可以在前面活动结束以前开始。 用一颗树来描绘控制进入和离开活

5、动的途径。这祥的树称作活动树。在一棵活动树中： 1. 每一个结点代表一个过程的活动; 2. 根结点代表主程序的活动; 3. 代表a的结点是b结点的父结点当且仅当控 制从活动a进入活动b; 4. 结点a在结点b的左边当且仅当a的生存期 发生在b的生存期之前。 用活动树来讨论正在这个结点上的控制 。 10srq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)q(2,3)p(2,3)q(2,1)q(3,3)q(5,9)p(5,9)q(5,5)q(7,9)p(7,9)q(7,7)图6.3 一棵活动树11结论：一个结点代表一个唯一的活动， 且每 一个活动只有一个结点表示，当控制进 入某一个活动

6、时，可以直接说，控制在 这个结点上。6.1.3 控制栈 程序执行的控制流对应于从根开始，按先根次序遍历活动树。因此，用一个栈保存过程活动的生存踪迹。把它称作控制栈。 当一个活动开始执行时，把代表这个活动的结点推进栈；当这个活动结束时，把代表这个活动的结点从栈中弹出。12例6.2 栈和活动树的变化栈ssrS rq(1,9)S q(1.9)p(1,9)S q(1.9) p(1,9)q(1,3)S q(1.9) q(1,3)p(1,3)S q(1.9) q(1,3) p(1,3)q(1,0)S q(1.9) q(1,3) q(1,0)q(2,3)S q(1.9) q(1,3) q(2,3)13 控制

7、栈中的活动都是活跃的，当前控制进入的活动在栈顶，从栈顶活动到栈底活动的活动序列是从活动树上当前结点通向根的路径上的结点序列： s,q（1，9），q（l，3），q（2，3） 从栈底活动到栈顶活动的活动序列表示了活动的生存期的嵌套关系。 结论结论：扩充控制栈可用来实现如Pascal语言的栈式存储分配，进入一个活动，在栈顶建立这个活动所使用的存储空间；这个活动结束，从栈顶弹出其使用的存储空间。146.1.4 说明的作用域说明的作用域 1 .说明明把名字与名字的属性信息绑定在一起。 2 . 说明的作用域是一个说明起作用的范围 （源程序行文）。一个名字在源程序行文中 可能有几处说明，语言的作用域规则规定

8、： 在语句序列中引用的一个名字是在何处说 明的名字。 3 . 编译时，处理说明把名字及其属性信息填 写进符号表(add(id.entry,id.vul); 处理引用 名字时，查找这个名字的属性信息 （lookup(id),符号表管理程序根据语 言的 作用域规则，使 lookup(id)返回id的作作用域 中绑定的属性信息。15名字与存储的绑定名字与存储的绑定 名字与存储单元的绑定是指把源程序中的数据名字映射到目标机存储单元的过程。 引进两个函数，environment和state。environment把名字映射到一个存储单元上；state把存储单元映射到那里所存放的值上。可以说，函数envi

9、ronment把一个名字映射为一个l-value（左-值）,而函数state把一个l-value（左-值）映射为一个r-value（右-值）。如图所示。16名字存储单元值存储分配程序运行environmentstatel-valuer-value图6.5 从名字到值的两个阶段映射17静态概念 动态对应过程定义 过程活动名字说明 名字的绑定说明的作用域 活动的生存期186.1.6 提出的问题提出的问题 编译程序组织存储分配所采用策略和方法主要取决于对源程序中下面的问题的回答。 1过程可以是递归的吗？ 2当控制从过程的一次活动返回时，局部 名的值将发生什么 变化? 3一个过程可以访问非局部名吗？

10、4当调用过程时参数是怎样传递的？ 5过程可以作为参数被传递吗？ 6过程可以作为结果被返回吗？ 7. 可以在程序控制下进行动态存储分配吗？ 8. 显式的存储重新分配（指撤除分配后的分 配）是必须的吗？ 19例：函数的返回值是函数。Fun times x y=x*y val times=fn: int (int int) twice=times 2fun compose(f, g)=f(g(x) compose=fn: ( ) ( )val fourtimes=compose(twice,twice)206.2 存储组织存储组织 6.2.1 运行时刻内存的划分运行时刻内存的划分 运行时刻的存储空间

11、必须划分以用来存放: 1. 生成的目标代码; 2. 数据目标; 3. 用于保存过程活动踪迹的一个控制栈。 存储空间划分的各部分：21目标代码静态数据栈堆1. 编译后知道目标代 码的大小。2. pascal主程序中的 数据,c,FORTRAN3. 栈:Pascal,c4. 堆: Pascal,c226.2.2 活动记录活动记录 把过程的一个活动所需要的信息组织成一块连续的存储单元，称为活动记录。 一个活动所需要的信息的每个数据项有相同的生存期，因此，组织成一个活动记录是很自然的。 对于pascal语言来说，运行过程中，当调用一个过程时，在栈顶构筑它的活动记录；当这个过程的活动执行完后，把它从栈顶

12、弹出。 源语言不同，实现方法不同，组成活动记录的域不同。实现pascal语言的活动记录如图6.7所示。23返回值实在参数控制链访问链保存机器状态局部数据临时变量控制链:指向调用过程活动 的活动记录。访问链：指向本活动要访 问的非局部数据所在的 活动记录。保存机器状态：调用过程 活动在调用点的机器 状态，包括计数器， 各种寄存器的值。局部数据：过程中定义的 局部量。临时变量：编译产生。246.2.3 编译时刻的局部数据的设计编译时刻的局部数据的设计 局部数据域是编译时刻在分析过程中的说 明时设计的。例如： PROCEDURE sub(x,y:real); VAR i ,j:integer; a:

13、ARRAY1.5 OF real; e, f : real; BEGIN f :=e+i*j; END;25符号表名字 形 类型 偏移量活动记录布局返回值(top-sp,0) x 形 real 1(top-sp,1) y 形 real 2(top-sp,2)(top-sp,3)(top-sp,20) i int 20(top-sp,21) j int 21(top-sp,22) a array 22(top-sp,27) e real 27(top-sp,28) f real 2826中间代码* i j t1 * (top-sp ,20) (top-sp ,21) (top-sp ,29) +

14、 e t1 t2 + (top-sp ,27) (top-sp ,29) (top-sp ,30) itor t2 t3 itor (top-sp ,30) (top-sp ,31):= t3 f := (top-sp ,31) (top-sp ,28) 编译结束，知道每个过程的活动记录的长度，将其填写到相应的过程表中，运行时，调用哪个过程，就在运行栈顶，推进那个过程的活动记录（栈箭头加上活动记录长度）。276.3 运行时刻存储分配策略运行时刻存储分配策略 分配策略是： 1静态分配； 2栈式分配，或称栈式动态分配； 3堆式分配，或称堆式动态分配。 6.3 .1 静态存储分配 6.3 .2 栈式

15、存储分配 6.3 .3 堆式存储分配 采用哪种分配策略是由源语言的语义决定的。286.3 .1 静态存储分配 在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置，且这种绑定在运行时刻不再发生变化。 局部名字的值在过程活动停止后仍保留下来。 限制： 1.在编译时刻知道数据目标的大小和它们在 内存位置上 约束； 2.不能递归调用过程（一个过程的两个活动 的生存期不相交,一个过程的所有活动可以 使用同一个活动记录）； 3.不能动态地建立数据结构。29 （1）PROGRAM CNSUME （2） CHARACTER *50 BUF （3） INTEGER NEXT （4 CHARACTER C

16、，PRDUCE （5） DATA NEXT1，BUF/ / （6） CPRDUCE（）。 （7） BUF（NEXT：NEXT）C （8 NEXTNEXT1 （9） IF（C.NE. )GOTO 6 （10） WRITE（*，(A)）BUF （11） END 30(12）CHARACTER FUNCTION PRDUCE（） （13) CHARACTER * 80 BUFFER （14） INTEGER NEXT （15） SAVE BUFFER，NEXT (16) DATA NEXT81 （17） IF(）THEN （18) READ（*，（A)BUFFER （19） NEXT1 （20) E

17、ND IF （21） PRDUCEBUFFER（NEXT：NEXT） （22 ) NEXTNEXT1 （23 ) END 图图6.8 一个一个Fortran 77程序程序 31CNSUME目标代码PRDUCE目标代码Char *50 buf int next char cChar *80 buffer int next Cnsume活动记录prduce活动记录目标代码静态数据326.3.2 栈式存储分配栈式存储分配 基于控制栈的原理： 存储空间被组织成栈，活动记录的推人和弹出分别对应于活动的开始和结束。 与静态分配不同的是，在每次活动中把局部名字和新的存储单元绑定，在活动结束时，活动记录从栈中

18、弹出，因而局部名字的存储空间也随之消失。 例6.5 图表明当控制流通过图的活动树时活动记录被推人或弹出运行时刻的栈中的情况，设寄存器top标记栈顶。 33sSa:arraytoprri:integertoptopq(1,9)q(1,9)i:integertopp(1,9)p(1,9)i:integertoptopq(1,3)q(1,3)i:integertop图 6.11 栈式分配活动记录在栈中的变化34 确定活动记录中局部数据的地址：假设top-sp标记一个活动记录的开始的位置， dx表示x的地址相对于top-sp的偏移量。那么， x在过程的目标代码中的地址可写成 dx（top-sp）在运行

19、时刻，当把x的活动记录筑于栈顶时，寄存器top- sp被赋于实际的地址， top- sp可以是一个寄存器。调用序列和返回序列调用序列和返回序列 通过在目标代码中生成调用序列和返回序列实现过程的调用。激活一个过程的活动是执行35过程语句的结果。过程语句 p(e1,e2,en)的目标代码（调用序列）完成任务： 1. 调用者对实在参数求值，并把它们传送给 被调用过程的活动记录的参数域。 2调用者在被调用者的活动记录中存放返 回地址和老top-sp之值。之后调用者把 top一sp之值增加到图所示的位置。 3被调用者存放寄存器值和其它状态信息。 4被调用者初始化其局部数据并开始执行。36返回序列，return目标代码完成的任务是： 1被调用者在自己的活动记录的返回值域 中放一个返回值。 2利用状态域中的信息，被调用者恢复 top-sp和其