1、Chapter 5.5 布爾表達式的翻譯,1. 概述,布爾表達式是布爾運算量和邏輯運算符按一定語法規(guī)則組成的式子。 邏輯運算符通常有、三種（在某些語言中，還有（等價）及（蘊含）等等）； 邏輯運算對象可以是邏輯值（True 或 False）、布爾變量、關系表達式以及由括號括起來的布爾表達式。 不論是布爾變量還是布爾表達式，都只能取邏輯值True或False。在計算機內通常用1（或非零整數(shù)）表示真值（True），用0表示假值(False)。,關系表達式是形如E1 Rop E2的式子，其中E1和E2為簡單算術表達式，Rop為關系運算符（, =, =, ）。若E1和E2之值使該關系式成立，則此關系表達

2、式之值為True，否則為False。,2. 布爾表達式的語義及作用,布爾表達式的語義在于指明計算一個邏輯值的規(guī)則 . 布爾表達式在程序設計語言中有兩個基本的作用： 一是在某些控制語句中作為實現(xiàn)控制轉移的條件； 另一個則是用于計算邏輯值本身。 約定:各類運算符的優(yōu)先順序（由高至低）如下： 括號 算術運算符*、/ +、- 關系運算符、=、 邏輯運算符 ,3. 布爾表達式的等價解釋-求值角度,為了方便起見，下面我們僅討論由文法 E EE | EE | E | (E) | I | i Rop i (5.1) 1）可采用類似算術表達式的方式來進行。例如，對于布爾表達式ABC，可翻譯為： (,B,C,T1

3、 ) (,A,T1,T2 ),3. 布爾表達式的等價解釋-過程角度,但是，對于一個布爾表達式而言，我們的目的僅僅是為了判定它的真假值。因此，有時只需計算它的一個子表達式，便能確定整個布爾表達式的真假值。例如，對于AB，只要知道A為真，則無論B取何值，表達式的結果一定為真。 可見，對于三種常見邏輯運算，可作如下等價的解釋： AB(A) ? B : 0(5.2) AB(A) ? 1 : B(5.3) A (A) ? 0 : 1(5.4),4. 布爾表達式的出口,對于布爾表達式A（B（CD）)，其等價的表述是 A ？ 1 ：（B ？（C ？ 0 ：1）？ 1 ： D ）： 0 ） 顯然，采用此種結構

4、可產生更為有效的中間代碼。這里需假定原布爾表達式的計算過程中不含有任何的副作用。 在上式的計算中，根據(jù)A、B、C、D的取值不同，計算的結果以及運算的終止點亦不同。例如，當A=1（真）時，結果為1且終止于左邊第一個1處。 這樣終止的點我們稱為該布爾表達式的出口，同時，把使布爾表達式取值為真的出口稱為真出口，反之稱為假出口。 對一個布爾表達式而言，它至少有一個真出口和一個假出口（當然可以有多個）。在用于控制流程的布爾表達式E的計算中，這些出口分別指出當E值為真和假時，控制所應轉向的目標（即某一四元式的序號）。,5. 控制語句中的布爾表達式,if E then S1 else S2或while E

5、do S,6. 布爾表達式真假值的確定,一個布爾表達式E的真假值的確定，是在語法翻譯過程中，根據(jù)(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及更復雜的表達式的真、假出口。,7. 條件語句的翻譯結果,在設計布爾表達式翻譯算法（即編寫語義動

6、作）時，可定義和使用如下三類四元式： (jnz, A1, ,p)當A1為真(非零)時，轉向第p四元式； (jrop,A1,A2,p)當關系A1 rop A2 成立時，轉向第p四元式； (j, , ,p) 無條件轉向第p四元式,例如，對于條件語句 if ABC 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（

7、也是整個表達式的真出口），假出口為3（即表達式BC的第一四元式）；BC的真、假出口也分別是整個表達式的真、假出口。,8. 拉鏈與回填,在自底向上的語法制導翻譯時（或者說，在S-屬性翻譯文法中), 在產生一個(無)條件轉移四元式時, 它所要轉向的那個四元式有時尚未產生，故無法立即產生一個完全的控制轉移四元式。 例如，在上例中，在產生第一個四元式時，由于語句S1的中間代碼尚未產生，即A的真出口確切位置并不知道，故此時只能產生一個空缺轉移目標的四元式(jnz,A,-,0), 并將此四元式的序號(即1)作為語義信息存起來，待開始翻譯S1時，再將S1的第一四元式的序號(即5)回填這個不完全的四元式。 另

8、外，在翻譯過程中，常常會出現(xiàn)若干轉移四元式轉向同一目標，但此目標的具體位置又尚未確定的情況，此時我們可將這些四元式用拉鏈的辦法將它們鏈接起來，用一指針指向鏈頭，在確定了目標四元式的位置之后，再回填這個鏈。,對于一個布爾表達式E來說，它應有兩條鏈：真出口鏈(稱為T鏈，記作TC)和假出口鏈(稱為F鏈，記作FC)。它們就是非終結符Expr的兩個屬性Expr.TC及Expr.FC。 例如，對于上述if語句中的布爾式E=AB0時,它給出本鏈的后繼四元式的序號， Result =0時表示本四元式是鏈尾結點。,(1)(jnz,A,-,0) (2)(j,-,-,3) E.TC(3)(j,B,C,1) E.FC

9、 (4)(j, -,-,0),ABC的四元式序列及其TC鏈和FC鏈,9. 文法的“拆分”,為便于實現(xiàn)布爾表達式的語法制導翻譯，我們先改寫文法，以便能在翻譯過程中的適當時機獲得所需的語義屬性值。例如，可將文法(5.1)改寫為： ExprExpr Expr | Expr Expr | Expr| iden |iden Rop iden | ( Expr ) Expr Expr Expr Expr (5.7) 將文法進行“拆分”的目的: 1.在翻譯完運算符（）左側的表達式后，能夠及時獲取其語義屬性TC及FC 2.完成用下一四元式序號（即運算符右側表達式的第一四元式之序號）回填前一表達式的相應真（假）

10、鏈TC（FC）， 3.將其另一鏈FC（TC）作為產生式左部符號的綜合屬性FC（TC）傳播之。,10. 語義變量及輔助語義函數(shù),1.NXQ全局變量，用于指示所要產生的下一四元式的序號； 2.GEN（）其意義同前,每次調用,NXQ+； 3.int Merge(int p1,int p2)將鏈首“指針”分別為p1和p2的兩條鏈合并為一條，并返回新鏈的鏈首“指針”（此處的“指針”實際上是四元式的序號，應為整型值）我們假定四元式是以一結構形式表示（存儲）的： struct _Quadruple int Op, arg1, arg2, Result; QuadrupleList; 4.void BackP

11、atch(int p,int t)用四元式序號t回填以p為首的鏈，將鏈中每個四元式的Result域改寫為t的值。 函數(shù)Merge( )及BackPatch( )的程序見書,11. 翻譯布爾表達式的屬性文法,1.Expriden $.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= $