第八章顺序控制

1、第八章第八章 顺序控制顺序控制2n顺序控制提供了操作和数据被组合成程顺序控制提供了操作和数据被组合成程序和程序集合的框架。序和程序集合的框架。n涉及两个方面的问题：涉及两个方面的问题：n操作执行顺序的控制（顺序控制）操作执行顺序的控制（顺序控制）n数据在子程序间的传递（数据控制）数据在子程序间的传递（数据控制）3执行顺序控制执行顺序控制n控制的层次和形式控制的层次和形式n语句内（即表达式）的顺序控制语句内（即表达式）的顺序控制n算术表达的顺序控制算术表达的顺序控制n非算术表达式的顺序控制非算术表达式的顺序控制n语句间的顺序控制语句间的顺序控制48.1 隐式和显式顺序控制隐式和显式顺序控制n顺序

2、控制结构可分为四组：顺序控制结构可分为四组：1、用于表达式中的结构（也针对语句，表达式是语句的基本建、用于表达式中的结构（也针对语句，表达式是语句的基本建筑块）。如：优先级规则和括号。筑块）。如：优先级规则和括号。2、用于语句或语句组间的结构。如：条件和迭代。、用于语句或语句组间的结构。如：条件和迭代。3、用于申明式程序设计语言的程序结构。如逻辑程序设计语言、用于申明式程序设计语言的程序结构。如逻辑程序设计语言4、用于子程序间的结构，如：子程序调用和协同例程。、用于子程序间的结构，如：子程序调用和协同例程。n这种分法并不是精确的，如这种分法并不是精确的，如lisp和和apl中只有表达式中只有表

3、达式而无语句。而无语句。n顺序控制结构可以是隐含的（缺省的）（由语言定义，顺序控制结构可以是隐含的（缺省的）（由语言定义，除非程序员显式修改）或显式的（程序员可用来修改除非程序员显式修改）或显式的（程序员可用来修改隐含顺序）。隐含顺序）。 5acabbroot2428.2 算术表达的顺序控制算术表达的顺序控制n考虑方程求根：考虑方程求根：n该公式至少涉及该公式至少涉及15个分开的操作，用汇编或机器语个分开的操作，用汇编或机器语言至少需要言至少需要15条指令甚至更多。而写成条指令甚至更多。而写成fortran程程序则为：序则为：nroot=(-b+sqrt(b*2-4*a*c)/(2*a)n这是

4、自然的表达方法，由翻译器而不是程序员来考这是自然的表达方法，由翻译器而不是程序员来考虑各种优化问题。虑各种优化问题。n然而，翻译器如何控制正确的操作顺序？然而，翻译器如何控制正确的操作顺序？ 6算术表达的顺序控制算术表达的顺序控制n算术表达式的表示算术表达式的表示n语法：语法：直观表示直观表示和和形式化表示形式化表示n语义语义：决定计值方式和过程：决定计值方式和过程n运算符的优先级运算符的优先级n算术表达式算术表达式在执行时的表示在执行时的表示7树结构表示树结构表示n目前，我们将表达式考虑为单个实体，目前，我们将表达式考虑为单个实体，忽略了其计值必需的实际语法和语义。忽略了其计值必需的实际语法

5、和语义。n表达式中的基本顺序控制机制是表达式中的基本顺序控制机制是“函数函数复合复合”：刻划操作及其操作数。：刻划操作及其操作数。n函数复合使表达式呈树结构特征，根为函数复合使表达式呈树结构特征，根为主操作，中间节点为中间层次操作，叶主操作，中间节点为中间层次操作，叶为操作数。为操作数。8树结构表示树结构表示n求方程根的表达式的树。求方程根的表达式的树。n树表示阐明了表达式的控制结构，树表示阐明了表达式的控制结构，低层的数据引用和操作作为高层低层的数据引用和操作作为高层操作的操作数，必须先计值，但操作的操作数，必须先计值，但树表示也留下一些计值顺序没有树表示也留下一些计值顺序没有指定。指定。n

6、如：如：b和和b*2谁先计值？谁先计值？b是否是否可组合为同一引用？可组合为同一引用？n通常语言定义只在树表示级定义通常语言定义只在树表示级定义表达式计值顺序，允许实现者决表达式计值顺序，允许实现者决定计值细节。定计值细节。返回9表达式的语法表达式的语法n表达式表达式(a+b)(ca)的树结构的树结构10表达式的语法表达式的语法n表达式可表示为树结构，但为了在程序中表示，表达式可表示为树结构，但为了在程序中表示，线性化是需要的。线性化是需要的。n前缀（波兰前缀）记法。前缀（波兰前缀）记法。n这是波兰数学家发明的无括号记号法。如：这是波兰数学家发明的无括号记号法。如：f(x,y,z)，+ab-c

7、anlisp使用了该记号法的变种，称为剑桥波兰，用括号将使用了该记号法的变种，称为剑桥波兰，用括号将操作符及其操作数括起来，如：操作符及其操作数括起来，如：(x(+ab)(-ca)。n后缀（逆波兰）记号法后缀（逆波兰）记号法n类似于前缀，但操作符数在后面，如：类似于前缀，但操作符数在后面，如：ab+ca-n中缀记号法中缀记号法n最适合二元操作，也是我们最常用的方式。最适合二元操作，也是我们最常用的方式。返回11表达式的语义表达式的语义 （1/3）n上三种记号法对语言的设计都有一些有用的属上三种记号法对语言的设计都有一些有用的属性，在如何计算表达式值方面也有不同。性，在如何计算表达式值方面也有不

8、同。n前缀计值前缀计值n可以通过一遍扫描计值每个表达式，然而需要知道可以通过一遍扫描计值每个表达式，然而需要知道每个操作的操作数量。除了可省去括号外，前缀表每个操作的操作数量。除了可省去括号外，前缀表达式在语言设计中有如下价值：达式在语言设计中有如下价值：1、一般的函数调用均采用前缀方式。、一般的函数调用均采用前缀方式。2、可表示有任意数量操作数的操作，写表达式只需一个语、可表示有任意数量操作数的操作，写表达式只需一个语法规则。法规则。3、解码可以机械地很容易地进行，将其翻译成简单代码序、解码可以机械地很容易地进行，将其翻译成简单代码序是容易的。是容易的。12表达式的语义表达式的语义 （1/3

9、）n前缀计值前缀计值n下面算法用一个执行栈计值表达式：对表达下面算法用一个执行栈计值表达式：对表达式式p，1、如、如p中下一项是操作子，压入栈项，设置所需中下一项是操作子，压入栈项，设置所需参数数目。参数数目。2、如、如p中下一项是操作数，压入栈项。中下一项是操作数，压入栈项。3、如栈项、如栈项n项是操作数（对栈中第一个项是操作数（对栈中第一个n元操元操作），则可以进行计值，用计值结果替代该操作作），则可以进行计值，用计值结果替代该操作符和操作数。符和操作数。13表达式的语义表达式的语义 （2/3）n后缀计值后缀计值n后缀计值时，操作符紧跟其操作数后而且操后缀计值时，操作符紧跟其操作数后而且操

10、作数已被计值。作数已被计值。n1、如、如p中下一项是操作数，压入栈顶中下一项是操作数，压入栈顶n2、如、如p中下一项是中下一项是n元操作符，元操作符，n个参数必须是个参数必须是栈顶部的栈顶部的n个元素，计算结果并替换这个元素，计算结果并替换这n个元素。个元素。n这种计值策略直接、简单，是很多翻译器中生成这种计值策略直接、简单，是很多翻译器中生成表达式代码的基础。表达式代码的基础。14表达式的语义表达式的语义 （3/3）n中缀计值中缀计值n中缀是常见的，但用于程序语言中会导致一中缀是常见的，但用于程序语言中会导致一些问题：些问题：n1、只适合于二元操作。语言单用中缀是不够的，、只适合于二元操作。

11、语言单用中缀是不够的，还需使用前缀，这二者的混合使翻译更为复杂。还需使用前缀，这二者的混合使翻译更为复杂。n2、表达式中涉及多个中缀操作时，如不使用括、表达式中涉及多个中缀操作时，如不使用括号，则存在固有二义性。为解决这个问题，通常号，则存在固有二义性。为解决这个问题，通常引入隐含的规则。引入隐含的规则。返回15操作子计值顺序操作子计值顺序16操作的层次操作的层次n即操作的优先规则即操作的优先规则返回返回n同一层次操作的计算顺序的隐含规则同一层次操作的计算顺序的隐含规则n优先级对算术表达式是适用的，因为表优先级对算术表达式是适用的，因为表达式语义的数学模型已对大多数程序员达式语义的数学模型已对

12、大多数程序员熟知的。熟知的。结合律结合律17结合律结合律n然而，当语言引入新的，不是源自传统数学的操作符然而，当语言引入新的，不是源自传统数学的操作符时，优先规则可能不再有用，因此，需要有不同方法时，优先规则可能不再有用，因此，需要有不同方法来处理扩展的操作集。来处理扩展的操作集。nc语言：使用扩展的优先规则集合，大多数使用从左到右的结语言：使用扩展的优先规则集合，大多数使用从左到右的结合律。大多数合律。大多数c规则是合理的。规则是合理的。napl：操作数为数组和矢量，语言没有优先规则。所有表达：操作数为数组和矢量，语言没有优先规则。所有表达式计值从右到左。这规则对大多数表达式也是合理的，除了

13、式计值从右到左。这规则对大多数表达式也是合理的，除了一些典型的表达式，如一些典型的表达式，如a-b-c-意为意为a-(b-c)。nsmalltalk：模型类似：模型类似apl，没有优先规则，表达式计值从左，没有优先规则，表达式计值从左到右。到右。nforth：用于实时过程控制。其运行时结构为栈，语言是纯后：用于实时过程控制。其运行时结构为栈，语言是纯后缀的，没有优先规则。缀的，没有优先规则。返回返回18执行时表示执行时表示n对中缀形式的表达式的解码是困难的，需要翻对中缀形式的表达式的解码是困难的，需要翻译为易于解码的可执行形式。通常的选择有：译为易于解码的可执行形式。通常的选择有：1、机器代码

14、序列、机器代码序列n表达式被直接翻译成实际的机器代码，而不是先翻译为中表达式被直接翻译成实际的机器代码，而不是先翻译为中间形式。指令顺序反映了初始表达式的顺序控制结构。间形式。指令顺序反映了初始表达式的顺序控制结构。n机器代码序列必须使用显式的临时存储位置来保持中间结机器代码序列必须使用显式的临时存储位置来保持中间结果，允许使用硬件解释器，因此，执行速度快。果，允许使用硬件解释器，因此，执行速度快。2、树结构、树结构n表达式可以表达式可以以其自然的树结构直接执行以其自然的树结构直接执行（使用软件解释（使用软件解释器）。执行通过简单的树遍历来完成。器）。执行通过简单的树遍历来完成。n这是这是li

15、sp中使用的典型技术，整个程序被表示为树结构。中使用的典型技术，整个程序被表示为树结构。19执行时表示执行时表示3、前缀或后缀形式、前缀或后缀形式n这两种形式可用前面给出的解释算法来执行。这两种形式可用前面给出的解释算法来执行。n在某些基于堆栈组织的实际计算机中，实际的机在某些基于堆栈组织的实际计算机中，实际的机器代码表示为后缀形式。器代码表示为后缀形式。n前缀表示是前缀表示是snobol4程序的执行形式，执行从程序的执行形式，执行从左到右进行。左到右进行。n每个操作递归地调用解释器来计值其操作数。每个操作递归地调用解释器来计值其操作数。20表达式的树表示的计值表达式的树表示的计值n表达式翻成

16、树结构虽有困难，但总体上是直接表达式翻成树结构虽有困难，但总体上是直接的。的。n而树到可执行原语序列的翻译，则涉及计值顺而树到可执行原语序列的翻译，则涉及计值顺序的一些微妙问题。在代码生成中出现的计值序的一些微妙问题。在代码生成中出现的计值顺序问题有：顺序问题有：n问题一：统一的计值规则问题一：统一的计值规则n问题二：副作用，问题二：副作用，side effect。n问题三：出错条件问题三：出错条件n问题四：短路布尔表达式问题四：短路布尔表达式21表达式的计值表达式的计值(1)：统一的计值规则：统一的计值规则n对表达式树中的每个操作结点，首先计值其操作数对表达式树中的每个操作结点，首先计值其操

17、作数（或生成相应代码），然而应用操作到计算出的操作（或生成相应代码），然而应用操作到计算出的操作数上（或生成相应代码）数上（或生成相应代码）积极计值规则（积极计值规则（eager）。）。n对有些表达式来说，计值发生的顺序并不重要，可以对有些表达式来说，计值发生的顺序并不重要，可以选择以优化存储和其他机器特性。选择以优化存储和其他机器特性。n例，对例，对(a+b)(c-a)，下列顺序均可接受。，下列顺序均可接受。顺序一：取顺序一：取a的右值的右值顺序二：取顺序二：取c的右值的右值 取取b的右值的右值 取取b的右值的右值 a+bd 取取a的右值的右值 取取c右值右值 c-ae c-ae a+bd

18、def表达式的右值表达式的右值 def22zy0xxyif/表达式的计值表达式的计值(1)：统一的计值规则：统一的计值规则n但是，并不是在任何情况下都可以使用这种统但是，并不是在任何情况下都可以使用这种统一的计值规则。一的计值规则。n例如，包含条件的表达式：例如，包含条件的表达式：nz+(y=0？x：x/y)，当，当y0时，计算时，计算x/y23表达式的计值表达式的计值(1)：统一的计值规则：统一的计值规则n采用统一规则，对采用统一规则，对if操作，需先计算操作数，即使操作，需先计算操作数，即使y=0。n显然，此时我们不希望所有操作数被计值。显然，此时我们不希望所有操作数被计值。n从而，我们有

19、另一个规则：永不在应用操作之前计值从而，我们有另一个规则：永不在应用操作之前计值操作数。操作数。n即，总是不计值地传递操作数，由作用操作决定什么时候计即，总是不计值地传递操作数，由作用操作决定什么时候计值操作数值操作数lazy计值。计值。n然而，对此规则，在很多情况下是不实际的。比如：如何仿然而，对此规则，在很多情况下是不实际的。比如：如何仿真未计值操作数到操作的传递？这需要软件仿真。真未计值操作数到操作的传递？这需要软件仿真。n这两种计值规则：积极和隋性（这两种计值规则：积极和隋性（lazy），对应子程序），对应子程序参数传递的按值和按名。参数传递的按值和按名。n对表达式而言，没有简单的统一

20、规则是完全令人满意的，通对表达式而言，没有简单的统一规则是完全令人满意的，通常规则是混合的。常规则是混合的。24表达式的计值表达式的计值(2)：副作用：副作用n表达式中使用有副作用的操作，一直是语言设计中的表达式中使用有副作用的操作，一直是语言设计中的争论点。争论点。n考虑：考虑：afun(x)+an对乘法：需先取对乘法：需先取a的右值并计值的右值并计值fun(x)n对加法：需取对加法：需取a的右值，并计算乘法。的右值，并计算乘法。n显然，我们希望只取显然，我们希望只取a一次并应用到两个地方，而且一次并应用到两个地方，而且fun(x)的的计值在取计值在取a的前或后并无区别。的前或后并无区别。n

21、但如但如fun有副作用，改变了有副作用，改变了a的值，则计值序成为关键。的值，则计值序成为关键。n如如a值本为值本为1，但，但fun执行后值为执行后值为3，并改，并改a为为2。则表达式可能值。则表达式可能值为：为：1、顺序计值：、顺序计值：13+2=52、取、取a一次：一次：13+1=43、在取、在取a前调用前调用fun：23+2=8n执行序不同导致不同结果。执行序不同导致不同结果。25表达式的计值表达式的计值(2)：副作用：副作用n对表达式中副作用的使用有两种选择：对表达式中副作用的使用有两种选择：1、不允许副作用、不允许副作用n不允许有副作用的函数或对副作用可能影响的表不允许有副作用的函数

22、或对副作用可能影响的表达式的值改为未定义。达式的值改为未定义。2、允许副作用、允许副作用n但语言定义应精确地给出计值顺序，这将使很多但语言定义应精确地给出计值顺序，这将使很多优化不可能。优化不可能。n通常，语句允许有副作用，如：赋值必通常，语句允许有副作用，如：赋值必须产生副作用。须产生副作用。26表达式的计值表达式的计值(3)：出错条件：出错条件n对可能失败和产生出错条件的操作，涉及一种对可能失败和产生出错条件的操作，涉及一种特殊的副作用。一般的副作用只涉及到程序员特殊的副作用。一般的副作用只涉及到程序员定义的函数，而出错条件可能在很多原操作中定义的函数，而出错条件可能在很多原操作中出现（溢

23、出、被零除等）。出现（溢出、被零除等）。n这类副作用是不希望被排除的，而出错条件的这类副作用是不希望被排除的，而出错条件的意义在于其出现甚至会受到表达式的计值顺序意义在于其出现甚至会受到表达式的计值顺序的影响。这样，程序员需要精确的计值顺序控的影响。这样，程序员需要精确的计值顺序控制。制。27表达式的计值表达式的计值(4)：短路布尔表达式：短路布尔表达式n考虑例子：考虑例子：nif (a=0)|(b/ac)nwhile(ic)n两个例子中，第二个条件可能产生出错条件。第一两个例子中，第二个条件可能产生出错条件。第一个操作数用于防止错误产生。个操作数用于防止错误产生。n在很多语言中，求布尔操作需

24、先计值操作数，在很多语言中，求布尔操作需先计值操作数，这将产生不期望的错误，因为人们期望左操作这将产生不期望的错误，因为人们期望左操作数短路右操作数。数短路右操作数。nada中提供了两个特殊的布尔操作来解决这个问题。中提供了两个特殊的布尔操作来解决这个问题。nand then 和和 or else。显式地提供短路机制。显式地提供短路机制。n例：例：if (a=0) or else (b/ac) thenn这将不会失败，因这将不会失败，因a=0将导致整个表达式计值结束。将导致整个表达式计值结束。返回288.3 语句间的顺序控制语句间的顺序控制n基本语句基本语句n语句级顺序控制的语句级顺序控制的形

25、式形式n语句级顺序控制的语句级顺序控制的语句语句n结构化顺序控制结构化顺序控制n结构的程序设计简介结构的程序设计简介n结构顺序控制语句结构顺序控制语句n结构顺序控制中的问题结构顺序控制中的问题n顺序控制的结构化：顺序控制的结构化：素程序素程序29基本语句基本语句n任何程序的结果由其基本语句确定。这任何程序的结果由其基本语句确定。这里我们不再考虑语句中表达式，而是将里我们不再考虑语句中表达式，而是将语句作为考虑的单元来代表一单步计算。语句作为考虑的单元来代表一单步计算。n数据对象的赋值数据对象的赋值n通过向数据对象赋值而改变计算状态是影响通过向数据对象赋值而改变计算状态是影响计算状态的主要机制。

26、计算状态的主要机制。30基本语句基本语句n数据对象的赋值数据对象的赋值n赋值语句赋值语句n主要目的是将某表达式的右值赋给某数据对象的左值。主要目的是将某表达式的右值赋给某数据对象的左值。n赋值为每个基本数据类型定义的中心操作。赋值为每个基本数据类型定义的中心操作。n输入语句输入语句n大多数语言有一种语句形式，从终端用户、文件或通大多数语言有一种语句形式，从终端用户、文件或通讯线读数据。这样的语句也通过赋值改变变量的值。讯线读数据。这样的语句也通过赋值改变变量的值。n其他赋值操作其他赋值操作n参数传递：给形参赋值参数传递：给形参赋值n隐含赋值：如隐含赋值：如snobol4中的引用，中的引用，pr

27、olog目标匹配，目标匹配，声明时初始值等。声明时初始值等。返回31语句级顺序控制的形式语句级顺序控制的形式n三种主要的语句级顺序控制：三种主要的语句级顺序控制：n复合：语句顺序放置，顺序执行。复合：语句顺序放置，顺序执行。n选择：两个语句序列可形成选择，使得一个选择：两个语句序列可形成选择，使得一个或另一个序列被执行，但不能同时执行。或另一个序列被执行，但不能同时执行。n迭代：一个语句序列被重复执行零次或多次。迭代：一个语句序列被重复执行零次或多次。n这是三种常见结构，语句被组成这三种这是三种常见结构，语句被组成这三种结构而形成程序。结构而形成程序。返回32显式顺序控制显式顺序控制ngoto

28、语句，两种形式语句，两种形式n无条件无条件goto和条件和条件gotongoto语句导致无结构的设计。语言的很多形式模语句导致无结构的设计。语言的很多形式模型均不允许型均不允许goto存在。存在。n此外，此外，goto也是多余的，没有也是多余的，没有goto也可以写出同也可以写出同样能力的程序。样能力的程序。nbreak语句语句n通常使控制被前移到一个显式点（在给定控制结构通常使控制被前移到一个显式点（在给定控制结构的结束处）。的结束处）。n如如c中中break语句使得立即退出语句使得立即退出while、for、switch语句。语句。nc中还有中还有continue语句，只结束本次循环。语句

29、，只结束本次循环。33结构化结构化break语句语句返回34结构的程序设计结构的程序设计n70年代，年代，goto语句受到很大攻击，以至语句受到很大攻击，以至有的语言完全删去了有的语言完全删去了goto。goto 语句语句有一些优点：有一些优点：如果标号只是局部语法标记，则对高效执如果标号只是局部语法标记，则对高效执行有直接的硬件支持。行有直接的硬件支持。在小程序中使用简单、容易。在小程序中使用简单、容易。为汇编语言和老语言用户熟悉。为汇编语言和老语言用户熟悉。可作为通用建筑块来表示（仿真）其他控可作为通用建筑块来表示（仿真）其他控制形式。制形式。35结构的程序设计结构的程序设计n它也有严重的

30、缺点：它也有严重的缺点：1、缺乏层次的程序结构、缺乏层次的程序结构n程序的正确性和开发效率已远比效率更为重要，语言也应程序的正确性和开发效率已远比效率更为重要，语言也应反映此需求。单进单出的控制结构概念，已成为更易理解反映此需求。单进单出的控制结构概念，已成为更易理解的设计。层次化提供了一种抽象，符合的设计。层次化提供了一种抽象，符合“分而治之分而治之”的思的思想。而想。而goto将打破这种层次性。将打破这种层次性。2、程序文本中语句顺序不一定对应执行的顺序。、程序文本中语句顺序不一定对应执行的顺序。n要理解程序，必须理解语句的执行顺序。要理解程序，必须理解语句的执行顺序。n静态顺序和动态顺序

31、有关联将使程序更易于理解。静态顺序和动态顺序有关联将使程序更易于理解。3、语句组可能有多个用途。、语句组可能有多个用途。n如果每个组只含单个用途。则程序更易理解。如果每个组只含单个用途。则程序更易理解。n人为地通过人为地通过goto使某组有多用途将打乱执行顺序，使程使某组有多用途将打乱执行顺序，使程序难于修改。序难于修改。36结构的程序设计结构的程序设计n结构化程序设计强调：结构化程序设计强调：、程序结构的层次设计，只用三种控制结、程序结构的层次设计，只用三种控制结构。构。、层次设计的表示应直接体现在程序文本、层次设计的表示应直接体现在程序文本中（只使用结构化控制语句）。中（只使用结构化控制语

32、句）。、语句的文本序列对应执行序列：、语句的文本序列对应执行序列：、使用单一用途的语句组。、使用单一用途的语句组。返回37结构顺序控制结构顺序控制n大多数语言提供了控制语句集合来表示三种基本的控大多数语言提供了控制语句集合来表示三种基本的控制形式，这些语句均应该是单入单出的。它们所构成制形式，这些语句均应该是单入单出的。它们所构成的程序，其执行和语句序基本对应。的程序，其执行和语句序基本对应。n复合语句复合语句n一个语句序列，可按单个语句处理来构造更大的语句。一个语句序列，可按单个语句处理来构造更大的语句。n用用beginend 和和 等来构造等来构造n其实现是将其存放在一个连续存储区域中。其

33、实现是将其存放在一个连续存储区域中。n条件语句条件语句n用来表示两个或更多语句的选择执行，或单个语句的可选执用来表示两个或更多语句的选择执行，或单个语句的可选执行。行。nif 语句语句n单分枝：单分枝：if 条件条件 then 语句语句语句的可选执行语句的可选执行n两分枝：两分枝：if 条件条件 thenelsen还可表示多分枝。还可表示多分枝。 38结构顺序控制结构顺序控制n条件语句条件语句ncase语句，重复测试某变量的值。语句，重复测试某变量的值。case tag is when 0 when 1 endcasen实现实现nif语句常用硬件支持的分枝和跳转指令实现。语句常用硬件支持的分枝

34、和跳转指令实现。ncase语句常用跳转表来避免同一变量值的重复测试。语句常用跳转表来避免同一变量值的重复测试。n跳转表是一个向量，顺序存放在内存中，其部件是无条件跳跳转表是一个向量，顺序存放在内存中，其部件是无条件跳转指令。转指令。39case语语句句的的跳跳转转表表实实现现40结构顺序控制结构顺序控制n迭代语句迭代语句n提供重复计算的机制。通常分为头和体两部分。体提供语句提供重复计算的机制。通常分为头和体两部分。体提供语句的动作。头控制重复执行体的次数。的动作。头控制重复执行体的次数。n简单重复简单重复n直接给出执行的次数。直接给出执行的次数。n例：例：cobol中，中，perform bo

35、dy k timesn当条件成立时重复当条件成立时重复nwhile test do bodyn计数器增量的重复计数器增量的重复nfor i:=1 step 2 until 30 do bodyn无限重复无限重复nloopexit when condition没有显式的终止测试。没有显式的终止测试。endloopn循环的实现循环的实现n直接使用硬件提供的分支直接使用硬件提供的分支/跳转指令。跳转指令。返回41结构顺序控制中的问题结构顺序控制中的问题n多出口循环多出口循环n有些情况下，可能在几种条件下都需要循环终止。有些情况下，可能在几种条件下都需要循环终止。n如：搜索循环是一个例子：如：搜索循环

36、是一个例子：从从k元素矢量中搜索第一个满足某条件的元素。元素矢量中搜索第一个满足某条件的元素。for i:=1 to k do if vect(i)=0 the goto for i in 1k loop exit when vect (i)=0;endloop42结构顺序控制中的问题结构顺序控制中的问题ndo-while-don经常最自然的测试是否退出循环的地方是在中间部经常最自然的测试是否退出循环的地方是在中间部位，即已完成某些处理之后。称为位，即已完成某些处理之后。称为do while do，因为中间点因为中间点while是需要的是需要的do while doread (x)while

37、(not end-of-file)process (x)endn例外条件例外条件n例外可表示各种错误条件。例外可表示各种错误条件。nraise bad-char-valveloopread(x)if end-of-file then goto process (x)end loop返回43n素程序的理论可用于描述一致的控制结构理论。素程序的理论可用于描述一致的控制结构理论。n1975年由年由maddux提出，作为结构化程序设计的推广，提出，作为结构化程序设计的推广，以定义唯一的流程图分解。以定义唯一的流程图分解。n假定程序图有三类结点：假定程序图有三类结点：nn每个流程图由这三类结构成。每个流

38、程图由这三类结构成。功能结点决策结点汇合结点素程序（素程序（prime program）44合式程序（合式程序（ proper program ）n控制结构的形式模式是如下的流程图：控制结构的形式模式是如下的流程图：n1、有单个进入线、有单个进入线n2、有单个退出线、有单个退出线n3、有从入口到每个结点和从每个结点到出口的路径。、有从入口到每个结点和从每个结点到出口的路径。n我们的目标是区分我们的目标是区分“结构的结构的”“”“合式程序合式程序”和和“非结非结构的构的”合式程序。下图均为合式程序，差别在于结构合式程序。下图均为合式程序，差别在于结构性。性。45素程序素程序n是合式程序，但不能被

39、分为更小的合式程序，是合式程序，但不能被分为更小的合式程序，（功能结点的长序列被视为基本的）。否则成（功能结点的长序列被视为基本的）。否则成为复合程序。为复合程序。n所有素程序可以枚举出来。注意：它们中大多所有素程序可以枚举出来。注意：它们中大多数或是无效的，或是常见的控制结构。数或是无效的，或是常见的控制结构。n所用的控制结构均是具有少量结点的素程序。所用的控制结构均是具有少量结点的素程序。n通过枚举，我们看出，通过枚举，我们看出，do-while-do是自然的是自然的控制结构。但很少有语言提供这种机制。控制结构。但很少有语言提供这种机制。46素程序的枚举素程序的枚举n至多至多4节点的素程序

40、，其中节点的素程序，其中na、b、e、i是功能结点序列。是功能结点序列。nf是是if-then、 g是是 do while、h 是是 repeat-until、nj是是 if-then-else、k是是 do-while-donc、d、l和和q只含决策结点和只含决策结点和汇合结点，没有功能结点，汇合结点，没有功能结点，故不会改变抽象机的状态空故不会改变抽象机的状态空间，因此，等价于恒等函数。间，因此，等价于恒等函数。而其中而其中c、l总退出，而总退出，而d、q是循环（一旦循环，将不会是循环（一旦循环，将不会终止）。终止）。47结构定理结构定理nbohm & jacobini任何素程序可被转换为

41、任何素程序可被转换为只使用只使用while和和if的素程序。的素程序。n该构造过程的概述：该构造过程的概述：1、给定任意流程图，标记每个结点，出口标记为、给定任意流程图，标记每个结点，出口标记为o2、定义、定义i为新的程序变量为新的程序变量3、对流程图中每个结点，应用转换规则。、对流程图中每个结点，应用转换规则。4、重建程序。、重建程序。n这里这里i类似虚拟机指令计数器，指出下一条执行语类似虚拟机指令计数器，指出下一条执行语句。句。n整个程序简单地是一系列嵌套的整个程序简单地是一系列嵌套的if语句（在单个语句（在单个while循环中），这样，任何程序可用此法转换为循环中），这样，任何程序可用此

42、法转换为“良构良构”程序。程序。48结结构构定定理理返回498.4 非算术表达式的顺序控制非算术表达式的顺序控制n控制方式：控制方式：n模式匹配模式匹配n合一合一n回溯回溯50n这是这是snobol4、prolog、ml等语言中的重要操作。操作的等语言中的重要操作。操作的成功是：匹配并赋一变量集到预定义的模板。如成功是：匹配并赋一变量集到预定义的模板。如bnf文法中文法中分析树的识别。分析树的识别。n例：例：a0a0|1a0|01n合法有效串合法有效串00100的识别过程为：的识别过程为：na1匹配中间匹配中间1na2匹配匹配 0 a1 0na3匹配匹配 0 a2 0nsnobol4是为直接仿

43、真这个操作而设计的语言。其实现独立是为直接仿真这个操作而设计的语言。其实现独立于任何实际的机器体系结构，面向串处理虚拟机而设计。为于任何实际的机器体系结构，面向串处理虚拟机而设计。为了执行了执行snorol4，需将串处理机的操作实现为现有机器上，需将串处理机的操作实现为现有机器上的宏。的宏。n因此，因此，snobol4是第一个几乎可运行于所有机器的语言。在是第一个几乎可运行于所有机器的语言。在其每个实现中有精确相同的语义。其每个实现中有精确相同的语义。nsnobol4使用串替代来实现匹配操作。使用串替代来实现匹配操作。模式匹配模式匹配51模式匹配模式匹配nprolog使用使用“关系作为关系作为

44、n元组集合元组集合”的概念作为匹的概念作为匹配机制。配机制。n通过刻划这些关系的已知实例，其他实例可被导出。通过刻划这些关系的已知实例，其他实例可被导出。n例：有事实例：有事实nparentof(john,mary)nparentof(susan,mary)nparentof(bill,john)nparentof(ann,john)n要想知道要想知道mary的父辈，我们写的父辈，我们写parentof(x,mary)，推导，推导结果结果x可以是可以是john或或susan。n如需知道如需知道mary的两个父辈，式子为：的两个父辈，式子为：nparentof(x,mary), parentof

45、(y,mary), not(x=y)n也可自己建立关系：也可自己建立关系：ngrandparentof(x,y) :- parentof(x,z), parentof(z,y)52模式匹配：模式匹配：项重写项重写n模式匹配的一种限制形式。模式匹配的一种限制形式。n给定串给定串a1a2an和重写规则和重写规则 ,if =ai，则，则a1a2ai-1an是是a1a2an的项重写。的项重写。n例：对文法例：对文法na0b|1nb0an产生产生001串的重写过程为：串的重写过程为：na0b00a001nml将项重写表示为一种函数定义形式。将项重写表示为一种函数定义形式。n例：求阶乘例：求阶乘fun f

46、act (1)=1 | fact (n:int)=n*fact(n-1)返回53合一合一nprolog数据库包含事实和规则。包含一个或多个变量数据库包含事实和规则。包含一个或多个变量的表达式称为查询，用来表示一个未知关系。的表达式称为查询，用来表示一个未知关系。nprolog的主要特性是使用模式匹配来发现是否查询可的主要特性是使用模式匹配来发现是否查询可解。解。n合一是进行模式匹配的方法，用于确定对查询的合法合一是进行模式匹配的方法，用于确定对查询的合法一致的替代。一致的替代。n例：对查询例：对查询nparentof(x, mary)=parentof(john, y)n显然，解答为显然，解答

47、为parentof(john,mary)n我们称，该实例使用替代我们称，该实例使用替代john/x, mary/y,合一了合一了parentof(x, mary)和和parentof(john, y)n合一可视为对替代的公共性质的扩展。合一可视为对替代的公共性质的扩展。54合一：替代与一般合一合一：替代与一般合一n替代替代n这是在编程中学到的第一条原则，涉及参数传递和这是在编程中学到的第一条原则，涉及参数传递和宏扩展。在宏扩展中，是用任意表达式替代一个变宏扩展。在宏扩展中，是用任意表达式替代一个变量。量。n一般合一：一般合一：n要合一两个表达式要合一两个表达式u和和v，需找到对，需找到对u、v

48、中出现的中出现的变量的替代，该替代使两个表达式相同。变量的替代，该替代使两个表达式相同。n例，例，f(x,john), f(g(john),z)n绑定绑定x到到g(john), z到到john可完成合一。可完成合一。n结果为结果为f(g(john),john), 我们将替代称为我们将替代称为 （sigma），），写成写成u =v 55替代和合一的不同替代和合一的不同56替代和合一的不同替代和合一的不同n对替代，有模式定义（表示子程序基调对替代，有模式定义（表示子程序基调或宏定义），以及模式的实例（表示子或宏定义），以及模式的实例（表示子程序调用或宏扩展）。程序调用或宏扩展）。n替代需用实际的实

49、例值来替代模式定义中的替代需用实际的实例值来替代模式定义中的参数。参数。n例：例：f(a, b)=g(a, b)，实例为，实例为f(g(i),h(j)n用用g(i)替替a, h(j)替替b，得到，得到f(a，b)=g(g(i),h(j)57替代和合一的不同替代和合一的不同n对合一，有两个模式定义，和一个模式的一个实例。对合一，有两个模式定义，和一个模式的一个实例。n需要知道的是：是否有对参数的赋值使得模式的实例成为两需要知道的是：是否有对参数的赋值使得模式的实例成为两个模式定义的一个替代。个模式定义的一个替代。n为了应用模式的定义，我们必须在两个方向上替换。为了应用模式的定义，我们必须在两个方向上替换。n例：模式例：模式f(a, b)=g(a, b)，m(c, d)=n(c, d)n实例为：实例为：f(john, m(h(v),7)n如果用如果用john替代替代a，7替代替代d，同时，用，同时，用m(h(v)替代替代b，h(v)替代替代c。n则我们的模式实例代表了一个有效的替代。则我们的模式实例代表了一个有效的替代。n从我们的初始表达式从我们的初始表达式f(john, m(h(v),7)，我们可有两个结，我们可有两个结果。果。n如先作用到如先作用到f：f(jo