語法制導(dǎo)翻譯和中間代碼生成

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

SLR分析器是由工作棧（狀態(tài)棧和符號棧）、分析表和總控程序三部分構(gòu)成，只要適當(dāng)修改工作棧和總控程序，就可將SLR分析器用于語義分析。①分析表不變②改造工作棧為了保存語義信息，在狀態(tài)棧、符號棧的基礎(chǔ)上增加單詞值（wval）棧和語義（semantic）棧。狀態(tài)棧符號棧單詞值棧語義棧5第五頁，共六十頁，2022年，8月28日

statesymbolwval.val.addr .cat.type …SmX……X.valX.addrX.catX.type……Sm-1Y……Y.valY.addrY.catY.type…………………………………………S0#"NUL"③修改總控程序在移進(jìn)時，除移進(jìn)狀態(tài)和單詞的種別外，還需移進(jìn)單詞的值。在用某個產(chǎn)生式進(jìn)行歸約時，除需執(zhí)行歸約動作外，還需調(diào)用相應(yīng)語義子程序。狀態(tài)棧不變符號棧不變增加單詞值棧，用于保存單詞的值（字符串形式）。增加語義棧，用于記錄分析過程中需保留的語義值。例，值（.val）、地址（.addr）、種屬（.cat）、類型（.type）等。經(jīng)改造后，工作棧如下所示：6第六頁，共六十頁，2022年，8月28日㈢解釋執(zhí)行例①文法及語義子程序

struct{charcode;charval[20];}t;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;}4.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]);}7第七頁，共六十頁，2022年，8月28日+*()x#E0s2s311s4s5Acc2s2s363r4r4r4r44s2s375s2s386s4s5s97r1s5r1r18r2r2r2r29r3r3r3r3③手工計算假設(shè)源程序為：7+9*5。經(jīng)詞法分析，單詞二元式序列為

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

state棧

symbol棧

wval棧

.val棧

輸入串②SLR分析表8第八頁，共六十頁，2022年，8月28日6.2符號表和常數(shù)表在編譯過程中，編譯程序需要不斷匯集和反復(fù)查證出現(xiàn)在源程序中各種符號名（標(biāo)識符）和常數(shù)，以及符號名的屬性，這些信息通常記錄在符號表和常數(shù)表中。㈠符號表①引入符號表的意義可用符號名表示內(nèi)存地址（變量）和語句的地址（標(biāo)號）。符號表的引入使得中間代碼生成（包括目標(biāo)代碼生成）與機(jī)器的內(nèi)存地址無關(guān)?？稍跈C(jī)器碼最終定位階段，甚至在程序運(yùn)行過程中，對變量進(jìn)行地址分配。在對變量進(jìn)行內(nèi)存地址分配時，符號表是地址分配的依據(jù)。轉(zhuǎn)移語句的翻譯是借助符號表來完成的。9第九頁，共六十頁，2022年，8月28日②符號表的結(jié)構(gòu)（略有修改）符號表由記錄構(gòu)成，相當(dāng)于一個結(jié)構(gòu)數(shù)組，模型語言的符號表定義如下：

struct{ void*addr; //標(biāo)號或變量的地址

charid[5]; //標(biāo)識符名

unsignedcat:4; //種屬（4個二進(jìn)制位）

unsignedtype:4; //類型（4個二進(jìn)制位）

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

存放內(nèi)存地址（2字節(jié)），地址標(biāo)識范圍為0-65535。變量的值并不存放于符號表，而是存儲在內(nèi)存的另外一個區(qū)域中，通過該地址指示，addr的值是在地址分配時填入。addr為結(jié)構(gòu)第一分量，結(jié)構(gòu)的地址值（&sym_table[i]）和結(jié)構(gòu)的第一分量地址值（&sym_table[i].addr）相等，結(jié)構(gòu)地址通常稱為變量在符號表中的入口。2）id

存放標(biāo)識符名，標(biāo)識符最多可由5個字符構(gòu)成。10第十頁，共六十頁，2022年，8月28日②符號表的結(jié)構(gòu)（略有修改）符號表由記錄構(gòu)成，相當(dāng)于一個結(jié)構(gòu)數(shù)組，模型語言的符號表定義如下：

struct{ void*addr; //標(biāo)號或變量的地址

charid[5]; //標(biāo)識符名

unsignedcat:4; //種屬（4個二進(jìn)制位）

unsignedtype:4; //類型（4個二進(jìn)制位）

}sym_table[NS]; //NS表示符號表長度3）cat

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

0表示簡單變量、1表示標(biāo)號4）type

用于記錄標(biāo)識符的類型（如整型、實(shí)型、布爾型、…），共有4個二進(jìn)制位，暫用1位。 簡單變量：0表示整型，1表示實(shí)型。 標(biāo)號：0表示標(biāo)號未定義，1表示標(biāo)號已定義。11第十一頁，共六十頁，2022年，8月28日③符號表的使用1）說明語句每當(dāng)識別出一個標(biāo)識符，就在符號表中為該標(biāo)識符建立一條記錄，并填入標(biāo)識符名、種屬、類型等語義信息。若符號表中已有記錄，說明標(biāo)識符被重定義，報錯。2）非說明語句每當(dāng)識別出一個標(biāo)識符，就根據(jù)標(biāo)識符名去查符號表，并由此獲得該標(biāo)識符在符號表的入口。若標(biāo)識符名在符號表中不存在，分情況處理：變量：報錯。標(biāo)號：在符號表中創(chuàng)建一個記錄，將標(biāo)識符名等信息填入符號表。④符號表地址使用說明在中間代碼生成時，若操作數(shù)是變量，則應(yīng)在操作數(shù)（operand）位置上填入該變量在符號表中的入口。根據(jù)中間代碼生成的目標(biāo)代碼，是通過間址尋址方式對變量進(jìn)行存?。?*operand）。借助間址尋址方式，使得中間代碼所使用的地址和實(shí)際存放數(shù)據(jù)的內(nèi)存地址相互獨(dú)立。12第十二頁，共六十頁，2022年，8月28日內(nèi)存地址（2字節(jié)）符號名（5字節(jié)）種屬（4Bit）類型（4Bit）…………………………未分配a99\0\0簡單整型…………………………值12345100符號表示意圖常數(shù)表示意圖13第十三頁，共六十頁，2022年，8月28日㈡常數(shù)表可設(shè)置一張常數(shù)表，同時記錄各種類型的常數(shù)；也可按類型設(shè)置多張常數(shù)表，按類型分表記錄。①常數(shù)表結(jié)構(gòu)

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

floatconst_real_table[NR]; //NR表示實(shí)常數(shù)表長度②常數(shù)表使用每當(dāng)識別出一個常數(shù)，將字符串轉(zhuǎn)換成數(shù)值后查常數(shù)表：若無，將常數(shù)填入常數(shù)表，獲取表中地址。若常數(shù)在表中已存在，直接獲取常數(shù)在表中地址。③常數(shù)表地址使用說明在中間代碼生成時，若操作數(shù)是常數(shù)，則應(yīng)在操作數(shù)(operand)位置上填入常數(shù)在常數(shù)表中的地址(&const_int_table[i]或&const_real_table[i])。目標(biāo)代碼運(yùn)行時，根據(jù)該地址（*operand）可獲得常數(shù)值，無需間址訪問。目標(biāo)代碼生成器可根據(jù)地址范圍來區(qū)分是符號表地址還是常數(shù)表地址，從而使用不同的尋址方式。14第十四頁，共六十頁，2022年，8月28日6.3中間代碼常用的中間代碼有三元式和四元式，在本書以后討論中，中間代碼采用四元式形式。6.3.1三元式㈠格式

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

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

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

15第十五頁，共六十頁，2022年，8月28日㈡優(yōu)點(diǎn)代碼生成無需引進(jìn)臨時變量。㈢缺點(diǎn)調(diào)整困難。在中間代碼優(yōu)化中，常常需要調(diào)整運(yùn)算順序、增減代碼，重新排列三元式。由于三元式通過指示器相聯(lián)系，調(diào)整相當(dāng)困難，有時甚至是不可能的。例，設(shè)源程序為： x=(a+b)*c; y=-d 它的三元式代碼為：⑴ + &a &b⑵ * ⑴ &c⑶ = &x ⑵⑷ - &d⑸ = &y ⑷若將源程序中的二條語句互換，改為：y=-d;x=(a+b)*c需修改三元式中一系列指示器，如下所示：⑴ - &d⑵ = &y ⑷⑴⑶ + &a &b⑷ * ⑴⑶ &c⑸ = &x ⑵⑷16第十六頁，共六十頁，2022年，8月28日6.3.2四元式㈠格式

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

⑵+ &a &T1 &T2說明：T1是臨時變量，&T1表示T1在臨時變量表中的入口，同理&T2。17第十七頁，共六十頁，2022年，8月28日㈡優(yōu)點(diǎn)調(diào)整方便。例，設(shè)源程序為 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它的四元式代碼只要簡單交換原二條語句相應(yīng)的四元式即可，無需再作任何修改。⑴- &d 0 &T3 ⑵= &T3 0 &y ⑶+ &a &b &T1 ⑷* &T1 &c &T2⑸= &T2 0 &x18第十八頁，共六十頁，2022年，8月28日㈢缺點(diǎn)在生成中間代碼時引進(jìn)大量臨時變量。㈣臨時變量的處理在形成四元式時，考慮代碼生成方便，不加限制地引進(jìn)臨時變量Ti（i=1,2,……）。在代碼優(yōu)化和目標(biāo)代碼生成階段，可將它們的數(shù)量壓縮到最低。關(guān)于臨時變量Ti有二種處理方法：①將Ti作為標(biāo)識符存入符號表，通過符號表入口對它們進(jìn)行引用。由于不加限制地引進(jìn)臨時變量，在隨后進(jìn)行的代碼優(yōu)化和目標(biāo)代碼生成中，有部分臨時變量有可能被刪除，采用此方法不是最合適。②臨時變量用于記錄運(yùn)算過程中的中間結(jié)果，必然是簡單變量，可另外設(shè)置臨時變量表（無需設(shè)置種屬一欄），將Ti存入臨時變量表，而不是存入符號表。在以后討論中，采用第二種方案。19第十九頁，共六十頁，2022年，8月28日6.4 說明語句（簡單變量）的翻譯說明語句用于定義變量，大多數(shù)高級語言都要求變量先定義后使用。說明語句的翻譯并不產(chǎn)生中間代碼，而是將變量的名字、種屬、類型等信息填入符號表。㈠文法及修改

<語句>→integer<標(biāo)識符表> S→aV <語句>→real<標(biāo)識符表> S→cV <標(biāo)識符表>→<標(biāo)識符表>,標(biāo)識符

V→V,i <標(biāo)識符表>→標(biāo)識符

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

<語句>→<說明> S→V <說明>→<說明>,標(biāo)識符

V→V,i <說明>→integer

標(biāo)識符

V→ai <說明>→real

標(biāo)識符

V→ci

用這個文法來制導(dǎo)翻譯，每當(dāng)讀進(jìn)一個標(biāo)識符，就可把它的變量名及其性質(zhì)填入符號表，沒有必要集中起來成批處理。20第二十頁，共六十頁，2022年，8月28日㈡語義子程序V→ai{ fill_sym_table(wval,0,0);//填寫符號表（標(biāo)識符名，簡單變量，整型）

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

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

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

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

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

}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

當(dāng)ai歸約為V，ai的所蘊(yùn)含的語義信息（整型、簡單變量）隨之消失。由于在一個說明語句中可定義多個變量，此時可使用語義變量V.cat和V.type保存語義信息。當(dāng)將V(1),i歸約為V時，i將繼承V(1)的語義信息。21第二十一頁，共六十頁，2022年，8月28日㈡語義子程序V→ai{ fill_sym_table(wval,0,0);//填寫符號表（標(biāo)識符名，簡單變量，整型） V.cat=0; //保存語義值（簡單變量） V.type=0;} //保存語義值（整型） V→ci{ fill_sym_table(wval,0,1);//填寫符號表（標(biāo)識符名，簡單變量，整型） V.cat=0; //保存語義值（簡單變量） V.type=1;} //保存語義值（實(shí)型） 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ù)標(biāo)識符的單詞值(變量名)查符號表。若無，則為其創(chuàng)建一個記錄，將變量名、種屬及類型等信息填入符號表；若已存在，說明變量名被重復(fù)定義，報錯。㈢手工計算設(shè)源程序說明語句為：intergera,b。經(jīng)詞法分析，源程序的單詞二元式序列為：(a,"NUL")(i,"a")(,,"NUL")(i,"b")(#,"NUL") 語法制導(dǎo)翻譯過程如黑板所示：

step

symbol棧

wval棧

.cat棧

.type棧

輸入串22第二十二頁，共六十頁，2022年，8月28日6.5 整型算術(shù)表達(dá)式及賦值語句的翻譯㈠文法<語句>→標(biāo)識符=<整型算術(shù)表達(dá)式> S→i=X<整型算術(shù)表達(dá)式>→<整型算術(shù)表達(dá)式>+<項> X→X+Y<整型算術(shù)表達(dá)式>→<項> X→Y<項>→<項>*<因子> Y→Y*Z<項>→<因子> Y→Z<因子>→(<整型算術(shù)表達(dá)式>) Z→(X)<因子>→-<因子> Z→-Z<因子>→標(biāo)識符

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

Z→x23第二十三頁，共六十頁，2022年，8月28日㈡語義子程序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ù)：voidgen_code(char*,void*,void*,void*);sym_entry函數(shù)：void*sym_entry(char*);get_tmpvar函數(shù)：void*get_tmpvar(int);const_int_entry函數(shù)：void*const_int_entry(unsignedshort);24第二十四頁，共六十頁，2022年，8月28日①get_tmpvar函數(shù)

void*get_tmpvar(int);

每調(diào)用一次，可獲得一個新的臨時變量，并將該變量在臨時變量表中的入口作為返回值。臨時變量名依次為T1、T2、…。1）get_tmpvar(0)表示申請一個整型臨時變量（2字節(jié)）2）get_tmpvar(1)表示申請一個實(shí)型臨時變量（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由一個或多個字符構(gòu)成，例+，jmp、itr等，故OP用字符串表示。④const_int_entry(wval)函數(shù)

void*const_int_entry(unsignedshort);

根據(jù)無符號整常數(shù)的單詞值（atoi(wval)）查無符號整常數(shù)表。若找到，則返回它在表中的地址；若無，則在表中創(chuàng)建該常數(shù)的記錄，然后返回表中地址。25第二十五頁，共六十頁，2022年，8月28日S→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(jié)→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ù)㈢手工計算設(shè)源程序為：a=-b*(c+2)。經(jīng)詞法分析，源程序的單詞二元式序列為：(i,"a")(=,"Nul")(-,"Nul")(i,"b")(*,"Nul")((,"Nul")(i,"c")(+,"Nul")(x,"2")(),"Nul")(#,"Nul")。語法制導(dǎo)翻譯過程如黑板所示：

step

symbol棧

wval棧

.addr棧

輸入串26第二十六頁，共六十頁，2022年，8月28日6.6混合型27第二十七頁，共六十頁，2022年，8月28日6.7 布爾表達(dá)式的翻譯㈠布爾表達(dá)式作用①控制語句的條件 ifx+y<10gotoL②計算邏輯值 d=x>y㈡程序設(shè)計語言的優(yōu)先級和結(jié)合性①標(biāo)準(zhǔn)Fortran語言（按表達(dá)式類別分級）第一級：算術(shù)表達(dá)式算術(shù)運(yùn)算符優(yōu)先級依次為： **,-（乘方/一元負(fù)）、*,/（乘/除）、+,-（加/減）第二級：關(guān)系表達(dá)式關(guān)系運(yùn)算符不相鄰，優(yōu)先性略。

<（.LT.）、<=（.LE.）、>（.GT.）、>=（.GE.）、<>（.NE.）、=（.EQ.）第三級：邏輯表達(dá)式邏輯運(yùn)算符優(yōu)先級依次為：～(.NOT.)、∧(.AND.)、∨(.OR)注：單目運(yùn)算服從右結(jié)合，雙目運(yùn)算服從左結(jié)合。28第二十八頁，共六十頁，2022年，8月28日例Fortran語言表達(dá)式((A+B).GT.(C+D)).AND.(E.EQ.F) ((A+B)>(C+D))∧(E=F) 等價于

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

NOT、-（一元負(fù)） 服從右結(jié)合第二級（乘法運(yùn)算符）： *、/、DIV、MOD、AND服從左結(jié)合第三級（加法運(yùn)算符）：

+、-、OR 服從左結(jié)合第四級（關(guān)系運(yùn)算符）：

<、<=、>、>=、<>、= 不相鄰例Pascal語言表達(dá)式((A+B)>(C+D))AND(E=F) ((A+B)>(C+D))∧(E=F) 等價于 (A+B>C+D)∧(E=F)③C語言（共分17級，同級運(yùn)算優(yōu)先性相同）略29第二十九頁，共六十頁，2022年，8月28日㈢描述布爾表達(dá)式文法以標(biāo)準(zhǔn)FORTRAN語言為基礎(chǔ)，適當(dāng)化簡。 E→E∨E|E∧E|(E)|～E|XrX|X X→X+X|X*X|(X)|-X|i|xE表示布爾表達(dá)式。X表示算術(shù)表達(dá)式。r是終結(jié)符，是關(guān)系運(yùn)算符(＞、≥、＜、≤、＝、≠)的抽象。文法G是一個二義文法。㈣布爾表達(dá)式計算方法①根據(jù)優(yōu)先性和結(jié)合性按步計算

例：1∨～0∧0∨0②優(yōu)化計算法a∨b解釋為：ifathentureelse計算b a∧b解釋為：ifathen計算belsefalse ～a解釋為：ifathenfalseelseture (～不計算)㈤布爾表達(dá)式的第一種翻譯法（同算術(shù)表達(dá)式） 例：a∨b∧～c＞230第三十頁，共六十頁，2022年，8月28日㈥布爾表達(dá)式的第二種翻譯法①概述布爾表達(dá)式E的作用在于控制對語句S1和S2的選擇，它的值無須保留。可賦予布爾表達(dá)式E二個出口：真出口：轉(zhuǎn)向語句S1假出口：轉(zhuǎn)向語句S2控制語句中的布爾表達(dá)式E，可譯成下述三種四元式的代碼序列：(jnz,&a,0,p) 若a為真（非0）轉(zhuǎn)移至四元式p，否則 順序執(zhí)行。(jr,&a,&b,p) 若arb為真（r為關(guān)系運(yùn)算符）轉(zhuǎn)移至 四元式p，否則順序執(zhí)行。(jmp,0,0,p) 無條件轉(zhuǎn)移至四元式p31第三十一頁，共六十頁，2022年，8月28日②實(shí)例引入例：ifa∨b<cthenS1elseS2

翻譯成如下四元式序列：

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

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

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

… …………… (n) 語句S2的四元式代碼結(jié)束1）每個布爾變量或關(guān)系表達(dá)式對應(yīng)二個四元式，條件和無條件轉(zhuǎn)移四元式各一。四元式⑴⑵對應(yīng)于布爾變量a，四元式⑶⑷對應(yīng)于關(guān)系表達(dá)式b<c，原布爾運(yùn)算消失。2）四元式⑴至⑷中含有多余的四元式，如⑵是不需要的。32第三十二頁，共六十頁，2022年，8月28日3）布爾表達(dá)式的真假出口（轉(zhuǎn)移目標(biāo)地址）E(1)∨E(2): E(1)的真出口是整個布爾表達(dá)式E(1)∨E(2)真出口

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

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

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

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

(jnz,&a,0,?) (jmp,0,0,?) 34第三十四頁，共六十頁，2022年，8月28日④解決辦法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∧

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

當(dāng)E∨歸約為E0時，可填假出口，假出口為下一個四元式地址，而真出口無法填寫。2）引進(jìn)語義變量.tc和.fc保存未填轉(zhuǎn)移目標(biāo)的四元式地址布爾表達(dá)式由若干子表達(dá)式構(gòu)成，轉(zhuǎn)移目標(biāo)地址只有二個，或為真出口、或為假出口。為了記錄和回填方便，利用四元式的第四項（改稱為next）構(gòu)成二條單向鏈。賦予E、EA和EO另外二個語義值.tc和.fc，分別記錄需回填真假出口單向鏈的鏈?zhǔn)住?5第三十五頁，共六十頁，2022年，8月28日假定布爾表達(dá)式E的四元式中需回填真出口的有p、q和r三個四元式，這三個四元式可構(gòu)成一單向鏈，鏈?zhǔn)子蒃.tc指出。當(dāng)X或XrX歸約為E時，將產(chǎn)生二個四元式。用E.tc指向第一個四元式，用E.fc指向第二個四元式，并將四元式的第四項置為0，表示鏈尾。如下所示：在分析過程中，利用語義值傳遞和合并鏈的方法，最終完成兩根真假出口鏈的構(gòu)造。在if-then-else語句中，當(dāng)翻譯完布爾表達(dá)式，就可找到真出口，利用E.tc進(jìn)行回填。當(dāng)翻譯完語句S1，就可知道假出口，利用E.fc進(jìn)行回填。36第三十六頁，共六十頁，2022年，8月28日3）變量和函數(shù)nxq指示器

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

將以p1和p2為鏈?zhǔn)椎亩l單向鏈合并為一條，并且將合并后的鏈?zhǔn)鬃鳛榉祷刂?。若p2為空，則以p1為合并后的鏈?zhǔn)祝蝗魀2非空，則以p2為合并后的鏈?zhǔn)??；靥詈瘮?shù)backpatch(p,t)

將以p為鏈?zhǔn)椎膯蜗蜴溨械拿總€四元式的第四項置為t。例a∨b<c∨d解：第一步（a∨）37第三十七頁，共六十頁，2022年，8月28日第二步（b<c∨） 第三步（d）38第三十八頁，共六十頁，2022年，8月28日第四步（布爾表達(dá)式處理完，回填真出口，語義動作在控制語句中實(shí)現(xiàn)）因(1)、(3)和(5)式轉(zhuǎn)移地址相同，故由三式構(gòu)成真出口鏈，鏈?zhǔn)子?tc指出，當(dāng)布爾表達(dá)式E處理完（開始處理S1前），可回填真出口。假出口鏈由(6)式單獨(dú)構(gòu)成，鏈?zhǔn)子?fc指出，當(dāng)處理到S2時，才可回填假出口。39第三十九頁，共六十頁，2022年，8月28日E→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){//真假出口鏈鏈?zhǔn)谆Q

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;//傳遞真出口鏈鏈?zhǔn)?/p>

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

E.fc=E(2).fc;//傳遞假出口鏈鏈?zhǔn)讅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));}⑤語義子程序。40第四十頁，共六十頁，2022年，8月28日⑥手工計算設(shè)源程序為a∨b∨c。經(jīng)詞法分析，它的單詞二元式序列為

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

symbol

wval

.addr

.tc

.fc

輸入串

nxq=141第四十一頁，共六十頁，2022年，8月28日6.8 標(biāo)號和無條件轉(zhuǎn)移語句的翻譯㈠標(biāo)號和goto語句標(biāo)號和變量不同，標(biāo)號不是通過說明語句來定義的，而是用

<標(biāo)號>:<語句>的形式來定義的，這種定義方式?jīng)Q定了標(biāo)號的使用范圍是局部的。只有少數(shù)程序設(shè)計語言（例Pascal）是用說明語句來定義標(biāo)號的。標(biāo)號是以“goto<標(biāo)號>”形式來使用的。標(biāo)號既可以先定位后使用（向后轉(zhuǎn)移），也可以先使用后定位（向前轉(zhuǎn)移）。②向前轉(zhuǎn)移①向后轉(zhuǎn)移42第四十二頁，共六十頁，2022年，8月28日㈡文法及修改

<語句>→標(biāo)識符:<語句> S→i:S <語句>→goto標(biāo)識符

S→gi

標(biāo)號用于標(biāo)領(lǐng)一個語句，為了能及時填寫標(biāo)號的地址，將文法修改如下：

<語句>→<標(biāo)號><語句> S→FS <標(biāo)號>→標(biāo)識符： F→i: <語句>→goto

標(biāo)識符

S→gi

當(dāng)i:歸約為F時，可將標(biāo)號名（L99）填入符號表，轉(zhuǎn)移地址為nxq的當(dāng)前值p（S的第1個四元式地址），種屬為1（標(biāo)號），類型為1（已定位）。符號表如下所示：內(nèi)存地址（2字節(jié)）符號名（5字節(jié)）種屬類型…………………………………pL9911…43第四十三頁，共六十頁，2022年，8月28日㈢問題的提出和解決辦法①gotoL99是一個向后轉(zhuǎn)移語句處理到gotoL99時，L99已定位?？赏ㄟ^查符號表獲得它的地址p，產(chǎn)生四元式(jmp,0,0,p)。②gotoL99是一個向前轉(zhuǎn)移語句L99第一次出現(xiàn)在符號表中創(chuàng)建一個記錄，符號名為“L99”，種屬為1（標(biāo)號），類型為0（未定位）,將nxq（設(shè)為q）作為鏈?zhǔn)滋钊隠99的地址欄，產(chǎn)生四元式：

(q)(jmp,0,0,0)L99非第一次出現(xiàn)說明以標(biāo)號L99為目標(biāo)的向前轉(zhuǎn)移語句不止一個，可利用四元式的第4項構(gòu)成一單向鏈。把L99的地址欄中的四元式編號（設(shè)為q）取出，把nxq（設(shè)為r）填入地址欄，然后產(chǎn)生四元式：

(r)(jmp,0,0,q)44第四十四頁，共六十頁，2022年，8月28日45第四十五頁，共六十頁，2022年，8月28日6.9控制語句的翻譯㈠概述在說明語句、賦值語句和無條件轉(zhuǎn)移語句的基礎(chǔ)上，增加了條件語句、循環(huán)語句和復(fù)合語句。

<語句>→if<布爾表達(dá)式>then<語句>endif S→fEtSj<語句>→if<布爾表達(dá)式>then<語句>else<語句> S→fEtSeS<語句>→while<布爾表達(dá)式>do<語句> S→wEdS<語句>→begin<語句串>end S→{L}<語句串>→<語句串>;<語句> L→L;S<語句串>→<語句> L→S

E的真出口只有掃描到then才明了，而E的假出口需處理完S1并且到達(dá)else才可進(jìn)行回填。這就是說必須把E.fc傳遞下去，以便到達(dá)else時回填。㈡語義變量E.fc的傳遞

布爾表達(dá)式E具有二個語義值E.tc和E.fc，分別指出尚待回填真假出口的四元式。46第四十六頁，共六十頁，2022年，8月28日㈢引進(jìn)語義變量.chain

當(dāng)語句S1執(zhí)行完，意味著整個if-then-else語句執(zhí)行完畢。因此，在S1的編碼之后應(yīng)產(chǎn)生一條無條件轉(zhuǎn)移指令，這條轉(zhuǎn)移指令將導(dǎo)致程序控制離開整個if-then-else語句。但是，在完成S2的翻譯之前，這一無條件轉(zhuǎn)移指令的轉(zhuǎn)移目標(biāo)是不知道的。甚至在翻譯完S2，轉(zhuǎn)移目標(biāo)仍有可能無法確定，這種情況是由語句的嵌套性所引起的。在S1代碼之后的那條無條件轉(zhuǎn)移指令不僅要跨越S2，而且還要跨越S3。參照布爾表達(dá)式的處理方法，讓非終結(jié)符S含有一項語義值S.chain。把所有的要離開控制語句的四元式構(gòu)成一條單向鏈，鏈?zhǔn)子蒘.chain指示。這些四元式期待在翻譯完語句S之后回填轉(zhuǎn)移目標(biāo)，語句翻譯完的標(biāo)志就是看到分號（;）。47第四十七頁，共六十頁，2022年，8月28日6.9.1if-then語句的翻譯㈠文法及修改

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

C→if<布爾表達(dá)式>then C→fEt<語句>→C<語句>endif S→CS(1)j<語句>→標(biāo)識符=<算術(shù)表達(dá)式> 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{ //賦值語句的四元式代碼中不存在需回填轉(zhuǎn)移目標(biāo)的四元式

S.chain=0; gen_code(=,X.addr,0,sym_entry(wval));}48第四十八頁，共六十頁，2022年，8月28日㈢手工計算設(shè)輸入串為：ifathenb=dendif。經(jīng)詞法分析，它的單詞二元式序列為：(f,"NUL")(i,"a")(t,"NUL")(i,"b")(=,"NUL")(i,"d")(j,"NUL")(#,"NUL")語法制導(dǎo)翻譯過程如下所示：step

symbol

wval

.addr

.tc

.fc

.chain

輸入串

nxq=149第四十九頁，共六十頁，2022年，8月28日6.9.2if-then-else語句的翻譯㈠文法及修改

if-then-else語句的產(chǎn)生式

<語句>→if<布爾表達(dá)式>then<語句>else<語句> S→fEtS(1)eS(2)

當(dāng)掃描到then可填真出口，當(dāng)掃描到else可填假出口，當(dāng)S(1)執(zhí)行完畢，應(yīng)離開if-then-else語句。為了能及時回填四元式，修改如下：

<語句>→TP<語句> S→TPS(2)TP→C<語句>else TP→CS(1)eC→if<布爾表達(dá)式>then C→fEt注：TP可理解為then-processed50第五十頁，共六十頁，2022年，8月28日㈡語義子程序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相當(dāng)于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);}C→fEt{ backpatch(E.tc,nxq);C.chain=E.FC;}51第五十一頁，共六十頁，2022年，8月28日㈢手工計算設(shè)輸入串為：ifathenb=celseb=d。經(jīng)詞法分析，它的單詞二元式序列為：(f,"NUL")(i,"a")(t,"NUL")(i,"b")(=,"NUL")(i,"c")(e,"NUL")(i,"b")(=,"NUL")(i,"d")(#,"NUL")語法制導(dǎo)翻譯過程如下所示：step

symbol

wval

.addr

.tc

.fc

.chain

輸入串

nxq=152第五十二頁，共六十頁，2022年，8月28日6.9.3while-do語句的翻譯㈠文法及修改①布爾表達(dá)式E的真出口為S的第一個四元式地址。②E的假出口導(dǎo)致程序控制離開while-do語句，然而這個轉(zhuǎn)移目標(biāo)地址在整個while-do語句翻譯完也未必明確。將該四元式的地址作為S的語義值S.chain保存下來，以便在外層環(huán)境中伺機(jī)回填。③在S的代碼最后應(yīng)有一條無條件轉(zhuǎn)移四元式，轉(zhuǎn)向測試布爾表達(dá)式E，構(gòu)成循環(huán)。需引進(jìn)新的語義變量.quad，用于記錄E的第一個四元式地址。53第五十三頁，共六十頁，2022年，8月28日

while-do語句的產(chǎn)生式如下所示：

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

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

W→while W→w Wd→W<布爾表達(dá)式>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){