第八章顺序控制.ppt
《第八章顺序控制.ppt》由会员分享,可在线阅读,更多相关《第八章顺序控制.ppt(63页珍藏版)》请在三一文库上搜索。
1、第八章 顺序控制,2,顺序控制提供了操作和数据被组合成程序和程序集合的框架。 涉及两个方面的问题: 操作执行顺序的控制(顺序控制) 数据在子程序间的传递(数据控制),3,执行顺序控制,控制的层次和形式 语句内(即表达式)的顺序控制 算术表达的顺序控制 非算术表达式的顺序控制 语句间的顺序控制,4,8.1 隐式和显式顺序控制,顺序控制结构可分为四组: 1、用于表达式中的结构(也针对语句,表达式是语句的基本建筑块)。如:优先级规则和括号。 2、用于语句或语句组间的结构。如:条件和迭代。 3、用于申明式程序设计语言的程序结构。如逻辑程序设计语言 4、用于子程序间的结构,如:子程序调用和协同例程。 这
2、种分法并不是精确的,如LISP和APL中只有表达式而无语句。 顺序控制结构可以是隐含的(缺省的)(由语言定义,除非程序员显式修改)或显式的(程序员可用来修改隐含顺序)。,5,8.2 算术表达的顺序控制,考虑方程求根: 该公式至少涉及15个分开的操作,用汇编或机器语言至少需要15条指令甚至更多。而写成Fortran程序则为: ROOT=(-B+SQRT(B*2-4*A*C)/(2*A) 这是自然的表达方法,由翻译器而不是程序员来考虑各种优化问题。 然而,翻译器如何控制正确的操作顺序?,6,算术表达的顺序控制,算术表达式的表示 语法:直观表示和形式化表示 语义:决定计值方式和过程 运算符的优先级
3、算术表达式在执行时的表示,7,树结构表示,目前,我们将表达式考虑为单个实体,忽略了其计值必需的实际语法和语义。 表达式中的基本顺序控制机制是“函数复合”:刻划操作及其操作数。 函数复合使表达式呈树结构特征,根为主操作,中间节点为中间层次操作,叶为操作数。,8,树结构表示,求方程根的表达式的树。 树表示阐明了表达式的控制结构,低层的数据引用和操作作为高层操作的操作数,必须先计值,但树表示也留下一些计值顺序没有指定。 如:B和B*2谁先计值?B是否可组合为同一引用? 通常语言定义只在树表示级定义表达式计值顺序,允许实现者决定计值细节。,返回,9,表达式的语法,表达式(a+b)(ca)的树结构,10
4、,表达式的语法,表达式可表示为树结构,但为了在程序中表示,线性化是需要的。 前缀(波兰前缀)记法。 这是波兰数学家发明的无括号记号法。如:f(x,y,z),+ab-ca LISP使用了该记号法的变种,称为剑桥波兰,用括号将操作符及其操作数括起来,如:(X(+ab)(-ca)。 后缀(逆波兰)记号法 类似于前缀,但操作符数在后面,如:ab+ca- 中缀记号法 最适合二元操作,也是我们最常用的方式。,返回,11,表达式的语义 (1/3),上三种记号法对语言的设计都有一些有用的属性,在如何计算表达式值方面也有不同。 前缀计值 可以通过一遍扫描计值每个表达式,然而需要知道每个操作的操作数量。除了可省去
5、括号外,前缀表达式在语言设计中有如下价值: 1、一般的函数调用均采用前缀方式。 2、可表示有任意数量操作数的操作,写表达式只需一个语法规则。 3、解码可以机械地很容易地进行,将其翻译成简单代码序是容易的。,12,表达式的语义 (1/3),前缀计值 下面算法用一个执行栈计值表达式:对表达式P, 1、如P中下一项是操作子,压入栈项,设置所需参数数目。 2、如P中下一项是操作数,压入栈项。 3、如栈项n项是操作数(对栈中第一个n元操作),则可以进行计值,用计值结果替代该操作符和操作数。,13,表达式的语义 (2/3),后缀计值 后缀计值时,操作符紧跟其操作数后而且操作数已被计值。 1、如P中下一项是
6、操作数,压入栈顶 2、如P中下一项是n元操作符,n个参数必须是栈顶部的n个元素,计算结果并替换这n个元素。 这种计值策略直接、简单,是很多翻译器中生成表达式代码的基础。,14,表达式的语义 (3/3),中缀计值 中缀是常见的,但用于程序语言中会导致一些问题: 1、只适合于二元操作。语言单用中缀是不够的,还需使用前缀,这二者的混合使翻译更为复杂。 2、表达式中涉及多个中缀操作时,如不使用括号,则存在固有二义性。为解决这个问题,通常引入隐含的规则。,返回,15,操作子计值顺序,16,操作的层次,即操作的优先规则,返回,同一层次操作的计算顺序的隐含规则 优先级对算术表达式是适用的,因为表达式语义的数
7、学模型已对大多数程序员熟知的。,结合律,17,结合律,然而,当语言引入新的,不是源自传统数学的操作符时,优先规则可能不再有用,因此,需要有不同方法来处理扩展的操作集。 C语言:使用扩展的优先规则集合,大多数使用从左到右的结合律。大多数C规则是合理的。 APL:操作数为数组和矢量,语言没有优先规则。所有表达式计值从右到左。这规则对大多数表达式也是合理的,除了一些典型的表达式,如a-b-c-意为a-(b-c)。 Smalltalk:模型类似APL,没有优先规则,表达式计值从左到右。 Forth:用于实时过程控制。其运行时结构为栈,语言是纯后缀的,没有优先规则。,返回,18,执行时表示,对中缀形式的
8、表达式的解码是困难的,需要翻译为易于解码的可执行形式。通常的选择有: 1、机器代码序列 表达式被直接翻译成实际的机器代码,而不是先翻译为中间形式。指令顺序反映了初始表达式的顺序控制结构。 机器代码序列必须使用显式的临时存储位置来保持中间结果,允许使用硬件解释器,因此,执行速度快。 2、树结构 表达式可以以其自然的树结构直接执行(使用软件解释器)。执行通过简单的树遍历来完成。 这是LISP中使用的典型技术,整个程序被表示为树结构。,19,执行时表示,3、前缀或后缀形式 这两种形式可用前面给出的解释算法来执行。 在某些基于堆栈组织的实际计算机中,实际的机器代码表示为后缀形式。 前缀表示是SNOBO
9、L4程序的执行形式,执行从左到右进行。 每个操作递归地调用解释器来计值其操作数。,20,表达式的树表示的计值,表达式翻成树结构虽有困难,但总体上是直接的。 而树到可执行原语序列的翻译,则涉及计值顺序的一些微妙问题。在代码生成中出现的计值顺序问题有: 问题一:统一的计值规则 问题二:副作用,Side effect。 问题三:出错条件 问题四:短路布尔表达式,21,表达式的计值(1):统一的计值规则,对表达式树中的每个操作结点,首先计值其操作数(或生成相应代码),然而应用操作到计算出的操作数上(或生成相应代码)积极计值规则(eager)。 对有些表达式来说,计值发生的顺序并不重要,可以选择以优化存
10、储和其他机器特性。 例,对(a+b)(c-a),下列顺序均可接受。 顺序一:取a的右值 顺序二:取c的右值 取b的右值 取b的右值 a+bd 取a的右值 取c右值 c-ae c-ae a+bd def表达式的右值 def,22,表达式的计值(1):统一的计值规则,但是,并不是在任何情况下都可以使用这种统一的计值规则。 例如,包含条件的表达式: Z+(Y=0?X:X/Y),当Y0时,计算X/Y,23,表达式的计值(1):统一的计值规则,采用统一规则,对IF操作,需先计算操作数,即使Y=0。 显然,此时我们不希望所有操作数被计值。 从而,我们有另一个规则:永不在应用操作之前计值操作数。 即,总是不
11、计值地传递操作数,由作用操作决定什么时候计值操作数Lazy计值。 然而,对此规则,在很多情况下是不实际的。比如:如何仿真未计值操作数到操作的传递?这需要软件仿真。 这两种计值规则:积极和隋性(lazy),对应子程序参数传递的按值和按名。 对表达式而言,没有简单的统一规则是完全令人满意的,通常规则是混合的。,24,表达式的计值(2):副作用,表达式中使用有副作用的操作,一直是语言设计中的争论点。 考虑:afun(x)+a 对乘法:需先取a的右值并计值fun(x) 对加法:需取a的右值,并计算乘法。 显然,我们希望只取a一次并应用到两个地方,而且fun(x)的计值在取a的前或后并无区别。 但如fu
12、n有副作用,改变了a的值,则计值序成为关键。 如a值本为1,但fun执行后值为3,并改a为2。则表达式可能值为: 1、顺序计值:13+2=5 2、取a一次:13+1=4 3、在取a前调用fun:23+2=8 执行序不同导致不同结果。,25,表达式的计值(2):副作用,对表达式中副作用的使用有两种选择: 1、不允许副作用 不允许有副作用的函数或对副作用可能影响的表达式的值改为未定义。 2、允许副作用 但语言定义应精确地给出计值顺序,这将使很多优化不可能。 通常,语句允许有副作用,如:赋值必须产生副作用。,26,表达式的计值(3):出错条件,对可能失败和产生出错条件的操作,涉及一种特殊的副作用。一
13、般的副作用只涉及到程序员定义的函数,而出错条件可能在很多原操作中出现(溢出、被零除等)。 这类副作用是不希望被排除的,而出错条件的意义在于其出现甚至会受到表达式的计值顺序的影响。这样,程序员需要精确的计值顺序控制。,27,表达式的计值(4):短路布尔表达式,考虑例子: if (A=0)|(B/AC) While(IC) 两个例子中,第二个条件可能产生出错条件。第一个操作数用于防止错误产生。 在很多语言中,求布尔操作需先计值操作数,这将产生不期望的错误,因为人们期望左操作数短路右操作数。 Ada中提供了两个特殊的布尔操作来解决这个问题。 and then 和 or else。显式地提供短路机制。
14、 例:if (A=0) or else (B/AC) then 这将不会失败,因A=0将导致整个表达式计值结束。,返回,28,8.3 语句间的顺序控制,基本语句 语句级顺序控制的形式 语句级顺序控制的语句 结构化顺序控制 结构的程序设计简介 结构顺序控制语句 结构顺序控制中的问题 顺序控制的结构化:素程序,29,基本语句,任何程序的结果由其基本语句确定。这里我们不再考虑语句中表达式,而是将语句作为考虑的单元来代表一单步计算。 数据对象的赋值 通过向数据对象赋值而改变计算状态是影响计算状态的主要机制。,30,基本语句,数据对象的赋值 赋值语句 主要目的是将某表达式的右值赋给某数据对象的左值。 赋
15、值为每个基本数据类型定义的中心操作。 输入语句 大多数语言有一种语句形式,从终端用户、文件或通讯线读数据。这样的语句也通过赋值改变变量的值。 其他赋值操作 参数传递:给形参赋值 隐含赋值:如SNOBOL4中的引用,Prolog目标匹配,声明时初始值等。,返回,31,语句级顺序控制的形式,三种主要的语句级顺序控制: 复合:语句顺序放置,顺序执行。 选择:两个语句序列可形成选择,使得一个或另一个序列被执行,但不能同时执行。 迭代:一个语句序列被重复执行零次或多次。 这是三种常见结构,语句被组成这三种结构而形成程序。,返回,32,显式顺序控制,goto语句,两种形式 无条件goto和条件goto G
16、oto语句导致无结构的设计。语言的很多形式模型均不允许goto存在。 此外,goto也是多余的,没有goto也可以写出同样能力的程序。 Break语句 通常使控制被前移到一个显式点(在给定控制结构的结束处)。 如C中Break语句使得立即退出while、for、switch语句。 C中还有Continue语句,只结束本次循环。,33,结构化break语句,返回,34,结构的程序设计,70年代,goto语句受到很大攻击,以至有的语言完全删去了goto。goto 语句有一些优点: 如果标号只是局部语法标记,则对高效执行有直接的硬件支持。 在小程序中使用简单、容易。 为汇编语言和老语言用户熟悉。 可
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八 顺序 控制
链接地址:https://www.31doc.com/p-5170968.html