布爾表達(dá)式的翻譯ppt課件

1、Chapter 5.5 布爾表達(dá)式的翻譯1. 概述2. 布爾表達(dá)式的語義及作用n布爾表達(dá)式的語義在于指明計(jì)算一個(gè)邏輯值的規(guī)那么布爾表達(dá)式的語義在于指明計(jì)算一個(gè)邏輯值的規(guī)那么 .n布爾表達(dá)式在程序設(shè)計(jì)言語中有兩個(gè)根本的作用：布爾表達(dá)式在程序設(shè)計(jì)言語中有兩個(gè)根本的作用：n一是在某些控制語句中作為實(shí)現(xiàn)控制轉(zhuǎn)移的條件；一是在某些控制語句中作為實(shí)現(xiàn)控制轉(zhuǎn)移的條件；n另一個(gè)那么是用于計(jì)算邏輯值本身。另一個(gè)那么是用于計(jì)算邏輯值本身。n商定商定:各類運(yùn)算符的優(yōu)先順序由高至低如下：各類運(yùn)算符的優(yōu)先順序由高至低如下：n括號(hào)括號(hào)n算術(shù)運(yùn)算符算術(shù)運(yùn)算符*、/n +、-n關(guān)系運(yùn)算符關(guān)系運(yùn)算符、=、n邏輯運(yùn)算符邏輯運(yùn)算符

2、n n 3. 布爾表達(dá)式的等價(jià)解釋-求值角度3. 布爾表達(dá)式的等價(jià)解釋-過程角度4. 布爾表達(dá)式的出口5. 控制語句中的布爾表達(dá)式if E then S1 else S2或while E do STE的代碼S1的代碼S2的代碼E的代碼S的代碼TFF6. 布爾表達(dá)式真假值確實(shí)定一個(gè)布爾表達(dá)式E的真假值確實(shí)定，是在語法翻譯過程中，根據(jù)(5.2)-(5.4)等價(jià)解釋式逐漸進(jìn)展的。 例如，對于布爾表達(dá)式E = E(1) E(2)假設(shè)E(1)為真，那么E必為真，故E(1)的真出口必是E的真出口(之一);假設(shè)E(1)為假，那么E的真假值取決于E(2)的真假值，此時(shí)，需對E(2)進(jìn)展計(jì)算，由此可見，E(1)

3、的假出口應(yīng)為E(2)對應(yīng)的四元式的序號(hào)(E(2)的入口)，同時(shí),E(2)的真、假出口也是E的真、假出口。類似地，可確定E(1) E(2) 、E及更復(fù)雜的表達(dá)式的真、假出口。 7. 條件語句的翻譯結(jié)果在設(shè)計(jì)布爾表達(dá)式翻譯算法即編寫語義動(dòng)作時(shí)，可定義和運(yùn)用如下三類四元式：(jnz, A1, ,p)當(dāng)A1為真(非零)時(shí)，轉(zhuǎn)向第p四元式；(jrop,A1,A2,p)當(dāng)關(guān)系A(chǔ)1 rop A2 成立時(shí)，轉(zhuǎn)向第p四元式；(j, , ,p) 無條件轉(zhuǎn)向第p四元式例如，對于條件語句if ABC then S1 else S2經(jīng)翻譯后，可得四元式序列： (1) (jnz, A, -, 5)(2) (j, - ,-

4、 , 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á)式BC的第一四元式；BC的真、假出口也分別是整個(gè)表達(dá)式的真、假出口。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的真出口確切位置并不知道，

5、故此時(shí)只能產(chǎn)生一個(gè)空缺轉(zhuǎn)移目的的四元式(jnz,A,-,0),并將此四元式的序號(hào)(即1)作為語義信息存起來，待開場翻譯S1時(shí)，再將S1的第一四元式的序號(hào)(即5)回填這個(gè)不完全的四元式。另外，在翻譯過程中，經(jīng)常會(huì)出現(xiàn)假設(shè)干轉(zhuǎn)移四元式轉(zhuǎn)向同一目的，但此目的的詳細(xì)位置又尚未確定的情況，此時(shí)我們可將這些四元式用拉鏈的方法將它們鏈接起來，用一指針指向鏈頭，在確定了目的四元式的位置之后，再回填這個(gè)鏈。n對于一個(gè)布爾表達(dá)式E來說，它應(yīng)有兩條鏈：真出口鏈(稱為T鏈，記作TC)和假出口鏈(稱為F鏈，記作FC)。它們就是非終結(jié)符Expr的兩個(gè)屬性Expr.TC及Expr.FC。n例如，對于上述if語句中的布爾式E

6、=AB0時(shí),它給出本鏈的后繼四元式的序號(hào)， Result =0時(shí)表示本四元式是鏈尾結(jié)點(diǎn)。(1)(jnz,A,-,0)( 2 )( j , - , - , 3 ) E.TC(3)(j,B,C,1) E.FC (4)(j, -,-,0) 9. 文法的“拆分n為便于實(shí)現(xiàn)布爾表達(dá)式的語法制導(dǎo)翻譯，我們先改寫文法，以便能在翻譯過程中的適當(dāng)時(shí)機(jī)獲得所需的語義屬性值。例如，可將文法(5.1)改寫為：nExprExpr Expr | Expr Expr | Expr|niden |iden Rop iden | ( Expr )nExpr Expr nExpr Expr (5.7)n 將文法進(jìn)展“拆分的目的:

7、n1.在翻譯完運(yùn)算符左側(cè)的表達(dá)式后，可以及時(shí)獲取其語義屬性TC及FCn2.完成用下一四元式序號(hào)即運(yùn)算符右側(cè)表達(dá)式的第一四元式之序號(hào)回填前一表達(dá)式的相應(yīng)真假鏈TCFC，n3.將其另一鏈FCTC作為產(chǎn)生式左部符號(hào)的綜合屬性FCTC傳播之。10. 語義變量及輔助語義函數(shù)1.NXQ全局變量，用于指示所要產(chǎn)生的下一四元式的序號(hào)；2.GEN其意義同前,每次調(diào)用,NXQ+；3.int Merge(int p1,int p2)將鏈?zhǔn)住爸羔樂謩e為p1和p2的兩條鏈合并為一條，并前往新鏈的鏈?zhǔn)住爸羔槾颂幍摹爸羔槍?shí)踐上是四元式的序號(hào)，應(yīng)為整型值我們假定四元式是以一構(gòu)造方式表示存儲(chǔ)的：struct _Quadrupl

8、e int Op, arg1, arg2, Result; QuadrupleList; 4.void BackPatch(int p,int t)用四元式序號(hào)t回填以p為首的鏈，將鏈中每個(gè)四元式的Result域改寫為t的值。函數(shù)Merge( )及BackPatch( )的程序見書11. 翻譯布爾表達(dá)式的屬性文法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= $2.TC; $.FC=Merge($1.FC,$2.FC); | Expr Ex