布爾表達式

布爾表達式

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

基本介紹

  • 中文名:布爾表達式
  • 外文名:Boolean expression
  • 類別:一段代碼聲明
  • 特點:最終只有真和假兩個取值
介紹,概述,作用,過程角度,出口,表達式,確定,譯結果,拉鏈回填,拆分,語義函式,屬性文法,例子,

介紹

從最基本的層次來說,所有的布爾表達式,不論它的長短如何,其值只能是true或false。
布爾表達式(Boolean expression)布爾表達式(Boolean expression)
最簡單的布爾表達式是等式(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&reg;Expr^ Expr | Expr∨ Expr | ﹃ Expr|
iden |iden Rop iden | ( Expr )
Expr^ &reg; Expr ∧
Expr∨&reg; 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(x1,x2) = ((ax1)∧(x1x'2))∨(bx1x2)化為主析取範式和主合取範式。
解 f(x1,x2) = ((ax1)∧(x1x'2))∨(bx1x2)
= (a∧(x1∧(x1x'2)))∨(bx1x2)
= (ax1)∨(bx1x2)
= (ax1∧(x2x'2))∨(bx1x2)
= (ax1x2)∨(ax1x'2)∨(bx1x2)
= (ax1x'2)∨((ab)∧x1x2)
= (ax1x'2)∨(x1x2)
= (am2)∨m3。(主析取範式)
f(x1,x2) = ((ax1)∧(x1x'2))∨(bx1x2)
= (a∧(x1∧(x1x'2)))∨(bx1x2)
= (ax1)∨(bx1x2)
= (a∨(bx1x2))∧(x1∨(bx1x2))
= (ab)∧(ax1)∧(ax2)∧x1
=x1∧(ax2)
= (x1∨(x2x'2))∧(a∨(x1x'1)∨x2)
= (x1x2)∧(x1x'2)∧(ax1x2)∧(ax'1x2)
= (x1x2)∧(x1x'2)∧(ax'1x2)
=M0M1∧(aM2)。(主合取範式)

相關詞條

熱門詞條

聯絡我們