布尔表达式的翻译.ppt

Ch apt er 布尔表达式的翻译 1 . 概述??布尔表布尔表达式达式是布尔运算量和逻辑运算符按一定语法规则组成的式子。??逻辑逻辑运算符运算符通常有∧、∨、﹃三种(在某些语言中, 还有≡(等价) 及→(蕴含)等等); ??逻辑运逻辑运算对象算对象可以是逻辑值( Tr ue 或F als e )、布尔变量、关系表达式以及由括号括起来的布尔表达式。?不论是布尔变量还是布尔表达式, 都只能取逻辑值 Tru e或F als e。在计算机内通常用1(或非零整数) 表示真值( T rue ),用 0 表示假值( Fal se )。??关系关系表达式表达式是形如 E E 1 1 Rop Rop E E 2 2的式子,其中 E E 1 1和E E 2 2为简单算术表达式, R R op op 为关系运算符( <, <, >, >, =, =, <=, <=, >= >= , < , < > >)。若E E 1 1和E E 2 2 之值使该关系式成立,则此关系表达式之值为 T rue ,否则为 Fa lse 。 2 . 布尔表达式的语义及作用?布尔表达式的语义在于指明计算一个逻辑值的规则. ?布尔表达式在程序设计语言中有两个基本的作用: ?一是在某些控制语句中作为实现控制转移的条件; ?另一个则是用于计算逻辑值本身。?约定: 各类运算符的优先顺序( 由高至低) 如下: ⒈括号⒉算术运算符*、/ + 、- ⒊关系运算符<、<= 、=、>、>= 、<> ⒋逻辑运算符┒∧∨ -求值角度为了方为了方便起见便起见,下面,下面我们仅我们仅讨论由讨论由文法文法 E E→→ E E∧∧ E | E | E E∨∨ E | E | ┑┑E E | | (E) (E) | | I I | | i i Ro Ro p i p i ( ( ) ) 1 1 )可采)可采用类似用类似算术表算术表达式的达式的方式来方式来进行。进行。例如, 例如, 对于布对于布尔表达尔表达式式A A∨∨B B∧∧C C,可翻,可翻译为: 译为: ( (∧∧, ,B B, ,C C, ,T T 1 ) 1 ) ( (∨∨, ,A A, ,T T 1, 1, T2 T2 ) ) -过程角度但但是,对是,对于一个于一个布尔表布尔表达式而达式而言,我言,我们的目们的目的仅仅的仅仅是为了是为了判定它判定它的真假的真假值。因值。因此,有此,有时只需时只需计算它计算它的一个的一个子表达子表达式,便式,便能确定能确定整个布整个布尔表达尔表达式的真式的真假值。假值。例如, 例如, 对于对于 A A∨∨B B, , 只要知只要知道道A A为为真,则真,则无论无论 B B 取何值取何值, , 表达表达式的结式的结果一定果一定为真。为真。可见可见,对于,对于三种常三种常见逻辑见逻辑运算, 运算, 可作可作如如下等价下等价的解释的解释: : A A∧∧B B??(A) (A) ? ? B : B : 0 0 (5 (5 .2) .2) A A∨∨B B??( ( A) A) ? 1 ? 1 : : B B (5. (5. 3) 3) ﹃﹃A A (A) (A) ? ? 0 : 0 : 1 1 (5 (5 .4) .4) 4. 布尔表达式的出口对对于于布尔布尔表达式表达式 A A∨∨( (B B∧∧( (┑┑C C∨∨D D) )) ) ,其,其等等价的表价的表述是述是 A A ? ?1 1:( :( B B ? ?(( (( C C? ? 0 0 : :1 1)? )? 1 1: : D D ) ): :0 0) ) 显显然,采然,采用此种用此种结构可结构可产生更产生更为有效为有效的中间的中间代码。代码。这里需这里需假定原假定原布尔表布尔表达式达式的的计算过计算过程程中不中不含有任含有任何的何的副副作用作用。。在在上式的上式的计算中计算中,根据,根据 A A、、B B、、C C、、D D的取的取值值不同不同,计算,计算的结果的结果以及运以及运算的终算的终止点亦止点亦不同。不同。例如, 例如, 当当 A= A= 1 1(真(真)时, )时, 结果为结果为 1 1且终且终止止于左于左边第一边第一个个‘‘1 1’’处。处。这样这样终止的终止的点我们点我们称为该称为该布尔表布尔表达式达式的的出口出口, , 同时, 同时, 把使把使布布尔表达尔表达式式取值取值为为真真的的出口出口称称为为真出真出口口,反,反之称为之称为假出口假出口。。对对一个一个布布尔表达尔表达式式而言而言,它至,它至少有一少有一个个真出真出口口和一和一个