布爾表達式

從最基本的層次來説，所有的布爾表達式，不論它的長短如何，其值只能是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值為真和假時，控制所應轉向的目標（即某一四元式的序號）。 ^[1] 

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及更復雜的表達式的真、假出口。 ^[2] 

在設計布爾表達式翻譯算法（即編寫語義動作）時，可定義和使用如下三類四元式：

(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的真、假出口也分別是整個表達式的真、假出口 ^[3]  。

在自底向上的語法制導翻譯時（或者説，在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）傳播之。 ^[4] 

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₂)。（主合取範式）