布爾表達式

從最基本的層次來說，所有的布爾表達式，不論它的長短如何，其值只能是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|iRop 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

經翻譯后，可得四元式序列：

(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

拉鏈回填

---

布爾表達式

在自底向上的語法制導翻譯時（或者說，在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

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,intt)—用四元式序號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) = ((a∧x1)∧(x1∨x'2))∨(b∧x1∧x2)化為主析取範式和主合取範式。

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

= (a∧(x1∧(x1∨x'2)))∨(b∧x1∧x2)

= (a∧x1)∨(b∧x1∧x2)

= (a∧x1∧(x2∨x'2))∨(b∧x1∧x2)

= (a∧x1∧x2)∨(a∧x1∧x'2)∨(b∧x1∧x2)

= (a∧x1∧x'2)∨((a∨b)∧x1∧x2)

= (a∧x1∧x'2)∨(x1∧x2)

= (a∧m2)∨m3。（主析取範式）

f(x1,x2) = ((a∧x1)∧(x1∨x'2))∨(b∧x1∧x2)

= (a∧(x1∧(x1∨x'2)))∨(b∧x1∧x2)

= (a∧x1)∨(b∧x1∧x2)

= (a∨(b∧x1∧x2))∧(x1∨(b∧x1∧x2))

= (a∨b)∧(a∨x1)∧(a∨x2)∧x1

=x1∧(a∨x2)

= (x1∨(x2∧x'2))∧(a∨(x1∧x'1)∨x2)

= (x1∨x2)∧(x1∨x'2)∧(a∨x1∨x2)∧(a∨x'1∨x2)

= (x1∨x2)∧(x1∨x'2)∧(a∨x'1∨x2)

=M0∧M1∧(a∨M2)。（主合取範式）