介紹
布爾表達式（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)。（主合取範式）
