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

語法制導(dǎo)翻譯和中間代碼生成第一頁，共五十五頁，2022年，8月28日代碼優(yōu)化靜態(tài)存儲分配目標(biāo)代碼生成789第二頁，共五十五頁，2022年，8月28日第5章語法制導(dǎo)翻譯和中間代碼生成自動機(jī)第三頁，共五十五頁，2022年，8月28日編譯中的語義處理是兩個功能：第一，審查每個語法結(jié)構(gòu)的靜態(tài)語義，即驗(yàn)證語法結(jié)構(gòu)合法的程序是否真正有意義。有時把這個工作稱為靜態(tài)語義分析或靜態(tài)審查。第二，如果靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯，即，要么生成程序的一種中間邊式形式（中間代碼），要么生成實(shí)際的目標(biāo)代碼。第四頁，共五十五頁，2022年，8月28日§5.1屬性文法

屬性文法的形式定義：一個屬性文法形式上可定義為一個三元組A，A=（G，V，F(xiàn)）。其中G表示一個上下文無關(guān)文法；V表示屬性的有窮集；F表示有關(guān)屬性的斷言或謂詞的有窮集。

屬性可以分為綜合屬性和繼承屬性兩類。綜合屬性一般用于自下而上傳遞信息，而繼承屬性常常用于自上而下傳遞信息。

第五頁，共五十五頁，2022年，8月28日

簡單算術(shù)表達(dá)式求值的屬性文法。

規(guī)則語義規(guī)則1.S→Eprint（E.val）2.E→E1＋TE.val:=E1.val＋T.val3.E→TE.va1:=T.valv4.T→T1FT.val:=T1.valF.val5.T→T1T.val:=T1.val6.F→（E）F.val:=E.val7.F→digitF.val:=digit.lexval

例5.1

：第六頁，共五十五頁，2022年，8月28日此例中，每一個非終結(jié)符都有一個表示整數(shù)值的屬性val，如E.va1，表示E的整數(shù)值。按照語義規(guī)則，每個規(guī)則的左部符號如E，T，F(xiàn)等的屬性值的計(jì)算取決于各自相應(yīng)的右部非終結(jié)符，我們把這種屬性稱為綜合屬性。單詞digit僅有綜合屬性，它的值是由詞法分析程序提供的。與規(guī)則S→E關(guān)聯(lián)的語義規(guī)則是一個過程print（E.vd），其功能是打印由E產(chǎn)生的表達(dá)式的值。對于在語義規(guī)則中并沒有出現(xiàn)文法符號S，我們認(rèn)為其屬性是虛的或者空的。

第七頁，共五十五頁，2022年，8月28日

說明語句中各種變量的類型信息的語義描述。規(guī)則語義規(guī)則1.D→TLL.in:=T.type2.T→intT.type:=integer3.T→realT.type:=real4.L→L1，idL1.in:=L.inaddtype（id.entry，L.in）5.L→idaddtype（id.entry，L.in）例5.2

：第八頁，共五十五頁，2022年，8月28日與例中對應(yīng)的原文法可以表示為1.D→intL｜realL2.L→L，id｜id下圖是句子intid1，id2的語法樹。用“→”表示屬性信息的傳遞情況。DTLLint，id1id2屬性信息的傳遞情況第九頁，共五十五頁，2022年，8月28日§5.2語法制導(dǎo)翻譯概述

語法制導(dǎo)翻譯技術(shù)分為自底向上語法制導(dǎo)翻譯和自頂向下語法制導(dǎo)翻譯。下面以LR語法制導(dǎo)翻譯為例，討論如何具體實(shí)現(xiàn)語法制導(dǎo)翻譯。假定有輸入串3＋45，這是一個簡單的算術(shù)表達(dá)式，相應(yīng)的文法及各產(chǎn)生式的語義規(guī)則見例5.1。表達(dá)式3＋45的語法制導(dǎo)翻譯法求值過程第十頁，共五十五頁，2022年，8月28日語法樹描述圖E.val:=335E.val:=234E.val:20E.val:=5E.val:=4+

Sny.valYSn-1x.valX┋┋┋S0-#狀態(tài)棧語義值棧文法符號符號棧擴(kuò)充的LR分析棧

第十一頁，共五十五頁，2022年，8月28日狀態(tài)actiongoto＋（）d#ETF0

s4

s5

1231

s6

acc

2s7r2

r2

r2

3r4r4

r4

r4

4

s4

s5

8235r6r6

r6

r6

6

s4

s5

937

s4

s5

108

s6

s11

9s7r1

r1

r1

10r3r3

r3

r3

11r5r5

r5

r5

LR分析表

第十二頁，共五十五頁，2022年，8月28日步驟狀態(tài)棧語義棧符號棧剩余串主要動作10-#3＋45#

205--#3＋45#

303-3#F＋45#r6402-3#T＋45#r4501-3#E＋45#r26016-3-#E＋5#

70165-3--#E＋45#

80163-3-4#E＋F5#r690169-3-4#E＋T5#r41001697-3-4-#E＋T5#

11016975-3-4--#E＋T5#

120169（10）-3-4-5#E＋TF

r6130169-3-20#E＋T#r31401-23#E#r115

acc表達(dá)式3＋45的語法語義分析和計(jì)值過程

第十三頁，共五十五頁，2022年，8月28日§5.3中間語言所謂中間語言，也稱中間代碼，是復(fù)雜性介于源程序語言和機(jī)器語言的一種記號系統(tǒng)。一般來說，快速編譯程序直接生成目標(biāo)代碼，沒有將中間代碼翻譯成目標(biāo)代碼的額外開銷。但是為了使編譯程序結(jié)構(gòu)在邏輯上更為簡單明確，使生成的的目標(biāo)代碼更為高效，通常采用中間語言。編譯程序所使用的中間語言形式較多。常見的逆波蘭式、三元式、四元式和樹形表示等。第十四頁，共五十五頁，2022年，8月28日逆波蘭式是最簡單的一種中間語言形式，用逆波蘭式表示的表達(dá)式也稱做后綴式。它的特點(diǎn)是將運(yùn)算對象寫在前面，把運(yùn)算符號寫在后面，比如把x＋y寫成xy＋，把xy寫成xy。對于簡單表達(dá)式E，相應(yīng)的逆波蘭式E′遵循下面的轉(zhuǎn)換規(guī)則：表達(dá)式逆波蘭式

EE′(E)E′5.3.1逆波蘭式第十五頁，共五十五頁，2022年，8月28日

－EE@（負(fù)號“－”是一元運(yùn)算符，為了區(qū)別于減號“－”，通常寫成@）

E1opE2E1′E2′op如，表達(dá)式x＋y

z的逆波蘭式為xyz＋；賦值語句x:=x

y－y/z的逆波蘭式為xxyyz/－:=。用逆波蘭式表示表達(dá)式，其最大的優(yōu)點(diǎn)是第十六頁，共五十五頁，2022年，8月28日從左至右掃描該算術(shù)表達(dá)式的逆波蘭式：每碰到運(yùn)算對象，就把它推進(jìn)棧；碰到運(yùn)算符，若該運(yùn)算符是k目運(yùn)算符，則對找頂部的k個運(yùn)算對象實(shí)施該運(yùn)算，并用運(yùn)算結(jié)果代替這k個運(yùn)算對象并入錢。這樣，當(dāng)將整個后綴式掃描完畢，該表達(dá)式的結(jié)果也就計(jì)算出來了。第十七頁，共五十五頁，2022年，8月28日t1:=－xxt1yzt2:=yzt1t2t3:=t1＋t2同時y、z入棧t3逆波蘭式的計(jì)值過程算術(shù)表達(dá)式－x＋yz的逆波蘭式為x@yz＋，在棧中的計(jì)值過程如圖所示。

例5.3

：第十八頁，共五十五頁，2022年，8月28日三元式是中間語言的另一種形式，每個三元式由三個部分組成:算符op，運(yùn)算對象arg1，運(yùn)算對象arg2。三元式的一般格式為：（i）（op，arg1，arg2）。其中（i）為序號。如表達(dá)式－ab＋cd可用三元式表示為：（1）（@，a，－）（2）（，（1），b）（3）（，c，d）5.3.2三元式和樹形表示第十九頁，共五十五頁，2022年，8月28日（4）（＋，（2），（3））“－”是一目運(yùn)算符（這里用@表示），用來使a取反，只需選用一個運(yùn)算對象，不妨規(guī)定只用arg1，至于多目算符，可采用多個相繼的三元式表示。2.樹形表示樹形表示實(shí)際上是三元式的另一種表示形式，例如，表達(dá)式－ab＋cd可用如下樹形表示如下。第二十頁，共五十五頁，2022年，8月28日間接三元式為了盡量不改變?nèi)奖恚梢粤碓O(shè)一張間接碼表來表示有關(guān)三元式在三元式表的計(jì)值順序。用這種方法獲得的中間代碼稱為間接三元式。－ab＋cd的樹形表示＋ab-dc第二十一頁，共五十五頁，2022年，8月28日例如，表達(dá)式a:=x＋yzb:=t－yz的間接三元式表示如圖所示。

三元式列表間接碼表（1）（，y，z）（2）（＋，x，（1））（3）（:=，a，（2））（4）（－，t，（1））（5）（:=，—，（4））

（1）（2）（3）（1）（4）（5）間接三元式表示

第二十二頁，共五十五頁，2022年，8月28日采用這種表示方法，當(dāng)編譯程序產(chǎn)生一個三元式時，就查看三元式表中是否存在該三元式，若存在，則不再重復(fù)填入三元式表，而只是將該三元式的序號填入三元碼標(biāo)中。如上例中的三元式（1）（，y，z），其序號（1）在間接碼表中出現(xiàn)了兩次，而該三元式在三元式表中實(shí)際只出現(xiàn)一次。

第二十三頁，共五十五頁，2022年，8月28日1.四元式在編譯過程產(chǎn)生的各種中間語言中，四元式是比較普遍采用的一種形式。與三元式類似，四元式由四個部分組成，算符op，運(yùn)算對象arg1和arg2，運(yùn)算結(jié)果t。四元式的一般格式為：（i）（op，arg1，arg2，t）其中，（i）為序號，運(yùn)算對象和運(yùn)算結(jié)果可以是用戶自己定義的變量，也可以是編譯程5.3.3四元式和三地址碼第二十四頁，共五十五頁，2022年，8月28日序引進(jìn)的臨時變量，運(yùn)算對象還可以是常數(shù)。例如a:=b＋cd的四元式表示如下:

（1）（，c，d，t1）（2）（＋，b，t1，t2）（3）（:=，t2，—，a）

四元式和三元式在形式上很相似，不同之處主要在于對中間結(jié)果的引用方式。也就是說，四元式之間的聯(lián)系是通過引入臨時變量來實(shí)現(xiàn)，而三元式則是通過三元式編號來傳遞中間結(jié)果的。

第二十五頁，共五十五頁，2022年，8月28日2.三地址碼就像樹形表示和三元式一樣，三地址代碼也可以看成是四元式的另一種表示方式，它比四元式更直觀、更易于理解。三地址碼的一般格式為t:=arg1oparg2其中t，arg1，arg2，op的含義與四元式同。這其實(shí)就是一個賦值語句，只是與賦值語句不同的是：在三地址碼中賦值符號的右邊最多只能有一個運(yùn)算符。第二十六頁，共五十五頁，2022年，8月28日§5.4自底向上語法制導(dǎo)翻譯

語法制導(dǎo)翻譯分為自底向上和自底向下兩種。自底向上語法制導(dǎo)翻譯方法就是在自底向上語法分析過程中逐步執(zhí)行語義規(guī)則。也就是在每次歸約的同時執(zhí)行相應(yīng)的語義動作。

簡單算術(shù)表達(dá)式和賦值語句是指不含數(shù)組元素、記錄等復(fù)雜數(shù)據(jù)結(jié)構(gòu)的算術(shù)表達(dá)式和賦值語句。5.4.1簡單算術(shù)表達(dá)式和賦值語句的翻譯第二十七頁，共五十五頁，2022年，8月28日布爾表達(dá)式也叫邏輯表達(dá)式，是由布爾運(yùn)算符和具有邏輯值的運(yùn)算對象構(gòu)成。布爾運(yùn)算符有三個，即not、and和or（或者表示為、和）。布爾運(yùn)算符的優(yōu)先順序（從高到低）為、和，和服從左結(jié)合，為一目運(yùn)算符。具有邏輯值的運(yùn)算對象可以是邏輯表達(dá)式，也可以式關(guān)系表達(dá)式或者常量。關(guān)系表達(dá)式是最簡單的邏輯表達(dá)式，運(yùn)算對象為算術(shù)表達(dá)式。關(guān)系運(yùn)算符有＞、＜、＝、5.4.2布爾表達(dá)式的翻譯第二十八頁，共五十五頁，2022年，8月28日≥、≤、≠等等，關(guān)系運(yùn)算符的優(yōu)先級相同，但運(yùn)算優(yōu)先級較低。在程序設(shè)計(jì)語言中，布爾表達(dá)式的作用有兩個方面，其一是計(jì)算布爾值，其二是作為控制流語句（如ifEthenS1elseS2，whileEdo等）中的條件表達(dá)式，用來控制程序轉(zhuǎn)向。計(jì)算布爾表達(dá)式的計(jì)值方法一般有兩種，第一種方法是與算術(shù)表達(dá)式的計(jì)值方法相同，即按照表達(dá)式的運(yùn)算順序，逐步計(jì)算出各個第二十九頁，共五十五頁，2022年，8月28日部分的值，最后得出整個表達(dá)式的值。下面我們用1表示邏輯值true，用0表示邏輯值false，那么布爾表達(dá)式1or（0andnot0）and1的計(jì)值過程為:1or（0andnot0）and1=1or（0and1）and1=1or0and1=1or0=1

第二種計(jì)算方法是采取優(yōu)化措施，只計(jì)算部分表達(dá)式，如要計(jì)算E1orE2，若計(jì)算出E1的值為1，那么E2值就無需計(jì)算，因?yàn)椴还蹺2的值如何，E1orE2的值都為1。第三十頁，共五十五頁，2022年，8月28日當(dāng)然，對布爾表達(dá)式采用不同的計(jì)值方法，與之相應(yīng)的翻譯方法也不同。按照布爾表達(dá)式的第一種計(jì)值方法。布爾表達(dá)式E1orE2andnotE3翻譯成的四元式序列可以表示為（1）tl:=notE3（2）t2:=E2andtl（3）t3:=E1ort2

如果E1是一個關(guān)系表達(dá)式，如A＞B，那么我們可以把它看成與之等價的條件語句第三十一頁，共五十五頁，2022年，8月28日ifA＞Bthen1else0來進(jìn)行處理，翻譯成的四元式序列為：（l）ifa＞bgoto（4）（2）t:=0（3）goto（5）（4）t:=1（5）…

其中用臨時變量t存放布爾表達(dá)式a＞b的值，（5）為后續(xù)的四元式序號。

第三十二頁，共五十五頁，2022年，8月28日當(dāng)布爾表達(dá)式出現(xiàn)在控制語句（如if-then；if-then-else和while-do等）中用做條件控制時，布爾表達(dá)式的作用就不僅僅是計(jì)值了，更重要的是決定程序控制流的轉(zhuǎn)向。三種控制語句的語法及其代碼結(jié)構(gòu)如下控制結(jié)構(gòu)語法if-thenifEthenS1if-then-elseifEthenS1elseS2while-dowhileEdoS1第三十三頁，共五十五頁，2022年，8月28日布爾表達(dá)式E的值（真或假）決定著控制流的轉(zhuǎn)向，我們把E取真值和取假值時的兩個出口分別叫做真出口和假出口，出口的目標(biāo)分別叫E.true和E.false。三種控制語句的代碼結(jié)構(gòu)E的代碼S1的代碼E的代碼S1的代碼S2的代碼E的代碼S1的代碼TFFFTT

if-then

if-then-else

while-do第三十四頁，共五十五頁，2022年，8月28日那么，對于E為aropb的形式生成代碼為:ifaropbgotoE.truegotoE.false值得注意的是，對于E為E1orE2的形式的情況，如果E1為真，則E為真，即E1的真出口和E的真出口一樣，無需考慮E2；如果E1為假，就必須計(jì)算E2的值，這時E1的假出口就是E2代碼的第一個四元式標(biāo)號，這時E2和E具有相同的真、假出口。

第三十五頁，共五十五頁，2022年，8月28日例5.4：

布爾表達(dá)式a<borc>d可以翻譯為如下四元式序列:（1）ifa<bgotoE.true（2）goto（3）（3）ifc>dgotoE.truegotoE.false例5.4：分析語句ifa<borc>dthenS1elseS2

分析可知，當(dāng)a<b為真時，可直接執(zhí)行S1語句序列，不需要再考慮c>d；但是，若a<b為假時，則第三十六頁，共五十五頁，2022年，8月28日需要計(jì)算c>d是否為真，若c>d為真，則執(zhí)行S1語句序列，若c>d為假，則執(zhí)行S2語句序列。所以，當(dāng)a<b與c>d分別為真時，程序控制流的轉(zhuǎn)向是一致的，即具有相同真出口。根據(jù)上述分析可得到如下四元式：（1）ifa<bgoto（5）（2）goto（3）（3）ifc>dgoto（5）（4）goto（p＋1）（5）（關(guān)于S1的四元式序列）……（p）goto（q）第三十七頁，共五十五頁，2022年，8月28日（p＋1）（關(guān)于S2的四元式序列）……（q）（控制語句的后繼四元式序列）分析可知，上述（5）是整個布爾表達(dá)式的真出口，但是在生成（1）（3）的時候，地址（5）是未知的，必須要等到將整個布爾表達(dá)式的四元式產(chǎn)生完畢后才知道。所以這個地址需要回填。同理，（p＋1）是假出口，在生成（4）的時候該地址也是未知的，因此也需要回填。為了記錄需要回填地址的四元式，通常采用“拉鏈”的辦法：把需要回填E.true和E.false的四元式分別形成一條鏈，分別叫做“真”鏈和“假”鏈。

第三十八頁，共五十五頁，2022年，8月28日考慮上述四元式序列中，真鏈的形成過程：（1）ifa<bgotoE.true……（3）ifc>dgotoE.true……則拉鏈如下（1）ifa<bgoto（0）……（3）ifc>dgoto（1）其中，地址（3）稱作鏈?zhǔn)祝?作為鏈尾標(biāo)志，即地址（1）為鏈尾。第三十九頁，共五十五頁，2022年，8月28日在語法制導(dǎo)翻譯中，為及時回填四元式中真假出口信息，需用到下列數(shù)據(jù)結(jié)構(gòu)1.用E.true和E.false分別表示"真"鏈和"假"鏈；用next指向下一四元式的地址，next的初值為1，每生成一個四元式，其值自動累加1。2.用變量E.scode表示表達(dá)式E的第一個四元式序號。3.函數(shù)backpatch（p，t），功能是把p所鏈接的每個四元式的第四區(qū)段回填為t。4.函數(shù)merge（p1，p2），其功能是將以p1和p2為鏈?zhǔn)椎膬蓷l鏈合并為1條，并返回合并后的鏈?zhǔn)字?。第四十頁，共五十五頁?022年，8月28日控制語句是指程序設(shè)計(jì)語言中的if-then，if-then-else，while-do等含條件轉(zhuǎn)移的語句。如將if語句文法改寫為G[S]：（1）S→CS1

（2）S→TpS2

（3）C→ifEthen

（4）Tp→CS1elsewhile-do語句文法可改寫為G[S]:

（1）S→WdS15.4.5簡單說明語句的翻譯第四十一頁，共五十五頁，2022年，8月28日（2）Wd→WEdo

（3）W→while那么語句while（A>B）doif（C>D）thenY:=X＋1將被翻譯成如下一組四元式:ifA>Bgoto（3）(1)

goto（8）(2)

ifC>Dgoto（5）(3)

goto（1）(4)

T:=X＋1(5)

Y:=T(6)

goto（1）第四十二頁，共五十五頁，2022年，8月28日比較常見的兩種循環(huán)語句：while-do語句和for循環(huán)語句。while-do語句已經(jīng)在上一節(jié)中介紹，for循環(huán)語句，一般形式為:fori:=E1stepE2untilE3doSlt為循環(huán)控制變量，E1是i的初值，E2為步長，E3是i的終值，S1是循環(huán)體。語句代碼結(jié)構(gòu)見下圖：

5.4.4循環(huán)語句的翻譯第四十三頁，共五十五頁，2022年，8月28日對于循環(huán)語句:fori:=1step2untilendox:=y＋z圖5.16for循環(huán)語句的代碼結(jié)構(gòu)i:=E1i≤E3?FTi:=i+E2

S1的代碼第四十四頁，共五十五頁，2022年，8月28日可以翻譯成如下四元式序列：1

i:=12

goto43

i:=i＋24

ifi≤ngoto65

goto1086

t:=y＋z7

x:=t8

goto3第四十五頁，共五十五頁，2022年，8月28日說明語句有常量說明語句、變量說明語句、類型說明語句、過程說明語句等等。說明語句的功能就是用來定義各種形式的有名實(shí)體，如常量、變量、過程、函數(shù)、數(shù)組、記錄等等，在編譯過程中，這些被定義的實(shí)體的名字和性質(zhì)被登記在符號表中，以便編譯程序及時檢查實(shí)體的引用和說明是否一致。簡單說明語句可用語法定義如下：D→integer〈namelist〉5.4.5簡單說明語句的翻譯第四十六頁，共五十五頁，2022年，8月28日

D→real〈namelist〉namelist→〈namelist〉，idnamelist→id其中關(guān)鍵字integer和real分別表示整型、實(shí)型，用來定義后繼列表中一組名字的性質(zhì)（類型）。這里，對簡單說明語句的翻譯，就是要將被定義的實(shí)體的名字及其性質(zhì)登錄到符號表中去。按照自底向上的方法對上述形式的文法進(jìn)行制導(dǎo)翻譯時，顯然存在著這樣一個問題，即我們必須第四十七頁，共五十五頁，2022年，8月28日首先用一個隊(duì)列或者棧把所有的名字都保存下來形成一個串namelist，然后再把它們的性質(zhì)成批登記到符號表。這樣做，無疑給系統(tǒng)帶來了額外的開銷，增加了系統(tǒng)的負(fù)擔(dān)。于是，我們把上述的文法進(jìn)行如下改寫:D→D1，idD→integeridD→realid這樣，每當(dāng)讀進(jìn)一個id時，就可以及時地把它的性質(zhì)登記到符號表中，從而避免了將id集中起來再成批登記所帶來的麻煩。為改寫后的文法中每個產(chǎn)生式定義相應(yīng)的語義規(guī)則：定義一個過第四十八頁，共五十五頁，2022年，8月28日程put（id，A），把名字id及性質(zhì)A登錄到符號表；給非終結(jié)符D定義語義變量D.ATT，來記錄和傳遞說明語句引入的id性質(zhì)，如real或integer。（1）D→integerid{put（id，integer）；

D.ATT:=integer}（2）D→realid{put（id，real）；

D.ATT:=real}（3）D→D1，id{put（id，D1.ATT）；

D.ATT:=D1.ATT}

第四十九頁，共五十五頁，2022年，8月28日數(shù)組是用來存儲邏輯上相關(guān)的同類型數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。數(shù)