编译原理（王晓斌）编译第三章.ppt

第三章 控制结构 第一节 语句级控制结构 uu控制结构控制结构:程序员用来规定程序各个成分 的执行流程的控制部分。 uu语句级控制结构语句级控制结构:语言用来构造各种语句 执行顺序的机制。 u传统语言的三种语句级控制结构:顺序、 选择、重复。 一. 顺序 u顺序运算符； u语句括号begin . . . end u复合语句 二. 选择 1. if语句 ALGOL 60的选择结构引起二义性 if x0 then if x 或 for in 或 for in reverse u可由exit或exit when终止循环 Dijkstra的卫哨命令表示法 do B1S1 B2S2 . . . . . . BNSN od 四. 语句级控制结构讨论 u顺序、选择、重复是一定意义的抽象 u关于goto语句的讨论 u控制结构的选择 五. 用户定义控制结构 如：Pascal的计数控制变量可以是枚举 类型 第二节 单元级控制结构 uu单元级控制结构单元级控制结构:规定程序单元之间控制 流程的机制 u四种单元级控制结构:显式调用,异常处 理,协同程序,并发单元 一. 显式调用从属单元 1.调用方式 由调用语句使用被调用单元的名字来 进行调用 2. 参数的两种绑定方式 位置绑定 关键字绑定 subprogram S(F1,F2,FN); end u位置绑定: call S(A1,A2,AN) call S(A1,A3,A8,A10) u关键字绑定: call S(A1=F1,A3=F3,A8=F8,A10=F10) 3. 副作用 对非局部环境的修改 副作用降低了程序的可读性 副作用限制了数学运算律的使用 如:w:=x+f(x,y)+z 副作用影响目标代码的优化 如:u:=x+z+f(x,y)+f(x,y)+x+z x、y为变参 z为全局变量 4.别名 在单元激活期间,两个变量表示(共享)同一 数据对象 FORTRAN的EQUIVALENCE语句 Pascal的变参使得形参和实参共享同一数 据对象 procedure swap(var x,y:integer); begin x:=x+y; y:=x-y; x:=x-y; end; 调用 swap(a,a); swap(bi,bj); 若i=j swap(p,q); 若p、q指向同一数据对象 变参和全局变量表示同一数据对象时，也 会引起别名 procedure swap(var x:integer); /*a是全局变量*/ begin x:=x+a; a:=x-a; x:=x-a; end; 调用 swap(a); 将产生不正确的结果 别名也影响编译器生成优化的代码 a:=(x-y*z)+w /* 若a与x、y或z中任一个 b:=(x-y*z)+u 是别名 */ 别名的消除 .废除可能引起别名的结构 .限制使用指针、变参、全局变量、数组 等 二. 隐式调用单元异常处理 异常是指导致程序正常执行中止的事件 ，要靠发信号来引发，用异常条件来表 示。 有关异常处理的主要问题： （1）异常如何说明说明，它的作用域是什么？ （2）异常如何发生发生（或如何发信号）？ （3）发出异常信号时，如何控制要执行的单元 （异常处理处理程序）？ （4）发生异常时，如何绑定绑定相应的异常处理程 序？ （5）处理异常之后，控制流程流程转向何处？ 1. PL/1异常处理 异常的说明 ON 异常的引发 SIGNAL 语言预定义了一些异常， 如 ZERODIVIDE 异常名可多次说明,以最新一个为准 ON ZERODIVIDE BEGIN END 可用“NO ”限定异常的范围 (NO ZERODIVIDE): BEGIN END 2. CLU的异常处理 处理方法 .当过程P引发一个异常时,只能将其信号 传送给调用P的过程。这样做的目的使程 序有良好的结构，但在表达力方面要弱一 些。 .发信号的过程被终止,而不再恢复。 过程内可以发信号的那些异常必须在过 程头加以说明 coca_cola=proc(a:int,s:string) returns(int) signals (zero(int),overflow,had_format(string) 异常处理程序静态绑定于调用者 exceptend 其中，的形式是 when : when: 3. Ada的异常处理 异常的说明类似于变量的类型说明 PECULIAR,BUFFER_FULL,ERROR:exception; 程序单元可以显式引发异常 raise ; 异常处理程序紧跟在子程序、程序包或 分程序之后 begin ; exception when HELP=; when DESPERATE=; end; 若引发异常的单元为异常提供处理程序, 控制将直接转移到那个处理程序, 一旦处理程 序执行完后, 引发异常的单元也终止 若当前执行的单元U并未提供相应的异常 处理程序,异常将被传播传播: 若U是一个分程序, 那 么终止U的执行, 并在包围U的单元内隐式引发 这个异常; 若U是一个程序包体, 那么异常传播传播 给包含这个程序包说明的单元 三. SIMULA 67协同程序 1. 两个或两个以上程序单元之间交错地 执行,这样的程序称为协同程序协同程序 2. SIMULA 67的协同程序是一个类实例 一般形式为: class 类名(参数); 参数说明; begin 说明; 语句表1; detach; 语句表2 end 若设类x, 变量y1和y2 是对x的引用, 那么可 写成: y1:-new x(); y2:-new x(); 当遇到一个new时, 建 立类的一个新实例, 并 执行类体 3. 玩牌游戏 begin boolean gameover; integer winner; class player(n,hand); integer n; integer array hand(1:13); begin ref(player) next; detach; while not gameover do begin 出牌; if gameover then winner:=n else resume(next) end end ref(player) array p(1:4);integer i; integer array cards(1:13); for i:=1 step 1 until 4 do begin 第i家拿牌; p(i):-new player(i, cards) end; for i:=1 step 1 until 3 do p(i).next:-p(i+1); p(4).next:-p(1); resume (1); 打印胜利者(winner) end 四.并发单元 1. 一个例子 “生产者-消费者”问题 单元producer单元consumer repeat 生产一个元素; 存放这个元素到缓冲区; forever repeat 从缓冲区移出一项; 对该项执行某个运算; forever 2. 几个基本概念 并发单元的特点:诸程序单元并行活动 同步问题 u正确访问缓冲区:不会向已满的缓冲区写数据, 不会从空缓冲区读数据 u动作的”不可分”与”可分” 设t表示所存项目总数,append是生产者向 缓冲区存数的操作,remove是消费者从缓冲区 取数的操作,这两个操作都要修改t的值,相应 执行操作(1)t:=t+1和(2)t:=t-1来实现。假定 (1)和(2)是这样实现的: 读t到一个专用寄存器; 更新更新专用寄存器的值; 将专用寄存器的值写到t; u互斥:执行(1)时不能开始执行(2),反之亦然。 即,(1)和(2)必须以互斥互斥的方式执行,(1)或(2) 就像不可分的操作。 进程的并发性:诸进程的执行概念上是可 重叠的（即正在执行的进程尚未终止，另一个 进程可能开始执行）。 3. 信号灯 信号灯是一个数据对象,该数据对象采用一个 整数值,并可用原语P和V对它进行操作。信号 灯在说明时,以某个整数值对它初始化。 P、V操作的定义 P(s): if s0 then s:=s-1 else 挂起当前进程 V(s): if 信号灯上有挂起的进程 then 唤醒进程 else s:=s+1 原语P、V是不可再分的原子操作 信号灯满足的要求 u记录挂起的进程（用队列） u唤醒策略（考虑优先级、时间等） 一个例子 “生产者-消费者”问题 const n=20 shared var 缓冲区长度n,缓冲区项目总数t; semaphare mutex:=1; 用于保证互斥 in:=0; 用于同步，可挂起consumer spaces:=n; 用于同步，可挂起 producer process producer; var i:integer; repeat produce (i); P(spaces); 等待自由空间 P(mutex); 等待缓冲区可用 添加项目i到缓冲区; V(mutex); 终止访问缓冲区 V(in); 缓冲区项目数加1 forever end producer; process co