第八章顺序控制.ppt

第八章 顺序控制,2,顺序控制提供了操作和数据被组合成程序和程序集合的框架。 涉及两个方面的问题： 操作执行顺序的控制（顺序控制） 数据在子程序间的传递（数据控制）,3,执行顺序控制,控制的层次和形式 语句内（即表达式）的顺序控制 算术表达的顺序控制 非算术表达式的顺序控制 语句间的顺序控制,4,8.1 隐式和显式顺序控制,顺序控制结构可分为四组： 1、用于表达式中的结构（也针对语句，表达式是语句的基本建筑块）。如：优先级规则和括号。 2、用于语句或语句组间的结构。如：条件和迭代。 3、用于申明式程序设计语言的程序结构。如逻辑程序设计语言 4、用于子程序间的结构，如：子程序调用和协同例程。 这种分法并不是精确的，如LISP和APL中只有表达式而无语句。 顺序控制结构可以是隐含的（缺省的）（由语言定义，除非程序员显式修改）或显式的（程序员可用来修改隐含顺序）。,5,8.2 算术表达的顺序控制,考虑方程求根： 该公式至少涉及15个分开的操作，用汇编或机器语言至少需要15条指令甚至更多。而写成Fortran程序则为： ROOT=(-B+SQRT(B*2-4*A*C)/(2*A) 这是自然的表达方法，由翻译器而不是程序员来考虑各种优化问题。 然而，翻译器如何控制正确的操作顺序？,6,算术表达的顺序控制,算术表达式的表示 语法：直观表示和形式化表示 语义：决定计值方式和过程 运算符的优先级 算术表达式在执行时的表示,7,树结构表示,目前，我们将表达式考虑为单个实体，忽略了其计值必需的实际语法和语义。 表达式中的基本顺序控制机制是“函数复合”：刻划操作及其操作数。 函数复合使表达式呈树结构特征，根为主操作，中间节点为中间层次操作，叶为操作数。,8,树结构表示,求方程根的表达式的树。 树表示阐明了表达式的控制结构，低层的数据引用和操作作为高层操作的操作数，必须先计值，但树表示也留下一些计值顺序没有指定。 如：B和B*2谁先计值？B是否可组合为同一引用？ 通常语言定义只在树表示级定义表达式计值顺序，允许实现者决定计值细节。,返回,9,表达式的语法,表达式(a+b)×(ca)的树结构,10,表达式的语法,表达式可表示为树结构，但为了在程序中表示，线性化是需要的。 前缀（波兰前缀）记法。 这是波兰数学家发明的无括号记号法。如：f(x,y,z)，×+ab-ca LISP使用了该记号法的变种，称为剑桥波兰，用括号将操作符及其操作数括起来，如：(X(+ab)(-ca)。 后缀（逆波兰）记号法 类似于前缀，但操作符数在后面，如：ab+ca-× 中缀记号法 最适合二元操作，也是我们最常用的方式。,返回,11,表达式的语义 （1/3）,上三种记号法对语言的设计都有一些有用的属性，在如何计算表达式值方面也有不同。 前缀计值 可以通过一遍扫描计值每个表达式，然而需要知道每个操作的操作数量。除了可省去括号外，前缀表达式在语言设计中有如下价值： 1、一般的函数调用均采用前缀方式。 2、可表示有任意数量操作数的操作，写表达式只需一个语法规则。 3、解码可以机械地很容易地进行，将其翻译成简单代码序是容易的。,12,表达式的语义 （1/3）,前缀计值 下面算法用一个执行栈计值表达式：对表达式P， 1、如P中下一项是操作子，压入栈项，设置所需参数数目。 2、如P中下一项是操作数，压入栈项。 3、如栈项n项是操作数（对栈中第一个n元操作），则可以进行计值，用计值结果替代该操作符和操作数。,13,表达式的语义 （2/3）,后缀计值 后缀计值时，操作符紧跟其操作数后而且操作数已被计值。 1、如P中下一项是操作数，压入栈顶 2、如P中下一项是n元操作符，n个参数必须是栈顶部的n个元素，计算结果并替换这n个元素。 这种计值策略直接、简单，是很多翻译器中生成表达式代码的基础。,14,表达式的语义 （3/3）,中缀计值 中缀是常见的，但用于程序语言中会导致一些问题： 1、只适合于二元操作。语言单用中缀是不够的，还需使用前缀，这二者的混合使翻译更为复杂。 2、表达式中涉及多个中缀操作时，如不使用括号，则存在固有二义性。为解决这个问题，通常引入隐含的规则。,返回,15,操作子计值顺序,16,操作的层次,即操作的优先规则,返回,同一层次操作的计算顺序的隐含规则 优先级对算术表达式是适用的，因为表达式语义的数学模型已对大多数程序员熟知的。,结合律,17,结合律,然而，当语言引入新的，不是源自传统数学的操作符时，优先规则可能不再有用，因此，需要有不同方法来处理扩展的操作集。 C语言：使用扩展的优先规则集合，大多数使用从左到右的结合律。大多数C规则是合理的。 APL：操作数为数组和矢量，语言没有优先规则。所有表达式计值从右到左。这规则对大多数表达式也是合理的，除了一些典型的表达式，如a-b-c-意为a-(b-c)。 Smalltalk：模型类似APL，没有优先规则，表达式计值从左到右。 Forth：用于实时过程控制。其运行时结构为栈，语言是纯后缀的，没有优先规则。,返回,18,执行时表示,对中缀形式的表达式的解码是困难的，需要翻译为易于解码的可执行形式。通常的选择有： 1、机器代码序列 表达式被直接翻译成实际的机器代码，而不是先翻译为中间形式。指令顺序反映了初始表达式的顺序控制结构。 机器代码序列必须使用显式的临时存储位置来保持中间结果，允许使用硬件解释器，因此，执行速度快。 2、树结构 表达式可以以其自然的树结构直接执行（使用软件解释器）。执行通过简单的树遍历来完成。 这是LISP中使用的典型技术，整个程序被表示为树结构。,19,执行时表示,3、前缀或后缀形式 这两种形式可用前面给出的解释算法来执行。 在某些基于堆栈组织的实际计算机中，实际的机器代码表示为后缀形式。 前缀表示是SNOBOL4程序的执行形式，执行从左到右进行。 每个操作递归地调用解释器来计值其操作数。,20,表达式的树表示的计值,表达式翻成树结构虽有困难，但总体上是直接的。 而树到可执行原语序列的翻译，则涉及计值顺序的一些微妙问题。在代码生成中出现的计值顺序问题有： 问题一：统一的计值规则 问题二：副作用，Side effect。 问题三：出错条件 问题四：短路布尔表达式,21,表达式的计值(1)：统一的计值规则,对表达式树中的每个操作结点，首先计值其操作数（或生成相应代码），然而应用操作到计算出的操作数上（或生成相应代码）积极计值规则（eager）。 对有些表达式来说，计值发生的顺序并不重要，可以选择以优化存储和其他机器特性。 例，对(a+b)×(c-a)，下列顺序均可接受。 顺序一：取a的右值 顺序二：取c的右值 取b的右值 取b的右值 a+bd 取a的右值 取c右值 c-ae c-ae a+bd d×ef表达式的右值 d×ef,22,表达式的计值(1)：统一的计值规则,但是，并不是在任何情况下都可以使用这种统一的计值规则。 例如，包含条件的表达式： Z+(Y=0？X：X/Y)，当Y0时，计算X/Y,23,表达式的计值(1)：统一的计值规则,采用统一规则，对IF操作，需先计算操作数，即使Y=0。 显然，此时我们不希望所有操作数被计值。 从而，我们有另一个规则：永不在应用操作之前计值操作数。 即，总是不计值地传递操作数，由作用操作决定什么时候计值操作数Lazy计值。 然而，对此规则，在很多情况下是不实际的。比如：如何仿真未计值操作数到操作的传递？这需要软件仿真。 这两种计值规则：积极和隋性（lazy），对应子程序参数传递的按值和按名。 对表达式而言，没有简单的统一规则是完全令人满意的，通常规则是混合的。,24,表达式的计值(2)：副作用,表达式中使用有副作用的操作，一直是语言设计中的争论点。 考虑：a×fun(x)+a 对乘法：需先取a的右值并计值fun(x) 对加法：需取a的右值，并计算乘法。 显然，我们希望只取a一次并应用到两个地方，而且fun(x)的计值在取a的前或后并无区别。 但如fun有副作用，改变了a的值，则计值序成为关键。 如a值本为1，但fun执行后值为3，并改a为2。则表达式可能值为： 1、顺序计值：1×3+2=5 2、取a一次：1×3+1=4 3、在取a前调用fun：2×3+2=8 执行序不同导致不同结果。,25,表达式的计值(2)：副作用,对表达式中副作用的使用有两种选择： 1、不允许副作用 不允许有副作用的函数或对副作用可能影响的表达式的值改为未定义。 2、允许副作用 但语言定义应精确地给出计值顺序，这将使很多优化不可能。 通常，语句允许有副作用，如：赋值必须产生副作用。,26,表达式的计值(3)：出错条件,对可能失败和产生出错条件的操作，涉及一种特殊的副作用。一般的副作用只涉及到程序员定义的函数，而出错条件可能在很多原操作中出现（溢出、被零除等）。 这类副作用是不希望被排除的，而出错条件的意义在于其出现甚至会受到表达式的计值顺序的影响。这样，程序员需要精确的计值顺序控制。,27,表达式的计值(4)：短路布尔表达式,考虑例子： if (A=0)|(B/AC) While(IC) 两个例子中，第二个条件可能产生出错条件。第一个操作数用于防止错误产生。 在很多语言中，求布尔操作需先计值操作数，这将产生不期望的错误，因为人们期望左操作数短路右操作数。 Ada中提供了两个特殊的布尔操作来解决这个问题。 and then 和 or else。显式地提供短路机制。 例：if (A=0) or else (B/AC) then 这将不会失败，因A=0将导致整个表达式计值结束。,返回,28,8.3 语句间的顺序控制,基本语句 语句级顺序控制的形式 语句级顺序控制的语句 结构化顺序控制 结构的程序设计简介 结构顺序控制语句 结构顺序控制中的问题 顺序控制的结构化：素程序,29,基本语句,任何程序的结果由其基本语句确定。这里我们不再考虑语句中表达式，而是将语句作为考虑的单元来代表一单步计算。 数据对象的赋值 通过向数据对象赋值而改变计算状态是影响计算状态的主要机制。,30,基本语句,数据对象的赋值 赋值语句 主要目的是将某表达式的右值赋给某数据对象的左值。 赋值为每个基本数据类型定义的中心操作。 输入语句 大多数语言有一种语句形式，从终端用户、文件或通讯线读数据。这样的语句也通过赋值改变变量的值。 其他赋值操作 参数传递：给形参赋值 隐含赋值：如SNOBOL4中的引用，Prolog目标匹配，声明时初始值等。,返回,31,语句级顺序控制的形式,三种主要的语句级顺序控制： 复合：语句顺序放置，顺序执行。 选择：两个语句序列可形成选择，使得一个或另一个序列被执行，但不能同时执行。 迭代：一个语句序列被重复执行零次或多次。 这是三种常见结构，语句被组成这三种结构而形成程序。,返回,32,显式顺序控制,goto语句，两种形式 无条件goto和条件goto Goto语句导致无结构的设计。语言的很多形式模型均不允许goto存在。 此外，goto也是多余的，没有goto也可以写出同样能力的程序。 Break语句 通常使控制被前移到一个显式点（在给定控制结构的结束处）。 如C中Break语句使得立即退出while、for、switch语句。 C中还有Continue语句，只结束本次循环。,33,结构化break语句,返回,34,结构的程序设计,70年代，goto语句受到很大攻击，以至有的语言完全删去了goto。goto 语句有一些优点： 如果标号只是局部语法标记，则对高效执行有直接的硬件支持。 在小程序中使用简单、容易。 为汇编语言和老语言用户熟悉。 可作为通用建筑块来表示（仿真）其他控制形式。,35,结构的程序设计,它也有严重的缺点： 1、缺乏层次的程序结构 程序的正确性和开发效率已远比效率更为重要，语言也应反映此需求。单进单出的控制结构概念，已成为更易理解的设计。层次化提供了一种抽象，符合“分而治之”的思想。而goto将打破这种层次性。 2、程序文本中语句顺序不一定对应执行的顺序。 要理解程序，必须理解语句的执行顺序。 静态顺序和动态顺序有关联将使程序更易于理解。 3、语句组可能有多个用途。 如果每个组只含单个用途。则程序更易理解。 人为地通过goto使某组有多用途将打乱执行顺序，使程序难于修改。,36,结构的程序设计,结构化程序设计强调： 、程序结构的层次设计，只用三种控制结构。 、层次设计的表示应直接体现在程序文本中（只使用结构化控制语句）。 、语句的文本序列对应执行序列： 、使用单一用途的语句组。,返回,37,结构顺序控制,大多数语言提供了控制语句集合来表示三种基本的控制形式，这些语句均应该是单入单出的。它们所构成的程序，其执行和语句序基本对应。 复合语句 一个语句序列，可按单个语句处理来构造更大的语句。 用beginend 和 等来构造 其实现是将其存放在一个连续存储区域中。 条件语句 用来表示两个或更多语句的选择执行，或单个语句的可选执行。 if 语句 单分枝：if 条件 then 语句 语句的可选执行 两分枝：if 条件 thenelse 还可表示多分枝。,38,结构顺序控制,条件语句 case语句，重复测试某变量的值。 case Tag is When 0 When 1 endcase 实现 if语句常用硬件支持的分枝和跳转指令实现。 case语句常用跳转表来避免同一变量值的重复测试。 跳转表是一个向量，顺序存放在内存中，其部件是无条件跳转指令。,39,case语句的跳转表实现,40,结构顺序控制,迭代语句 提供重复计算的机制。通常分为头和体两部分。体提供语句的动作。头控制重复执行体的次数。 简单重复 直接给出执行的次数。 例：COBOL中，perform body k times 当条件成立时重复 while test do body 计数器增量的重复 for I:=1 step 2 until 30 do body 无限重复 Loop exit when condition 没有显式的终止测试。 endloop 循环的实现 直接使用硬件提供的分支/跳转指令。,返回,41,结构顺序控制中的问题,多出口循环 有些情况下，可能在几种条件下都需要循环终止。 如：搜索循环是一个例子： 从K元素矢量中搜索第一个满足某条件的元素。 For I:=1 to k do if VECT(I)=0 the goto for I in 1k loop exit when VECT (I)=0; endloop,42,结构顺序控制中的问题,do-while-do 经常最自然的测试是否退出循环的地方是在中间部位，即已完成某些处理之后。称为do while do，因为中间点while是需要的 do while do read (x) while (not end-of-file) process (x) end 例外条件 例外可表示各种错误条件。 Raise BAD-CHAR-VALVE,loop read(x) if end-of-file then goto process (x) end loop,返回,43,素程序的理论可用于描述一致的控制结构理论。 1975年由Maddux提出，作为结构化程序设计的推广，以定义唯一的流程图分解。 假定程序图有三类结点： 每个流程图由这三类结构成。,素程序（Prime Program）,44,合式程序（ proper program ）,控制结构的形式模式是如下的流程图： 1、有单个进入线 2、有单个退出线 3、有从入口到每个结点和从每个结点到出口的路径。 我们的目标是区分“结构的”“合式程序”和“非结构的”合式程序。下图均为合式程序，差别在于结构性。,45,素程序,是合式程序，但不能被分为更小的合式程序，（功能结点的长序列被视为基本的）。否则成为复合程序。 所有素程序可以枚举出来。注意：它们中大多数或是无效的，或是常见的控制结构。 所用的控制结构均是具有少量结点的素程序。 通过枚举，我们看出，do-while-do是自然的控制结构。但很少有语言提供这种机制。,46,素程序的枚举,至多4节点的素程序，其中 a、b、e、i是功能结点序列。 f是if-then、 g是 do while、h 是 repeat-until、 j是 if-then-else、k是 do-while-do c、d、l和q只含决策结点和汇合结点，没有功能结点，故不会改变抽象机的状态空间，因此，等价于恒等函数。而其中c、l总退出，而d、q是循环（一旦循环，将不会终止）。,47,结构定理,Bohm & Jacobini任何素程序可被转换为只使用while和if的素程序。 该构造过程的概述： 1、给定任意流程图，标记每个结点，出口标记为O 2、定义I为新的程序变量 3、对流程图中每个结点，应用转换规则。 4、重建程序。 这里I类似虚拟机指令计数器，指出下一条执行语句。 整个程序简单地是一系列嵌套的if语句（在单个while循环中），这样，任何程序可用此法转换为“良构”程序。,48,结构定理,返回,49,8.4 非算术表达式的顺序控制,控制方式： 模式匹配 合一 回溯,50,这是SNOBOL4、Prolog、ML等语言中的重要操作。操作的成功是：匹配并赋一变量集到预定义的模板。如BNF文法中分析树的识别。 例：A0A0|1A0|01 合法有效串00100的识别过程为： A1匹配中间1 A2匹配 0 A1 0 A3匹配 0 A2 0 SNOBOL4是为直接仿真这个操作而设计的语言。其实现独立于任何实际的机器体系结构，面向串处理虚拟机而设计。为了执行SNOROL4，需将串处理机的操作实现为现有机器上的宏。 因此，SNOBOL4是第一个几乎可运行于所有机器的语言。在其每个实现中有精确相同的语义。 SNOBOL4使用串替代来实现匹配操作。,模式匹配,51,模式匹配,Prolog使用“关系作为n元组集合”的概念作为匹配机制。 通过刻划这些关系的已知实例，其他实例可被导出。 例：有事实 Parentof(John,Mary) Parentof(Susan,Mary) Parentof(Bill,John) Parentof(Ann,John) 要想知道Mary的父辈，我们写Parentof(X,Mary)，推导结果X可以是John或Susan。 如需知道Mary的两个父辈，式子为： Parentof(X,Mary), Parentof(Y,Mary), not(X=Y) 也可自己建立关系： Grandparentof(X,Y) :- Parentof(X,Z), Parentof(Z,Y),52,模式匹配：项重写,模式匹配的一种限制形式。 给定串a1a2an和重写规则 ,if =ai，则a1a2ai-1an是a1a2an的项重写。 例：对文法 A0B|1 B0A 产生001串的重写过程为： A0B00A001 ML将项重写表示为一种函数定义形式。 例：求阶乘fun fact (1)=1 | fact (N:int)=N*fact(N-1),返回,53,合一,Prolog数据库包含事实和规则。包含一个或多个变量的表达式称为查询，用来表示一个未知关系。 Prolog的主要特性是使用模式匹配来发现是否查询可解。 合一是进行模式匹配的方法，用于确定对查询的合法一致的替代。 例：对查询 Parentof(X, Mary)=Parentof(John, Y) 显然，解答为Parentof(John,Mary) 我们称，该实例使用替代John/X, Mary/Y,合一了Parentof(X, Mary)和Parentof(John, Y) 合一可视为对替代的公共性质的扩展。,54,合一：替代与一般合一,替代 这是在编程中学到的第一条原则，涉及参数传递和宏扩展。在宏扩展中，是用任意表达式替代一个变量。 一般合一： 要合一两个表达式U和V，需找到对U、V中出现的变量的替代，该替代使两个表达式相同。 例，f(X,John), f(g(John),Z) 绑定X到g(John), Z到John可完成合一。 结果为f(g(John),John), 我们将替代称为（sigma），写成U=V,55,替代和合一的不同,56,替代和合一的不同,对替代，有模式定义（表示子程序基调或宏定义），以及模式的实例（表示子程序调用或宏扩展）。 替代需用实际的实例值来替代模式定义中的参数。 例：F(A, B)=G(A, B)，实例为F(g(I),h(j) 用g(i)替A, h(j)替B，得到F(A，B)=G(g(i),h(j),57,替代和合一的不同,对合一，有两个模式定义，和一个模式的一个实例。 需要知道的是：是否有对参数的赋值使得模式的实例成为两个模式定义的一个替代。 为了应用模式的定义，我们必须在两个方向上替换。 例：模式F(A, B)=G(A, B)，M(C, D)=N(C, D) 实例为：F(John, M(h(v),7) 如果用John替代A，7替代D，同时，用M(h(v)替代B，h(v)替代C。 则我们的模式实例代表了一个有效的替代。 从我们的初始表达式F(John, M(h(v),7)，我们可有两个结果。 如先作用到F：F(John, M(h(v),7)=G(John, M(h(v),7) 如先作用到M：F(John, M(h(v),7)=F(John, N(h(v),7) 在第二次替代后，我们可得到同样结果， G(John, N(h(v),7) 因此，合一成功。,58,合一在Prolog中应用,假定有查询q，q=q1,q2，这里q1,q2是子查询。 我们首先试图合一q1和某规则P，P：-P1，P2，Pn 如果q1和P合一，则，我们可用P 替代q1 产生新的查询。 P ，q2 =p1 , p2 , , pn , q2 =p1, p2 , pn, q2 另一方面，如果查询q1和事实r合一，则可用true替代q1。 新查询变为true, q2 =q2 =q2 这是Prolog的执行过程，查询和规则或事实合一，直至产生true。 当然也可能产生false，意味着错误的规则或事实和q1合一,必须继续去寻找有效的解答。 变换的集合变成查询的答案。,59,合一在Prolog中应用,例：一个更完整的例子，下面子句集定义了加法。 1、succ(Y,X):-Y is X+1 2、add (Y,0,X):-Y=X 3、add (Z,X,Y):-W is X-1, add (U,W,Y), Succ (Z,U) 其中，add规则计算和，根据两个关于加法的事实。 0+x=x (Rule2) (x+1)+y=x+(y+1)=x+Succ(y) (Rule 3) 计算add（Y，2，3）,Y=5是变换，使查询和数据库中规则合一。,60,合一在Prolog中应用：实现,标准的Prolog树遍历算法,61,合一在Prolog中应用：实现,图 (a)表示了M个目标的集合。对加法例子，有两个可能的目标： add1有子目标Y=X add2的子目标为W is X-1, add(U,W,Z)和succ(Z,U) 对每个目标，Prolog试图去匹配每个子目标。 例如：对add2，首先，W和X-1合一，这样给W赋值为X-1。然后，试图匹配子目标add(U,W,Y)，递归地调用add规则。如果成功，U成为W和Y的和。 如果这个子目标匹配，则succ(Z,U)合一Z和U+1，或Z被设置为(X-1)+Y+1)=(X+Y)。 这个子目标匹配成功，则add2的规则成功。 如果任何子目标失败，则应用标准的回溯算法，对前面的子目标采用另一个匹配。如所有子目标失败，则规则本身失败。,62,返回,Prolog合一： add(Y,2,3)计算过程,63,回溯,如果某子目标不能和数据库中某规则匹配，则称规则失败。 可和另外的规则匹配，如所有规则均失败，则我们需回溯到前一个子目标（已匹配），并试用另外的规则。,