第6章語法制導翻譯和中間代碼生成

1第6章語法制導翻譯和中間代碼生成6.1

語法制導翻譯概述6.2

符號表和常數(shù)表6.3

中間代碼6.4

說明語句（簡單變量）的翻譯6.5

整型算術表達式及賦值語句的翻譯6.6

混合型算術表達式及賦值語句的翻譯6.7

布爾表達式的翻譯6.8

標號和無條件轉移語句的翻譯6.9

控制語句的翻譯

if-then

if-then-else

while-do

復合語句6.10

小結2㈠語法分析和語義分析的區(qū)別①語法分析利用產(chǎn)生式推導或歸約，驗證符號串是否為文法的一個句子，并沒有考慮符號和符號串的意義。②語義分析規(guī)定每個符號和符號串的意義，同時完成符號串所規(guī)定的語義動作，顯然這是以語法正確為前提。例文法G E→E(1)+T|T T→T(1)*F|F F→(E)|i|x|yi：語法分析認為i是一個終結符，代表標識符；而語義分析認為它不僅是一個標識符，還具有標識符名、種屬和類型等。i可能是一個簡單變量，也可能是一個標號。標識符名由單詞二元式中的值給出，種屬和類型可從符號表獲取。x：語法分析認為它是一個終結符，代表整常數(shù)；而語義分析認為它不僅是一個整常數(shù)，還具有值，值由單詞二元式中的值給出。3y：語法分析認為y是一個終結符,代表實常數(shù)；而語義分析認為它不僅是一個實常數(shù)，還具有值，值由單詞二元式中的值給出。F：語法分析認為F是一個非終結符，代表語法單位<因子>，F(xiàn)由i、x、y或(E)歸約而得；而語義分析認為F還具有值、類型等屬性。為了保存值和類型，引入語義變量F.val、F.type。T：語法分析認為T是一個非終結符，代表語法單位<項>，由F或T*F歸約而得；而語義分析認為T還具有值、類型等屬性。為了保存值和類型，引入語義變量T.val、T.type。E：語法分析認為E是一個非終結符，代表語法單位<算術表達式>，由T或E+T歸約而得；而語義分析認為E還具有值、類型等屬性。為了保存值和類型，引入語義變量E.val、E.type。+：語法分析認為它是一個終結符，代表算術加；而語義分析認為它可能是一個實數(shù)加運算符，也可能是一個整數(shù)加運算符，視運算對象而定。*：語法分析認為它是一個終結符，代表算術乘；而語義分析認為它可能是一個實數(shù)乘運算符，也可能是一個整數(shù)乘運算符，視運算對象而定。4E→E(1)+T：在語法分析時認為它是一個<算術表達式>的產(chǎn)生式，而在語義分析時認為：應將E(1)的值（用E(1).val表示）加上T的值（用T.val表示），結果放在E.val中。若數(shù)據(jù)類型有實型和整型之分，在運算前還需檢查它們的類型。若類型不同，根據(jù)語言的語義規(guī)定，或者拒絕運算，或者將它們轉換成相同類型（例實型），然后再進行實數(shù)加運算。T→T(1)*F：在語法分析時認為它是一個<項>的產(chǎn)生式，而在語義分析時認為：應將T(1)的值（用T(1).val表示）乘上F的值（用F.val表示），結果放在T.val中。若數(shù)據(jù)類型有實型和整型之分，在運算前還需檢查它們的類型。若類型不同，根據(jù)語言的語義規(guī)定，或者拒絕運算，或者將它們轉換成相同類型（例實型），然后再進行實數(shù)乘運算。㈡語義分析主要工作①建立符號表和常數(shù)表。②診察和報告源程序中的語義錯誤。③根據(jù)語言的語義產(chǎn)生中間代碼（或機器指令），或直接解釋執(zhí)行。56.1語法制導翻譯概述㈠語法制導翻譯方法簡介為每一個產(chǎn)生式配一個語義子程序。在語法分析過程中，當一個產(chǎn)生式獲得匹配或用于歸約時，此產(chǎn)生式相應的語義子程序進入工作，完成既定的翻譯任務。㈡實現(xiàn)方法（以SLR分析器為例）

SLR分析器是由工作棧（狀態(tài)棧和符號棧）、分析表和總控程序三部分構成，只要適當修改工作棧和總控程序，就可將SLR分析器用于語義分析。①分析表不變②改造工作棧為了保存語義信息，在狀態(tài)棧、符號棧的基礎上增加單詞值（wval）棧和語義（semantic）棧。狀態(tài)棧（原有）符號棧（原有）單詞值棧（新增）語義棧（新增）6狀態(tài)棧（不變）符號棧（不變）增加單詞值棧（wval），用于保存單詞的值（字符串形式）。增加語義棧（semantic）

，用于記錄分析過程中需保留的語義值。例：值（semantic.val）、地址（semantic.addr）、種屬（semantic.cat）、類型（semantic.type）、……。經(jīng)改造后，工作棧如下所示：statesymbolwval.val.addr .cat.type …SmX……X.valX.addrX.catX.type……Sm-1Y……Y.valY.addrY.catY.type…………………………………………S0#"NUL"③修改總控程序在移進時，除移進狀態(tài)和單詞的種別外，還需移進單詞的值。在用某個產(chǎn)生式進行歸約時，除需執(zhí)行歸約動作外，還需調(diào)用相應語義子程序。7㈢解釋執(zhí)行例①文法及語義子程序0.S→E {cout<<E.val}1.E→E(1)+E(2) {E.val=E(1).val+E(2).val;}2.E→E(1)*E(2) {E.val=E(1).val*E(2).val;}3.E→(E(1)) {E.val=E(1).val;}E→x {E.val=atoi(t.val);}//atoi為C語言系統(tǒng)函數(shù)假定語義動作是緊接著歸約之后執(zhí)行，語義子程序改寫如下：0.S→E {cout<<semantic[top].val;}1.E→E(1)+E(2)

{semantic[top].val=semantic[top].val+semantic[top+2].val;}2.E→E(1)*E(2)

{semantic[top].val=semantic[top].val*semantic[top+2].val;}3.E→(E(1)) {semantic[top].val=semantic[top+1].val.val;}4.E→x {semantic[top].val=atoi(wval[top]);}struct{charcode;charval[20];}t;//存放單詞二元式

//常數(shù)7的單詞二元式為（x,"7"），t.code='x'，t.val="7"。8+*()x#E0s2s311s4s5Acc2s2s363r4r4r4r44s2s375s2s386s4s5s97r1s5r1r18r2r2r2r29r3r3r3r3③手工計算假設源程序為：7+9*5。經(jīng)詞法分析，單詞二元式序列為

(x,"7")(+,"NUL")(x,"9")(*,"NUL")(x,"5")(#,"NUL")分析過程如黑板所示（在語義棧中，“NUL”改用‘-’表示）：step

state棧

symbol棧

wval棧

.val棧

輸入串②SLR分析表0.S→E 1.E→E(1)+E(2)2.E→E(1)*E(2)3.E→(E(1)) 4.E→x 9

在編譯過程中，編譯程序需要不斷匯集和反復查證出現(xiàn)在源程序中各種符號名（標識符）和常數(shù)，以及符號名的屬性，這些信息通常記錄在符號表和常數(shù)表中。㈠符號表①符號表的結構例：整型簡單變量“a99”在符號表中的記錄6.2符號表和常數(shù)表內(nèi)存地址（2字節(jié)）符號名（5字節(jié)）種屬（4Bit）類型（4Bit）…………………………未分配a99\0\0簡單整型…………………………

內(nèi)存單元X

內(nèi)存單元Y符號表入口10②符號表的定義（略有修改）符號表由記錄構成，相當于一個結構數(shù)組，模型語言的符號表定義如下：

struct{ void*addr; //標號或變量的地址

charid[4]; //標識符名

charcat; //種屬（4個二進制位）

chartype; //類型（4個二進制位）

}sym_table[NS]; //NS表示符號表長度1）addr

存放內(nèi)存地址（2字節(jié)），地址標識范圍為0-65535。變量的值并不存放于符號表，而是存儲在內(nèi)存的另外一個區(qū)域中，通過該地址指示，addr的值是在地址分配時填入。addr為結構第一分量，結構的地址值（&sym_table[i]）和結構的第一分量地址值（&sym_table[i].addr）相等，結構地址通常稱為變量在符號表中的入口（簡稱“符號表入口”）。2）id存放標識符名，標識符最多可由4個字符構成（與書略有不同）。113）cat

用于記錄標識符的種屬（如簡單變量、標號、數(shù)組、函數(shù)、…），4個二進制位，暫用1位。

0：簡單變量

1：標號4）type

用于記錄標識符的類型（如整型、實型、布爾型、……），4個二進制位，暫用1位。 簡單變量：0表示整型，1表示實型。 標號：0表示標號未定義，1表示標號已定義。③引入符號表的意義可用符號名表示內(nèi)存地址（變量）和語句的地址（標號）。符號表的引入使得中間代碼生成（包括目標代碼生成）與機器的內(nèi)存地址無關。可在機器碼最終定位階段，甚至在程序運行過程中，對變量進行地址分配。在對變量進行內(nèi)存地址分配時，符號表是地址分配的依據(jù)。轉移語句的翻譯是借助符號表來完成的。12④符號表的使用1）說明語句每當識別出一個標識符，就在符號表中為該標識符建立一條記錄，并填入標識符名、種屬、類型等語義信息。若符號表中已有記錄，說明標識符被重定義，報錯。2）非說明語句每當識別出一個標識符，就根據(jù)標識符名去查符號表，并由此獲得該標識符在符號表的入口。若標識符名在符號表中不存在，分情況處理：變量：報錯。標號：在符號表中創(chuàng)建一個記錄，將標識符名等信息填入符號表。⑤符號表入口地址使用說明在中間代碼生成時，若操作數(shù)是變量，則應在操作數(shù)（operand）位置上填入該變量在符號表中的入口。根據(jù)中間代碼生成的目標代碼，是通過間址尋址方式對變量進行存?。?*operand）。借助間址尋址方式，使得中間代碼所使用的地址和實際存放數(shù)據(jù)的內(nèi)存地址相互獨立。13㈡常數(shù)表可設置一張常數(shù)表，同時記錄各種類型的常數(shù)；也可按類型設置多張常數(shù)表，按類型分表記錄。①常數(shù)表結構

unsignedshortconst_int_table[NI]; //NI表示整常數(shù)表長度

floatconst_real_table[NR]; //NR表示實常數(shù)表長度②常數(shù)表使用每當識別出一個常數(shù)，將字符串轉換成數(shù)值后查常數(shù)表：若無，將常數(shù)填入常數(shù)表，獲取表中地址。若常數(shù)在表中已存在，直接獲取常數(shù)在表中地址。③常數(shù)表地址使用說明在中間代碼生成時，若操作數(shù)是常數(shù)，則應在操作數(shù)(operand)位置上填入常數(shù)在常數(shù)表中的地址(&const_int_table[i]或&const_real_table[i])。目標代碼運行時，根據(jù)該地址（*operand）可獲得常數(shù)值，無需間址訪問。目標代碼生成器可根據(jù)地址范圍來區(qū)分是符號表地址還是常數(shù)表地址，從而使用不同的尋址方式。值12345常數(shù)表入口146.3中間代碼

常用的中間代碼有三元式和四元式，在本書以后討論中，中間代碼采用四元式形式。6.3.1三元式㈠格式

(i)（OP，ARG1，ARG2）①三元式相當于二地址指令,計算結果用三元式序號i表示。②ARG1、ARG2均為指示器（三元式的序號、常數(shù)表地址或符號表入口）。③若為一目運算，ARG2不使用。例表達式a+b*2可表示為：

⑴ * &b &2 //⑴代表子表達式b*2的計算結果

⑵

+ &a ⑴ //&b表示變量b在符號表中的入口

//&2表示整常數(shù)2在整常數(shù)表中的地址

15㈡優(yōu)點代碼生成無需引進臨時變量。㈢缺點調(diào)整困難。在中間代碼優(yōu)化中，常常需要調(diào)整運算順序、增減代碼，重新排列三元式。由于三元式通過指示器相聯(lián)系，調(diào)整相當困難，有時甚至是不可能的。例，設源程序為：

x=(a+b)*c; y=-d 它的三元式代碼為：⑴ + &a &b⑵ * ⑴ &c⑶ = &x ⑵⑷ - &d⑸ = &y ⑷

若將源程序中的二條語句互換，改為：

y=-d;x=(a+b)*c需修改三元式中一系列指示器，如下所示：⑴ - &d⑵ = &y ⑷⑴⑶ + &a &b⑷ * ⑴⑶ &c⑸ = &x ⑵⑷166.3.2四元式㈠格式

（OP，ARG1，ARG2，RESULT）①相當于三地址指令。②ARG1、ARG2及RESULT均為指示器，或者指向常數(shù)表，或者是符號表和臨時變量表的入口。③若為一目運算，ARG2不使用?？紤]輸入和處理方便，將ARG2標記為0（變量或常數(shù)的地址不可能是0）。例表達式a+b*2可表示為：

⑴* &b &2 &T1

⑵+ &a &T1 &T2說明：

T1是臨時變量，&T1表示T1在臨時變量表中的入口，同理&T2。17㈡優(yōu)點調(diào)整方便。例，設源程序為

x=(a+b)*c; y=-d 它的四元式代碼為⑴ + &a &b &T1 ⑵ * &T1 &c &T2⑶ = &T2 0 &x⑷ - &d 0 &T3⑸ = &T3 0 &y

若將源程序中的二條語句互換，改為

y=-d;x=(a+b)*c

它的四元式代碼只要簡單交換原二條語句相應的四元式即可，無需再作任何修改。⑴- &d 0 &T3 ⑵= &T3 0 &y ⑶+ &a &b &T1 ⑷* &T1 &c &T2⑸= &T2 0 &x18㈢缺點在生成中間代碼時引進大量臨時變量。㈣臨時變量的處理在形成四元式時，考慮代碼生成方便，不加限制地引進臨時變量Ti（i=1,2,……）。在代碼優(yōu)化和目標代碼生成階段，可將它們的數(shù)量壓縮到最低。關于臨時變量Ti有二種處理方法：①將Ti作為標識符存入符號表，通過符號表入口對它們進行引用。由于不加限制地引進臨時變量，在隨后進行的代碼優(yōu)化和目標代碼生成中，有部分臨時變量有可能被刪除，采用此方法不是最合適。②臨時變量用于記錄運算過程中的中間結果，必然是簡單變量，可另外設置臨時變量表（無需設置種屬一欄），將Ti存入臨時變量表，而不是存入符號表。在以后討論中，采用第二種方案。196.4 說明語句（簡單變量）的翻譯

說明語句用于定義變量，大多數(shù)高級語言都要求變量先定義后使用。說明語句的翻譯并不產(chǎn)生中間代碼，而是將變量的名字、種屬、類型等信息填入符號表。㈠文法及修改

<語句>→integer<標識符表> S→aV <語句>→real<標識符表> S→cV <標識符表>→<標識符表>,標識符

V→V,i <標識符表>→標識符

V→i用這個文法來制導翻譯存在一個問題，只有把所有標識符歸約成<標識符表>，才能把變量名、種屬、類型等信息填入符號表，需使用一個隊列來保存這些變量名。為了避免使用隊列，文法修改如下：

<語句>→<說明> S→V <說明>→<說明>,標識符

V→V,i <說明>→integer

標識符

V→ai <說明>→real

標識符

V→ci

用這個文法來制導翻譯，每當讀進一個標識符，就可把它的變量名及其性質(zhì)填入符號表，沒有必要集中起來成批處理。integera,b的語法結構為：ai,iSaVaV,iai,iai,i、aV,i、aV、Sintegera,b的語法結構為：ai,i

SVV,iai,iai,i、V,i、V、S20㈡語義子程序V→ai{ fill_sym_table(wval,0,0);//填寫符號表（標識符名，簡單變量，整型）

V.cat=0; //保存語義值（簡單變量）

V.type=0; //保存語義值（整型）

}V→ci{ fill_sym_table(wval,0,1);//填寫符號表（標識符名，簡單變量，整型）

V.cat=0; //保存語義值（簡單變量）

V.type=1; //保存語義值（實型）

}V→V(1),i{ fill_sym_table(wval,V(1).cat,V(1).type); //繼承V(1)的語義信息

V.cat=V(1).cat; V.type=V(1).type;}S→V{;} //暫且為空①語義變量.cat和.type

當ai歸約為V，ai的所蘊含的語義信息（整型、簡單變量）隨之消失。由于在一個說明語句中可定義多個變量，此時可使用語義變量V.cat和V.type保存語義信息。當將V(1),i歸約為V時，i將繼承V(1)的語義信息。21㈡語義子程序V→ai{ fill_sym_table(wval,0,0);//填寫符號表（標識符名，簡單變量，整型）

V.cat=0; //保存語義值（簡單變量）

V.type=0;} //保存語義值（整型） V→ci{ fill_sym_table(wval,0,1);//填寫符號表（標識符名，簡單變量，整型）

V.cat=0; //保存語義值（簡單變量）

V.type=1;} //保存語義值（實型） V→V(1),i{fill_sym_table(wval,V(1).cat,V(1).type); //繼承V(1)的語義信息

V.cat=V(1).cat; V.type=V(1).type;}S→V{;} //暫且為空②fill_sym_table函數(shù)

voidfill_sym_table(char*,int,int); //變量名，種屬，類型根據(jù)標識符的單詞值(變量名)查符號表。若無，則為其創(chuàng)建一個記錄，將變量名、種屬及類型等信息填入符號表；若已存在，說明變量名被重復定義，報錯。㈢手工計算設源程序說明語句為：intergera,b。經(jīng)詞法分析，源程序的單詞二元式序列為：(a,"NUL")(i,"a")(,,"NUL")(i,"b")(#,"NUL") 語法制導翻譯過程如黑板所示：

step

symbol棧

wval棧

.cat棧

.type棧

輸入串226.5 整型算術表達式及賦值語句的翻譯㈠文法<語句>→標識符=<整型算術表達式> S→i=X<整型算術表達式>→<整型算術表達式>+<項> X→X+Y<整型算術表達式>→<項> X→Y<項>→<項>*<因子> Y→Y*Z<項>→<因子> Y→Z<因子>→(<整型算術表達式>) Z→(X)<因子>→-<因子> Z→-Z<因子>→標識符

Z→i<因子>→無符號整常數(shù)

Z→x說明：在算法表達式文法中，用X取代E，用Y取代T，用Z取代F。E、T和F將用于布爾表達式23㈡語義子程序S→i=X {gen_code(=,X.addr,0,sym_entry(wval));}X→X(1)+Y {X.addr=get_tmpvar(0); gen_code(+,X(1).addr,Y.addr,X.addr);} X→Y {X.addr=Y.addr;} Y→Y(1)*Z {Y.addr=get_tmpvar(0); gen_code(*,Y(1).addr,Z.addr,Y.addr);} Y→Z {Y.addr=Z.addr;} Z→(X) {Z.addr=X.addr;} Z→-Z(1) {Z.addr=get_tmpvar(0); gen_code(-,Z(1).addr,0,Z.addr)} Z→i {Z.addr=sym_entry(wval);} Z→x {Z.addr=const_int_entry(atoi(wval));} gen_code函數(shù):根據(jù)4個參數(shù)產(chǎn)生四元式；sym_entry函數(shù):根據(jù)變量的符號名查表，返回它的符號表入口。get_tmpvar函數(shù):申請一個臨時變量(實或整)，返回它的地址。const_int_entry函數(shù):根據(jù)常數(shù)值查常數(shù)表，返回入口地址。本書P147-P14824①get_tmpvar函數(shù)

void*get_tmpvar(int);

每調(diào)用一次，可獲得一個新的臨時變量，并將該變量在臨時變量表中的入口作為返回值。臨時變量名依次為T1、T2、…。1）get_tmpvar(0)表示申請一個整型臨時變量（2字節(jié)）2）get_tmpvar(1)表示申請一個實型臨時變量（4字節(jié)）②sym_entry函數(shù)

void*sym_entry(char*);

根據(jù)單詞值（變量名）查符號表。若找到，則返回變量在符號表中的入口；若無，則返回0。③gen_code函數(shù)

voidgen_code(char*,void*,void*,void*);

根據(jù)參數(shù)產(chǎn)生四元式(OP,ARG1,ARG2,RESULT)，并填入四元式表，表的指示器加1，函數(shù)無返回值。初始時四元式表空，指示器指向表的第一個空白位置。在本書中，四元式的算符OP由一個或多個字符構成，例+，jmp、itr等，故OP用字符串表示。④const_int_entry(wval)函數(shù)

void*const_int_entry(unsignedshort);

根據(jù)無符號整常數(shù)的單詞值（atoi(wval)）查無符號整常數(shù)表。若找到，則返回它在表中的地址；若無，則在表中創(chuàng)建該常數(shù)的記錄，然后返回表中地址。25S→i=X {gen_code(=,X.addr,0,sym_entry(wval));} //產(chǎn)生四元式X→X(1)+Y {X.addr=get_tmpvar(0); //申請臨時變量(整型) gen_code(+,X(1).addr,Y.addr,X.addr);} //產(chǎn)生四元式X→Y {X.addr=Y.addr;} //傳遞語義值

Y→Y(1)*Z {Y.addr=get_tmpvar(0); //申請臨時變量(整型) gen_code(*,Y(1).addr,Z.addr,Y.addr);} //產(chǎn)生四元式Y→Z {Y.addr=Z.addr;} //傳遞語義值Z→(X) {Z.addr=X.addr;} //傳遞語義值Z→-Z(1) {Z.addr=get_tmpvar(0); //申請臨時變量(整型) gen_code(-,Z(1).addr,0,Z.addr)} //產(chǎn)生四元式Z→i {Z.addr=sym_entry(wval);} //wval表示單詞的值Z→x {Z.addr=const_int_entry(atoi(wval));}//atoi為C系統(tǒng)函數(shù)㈢手工計算設源程序為：a=-b*(c+2)。經(jīng)詞法分析，源程序的單詞二元式序列為：(i,"a")(=,"Nul")(-,"Nul")(i,"b")(*,"Nul")((,"Nul")(i,"c")(+,"Nul")(x,"2")(),"Nul")(#,"Nul")。語法制導翻譯過程如黑板所示：

step

symbol棧

wval棧

.addr棧

輸入串⑴（-,&b,0,&T1）⑵（+,&c,&2,&T2）⑶（*,&T1,&T2,&T3）⑷（=,&T3,0,&a）266.7 布爾表達式的翻譯㈠布爾表達式作用①控制語句的條件 ifx+y<10gotoL②計算邏輯值 d=x>y㈡程序設計語言的優(yōu)先級和結合性①標準Fortran語言（按表達式類別分級）第一級：算術表達式算術運算符優(yōu)先級依次為：

**,-（乘方/一元負）、*,/（乘/除）、+,-（加/減）第二級：關系表達式關系運算符不相鄰，優(yōu)先性略。

<（.LT.）、<=（.LE.）、>（.GT.）、>=（.GE.）、<>（.NE.）、=（.EQ.）第三級：邏輯表達式邏輯運算符優(yōu)先級依次為：～(.NOT.)、∧(.AND.)、∨(.OR)注：單目運算服從右結合，雙目運算服從左結合。27

例Fortran語言表達式((A+B).GT.(C+D)).AND.(E.EQ.F) ((A+B)>(C+D))∧(E=F) 等價于

A+B>C+D∧E=F②Pascal語言（共分4級，同級運算優(yōu)先性相同）第一級（一目運算符）：

NOT、-（一元負） 服從右結合第二級（乘法運算符）：

*、/、DIV、MOD、AND服從左結合第三級（加法運算符）：

+、-、OR 服從左結合第四級（關系運算符）：

<、<=、>、>=、<>、= 不相鄰例Pascal語言表達式((A+B)>(C+D))AND(E=F) ((A+B)>(C+D))∧(E=F) 等價于 (A+B>C+D)∧(E=F)③C語言（共分17級，同級運算優(yōu)先性相同）略28㈢描述布爾表達式文法以標準FORTRAN語言為基礎，適當化簡。

E→E∨E|E∧E|(E)|～E|XrX|X

X→X+X|X*X|(X)|-X|i|xE表示布爾表達式X表示算術表達式r是終結符，是關系運算符(＞、≥、＜、≤、＝、≠)的抽象。文法G是一個二義文法㈣布爾表達式計算方法①根據(jù)優(yōu)先性和結合性按步計算

例：1∨～0∧0∨0=1∨1∧0∨0

=………②優(yōu)化計算法

a∨b解釋為：ifathentureelse{計算b} a∧b解釋為：ifathen{計算b}elsefalse

～a解釋為：ifathenfalseelseture//～不計算㈤布爾表達式的第一種翻譯法（同算術表達式） 例：a∨b∧～c＞2 //a∨b∧～(c＞2)⑴（＞,&c,&2,&T1）⑵（～,&T1,0,&T2）⑶（∧,&b,&T2,&T3）⑷（∨,&a,&T3,&T4）29㈥布爾表達式的第二種翻譯法①概述

布爾表達式E的作用在于控制對語句S1和S2的選擇，它的值無須保留?？少x予布爾表達式E二個出口： 真出口：轉向語句S1代碼 假出口：轉向語句S2代碼布爾表達式E，可使用下述三種四元式進行翻譯：(jnz,&a,0,p) 若a為真（非0）轉移至四元式p，否則 順序執(zhí)行。(jr,&a,&b,p) 若arb為真（r為關系運算符）轉移至 四元式p，否則順序執(zhí)行。(jmp,0,0,p) 無條件轉移至四元式p30②實例引入例：ifa∨b<cthenS1elseS2

翻譯成如下四元式序列：

(1) (jnz,&a,0,5) //對應于布爾變量a (2) (jmp,0,0,3) //對應于布爾變量a (3) (j<,&b,&c,5) //對應于布爾表達式b<c (4) (jmp,0,0,m+1) //對應于布爾表達式b<c (5) 語句S1的四元式代碼開始

… …………… (m-1) 語句S1的四元式代碼結束

(m) (jmp,0,0,n+1) (m+1) 語句S2的四元式代碼開始

… …………… (n) 語句S2的四元式代碼結束1）每個布爾變量或關系表達式對應二個四元式，條件和無條件轉移四元式各一。四元式⑴⑵對應于布爾變量a，四元式⑶⑷對應于關系表達式b<c，原布爾運算消失。2）四元式⑴至⑷中含有多余的四元式，如⑵是不需要的。313）布爾表達式的真假出口（轉移目標地址）E(1)∨E(2)

E(1)的真出口是整個布爾表達式E(1)∨E(2)真出口

E(2)的第一個四元式地址是E(1)的假出口

E(2)的真假出口是整個布爾表達式E(1)∨E(2)的真假出口E(1)∧E(2)

E(1)的假出口是整個布爾表達式E(1)∧E(2)假出口

E(2)的第一個四元式地址是E(1)的真出口

E(2)的真假出口是整個布爾表達式E(1)∧E(2)的真假出口～E(1)

只要調(diào)換E(1)的真假出口就可得到～E(1)的真假出口TrueTrueTrueFalseFalseFalse32若后繼輸入符號為'∧'，則可將⑴式的第四項置為3；若后繼輸入符號為'∨'，可將⑵式的第四項置為3。另外一個未填轉移地址的四元式的地址只能作為語義值保存下來。當處理到then，說明布爾表達式翻譯完畢，此時可回填布爾表達式的真出口；當處理到else，可回填布爾表達式的假出口。③問題的提出在自下而上的分析過程中，語法分析器是自左至右掃描輸入符號串，一個布爾表達式的真假出口，往往不能在產(chǎn)生四元式的同時填入。接上例，首先將i歸約為X，X.addr保留變量a在符號表中的入口地址。然后將X歸約為E時，產(chǎn)生二個四元式如下： ⑴

(jnz,&a,0,?) ⑵

(jmp,0,0,?) 33④解決辦法1）修改文法

E→EAE|EOE|～E|(E)|XrX|X EA→E∧ //A表示and EO→E∨ //O表示or

X→X+X|X*X|(X)|-X|i|x通過文法修改解決了一半問題。EA→E∧

當E∧歸約為EA時，可填真出口，真出口為下一個四元式地址，而假出口無法填寫。EO→E∨

當E∨歸約為EO時，可填假出口，假出口為下一個四元式地址，而真出口無法填寫。2）引進語義變量.tc和.fc保存未填轉移目標的四元式地址布爾表達式由若干子表達式構成，轉移目標地址只有二個，或為真出口、或為假出口。為了記錄和回填方便，利用四元式的第四項（改稱為next）構成二條單向鏈。賦予E、EA和EO另外二個語義值.tc和.fc，分別記錄需回填真假出口單向鏈的鏈首。34

假定布爾表達式E的四元式中需回填真出口的有p、q和r三個四元式，這三個四元式可構成一單向鏈，鏈首由E.tc指出。

當X或XrX歸約為E時，將產(chǎn)生二個四元式。用E.tc指向第一個四元式，用E.fc指向第二個四元式，并將四元式的第四項置為0，表示鏈尾。如下所示：

在分析過程中，利用語義值傳遞和合并鏈的方法，最終完成兩根真假出口鏈的構造。在if-then-else語句中，當翻譯完布爾表達式，就可找到真出口，利用E.tc進行回填。當翻譯完語句S1，就可知道假出口，利用E.fc進行回填。353）變量和函數(shù)nxq指示器

nxq指向下一個將要形成但尚未形成的四元式地址（編號）。nxq初值為1，每執(zhí)行一次gen_code函數(shù)之后，nxq自動增1。鏈合并函數(shù)merg(p1,p2)

將以p1和p2為鏈首的二條單向鏈合并為一條，并且將合并后的鏈首作為返回值。若p2為空，則以p1為合并后的鏈首；若p2非空，則以p2為合并后的鏈首?；靥詈瘮?shù)backpatch(p,t)

將以p為鏈首的單向鏈中的每個四元式的第四項置為t。例a∨b<c∨d解：第一步（a∨）36第二步（a∨b<c∨） 第三步（a∨b<c∨

d）37第四步（當布爾表達式處理完，看到then后可回填真出口，語義動作是在控制語句的翻譯中實現(xiàn)）

因(1)式、(3)式和(5)式轉移地址相同，故由三個四元式構成一條真出口鏈，鏈首由.tc指出。當布爾表達式E處理完，看到then后，可回填真出口。假出口鏈由(6)式單獨構成，鏈首由.fc指出，作為語義值不斷地傳遞下去。當處理到else時，可回填假出口。38E→X{E.tc=nxq;gen_code(jnz,X.addr,0,0);E.fc=nxq;gen_code(jmp,0,0,0); }Er→XrX(1){E.tc=nxq;E.tc=nxq+1;gen_code(jr,X.addr,X(1).addr,0);gen_code(jmp,0,0,0) }E→～E(1){//真假出口鏈鏈首互換

E.tc=E(1).fc;E.fc=E(1).tc;}E→(E(1)){//傳遞

E.tc=E(1).tc;E.fc=E(1).fc;}EA→E∧{

backpatch(E.tc,nxq);//可填真出口

EA.fc=E.fc; //傳遞}E→EAE(2){E.tc=E(2).tc;//傳遞真出口鏈鏈首

E.fc=merge(EA.fc,E(2).fc);//合并}E→EOE(2){E.tc=merge(EO.tc,E(2).tc);//合并

E.fc=E(2).fc;//傳遞假出口鏈鏈首}EO→E(1)∨{EO.tc=E(1).tc;//傳遞

backpatch(E(1).fc,nxq);//可填假出口}X→i{//wval表示單詞的值

X.addr=sym_entry(wval);}X→x{X.addr=const_int_entry(atoi(wval));}⑤語義子程序。39⑥手工計算設源程序為a∨b∨c。經(jīng)詞法分析，它的單詞二元式序列為

(i,"a")(∨,"NUL")(i,"b")(∨,"NUL")(i,"c")(#,"NUL")語法制導翻譯過程如黑板所示：step

symbol

wval

.addr

.tc

.fc

輸入串

nxq=1翻譯結果⑴(JNZ,&a,0,0)⑵(JMP,0,0,⑶)⑶(JNZ,&b,0,⑴)⑷(JMP,0,0,⑸)⑸(JNZ,&c,0,⑶)⑹(JMP,0,0,0)E.tcE.fc406.9控制語句的翻譯㈠概述在說明語句、賦值語句和無條件轉移語句的基礎上，增加了條件語句、循環(huán)語句和復合語句。

<語句>→if<布爾表達式>then<語句>endif S→fEtSj<語句>→if<布爾表達式>then<語句>else<語句> S→fEtSeS<語句>→while<布爾表達式>do<語句> S→wEdS<語句>→begin<語句串>end S→{L}<語句串>→<語句串>;<語句> L→L;S<語句串>→<語句> L→SE的真出口只有掃描到then才明了，而E的假出口需處理完S1并且到達else才可進行回填。這就是說必須把E.fc傳遞下去，以便到達else時回填。㈡語義變量E.fc的傳遞

布爾表達式E具有二個語義值E.tc和E.fc，分別指出尚待回填真假出口的四元式。41㈢引進語義變量.chain

當語句S1執(zhí)行完，意味著整個if-then-else語句執(zhí)行完畢。因此，在S1的編碼之后應產(chǎn)生一條無條件轉移指令，這條轉移指令將導致程序控制離開整個if-then-else語句。但是，在完成S2的翻譯之前，這一無條件轉移指令的轉移目標是不知道的。甚至在翻譯完S2，轉移目標仍有可能無法確定，這種情況是由語句的嵌套性所引起的。

在S1代碼之后的那條無條件轉移指令不僅要跨越S2，而且還要跨越S3。參照布爾表達式的處理方法，讓非終結符S含有一項語義值S.chain。把所有的要離開控制語句的四元式構成一條單向鏈，鏈首由S.chain指示。這些四元式期待在翻譯完語句S之后回填轉移目標，語句翻譯完的標志就是看到分號（;是作為語句分割而引入的，它不是語句的必要組成部分，這一點和C語言不同）。ifE1thenifE2then S1else S2elseS3;//分號為語句間分割A=A+1426.9.1if-then語句的翻譯㈠文法及修改

<語句>→if<布爾表達式>then<語句>endif S→fEtS(1)j<語句>→標識符=<算術表達式> S→i=X為了能及時回填真出口，文法修改如下：

C→if<布爾表達式>then C→fEt<語句>→C<語句>endif S→CS(1)j<語句>→標識符=<算術表達式> S→i=X㈡語義子程序

C→fEt{ backpatch(E.tc,nxq); //回填真出口

C.chain=E.FC;} //假出口是離開if-then語句

S→CS(1)j{ //S(1)中可能含有離開if_then的四元式

S.chain=merge(C.chain,S(1).chain);}S→i=X{//賦值語句的四元式代碼中，不存在需回填轉移目標的四元式。

S.chain=0; gen_code(=,X.addr,0,sym_entry(wval));}43㈢手工計算設輸入串為：ifathenb=dendif，經(jīng)詞法分析，它的單詞二元式序列為：(f,"NUL")(i,"a")(t,"NUL")(i,"b")(=,"NUL")(i,"d")(j,"NUL")(#,"NUL")語法制導翻譯過程如下所示：step

symbol

wval

.addr

.tc

.fc

.chain

輸入串

nxq=1⑴(jnz,&a,0,⑶)⑵(jmp,0,0,0)⑶(=,&d,0,&b)S.chain=2446.9.2if-then-else語句的翻譯㈠文法及修改

<語句>→if<布爾表達式>then<語句1>else<語句2>

用文法符號表示如下：

S→fEtS(1)eS(2)

當掃描到then可填真出口，當掃描到else可填假出口，當S(1)的代碼執(zhí)行完畢，程序控制應離開if-then-else語句。為了能及時回填四元式，文法修改如下：

<語句>→TP<語句2> S→TPS(2)TP→C<語句1>else TP→CS(1)e //可填假出口

C→if<布爾表達式>then C→fEt //可填真出口注：TP可理解為then-processed45㈡語義子程序C→fEt{ //和if-then語句同

backpatch(E.tc,nxq);C.chain=E.FC;}TP→CS(1)e{

void*t;t=nxq;

//t為下一條四元式地址，即(jmp,0,0,0)的地址（編號）。

gen_code(jmp,0,0,0);

//執(zhí)行完S(1)后，離開if-then-else語句。

backpatch(C.chain,nxq);

//回填假出口，C.chain相當于E.FC，此時nxq=t+1。

TP.chain=merge(S(1).chain,t);

//S(1)中可能含有離開if_then-else的四元式}S→TPS(2){ //S(2)中可能含有離開if_then-else的四元式

S.chain=merge(TP.chain，S(2).chain);}46㈢手工計算設輸入串為：ifathenb=celseb=d。經(jīng)詞法分析，它的單詞二元式序列為：(f,"NUL")(i,"a")(t,"NUL")(i,"b")(=,"NUL")(i,"c")(e,"NUL")(i,"b")(=,"NUL")(i,"d")(#,"NUL")語法制導翻譯過程如下所示：step

symbol

wval

.addr

.tc

.fc

.chain

輸入串

nxq=1⑴(jnz,&a,0,⑶)⑵(jmp,0,0,⑸)⑶(=,&c,0,&b)⑷(jmp,0,0,0)⑸(=,&d,0,&b)S.chain476.9.3while-do語句的翻譯㈠文法及修改①布爾表達式E的真出口為S的第一個四元式地址。②E的假出口導致程序控制離開while-do語句，然而這個轉移目標地址在整個while-do語句翻譯完也未必明確。將該四元式的地址作為S的語義值S.chain保存下來，以便在外層環(huán)境中伺機回填。③在S的代碼最后應有一條無條件轉移四元式，轉向測試布爾表達式E，構成循環(huán)。需引進新的語義變量.quad，用于記錄E的第一個四元式地址。a=5;whilea>0doa=a-148while-do語句的產(chǎn)生式如下所示：

<語句>→while<布爾表達式>do<語句> S→wEdS(1)

為了便于語義分析，修改如下：

W→while W→w//可記錄E的第一個四元式地址

Wd→W<布爾表達式>do Wd→WEd //回填真出口

<語句>→Wd<語句> S→WdS(1)㈡語義子程序

W→w{ W.quad=nxq;} //記錄E的第一個四元式編號

Wd→WEd{ //Wd可理解為while-do backpatch(E.TC,nxq); //回填真出口

Wd.chain=E.fc; //傳遞假出口、即while-do的出口。

Wd.quad=W.quad; //傳遞E的第一個四元式地址

}S→WdS(1){ backpatch(S(1).chain,Wd.quad); /*回填S(1).chain鏈，因S(1)可能是控制語句，離開S(1)的四元式的轉移目標是E的第一個四元式。*/