《编译原理(王晓斌)编译第三章.ppt》由会员分享，可在线阅读，更多相关《编译原理(王晓斌)编译第三章.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 控制结构第一节 语句级控制结构uu控控制制结结构构:程序员用来规定程序各个成分的执行流程的控制部分。uu语语句句级级控控制制结结构构:语言用来构造各种语句执行顺序的机制。u传统语言的三种语句级控制结构:顺序、选择、重复。一.顺序u顺序运算符；u语句括号begin.end u复合语句二.选择 1.if语句ALGOL 60的选择结构引起二义性if x0 then if x10 then x:=0 else x:=1000PL/1和Pascal的“最近匹配原则”ALGOL 68中if语句的结束符号fi ALGOL 68和Ada对else if 进行缩写 2.多重选择PL/1的select结构
2、SELECT:WHEN(A)S1;WHEN(B)S2;WHEN(C)S3;OTHERWISE S4;END 多种语言的case语句var operator:char;operand1,operand2,result:boolean;case operator of .:result:=operand1 and operand2;+:result:=operand1 or operand2;=:result:=operand1=operand2;end Dijkstra选择结构的非确定性if B1S1 B2 S2 B3 S3 .BN SN其中，Bi是布尔表达式，称为卫哨。若有多个卫哨为真时执行任
3、一Si。三.重复 1.计数器制导 当预先知道重复次数时,在循环计数器值的有限集合上重复。FORTRAN的DO循环中,用标号控制循环体 DO 7 I=1，10 A（I）=0 B（I）=07 CONTINUEPascal的for 语句u计数重复的值可在任何有序集上ufor.toufor.downtou在循环外循环控制变量的值无定义2.条件制导 while 循环：描述0或任意多次的重复 repeat until循环：至少一次以上的重复 ALGOL 68循环的一般形式：for i from j by k to m while b do.od Ada 的循环结构 loop /*可以在loop前加重复说明
4、*/循环体(语句序列)end loop;u重复说明可以是：while 或 for in 或 for in reverse u可由exit或exit when终止循环Dijkstra的卫哨命令表示法do B1S1 B2S2 .BNSNod四.语句级控制结构讨论u顺序、选择、重复是一定意义的抽象u关于goto语句的讨论u控制结构的选择五.用户定义控制结构 如：Pascal的计数控制变量可以是枚举类型第二节 单元级控制结构uu单单元元级级控控制制结结构构:规定程序单元之间控制流程的机制u四种单元级控制结构:显式调用,异常处理,协同程序,并发单元一.显式调用从属单元 1.调用方式 由调用语句使用被调用
5、单元的名字来进行调用 2.参数的两种绑定方式位置绑定 关键字绑定subprogram S(F1,F2,FN);endu位置绑定: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+zx、y为变参z为全局变量 4.别名 在单元激活期间,两个变量表示(共享)同一数据对象FORTRAN的EQUIVALENCE
6、语句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=jswap(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:
7、=(x-y*z)+u 是别名 */别名的消除 .废除可能引起别名的结构 .限制使用指针、变参、全局变量、数组等二.隐式调用单元异常处理 异常是指导致程序正常执行中止的事件，要靠发信号来引发，用异常条件来表示。有关异常处理的主要问题：（1）异常如何说明说明说明说明，它的作用域是什么？（2）异常如何发生发生发生发生（或如何发信号）？（3）发出异常信号时，如何控制要执行的单元（异常处理处理处理处理程序）？（4）发生异常时，如何绑定绑定绑定绑定相应的异常处理程序？（5）处理异常之后，控制流程流程流程流程转向何处？1.PL/1异常处理 异常的说明 ON 异常的引发 SIGNAL语言预定义了一些异常，如
8、ZERODIVIDE异常名可多次说明,以最新一个为准ON ZERODIVIDE BEGIN END可用“NO”限定异常的范围(NO ZERODIVIDE):BEGIN END2.CLU的异常处理 处理方法 .当过程P引发一个异常时,只能将其信号传送给调用P的过程。这样做的目的使程序有良好的结构，但在表达力方面要弱一些。.发信号的过程被终止,而不再恢复。过程内可以发信号的那些异常必须在过程头加以说明 coca_cola=proc(a:int,s:string)returns(int)signals(zero(int),overflow,had_format(string)异常处理程序静态绑定于调
9、用者 exceptend其中，的形式是 when:when:3.Ada的异常处理异常的说明类似于变量的类型说明PECULIAR,BUFFER_FULL,ERROR:exception;程序单元可以显式引发异常 raise;异常处理程序紧跟在子程序、程序包或分程序之后begin;exception when HELP=;when DESPERATE=;end;若引发异常的单元为异常提供处理程序,控制将直接转移到那个处理程序,一旦处理程序执行完后,引发异常的单元也终止 若当前执行的单元U并未提供相应的异常处理程序,异常将被传播传播传播传播:若U是一个分程序,那么终止U的执行,并在包围U的单元内隐式
10、引发这个异常;若U是一个程序包体,那么异常传传传传播播播播给包含这个程序包说明的单元三.SIMULA 67协同程序 1.两个或两个以上程序单元之间交错地执行,这样的程序称为协同程序协同程序 2.SIMULA 67的协同程序是一个类实例 一般形式为:class 类名(参数);参数说明;begin 说明;语句表1;detach;语句表2end若设类x,变量y1和y2是对x的引用,那么可写成:y1:-new x();y2:-new x();当遇到一个new时,建立类的一个新实例,并执行类体 3.玩牌游戏begin boolean gameover;integer winner;class playe
11、r(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
12、 until 3 do p(i).next:-p(i+1);p(4).next:-p(1);resume(1);打印胜利者(winner)end四.并发单元 1.一个例子 “生产者-消费者”问题单元producer单元consumerrepeat 生产一个元素;存放这个元素到缓冲区;foreverrepeat 从缓冲区移出一项;对该项执行某个运算;forever 2.几个基本概念 并发单元的特点:诸程序单元并行活动 同步问题u正确访问缓冲区:不会向已满的缓冲区写数据,不会从空缓冲区读数据u动作的”不可分”与”可分”设t表示所存项目总数,append是生产者向缓冲区存数的操作,remove是消费
13、者从缓冲区取数的操作,这两个操作都要修改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
14、):if s0 then s:=s-1 else 挂起当前进程 V(s):if 信号灯上有挂起的进程 then 唤醒进程 else s:=s+1原语P、V是不可再分的原子操作信号灯满足的要求u记录挂起的进程（用队列）u唤醒策略（考虑优先级、时间等）一个例子 “生产者-消费者”问题const n=20shared var 缓冲区长度n,缓冲区项目总数t;semaphare mutex:=1;用于保证互斥 in:=0;用于同步，可挂起consumer spaces:=n;用于同步，可挂起producerprocess producer;var i:integer;repeat produce(i);P(spaces);等待自由空间 P(mutex);等待缓冲区可用 添加项目i到缓冲区;V(mutex);终止访问缓冲区 V(in);缓冲区项目数加1 foreverend producer;process consumer;var j:integer;repeat P(in);等待缓冲区项目 P(mutex);等待缓冲区可用 从缓冲区移出一个项目到j;V(mutex);终止访问缓冲区 V(spaces);缓冲区增加一个自由空间 foreverend consumer;注意注意:在访问共享资源前,不能忘记执行一次P操作;释放资源时不要忽略执行一次V操作第三章习题所有习题均为思考题