第六章
顺 序 控 制
顺序控制提供了操作和数据被组合成程序和程序集合的框架。
涉及两个方面的问题：操作执行顺序的控制（顺序控制），
以及数据在子程序间的传递（数据控制）（下一章）
6.1 隐式和显式顺序控制
顺序控制结构可分为三组,
1、用于表达式中的结构（也针对语句，表达式是语句的基
本建筑块）。如：优先级规则和括号。
2、用于语句或语句组间的结构。如：条件和迭代。
3、用于子程序间的结构，如：子程序调用和协同例程。
这种分法并不是精确的，如 LISP和 APL中只有表达式而无语
句。
顺序控制结构可以是隐含的（缺省的）（由语言定义、程序
员可显式修改）或显式的（程序员可用来显式地修改隐含顺
序）。
6.2 算术表达的顺序控制
考虑方程求根,
该公式至少涉及 15个分开的操作，用汇编或机器语言至少需
要 15条指令甚至更多。而写成 Fortran程序则为,
ROOT=(-B+SQRT(B**2-4*A*C))/(2*A)
这是自然的表达方法，由翻译器而不是程序员来考虑各种优
化问题。
然而，翻译器如何控制正确的操作顺序？
A
CABBr o o t
?
??????
2
42
树结构表示
目前，我们将表达式考虑为单个实体，忽略了其计值必须的
实际语法和语义。
表达式中的基本顺序控制机制是“函数复合”：刻划操作及
其操作数。
函数复合是表达式呈树结构特征，根为主操作，中间节点为
中间层次操作，叶为操作数。如图 6.1，求方程根的表达式的
树。
树表示阐明了表达式的控制结构，低层的数据引用和操作作
为高层操作的操作数，必须先计值，但树表示也留下一些计
值顺序没有指定。
如：－ B和 B**2谁先计值？ B是否可组合为同一引用？
通常语言定义只在树表示级定义表达式计值顺序，允许实现
者决定计值细节。
平
方
根
公
式
的
表
示
?表达式的语法
表达式可表示为树结构，但为了在程序中表示，线性化是
需要的。
?前缀（波兰前缀）记法。
这是波兰数学家发明的无括号记号法。
如,f(x,y,z)
× +ab-ca
LISP使用了该记号法的变种，称为剑桥波兰，用括号
将操作符及其操作数括起来，如,(X(+ab)(-ca))。
?后缀（逆波兰）记号法
类似于前缀，但操作符数在后面，如,
ab+ca-×
?中缀记号法
最适合二元操作，也是我们最常用的方式。
表达式 (a+b)× (c－ a)的树结构
?表达式的语义
上三种记号法对语言的设计都有一些有用的属性，在如何计
算表达式值方面也有不同。
?前缀计值
可以通过一遍扫描计值每个表达式，然而需要知道每个
操作的操作数量。除了可省去括号外，前缀表达式在语
言设计中有如下价值,
1、一般的函数调用均采用前缀方式。
2、可表示有任意数量操作数的操作，写表达式只需
一个语法规则。
3、解码可以机械地很容易地进行，将其翻译成简单
代码序是容易的。
下面算法用一个执行栈计值表达式：对表达式 P,
1、如 P中下一项是操作子，压入栈项，设置所需参数
数目。
2、如 P中下一项是操作数，压入栈项。
3、如栈项 n项是操作数（对栈中第一个 n元操作），
则可以进行计值，用计值结果替代该操作符和操作数。
?后缀计值
后缀计值时，操作符紧跟其操作数后而且操作数已被计值。
1、如 P中下一项是操作数，压入栈顶
2、如 P中下一项是 n元操作符,n个参数必须是栈顶部
的 n个元素，计算结果并替换这 n个元素。
这种计值策略直接、简单，是很多翻译器中生成表达
式代码的基础。
?中缀计值
中缀是常见的，但用于程序语言中会导致一些问题,
1、只适合于二元操作。语言单用中缀是不够的，还需
使用前缀，这二者的混合使翻译更为复杂。
2、表达式中涉及多个中缀操作时，如不使用括号，则
存在固有二义性。为解决这个问题，通常引入隐含的
规则。
操作子计值顺序
?操作的层次（例如优先规则）－－ P245 表 6.1 6.2
?结合律－－是同一层次的隐含规则，亦用于定义操作的
顺序
优先级计算术表达式是合用的，因为表达式语义的数学
模型已对大多数程序员熟知的。然而，当语言引入新的，
不是源自传统数学的操作符时，优先规则不再有用，因
此，有不同方法来处理扩展的操作集。
△ C语言：使用扩展的优先规则集合，表 6.2大多数使用
从左到右的结合律。大多数 C规则是合理的。
△ APL：操作数为数组和矢量，语言没有优先规则。所
有表达式计值从右到左。这规则对大多数表达式也是合
理的，除了一些典型的表达式，如 a-b-c-意为 a-(b-c)。
△ Smalltalk：模型类似 APL，没有优先规则，表达式计
值从左到右。
△ Forth：用于实时过程控制。其运行时结构为栈，语
言是纯后缀的，没有优先规则。
执行时表示
对中缀形式的表达式的解码是困难的，需要翻译为易于解码
的可执行形式。通常的选择有,
1、机器代码序列
表达式被直接翻译成实际的机器代码，而不是先翻译为中间
形式。指令顺序反映了初始表达式的顺序控制结构。
机器代码序列必须使用显式的临时存储位置来保持中间结果，
允许使用硬件解释器，因此，执行速度快。
2、树结构
表达式可以以其自然的树结构直接执行（使用软件解释器）。
执行通过简单的树遍历来完成。
这是 LISP中使用的典型技术，整个程序被表示为树结构。
3、前缀或后缀形式
这两种形式可用前面给出的解释算法来执行。
在某些基于堆栈组织的实际计算机中，实际的机器代码表示
为后缀形式。
前缀表示是 SNOBOL4程序的执行形式，执行从左到右进行。
每个操作递归地调用解释器来计值其操作数。
?表达式的树表示的计值
表达式翻成树结构虽有困难，但总体上是直接的。
而树到可执行原语序列的翻译，则涉及计值顺序的一些
微妙问题。在代码生成中出现的计值顺序问题有,
问题一：一致的计值规则
对表达式树中的每个操作结点，首先计值其操作数（或
生成相应代码），然而应用操作到计算出的操作数上
（或生成相应代码） —— 积极计值规则（ eager）。
而这些计值发生的顺序并不重要，可以选择以优化存储
和其他机器特性。
例，对 (a+b)× (c-a)，下列顺序均可接受。
顺序一：取 a的右值 顺序二：取 c的右值
取 b的右值 取 b的右值
a+b→d 取 a的右值
取 c右值 c-a→e
c-a→e a+b→d
d× e→f 表达式的右值 d× e→f
但是，一致计值规则并不是总可使用的。
例,Z+(Y=0？ X,X/Y)，当 Y≠0时，计算 X/Y
＋
Z
Y 0
X
X Y
IF
＝ /
包含条件的表达式
采用一致规则，对 IF操作，需先计算操作数，即使 Y=0。
显然，此时我们不希望所有操作数被计值。
从而，我们有另一个规则：永不在应用操作之前计值操
作数。
即，总是不计值地传递操作数，由作用操作决定什么时
候计值操作数 —— Lazy计值。
然而，对此规则，实现在很多情况下是不实际的。比如：
如何仿真未计值操作数到操作的传递？这需要软件仿真。
这两种计值规则：积极和隋性（ lazy），对应子程序参
数传递的按值和按名。
对表达式而言，没有简单的一致规则是完全令人满意的，
通常规则是混合的。
问题二：副作用,Side effect。
表达式中使用有副作用的操作，一直是语言设计中的争
论点。考虑,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
执行序不同导致不同结果。
对表达式中副作用的使用有两种选择,
1、不允许副作用
不允许有副作用的函数或对副作用可能影响的表达
式的值改为未定义。
2、允许副作用
但语言定义应精确地给出计值顺序，这将使很多优
化不可能。
通常，语句允许有副作用，如：赋值必须产生副作用。
问题三：出错条件
对可能失败和产生出错条件的操作，涉及一种特殊的副作
用。和一般副作用不同，它将限制到程序员定义的函数，
出错条件可能在很多原操作中出现（溢出、被零除等）。
这类副作用是不希望被排除的，而出错条件的意义，甚至
其出现被计值序的不同而影响。这样，程序员需要精确的
计值顺序控制。
问题四：短路布尔表达式
考虑例子,
if ((A==0)||(B/A>C)){……}
While(I<=UB)&&(V[I]>C)){……}
两个例子中，第二个条件可能产生出错条件。第一个操作
数用于防止错误产生。
在很多语言中，求布尔操作需先计值操作数，这将产生不
期望的错误，因为人们期望左操作数短路右操作数。
Ada中提供了两个特殊的布尔操作来解决这个问题。
and then 和 or else。显式地提供短路机制。
例,if (A=0) or else (B/A>C) then
这将不会失败，因 A=0将导致整个表达式计值结束。
6.3 非算术表达式的顺序控制
模式匹配
这是 SNOBOL4,Prolog,ML等语言中的重要操作 。 操作的成
功是：匹配并赋一变量集到预定义的模板 。 如 BNF文法中分
析树的识别 。
例,A→ 0A0|1A0|01
合法有效串 00100的识别过程为,
A1匹配中间 1
A2匹配 0A10
A3匹配 0A20
SNOBOL为是为直接仿真这个操作而设计的语言 。 其实现独
立于任何实际的机器体系结构, 面向串处理虚拟机而设计 。
为了执行 SNOROL4,需将串处理机的操作实现为现有机器上
的宏 。
因此, SNOBOL4是第一个几乎可运行于所有机器的语言 。 在
其每个实现中有精确相同的语义 。
SNOBOL4使用串替代来实现匹配操作 。
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)
?项重写
模式匹配的一种限制形式。
给定串 a1a2……a n和重写规则 ?=>β,if ? =ai，则
a1a2……a i-1β……a n是 a1a2……a n的项重写。
例：对文法
A→0B|1
B→0A
产生 001串的重写过程为,
A→0B→00A→001
ML将项重写表示为一种函数定义形式。
例：求阶乘 fun fact (1)=1
| fact (N:int)=N*fact(N-1)
合一
Prolog数据库包含事实和规则。包含一个或多个变量的表达
式称为查询，用来表示一个未知关系。
Prolog的主要特性是使用模式匹配来发现是否查询可解。
合一是进行模式匹配的方法，用于确定对查询的合法一致的
替代。
例：对查询
Parentof(X,Mary)=Parentof(John,Y)
显然，解答为 Parentof(John,Mary)
我们称，该实例使用替代 John/X,Mary/Y,合一了
[Parentof(X,Mary)和 Parentof(John,Y)
合一可视为对替代的公共性质的扩展。
替代 —— 这是在编程中学到的第一条原则，涉及参数传
递和宏扩展。在宏扩展中，是用任意表达式替代一个变
量。
一般合一,
要合一两个表达式 U和 V，需找到对 U,V中出现的变量的
替代，该替代使两个表达式相同。
例,f(X,John),f(g(John),Z)
绑定 X到 g(John),Z到 John可完成合一。
结果为 f(g(John),John),我们将替代称为 ? （ sigma）
写成 U?=V ?
图 6.6给出了替代和合一间的不同。
替代和合一间的不同
对替代，有模式定义（表示子程序基调或宏定义），以
及模式的实例（表示子程序调用或宏扩展）。
替代需用实际的实例值来替代模式定义中的参数。
例,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))
对合一，有两个模式定义，和一个模式的一个实例。
需要知道的是：是否有对参数的赋值使得模式的实例成
为两个模式定义的一个替代。
为了应用模式的定义，我们必须在两个方向上替换。
例：模式 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))
因此，合一成功。
?合一在 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合一,
必须继续去寻找有效的解答。
?变换的集合变成查询的答案。
例：一个更完整的例子，下面子句集定义了加法。
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是 ?变换，使查询和数据库中规
则合一。
?实现
Prolog的执行在图 6.7中总结，表示了一标准的树遍历算法
图 6.7(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的规则成功。
如果任何子目标失败，则应用标准的回溯算法，对前面
的子目标采用另一个匹配。如所有子目标失败，则规则
本身失败。图 6.8给出了 add(Y,2,3)计算过程。
Prolog合一
回溯
如果某子目标不能和数据库中某规则匹配，则称规则失败。
可和另外的规则匹配，如所有规则均失败，则我们需回溯到
前一个子目标（已匹配），并试用另外的规则。
回溯算法为,P263
6.4 语句间的顺序控制
基本语句
任何程序的结果由其基本语句确定 。 这里我们不再考虑语句
中表达式, 而是将语句作为考虑的单元来代表一单步计算 。
?数据对象的赋值
通过向数据对象赋值而改变计算状态是影响计算状态的主
要机制 。 有几种这样的语句,
?赋值语句
主要目的是将某表达式的右值赋给某数据对象的左值 。
赋值为每个基本数据类型定义的中心操作 。
?输入语句
大多数语言有一种语句形式, 从终端用户, 文件或通
讯线读数据 。 这样的语句也通过赋值改变变量的值 。
?其他赋值操作
参数传递：给形参赋值
隐含赋值：如 SNOBOL4中的引用, Prolog目标匹配,
声明时初始值等 。
?语句级顺序控制的形式
三种主要的语句级顺序控制,
?复合：语句顺序放置，顺序执行。
?选择：两个语句序列可形成选择，使得一个或另一个序
列被执行，但不能同时执行。
?迭代：一个语句序列被重复执行零次或多次。
这是三种常见结构，语句被组成这三种结构而形成程序。
?显式顺序控制
?goto语句，两种形式
无多件 goto和条件 goto
Goto语句导致无结构的设计。语言的很多形式模型均
不允许 goto存在。
此外,goto也是多余的，没有 goto也可以写出同样能力
的程序。
?Break语句
通常使控制被前移到一个显式点（在给定控制结构的
结束处）。
如 C中 Break语句使得立即退出 while,for,switch语句。
C中还有 Continue语句，只结束本次循环。
结构化 break语句
?结构的程序设计
70年代,goto语句受到很大攻击，以至有的语言完全删去
了 goto。 goto 语句有一些优点,
①如果标号只是局部语法标记，则对高效执行有直接
的硬件支持。
②在小程序中使用简单、容易。
③为汇编语言和老语言用户熟悉。
④可用为通用建筑块来表示（仿真）其他控制形式。
然而，它也有严重的缺点,
1、缺乏层次的程序结构
程序的正确性和开发效率已远比效率更为重要，语言
也应反应此需求。单进单出的控制结构概念，已成为
更易理解的设计。层次化提供了一种抽象，符合“分
而治之”的思想。而 goto将打破这种层次性。
2、程序文本中语句顺序不一定对应执行的顺序。
要理解程序，必须理解语句的执行顺序。
静态顺序和动态顺序有关联将使程序更易于理解。
3、语句组可能有多个用途。
如果每个组只含单个用途。则程序更易理解。
人为地通过 goto使某组有多用途将打乱执行顺序，使
程序难于修改。
?结构化程序设计强调,
①程序结构的层次设计，只用三种控制结构。
②层次设计的表示应直接体现在程序文本中（只使用
结构化控制语句）。
③语句的文本序列对应执行序列,
④使用单一用途的语句组。
结构顺序控制
大多数语言提供了控制语句集合来表示三种基本的控制形式，
这些语句均应该是单入单出的。它们所构成的程序，其执行
和语句序基本对应。
?复合语句
一个语句序列，可按单个语句处理来构造更大的语句。
用 begin……end 和 { }等来构造
其实现是将其存放在一个连续存储区域中。
?条件语句
用来表示两个或更多语句的选择执行，或单个语句的可
选执行。
?if 语句
单分枝,if 条件 then 语句 语句的可选执行
两分枝,if 条件 then…else…
还可表示多分枝。
?case语句，重复测试某变量的值。
case Tag is
When 0→
When 1→
……
endcase
?实现
if语句常用硬件支持的分枝和跳转指令实现。
case语句常用跳转表来避免同一变量值的重复测试。
跳转表是一个向量，顺序存放在内存中，其部件是无
条件跳转指令。
case
语句
的跳
转表
实现
?迭代语句
提供重复计算的机制。通常分为头和体两部分。体提供
语句的动作。头控制重复执行体的次数。
?简单重复
直接给出执行的次数。
例,COBOL中,perform body k times
?当条件成立时重复
while test do body
?计数器增量的重复
for I:=1 step 2 until 30 do body
?无限重复
Loop
exit when condition 没有显式的终止测试。
endloop
?循环的实现
直接使用硬件提供的分支 /跳转指令。
?结构顺序控制中的问题
?多出口循环
经常几个条件需要循环的终止。
如：搜索循环是一个例子,
从 K元素矢量中搜索第一个满足某条件的元素。
For I:=1 to k do
if VECT(I)=0 the goto ?
for I in 1…k loop
exit when VECT (I)=0;
endloop
?do-while-do
经常最自然的测试是否退出循环的地方是在中间部位，即
已完成某些处理之后。
loop
read(x)
if end-of-file then goto ?
process (x)
end loop
称为 do while do，因为中间点 while是需要的
do while do
read (x)
while (not end-of-file)
process (x)
end
?例外条件
例外可表示各种错误条件。
Raise BAD-CHAR-VALVE
基本程序（ Prime Program）
基本程序的理论可用于描述一致的控制结构理论。
1975年由 Maddux提出，作为结构化程序设计的推广，以定义
唯一的流程图分解。
假定程序图有三类结点,
每个流程图由这三类结构成 。
功能结点 决策结点 汇合结点
?合式程序（ proper program ） —— 控制结构的形式模式，
是如下的流程图。
1、有单个进入线
2、有单个退出线
3、有从入口到每个结点和从每个结点到出口的路径。
我们的目标是区分“结构的”“合式程序”和“非结构的”
合式程序。下图均为合式程序，差别在于结构性。
?基本程序 —— 是合式程序，但不能被分为更小的合式程
序，（功能结点的长序列被视为基本的）。
?复合程序 —— 是合式程序，但不是基本的。
所有基本程序可以枚举出来，图 6.13描述了所有到 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是循环（一旦循环，将不会终
止）。
通过分析，也就不会对语言用本章描述的控制结构来定义感
到奇怪，所用的控制结构均是具有少量结点的基本程序。
通过枚举，我们看出,do-while-do是自然的控制结构。但很
少有语言提供这种机制。
基
本
程
序
的
枚
举
?结构定理
Bohm & Jacobini—— 任何基本程序可被转换为只使用
while和 if的基本程序。
图 6.14是该构造过程的一个类似过程的概述,
1、给定任意流程图，标记每个结点，出口标记为 O
2、定义 I为新的程序变量
3、对流程图中每个结点，应用图 6.14(a)中描述的转换
规则。
4、如图 6.14(b)重建程序。
这里 I类似虚拟机指令计数器，指出下一条执行语句。
整个程序简单地是一系列嵌套的 if语句（在单个 while循环
中），这样，任何程序可用此法转换为“良构”程序。
结
构
定
理
顺 序 控 制
顺序控制提供了操作和数据被组合成程序和程序集合的框架。
涉及两个方面的问题：操作执行顺序的控制（顺序控制），
以及数据在子程序间的传递（数据控制）（下一章）
6.1 隐式和显式顺序控制
顺序控制结构可分为三组,
1、用于表达式中的结构（也针对语句，表达式是语句的基
本建筑块）。如：优先级规则和括号。
2、用于语句或语句组间的结构。如：条件和迭代。
3、用于子程序间的结构，如：子程序调用和协同例程。
这种分法并不是精确的，如 LISP和 APL中只有表达式而无语
句。
顺序控制结构可以是隐含的（缺省的）（由语言定义、程序
员可显式修改）或显式的（程序员可用来显式地修改隐含顺
序）。
6.2 算术表达的顺序控制
考虑方程求根,
该公式至少涉及 15个分开的操作，用汇编或机器语言至少需
要 15条指令甚至更多。而写成 Fortran程序则为,
ROOT=(-B+SQRT(B**2-4*A*C))/(2*A)
这是自然的表达方法，由翻译器而不是程序员来考虑各种优
化问题。
然而，翻译器如何控制正确的操作顺序？
A
CABBr o o t
?
??????
2
42
树结构表示
目前，我们将表达式考虑为单个实体，忽略了其计值必须的
实际语法和语义。
表达式中的基本顺序控制机制是“函数复合”：刻划操作及
其操作数。
函数复合是表达式呈树结构特征，根为主操作，中间节点为
中间层次操作，叶为操作数。如图 6.1，求方程根的表达式的
树。
树表示阐明了表达式的控制结构，低层的数据引用和操作作
为高层操作的操作数，必须先计值，但树表示也留下一些计
值顺序没有指定。
如：－ B和 B**2谁先计值？ B是否可组合为同一引用？
通常语言定义只在树表示级定义表达式计值顺序，允许实现
者决定计值细节。
平
方
根
公
式
的
表
示
?表达式的语法
表达式可表示为树结构，但为了在程序中表示，线性化是
需要的。
?前缀（波兰前缀）记法。
这是波兰数学家发明的无括号记号法。
如,f(x,y,z)
× +ab-ca
LISP使用了该记号法的变种，称为剑桥波兰，用括号
将操作符及其操作数括起来，如,(X(+ab)(-ca))。
?后缀（逆波兰）记号法
类似于前缀，但操作符数在后面，如,
ab+ca-×
?中缀记号法
最适合二元操作，也是我们最常用的方式。
表达式 (a+b)× (c－ a)的树结构
?表达式的语义
上三种记号法对语言的设计都有一些有用的属性，在如何计
算表达式值方面也有不同。
?前缀计值
可以通过一遍扫描计值每个表达式，然而需要知道每个
操作的操作数量。除了可省去括号外，前缀表达式在语
言设计中有如下价值,
1、一般的函数调用均采用前缀方式。
2、可表示有任意数量操作数的操作，写表达式只需
一个语法规则。
3、解码可以机械地很容易地进行，将其翻译成简单
代码序是容易的。
下面算法用一个执行栈计值表达式：对表达式 P,
1、如 P中下一项是操作子，压入栈项，设置所需参数
数目。
2、如 P中下一项是操作数，压入栈项。
3、如栈项 n项是操作数（对栈中第一个 n元操作），
则可以进行计值，用计值结果替代该操作符和操作数。
?后缀计值
后缀计值时，操作符紧跟其操作数后而且操作数已被计值。
1、如 P中下一项是操作数，压入栈顶
2、如 P中下一项是 n元操作符,n个参数必须是栈顶部
的 n个元素，计算结果并替换这 n个元素。
这种计值策略直接、简单，是很多翻译器中生成表达
式代码的基础。
?中缀计值
中缀是常见的，但用于程序语言中会导致一些问题,
1、只适合于二元操作。语言单用中缀是不够的，还需
使用前缀，这二者的混合使翻译更为复杂。
2、表达式中涉及多个中缀操作时，如不使用括号，则
存在固有二义性。为解决这个问题，通常引入隐含的
规则。
操作子计值顺序
?操作的层次（例如优先规则）－－ P245 表 6.1 6.2
?结合律－－是同一层次的隐含规则，亦用于定义操作的
顺序
优先级计算术表达式是合用的，因为表达式语义的数学
模型已对大多数程序员熟知的。然而，当语言引入新的，
不是源自传统数学的操作符时，优先规则不再有用，因
此，有不同方法来处理扩展的操作集。
△ C语言：使用扩展的优先规则集合，表 6.2大多数使用
从左到右的结合律。大多数 C规则是合理的。
△ APL：操作数为数组和矢量，语言没有优先规则。所
有表达式计值从右到左。这规则对大多数表达式也是合
理的，除了一些典型的表达式，如 a-b-c-意为 a-(b-c)。
△ Smalltalk：模型类似 APL，没有优先规则，表达式计
值从左到右。
△ Forth：用于实时过程控制。其运行时结构为栈，语
言是纯后缀的，没有优先规则。
执行时表示
对中缀形式的表达式的解码是困难的，需要翻译为易于解码
的可执行形式。通常的选择有,
1、机器代码序列
表达式被直接翻译成实际的机器代码，而不是先翻译为中间
形式。指令顺序反映了初始表达式的顺序控制结构。
机器代码序列必须使用显式的临时存储位置来保持中间结果，
允许使用硬件解释器，因此，执行速度快。
2、树结构
表达式可以以其自然的树结构直接执行（使用软件解释器）。
执行通过简单的树遍历来完成。
这是 LISP中使用的典型技术，整个程序被表示为树结构。
3、前缀或后缀形式
这两种形式可用前面给出的解释算法来执行。
在某些基于堆栈组织的实际计算机中，实际的机器代码表示
为后缀形式。
前缀表示是 SNOBOL4程序的执行形式，执行从左到右进行。
每个操作递归地调用解释器来计值其操作数。
?表达式的树表示的计值
表达式翻成树结构虽有困难，但总体上是直接的。
而树到可执行原语序列的翻译，则涉及计值顺序的一些
微妙问题。在代码生成中出现的计值顺序问题有,
问题一：一致的计值规则
对表达式树中的每个操作结点，首先计值其操作数（或
生成相应代码），然而应用操作到计算出的操作数上
（或生成相应代码） —— 积极计值规则（ eager）。
而这些计值发生的顺序并不重要，可以选择以优化存储
和其他机器特性。
例，对 (a+b)× (c-a)，下列顺序均可接受。
顺序一：取 a的右值 顺序二：取 c的右值
取 b的右值 取 b的右值
a+b→d 取 a的右值
取 c右值 c-a→e
c-a→e a+b→d
d× e→f 表达式的右值 d× e→f
但是，一致计值规则并不是总可使用的。
例,Z+(Y=0？ X,X/Y)，当 Y≠0时，计算 X/Y
＋
Z
Y 0
X
X Y
IF
＝ /
包含条件的表达式
采用一致规则，对 IF操作，需先计算操作数，即使 Y=0。
显然，此时我们不希望所有操作数被计值。
从而，我们有另一个规则：永不在应用操作之前计值操
作数。
即，总是不计值地传递操作数，由作用操作决定什么时
候计值操作数 —— Lazy计值。
然而，对此规则，实现在很多情况下是不实际的。比如：
如何仿真未计值操作数到操作的传递？这需要软件仿真。
这两种计值规则：积极和隋性（ lazy），对应子程序参
数传递的按值和按名。
对表达式而言，没有简单的一致规则是完全令人满意的，
通常规则是混合的。
问题二：副作用,Side effect。
表达式中使用有副作用的操作，一直是语言设计中的争
论点。考虑,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
执行序不同导致不同结果。
对表达式中副作用的使用有两种选择,
1、不允许副作用
不允许有副作用的函数或对副作用可能影响的表达
式的值改为未定义。
2、允许副作用
但语言定义应精确地给出计值顺序，这将使很多优
化不可能。
通常，语句允许有副作用，如：赋值必须产生副作用。
问题三：出错条件
对可能失败和产生出错条件的操作，涉及一种特殊的副作
用。和一般副作用不同，它将限制到程序员定义的函数，
出错条件可能在很多原操作中出现（溢出、被零除等）。
这类副作用是不希望被排除的，而出错条件的意义，甚至
其出现被计值序的不同而影响。这样，程序员需要精确的
计值顺序控制。
问题四：短路布尔表达式
考虑例子,
if ((A==0)||(B/A>C)){……}
While(I<=UB)&&(V[I]>C)){……}
两个例子中，第二个条件可能产生出错条件。第一个操作
数用于防止错误产生。
在很多语言中，求布尔操作需先计值操作数，这将产生不
期望的错误，因为人们期望左操作数短路右操作数。
Ada中提供了两个特殊的布尔操作来解决这个问题。
and then 和 or else。显式地提供短路机制。
例,if (A=0) or else (B/A>C) then
这将不会失败，因 A=0将导致整个表达式计值结束。
6.3 非算术表达式的顺序控制
模式匹配
这是 SNOBOL4,Prolog,ML等语言中的重要操作 。 操作的成
功是：匹配并赋一变量集到预定义的模板 。 如 BNF文法中分
析树的识别 。
例,A→ 0A0|1A0|01
合法有效串 00100的识别过程为,
A1匹配中间 1
A2匹配 0A10
A3匹配 0A20
SNOBOL为是为直接仿真这个操作而设计的语言 。 其实现独
立于任何实际的机器体系结构, 面向串处理虚拟机而设计 。
为了执行 SNOROL4,需将串处理机的操作实现为现有机器上
的宏 。
因此, SNOBOL4是第一个几乎可运行于所有机器的语言 。 在
其每个实现中有精确相同的语义 。
SNOBOL4使用串替代来实现匹配操作 。
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)
?项重写
模式匹配的一种限制形式。
给定串 a1a2……a n和重写规则 ?=>β,if ? =ai，则
a1a2……a i-1β……a n是 a1a2……a n的项重写。
例：对文法
A→0B|1
B→0A
产生 001串的重写过程为,
A→0B→00A→001
ML将项重写表示为一种函数定义形式。
例：求阶乘 fun fact (1)=1
| fact (N:int)=N*fact(N-1)
合一
Prolog数据库包含事实和规则。包含一个或多个变量的表达
式称为查询，用来表示一个未知关系。
Prolog的主要特性是使用模式匹配来发现是否查询可解。
合一是进行模式匹配的方法，用于确定对查询的合法一致的
替代。
例：对查询
Parentof(X,Mary)=Parentof(John,Y)
显然，解答为 Parentof(John,Mary)
我们称，该实例使用替代 John/X,Mary/Y,合一了
[Parentof(X,Mary)和 Parentof(John,Y)
合一可视为对替代的公共性质的扩展。
替代 —— 这是在编程中学到的第一条原则，涉及参数传
递和宏扩展。在宏扩展中，是用任意表达式替代一个变
量。
一般合一,
要合一两个表达式 U和 V，需找到对 U,V中出现的变量的
替代，该替代使两个表达式相同。
例,f(X,John),f(g(John),Z)
绑定 X到 g(John),Z到 John可完成合一。
结果为 f(g(John),John),我们将替代称为 ? （ sigma）
写成 U?=V ?
图 6.6给出了替代和合一间的不同。
替代和合一间的不同
对替代，有模式定义（表示子程序基调或宏定义），以
及模式的实例（表示子程序调用或宏扩展）。
替代需用实际的实例值来替代模式定义中的参数。
例,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))
对合一，有两个模式定义，和一个模式的一个实例。
需要知道的是：是否有对参数的赋值使得模式的实例成
为两个模式定义的一个替代。
为了应用模式的定义，我们必须在两个方向上替换。
例：模式 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))
因此，合一成功。
?合一在 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合一,
必须继续去寻找有效的解答。
?变换的集合变成查询的答案。
例：一个更完整的例子，下面子句集定义了加法。
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是 ?变换，使查询和数据库中规
则合一。
?实现
Prolog的执行在图 6.7中总结，表示了一标准的树遍历算法
图 6.7(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的规则成功。
如果任何子目标失败，则应用标准的回溯算法，对前面
的子目标采用另一个匹配。如所有子目标失败，则规则
本身失败。图 6.8给出了 add(Y,2,3)计算过程。
Prolog合一
回溯
如果某子目标不能和数据库中某规则匹配，则称规则失败。
可和另外的规则匹配，如所有规则均失败，则我们需回溯到
前一个子目标（已匹配），并试用另外的规则。
回溯算法为,P263
6.4 语句间的顺序控制
基本语句
任何程序的结果由其基本语句确定 。 这里我们不再考虑语句
中表达式, 而是将语句作为考虑的单元来代表一单步计算 。
?数据对象的赋值
通过向数据对象赋值而改变计算状态是影响计算状态的主
要机制 。 有几种这样的语句,
?赋值语句
主要目的是将某表达式的右值赋给某数据对象的左值 。
赋值为每个基本数据类型定义的中心操作 。
?输入语句
大多数语言有一种语句形式, 从终端用户, 文件或通
讯线读数据 。 这样的语句也通过赋值改变变量的值 。
?其他赋值操作
参数传递：给形参赋值
隐含赋值：如 SNOBOL4中的引用, Prolog目标匹配,
声明时初始值等 。
?语句级顺序控制的形式
三种主要的语句级顺序控制,
?复合：语句顺序放置，顺序执行。
?选择：两个语句序列可形成选择，使得一个或另一个序
列被执行，但不能同时执行。
?迭代：一个语句序列被重复执行零次或多次。
这是三种常见结构，语句被组成这三种结构而形成程序。
?显式顺序控制
?goto语句，两种形式
无多件 goto和条件 goto
Goto语句导致无结构的设计。语言的很多形式模型均
不允许 goto存在。
此外,goto也是多余的，没有 goto也可以写出同样能力
的程序。
?Break语句
通常使控制被前移到一个显式点（在给定控制结构的
结束处）。
如 C中 Break语句使得立即退出 while,for,switch语句。
C中还有 Continue语句，只结束本次循环。
结构化 break语句
?结构的程序设计
70年代,goto语句受到很大攻击，以至有的语言完全删去
了 goto。 goto 语句有一些优点,
①如果标号只是局部语法标记，则对高效执行有直接
的硬件支持。
②在小程序中使用简单、容易。
③为汇编语言和老语言用户熟悉。
④可用为通用建筑块来表示（仿真）其他控制形式。
然而，它也有严重的缺点,
1、缺乏层次的程序结构
程序的正确性和开发效率已远比效率更为重要，语言
也应反应此需求。单进单出的控制结构概念，已成为
更易理解的设计。层次化提供了一种抽象，符合“分
而治之”的思想。而 goto将打破这种层次性。
2、程序文本中语句顺序不一定对应执行的顺序。
要理解程序，必须理解语句的执行顺序。
静态顺序和动态顺序有关联将使程序更易于理解。
3、语句组可能有多个用途。
如果每个组只含单个用途。则程序更易理解。
人为地通过 goto使某组有多用途将打乱执行顺序，使
程序难于修改。
?结构化程序设计强调,
①程序结构的层次设计，只用三种控制结构。
②层次设计的表示应直接体现在程序文本中（只使用
结构化控制语句）。
③语句的文本序列对应执行序列,
④使用单一用途的语句组。
结构顺序控制
大多数语言提供了控制语句集合来表示三种基本的控制形式，
这些语句均应该是单入单出的。它们所构成的程序，其执行
和语句序基本对应。
?复合语句
一个语句序列，可按单个语句处理来构造更大的语句。
用 begin……end 和 { }等来构造
其实现是将其存放在一个连续存储区域中。
?条件语句
用来表示两个或更多语句的选择执行，或单个语句的可
选执行。
?if 语句
单分枝,if 条件 then 语句 语句的可选执行
两分枝,if 条件 then…else…
还可表示多分枝。
?case语句，重复测试某变量的值。
case Tag is
When 0→
When 1→
……
endcase
?实现
if语句常用硬件支持的分枝和跳转指令实现。
case语句常用跳转表来避免同一变量值的重复测试。
跳转表是一个向量，顺序存放在内存中，其部件是无
条件跳转指令。
case
语句
的跳
转表
实现
?迭代语句
提供重复计算的机制。通常分为头和体两部分。体提供
语句的动作。头控制重复执行体的次数。
?简单重复
直接给出执行的次数。
例,COBOL中,perform body k times
?当条件成立时重复
while test do body
?计数器增量的重复
for I:=1 step 2 until 30 do body
?无限重复
Loop
exit when condition 没有显式的终止测试。
endloop
?循环的实现
直接使用硬件提供的分支 /跳转指令。
?结构顺序控制中的问题
?多出口循环
经常几个条件需要循环的终止。
如：搜索循环是一个例子,
从 K元素矢量中搜索第一个满足某条件的元素。
For I:=1 to k do
if VECT(I)=0 the goto ?
for I in 1…k loop
exit when VECT (I)=0;
endloop
?do-while-do
经常最自然的测试是否退出循环的地方是在中间部位，即
已完成某些处理之后。
loop
read(x)
if end-of-file then goto ?
process (x)
end loop
称为 do while do，因为中间点 while是需要的
do while do
read (x)
while (not end-of-file)
process (x)
end
?例外条件
例外可表示各种错误条件。
Raise BAD-CHAR-VALVE
基本程序（ Prime Program）
基本程序的理论可用于描述一致的控制结构理论。
1975年由 Maddux提出，作为结构化程序设计的推广，以定义
唯一的流程图分解。
假定程序图有三类结点,
每个流程图由这三类结构成 。
功能结点 决策结点 汇合结点
?合式程序（ proper program ） —— 控制结构的形式模式，
是如下的流程图。
1、有单个进入线
2、有单个退出线
3、有从入口到每个结点和从每个结点到出口的路径。
我们的目标是区分“结构的”“合式程序”和“非结构的”
合式程序。下图均为合式程序，差别在于结构性。
?基本程序 —— 是合式程序，但不能被分为更小的合式程
序，（功能结点的长序列被视为基本的）。
?复合程序 —— 是合式程序，但不是基本的。
所有基本程序可以枚举出来，图 6.13描述了所有到 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是循环（一旦循环，将不会终
止）。
通过分析，也就不会对语言用本章描述的控制结构来定义感
到奇怪，所用的控制结构均是具有少量结点的基本程序。
通过枚举，我们看出,do-while-do是自然的控制结构。但很
少有语言提供这种机制。
基
本
程
序
的
枚
举
?结构定理
Bohm & Jacobini—— 任何基本程序可被转换为只使用
while和 if的基本程序。
图 6.14是该构造过程的一个类似过程的概述,
1、给定任意流程图，标记每个结点，出口标记为 O
2、定义 I为新的程序变量
3、对流程图中每个结点，应用图 6.14(a)中描述的转换
规则。
4、如图 6.14(b)重建程序。
这里 I类似虚拟机指令计数器，指出下一条执行语句。
整个程序简单地是一系列嵌套的 if语句（在单个 while循环
中），这样，任何程序可用此法转换为“良构”程序。
结
构
定
理
