第八章 語法制導(dǎo)翻譯

第八章語法制導(dǎo)翻譯和中間代碼生成8.1概述8.2屬性文法和語法制導(dǎo)翻譯8.3中間代碼概述語義處理程序設(shè)計(jì)語言的語義

靜態(tài)語義是對(duì)程序約束的描述，這些約束無法通過抽象語法規(guī)則來妥善地描述，實(shí)質(zhì)上就是語法規(guī)則的良形式條件，它可以分為類型規(guī)則和作用域/可見性規(guī)則兩大類類型相容性變量先聲明后引用名稱相關(guān)要求

動(dòng)態(tài)語義

程序單位描述的計(jì)算編譯程序的語義處理工作靜態(tài)語義審查解釋執(zhí)行動(dòng)態(tài)語義（計(jì)算）生成代碼...語

法

分

析

后

的

源

程

序

T

語義處理概述語義形式化語義建模文法模型----屬性文法命令式或操作式模型-----操作語義學(xué)應(yīng)用式模型-----指稱語義學(xué)公理式模型-----公理語義學(xué)操作語義學(xué)操作語義學(xué)，是形式語義學(xué)的一個(gè)分支。程序設(shè)計(jì)語言的實(shí)施是在具體的計(jì)算機(jī)系統(tǒng)中按照語言的語義編制語言的翻譯程序，將語言中各個(gè)成分翻譯成計(jì)算機(jī)系統(tǒng)中相應(yīng)的一組操作。語言在計(jì)算機(jī)系統(tǒng)中的一種實(shí)施一旦完成，那么對(duì)這個(gè)計(jì)算機(jī)系統(tǒng)而言，語言各個(gè)成分的含義也就完全確定了。因此語言的實(shí)施也可用來定義語言的語義，即將語言成分所對(duì)應(yīng)的計(jì)算機(jī)系統(tǒng)的操作作為語言成分的語義，這種語義被稱作操作語義。由于語言的語義應(yīng)該是標(biāo)準(zhǔn)的，不應(yīng)依附于一個(gè)特定的計(jì)算機(jī)和一種具體的實(shí)施，因此操作語義學(xué)是用解釋執(zhí)行程序的抽象的機(jī)器來定義語言的語義。

指稱語義學(xué)

（denotationalsemantics）

形式語義學(xué)的一個(gè)分支。人們用程序設(shè)計(jì)語言編制程序，命令計(jì)算機(jī)系統(tǒng)去加工數(shù)據(jù)。不同的計(jì)算機(jī)系統(tǒng)有不同的結(jié)構(gòu)，因此對(duì)同一個(gè)命令的執(zhí)行過程可以不同，但最終效果應(yīng)該相同。指稱語義學(xué)方法認(rèn)為不應(yīng)該將程序設(shè)計(jì)語言中各個(gè)成分的執(zhí)行過程計(jì)入語言成分的語義中。語言成分的語義，應(yīng)該是執(zhí)行語言成分所要得到的最終效果。這是語言成分所要表達(dá)的含義，是語言成分本身所固有的，不因計(jì)算機(jī)系統(tǒng)的不同而改變。執(zhí)行語言成分產(chǎn)生的最終效果被看作是語言成分的所指，稱作為語言成分的指稱物。這種語義學(xué)以語言成分的指稱物作為語言成分的語義，故名為指稱語義學(xué)。指稱語義學(xué)中用于定義語義的指稱物多數(shù)是傳統(tǒng)的數(shù)學(xué)對(duì)象，如整數(shù)、集合、映象等，故早期又稱為數(shù)學(xué)語義學(xué)。這一名稱容易使人誤認(rèn)為其他形式語義學(xué)分支是非數(shù)學(xué)的，后已不再使用。公理語義學(xué)形式語義學(xué)的一個(gè)分支。不同的人在了解程序的含義時(shí)有不同的要求。公理語義學(xué)方法就是研究如何將這些不同的要求形式化，并根據(jù)這些要求嚴(yán)格給出程序設(shè)計(jì)語言的有關(guān)語義。屬性文法

表達(dá)式文法E—>T+T|TorT

T—>n|bET1+T2

{T1.type=intT2.type=T1.type E.type:=int}E

T1orT2

{T1.type=bool T2.type=T1.typeE.type:=bool}Tn{T.type:=int}Tb{T.type:=bool}屬性文法和語法制導(dǎo)翻譯雖然形式語義學(xué)(如指稱語義學(xué)、公理語義學(xué)、操作語義學(xué)等)的研究已取得了許多重大的進(jìn)展，但目前在實(shí)際應(yīng)用中比較流行的語義描述和語義處理的方法主要還是屬性文法和語法制導(dǎo)翻譯方法屬性文法屬性文法(attributegrammar)是一個(gè)三元組:A=(G,V,F),其中G:是一個(gè)上下文無關(guān)文法V:有窮的屬性集,每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號(hào)相關(guān)信息，如它的類型、值、代碼序列、符號(hào)表內(nèi)容等等.屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。屬性加工的過程即是語義處理的過程。F:關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則(稱為語義規(guī)則).斷言或語義規(guī)則與一個(gè)產(chǎn)生式相聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性.

屬性有兩種

繼承的和綜合的屬性屬性通常分為兩類：綜合屬性和繼承屬性。簡(jiǎn)單地說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給定的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算或者由生計(jì)算器的參數(shù)提供。AX1X2…XnA的綜合屬性,計(jì)算S(A):=f(I(X1),…,I(Xn))Xj的繼承屬性,計(jì)算T(Xj):=f(I(A),...I(Xn))1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始符號(hào)沒有繼承屬性.2)終結(jié)符只有綜合屬性.在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為b:=f(c1,c2…ck)這里，f是一個(gè)函數(shù)，而且或者 （1）b是A的一個(gè)綜合屬性并且c1,c2…ck是產(chǎn)生式右邊文法符號(hào)的屬性;或者 （2）b是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且c1,c2…ck是A或產(chǎn)生式右邊任何文法符號(hào)的屬性。在兩種情況下，我們都說屬性b依賴于屬性c1,c2…ck。

一個(gè)屬性文法的例子例8.1P156非終結(jié)符E、T及F都有一個(gè)綜合屬性val,符號(hào)digit有一個(gè)綜合屬性，它的值由詞法分析器提供。與產(chǎn)生式L→En對(duì)應(yīng)的語義規(guī)則僅僅是打印由E產(chǎn)生的算術(shù)表達(dá)式的值的一個(gè)過程，我們可認(rèn)為這條規(guī)則定義了L的一個(gè)虛屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)語義規(guī)則

LEEE1+TETTT1*FTFF(E)FdigitPrint(E.val)

E.val:=E1.val+T.val

E.val:=T.val

T.val:=T1.valF.val

T.val:=F.valF.val:=E.valF.val:=digit.lexval產(chǎn)生式設(shè)表達(dá)式為3＊5+4，則語義動(dòng)作打印數(shù)值19.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹繼承屬性一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性來決定的。例8.2繼承屬性L.in生產(chǎn)式語義規(guī)則DTL

Tint

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)

DL.in=realL.in=realL.in=realT.type=realrealid2id1id3.Realid1,id2,id3，，語法制導(dǎo)的翻譯一個(gè)翻譯是符號(hào)串對(duì)的一個(gè)集合。在一個(gè)編譯程序定義的翻譯中，符號(hào)串對(duì)是源程序和目標(biāo)程序。各個(gè)編譯階段定義一個(gè)翻譯，詞法分析：（字符串，單詞串）語法分析：（單詞串，語法樹）代碼生成（語法樹，匯編語言）設(shè)是輸入字母表且是輸出字母表。定義由語言L1*到語言L2*的一個(gè)翻譯是由*到*的一個(gè)關(guān)系T,使得T的定義域?yàn)長(zhǎng)1且T的值域?yàn)長(zhǎng)2。使(x,y)∈T的句子y叫做x的一個(gè)輸出.語法制導(dǎo)的翻譯直觀地說，一個(gè)語法制導(dǎo)翻譯的基礎(chǔ)是一個(gè)文法，其中翻譯成分依附在每一產(chǎn)生式上。

例8.5：把下述產(chǎn)生式定義的算術(shù)表達(dá)式映射到后綴波蘭表示：EE+TETTTFTFF(E)FaE=ET+E=TT=TFT=FF=EF=a產(chǎn)生式

翻譯規(guī)則

確定輸入a+aa的輸出：

(E,E)(E+T,ET+)

(T+T,TT+)

(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+).

.

.

何謂中間代碼

(

Intermediatecode

)

(

Intermediaterepresentation

)

(

Intermediatelanguage

)

源程序的一種內(nèi)部表示，不依賴目標(biāo)機(jī)的結(jié)構(gòu)，易于機(jī)械生成

目

標(biāo)代碼的中間表示。為什么要此階段？邏輯結(jié)構(gòu)清楚；利于不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語言；

利于進(jìn)行與機(jī)器無關(guān)的優(yōu)化

；這些內(nèi)部形式也能用于解釋。中間代碼的幾種形式逆波蘭

四元式

三元式

間接三元式

樹中間代碼例:A+B*(C-D)+E/(C-D)^N例:A+B*(C-D)+E/(C-D)^N例:A+B*(C-D)+E/(C-D)^N簡(jiǎn)單賦值語句的(四元式）翻譯四元式形式

:

result:=arg1op

arg2語義屬性：,E.place

函數(shù)：lookup();

過程：emit(t:=arg1oparg2);

newtemp;

產(chǎn)生式和語義描述：(1)Sid:=E

{P:=lookup

()

;ifPnilthenemit(P“:=”E.place)

elseerror}(op,arg1,arg2,result)或(2)EE1+E2

{E.place:=newtemp;emit(E.place“:=”E1.place“+”E2.place)}(3)E-E1

{E.place:=newtemp;