第6章屬性文法

1詞法分析與語(yǔ)法分析是編譯程序的一部分。在早期的一些編譯程序中，是在語(yǔ)法分析的基礎(chǔ)上根據(jù)源程序中各語(yǔ)法成份的語(yǔ)義，直接產(chǎn)生機(jī)器語(yǔ)言或匯編語(yǔ)言形式的目標(biāo)代碼。現(xiàn)在的編譯系統(tǒng)一般都將經(jīng)過(guò)語(yǔ)法分析的源程序先翻譯為某種形式的中間語(yǔ)言代碼，然后再將其翻譯為目標(biāo)代碼。

優(yōu)點(diǎn)：使編譯程序各組成部分功能更單一;使得編譯程序的邏輯結(jié)構(gòu)更為清晰，從而使編譯程序更易于編寫(xiě)與調(diào)整;同時(shí)為代碼優(yōu)化和程序的可移植性提供了條件

引言后面要討論的中間代碼生成，是指把單詞符號(hào)串形式的源程序轉(zhuǎn)換為另一種等價(jià)的便于代碼優(yōu)化處理和目標(biāo)代碼生成的表示方法。

目前常見(jiàn)的中間語(yǔ)言有逆波蘭表示、三元式、四元式等等。

遺憾的是，中間代碼生成與語(yǔ)言的語(yǔ)義密切相關(guān)，而語(yǔ)義的形式化描述是一件非常困難的事情;存在一種稱(chēng)為語(yǔ)法制導(dǎo)翻譯的模式，這種模式實(shí)際上是對(duì)上下文無(wú)關(guān)文法的一種擴(kuò)充。方法:對(duì)文法中的每個(gè)產(chǎn)生式都附加一個(gè)語(yǔ)義動(dòng)作或語(yǔ)義子程序,在語(yǔ)法分析過(guò)程中，每當(dāng)需要使用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約，語(yǔ)法分析程序除執(zhí)行相應(yīng)的語(yǔ)法分析動(dòng)作外，還要執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作或調(diào)用相應(yīng)的語(yǔ)義子程序。

引言(續(xù))這種模式既把語(yǔ)法分析與語(yǔ)義處理分開(kāi)，又令其平行地進(jìn)行，讓其在同一遍掃描中同時(shí)完成語(yǔ)法分析和語(yǔ)義處理兩項(xiàng)工作。由此可見(jiàn)，抽象文法符號(hào)的具體語(yǔ)義信息，是在與語(yǔ)法分析同步的語(yǔ)義處理過(guò)程中獲取和加工的。文法符號(hào)X的語(yǔ)義信息我們稱(chēng)之為語(yǔ)義屬性或簡(jiǎn)稱(chēng)為屬性（Attributes）。我們用形如X.ATTR的記號(hào)來(lái)表示文法符號(hào)X的相關(guān)語(yǔ)義屬性。如果一個(gè)文法符號(hào)X在一產(chǎn)生式中多次出現(xiàn)，為了在語(yǔ)義上能夠?qū)ζ溥M(jìn)行區(qū)分，可添加不同的上標(biāo)。文法符號(hào)及其語(yǔ)義屬性例如,文法G[E]:產(chǎn)生式

語(yǔ)義子程序E→E(1)+T {E.Val=E(1).val+T.val;}E→T {E.Val=T.Val;}T→digit {T.Val=digit;}為了能在語(yǔ)法分析過(guò)程中平行地進(jìn)行語(yǔ)義處理，可在語(yǔ)法分析棧旁邊并行地設(shè)置一個(gè)語(yǔ)義信息棧

語(yǔ)法分析棧語(yǔ)義分析棧TT.Val+‘+’E……#

源語(yǔ)言程序中間代碼匯編代碼詞法分析語(yǔ)義分析語(yǔ)法分析中間代碼生成代碼生成在編譯中的邏輯階段前端處理后端處理語(yǔ)義處理語(yǔ)義處理（語(yǔ)義分析和中間代碼生成）源語(yǔ)言程序匯編代碼詞法分析語(yǔ)義分析語(yǔ)法分析代碼生成前端處理后端處理語(yǔ)義處理語(yǔ)義處理7第六章屬性文法和語(yǔ)法制導(dǎo)翻譯6.1

屬性文法6.2

基于屬性文法的處理方法6.3

S—屬性文法的自下而上計(jì)算6.4

L—屬性文法和自頂向下翻譯6.5自下而上計(jì)算繼承屬性86.1

屬性文法一、基本概念1.屬性廣義：用以描述事物或人的特征、性質(zhì)、品質(zhì)等等。狹義：代表與文法符號(hào)相關(guān)的信息，其信息值即為 屬性值。例如：其類(lèi)型、值、代碼序列、符號(hào)表內(nèi)容等。9（1）屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。6.1

屬性文法（2）屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程。（3）屬性綜合屬性： 繼承屬性：用于“自上而下”傳遞信息。用于“自下而上”傳遞信息。注:102.語(yǔ)義規(guī)則

為文法的每一個(gè)產(chǎn)生式配備的計(jì)算屬性的計(jì)算規(guī)則，稱(chēng)為語(yǔ)義規(guī)則。3.屬性文法

在上下文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)（終結(jié)符或非終結(jié)符）引進(jìn)一組屬性，且讓該文法中的重寫(xiě)規(guī)則附加上語(yǔ)義規(guī)則時(shí)，稱(chēng)該上下文無(wú)關(guān)文法為屬性文法。6.1

屬性文法注：語(yǔ)法制導(dǎo)翻譯是指在語(yǔ)法分析的過(guò)程中，完成附加在所使用的產(chǎn)生式上的語(yǔ)義規(guī)則所描述的動(dòng)作。屬性文法屬性文法(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)的屬性.

12二、基本規(guī)則1.語(yǔ)義規(guī)則的形式：產(chǎn)生式Aα的語(yǔ)義規(guī)則的形式為b:=f(c1,c2,…,ck)其中:(1)f是一個(gè)函數(shù);通常以表達(dá)式的形式出現(xiàn)

?屬性b依賴(lài)于屬性c1,c2,…,ck(2)或者b—A的綜合屬性，且c1,c2,…,ck是α中文法符號(hào)的屬性;6.1

屬性文法(3)或者b—α中某個(gè)文法符號(hào)的繼承屬性,

且c1,c2,…,ck是A或α中任何文法符號(hào)的屬性.b有兩種可能132.VT—VN的屬性(1)VT—

只有綜合屬性,由詞法分析器提供.6.1屬性文法(2)VN—

既可有綜合屬性也可有繼承屬性;

開(kāi)始符號(hào)S的所有繼承屬性作為屬性計(jì)算 前的初始值.出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給定的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算或者由屬性計(jì)算器的參數(shù)提供。

AX1X2…XnA的綜合屬性S(A)計(jì)算公式S(A):=f(I(X1),…,I(Xn))Xj的繼承屬性T(Xj)計(jì)算公式T(Xj):=f(I(A),...I(Xn))1)非終結(jié)符既可有綜合屬性也可有繼承屬性2)終結(jié)符只有綜合屬性,它們由詞法程序提供.153.屬性的計(jì)算/獲得(1)

產(chǎn)生式右邊的繼承屬性產(chǎn)生式左邊的綜合屬性(2)

產(chǎn)生式左邊的繼承屬性產(chǎn)生式右邊的綜合屬性由該產(chǎn)生式提供的計(jì)算規(guī)則計(jì)算獲得由其它產(chǎn)生式的屬性規(guī)則計(jì)算或由屬性計(jì)算器的參數(shù)提供6.1

屬性文法16例6.1:考慮非終結(jié)符Ａ，Ｂ和Ｃ，其中，Ａ有一個(gè)繼承屬性

ａ和一個(gè)綜合屬性ｂ，Ｂ有綜合屬性ｃ，Ｃ有繼承屬性ｄ。C.d:=B.c+1A.b:=A.a+B.c產(chǎn)生式ABC可能有規(guī)則：屬性A.a和B.c在其它地方計(jì)算。A.a—左部繼承屬性A.b—左部綜合屬性B.c—右部綜合屬性C.d—右部繼承屬性6.1

屬性文法17例6.2:

一個(gè)簡(jiǎn)單臺(tái)式計(jì)算器的屬性文法產(chǎn)生式語(yǔ)義規(guī)則LEnEE1+TETTT1*FTFF(E)FdigitPrint(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval6.1

屬性文法18三、綜合屬性1.語(yǔ)法樹(shù)中,一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定;2.通常使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語(yǔ)義規(guī)則計(jì)算綜合屬性的值.S—屬性文法：僅使用綜合屬性的屬性文法.6.1

屬性文法19例6.3:例6.2的表中定義的屬性文法說(shuō)明了一個(gè)臺(tái)式計(jì)算器，該計(jì)算器讀入一個(gè)可含數(shù)字、括號(hào)和+、*運(yùn)算符的算術(shù)表達(dá)式，并打印表達(dá)式的值，每個(gè)輸入行以n作為結(jié)束。假設(shè)表達(dá)式為3*5+4，后跟一個(gè)換行符n。程序打印數(shù)值19其帶注釋的語(yǔ)法樹(shù)6.1

屬性文法20LE.val=19

nE.val=15+

T.val=4T.val=15T.val=3*

F.val=5F.val=3digit.lexval=3digit.lexval=5digit.lexval=4F.val=4返回３*５+４ｎ的帶注釋的語(yǔ)法樹(shù)21四、繼承屬性1.語(yǔ)法樹(shù)中,一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)

和／或兄弟結(jié)點(diǎn)的某些屬性確定;2.用繼承屬性來(lái)表示程序設(shè)計(jì)語(yǔ)言結(jié)構(gòu)中的上下文依賴(lài)關(guān)系很方便.6.1

屬性文法22例6.４:帶繼承屬性L(fǎng).in的屬性文法產(chǎn)生式語(yǔ)義規(guī)則DTLTintTrealLL1,idLidaddtype(id.entry,L.in)T.type:=integerT.type:=realL1.in:=L.inL.in:=T.typeaddtype(id.entry,L.in)6.1

屬性文法23輸入串:realid1,id2,id3的帶注釋的語(yǔ)法樹(shù)DT.type=realL.in=realrealL.in=realL.in=real，id2id3，id124基于屬性文法的處理過(guò)程:單詞符號(hào)串語(yǔ)法分析語(yǔ)法分析樹(shù)遍歷計(jì)算例:輸入串 語(yǔ)法樹(shù) 依賴(lài)圖 語(yǔ)義規(guī)則的計(jì)算次序 進(jìn)行語(yǔ)義規(guī)則計(jì)算，得到翻譯結(jié)果6.2

基于屬性文法的處理方法25語(yǔ)法制導(dǎo)翻譯法語(yǔ)義規(guī)則的計(jì)算將有下列作用：

產(chǎn)生代碼，在符號(hào)表中存放信息，給出錯(cuò)誤信息或執(zhí)行其它動(dòng)作。由源程序的語(yǔ)法結(jié)構(gòu)所驅(qū)動(dòng)的處理方法。6.2

基于屬性文法的處理方法對(duì)輸入符號(hào)串的翻譯也就是根據(jù)語(yǔ)義規(guī)則進(jìn)行計(jì)算的結(jié)果。6.2

基于屬性文法的處理方法依賴(lài)圖樹(shù)遍歷一遍掃描27一、依賴(lài)圖1.定義：一個(gè)表示一棵語(yǔ)法樹(shù)中結(jié)點(diǎn)的繼承屬性和綜合屬性之間的相互依賴(lài)關(guān)系的有向圖。6.2

基于屬性文法的處理方法282.依賴(lài)圖的構(gòu)造方法（1）構(gòu)造依賴(lài)圖以前，先為每一個(gè)包含過(guò)程調(diào)

用的語(yǔ)義規(guī)則引入一個(gè)虛綜合屬性b，在每 一個(gè)語(yǔ)義規(guī)則均寫(xiě)成b=f（c1,c2,…,ck）的形式.（2）在依賴(lài)圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn).（3）若屬性b依賴(lài)于屬性c，則從屬性c的結(jié)點(diǎn)有 一條有向邊連到屬性b的結(jié)點(diǎn)。程序6.2基于屬性文法的處理方法29依賴(lài)圖的構(gòu)造方法for

語(yǔ)法樹(shù)中每一結(jié)點(diǎn)n

do

for

結(jié)點(diǎn)n的文法符號(hào)的每一個(gè)屬性

a

do

為a在依賴(lài)圖中建立一個(gè)結(jié)點(diǎn)；for

語(yǔ)法樹(shù)中每一結(jié)點(diǎn)n

do

for

結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)的每一個(gè)語(yǔ)義規(guī)則

b:=f（C1,C2,…,Ck）do

fori:=1tok

do

從Ci

結(jié)點(diǎn)到b結(jié)點(diǎn)構(gòu)造一條有向邊；返回6.2

基于屬性文法的處理方法30例6.5:AXY

?A.a:=f(X.x,Y.y) X.i:=g(A.a,Y.y)6.2

基于屬性文法的處理方法313.例題例6.6:

將下面的產(chǎn)生式應(yīng)用于語(yǔ)法樹(shù)中產(chǎn)生式 語(yǔ)義規(guī)則EE1+E2 E.val:=E1.val+E2.valEE1+

E2

valval val?

E.Val是從E1.val和E2.val綜合得出6.2

基于屬性文法的處理方法句子realid1，id2，id3的帶注釋的語(yǔ)法樹(shù)的依賴(lài)圖id1L,id2L,id3LrealTD4type5in6-addtype(id.entry,L.in)7in8addtype9in10

addtype1entry2entry3entry產(chǎn)生式

語(yǔ)義規(guī)則

D→TLL.in:=T.typeT→int T.type:=integerT→realT.type:=realL→L1,idL1.in:=L.inaddtype(id.entry,L.in)L→id addtype(id.entry,L.in)例6.7:例6.4中語(yǔ)法分析樹(shù)的依賴(lài)圖33４.屬性的計(jì)算次序：6.2

基于屬性文法的處理方法

一個(gè)依賴(lài)圖的任何拓?fù)渑判蚨冀o出一個(gè)語(yǔ)法樹(shù)中結(jié)點(diǎn)的語(yǔ)義規(guī)則計(jì)算的有效順序。注:在拓?fù)渑判蛑?在一個(gè)結(jié)點(diǎn)上，語(yǔ)義規(guī)則

b:=f(c1,c2,…,ck)中的屬性c1,c2,…,ck

在計(jì)算b以前是可用的。良定義的：若一個(gè)屬性文法不存在屬性之間的循環(huán)依賴(lài)關(guān)系，則稱(chēng)該文法為良定義的。屬性的計(jì)算次序一個(gè)依賴(lài)圖的任何拓?fù)渑判蚨冀o出一個(gè)語(yǔ)法樹(shù)中結(jié)點(diǎn)的語(yǔ)義規(guī)則計(jì)算的有效順序?qū)傩晕姆ㄕf(shuō)明的翻譯是很精確的基礎(chǔ)文法用于建立輸入符號(hào)串的語(yǔ)法分析樹(shù)根據(jù)語(yǔ)義規(guī)則建立依賴(lài)圖從依賴(lài)圖的拓?fù)渑判蛑?，我們可以得到?jì)算語(yǔ)義規(guī)則的順序輸入串語(yǔ)法樹(shù)依賴(lài)圖語(yǔ)義規(guī)則計(jì)算次序句子realid1，id2，id3的帶注釋的語(yǔ)法樹(shù)的依賴(lài)圖id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entrya4:=real;a5:=a4addtype(id3.entry,a5);a7:=a5;addtype(id2.entry,a7);a9:=a7addtype(id1.entry,a9);6.2

基于屬性文法的處理方法依賴(lài)圖樹(shù)遍歷一遍掃描37二、樹(shù)遍歷的屬性計(jì)算方法1.方法

A.前提：假設(shè)語(yǔ)法樹(shù)已經(jīng)建立起來(lái)了，且樹(shù)中已 有如下信息：開(kāi)始符號(hào)—繼承屬性 終結(jié)符——綜合屬性B.遍歷：以某種次序遍歷語(yǔ)法樹(shù)，直至計(jì)算出所有屬性.遍歷方法：深度優(yōu)先，從左到右6.2基于屬性文法的處理方法382.算法

While

還有未被計(jì)算的屬性do

VisitNode(S)

/*S是開(kāi)始符號(hào)*/procedureVisitNode(N:Node);begin

IfN是一個(gè)非終結(jié)符then

/*假設(shè)它的產(chǎn)生式為NX1…Xm*/

fori:=1tomdo

ifnotXi∈VTthen/*即Xi是非終結(jié)符*/

begin

計(jì)算Xi的所有能夠計(jì)算的繼承屬性;

VisitNode(Xi)

end;

計(jì)算N的所有能夠計(jì)算的綜合屬性end396.2

基于屬性文法的處理方法注：只要文法的屬性是非循環(huán)定義的，則每次掃描至少有一個(gè)屬性值被計(jì)算出來(lái)。40其中，S有繼承屬性a，綜合屬性b；X有繼承屬性c，綜合屬性d；Y有繼承屬性e，綜合屬性f；Z有繼承屬性h，綜合屬性g。3.舉例例6.9:考慮下表所給的屬性文法G。產(chǎn)生式語(yǔ)義規(guī)則SXYZXxYyZzZ.h:=S.aX.c:=Z.gS.b:=X.d-2Y.e:=S.bX.d:=2*X.cY.f:=Y.e*3Z.g:=Z.h+16.2基于屬性文法的處理方法41S:a=0XYZxy(a)z6.2

基于屬性文法的處理方法S:a=0XYZ：h=0g=1xyz(b)426.2

基于屬性文法的處理方法S:a=0,b=0X:c=1d=2YZ：h=0g=1xyz(c)S:a=0,b=0X:c=1d=2Y:e=0f=0Z：h=0g=1xyz(d)假設(shè)S.a的初始值為0，輸入串為xyzS:a=0XYZxyzZ:h=0g=1X:c=1d=2S:a=0,b=0Y:e=0f=0產(chǎn)生式 語(yǔ)義規(guī)則

S→XYZZ.h:=S.aX.c:=Z.gS.b:=X.d-2Y.e:=S.bX→xX.d:=2*X.cY→yY.f:=Y.e*3Z→zZ.g:=Z.h+16.2

基于屬性文法的處理方法依賴(lài)圖樹(shù)遍歷一遍掃描45三、一遍掃描的處理方法1.特點(diǎn)

在語(yǔ)法分析的同時(shí)計(jì)算屬性值，而不是語(yǔ)法分析構(gòu)造語(yǔ)法樹(shù)之后進(jìn)行屬性的計(jì)算，而且無(wú)需構(gòu)造實(shí)際的語(yǔ)法樹(shù)。注：采用該處理方法，當(dāng)一個(gè)屬性值不再用于計(jì)算其它屬性值時(shí)，編譯程序就不必再保留這個(gè)屬性值。如果需要，可把語(yǔ)義值存到文件中。6.2

基于屬性文法的處理方法462.相關(guān)因素：（1）所使用的語(yǔ)法分析方法 L-屬性文法—一遍掃描的自上而下分析

S-屬性文法—一遍掃描的自下而上分析6.2

基于屬性文法的處理方法（2）屬性的計(jì)算次序

473.語(yǔ)法制導(dǎo)翻譯

A.

在語(yǔ)法規(guī)則的制導(dǎo)下，通過(guò)計(jì)算語(yǔ)義規(guī)則，完成對(duì)輸入符號(hào)串的翻譯。6.2

基于屬性文法的處理方法

該產(chǎn)生式相應(yīng)的語(yǔ)義規(guī)則被計(jì)算，完成有關(guān)的語(yǔ)義分析和代碼產(chǎn)生工作。

由此可見(jiàn)，在該情況下，語(yǔ)法分析工作和語(yǔ)義規(guī)則的計(jì)算是穿插進(jìn)行的。即：自上而下分析中，一個(gè)產(chǎn)生式匹配輸入串成功時(shí)[語(yǔ)義規(guī)則自下而上分析中，一個(gè)產(chǎn)生式被用于進(jìn)行規(guī)約時(shí)被計(jì)算的時(shí)機(jī)]B.

為文法中每個(gè)產(chǎn)生式配上一組語(yǔ)義規(guī)則，并在語(yǔ)法分析的同時(shí)執(zhí)行這些語(yǔ)義規(guī)則。48四、抽象語(yǔ)法樹(shù)—AbstractSyntaxTree1.定義：注：抽象語(yǔ)法樹(shù)中，操作符和關(guān)鍵字都不作為葉結(jié)點(diǎn)出現(xiàn),而是把它們作為內(nèi)部結(jié)點(diǎn),即這些葉結(jié)點(diǎn)的父結(jié)點(diǎn).6.2

基于屬性文法的處理方法

在語(yǔ)法樹(shù)中去掉那些對(duì)翻譯不必要的信息，從而獲得更有效的源程序中間表示，這種經(jīng)變換后的語(yǔ)法樹(shù)稱(chēng)之為抽象語(yǔ)法樹(shù)。BS1S2if_then_elseS→ifBthenS1elseS23*5+4*54+3四、抽象語(yǔ)法樹(shù)—AbstractSyntaxTree6.2

基于屬性文法的處理方法502.如何建立表達(dá)式的抽象語(yǔ)法樹(shù)（1）方法：通過(guò)為每一個(gè)運(yùn)算分量或運(yùn)算符號(hào)都建立一個(gè)結(jié)點(diǎn)來(lái)為子表達(dá)式建立子樹(shù)；6.2

基于屬性文法的處理方法

運(yùn)算符號(hào)結(jié)點(diǎn)的各個(gè)子結(jié)點(diǎn)分別是表示該運(yùn)算符號(hào)的各個(gè)運(yùn)算分量的子表達(dá)式組成的子樹(shù)的根。51（2）抽象語(yǔ)法樹(shù)中每個(gè)結(jié)點(diǎn)可由包含幾個(gè)域的記錄 來(lái)實(shí)現(xiàn)6.2

基于屬性文法的處理方法運(yùn)算符號(hào)結(jié)點(diǎn)：一個(gè)域—

運(yùn)算符號(hào)其它域—

指向運(yùn)算符號(hào)分量的結(jié)點(diǎn)的指針結(jié)點(diǎn)：附加的域—存放結(jié)點(diǎn)的屬性值/指向?qū)傩灾档闹羔槨?2（3）建立帶有二目算符的表達(dá)式的抽象語(yǔ)法樹(shù)結(jié)點(diǎn) 的函數(shù)：

mknode(op,left,right)建立一個(gè)運(yùn)算符號(hào)結(jié)點(diǎn)，標(biāo)號(hào)是op，兩個(gè)域left 和right分別指向左子樹(shù)和右子樹(shù)。mkleaf(id,entry)建立一個(gè)標(biāo)識(shí)符結(jié)點(diǎn)，標(biāo)號(hào)為id，一個(gè)域entry指向標(biāo)識(shí)符

在符號(hào)表中的入口。mkleaf(num,ral)建立一個(gè)數(shù)結(jié)點(diǎn)，標(biāo)號(hào)為num，一個(gè)域val用于存放數(shù)的值。

每個(gè)函數(shù)均返回一個(gè)指向新建立結(jié)點(diǎn)的指針。6.2基于屬性文法的處理方法53例6.10:下面一系列函數(shù)調(diào)用建立了表達(dá)式a-4+c的抽象語(yǔ)法樹(shù)（如圖）。在這個(gè)序列中，p1,p2,…,p5是指向結(jié)點(diǎn)的指針，entrya和entryc分別是指向符號(hào)表中的標(biāo)識(shí)符a和c的指針。+-num4idtoentryforc6.2基于屬性文法的處理方法(1)p1:=mkleaf(id,entrya);(2)p2:=mkleaf(num,4);(3)p3:=mknode(‘-’,p1,p2);(4)p4:=mkleaf(id,entryc);(5)p5:=mknode(‘+’,p3,p4)idToentryfora54產(chǎn)生式語(yǔ)義規(guī)則E→E1+TE→E1-TE→TT→(E)T→idT→numE.nptr:=mkNode(‘+’,E1.nptr,T.nptr)E.nptr:=mkNode(‘-’,E1.nptr,T.nptr)E.nptr:=T.nptrE.nptr:=T.nptrT.nptr:=mkleaf(id,id.entry)T.nptr:=mkleaf(num,num.val)為表達(dá)式建立抽象語(yǔ)法樹(shù)的屬性文法6.2

基于屬性文法的處理方法55EnptrTnptrEnptrETnptrnumTnptrid+—id＋●

●

－●

●

id●id●num4帶注釋的語(yǔ)法分析樹(shù)ToentryforaToentryforc566.3

S—屬性文法的自下而上計(jì)算1.S—屬性文法

定義:（1）所有非終結(jié)符只具有綜合屬性；

（2）在一個(gè)產(chǎn)生式中，每個(gè)符號(hào)的各個(gè)綜合屬性的定義互不依賴(lài)。2.綜合屬性的計(jì)算

在分析輸入符號(hào)串的同時(shí)由自下而上的分析器來(lái)計(jì)算，分析器可以保存與棧中文法符號(hào)有關(guān)的綜合屬性值，每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號(hào)的屬性值來(lái)計(jì)算.573.S-屬性文法的翻譯器通?？山柚贚R分析器實(shí)現(xiàn)

在S-屬性文法的基礎(chǔ)上，LR分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。6.3S—屬性文法的自下而上計(jì)算產(chǎn)生式語(yǔ)義規(guī)則０）Ｌ→Ｅｐｒｉｎｔ（Ｅ.ｖａｌ）１）Ｅ→Ｅ1＋ＴＥ.ｖａｌ∶＝Ｅ1.ｖａｌ＋Ｔ.ｖａｌ２）Ｅ→ＴＥ.ｖａｌ∶＝Ｔ.ｖａl３）Ｔ→Ｔ1*ＦＴ.ｖａｌ∶＝Ｔ1.ｖａｌ×Ｆ.ｖａｌ４）Ｔ→FＴ.ｖａｌ∶＝F.ｖａｌ５）Ｆ→（Ｅ）Ｆ.ｖａｌ∶＝Ｅ.ｖａｌ６）Ｆ→ｄiｇiｔＦ.ｖａｌ:＝ｄｉｇｉｔ.ｌｅｘｖａｌLR分析器可以改造為一個(gè)翻譯器,增加語(yǔ)義棧

，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。

ＬＲ分析器模型總控程序outputInput#S1Xm…S1…X1S0#棧

狀態(tài)符號(hào)ACTIONGOTOLR分析表產(chǎn)生式表VmV1-

語(yǔ)義…S1S0VmV1-

２＋３*５的分析和計(jì)值過(guò)程步驟動(dòng)作狀態(tài)棧語(yǔ)義棧(值棧)符號(hào)棧余留輸入串１）０

－＃２＋3*５＃２）０５

－－＃2＋3*５＃３）ｒ６０３

－２＃Ｆ＋３*５＃４）ｒ４０２

－２＃Ｔ＋３*５＃５）ｒ２０１

－２＃Ｅ＋３*５＃６）０１６

－２－＃Ｅ＋３*５＃７）０１６５

－２－－＃Ｅ＋３

*５＃８）ｒ６０１６３

－２－３＃Ｅ＋Ｆ

*５＃９）ｒ４０１６９

－２－３＃Ｅ＋Ｔ

*５＃１０）０１６９７

－２－３－＃Ｅ＋Ｔ*

５＃１１）０１６９７５

－２－３－－＃Ｅ＋Ｔ*５＃１２）ｒ６０１６９７（１０）－２－３－５＃Ｅ＋Ｔ*Ｆ#１３）ｒ３０１６９－２－（１５）＃Ｅ＋Ｔ＃１４）ｒ１０１－（１７）＃Ｅ＃１５）接受614.分析棧Stateval6.3S—屬性文法的自下而上計(jì)算自底向上分析法中：?！娣乓呀?jīng)分析過(guò)的子樹(shù)的內(nèi)容

附加域—存放綜合屬性值數(shù)組State:

元素－一個(gè)指向LR(1)分析表的指針(索引）,

指向表中某個(gè)文法符號(hào).數(shù)組Val:

存放語(yǔ)法樹(shù)中與結(jié)點(diǎn)對(duì)應(yīng)的屬性值.注:(1)假定綜合屬性剛好在每次歸約前計(jì)算.

(2)若一個(gè)符號(hào)無(wú)綜合屬性,則數(shù)組val中相應(yīng)的元素就不定義.625.舉例L→EnE→E1+TE→TT→T1*FT→FF→(E)F→digit輸入stateval產(chǎn)生式輸入串

3*5+4n3*5+4n??

*5+4n33

*5+4nF3

*5+4nT3

5+4nT*3?

+4nT*53?5

+4nT15

+4nE15

4nE+15

?

+4nT*F3?5F→digitT→FF→digitT→T*FE→T63L→EnE→E1+TE→TT→T1*FT→FF→(E)F→digit輸入串

3*5+4n輸入stateval產(chǎn)生式

4nE+15

?

nE+415

?4

nE+F15

?4

nE+T15

?4

nE19

En19?

L19F→digitT→FE→E+TL→En5.舉例646.4L-屬性文法和自頂向下翻譯L-屬性文法1.定義:若屬性文法中每個(gè)產(chǎn)生式A→X1X2…Xn,

其相關(guān)的每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性:①或者是綜合屬性;②或者是Xj的一個(gè)繼承屬性且該繼承屬性?xún)H依賴(lài)于Xj左邊符號(hào)X1,X2,…,Xj-1的屬性和A的繼承屬性。則稱(chēng)該屬性文法為L(zhǎng)-屬性文法.652.特點(diǎn):6.4L-屬性文法和自頂向下翻譯L-屬性文法A.

該類(lèi)屬性文法允許我們通過(guò)一次遍歷就計(jì)算出所有屬性值.B.

可在自上而下語(yǔ)法分析的同時(shí)實(shí)現(xiàn)L-屬性文法的計(jì)算.C.S-屬性文法一定是L-屬性文法.666.4L-屬性文法和自頂向下翻譯一個(gè)非L-屬性文法產(chǎn)生式語(yǔ)義規(guī)則A→LMA→QRL.i=l(A.i)M.i=m(L.s)R.i=r(A.i)Q.i=q(R.s)A.s=f(Q.s)67一.翻譯模式1.翻譯模式的定義：

一種適合語(yǔ)法制導(dǎo)翻譯的語(yǔ)義描述形式,給出了使用語(yǔ)義規(guī)則進(jìn)行計(jì)算的次序,可把某些實(shí)現(xiàn)細(xì)節(jié)表示出來(lái).

形式:在翻譯模式中,和文法符號(hào)相關(guān)的屬性和語(yǔ)義規(guī)則,用{}括起來(lái),插入到產(chǎn)生式右部的合適位置上.例:E→TRR→addopT{pr(addop.lex)}

R1|ε

T→num{pr(num.val)}

6.4L-屬性文法和自頂向下翻譯68

為每一個(gè)語(yǔ)義規(guī)則建立一個(gè)包含賦值的動(dòng)作,并把這個(gè)動(dòng)作放在相應(yīng)的產(chǎn)生式右邊的末尾.6.4L-屬性文法和自頂向下翻譯2.翻譯模式的設(shè)計(jì)：

A.

只有綜合屬性時(shí),可以按如下方式建立翻譯模式:69B.若既有綜合屬性又有繼承屬性時(shí),則按如下方式建立翻譯模式:

①產(chǎn)生式右邊的符號(hào)的繼承屬性必須在這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來(lái).

②一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號(hào)的綜合屬性.

③產(chǎn)生式左邊非終結(jié)符的綜合屬性只有在它所引用的所有屬性都計(jì)算出來(lái)以后才能計(jì)算.計(jì)算這種屬性的動(dòng)作通?？煞旁诋a(chǎn)生式右端的末尾.

6.4L-屬性文法和自頂向下翻譯2.翻譯模式的設(shè)計(jì)：

70舉例:E→TRR→addopT{pr(addop.lex)}R1|ε

T

→num{pr(num.val)}

輸入：9－5＋2深度優(yōu)先遍歷后輸出：95－2＋ETRRR9Pr(‘9’)－TPr(‘－’)＋TPr(‘＋’)5Pr(‘5’)2Pr(‘2’)ε71二.自頂向下翻譯1.討論:

L-屬性文法在自頂向下分析中的實(shí)現(xiàn)6.4L-屬性文法和自頂向下翻譯自頂向下語(yǔ)法分析的前提是消除文法中的左遞歸.72E→E1+T{E.val:=E1.val+T.val}E→E1－T{E.val:=E1.val－T.val}E→T{E.val:=T.val}T→(E){T.val:=E.val}T→num{T.val:=num.val}E→T{R.i:=T.val}

R

{E.val:=R.s}R→+T{R1.i:=R.i+T.val}

R1

{R.s:=R1.s}R→－

T{R1.i:=R.i-T.val}

R1

{R.s:=R1.s}R→ε

{R.s:=R.i}T→(E){T.val:=E.val}T→num{T.val:=num.val}2.例題:

73計(jì)算表達(dá)式9－5＋2帶注釋語(yǔ)法樹(shù)i:

繼承屬性s:

綜合屬性ET.val=9R.i=9R.i=4R.i=6Num.val=9－T.val=5+T.val=2Num.val=2εNum.val=56.4L-屬性文法和自頂向下翻譯E.valR.sR.sR.s74A→A1Y{A.a=g(A1.a,Y.y}A→X

{A.a=f(X.x)}A→X{R.i:=f(X.x)}

R{A.a:=R.s}R→Y{R1.i=g(R.i,Y.y)}

R1{R.s:=R1.s}R→ε

{R.s:=R.i}6.4L-屬性文法和自頂向下翻譯

3.轉(zhuǎn)換左遞歸翻譯模式的一般方法：

消除左遞歸前:

消除左遞歸后:

75A.a=g(g(f(X.x),Y1.y),Y2.y)A.a=g(f(X.x),Y1.y)A.a=f(X.x)XY2Y16.4L-屬性文法和自頂向下翻譯帶注釋語(yǔ)法樹(shù)R.i=g(g(f(X.x),Y1.y),Y2.y)Y2R.i=g(f(X.x),Y1.y)R.i=f(X.x)AXY1R.sR.sR.sA.aP155-15676遞歸下降分析器的構(gòu)造

p156舉例

AST:AbstractSyntaxTree

三.遞歸下降翻譯器的設(shè)計(jì)6.4L-屬性文法和自頂向下翻譯77

L-屬性文法的自上而下分析翻譯方法，適用于所有基于LL(1)文法和許多基于LR(1)文法的L-屬性文法，是S-屬性文法自下而上翻譯技術(shù)的一般化。（1）從翻譯模式中去掉嵌入在產(chǎn)生式中間的動(dòng)作（2）分析棧中的繼承屬性（3）模擬繼承屬性的計(jì)算（4）用綜合屬性代替繼承屬性6.5

自下而上的計(jì)算繼承屬性78S－屬性文法翻譯自下而上規(guī)約時(shí)進(jìn)行，翻譯模式允許翻譯動(dòng)作嵌入產(chǎn)生式，如何保證嵌入的動(dòng)作在產(chǎn)生式的末尾？標(biāo)記非終結(jié)符

M→ε

標(biāo)記非終結(jié)符代替嵌入在產(chǎn)生式中間的語(yǔ)義動(dòng)作，并將這個(gè)動(dòng)作放在產(chǎn)生式M→ε的末尾。一.從翻譯模式中去掉嵌入在產(chǎn)生式中間的動(dòng)作6.5自下而上的計(jì)算繼承屬性例：

E→TR{A.a=f(X.x)}