第八章 語法制導翻譯

第八章語法制導翻譯和中間代碼生成8.1概述8.2屬性文法和語法制導翻譯8.3中間代碼概述語義處理程序設計語言的語義

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

動態(tài)語義

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

法

分

析

后

的

源

程

序

T

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

指稱語義學

（denotationalsemantics）

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

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

屬性有兩種

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

一個屬性文法的例子例8.1P156非終結符E、T及F都有一個綜合屬性val,符號digit有一個綜合屬性，它的值由詞法分析器提供。與產生式L→En對應的語義規(guī)則僅僅是打印由E產生的算術表達式的值的一個過程，我們可認為這條規(guī)則定義了L的一個虛屬性。某些非終結符加下標是為了區(qū)分一個產生式中同一非終結符多次出現(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產生式設表達式為3＊5+4，則語義動作打印數(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的帶注釋的分析樹繼承屬性一個結點的繼承屬性值是由此結點的父結點和/或兄弟結點的某些屬性來決定的。例8.2繼承屬性L.in生產式語義規(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，，語法制導的翻譯一個翻譯是符號串對的一個集合。在一個編譯程序定義的翻譯中，符號串對是源程序和目標程序。各個編譯階段定義一個翻譯，詞法分析：（字符串，單詞串）語法分析：（單詞串，語法樹）代碼生成（語法樹，匯編語言）設是輸入字母表且是輸出字母表。定義由語言L1*到語言L2*的一個翻譯是由*到*的一個關系T,使得T的定義域為L1且T的值域為L2。使(x,y)∈T的句子y叫做x的一個輸出.語法制導的翻譯直觀地說，一個語法制導翻譯的基礎是一個文法，其中翻譯成分依附在每一產生式上。

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

翻譯規(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

)

源程序的一種內部表示，不依賴目標機的結構，易于機械生成

目

標代碼的中間表示。為什么要此階段？邏輯結構清楚；利于不同目標機上實現(xiàn)同一種語言；

利于進行與機器無關的優(yōu)化

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

四元式

三元式

間接三元式

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

:

result:=arg1op

arg2語義屬性：,E.place

函數(shù)：lookup();

過程：emit(t:=arg1oparg2);

newtemp;

產生式和語義描述：(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;