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

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

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

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

法

分

析

后

的

源

程

序

T

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

指稱(chēng)語(yǔ)義學(xué)

（denotationalsemantics）

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

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

屬性有兩種

繼承的和綜合的屬性屬性通常分為兩類(lèi)：綜合屬性和繼承屬性。簡(jiǎn)單地說(shuō)，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。出現(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é)符既可有綜合屬性也可有繼承屬性，但文法開(kāi)始符號(hào)沒(méi)有繼承屬性.2)終結(jié)符只有綜合屬性.在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語(yǔ)義規(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)的屬性。在兩種情況下，我們都說(shuō)屬性b依賴(lài)于屬性c1,c2…ck。

一個(gè)屬性文法的例子例8.1P156非終結(jié)符E、T及F都有一個(gè)綜合屬性val,符號(hào)digit有一個(gè)綜合屬性，它的值由詞法分析器提供。與產(chǎn)生式L→En對(duì)應(yīng)的語(yǔ)義規(guī)則僅僅是打印由E產(chǎn)生的算術(shù)表達(dá)式的值的一個(gè)過(guò)程，我們可認(rèn)為這條規(guī)則定義了L的一個(gè)虛屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)語(yǔ)義規(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，則語(yǔ)義動(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的帶注釋的分析樹(shù)繼承屬性一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性來(lái)決定的。例8.2繼承屬性L(fǎng).in生產(chǎn)式語(yǔ)義規(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，，語(yǔ)法制導(dǎo)的翻譯一個(gè)翻譯是符號(hào)串對(duì)的一個(gè)集合。在一個(gè)編譯程序定義的翻譯中，符號(hào)串對(duì)是源程序和目標(biāo)程序。各個(gè)編譯階段定義一個(gè)翻譯，詞法分析：（字符串，單詞串）語(yǔ)法分析：（單詞串，語(yǔ)法樹(shù)）代碼生成（語(yǔ)法樹(shù)，匯編語(yǔ)言）設(shè)是輸入字母表且是輸出字母表。定義由語(yǔ)言L(fǎng)1*到語(yǔ)言L(fǎng)2*的一個(gè)翻譯是由*到*的一個(gè)關(guān)系T,使得T的定義域?yàn)長(zhǎng)1且T的值域?yàn)長(zhǎng)2。使(x,y)∈T的句子y叫做x的一個(gè)輸出.語(yǔ)法制導(dǎo)的翻譯直觀(guān)地說(shuō)，一個(gè)語(yǔ)法制導(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)部表示，不依賴(lài)目標(biāo)機(jī)的結(jié)構(gòu)，易于機(jī)械生成

目

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

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

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

四元式

三元式

間接三元式

樹(shù)中間代碼例: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)單賦值語(yǔ)句的(四元式）翻譯四元式形式

:

result:=arg1op

arg2語(yǔ)義屬性：,E.place

函數(shù)：lookup();

過(guò)程：emit(t:=arg1oparg2);

newtemp;

產(chǎn)生式和語(yǔ)義描述：(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;