布爾表達式

布爾表達式

布爾表達式(Boolean expression)是一段代碼聲明,它最終只有true(真)和false(假)兩個取值。最簡單的布爾表達式是等式(equality),這種布爾表達式用來測試一個值是否與另一個值相同。

基本信息

介紹

布爾表達式(Boolean expression) 布爾表達式(Boolean expression)

從最基本的層次來說,所有的布爾表達式,不論它的長短如何,其值只能是true或false。

最簡單的布爾表達式是等式(equality)。這種布爾表達式用來測試一個值是否與另一個值相同。它可以是一個簡單的等式,例如:

2 == 4

上面這個布爾表達式的值是false,因為2和4不相等。它也可以是複雜的等式,如:

MyObject.MyProperty == YourObject.YourProperty

這個等式的值是不確定的,可能取真值也可能取假值,只有在程式運行時才能確定。如果你對C、C++甚至C#比較熟悉的話,就會知道上式中的= = (雙等號) 是一個邏輯布爾操作符,而= (單等號)是用來對變數賦值的賦值操作符。程式設計師有時會將這兩個操作符放錯位置,這是一個導致程式在編譯時或運行時出錯的常見原因。

概述

布爾表達式是布爾運算量和邏輯運算符按一定語法規則組成的式子。 n邏輯運算符通常有∧、∨、﹃三種(在某些語言中,還有≡(等價)及→(蘊含)等等);

邏輯運算對象可以是邏輯值(True 或False)、布爾變數、關係表達式以及由括弧括起來的布爾表達式。

不論是布爾變數還是布爾表達式,都只能取邏輯值True或False。在計算機內通常用1(或非零整數)表示真值(True),用0表示假值(False)。

關係表達式是形如E1 Rop E2的式子,其中E1和E2為簡單算術表達式,Rop 為關係運算符(<, >, =, <=, >=, <> )。若E1和E2之值使該關係式成立,則此關係表達式之值為True ,否則為False 。

作用

布爾表達式的語義在於指明計算一個邏輯值的規則;

布爾表達式在程式設計語言中有兩個基本的作用:

一是在某些控制語句中作為實現控制轉移的條件;

另一個則是用於計算邏輯值本身。

約定:各類運算符的優先順序(由高至低)如下:

⒈括弧

⒉算術運算符 *(乘法) / (除法) +(加法) -(減法) %(模)(返回一個除法的整數餘數,例如:12%5=2,這裡是因為12除以5的餘數是2)

⒊關係運算符 <(小於)、<=(小於等於)、=(等於)、>(大於)、>=(大於等於)、<>(不等於)

⒋邏輯運算符 ┒ ∧ ∨

3. 布爾表達式的等價解釋-求值角度

為了方便起見,下面我們僅討論由文法

E→ E∧E | E∨E | ┑E | (E) | I | i Rop i (5.1)

可採用類似算術表達式的方式來進行。例如,對於布爾表達式A∨B∧C,可翻譯為:

(∧, B, C, T1 )

(∨, A, T1, T2 )

過程角度

對於一個布爾表達式而言,我們的目的僅僅是為了判定它的真假值。因此,有時只需計算它的一個子表達式,便能確定整個布爾表達式的真假值。例如,對於A∨B,只要知道A為真,則無論B取何值,表達式的結果一定為真。

可見,對於三種常見邏輯運算,可作如下等價的解釋:

A∧B —(A) ? B : 0 (5.2)

A∨B —(A) ? 1 : B (5.3)

﹃A (A) ? 0 : 1 (5.4)

出口

對於布爾表達式A∨(B∧(┑C∨D)),其等價的表述是

A ?1 :(B ?((C ?0 :1)? 1 :D ):0 )

顯然,採用此種結構可產生更為有效的中間代碼。這裡需假定原布爾表達式的計算過程中不含有任何的副作用。

在上式的計算中,根據A、B、C、D的取值不同,計算的結果以及運算的終止點亦不同。例如,當A=1(真)時,結果為1且終止於左邊第一個‘1’處。

這樣終止的點我們稱為該布爾表達式的出口,同時,把使布爾表達式取值為真的出口稱為真出口,反之稱為假出口。

對一個布爾表達式而言,它至少有一個真出口和一個假出口(當然可以有多個)。在用於控制流程的布爾表達式E的計算中,這些出口分別指出當E值為真和假時,控制所應轉向的目標(即某一四元式的序號)。

表達式

if E then S1 else S2或while E do S

確定

一個布爾表達式E的真假值的確定,是在語法翻譯過程中,根據(5.2)-(5.4)等價解釋式逐步進行的。

例如,對於布爾表達式 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及更複雜的表達式的真、假出口。

譯結果

在設計布爾表達式翻譯算法(即編寫語義動作)時,可定義和使用如下三類四元式:

(jnz, A1, ,p)—當A1為真(非零)時,轉向第p四元式;

(jrop,A1,A2,p)當關係A1 rop A2成立時,轉向第p四元式;

(j, , ,p)無條件轉向第p四元式

例如,對於條件語句

if A∨B<C then S1 else S2

經翻譯後,可得四元式序列:

(1) (jnz, A, -, 5)

(2) (j, - ,- , 3)

(3) (j<, B, C, 5)

(4) (j, -, -, p+1)

(5) S1相應的四元式序列

(p) (j, -, -, q)

(p+1) S2相應的四元式序列

(q) …

其中,表達式A的真出口為5(也是整個表達式的真出口),假出口為3(即表達式B<C的第一四元式);B<C的真、假出口也分別是整個表達式的真、假出口 。

拉鏈回填

在自底向上的語法制導翻譯時(或者說,在S-屬性翻譯文法中), 在產生一個(無)條件轉移四元式時, 它所要轉向的那個四元式有時尚未產生,故無法立即產生一個完全的控制轉移四元式。

例如,在上例中,在產生第一個四元式時,由於語句S1的中間代碼尚未產生,即A的真出口確切位置並不知道,故此時只能產生一個空缺轉移目標的四元式 (jnz,A,-,0),

並將此四元式的序號(即1)作為語義信息存起來,待開始翻譯S1時,再將S1的第一四元式的序號(即5)回填這個不完全的四元式。

另外,在翻譯過程中,常常會出現若干轉移四元式轉向同一目標,但此目標的具體位置又尚未確定的情況,此時我們可將這些四元式用拉鏈的辦法將它們連結起來,用一指針指向鏈頭,在確定了目標四元式的位置之後,再回填這個鏈。

n對於一個布爾表達式E來說,它應有兩條鏈:真出口鏈(稱為T鏈,記作TC)和假出口鏈(稱為F鏈,記作FC)。它們就是非終結符Expr的兩個屬性Expr . TC及Expr . FC。

n例如,對於上述if語句中的布爾式E=A∨B<C,在翻譯過程中形成的T鏈和F鏈如右圖所示。

n其中,每條鏈都是利用四元式中的Result域連線的,Result >0時,它給出本鏈的後繼四元式的序號,Result =0時表示本四元式是鏈尾結點。

拆分

n為便於實現布爾表達式的語法制導翻譯,我們先改寫文法,以便能在翻譯過程中的適當時機獲得所需的語義屬性值。例如,可將文法(5.1)改寫為:

qExpr®Expr^ Expr | Expr∨ Expr | ﹃ Expr|

iden |iden Rop iden | ( Expr )

Expr^ ® Expr ∧

Expr∨® Expr ∨ (5.7)

n將文法進行“拆分”的目的:

1.在翻譯完運算符∧(∨)左側的表達式後,能夠及時獲取其語義屬性TC及FC

2.完成用下一四元式序號(即運算符右側表達式的第一四元式之序號)回填前一表達式的相應真(假)鏈TC(FC),

3.將其另一鏈FC(TC)作為產生式左部符號的綜合屬性FC(TC)傳播之。

語義函式

1.NXQ—全局變數,用於指示所要產生的下一四元式的序號;

2.GEN(…)—其意義同前,每次調用,NXQ++;

3. int Merge(int p1,int p2)—將鏈首“指針”分別為p1和p2的兩條鏈合併為一條,並返回新鏈的鏈首“指針”(此處的“指針”實際上是四元式的序號,應為整型值)我們假定四元式是以一結構形式表示(存儲)的:

struct _Quadruple{

int Op, arg1, arg2, Result;

} QuadrupleList[];

4.void BackPatch(int p,int t)—用四元式序號t回填以p為首的鏈,將鏈中每個四元式的Result域改寫為t的值。

函式Merge( )及BackPatch( )的程式見書

屬性文法

1.Expr→iden { $$.TC= NXQ; $$.FC= NXQ+1; GEN(jnz, Entry($1), 0, 0); GEN(j,0,0,0); }

| iden rop iden { $$.TC= NXQ; $$.FC= NXQ+1;

GEN(jrop, Entry($1), Entry($3), 0);

GEN(j, 0, 0, 0); }

| ‘(’ Expr ‘)’ { $$.TC= $2 . TC; $$.FC= $2.FC; }

| ‘﹃’ Expr { $$.TC= $2.FC; $$.FC= $2 . TC; }

| Expr^ Expr

{ $$.TC= $2 . TC; $$.FC=Merge($1.FC,$2.FC); }

| Expr∨ Expr

{ $$.FC= $2.FC; $$.TC=Merge($ 1 . TC,$2 . TC); }

| Expr^→ Expr ‘∧’

{ BackPatch($ 1 . TC,NXQ); $$.FC= $1.FC; }

| Expr∨→ Expr ‘∨’

{BackPatch($1.FC,NXQ); $$.TC= $ 1 . TC; }

例子

將布爾代數<{0, a, b,1},∧,∨, ',0,1>上的布爾表達式 f( x, x) = (( a∧ x)∧( x∨ x'))∨( b∧ x∧ x)化為主析取範式和主合取範式。

解  f( x, x) = (( a∧ x)∧( x∨ x'))∨( b∧ x∧ x)

= ( a∧( x∧( x∨ x')))∨( b∧ x∧ x)

= ( a∧ x)∨( b∧ x∧ x)

= ( a∧ x∧( x∨ x'))∨( b∧ x∧ x)

= ( a∧ x∧ x)∨( a∧ x∧ x')∨( b∧ x∧ x)

= ( a∧ x∧ x')∨(( a∨ b)∧ x∧ x)

= ( a∧ x∧ x')∨( x∧ x)

= ( a∧ m)∨ m。(主析取範式)

f( x, x) = (( a∧ x)∧( x∨ x'))∨( b∧ x∧ x)

= ( a∧( x∧( x∨ x')))∨( b∧ x∧ x)

= ( a∧ x)∨( b∧ x∧ x)

= ( a∨( b∧ x∧ x))∧( x∨( b∧ x∧ x))

= ( a∨ b)∧( a∨ x)∧( a∨ x)∧ x

= x∧( a∨ x)

= ( x∨( x∧ x'))∧( a∨( x∧ x')∨ x)

= ( x∨ x)∧( x∨ x')∧( a∨ x∨ x)∧( a∨ x'∨ x)

= ( x∨ x)∧( x∨ x')∧( a∨ x'∨ x)

= M∧ M∧( a∨ M)。(主合取範式)

相關搜尋

熱門詞條

聯絡我們