第八章顺序控制.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 c a 的树结构 10 表达式的语法 表达式可表示为树结构 但为了在程序中表示 线性化是需要的 前缀 波兰前缀 记法 这是波兰数学家发明的无括号记号法 如 f x y z ab calisp使用了该记号法的变种 称为剑桥波兰 用括号将操作符及其操作数括起来 如 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 表达式的树表示的计值 表达式翻成树结构虽有困难 但总体上是直接的 而树到可执行原语序列的翻译 则涉及计值顺序的一些微妙问题 在代码生成中出现的计值顺序问题有 问题一 统一的计值规则问题二 副作用 sideeffect 问题三 出错条件问题四 短路布尔表达式 21 表达式的计值 1 统一的计值规则 对表达式树中的每个操作结点 首先计值其操作数 或生成相应代码 然而应用操作到计算出的操作数上 或生成相应代码 积极计值规则 eager 对有些表达式来说 计值发生的顺序并不重要 可以选择以优化存储和其他机器特性 例 对 a b c a 下列顺序均可接受 顺序一 取a的右值顺序二 取c的右值取b的右值取b的右值a b d取a的右值取c右值c a ec a ea b dd e f表达式的右值d e f 22 表达式的计值 1 统一的计值规则 但是 并不是在任何情况下都可以使用这种统一的计值规则 例如 包含条件的表达式 z y 0 x x y 当y 0时 计算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 52 取a一次 1 3 1 43 在取a前调用fun 2 3 2 8执行序不同导致不同结果 25 表达式的计值 2 副作用 对表达式中副作用的使用有两种选择 1 不允许副作用不允许有副作用的函数或对副作用可能影响的表达式的值改为未定义 2 允许副作用但语言定义应精确地给出计值顺序 这将使很多优化不可能 通常 语句允许有副作用 如 赋值必须产生副作用 26 表达式的计值 3 出错条件 对可能失败和产生出错条件的操作 涉及一种特殊的副作用 一般的副作用只涉及到程序员定义的函数 而出错条件可能在很多原操作中出现 溢出 被零除等 这类副作用是不希望被排除的 而出错条件的意义在于其出现甚至会受到表达式的计值顺序的影响 这样 程序员需要精确的计值顺序控制 27 表达式的计值 4 短路布尔表达式 考虑例子 if a 0 b a c while ic 两个例子中 第二个条件可能产生出错条件 第一个操作数用于防止错误产生 在很多语言中 求布尔操作需先计值操作数 这将产生不期望的错误 因为人们期望左操作数短路右操作数 ada中提供了两个特殊的布尔操作来解决这个问题 andthen和orelse 显式地提供短路机制 例 if a 0 orelse b a c then这将不会失败 因a 0将导致整个表达式计值结束 返回 28 8 3语句间的顺序控制 基本语句语句级顺序控制的形式语句级顺序控制的语句结构化顺序控制结构的程序设计简介结构顺序控制语句结构顺序控制中的问题顺序控制的结构化 素程序 29 基本语句 任何程序的结果由其基本语句确定 这里我们不再考虑语句中表达式 而是将语句作为考虑的单元来代表一单步计算 数据对象的赋值通过向数据对象赋值而改变计算状态是影响计算状态的主要机制 30 基本语句 数据对象的赋值赋值语句主要目的是将某表达式的右值赋给某数据对象的左值 赋值为每个基本数据类型定义的中心操作 输入语句大多数语言有一种语句形式 从终端用户 文件或通讯线读数据 这样的语句也通过赋值改变变量的值 其他赋值操作参数传递 给形参赋值隐含赋值 如snobol4中的引用 prolog目标匹配 声明时初始值等 返回 31 语句级顺序控制的形式 三种主要的语句级顺序控制 复合 语句顺序放置 顺序执行 选择 两个语句序列可形成选择 使得一个或另一个序列被执行 但不能同时执行 迭代 一个语句序列被重复执行零次或多次 这是三种常见结构 语句被组成这三种结构而形成程序 返回 32 显式顺序控制 goto语句 两种形式无条件goto和条件gotogoto语句导致无结构的设计 语言的很多形式模型均不允许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 结构顺序控制 大多数语言提供了控制语句集合来表示三种基本的控制形式 这些语句均应该是单入单出的 它们所构成的程序 其执行和语句序基本对应 复合语句一个语句序列 可按单个语句处理来构造更大的语句 用begin end和 等来构造其实现是将其存放在一个连续存储区域中 条件语句用来表示两个或更多语句的选择执行 或单个语句的可选执行 if语句单分枝 if条件then语句语句的可选执行两分枝 if条件then else 还可表示多分枝 38 结构顺序控制 条件语句case语句 重复测试某变量的值 casetagiswhen0 when1 endcase实现if语句常用硬件支持的分枝和跳转指令实现 case语句常用跳转表来避免同一变量值的重复测试 跳转表是一个向量 顺序存放在内存中 其部件是无条件跳转指令 39 case语句的跳转表实现 40 结构顺序控制 迭代语句提供重复计算的机制 通常分为头和体两部分 体提供语句的动作 头控制重复执行体的次数 简单重复直接给出执行的次数 例 cobol中 performbodyktimes当条件成立时重复whiletestdobody计数器增量的重复fori 1step2until30dobody无限重复loopexitwhencondition没有显式的终止测试 endloop循环的实现直接使用硬件提供的分支 跳转指令 返回 41 结构顺序控制中的问题 多出口循环有些情况下 可能在几种条件下都需要循环终止 如 搜索循环是一个例子 从k元素矢量中搜索第一个满足某条件的元素 fori 1tokdoifvect i 0thegoto foriin1 kloopexitwhenvect i 0 endloop 42 结构顺序控制中的问题 do while do经常最自然的测试是否退出循环的地方是在中间部位 即已完成某些处理之后 称为dowhiledo 因为中间点while是需要的dowhiledoread x while notend of file process x end例外条件例外可表示各种错误条件 raisebad char valve loopread x ifend of filethengoto process x endloop 返回 43 素程序的理论可用于描述一致的控制结构理论 1975年由maddux提出 作为结构化程序设计的推广 以定义唯一的流程图分解 假定程序图有三类结点 每个流程图由这三类结构成 素程序 primeprogram 44 合式程序 properprogram 控制结构的形式模式是如下的流程图 1 有单个进入线2 有单个退出线3 有从入口到每个结点和从每个结点到出口的路径 我们的目标是区分 结构的 合式程序 和 非结构的 合式程序 下图均为合式程序 差别在于结构性 45 素程序 是合式程序 但不能被分为更小的合式程序 功能结点的长序列被视为基本的 否则成为复合程序 所有素程序可以枚举出来 注意 它们中大多数或是无效的 或是常见的控制结构 所用的控制结构均是具有少量结点的素程序 通过枚举 我们看出 do while do是自然的控制结构 但很少有语言提供这种机制 46 素程序的枚举 至多4节点的素程序 其中a b e i是功能结点序列 f是if then g是dowhile h是repeat until j是if then else k是do while doc d l和q只含决策结点和汇合结点 没有功能结点 故不会改变抽象机的状态空间 因此 等价于恒等函数 而其中c l总退出 而d q是循环 一旦循环 将不会终止 47 结构定理 bohm jacobini 任何素程序可被转换为只使用while和if的素程序 该构造过程的概述 1 给定任意流程图 标记每个结点 出口标记为o2 定义i为新的程序变量3 对流程图中每个结点 应用转换规则 4 重建程序 这里i类似虚拟机指令计数器 指出下一条执行语句 整个程序简单地是一系列嵌套的if语句 在单个while循环中 这样 任何程序可用此法转换为 良构 程序 48 结构定理 返回 49 8 4非算术表达式的顺序控制 控制方式 模式匹配合一回溯 50 这是snobol4 prolog ml等语言中的重要操作 操作的成功是 匹配并赋一变量集到预定义的模板 如bnf文法中分析树的识别 例 a 0a0 1a0 01合法有效串00100的识别过程为 a1匹配中间1a2匹配0a10a3匹配0a20snobol4是为直接仿真这个操作而设计的语言 其实现独立于任何实际的机器体系结构 面向串处理虚拟机而设计 为了执行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 模式匹配 项重写 模式匹配的一种限制形式 给定串a1a2 an和重写规则 if ai 则a1a2 ai 1 an是a1a2 an的项重写 例 对文法a 0b 1b 0a产生001串的重写过程为 a 0b 00a 001ml将项重写表示为一种函数定义形式 例 求阶乘funfact 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 因此