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

1第6章語法制導(dǎo)翻譯和中間代碼生成6.1

語法制導(dǎo)翻譯概述6.2

符號(hào)表和常數(shù)表6.3

中間代碼6.4

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

整型算術(shù)表達(dá)式及賦值語句的翻譯6.6

混合型算術(shù)表達(dá)式及賦值語句的翻譯6.7

布爾表達(dá)式的翻譯6.8

標(biāo)號(hào)和無條件轉(zhuǎn)移語句的翻譯6.9

控制語句的翻譯

if-then

if-then-else

while-do

復(fù)合語句6.10

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

SLR分析器是由工作棧（狀態(tài)棧和符號(hào)棧）、分析表和總控程序三部分構(gòu)成，只要適當(dāng)修改工作棧和總控程序，就可將SLR分析器用于語義分析。①分析表不變②改造工作棧為了保存語義信息，在狀態(tài)棧、符號(hào)棧的基礎(chǔ)上增加單詞值（wval）棧和語義（semantic）棧。狀態(tài)棧（原有）符號(hào)棧（原有）單詞值棧（新增）語義棧（新增）6狀態(tài)棧（不變）符號(hào)棧（不變）增加單詞值棧（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"③修改總控程序在移進(jìn)時(shí)，除移進(jìn)狀態(tài)和單詞的種別外，還需移進(jìn)單詞的值。在用某個(gè)產(chǎn)生式進(jìn)行歸約時(shí)，除需執(zhí)行歸約動(dòng)作外，還需調(diào)用相應(yīng)語義子程序。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ù)假定語義動(dòng)作是緊接著歸約之后執(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③手工計(jì)算假設(shè)源程序?yàn)椋?+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

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

內(nèi)存單元X

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

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

charid[4]; //標(biāo)識(shí)符名

charcat; //種屬（4個(gè)二進(jìn)制位）

chartype; //類型（4個(gè)二進(jìn)制位）

}sym_table[NS]; //NS表示符號(hào)表長度1）addr

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

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

0：簡單變量

1：標(biāo)號(hào)4）type

用于記錄標(biāo)識(shí)符的類型（如整型、實(shí)型、布爾型、……），4個(gè)二進(jìn)制位，暫用1位。 簡單變量：0表示整型，1表示實(shí)型。 標(biāo)號(hào)：0表示標(biāo)號(hào)未定義，1表示標(biāo)號(hào)已定義。③引入符號(hào)表的意義可用符號(hào)名表示內(nèi)存地址（變量）和語句的地址（標(biāo)號(hào)）。符號(hào)表的引入使得中間代碼生成（包括目標(biāo)代碼生成）與機(jī)器的內(nèi)存地址無關(guān)?？稍跈C(jī)器碼最終定位階段，甚至在程序運(yùn)行過程中，對變量進(jìn)行地址分配。在對變量進(jìn)行內(nèi)存地址分配時(shí)，符號(hào)表是地址分配的依據(jù)。轉(zhuǎn)移語句的翻譯是借助符號(hào)表來完成的。12④符號(hào)表的使用1）說明語句每當(dāng)識(shí)別出一個(gè)標(biāo)識(shí)符，就在符號(hào)表中為該標(biāo)識(shí)符建立一條記錄，并填入標(biāo)識(shí)符名、種屬、類型等語義信息。若符號(hào)表中已有記錄，說明標(biāo)識(shí)符被重定義，報(bào)錯(cuò)。2）非說明語句每當(dāng)識(shí)別出一個(gè)標(biāo)識(shí)符，就根據(jù)標(biāo)識(shí)符名去查符號(hào)表，并由此獲得該標(biāo)識(shí)符在符號(hào)表的入口。若標(biāo)識(shí)符名在符號(hào)表中不存在，分情況處理：變量：報(bào)錯(cuò)。標(biāo)號(hào)：在符號(hào)表中創(chuàng)建一個(gè)記錄，將標(biāo)識(shí)符名等信息填入符號(hào)表。⑤符號(hào)表入口地址使用說明在中間代碼生成時(shí)，若操作數(shù)是變量，則應(yīng)在操作數(shù)（operand）位置上填入該變量在符號(hào)表中的入口。根據(jù)中間代碼生成的目標(biāo)代碼，是通過間址尋址方式對變量進(jìn)行存?。?*operand）。借助間址尋址方式，使得中間代碼所使用的地址和實(shí)際存放數(shù)據(jù)的內(nèi)存地址相互獨(dú)立。13㈡常數(shù)表可設(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í)別出一個(gè)常數(shù)，將字符串轉(zhuǎn)換成數(shù)值后查常數(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)行時(shí)，根據(jù)該地址（*operand）可獲得常數(shù)值，無需間址訪問。目標(biāo)代碼生成器可根據(jù)地址范圍來區(qū)分是符號(hào)表地址還是常數(shù)表地址，從而使用不同的尋址方式。值12345常數(shù)表入口146.3中間代碼

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

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

⑴ * &b &2 //⑴代表子表達(dá)式b*2的計(jì)算結(jié)果

⑵

+ &a ⑴ //&b表示變量b在符號(hào)表中的入口

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

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

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

⑴* &b &2 &T1

⑵+ &a &T1 &T2說明：

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

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㈢缺點(diǎn)在生成中間代碼時(shí)引進(jìn)大量臨時(shí)變量。㈣臨時(shí)變量的處理在形成四元式時(shí)，考慮代碼生成方便，不加限制地引進(jìn)臨時(shí)變量Ti（i=1,2,……）。在代碼優(yōu)化和目標(biāo)代碼生成階段，可將它們的數(shù)量壓縮到最低。關(guān)于臨時(shí)變量Ti有二種處理方法：①將Ti作為標(biāo)識(shí)符存入符號(hào)表，通過符號(hào)表入口對它們進(jìn)行引用。由于不加限制地引進(jìn)臨時(shí)變量，在隨后進(jìn)行的代碼優(yōu)化和目標(biāo)代碼生成中，有部分臨時(shí)變量有可能被刪除，采用此方法不是最合適。②臨時(shí)變量用于記錄運(yùn)算過程中的中間結(jié)果，必然是簡單變量，可另外設(shè)置臨時(shí)變量表（無需設(shè)置種屬一欄），將Ti存入臨時(shí)變量表，而不是存入符號(hào)表。在以后討論中，采用第二種方案。196.4 說明語句（簡單變量）的翻譯

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

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

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

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

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

V→V,i <說明>→integer

標(biāo)識(shí)符

V→ai <說明>→real

標(biāo)識(shí)符

V→ci

用這個(gè)文法來制導(dǎo)翻譯，每當(dāng)讀進(jìn)一個(gè)標(biāo)識(shí)符，就可把它的變量名及其性質(zhì)填入符號(hào)表，沒有必要集中起來成批處理。integera,b的語法結(jié)構(gòu)為：ai,iSaVaV,iai,iai,i、aV,i、aV、Sintegera,b的語法結(jié)構(gòu)為：ai,i

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

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

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

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

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)含的語義信息（整型、簡單變量）隨之消失。由于在一個(gè)說明語句中可定義多個(gè)變量，此時(shí)可使用語義變量V.cat和V.type保存語義信息。當(dāng)將V(1),i歸約為V時(shí)，i將繼承V(1)的語義信息。21㈡語義子程序V→ai{ fill_sym_table(wval,0,0);//填寫符號(hào)表（標(biāo)識(shí)符名，簡單變量，整型）

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

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

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)識(shí)符的單詞值(變量名)查符號(hào)表。若無，則為其創(chuàng)建一個(gè)記錄，將變量名、種屬及類型等信息填入符號(hào)表；若已存在，說明變量名被重復(fù)定義，報(bào)錯(cuò)。㈢手工計(jì)算設(shè)源程序說明語句為：intergera,b。經(jīng)詞法分析，源程序的單詞二元式序列為：(a,"NUL")(i,"a")(,,"NUL")(i,"b")(#,"NUL") 語法制導(dǎo)翻譯過程如黑板所示：

step

symbol棧

wval棧

.cat棧

.type棧

輸入串226.5 整型算術(shù)表達(dá)式及賦值語句的翻譯㈠文法<語句>→標(biāo)識(shí)符=<整型算術(shù)表達(dá)式> S→i=X<整型算術(shù)表達(dá)式>→<整型算術(shù)表達(dá)式>+<項(xiàng)> X→X+Y<整型算術(shù)表達(dá)式>→<項(xiàng)> X→Y<項(xiàng)>→<項(xiàng)>*<因子> Y→Y*Z<項(xiàng)>→<因子> Y→Z<因子>→(<整型算術(shù)表達(dá)式>) Z→(X)<因子>→-<因子> Z→-Z<因子>→標(biāo)識(shí)符

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

Z→x說明：在算法表達(dá)式文法中，用X取代E，用Y取代T，用Z取代F。E、T和F將用于布爾表達(dá)式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個(gè)參數(shù)產(chǎn)生四元式；sym_entry函數(shù):根據(jù)變量的符號(hào)名查表，返回它的符號(hào)表入口。get_tmpvar函數(shù):申請一個(gè)臨時(shí)變量(實(shí)或整)，返回它的地址。const_int_entry函數(shù):根據(jù)常數(shù)值查常數(shù)表，返回入口地址。本書P147-P14824①get_tmpvar函數(shù)

void*get_tmpvar(int);

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

void*sym_entry(char*);

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

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

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

void*const_int_entry(unsignedshort);

根據(jù)無符號(hào)整常數(shù)的單詞值（atoi(wval)）查無符號(hào)整常數(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); //申請臨時(shí)變量(整型) 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); //申請臨時(shí)變量(整型) 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); //申請臨時(shí)變量(整型) 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ù)㈢手工計(jì)算設(shè)源程序?yàn)椋篴=-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棧

輸入串⑴（-,&b,0,&T1）⑵（+,&c,&2,&T2）⑶（*,&T1,&T2,&T3）⑷（=,&T3,0,&a）266.7 布爾表達(dá)式的翻譯㈠布爾表達(dá)式作用①控制語句的條件 ifx+y<10gotoL②計(jì)算邏輯值 d=x>y㈡程序設(shè)計(jì)語言的優(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é)合。27

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

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) 等價(jià)于 (A+B>C+D)∧(E=F)③C語言（共分17級，同級運(yùn)算優(yōu)先性相同）略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是一個(gè)二義文法㈣布爾表達(dá)式計(jì)算方法①根據(jù)優(yōu)先性和結(jié)合性按步計(jì)算

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

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

a∨b解釋為：ifathentureelse{計(jì)算b} a∧b解釋為：ifathen{計(jì)算b}elsefalse

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

布爾表達(dá)式E的作用在于控制對語句S1和S2的選擇，它的值無須保留?？少x予布爾表達(dá)式E二個(gè)出口： 真出口：轉(zhuǎn)向語句S1代碼 假出口：轉(zhuǎn)向語句S2代碼布爾表達(dá)式E，可使用下述三種四元式進(jìn)行翻譯：(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)移至四元式p30②實(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）每個(gè)布爾變量或關(guān)系表達(dá)式對應(yīng)二個(gè)四元式，條件和無條件轉(zhuǎn)移四元式各一。四元式⑴⑵對應(yīng)于布爾變量a，四元式⑶⑷對應(yīng)于關(guān)系表達(dá)式b<c，原布爾運(yùn)算消失。2）四元式⑴至⑷中含有多余的四元式，如⑵是不需要的。313）布爾表達(dá)式的真假出口（轉(zhuǎn)移目標(biāo)地址）E(1)∨E(2)

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

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

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

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

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

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

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

(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∧

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

當(dāng)E∨歸約為EO時(shí)，可填假出口，假出口為下一個(gè)四元式地址，而真出口無法填寫。2）引進(jìn)語義變量.tc和.fc保存未填轉(zhuǎn)移目標(biāo)的四元式地址布爾表達(dá)式由若干子表達(dá)式構(gòu)成，轉(zhuǎn)移目標(biāo)地址只有二個(gè)，或?yàn)檎娉隹?、或?yàn)榧俪隹?。為了記錄和回填方便，利用四元式的第四?xiàng)（改稱為next）構(gòu)成二條單向鏈。賦予E、EA和EO另外二個(gè)語義值.tc和.fc，分別記錄需回填真假出口單向鏈的鏈?zhǔn)住?4

假定布爾表達(dá)式E的四元式中需回填真出口的有p、q和r三個(gè)四元式，這三個(gè)四元式可構(gòu)成一單向鏈，鏈?zhǔn)子蒃.tc指出。

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

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

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

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

將以p為鏈?zhǔn)椎膯蜗蜴溨械拿總€(gè)四元式的第四項(xiàng)置為t。例a∨b<c∨d解：第一步（a∨）36第二步（a∨b<c∨） 第三步（a∨b<c∨

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

因(1)式、(3)式和(5)式轉(zhuǎn)移地址相同，故由三個(gè)四元式構(gòu)成一條真出口鏈，鏈?zhǔn)子?tc指出。當(dāng)布爾表達(dá)式E處理完，看到then后，可回填真出口。假出口鏈由(6)式單獨(dú)構(gòu)成，鏈?zhǔn)子?fc指出，作為語義值不斷地傳遞下去。當(dāng)處理到else時(shí)，可回填假出口。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){//真假出口鏈鏈?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));}⑤語義子程序。39⑥手工計(jì)算設(shè)源程序?yàn)閍∨b∨c。經(jīng)詞法分析，它的單詞二元式序列為

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

symbol

wval

.addr

.tc

.fc

輸入串

nxq=1翻譯結(jié)果⑴(JNZ,&a,0,0)⑵(JMP,0,0,⑶)⑶(JNZ,&b,0,⑴)⑷(JMP,0,0,⑸)⑸(JNZ,&c,0,⑶)⑹(JMP,0,0,0)E.tcE.fc406.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→SE的真出口只有掃描到then才明了，而E的假出口需處理完S1并且到達(dá)else才可進(jìn)行回填。這就是說必須把E.fc傳遞下去，以便到達(dá)else時(shí)回填。㈡語義變量E.fc的傳遞

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

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

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

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

C→if<布爾表達(dá)式>then C→fEt<語句>→C<語句>endif S→CS(1)j<語句>→標(biāo)識(shí)符=<算術(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));}43㈢手工計(jì)算設(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=1⑴(jnz,&a,0,⑶)⑵(jmp,0,0,0)⑶(=,&d,0,&b)S.chain=2446.9.2if-then-else語句的翻譯㈠文法及修改

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

用文法符號(hào)表示如下：

S→fEtS(1)eS(2)

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

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

C→if<布爾表達(dá)式>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)的地址（編號(hào)）。

gen_code(jmp,0,0,0);

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

backpatch(C.chain,nxq);

//回填假出口，C.chain相當(dāng)于E.FC，此時(shí)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㈢手工計(jì)算設(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=1⑴(jnz,&a,0,⑶)⑵(jmp,0,0,⑸)⑶(=,&c,0,&b)⑷(jmp,0,0,0)⑸(=,&d,0,&b)S.chain476.9.3while-do語句的翻譯㈠文法及修改①布爾表達(dá)式E的真出口為S的第一個(gè)四元式地址。②E的假出口導(dǎo)致程序控制離開while-do語句，然而這個(gè)轉(zhuǎn)移目標(biāo)地址在整個(gè)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的第一個(gè)四元式地址。a=5;whilea>0doa=a-148while-do語句的產(chǎn)生式如下所示：

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

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

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

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

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

W→w{ W.quad=nxq;} //記錄E的第一個(gè)四元式編號(hào)

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

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

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

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