第六章 屬性文法和語法制導(dǎo)的翻譯

第六章屬性文法和語法制導(dǎo)翻譯源程序表格管理詞法分析語法分析語義分析與中間代碼產(chǎn)生優(yōu)化器目標(biāo)代碼生成器單詞符號語法單位中間代碼中間代碼目標(biāo)代碼出錯處理語義分析是編譯程序的第三個階段，這是編譯程序最實(shí)質(zhì)性的工作。一個源程序在經(jīng)歷了詞法分析和語法分析之后，表明它在書寫和語法結(jié)構(gòu)上是正確的。然而，語法的正確并不能保證語義的正確。粗略地說，語義分析階段就是分析源程序的含義，并做相應(yīng)的語義處理，生成目標(biāo)代碼或某種形式的中間代碼。目前大多數(shù)編譯程序普遍采用的一種語義分析方法——語法制導(dǎo)翻譯方法語義分析的任務(wù)是根據(jù)語義規(guī)則對識別出的各種語法成分分析其含義，進(jìn)行初步翻譯，生成相應(yīng)的中間代碼或直接生成目標(biāo)代碼。具體來說，其主要任務(wù)包括以下幾部分。(1)確定類型。即確定標(biāo)識符所對應(yīng)數(shù)據(jù)對象的數(shù)據(jù)類型，這部分工作有時也由詞法分析來完成。(2)語義檢查。動態(tài)語義檢查在運(yùn)行時進(jìn)行，需要生成相應(yīng)的目標(biāo)代碼；而靜態(tài)語義檢查則在編譯時完成，它主要涉及以下四個方面。

①類型檢查。按照語言的類型規(guī)則，對運(yùn)算及運(yùn)算對象進(jìn)行類型檢查，檢查運(yùn)算的合法性與運(yùn)算對象類型的一致性，必要時作相應(yīng)的類型轉(zhuǎn)換。語義分析任務(wù)②控制流檢查。通過檢查控制流語句，以確?？刂普Z句有合法的轉(zhuǎn)向點(diǎn)。例如，c語言中break語句的作用是使程序跳離包括該語句的最小的switch、while或for語句，如果不存在這樣的語句，則應(yīng)報(bào)錯。③一致性檢查。很多情況下要求對象只能被定義一次。例如，c語言中規(guī)定一個標(biāo)識符在同一作用域中只能被說明一次，同一switch語句的case語句標(biāo)號不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等。④相關(guān)名字檢查。有的語言中有時規(guī)定，同一名字必須出現(xiàn)兩次或多次。例如，Ada語言中，循環(huán)或程序塊可以有兩個名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)尾，如同語句括號一般，編譯程序必須檢查它們的配對情況。語義分析任務(wù)

(3)識別含義。如果靜態(tài)語義正確，則進(jìn)行真正的翻譯，即識別程序中各種語法成分的含義，并做相應(yīng)的語義處理。生成相應(yīng)的中間代碼或直接生成目標(biāo)代碼。語義分析程序是在詞法分析和語法分析之后，可以由語法分析程序直接調(diào)用相應(yīng)的語義。語義分析任務(wù)屬性文法在上下文無關(guān)文法基礎(chǔ)上，賦予每個文法符號以一定屬性，并規(guī)定文法的每個產(chǎn)生式對相關(guān)屬性的運(yùn)算規(guī)則，這些附加了一組屬性和運(yùn)算規(guī)則的文法稱為屬性文法。屬性的運(yùn)算規(guī)則又稱為語義規(guī)則或語義子程序?qū)傩缘闹凳怯烧Z義規(guī)則計(jì)算出來的，而語義規(guī)則的計(jì)算可以產(chǎn)生中間代碼或目標(biāo)代碼屬性的表示在屬性文法中，文法符號X的屬性t常用X.t,例如，可以用X.val,X.type,X.addr分別表示X的值、類型和地址。但是對于特定的屬性文法，每個文法符號只可能涉及部分屬性。例如，對于表達(dá)式文法G（E）：EE+T|TTT*F|FF(E)|i如果只想計(jì)算表達(dá)式的結(jié)果，則只關(guān)心各文法符號的值屬性，因此E、T、F，都有一個整數(shù)值的屬性，分別表示為E.val、T.val、F.val，而對于終結(jié)符i，由于它是詞法分析傳過來的整數(shù)，設(shè)其內(nèi)部值用lexval來表示，則i的屬性表示i.lexval。至于其他終結(jié)符號+、*、(、)等所代表的都是語義動作，這些語義動作將在語義規(guī)則中反映出來。語義規(guī)則表示一個產(chǎn)生式對應(yīng)的語義規(guī)則是根據(jù)產(chǎn)生式所蘊(yùn)涵的語義操作建立起來的，并與語義分析的目標(biāo)有關(guān)。不同的產(chǎn)生式對應(yīng)不同的語義規(guī)則，不同的分析目標(biāo)也對應(yīng)不同的語義規(guī)則。例6.1：文法G（E）：EE+T|TTT*F|FF(E)|i

以表達(dá)式求值為目標(biāo)，構(gòu)造各產(chǎn)生式的語義規(guī)則。因?yàn)檎Z義分析的目的是求算術(shù)表達(dá)式的值，不產(chǎn)生中間代碼，因而相應(yīng)的語義子程序只需進(jìn)行值的運(yùn)算和傳遞，各產(chǎn)生式的語義規(guī)則如下表所示。產(chǎn)

生

式

語

義

規(guī)

則

E

E1+T

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

E

T

E.val:=T.val

T

T1*F

T.val:=T1.val*F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

i

F.val:=i.lexval語義規(guī)則表示語法制導(dǎo)翻譯的過程在文法中，文法符號有明確的語義，文法符號之間有確定的語義關(guān)系。用屬性描述語義信息，用語義規(guī)則描述屬性間的關(guān)系，將語義規(guī)則與語法規(guī)則相結(jié)合，在語法分析的過程中通過執(zhí)行語義動作，計(jì)算語義屬性值，從而完成預(yù)定的翻譯工作。這就是語法制導(dǎo)翻譯的思想。具體實(shí)現(xiàn)時，語法制導(dǎo)翻譯分為以下兩種處理方法。(1)屬性文法，即對每個產(chǎn)生式編制一個語義分析子程序，在進(jìn)行語法分析的過程中，當(dāng)一個產(chǎn)生式獲得匹配時，就調(diào)用相應(yīng)的語義分析子程序?qū)崿F(xiàn)語義檢查與翻譯。這種實(shí)現(xiàn)方案隱藏了語義規(guī)則的計(jì)算次序等細(xì)節(jié)，不必規(guī)定翻譯順序。(2)翻譯模式，即在產(chǎn)生式右部的適當(dāng)位置，插入相應(yīng)的語義動作，按照分析的進(jìn)程，執(zhí)行遇到的語義動作。這是一種動作與分析交錯的實(shí)現(xiàn)方案。不論是應(yīng)用屬性文法方式還是應(yīng)用翻譯模式，翻譯過程都是類似的，可分為以下幾步：(1)分析輸入符號串，建立語法分析樹；(2)從分析樹得到描述結(jié)點(diǎn)屬性間依賴關(guān)系的依賴圖，由依賴圖得到語義規(guī)則的計(jì)算次序；(3)進(jìn)行語義規(guī)則的計(jì)算，得到翻譯結(jié)果。然而，一個具體的實(shí)現(xiàn)并不一定按照上述步驟進(jìn)行。例如，當(dāng)編譯程序應(yīng)用語法制導(dǎo)定義一遍掃描實(shí)現(xiàn)語義規(guī)則計(jì)算時，它就在語法分析過程中同時完成語義規(guī)則的計(jì)算，而不產(chǎn)生明顯的語法分析樹或依賴圖。由于單遍編譯的效率較高，所以被一些編譯程序所采用。語法制導(dǎo)翻譯的過程屬性分類屬性文法是上下文無關(guān)文法的推廣，其中每一個文法符號都有一個與之相關(guān)聯(lián)的屬性集，它分成兩個子集，分別叫做該文法符號的綜合屬性集合和繼承屬性集合。如果我們把分析樹上的結(jié)點(diǎn)看成是保存對應(yīng)文法符號的屬性的記錄，那么屬性對應(yīng)記錄的域。屬性可以表示任何東西：串、數(shù)、類型、內(nèi)存單元，或其他想表示的內(nèi)容。分析樹結(jié)點(diǎn)的屬性值由該結(jié)點(diǎn)所用產(chǎn)生式的語義規(guī)則定義。從分析樹上來看，一個結(jié)點(diǎn)的綜合屬性值是從其子結(jié)點(diǎn)的屬性值計(jì)算出來的，而繼承屬性值則是由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和父結(jié)點(diǎn)的屬性值計(jì)算出來的。屬性分類設(shè)在屬性文法中，對應(yīng)于每個文法產(chǎn)生式A

都有與之相關(guān)聯(lián)的一套語義規(guī)則，規(guī)則形式為b:=f(c1,c2,…,ck)

，其中，f是一個函數(shù)，b和c1,c2,…,ck

是產(chǎn)生式文法符號的屬性。具體分為以下兩種情況：(1)如果b是A的屬性，c1,c2,…,ck是產(chǎn)生式右部文法符號的屬性或A的其他屬性，那么b叫做文法符號A的綜合屬性；(2)如果b是產(chǎn)生式右部某個文法符號X的屬性，c1,c2,…,ck是A或產(chǎn)生式右部任何文法符號的屬性，那么b叫做文法符號X的繼承屬性。在這兩種情況下，我們都說屬性b依賴于屬性c1,c2,…,ck。在語法制導(dǎo)定義中，我們把其中的文法稱為基礎(chǔ)文法。終結(jié)符：只有綜合屬性，由詞法分析器提供非終結(jié)符：既可有綜合屬性又可有繼承屬性；文法開始符：所有繼承屬性作為屬性計(jì)算前的初始值。綜合屬性綜合屬性在實(shí)際中被廣泛地應(yīng)用。只使用綜合屬性的語法制導(dǎo)定義稱為s屬性定義。在s屬性定義的語法分析樹中，可以使用自底向上的方法在每一個結(jié)點(diǎn)處使用語義規(guī)則來計(jì)算綜合屬性值，即從葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)算。注釋分析樹每個結(jié)點(diǎn)的屬性值都標(biāo)注出來的分析樹叫做注釋分析樹對例6．1中的表達(dá)式文法G[E]進(jìn)行拓廣，增加一個產(chǎn)生式L

En(n代表換行符)，并附以相應(yīng)的語義規(guī)則來計(jì)算并打印表達(dá)式的值，如下表所示。產(chǎn)

生

式

語

義

規(guī)

則

L

E

n

print(E.val)

E

E1+T

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

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval每個產(chǎn)生式左部的E、T、F的屬性值的計(jì)算來自它右部的非終結(jié)符，都是綜合屬性。單詞i僅有綜合屬性，它的值是由詞法分析程序提供的。和產(chǎn)生式L

En相聯(lián)的語義規(guī)則是一個過程，打印由E產(chǎn)生的表達(dá)式的值。L在語義規(guī)則中沒有出現(xiàn)，可以理解L的屬性是空的或是虛的。用分析樹計(jì)算表達(dá)式2+3*4i.lexval=4LE.val=14T.val=12E.val=2T.val=2F.val=2i.lexval=2T.val=3+*F.val=3F.val=4i.lexval=3nS屬性文法僅僅使用綜合屬性的文法產(chǎn)

生

式

語

義

規(guī)

則

L

E

n

print(E.val)

E

E1+T

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

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

i

F.val:=i.lexvalS屬性文法的特點(diǎn)僅僅使用綜合屬性的文法語法樹中每個節(jié)點(diǎn)的綜合屬性值由其子節(jié)點(diǎn)的屬性值決定屬性值的計(jì)算采用自下而上的方法計(jì)算實(shí)例：8+5*2\n語法分析樹iLETETFiT+*FFin分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成i.lexvalLE.valnT.valE.valT.valF.vali.lexvalT.val+*F.valF.vali.lexval分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成i.lexvalLE.valnT.valE.valT.valF.vali.lexval

=8T.val+*F.valF.vali.lexval分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexvalLE.valnT.valE.valT.valF.val

=8digit.lexval

=8T.val+*F.valF.valdigit.lexval分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexvalLE.valnT.valE.valT.val

=8F.val

=8digit.lexval

=8T.val+*F.valF.valdigit.lexval分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexvalLE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val+*F.valF.valdigit.lexval分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexvalLE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val+*F.valF.valdigit.lexval

=5分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexvalLE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val+*F.val

=5F.valdigit.lexval

=5分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexvalLE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val

=5+*F.val

=5F.valdigit.lexval

=5分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval

=2LE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val

=5+*F.val

=5F.valdigit.lexval

=5分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval

=2LE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val

=5+*F.val

=5F.val

=2digit.lexval

=5分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval

=2LE.valnT.val

=10E.val

=8T.val

=8F.val

=8digit.lexval

=8T.val

=5+*F.val

=5F.val

=2digit.lexval

=5分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval

=2LE.val=18nT.val

=10E.val

=8T.val

=8F.val

=8digit.lexval

=8T.val

=5+*F.val

=5F.val

=2digit.lexval

=5例題6.2例6.2為文法G[S】：S(L)|aLL，S|S寫一個語法制導(dǎo)定義，輸出括號的對數(shù)。例如對于句子(a，(a，a))，輸出是2。解：首先對文法進(jìn)行拓廣，增加一個產(chǎn)生式S’

S，以使輸出動作唯一，保證正確輸出結(jié)果。然后分析題目的要求，求出所有括號的對數(shù)。我們從后向前依次查看每個產(chǎn)生式：當(dāng)使用LS歸約時，L中的括號對數(shù)等于S中的括號對數(shù)；當(dāng)使用LL1，S歸約時，Ll與S用“，”連接，因此L中的括號對數(shù)等于S中的括號對數(shù)與L1中的括號對數(shù)之和；當(dāng)使用Sa歸約時，S中的括號對數(shù)等于O；當(dāng)使用S(L)歸約時，S中的括號對數(shù)等于L中的括號對數(shù)加1：當(dāng)使用S’S歸約時，輸出S的括號對數(shù)。在此分析的基礎(chǔ)上，為S和L引入綜合屬性num記錄括號的對數(shù)，很容易就能寫出各個產(chǎn)生式的語義規(guī)則了，如下表所示。例6.2為文法G[S】：S’

SS(L)|aLL，S|S產(chǎn)生式

語義規(guī)則

S’Sprint(S.num)S(L)S.num=L.num+1SaS.num=0LL1，SL.num=L1.num+S.numLSL.num=S.num從語法分析樹上來看，一個結(jié)點(diǎn)繼承屬性的值是由其父結(jié)點(diǎn)或兄弟結(jié)點(diǎn)的某些屬性來決定的。用繼承屬性來表示程序設(shè)計(jì)語言上下文的結(jié)構(gòu)關(guān)系是很方便的。繼承屬性例6.3：描述說明語句中各種變量類型的文法G[D]如下：D

TL

T

int

T

real

L

L1,

id

L

id構(gòu)造各產(chǎn)生式的語義規(guī)則，將每個變量名及其類型信息填入符號表。

舉例，繼承屬性用來給說明語句中的各個標(biāo)識符傳遞類型信息。產(chǎn)生式

語義規(guī)則

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

舉例，繼承屬性用來給說明語句中的各個標(biāo)識符傳遞類型信息。這個例子的文法所定義的說明語句是由int或real開頭，后跟一個標(biāo)識符表，標(biāo)識符之間由逗號分隔。非終結(jié)符號T有一個綜合屬性type，它的值是由說明中的關(guān)鍵字int或real來確定的。語義規(guī)則L．in=T．type對應(yīng)于產(chǎn)生式DTL，它把說明中的類型賦給繼承屬性L.in，這些規(guī)則使用繼承屬性L.in把這個類型信息在分析樹中向下傳遞。與L的產(chǎn)生式對應(yīng)的語義規(guī)則調(diào)用過程

addtype

，把標(biāo)識符的名字及其類型信息填寫在符號表中，屬性entry代表標(biāo)識符在符號表中的入口地址。繼承屬性L．in在說明中為各個標(biāo)識符提供了類型信息。intid1,id2,id3的注釋分析樹DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,產(chǎn)生式

語

義

規(guī)

則

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

使用繼承屬性的地方很多，例如可以利用繼承屬性來跟蹤一個標(biāo)識符是出現(xiàn)在賦值符號的右邊還是左邊，以確定是需要這個標(biāo)識符的值還是地址。對于一個語法制導(dǎo)定義，可以通過改寫使其只具有綜合屬性，但改寫之后，有時會使得文法失去了簡潔和直觀，反而不如使用帶繼承屬性的語法制導(dǎo)定義自然。例題6.4下面是產(chǎn)生字母表={0,1,2}上數(shù)字串的一個文法：

SDSD|2 D0|1寫一個屬性文法（語法制導(dǎo)定義），判斷它接受的句子是否為回文。解：

首先對文法進(jìn)行拓廣，增加一個產(chǎn)生式S’

S，引入S的綜合屬性boolean記錄句子為回文，引入D的綜合屬性val記錄其值，則其屬性文法如下：S

S print(S.boolean)SD1S1D2S.boolean=(D1.val==D2.val)andS1.boolean

S2 S.boolean

=trueD0 D.val=0D1 D.val=1例題6.5為下面文法寫一個屬性文法，用S的綜合屬性val給出下面文法中S產(chǎn)生的二進(jìn)制數(shù)的十進(jìn)制值。例如，輸入101.101時，S.val:=5.625。不得修改文法，但屬性使用沒有限制。 SL.R|L LLB|B RBR|B B0|1解：將二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)，其方法是按權(quán)展開，引入綜合屬性val記錄S,L,R的十進(jìn)制值，引入綜合屬性c記錄了B的二進(jìn)制位的結(jié)果值，所以其屬性文法如下：SL.R SL

LL1B LB

RBR1

RB

B0B1S.val:=L.val+R.valS.val:=L.val

L.val:=L1.val

2+B.cL.val:=B.c

R.val:=(R1.val+B.c)/2R.val:=B.c/2B.c:=0B.c:=1S.LLBLBBRRBRBB例題6.6為文法S->(L)|aL->L,S|S寫一個屬性文法，它輸出括號嵌套的最大深度S->(L)|aL->L,S|SSa(L)L,SSS深度的定義:a,(a),((a),(a)),(((a),(a)),(a))S->(L)S.d=L.d+1S->aS.d=0L->L,SL.d=MAX(L.d,S.d)L->SL.d=S.d6.2基于屬性文法的處理方法

——屬性的計(jì)算方法輸入串語法樹依賴圖語義規(guī)則的計(jì)算語法制導(dǎo)翻譯過程語法制導(dǎo)翻譯可以不遵循這一過程。語法制導(dǎo)翻譯也可以在語法分析階段完成，例如S-屬性文法和L-屬性文法屬性依賴圖對于一個輸入符號串，在建立注釋分析樹后，可以構(gòu)造一個有向圖，用來描述分析樹結(jié)點(diǎn)的屬性間的互相依賴關(guān)系。如果分析樹一結(jié)點(diǎn)的屬性b依賴某個結(jié)點(diǎn)的屬性c，那么屬性b的語義規(guī)則的計(jì)算必須在屬性c的語義規(guī)則的計(jì)算之后。這樣由依賴圖可以得到語義規(guī)則的計(jì)算次序，據(jù)此進(jìn)行語義規(guī)則的計(jì)算便得到了翻譯結(jié)果。屬性依賴圖的構(gòu)造為了構(gòu)造屬性依賴圖，需要對那些由過程調(diào)用組成的語義規(guī)則引入虛擬綜合屬性b，使得每條語義規(guī)則都能寫成b=f(c1，c2，…，ck)的形式。依賴圖構(gòu)造的基本思想是：對分析樹上每個結(jié)點(diǎn)的所有屬性都構(gòu)造一個結(jié)點(diǎn)，如果屬性b依賴于屬性c，則從c的結(jié)點(diǎn)到b的結(jié)點(diǎn)作一條有向邊。在語法樹的基礎(chǔ)上完成針對語法樹中的每一個文法符號的每一個屬性，建立一個節(jié)點(diǎn)；對于涉及到過程調(diào)用組成的語義規(guī)則，建立一個虛節(jié)點(diǎn)根據(jù)語義規(guī)則中關(guān)于屬性的計(jì)算規(guī)則的定義，在節(jié)點(diǎn)之間建立連線，描述屬性之間的依賴關(guān)系。例如，若X.x=f(A.a

B.b)是產(chǎn)生式XAB的語義規(guī)則，它定義了依賴于屬性A.a和B.b的綜合屬性X.x。如果把這個產(chǎn)生式用于分析樹，那么在依賴圖上有三個結(jié)點(diǎn)X.x、A.a和B.b，并且結(jié)點(diǎn)A.a和B.b分別有一條有向邊到結(jié)點(diǎn)X.x,如果產(chǎn)生式XAB有語義規(guī)則A．a(chǎn)=g(X.x，B.b)，那么在依賴圖上，結(jié)點(diǎn)X.x和B.b分別有邊到結(jié)點(diǎn)A.a，因?yàn)锳.a依賴于X.x和B.b。intid1,id2,id3的分析樹的依賴圖其中虛線表示的是分析樹；依賴圖的結(jié)點(diǎn)用數(shù)表示,

邊用實(shí)線表示。

,D

intTid3LLLid2id1,1

entry102

entry3

entryin

98in

76in

54

type產(chǎn)生式

語

義

規(guī)

則

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

根據(jù)產(chǎn)生式DTL的語義規(guī)則L.in=T.type，有L.in依賴于T.type，所以從結(jié)點(diǎn)4的T.type到結(jié)點(diǎn)5的L.in構(gòu)造一條邊。根據(jù)產(chǎn)生式LL1,id的語義規(guī)則L1.in=L.in，有L1.in依賴于L.in，因此可以分別構(gòu)造到達(dá)結(jié)點(diǎn)7和9的兩條向下的邊。根據(jù)產(chǎn)生式Lid的語義規(guī)則addtype(id.entry,L.in),建立虛擬屬性結(jié)點(diǎn)6，8，10。屬性計(jì)算次序拓?fù)渑判颍菏菬o環(huán)有向圖的結(jié)點(diǎn)的一種排序。這種排序滿足：依賴圖中的邊只會從該次序中先出現(xiàn)的結(jié)點(diǎn)到后出現(xiàn)的結(jié)點(diǎn)。例如，在下圖所示的依賴圖中，每條邊從序號較低的結(jié)點(diǎn)到序號較高的結(jié)點(diǎn)，因此結(jié)點(diǎn)l，2，…，10構(gòu)成該圖的一個拓?fù)渑判?。我們把依賴圖中序號為n的結(jié)點(diǎn)的屬性寫成an，那么從這個拓?fù)渑判蚩梢缘孟旅娴某绦颍篋

intT,id3LLLid2id1,1entry102entry3entryin98in76in54typea4=integera5=a4Addtype(id3.entry,a5)a7=a5Addtype(id2.entry,a7)a9=a7Addtype(id1.entry,a7)6.2.2樹遍歷的屬性計(jì)算方法通過樹遍歷計(jì)算屬性值得方法很多種。這些方法都假設(shè)語法樹已經(jīng)建立起了，并且樹中已帶有開始符號的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語法樹，直至計(jì)算出所有的屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。While還有未被計(jì)算的屬性do

visitNode(s)/*S是文法開始符號*/Procedurevisitnode(N:node);BeginifN是一個非終結(jié)符then{對于該非終結(jié)符的候選式中的每一個文法符號X{ifX是非終結(jié)符{計(jì)算該非終結(jié)符的所有繼承屬性；

visitnode（該非終結(jié)符）}}}計(jì)算N的所有能夠計(jì)算的綜合屬性end

,D

intTid3LLLid2id1,下面算法可對任何無循環(huán)的屬性文法進(jìn)行計(jì)算6.2.3一遍掃描的處理方法與樹遍歷的屬性計(jì)算方法不同，一遍掃描的方法是在語法分析的同時計(jì)算屬性值。如果按這種一遍掃描的編譯程序模型來理解語法制導(dǎo)翻譯方法的話，所謂語法制導(dǎo)翻譯法，直觀上說是為文法中每個產(chǎn)生式配上一組語義規(guī)則，并且在語法分析的同時執(zhí)行這些語義規(guī)則.在自上而下的語義分析中,若一個產(chǎn)生式匹配輸入串成功,或者在自下而上分析中,當(dāng)一個產(chǎn)生式被用于進(jìn)行歸約時,此產(chǎn)生式相應(yīng)的語義規(guī)則就被計(jì)算,完成有關(guān)語義分析和代碼生成的工作.為了適應(yīng)語義分析的需要，把語法規(guī)則中對語義無關(guān)緊要的具體規(guī)定去掉，剩下來的本質(zhì)性的東西叫做抽象語法。在不同的語言中賦值語句有不同的寫法，如

x=y；x=y；yx；等，但本質(zhì)是一樣的，因此可用抽象形式：

assignment(variable,expression)把前面各種具體形式統(tǒng)一起來，把a(bǔ)ssignment看作運(yùn)算符號，把expression和variable看作它的兩個運(yùn)算分量。與此相應(yīng)可以使用抽象語法樹來反映抽象的語法結(jié)構(gòu)，也稱作語法結(jié)構(gòu)樹，或結(jié)構(gòu)樹。而分析樹是反映具體語法結(jié)構(gòu)的。抽象語法樹是分析樹的抽象形式，或壓縮形式，它把分析樹中對語義無關(guān)緊要的成分去掉。語法樹中的每一個結(jié)點(diǎn)表示一個運(yùn)算符號，各子結(jié)點(diǎn)表示運(yùn)算分量。6.2.4抽象語法樹(自學(xué))抽象語法樹是分析樹的濃縮表示：算符和關(guān)鍵字是作為內(nèi)部結(jié)點(diǎn)。

語法制導(dǎo)翻譯可以基于分析樹，也可以基于抽象語法樹抽象語法樹的例子：if-then-elseBS1S2+*258抽象語法樹S->ifBthenS1elseS28+5*2構(gòu)造抽象語法樹的語法制導(dǎo)定義建立表達(dá)式的語法樹與把表達(dá)式翻譯成后綴形式類似。我們通過為每一個運(yùn)算對象或運(yùn)算符都建立一個結(jié)點(diǎn)來為子表達(dá)式建立子樹。運(yùn)算符結(jié)點(diǎn)的各子結(jié)點(diǎn)分別是表示該運(yùn)算符的各個運(yùn)算對象的子表達(dá)式組成的子樹的根。語法樹中的每個結(jié)點(diǎn)都是由包含幾個域的記錄來表示的。對于運(yùn)算符結(jié)點(diǎn)，其中一個域標(biāo)識運(yùn)算符，其他域包含指向運(yùn)算對象的結(jié)點(diǎn)的指針。運(yùn)算符通常叫作這個結(jié)點(diǎn)的標(biāo)號。在翻譯時，語法樹中的結(jié)點(diǎn)可能會用附加的域來存放結(jié)點(diǎn)的屬性值(或指向?qū)傩灾档闹羔?。下面定義一些函數(shù)用來建立帶有二元運(yùn)算符的表達(dá)式的語法樹結(jié)點(diǎn)。每個函數(shù)都返回一個指向新建結(jié)點(diǎn)的指針。

(1)mknode(op,left,right)：建立一個運(yùn)算符號結(jié)點(diǎn)，其中標(biāo)號是op，兩個域left和right是分別指向左右運(yùn)算對象結(jié)點(diǎn)的指針。

(2)mkleaf(id,entry)：建立一個標(biāo)識符結(jié)點(diǎn)，由標(biāo)號id標(biāo)識，域entry是指向標(biāo)識符在符號表中的相應(yīng)表項(xiàng)的指針。

(3)mkleaf(num，val):建立一個數(shù)結(jié)點(diǎn)，標(biāo)號為num，域val用于存放數(shù)的值。構(gòu)造抽象語法樹的語法制導(dǎo)定義產(chǎn)生式語

義

規(guī)

則

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,

T.nptr)

ET

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,

F.nptr)

T

F

T.nptr:=F.nptr

F(E)

F.nptr:=E.nptr

Fid

F.nptr:=mkleaf

(id,id.entry)

Fnum

F.nptr:=mkleaf

(num,num.val)

下表是一個為包含+和*的表達(dá)式構(gòu)造語法樹的S屬性定義。語義規(guī)則中調(diào)用函數(shù)mknode和mkleaf，非終結(jié)符E、T和F的綜合屬性nptr是用來記錄函數(shù)調(diào)用返回值的指針。a+5*b語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnum+*id指向符號表中b的入口id指向符號表中a的入口num5E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,

T.nptr)

ET

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,

F.nptr)

T

F

T.nptr:=F.nptr

F(E)

F.nptr:=E.nptr

Fid

F.nptr:=mkleaf

(id,id.entry)

Fnum

F.nptr:=mkleaf

(num,num.val)a+5*b的語法樹的構(gòu)造（紅色為抽象語法樹）E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口6.3S屬性文法的自下而上計(jì)算

要建立一個通用的語法制導(dǎo)定義的翻譯器是很困難的，但是可以針對某一類的語法制導(dǎo)定義給出其翻譯的實(shí)現(xiàn)方案。介紹只含有綜合屬性的語法制導(dǎo)定義，即S屬性定義和只帶有繼承屬性的語法制導(dǎo)定義即L屬性定義的實(shí)現(xiàn)。

因?yàn)镾屬性定義只有綜合屬性，所以可以在自底向上的語法分析過程中，對輸入符號串進(jìn)行語法分析的同時，實(shí)現(xiàn)對綜合屬性的計(jì)算。分析器可以把文法符號的綜合屬性值放在它擴(kuò)充分析棧里，每當(dāng)歸約時，根據(jù)出現(xiàn)在棧頂?shù)漠a(chǎn)生式右部符號的屬性來計(jì)算左部符號的綜合屬性。

6.3S屬性文法的自下而上計(jì)算在具體實(shí)現(xiàn)時，s屬性定義的翻譯器可以借助像Yacc那樣的LR分析器來實(shí)現(xiàn)，通過擴(kuò)充LR分析器的分析棧，在棧中增加一個域來保存綜合屬性值。擴(kuò)充后的分析棧包括狀態(tài)數(shù)組state和值數(shù)組val，如圖所示。其中，state表示分析棧中的狀態(tài)，val表示屬性值。如果第i個狀態(tài)所涉及的文法符號是A，則用val[i]保存分析樹中對應(yīng)A的結(jié)點(diǎn)的屬性值。棧頂由指針top指示，并假定綜合屬性剛好在每步歸約前計(jì)算。若產(chǎn)生式AXYZ的語義規(guī)則是A.a=f(X.x，Y.y，Z.z)，則在XYZ

歸約成A之前，屬性Z.z的值在val[top]中，Y.y的值在val[top-1]中，X.x的值在val[top-2]中。歸約后，top的值減2，A對應(yīng)的狀態(tài)保存在state[top](即x原來的位置)中，綜合屬性的值A(chǔ).a放進(jìn)val[top]中。......ZZ.zYY.yXX.x......棧statevaltop臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(E.val)

E

E1+T

E.val

:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

E.val

:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval......ZZ.zYY.yXX.x......棧statevaltop臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval......ZZ.zYY.yXX.x......棧statevaltop臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

F(E)

val

[top2]

:=val

[top1]

F

digit

F.val:=digit.lexval......ZZ.zYY.yXX.x......棧statevaltop臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

F(E)

val

[top2]

:=val

[top1]

F

digit

......ZZ.zYY.yXX.x......棧statevaltop輸入3*5+4n所做的移動6.4L屬性定義的自上而下計(jì)算S屬性定義的翻譯可以通過擴(kuò)充LR分析器，在語法分析的同時進(jìn)行翻譯，那么這種邊分析邊翻譯的方式是否適用于有繼承屬性的情況呢?

當(dāng)在語法分析的同時進(jìn)行翻譯時，對屬性的計(jì)算順序一定受到語法分析時所建立語法分析樹中結(jié)點(diǎn)順序的制約。不管是自頂向下分析還是自底向上分析，分析樹的結(jié)點(diǎn)都是自左向右生成。這樣我們不妨設(shè)想，如果屬性信息出現(xiàn)的順序是自左向右流動。那么就有可能在分析的同時完成屬性計(jì)算。下面我們按這種想法定義L屬性定義，L代表左(left)，因?yàn)閷傩孕畔⑹菑淖笙蛴页霈F(xiàn)的。*L屬性文法如果每個產(chǎn)生式AX1

X2…Xn

的每條語義規(guī)則計(jì)算的屬性是A的綜合屬性；或者是Xj

的繼承屬性，1

j

n,但它僅依賴：（1）該產(chǎn)生式中Xj左邊符號X1,X2,…,Xj-1的屬性；（2）A的繼承屬性。則稱其是L屬性文法。顯然，S屬性文法屬于L屬性文法，因?yàn)?1)和(2)僅對繼承屬性進(jìn)行限制。變量類型聲明的語法制導(dǎo)定義是一個L屬性定義

產(chǎn)生式

語

義

規(guī)

則

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

D

intT,id3LLLid2id1,1entry102entry3entryin98in76in54typeL屬性文法中屬性值的計(jì)算特點(diǎn)在自上而下分析中進(jìn)行屬性計(jì)算的問題D

intT,id3LLLid2id1,1entry102entry3entryin98in76in54type非L-屬性文法的例子產(chǎn)生式語義規(guī)則A->LML.i=l(A.i)M.i=m(l.s)A->QRR.i=r(A.i)Q.i=q(R.s)A.s=f(Q.s)翻譯模式：適合于語法制導(dǎo)翻譯的另一種描述方式特點(diǎn)：翻譯方案中包含以下內(nèi)容： 基礎(chǔ)文法 文法符號的屬性 關(guān)于語義動作的定義，定義了語義動作執(zhí)行的時間語義動作的表示：在產(chǎn)生式的右部的任何地方，用{}，實(shí)現(xiàn)動作和分析的交叉表示6.4.1翻譯模式翻譯模式語義動作的執(zhí)行時間： Aa{……}b翻譯方案示例：將中綴表達(dá)式翻譯成后綴表達(dá)式 E

TR

R

addop

T{print(addop.lexeme)}R1|

Tnum{print(num.val)}例把有加和減的中綴表達(dá)式翻譯成后綴表達(dá)式 如果輸入是8+52，則輸出是85+2。

E

TR

R

addop

T{print(addop.lexeme)}R1|

Tnum{print(num.val)}E

TRnum{print(8)}

R

num{print(8)}addopT{print(+)}Rnum{print(8)}addopnum

{print(5)}{print(+)}R{print(8)}{print(5)}{print(+)}

addop

T{print()}

R{print(8)}{print(5)}{print(+)}{print(2)}{print()}只保留翻譯方案設(shè)計(jì)應(yīng)注意的問題基本原則：動作在引用屬性時，屬性的值應(yīng)該是已知的實(shí)現(xiàn)方案：（1）當(dāng)只有綜合屬性時，可以把語義動作放在產(chǎn)生式的最后D

intT,id3LLLid2id1,1entry102entry3entryin98in76in54type產(chǎn)生式

語

義

規(guī)

則

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

翻譯方案設(shè)計(jì)應(yīng)注意的問題（2）如果有繼承屬性產(chǎn)生式右部的文法符號的繼承屬性必須在先于這個符號的動作中計(jì)算一個動作不能引用該動作右邊符號的綜合屬性左部非終結(jié)符的綜合屬性只能在它所引用的所有屬性都計(jì)算完后才能計(jì)算。D

intT,id3LLLid2id1,1entry102entry3entryin98in76in54type產(chǎn)生式

語

義

規(guī)

則

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

翻譯模式示例構(gòu)造抽象語法樹的翻譯模式E->E+TE->T{E.nptr=makenode(+,E1.nptr,T.nptr)}{E.nptr=T.nptr}翻譯方案示例：將中綴表達(dá)式翻譯成后綴表達(dá)式E

TR R

addop

T{print(addop.lexeme)}R1|Tnum{print(num.val)}8+52Enum{print(num.val)}TRaddop

T{print(addop.lexeme)}R1num{print(num.val)}翻譯模式示例為文法S->(L)|aL->L,S|S寫一個翻譯模式，它輸出每個a的嵌套深度。例如對句子(a,(a,a)),輸出的結(jié)果是1，2，2基本原則：動作在引用屬性時，屬性的值應(yīng)該是已知的實(shí)現(xiàn)方案：（1）當(dāng)只有綜合屬性時，可以把語義動作放在產(chǎn)生式的最后（2）如果有繼承屬性產(chǎn)生式右部的文法符號的繼承屬性必須在先于這個符號的動作中計(jì)算一個動作不能引用該動作右邊符號的綜合屬性左部非終結(jié)符的綜合屬性只能在它所引用的所有屬性都計(jì)算完后才能計(jì)算。S->(L)|aL->L,S|S寫一個翻譯模式，它輸出每個a的嵌套深度。例如對句子(a,(a,a)),輸出的結(jié)果是1，2，2分析：由于a的嵌套深度不是由a本身決定的．所以一定得用繼承屬性。另外，a的嵌套深度從a左邊的部分足以判斷，因此可以用L屬性定義解決，為S和L引入繼承屬性val記錄a的嵌套深度。a的嵌套深度等于當(dāng)前還沒有匹配完的左括號的個數(shù)，因此累加操作應(yīng)該在讀入一個左括號之后立即進(jìn)行，而當(dāng)讀入一個字符a的時候立即輸出它的深度。據(jù)此便可寫出如下的屬性文法和翻譯模式：SaS(L)L,SSS->(L)|aL->L,S|S寫一個翻譯模式，它輸出每個a的嵌套深度。例如對句子(a,(a,a)),輸出的結(jié)果是1，2，2a屬性文法(val是繼承屬性）S’->S {S.val=0}S->(L) {L.val=S.val+1}S->a {printf(S.val)}L->L1,S{L1.val=L.val,S.val=L.val}L->S{S.val=L.val}S(L)L,SSaa翻譯模式S’->{S.val=0}SS->({L.val=S.val+1}

L) S->a{printf(S.val)}L->{L1.val=L.val}L,{S.val=L.val}SL->{S.val=L.val}

S輸出句子(a,(a,a))中每個a的嵌套深度：翻譯模式S’->{S.val=0}SS->({L.val=S.val+1}

L) S->a{printf(S.val)}L->{L1.val=L.val}L,{S.val=L.val}SL->{S.val=L.val}

SS({L.val=S.val+1}

L)S({L.val=S.val+1}

L){L1.val=L.val}L,{S.val=L.val}S{L1.val=L.val}L,{S.val=L.val}Sa{printf(S.val)}

a{printf(S.val)}

Sa{printf(S.val)}

已知文法：S->aBS|bAS|εB->aBB|bA->bAA|a構(gòu)造一個翻譯模式，它統(tǒng)計(jì)句子中a的個數(shù)和b的個數(shù)

屬性文法S->aBS {S.a=B.a+s1.a+1;S.b=B.b+S.b}S->bAS {S.a=A.a+s1.a;S.b=A.b+S.b+1}S->ε {S.a=0;S.b=0}B->aBB {B.a=B1.a+B2.a+1;B.b=B1.b+B2.b}B->b {B.a=0;B.b=1}A->bAA {A.a=A1.a+A2.a;A.b=A1.b+A2.b+1}A->a {A.a=1;A.b=0}翻譯模式S->aBS {S.a=B.a+s1.a+1;S.b=B.b+S.b}S->bAS {S.a=A.a+s1.a;S.b=A.b+S.b+1}S->ε {S.a=0;S.b=0}B->aBB {B.a=B1.a+B2.a+1;B.b=B1.b+B2.b}B->b {B.a=0;B.b=1}A->bAA {A.a=A1.a+A2.a;A.b=A1.b+A2.b+1}A->a {A.a=1;A.b=0}6.4.2自頂向下翻譯對于一個翻譯模式，若采用自頂向下分析，必須消除左遞歸和提取左公因子，在改寫基本文法時考慮屬性值的計(jì)算。

EE1+T｛E

val:=E1val+T

val}EE1-T｛E

val:=E1

val-Tval｝

ET{E.val:=T

val}T(E)｛T

val:=Eval｝

Tnum｛T

val:=numval}

例

帶左遞歸的文法的翻譯模式被轉(zhuǎn)換成帶右遞歸的文法的翻譯模式。

E→T{Ri:=T

val}R｛E

val:=Rs｝

R→＋

T｛R1i:=R.i+T.val}R1｛R.s:=R1

s}R→-T｛R1

i:=R

i-Tval}R1｛Rs:=R1

s}R→ε｛Rs:=Ri}T→（E）｛Tval:=E.val}T→num{Tval:=numval}EE1+TEE1-TETT(E)Tnum繼承屬性i綜合屬性sETRR(+T|-T)R|εT(E)Tnum對于原左遞歸的文法，屬性的計(jì)算自底向上；經(jīng)過轉(zhuǎn)換的帶有右遞歸文法，屬性的計(jì)算自左向右。

E→T{Ri:=T

val}R｛E

val:=Rs｝

R→＋T｛R1i:=R.i+T.val}R1｛R.s:=R1

s}R→-T｛R1

i:=R

i-Tval}R1｛Rs:=R1

s}R→ε｛Rs:=Ri}T→（E）｛Tval:=E.val}|num{Tval:=numval}E5+3T{Ri:=T

val}R

｛E

val:=Rs｝num{Tval:=numval}＋T｛R1i:=R.i+Tval}R1｛Rs:=R1s}ε

｛Rs:=Ri}

num{Tval:=numval}Eval=6Tval=9Ri=9;Rs=69–Tval=55Ri=4;Rs=6+Tval=2R

i=6;

Rs=62表達(dá)式9-5+2的計(jì)算

E→T{Ri:=T

val}R{E

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

s}R→-T{R1

i:=R

i-Tval}R1{Rs:=R1

s}R→ε｛Rs:=Ri}T→(E){Tval:=E.val}T→num{Tval:=numval}Tval=9Ri=9Tval=5Ri=4Tval=2R

i=6Rs=6Rs=6Rs=6Eval=6◆關(guān)于左遞歸翻譯模式更一般化的討論左遞歸翻譯模式

A→A1Y｛A.a:=g(A1.a,Y.y)}A→X｛A.a:=f(X.x)}

每一個文法符號都有一個綜合屬性，用相應(yīng)的小寫字母表示，g和f是任意函數(shù)。

消除左遞歸，文法轉(zhuǎn)換成

A→XRR→YR|ε再考慮語義動作，翻譯模式變?yōu)椋?/p>

A→X｛Ri:=f(Xx)}R｛Aa:=Rs}R→Y｛R1

i:=g（Ri,Yy）}R1

｛Rs:=R1

s}R→ε｛Rs:=Ri}

經(jīng)過轉(zhuǎn)換的翻譯模式，使用R的繼承屬性