布尔表达式的翻译.ppt

Chapter 布尔表达式的翻译
1. 概述
布尔表达式是布尔运算量和逻辑运算符按一定语法规则组成的式子。
逻辑运算符通常有∧、∨、﹃三种(在某些语言中,还有≡(等价)及→(蕴含)等等);
逻辑运算对象可以是逻辑值(True 或 False)、布尔变量、关系表达式以及由括号括起来的布尔表达式。
不论是布尔变量还是布尔表达式,都只能取逻辑值True或False。在计算机内通常用1(或非零整数)表示真值(True),用0表示假值(False)。
关系表达式是形如E1 Rop E2的式子,其中E1和E2为简单算术表达式,Rop为关系运算符(<, >, =, <=, >=, <>)。若E1和E2之值使该关系式成立,则此关系表达式之值为True,否则为False。
2. 布尔表达式的语义及作用
布尔表达式的语义在于指明计算一个逻辑值的规则.
布尔表达式在程序设计语言中有两个基本的作用:
一是在某些控制语句中作为实现控制转移的条件;
另一个则是用于计算逻辑值本身。
约定:各类运算符的优先顺序(由高至低)如下:
⒈括号
⒉算术运算符 *、/
+、-
⒊关系运算符 <、<=、=、>、>=、<>
⒋逻辑运算符 ┒
∧
∨
3. 布尔表达式的等价解释-求值角度
为了方便起见,下面我们仅讨论由文法
E→ E∧E | E∨E | ┑E | (E) | I | i Rop i ()
1)可采用类似算术表达式的方式来进行。例如,对于布尔表达式A∨B∧C,可翻译为:
(∧, B, C, T1 )
(∨, A, T1, T2 )
3. 布尔表达式的等价解释-过程角度
但是,对于一个布尔表达式而言,我们的目的仅仅是为了判定它的真假值。因此,有时只需计算它的一个子表达式,便能确定整个布尔表达式的真假值。例如,对于A∨B,只要知道A为真,则无论B取何值,表达式的结果一定为真。
可见,对于三种常见逻辑运算,可作如下等价的解释:
A∧B (A) ? B : 0 ()
A∨B (A) ? 1 : B ()
﹃A (A) ? 0 : 1 ()
4. 布尔表达式的出口
对于布尔表达式A∨(B∧(┑C∨D)),其等价的表述是
A ? 1 :(B ?((C ? 0 :1)? 1 : D ): 0 )
显然,采用此种结构可产生更为有效的中间代码。这里需假定原布尔表达式的计算过程中不含有任何的副作用。
在上式的计算中,根据A、B、C、D的取值不同,计算的结果以及运算的终止点亦不同。例如,当A=1(真)时,结果为1且终止于左边第一个‘1’处。
这样终止的点我们称为该布尔表达式的出口,同时,把使布尔表达式取值为真的出口称为真出口,反之称为假出口。
对一个布尔表达式而言,它至少有一个真出口和一个假出口(当然可以有多个)。在用于控制流程的布尔表达式E的计算中,这些出口分别指出当E值为真和假时,控制所应转向的目标(即某一四元式的序号)。
5. 控制语句中的布尔表达式
if E then S1 else S2或while E do S
T
E的代码
S1的代码
S2的代码
E的代码
S的代码
T
F
F
(a) if语句
(b) while语句
6. 布尔表达式真假值的确定
一个布尔表达式E的真假值的确定,是在语法翻译过程中,根据()-()等价解释式逐步进行的。
例如,对于布尔表达式 E = E(1) ∨E(2)
若E(1)为真,则E必为真,故E(1)的真出口必是E的真出口(之一);
若E(1)为假,则E的真假值取决于E(2)的真假值,此时,需对E(2)进行计算,由此可见,E(1)的假出口应为E(2)对应的四元式的序号(E(2)的入口),同时,E(2)的真、假出口也是E的真、假出口。
类似地,可确定E(1) ∧ E(2) 、﹃E及更复杂的表达式的真、假出口。
7. 条件语句的翻译结果
在设计布尔表达式翻译算法(即编写语义动作)时,可定义和使用如下三类四元式:
(jnz, A1, ,p)当A1为真(非零)时,转向第p四元式;
(jrop,A1,A2,p)当关系A1 rop A2 成立时,转向第p四元式;
(j, , ,p) 无条件转向第p四元式