布爾表達(dá)式的翻譯第一頁，共十七頁，編輯于2023年，星期日1.概述布爾表達(dá)式是布爾運(yùn)算量和邏輯運(yùn)算符按一定語法規(guī)則組成的式子。邏輯運(yùn)算符通常有∧、∨、﹃三種（在某些語言中，還有≡（等價(jià)）及→（蘊(yùn)含）等等）；邏輯運(yùn)算對象可以是邏輯值（True

或False）、布爾變量、關(guān)系表達(dá)式以及由括號括起來的布爾表達(dá)式。不論是布爾變量還是布爾表達(dá)式，都只能取邏輯值True或False。在計(jì)算機(jī)內(nèi)通常用1（或非零整數(shù)）表示真值（True），用0表示假值(False)。第二頁，共十七頁，編輯于2023年，星期日關(guān)系表達(dá)式是形如E1

RopE2的式子，其中E1和E2為簡單算術(shù)表達(dá)式，Rop為關(guān)系運(yùn)算符（<,>,=,<=,>=,<>）。若E1和E2之值使該關(guān)系式成立，則此關(guān)系表達(dá)式之值為True，否則為False。第三頁，共十七頁，編輯于2023年，星期日2.布爾表達(dá)式的語義及作用布爾表達(dá)式的語義在于指明計(jì)算一個(gè)邏輯值的規(guī)則.布爾表達(dá)式在程序設(shè)計(jì)語言中有兩個(gè)基本的作用：一是在某些控制語句中作為實(shí)現(xiàn)控制轉(zhuǎn)移的條件；另一個(gè)則是用于計(jì)算邏輯值本身。約定:各類運(yùn)算符的優(yōu)先順序（由高至低）如下：⒈括號⒉算術(shù)運(yùn)算符 *、/ +、-⒊關(guān)系運(yùn)算符

<、<=、=、>、>=、<>⒋邏輯運(yùn)算符 ┒ ∧ ∨第四頁，共十七頁，編輯于2023年，星期日3.布爾表達(dá)式的等價(jià)解釋-求值角度為了方便起見，下面我們僅討論由文法E→E∧E|E∨E|┑E|(E)|I|iRopi(5.1)1）可采用類似算術(shù)表達(dá)式的方式來進(jìn)行。例如，對于布爾表達(dá)式A∨B∧C，可翻譯為：

(∧, B, C, T1) (∨, A, T1, T2)第五頁，共十七頁，編輯于2023年，星期日3.布爾表達(dá)式的等價(jià)解釋-過程角度但是，對于一個(gè)布爾表達(dá)式而言，我們的目的僅僅是為了判定它的真假值。因此，有時(shí)只需計(jì)算它的一個(gè)子表達(dá)式，便能確定整個(gè)布爾表達(dá)式的真假值。例如，對于A∨B，只要知道A為真，則無論B取何值，表達(dá)式的結(jié)果一定為真。可見，對于三種常見邏輯運(yùn)算，可作如下等價(jià)的解釋：

A∧B (A)?B:0 (5.2) A∨B (A)?1:B (5.3) ﹃A (A)?0:1 (5.4)第六頁，共十七頁，編輯于2023年，星期日4.布爾表達(dá)式的出口對于布爾表達(dá)式A∨（B∧（┑C∨D）)，其等價(jià)的表述是

A？1：（B？（（C？0：1）？1：D）：0

）顯然，采用此種結(jié)構(gòu)可產(chǎn)生更為有效的中間代碼。這里需假定原布爾表達(dá)式的計(jì)算過程中不含有任何的副作用。在上式的計(jì)算中，根據(jù)A、B、C、D的取值不同，計(jì)算的結(jié)果以及運(yùn)算的終止點(diǎn)亦不同。例如，當(dāng)A=1（真）時(shí)，結(jié)果為1且終止于左邊第一個(gè)‘1’處。這樣終止的點(diǎn)我們稱為該布爾表達(dá)式的出口，同時(shí)，把使布爾表達(dá)式取值為真的出口稱為真出口，反之稱為假出口。對一個(gè)布爾表達(dá)式而言，它至少有一個(gè)真出口和一個(gè)假出口（當(dāng)然可以有多個(gè)）。在用于控制流程的布爾表達(dá)式E的計(jì)算中，這些出口分別指出當(dāng)E值為真和假時(shí)，控制所應(yīng)轉(zhuǎn)向的目標(biāo)（即某一四元式的序號）。第七頁，共十七頁，編輯于2023年，星期日5.控制語句中的布爾表達(dá)式if

E

then

S1

else

S2或while

E

do

STE的代碼S1的代碼S2的代碼E的代碼S的代碼TFF(a)if語句(b)while語句第八頁，共十七頁，編輯于2023年，星期日6.布爾表達(dá)式真假值的確定一個(gè)布爾表達(dá)式E的真假值的確定，是在語法翻譯過程中，根據(jù)(5.2)-(5.4)等價(jià)解釋式逐步進(jìn)行的。例如，對于布爾表達(dá)式 E=E(1)∨E(2)

若E(1)為真，則E必為真，故E(1)的真出口必是E的真出口(之一);

若E(1)為假，則E的真假值取決于E(2)的真假值，此時(shí)，需對E(2)進(jìn)行計(jì)算，由此可見，E(1)的假出口應(yīng)為E(2)對應(yīng)的四元式的序號(E(2)的入口)，同時(shí),E(2)的真、假出口也是E的真、假出口。 類似地，可確定E(1)∧

E(2)

、﹃E及更復(fù)雜的表達(dá)式的真、假出口。

第九頁，共十七頁，編輯于2023年，星期日7.條件語句的翻譯結(jié)果在設(shè)計(jì)布爾表達(dá)式翻譯算法（即編寫語義動作）時(shí)，可定義和使用如下三類四元式：(jnz,A1,,p)當(dāng)A1為真(非零)時(shí)，轉(zhuǎn)向第p四元式；(jrop,A1,A2,p)當(dāng)關(guān)系A(chǔ)1ropA2

成立時(shí)，轉(zhuǎn)向第p四元式；(j,,,p)

無條件轉(zhuǎn)向第p四元式第十頁，共十七頁，編輯于2023年，星期日例如，對于條件語句ifA∨B<C

then

S1

else

S2經(jīng)翻譯后，可得四元式序列：

(1) (jnz,A,-,5) (2) (j,-,-,3) (3) (j<,B,C,5) (4) (j,-,-,p+1) (5) S1相應(yīng)的四元式序列

(p) (j,-,-,q) (p+1)S2相應(yīng)的四元式序列

(q) …

其中，表達(dá)式A的真出口為5（也是整個(gè)表達(dá)式的真出口），假出口為3（即表達(dá)式B<C的第一四元式）；B<C的真、假出口也分別是整個(gè)表達(dá)式的真、假出口。第十一頁，共十七頁，編輯于2023年，星期日8.拉鏈與回填在自底向上的語法制導(dǎo)翻譯時(shí)（或者說，在S-屬性翻譯文法中),在產(chǎn)生一個(gè)(無)條件轉(zhuǎn)移四元式時(shí),它所要轉(zhuǎn)向的那個(gè)四元式有時(shí)尚未產(chǎn)生，故無法立即產(chǎn)生一個(gè)完全的控制轉(zhuǎn)移四元式。例如，在上例中，在產(chǎn)生第一個(gè)四元式時(shí)，由于語句S1的中間代碼尚未產(chǎn)生，即A的真出口確切位置并不知道，故此時(shí)只能產(chǎn)生一個(gè)空缺轉(zhuǎn)移目標(biāo)的四元式 (jnz,A,-,0),并將此四元式的序號(即1)作為語義信息存起來，待開始翻譯S1時(shí)，再將S1的第一四元式的序號(即5)回填這個(gè)不完全的四元式。 另外，在翻譯過程中，常常會出現(xiàn)若干轉(zhuǎn)移四元式轉(zhuǎn)向同一目標(biāo)，但此目標(biāo)的具體位置又尚未確定的情況，此時(shí)我們可將這些四元式用拉鏈的辦法將它們鏈接起來，用一指針指向鏈頭，在確定了目標(biāo)四元式的位置之后，再回填這個(gè)鏈。第十二頁，共十七頁，編輯于2023年，星期日對于一個(gè)布爾表達(dá)式E來說，它應(yīng)有兩條鏈：真出口鏈(稱為T鏈，記作TC)和假出口鏈(稱為F鏈，記作FC)。它們就是非終結(jié)符Expr的兩個(gè)屬性Expr.TC及Expr.FC。例如，對于上述if語句中的布爾式E=A∨B<C，在翻譯過程中形成的T鏈和F鏈如右圖所示。其中，每條鏈都是利用四元式中的Result域連接的，Result>0時(shí),它給出本鏈的后繼四元式的序號，Result=0時(shí)表示本四元式是鏈尾結(jié)點(diǎn)。第十三頁，共十七頁，編輯于2023年，星期日(1) (jnz,A,-,0)(2) (j,-,-,3)

E.TC→(3)(j<,B,C,1)E.FC→

(4)(j,-,-,0)

A∧B∨C的四元式序列及其TC鏈和FC鏈第十四頁，共十七頁，編輯于2023年，星期日9.文法的“拆分”為便于實(shí)現(xiàn)布爾表達(dá)式的語法制導(dǎo)翻譯，我們先改寫文法，以便能在翻譯過程中的適當(dāng)時(shí)機(jī)獲得所需的語義屬性值。例如，可將文法(5.1)改寫為：ExprExpr^Expr|Expr∨Expr|﹃Expr| iden|idenRopiden|(Expr) Expr^Expr∧ Expr∨Expr∨

(5.7)

將文法進(jìn)行“拆分”的目的:1.在翻譯完運(yùn)算符∧（∨）左側(cè)的表達(dá)式后，能夠及時(shí)獲取其語義屬性TC及FC2.完成用下一四元式序號（即運(yùn)算符右側(cè)表達(dá)式的第一四元式之序號）回填前一表達(dá)式的相應(yīng)真（假）鏈TC（FC），3.將其另一鏈FC（TC）作為產(chǎn)生式左部符號的綜合屬性FC（TC）傳播之。第十五頁，共十七頁，編輯于2023年，星期日10.語義變量及輔助語義函數(shù)1.NXQ全局變量，用于指示所要產(chǎn)生的下一四元式的序號；2.GEN（…）其意義同前,每次調(diào)用,NXQ++；3.int

Merge(int

p1,int

p2)將鏈?zhǔn)住爸羔槨狈謩e為p1和p2的兩條鏈合并為一條，并返回新鏈的鏈?zhǔn)住爸羔槨保ù颂幍摹爸羔槨睂?shí)際上是四元式的序號，應(yīng)為整型值）我們假定四元式是以一結(jié)構(gòu)形式表示（存儲）的：

struct

_Quadruple{

int

Op,arg1,arg2,Result; }QuadrupleList[];4.void

BackPatch(int

p,int

t)用四元式序號t回填以p為首的鏈，將鏈中每個(gè)四元式的Result域改寫為t的值。函數(shù)Merge()及BackPatch()的程序見書第十六頁，共十七頁，編輯于2023年，星期日11.翻譯布爾表達(dá)式的屬性文法1.Expr→iden{$$.TC=NXQ;$$.FC=NXQ+1; GEN(jnz,Entry($1),0,0);GEN(j,0,0,0);}|idenropiden{$$.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);