第語法制導(dǎo)翻譯和中間代碼生成演示文稿

第語法制導(dǎo)翻譯和中間代碼生成演示文稿當(dāng)前1頁，總共141頁。優(yōu)選第語法制導(dǎo)翻譯和中間代碼生成當(dāng)前2頁，總共141頁?！颈菊轮攸c】(1)幾種典型的中間代碼（語言）的形式;(2)語義的描述方法:

一種形式化的語義描述方法—屬性文法;(3)語義的處理方法:

語法制導(dǎo)的翻譯法—包括它的兩種具體形式：語法制導(dǎo)的翻譯和翻譯方案。當(dāng)前3頁，總共141頁。編譯程序的任務(wù)是把源程序翻譯成目標(biāo)程序，這個目標(biāo)程序必須和源程序的語義等同，也就是說，盡管它們的語法結(jié)構(gòu)完全不同，但它們所表達(dá)的結(jié)果應(yīng)完全相同。通常，在詞法分析程序和語法分析程序?qū)υ闯绦虻恼Z法結(jié)構(gòu)進(jìn)行分析之后:或者由語法分析程序直接調(diào)用相應(yīng)的語義子程序進(jìn)行語義處理;或者先生成語法樹或該結(jié)構(gòu)的某種表示，再進(jìn)行語義處理。8.0概述當(dāng)前4頁，總共141頁。第一，審查每個語法結(jié)構(gòu)的靜態(tài)語義，即驗證語法結(jié)構(gòu)合法的程序是否真正有意義。有時把這個工作稱為靜態(tài)語義分析或靜態(tài)審查。

靜態(tài)語義分析通常包括：①類型檢查②控制流檢查③一致性檢查④相關(guān)名字檢查⑤名字的作用域分析第二，如果靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯，即，或者將源程序翻譯成程序的一種中間表示形式（中間代碼），或者將源程序翻譯成目標(biāo)代碼。編譯中的語義處理是指兩個功能：當(dāng)前5頁，總共141頁。中間代碼，也稱中間語言，是復(fù)雜性介于源程序語言和機(jī)器語言的一種表示形式。為什么有的編譯程序直接生成目標(biāo)代碼，有的編譯程序采用中間代碼。一般，快速編譯程序直接生成目標(biāo)代碼，沒有將中間代碼翻譯成目標(biāo)代碼的額外開銷。但是為了使編譯程序結(jié)構(gòu)在邏輯上更為簡單明確，常采用中間代碼。這樣可以將與機(jī)器相關(guān)的某些實現(xiàn)細(xì)節(jié)置于代碼生成階段仔細(xì)處理，并且可以在中間代碼一級進(jìn)行優(yōu)化工作使得代碼優(yōu)化比較容易實現(xiàn)。當(dāng)前6頁，總共141頁。8.1屬性文法(attributegrammar)屬性文法(也稱屬性翻譯文法)是Knuth在1968年首先提出的。它是在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號(終結(jié)符或非終結(jié)符)配備若干相關(guān)的“特性”（稱為屬性）。這些屬性代表與文法符號相關(guān)信息，例如它的類型、值、代碼序列、符號表內(nèi)容等等。屬性與變量一樣，可以進(jìn)行計算和傳遞。屬性加工的過程即是語義處理的過程。當(dāng)前7頁，總共141頁。對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。所謂屬性，其涉及的概念比較廣泛，常用以描述事物或人的特征、性質(zhì)，品質(zhì)等等。比如，談到一個物體，可以用"顏色"描述它，談起某人，可以使用"有幽默感"來形容他。對編譯程序使用的語法樹的結(jié)點，可以用"類型"、"值"或"存儲位置"來描述它。一個屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則，這些語義規(guī)則附在文法的每個產(chǎn)生式上。所謂語法制導(dǎo)的翻譯指的是在語法分析過程中，完成這些語義規(guī)則描述的動作，從而實現(xiàn)語義處理。當(dāng)前8頁，總共141頁。8.1.1屬性文法定義定義1：形式上講，屬性文法是一個三元組

:A=(G，V，F(xiàn))，其中：G:是一個上下文無關(guān)文法；V:有窮的屬性集,每個屬性與文法的一個終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號相關(guān)信息；F:關(guān)于屬性的屬性斷言或一組屬性的計算規(guī)則(稱為語義規(guī)則)。斷言或語義規(guī)則與一個產(chǎn)生式相聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。當(dāng)前9頁，總共141頁。定義2：一個屬性文法是一個三元組：A=(G,V,F),其中G--基礎(chǔ)文法（一個上下文無關(guān)文法）V--每個文法符號有一組屬性F--每個文法產(chǎn)生式A有一組形式為b:=f(c1,c2,…,ck)的語義規(guī)則，其中f

是函數(shù)，b和c1,c2,…,ck是該產(chǎn)生式文法符號的屬性。當(dāng)前10頁，總共141頁。

屬性文法中的屬性分成兩類：繼承屬性和綜合屬性。簡單地說，綜合屬性用“自下而上"傳遞信息，而繼承屬性用于"自上而下"傳遞信息。綜合屬性（synthesizedattribute）：如果b是A的屬性，c1,c2,…,ck是產(chǎn)生式右部文法符號的屬性或A的其它屬性，則稱b是文法符號A的綜合屬性。繼承屬性(inheritedattribute)：如果b是產(chǎn)生式右部某個文法符號X的屬性，并且c1,c2,…,ck是A或產(chǎn)生式右部文法符號的屬性，則稱b是文法符號X的繼承屬性。當(dāng)前11頁，總共141頁。屬性文法的主要思想是：.對每個文法符號引入相關(guān)的屬性符號；.對于每個產(chǎn)生式寫出計算屬性值的屬性規(guī)則（語義規(guī)則），其形式為：b：=f(c1,c2,…,ck)

即：屬性變量：=<屬性表達(dá)式>這里f是一個函數(shù)，且對于產(chǎn)生式A，(1)b或者是A的一個綜合屬性并且c1,c2,…，ck是產(chǎn)生式右邊文法符號的屬性；(2)b或者是產(chǎn)生式右邊某個文法符號的一個繼承屬性并且c1,c2,…，ck是A或產(chǎn)生式右邊任何文法符號的屬性。在兩種情況下，我們都說屬性b依賴于屬性c1,c2,…，ck。當(dāng)前12頁，總共141頁。繼承屬性的求值規(guī)則：產(chǎn)生式左部非終結(jié)符號的繼承屬性值取前面產(chǎn)生式右部該符號已有的繼承屬性值；產(chǎn)生式右部符號的繼承屬性值用該產(chǎn)生式左部符號的繼承屬性或出現(xiàn)在該符號左部的符號的屬性值進(jìn)行計算。體現(xiàn)自頂向下，自左向右的求值特性體現(xiàn)自底向上，自右向左的求值特性綜合屬性的求值規(guī)則：產(chǎn)生式右部非終結(jié)符號的綜合屬性值取其下部產(chǎn)生式或左部同名非終結(jié)符號的綜合屬性值；產(chǎn)生式左部非終結(jié)符號的綜合屬性值用該產(chǎn)生式左部符號的繼承屬性或某個右部符號的屬性進(jìn)行計算；當(dāng)前13頁，總共141頁。例8.1有文法G為：E→T1+T2|T1orT2T→num|true|false對輸入串3+4的類型檢查的屬性文法如圖8.1。E→T1+T2{T1.t＝int

AND

T2.t＝int}E→T1orT2{T1.t＝bool

ANDT2.t＝bool}T→num{T.t∶＝int}T→true{T.t∶＝bool}T→false{T.t∶＝bool}圖8.1類型檢查的屬性文法

當(dāng)前14頁，總共141頁。屬性文法記號中常使用N.t的形式表示與非終結(jié)符N相聯(lián)的屬性t。與非終結(jié)符E的產(chǎn)生式相聯(lián)的語義規(guī)則指明：兩個T的屬性必須相同。圖8.2靜態(tài)語義審查ETT+34（a）ETT+34（b）{T2.t=int}{T1.t=int}{T1.t=T2.t}圖8.2(b)是圖8.2(a)語法樹結(jié)點帶有語義信息的表示。

當(dāng)前15頁，總共141頁。8.1.2屬性的確定

寫屬性文法，首先應(yīng)確定對于每個文法符號都有哪些屬性，然后給每個屬性起個名字，接著確定每個屬性的類別。特別強(qiáng)調(diào)：（1）終結(jié)符只有綜合屬性，它們的值由詞法分析器提供；（2）非終結(jié)符既可有綜合屬性也可有繼承屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值要在計算（整個處理）開始時指定。正確確定綜合屬性和繼承屬性是非常重要的，究竟哪些屬性確定為綜合屬性，哪些屬性確定為繼承屬性，并沒有固定的模式。當(dāng)前16頁，總共141頁。

每個文法符號表示一類語法對象，而每個語法對象都有自己的功能。

圖8.3表示E有兩個屬性，其一是值環(huán)境，其二是結(jié)果值。它們的屬性名分別為Env和Value，其中Env是需要由外部給的，Value則由自己計算出來，而且一旦給定Env值，則Value的值就被確定。這時將屬性Env定義為繼承屬性，而屬性Value則要定義為綜合屬性。EEnvValue圖8.3E的屬性比如，E表示由整常數(shù)和整型變量組成的表達(dá)式，則E的功能是給出一個變量求值的環(huán)境，且輸出一個整型值。因此，可以稱繼承屬性為輸入屬性，而稱綜合屬性為輸出屬性。當(dāng)前17頁，總共141頁。例8.2簡單算術(shù)表達(dá)式求值的語義描述。產(chǎn)生式語義規(guī)則L→Eprint(E.val)E→E1+TE.val∶＝E1.val+T.valE→TE.val∶＝T.valT→T1*FT.val∶＝T1.val*F.valT→FT.val∶＝F.valF→（E）F.val∶＝E.valF→digitF.val∶＝digit.lexval按照語義規(guī)則對每個產(chǎn)生式來說，它的左部E，T，F(xiàn)的屬性值的計算來自它右部的非終結(jié)符，這種屬性稱作綜合屬性。單詞digit僅有綜合屬性，它的值是由詞法分析程序提供的。和產(chǎn)生式L→E相聯(lián)的語義規(guī)則是一個過程，打印由E產(chǎn)生的表達(dá)式的值。我們可以理解為L的屬性是空的或是虛的。當(dāng)前18頁，總共141頁。例8.3

描述說明語句中各種變量的類型信息的語義規(guī)則。

產(chǎn)生式語義規(guī)則（1）D→TL

{L.in∶＝T.type}（2）T→int

{T.Type∶＝integer}（3）T→real

{T.Type∶＝real}（4）L→L1，id{L1.in∶＝L.in;

addtype（id.entry，L.in）}（5）L→id

{addtype（id.entry，L.in）}非終結(jié)符T有一個綜合屬性type，它的值由關(guān)鍵字決定（int或real）。與產(chǎn)生式D→TL相聯(lián)的語義規(guī)則L.in∶＝T.type將L.in的屬性值置為該說明語句指定的類型。屬性L.in將被沿著語法樹傳遞到下邊的結(jié)點使用，與L產(chǎn)生式相聯(lián)的規(guī)則里使用了它。這個例子里，繼承屬性在說明中為各個標(biāo)識符提供類型信息。

當(dāng)前19頁，總共141頁。圖8.4是句子intid1,id2的語法樹，使用表示屬性的傳遞情況。圖8.4屬性信息傳遞情況DTLLintid1，Id2當(dāng)前20頁，總共141頁。8.2中間代碼（語言）

中間代碼（語言）是一種特殊結(jié)構(gòu)的語言，編譯程序所使用的中間代碼有多種形式。按其結(jié)構(gòu)分常見的有逆波蘭式（后綴式）、三地址代碼（三元式、四元式）和樹形表示（抽象語法樹）、DAG表示。8.2.1逆波蘭式（后綴式）逆波蘭式最早是用于表示表達(dá)式的,后來計算機(jī)科學(xué)家把它應(yīng)用于表示程序語言的各種語法成分。當(dāng)前21頁，總共141頁。（一）特點

首先我們考察算術(shù)表達(dá)式（中綴式）的計值順序.例8.4中綴式的計值順序見圖8.5。

中綴式計值三個特點：（1）運算對象分別放在運算符（雙目運算符）的兩邊；（2）計值順序是根據(jù)運算符的優(yōu)先級別及結(jié)合性確定，使用括號可以改變計值順序；（3）運算符的排列順序不等價于計值順序。圖8.5中綴式的計值順序例①②③④⑤a+b*(c+d*(e–f))③③a+b*(c+d*(e–f))當(dāng)前22頁，總共141頁。后綴式計值三個特點：（1）不考慮運算符的優(yōu)先關(guān)系，又不使用括號；（2）運算符的排列順序就是計值順序；（3）運算對象放在運算符的前面。例：a＋b＊(c＋d＊(e－f))其逆波蘭式為：abcdef－＊＋＊＋當(dāng)前23頁，總共141頁。(二)定義逆波蘭式（后綴式）的一般形式為：若是一個K元運算符（K≥1），它對其運算對象e1,e2,…,ek作用的結(jié)果被表示為：

e1e2…ek

表達(dá)式E的后綴表示的遞歸定義：（1）如果E是變量或常數(shù)，那么E的后綴表示是E本身；（2）如果E是形如E1opE2的表達(dá)式，其中op是任意的二元運算符，那么E的后綴表示是E1′||E2′||op,其中；E1′和E2′分別是E1和E2的后綴表示，||稱為連接

（并置）運算符；（3）如果E是形如（E1），那么E的后綴表示就是E1的后綴表示。當(dāng)前24頁，總共141頁。（三）轉(zhuǎn)換（中綴式后綴式）轉(zhuǎn)換算法：轉(zhuǎn)換規(guī)則：設(shè)E為給定的中綴式，我們用<E>表示E的后綴式，則有：①<E1E2><E1>||<E2>||；②<（E）><E>；③<a>a,其中a表示變量或常數(shù)。對于給定的中綴式首先找出最后被計算的運算符，并把此運算符作為上述①式中的，使用上述規(guī)則轉(zhuǎn)換之；對中綴式的剩余部分重復(fù)上述過程，直至中綴式的每個量均被處理到為止。當(dāng)前25頁，總共141頁。表8.1把表達(dá)式翻譯為后綴式的語義規(guī)則描述

產(chǎn)生式 語義規(guī)則 E→E1opE2E.code∶=E1.code||E2.code||opE→（E1）E.code∶=E1.codeE→id E.code∶=id

表8.1給出了把表達(dá)式翻譯為后綴式的語義規(guī)則描述，其中E.code表示E后綴形式，op表示任意二元操作符，“||”表示后綴形式的連接。當(dāng)前26頁，總共141頁。例8.5有下面翻譯模式：E→TRR→＋T{print（‘＋’）}R1|－T{print（‘－’）}R1|εT→num{print（num.val）}把中綴表達(dá)式8+52翻譯成后綴表達(dá)式。解：ETRnum{print(8)}Rnum{print(8)}+T{print(‘+’)}R1num{print(8)}+num{print(5)}{print(‘+’)}R1num{print(8)}+num{print(5)}{print(‘+’)}T{print(‘’)}R1num{print(8)}+num{print(5)}{print(‘+’)}num{print(2)}{print(‘’)}R1num{print(8)}+num{print(5)}{print(‘+’)}num{print(2)}{print(‘’)}輸出：{print(8)}{print(5)}{print(‘+’)}{print(2)}{print(‘’)}

即：85+2–

當(dāng)前27頁，總共141頁。后綴式很容易擴(kuò)充到表達(dá)式以外的范圍。只要遵守運算對象后直接緊跟它們的運算符的規(guī)則即可。賦值語句的后綴表示：如有a∶＝b+c，則有abc+∶＝

轉(zhuǎn)向語句GOTOL的后綴表示為“Ljump”，運算對象L為語句標(biāo)號，運算符jump表示轉(zhuǎn)到某個標(biāo)號。當(dāng)前28頁，總共141頁。數(shù)組元素A[〈下標(biāo)表達(dá)式1〉，…，〈下標(biāo)表達(dá)式n〉]的后綴表示可表示為：〈下標(biāo)表達(dá)式1〉〈下標(biāo)表達(dá)式2〉……〈下標(biāo)表達(dá)式n〉A(chǔ)subs，運算符Subs表示求數(shù)組的下標(biāo)。條件語句ifEthenS1elseS2的后綴表示可表示為：ES1S2￥，把if-then-else看成三目運算符，用￥來表示。當(dāng)前29頁，總共141頁。8.2.2三地址代碼一般形式：x:=yopz如表達(dá)式x+y

z翻譯成的三地址代碼序列是

t1:=y

z

t2:=x+t1

常用的三地址表示:賦值語句x:=yopz，x:=opy，x:=y無條件轉(zhuǎn)移gotoL條件轉(zhuǎn)移ifxrelop

ygotoL過程調(diào)用paramx

和callp,n過程返回returny索引賦值x:=y[i]和x[i]:=y地址和指針賦值x:=&y，x:=y

和x:=y當(dāng)前30頁，總共141頁。四元式、三元式、間接三元式三地址代碼可看成中間代碼的一種抽象形式。編譯程序中，三地址代碼語句的具體實現(xiàn)可以用記錄表示，記錄中包含表示運算符和操作數(shù)的域。三地址代碼通常有三種表示方法：四元式、三元式、間接三元式。四元式結(jié)構(gòu)形式:(OP，ARG1，ARG2，RESULT)算符左運算對象右運算對象運算結(jié)果三元式結(jié)構(gòu)形式:編號(OP，ARG1，ARG2)間接三元式：由間接三元式序列和間接碼表組成。當(dāng)前31頁，總共141頁。例8.6有中綴式a:＝b*－c＋b*－c，求其等價的四元式和三元式。

四元式三元式算符左對象右對象結(jié)果量編號算符左對象右對象

oparg1arg2resultoparg1arg2minuscT1(1)minusc

＊bT1T2(2)＊b(1)

minuscT3(3)minusc

＊bT3T4(4)＊b(3)

＋T2T4T5(5)＋(4)(2)∶＝T5a(6)assigna圖8.6四元式、三元式結(jié)構(gòu)當(dāng)前32頁，總共141頁。例8.7有中綴式A+B*(C-D)+E/(C-D)^N，求其等價的幾種不同的三地址代碼序列的形式。四元式：（1）（－C

D

T1）（2）（*B

T1

T2）（3）（+

A

T2

T3）（4）（－C

D

T4）（5）（^

T4

N

T5）（6）（/

E

T5

T6）（7）（+T3

T6

T7）三元式：（1）（－C

D）（2）（*B（1））（3）（+

A（2））（4）（－C

D）（5）（^（4）N）（6）（/

E（5））（7）（+（3）（6））間接三元式：間接三元式序列（1）（－C

D）（2）（*B（1））（3）（+

A（2））（4）（^（1）N）（5）（/

E（4））（6）（+（3）（5））間接碼表（1）（2）（3）（1）（4）（5）（6）間接碼表表示了執(zhí)行三元式的順序。圖8.7幾種不同的三地址代碼序列當(dāng)前33頁，總共141頁。8.2.3圖形表示抽象語法樹是一種圖形化的中間表示，它的每一個葉結(jié)點都表示諸如常量或變量這樣的運算對象，而它的內(nèi)部結(jié)點則表示運算符；它不同于前述的語法樹，它展示了一個操作過程并同時描述了源程序的自然層次結(jié)構(gòu)；DAG（有向無環(huán)圖）以更緊湊的方式給出了同樣的信息（即對于相同的語法成分只給出一次），在圖中其結(jié)點的含義同抽象語法樹。當(dāng)前34頁，總共141頁。assigna++bcdcdminus(a)抽象語法樹assigna++bcdminus(b)DAG

圖8.8a:=(b+cd)+cd的圖形表示例：表達(dá)式a:=(b+cd)+cd的兩種圖形表示見圖8.8。當(dāng)前35頁，總共141頁。抽象語法樹是分析樹的濃縮表示：算符和關(guān)鍵字是作為內(nèi)部結(jié)點出現(xiàn)的。

語法制導(dǎo)翻譯可以基于分析樹，也可以基于抽象語法樹抽象語法樹的例子：if-then-elseBS1S2+*258圖8.9抽象語法樹的例子

抽象語法樹當(dāng)前36頁，總共141頁。

構(gòu)造抽象語法樹的語法制導(dǎo)定義

F.nptr:=mkleaf(num,num.val)

Fnum

F.nptr:=mkleaf(id,id.entry)

Fid

F.nptr:=E.nptr

F(E)

T.nptr:=F.nptr

T

F

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

T

T1*F

E.nptr:=T.nptr

ET

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

E

E1+T

語

義

規(guī)

則產(chǎn)生式圖8.10抽象語法樹的語法制導(dǎo)定義例子當(dāng)前37頁，總共141頁。例8.8a+5*b的抽象語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口圖8.11(a)a+5*b的抽象語法樹當(dāng)前38頁，總共141頁。E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口圖8.11(b)a+5*b的抽象語法樹當(dāng)前39頁，總共141頁。E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口圖8.11(c)a+5*b的抽象語法樹當(dāng)前40頁，總共141頁。E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口圖8.11(d)a+5*b的抽象語法樹當(dāng)前41頁，總共141頁。E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口圖8.11(e)a+5*b的抽象語法樹當(dāng)前42頁，總共141頁。E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口圖8.11(f)a+5*b的抽象語法樹當(dāng)前43頁，總共141頁。E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口圖8.11(g)a+5*b的抽象語法樹當(dāng)前44頁，總共141頁。E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口圖8.11(h)a+5*b的抽象語法樹當(dāng)前45頁，總共141頁。E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口圖8.11(i)a+5*b的抽象語法樹當(dāng)前46頁，總共141頁。8.3語法制導(dǎo)翻譯編譯程序的整個任務(wù)就是把源程序翻譯為目標(biāo)程序。實際上可以把每個編譯階段都看作是完成一定翻譯任務(wù)的處理過程：詞法分析階段把字符流翻譯為單詞流，語法分析階段把單詞流翻譯為語法樹，目標(biāo)代碼生成階段把語法樹翻譯為匯編語言等等。語法制導(dǎo)翻譯：在語法分析過程中，隨著分析的步步進(jìn)展，每當(dāng)進(jìn)行推導(dǎo)或歸約時，同步的去執(zhí)行每個產(chǎn)生式所附帶的語義規(guī)則描述的語義動作（或語義子程序），這樣進(jìn)行翻譯的辦法稱作語法制導(dǎo)翻譯。

當(dāng)前47頁，總共141頁。例8.9：把中綴算術(shù)表達(dá)式翻譯為后綴表示形式，給出如下語義描述：E→T+E1{E.code=T.code||E1.code||+}E→T{E.code=T.code}T→F*T1{T.code=F.code||T1.code||*}T→F{T.code=F.code}F→（E）{F.code=E.code}F→a{F.code=a}其中使用E.code，T.code和F.code分別表示其相應(yīng)的后綴式，"||"表示后綴式的連接。如果對于輸入串a(chǎn)+b*c采用最左分析，其形成的推導(dǎo)過程為：

ET+EF+Ea+Ea+Ta+T*Fa+F*F

a+b*Fa+b*c當(dāng)前48頁，總共141頁。

把語義規(guī)則計算帶入推導(dǎo)過程中，用(α，β)表示拓廣的句型,其中α是句型，β是翻譯的輸出形式，則有：(E,E.code)(T+E,T.code||E.code||+)(F+E,F.code||E.code||+

)

(a+E,a||E.code||+)

(a+T,a||T.code||+)

(a+F＊T,a||F.code||T.code||＊||+)

(a+b＊T,a||b||T.code||＊||+)

(a+b＊F,a||b||F.code||＊||+)

(a+b*c,a||b||c||＊||+)

去掉a||b||c||＊||+中的連結(jié)符，得到中綴表達(dá)式a+b＊c的后綴式abc＊+

。ET+EF+Ea+Ea+Ta+T*Fa+F*F

a+b*Fa+b*c當(dāng)前49頁，總共141頁。8.3.1基于屬性文法的處理方法處理方法：1）多遍掃描依賴圖樹遍歷2）一遍掃描基于屬性文法的處理過程(理論上):輸入串→語法樹→依賴圖→計算語義規(guī)則順序→語法分析樹遍歷→執(zhí)行語義規(guī)則語義規(guī)則的計算可能產(chǎn)生代碼，在符號表中存取信息，給出出錯信息或執(zhí)行其它動作。對輸入串的翻譯也就是根據(jù)語義規(guī)則進(jìn)行計算的結(jié)果。當(dāng)前50頁，總共141頁。8.3.2屬性依賴圖依賴圖是一個有向圖，用于描述分析樹中的屬性和屬性之間的相互依賴關(guān)系。依賴圖構(gòu)造算法：for語法樹中每一結(jié)點ndo

for結(jié)點n的文法符號的每一個屬性ado

為a在依賴圖中建立一個結(jié)點；for語法樹中每一個結(jié)點ndo

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

b:=f(c1，c2，…，ck)do

fori:=1tokdo

從ci結(jié)點到b結(jié)點構(gòu)造一條有向邊；注:在構(gòu)造依賴圖之前,要為每一個過程調(diào)用的語義規(guī)則引入一個虛綜合屬性，即在依賴圖中構(gòu)造一個結(jié)點。這樣，若屬性b依賴于屬性c，則從c的結(jié)點有一條有向邊連接到b的結(jié)點。當(dāng)前51頁，總共141頁。

例8.10：有屬性文法見表8.2，構(gòu)造intid1,id2,id3的分析樹依賴圖。產(chǎn)生式

語

義

規(guī)

則

D

TL

L.in:=T.type

Tint

T.type:=integer

Treal

T.type:=real

L

L1,id

L1.in:=L.in;

addtype(id.entry,L.in)

Lid

addtype(id.entry,L.in)表8.2說明語句的屬性文法當(dāng)前52頁，總共141頁。表8.2說明語句的屬性文法圖8.12(a)intid1,id2,id3的注釋分析樹產(chǎn)生式

語

義

規(guī)

則

D

TL

L.in:=T.type

Tint

T.type:=integer

Treal

T.type:=real

L

L1,id

L1.in:=L.in;

addtype(id.entry,L.in)

Lid

addtype(id.entry,L.in)

先構(gòu)造intid1,id2,id3的語法樹見圖8.12(a)所示。當(dāng)前53頁，總共141頁。再構(gòu)造intid1,id2,id3的分析樹的依賴圖(結(jié)點用數(shù)字表示)見圖8.12b。

D

TL

L.in:=T.typeDintT,id3LLLid2id1,1entry102entry3entryin98in76in54typeaddtype(id.entry,L.in)圖8.12(b)intid1,id2,id3的依賴圖當(dāng)前54頁，總共141頁。8.3.3語義規(guī)則的計算次序1）拓?fù)渑判驈囊蕾噲D的拓?fù)渑判蛑形覀兛梢缘玫接嬎阏Z義規(guī)則的次序，用這個順序來計算語義規(guī)則就得到了輸入串的翻譯。拓?fù)渑判颍航Y(jié)點的一種排序，使得有向邊只會從該次序中先出現(xiàn)的結(jié)點指向后出現(xiàn)的結(jié)點。例：圖8.12(b)的拓?fù)渑判驗椋?，2，3，4，5，6，7，8，9，10。一個依賴圖的任何拓?fù)渑判蚨冀o出了語法樹中結(jié)點的語義規(guī)則計算的有效順序。當(dāng)前55頁，總共141頁。根據(jù)例8.10的拓?fù)渑判蛭覀兛傻玫较铝姓Z義規(guī)則計算順序（其中an代表圖中與序號n的結(jié)點有關(guān)的屬性)：a4:=int;a5:=a4;addtype(id1，entry，a5);a7:=a5;addtype(id2，entry，a7);a9:=a7;addtype(id3，entry，a9);通過這些語義規(guī)則的計算將把類型值int填入到每個標(biāo)識符對應(yīng)的符號表項中去．也就是說，在拓?fù)渑判蛑?，在一個結(jié)點上，語義規(guī)則b:=f(c1,c2,…,ck)中屬性c1,c2,…,ck

在計算b之時是可用的。既屬性b依賴于屬性c1,c2,…,ck

。當(dāng)前56頁，總共141頁。2）屬性的計算過程圖8.12(a)intid1,id2,id3的語法樹DintT,id3LLLid2id1,

屬性計算有樹遍歷和一遍掃描兩種方法。樹遍歷：構(gòu)造輸入的語法樹見圖8.12(a)，當(dāng)前57頁，總共141頁。2）屬性的計算過程DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,圖8.13

intid1,id2,id3的注釋分析樹構(gòu)造帶有屬性分析樹見圖8.13。屬性計算有樹遍歷和一遍掃描兩種方法。樹遍歷：構(gòu)造輸入的語法樹見圖8.12(a)，當(dāng)前58頁，總共141頁。用深度優(yōu)先遍歷該分析樹。還可以采用一遍掃描的處理方法來計算屬性值。一遍掃描的處理方法不同于樹遍歷的方法，它不需要構(gòu)造實際語法樹，而是在語法分析的同時計算屬性值。如果需要的話，可以進(jìn)行多次遍歷，直至計算出所有屬性。當(dāng)前59頁，總共141頁。3）樹遍歷的屬性計算方法現(xiàn)在我們來考慮如何通過樹遍歷的方法計算屬性的值。通過樹遍歷計算屬性值的方法有多種。這些方法都假設(shè)語法樹已經(jīng)建立起了，并且樹中已帶有開始符號的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語法樹，直至計算出所有屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用多次遍歷（或稱遍）。當(dāng)前60頁，總共141頁。下面算法可對任何無循環(huán)的屬性文法進(jìn)行計算。While還有未被計算的屬性do

VisitNode(S)/*S是開始符號*/procedureVisitNode(N∶Node);begin

ifN是一個非終結(jié)符then

/*假設(shè)它的產(chǎn)生式為N→X1…Xm*/fori:=1tomdoifXi∈VNthen/*即Xi是非終結(jié)符*/

begin計算Xi的所有能夠計算的繼承屬性;

VisitNode(Xi)

End;

計算N的所有能夠計算的綜合屬性;end當(dāng)前61頁，總共141頁。例8.11考慮表8.3所給的屬性的文法G。表8.3語義規(guī)則中有較復(fù)雜的依賴關(guān)系

產(chǎn)生式語義規(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*3

Z→z Z.g∶=Z.h+1其中S有繼承屬性a，綜合屬性b；X有繼承屬性c、綜合屬性d；Y有繼承屬性e、綜合屬性f；Z有繼承屬性h、綜合屬性g。當(dāng)前62頁，總共141頁。

假設(shè)文法開始符號的繼承屬性S.a的初始值為0，則輸入串xyz的語法樹如圖8.14（a）所示。S.a=0XYZxyz(a)S.a=0Z.h=0g=1XYxyz(b)Z.h=0

.g=1X.c=1.d=2Yxyz(c)S.a=0,b=0Z.h=0.g=1X.c=1.d=2Y.e=0.f=0xyz(d)S.a=0,b=0圖8.14對文法G的屬性計算步驟（a）初始狀態(tài)；（b）對VisitNode(S)的第一次調(diào)用后；（c）對VisitNode(S)第二次調(diào)用后；（d）最終狀態(tài)當(dāng)前63頁，總共141頁。8.3.4S-屬性文法和自下而上翻譯S-屬性文法：僅僅使用綜合屬性的屬性文法。

1）綜合屬性的求值規(guī)則：產(chǎn)生式右部非終結(jié)符號的綜合屬性值取其下面產(chǎn)生式或左部同名非終結(jié)符號的綜合屬性值；產(chǎn)生式左部非終結(jié)符號的綜合屬性值用該產(chǎn)生式左部符號的繼承屬性或某個右部符號的屬性進(jìn)行計算；體現(xiàn)自底向上，自右向左的求值特性在語法樹中，一個結(jié)點的綜合屬性的值由其子結(jié)點的屬性值確定。而葉結(jié)點的（終結(jié)點）的綜合屬性值由詞法分析得到。因此，通常使用自底向上的方法在每個結(jié)點處執(zhí)行語義規(guī)則計算綜合屬性的值。當(dāng)前64頁，總共141頁。例8.12簡單臺式計算器的屬性文法。

F.val:=digit.lexval

F

digit

F.val:=E.val

F(E)

T.val:=F.val

T

F

T.val:=T1.val

*

F.val

T

T1

*

F

E.val:=T.val

E

T

E.val:=E1

.val+T.val

E

E1

+T

print(E.val)

L

E

n

語

義

規(guī)

則

產(chǎn)

生

式

表8.4簡單臺式計算器的屬性文法當(dāng)前65頁，總共141頁。8+5*2n的注釋分析樹見圖8.15。圖8.158+5*2n的注釋分析樹digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=5當(dāng)前66頁，總共141頁。2）考察S屬性的自下而上計算過程：將LR分析器符號棧中增加一個域來保存綜合屬性值。......X.xXY.yYZ.zZ......棧statevaltop若產(chǎn)生式A

→XYZ的語義規(guī)則是A.a:=f(X.x,Y.y,Z.z)那么歸約后有：......A.aA......top圖8.16LR分析器符號棧屬性域示意圖當(dāng)前67頁，總共141頁。例8.13把臺式計算器的語法制導(dǎo)定義改成棧操作代碼如圖8.17。F.val:=digit.lexval

F

digit

F.val:=E.val

F(E)

T.val:=F.val

T

F

T.val:=T1.val

*

F.val

T

T1

*

F

E.val:=T.val

E

T

E.val:=E1

.val+T.val

E

E1

+T

print(E.val)

L

E

n

代碼段產(chǎn)

生

式

......X.xXY.yYZ.zZ......棧statevaltopＥn圖8.17(a)語法制導(dǎo)定義改成棧操作代碼示意圖當(dāng)前68頁，總共141頁。例8.13把臺式計算器的語法制導(dǎo)定義改成棧操作代碼如圖8.17。F.val:=digit.lexval

F

digit

F.val:=E.val

F(E)

T.val:=F.val

T

F

T.val:=T1.val

*

F.val

T

T1*

F

E.val:=T.val

E

T

E.val:=E1

.val+T.val

E

E1

+T

print(val[top1])

L

E

n

代碼段產(chǎn)

生

式

......X.xXY.yYZ.zZ......棧statevaltopＥn圖8.17(b)語法制導(dǎo)定義改成棧操作代碼示意圖當(dāng)前69頁，總共141頁。例8.13把臺式計算器的語法制導(dǎo)定義改成棧操作代碼如圖8.17。F.val:=digit.lexval

F

digit

F.val:=E.val

F(E)

T.val:=F.val

T

F

T.val:=T1.val

*

F.val

T

T1

*

F

E.val:=T.val

E

T

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

E

E1

+T

print(val[top1])

L

E

n

代碼段產(chǎn)

生

式

......X.xXY.yYZ.zZ......棧statevaltopE1+T圖8.17(c)語法制導(dǎo)定義改成棧操作代碼示意圖當(dāng)前70頁，總共141頁。例8.13把臺式計算器的語法制導(dǎo)定義改成棧操作代碼如圖8.17。F.val:=digit.lexval

F

digit

F.val:=E.val

F(E)

T.val:=F.val

T

F

T.val:=T1.val

*

F.val

T

T1

*

F

E

T

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

E

E1

+T

print(val[top1])

L

E

n

代碼段產(chǎn)

生

式

......X.xXY.yYZ.zZ......棧statevaltopT圖8.17(d)語法制導(dǎo)定義改成棧操作代碼示意圖當(dāng)前71頁，總共141頁。例8.13把臺式計算器的語法制導(dǎo)定義改成棧操作代碼如圖8.17。F.val:=digit.lexval

F

digit

F.val:=E.val

F(E)

T.val:=F.val

T

F

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

T

T1

*

F

E

T

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

E

E1

+T

print(val[top1])

L

E

n

代碼段產(chǎn)

生

式

......X.xXY.yYZ.zZ......棧statevaltopT1*F圖8.17(e)語法制導(dǎo)定義改成棧操作代碼示意圖當(dāng)前72頁，總共141頁。例8.13把臺式計算器的語法制導(dǎo)定義改成棧操作代碼如圖8.17。F.val:=digit.lexval

F

digit

F.val:=E.val

F(E)

T

F

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

T

T1

*

F

E

T

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

E

E1

+T

print(val[top1])

L

E

n

代碼段產(chǎn)

生

式

......X.xXY.yYZ.zZ......棧statevaltopF圖8.17(f)語法制導(dǎo)定義改成棧操作代碼示意圖當(dāng)前73頁，總共141頁。例8.13把臺式計算器的語法制導(dǎo)定義改成棧操作代碼如圖8.17。F.val:=digit.lexval

F

digit

val[top2]

:=val[top1]

F(E)

T

F

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

T

T1

*

F

E

T

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

E

E1

+T

print(val[top1])

L

E

n

代碼段產(chǎn)

生

式

......X.xXY.yYZ.zZ......棧statevaltop)E(圖8.17(g)語法制導(dǎo)定義改成棧操作代碼示意圖當(dāng)前74頁，總共141頁。例8.13把臺式計算器的語法制導(dǎo)定義改成棧操作代碼如圖8.17。

F

digit

val[top2]

:=val[top1]

F(E)

T

F

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

T

T1*

F

E

T

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

E

E1

+T

print(val[top1])

L

E

n

代碼段產(chǎn)

生

式

......X.xXY.yYZ.zZ......棧statevaltopdigit圖8.17(h)語法制導(dǎo)定義改成棧操作代碼示意圖當(dāng)前75頁，總共141頁。8.3.5L-屬性文法在自上而下分析中的實現(xiàn)

8.3.5.1L-屬性文法

定義：L-屬性文法是下列屬性文法，如果對于每一個產(chǎn)生式AX1X2…Xn，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj（1≤

j≤n）的一個繼承屬性(inheritedattribute)，且這個繼承屬性僅依賴于：(1)產(chǎn)生式Xj在左邊符號X1X2…Xj-1的屬性;(2)A的繼承屬性。即繼承屬性的求值規(guī)則：產(chǎn)生式左部非終結(jié)符號的繼承屬性值取前面產(chǎn)生式右部該符號已有的繼承屬性值；產(chǎn)生式右部符號的繼承屬性值用該產(chǎn)生式左部符號的繼承屬性或出現(xiàn)在該符號左邊的符號的屬性值進(jìn)行計算。體現(xiàn)自頂向下，自左向右的求值特性S-屬性文法是L-屬性文法的一種。L-屬性文法允許一次遍歷就計算出所有屬性值。當(dāng)前76頁，總共141頁。L-屬性文法的輸入文法要求是LL(1)文法，可用自頂向下分析構(gòu)造分析器，在分析過程中可進(jìn)行屬性求值。例8.14

A→BC的屬性求值順序:A的繼承屬性（若A為開始符號則有指定值，否則由前面產(chǎn)生式右部符號的繼承屬性求得）B的繼承屬性（由A的繼承屬性求得）

B的綜合屬性（由后面產(chǎn)生式中左部符號為B的綜合屬性求得）C的繼承屬性（由A的繼承屬性和/或B的屬性求得）C的綜合屬性（由后面產(chǎn)生式左部符號為C的綜合屬性求得）A的綜合屬性（由A的繼承屬性和/或B及C的屬性求得）當(dāng)前77頁，總共141頁。8.3.5.2翻譯模式（翻譯方案，Translationschemes

）目前流行的語義處理方法有兩種：語法制導(dǎo)的定義和翻譯模式。語法制導(dǎo)的定義：構(gòu)造屬性文法時，不指明翻譯時語義規(guī)則的計算次序，這樣的屬性文法稱為語法制導(dǎo)的定義。其語義規(guī)則的計算次序要通過拓?fù)渑判虻确椒▉泶_定。在這里，屬性文法可以看作是關(guān)于語言翻譯的高級規(guī)范說明，其中隱去實現(xiàn)細(xì)節(jié)，使用戶從明確說明翻譯順序的工作中解脫出來。當(dāng)前78頁，總共141頁。翻譯模式：下面我們來討論翻譯模式。如果在構(gòu)造屬性文法時把語義規(guī)則用花括號{}括起來，插入到產(chǎn)生式右部的合適位置上，用以指明語義規(guī)則的計算次序，這樣的屬性文法稱為翻譯模式（或稱為翻譯方案）。這是語法分析與語義動作交錯進(jìn)行的表示方法，以此來表示語義動作在語法分析過程中的執(zhí)行時刻。這樣就可把某些實現(xiàn)細(xì)節(jié)表示出來。當(dāng)前79頁，總共141頁。例8.15把帶加號和減號的中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式的屬性文法，其中addop表示＋或－。

E→EaddopT{print（addop.lexeme）}|T

T→num{print（num.val）}圖8.182＋3－5的說明語義動作的語法分析樹（1）TET3{print(‘2’)}{print(‘5’)}{print(‘－’)}2－ET{print(‘+’)}＋E5{print(‘3’)}

如果采用LR分析方法，則其屬性計算很容易實現(xiàn)，比如在對串2＋3－5的分析的同時執(zhí)行語義動作輸出23＋5－。語法分析樹中加上虛線聯(lián)結(jié)的語義結(jié)點，形成一個可說明語義動作的樹。見圖8.18。當(dāng)前80頁，總共141頁。對于LL（1）這種自頂向下分析方法的分析過程，從概念上來說可以看成是深度優(yōu)先建立語法樹的過程。因此，我們可以在自頂向下語法分析的同時實現(xiàn)L-屬性文法的計算。要注意的是，上例是一個含左遞歸的文法，如果采用LL（1）分析必須改寫文法如下：E→TRR→addopTR1|εT→num這時對串2＋3－5分析的語法樹見圖8.19，而將后綴式23＋5－輸出的動作在語法樹中應(yīng)該出現(xiàn)的位置見圖8.20所示。圖8.19

2＋3－5語法樹RTETTRR23ε5＋－當(dāng)前81頁，總共141頁。RTETTRR2 3ε{print(‘5’)}{print(‘－’)}{print(‘2’)}{print(‘3’)}{print(‘＋’)}5＋－圖8.202＋3－5的說明語義動作的語法分析樹（2）圖8.19

2＋3－5語法樹RTETTRR23ε5＋－當(dāng)前82頁，總共141頁。例8.16：下面是一個簡單的翻譯模式例子，它把帶加號和減號的中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式。

E→TRR→addopT{print（addop.lexeme）}R1|εT→num{print（num.val）}

此例給出了可使用LL（1）分析方法的語義描述，不同的是，語義動作不是附在產(chǎn)生式右部的末尾，而是嵌入在產(chǎn)生式右部某些符號（如T和R）之間。當(dāng)前83頁，總共141頁。當(dāng)只需要綜合屬性時，情況最為簡單。在這種情況下，我們可以這樣來建立翻譯模式：為每一個語義規(guī)則建立一個包含賦值的動作，并把這個動作放在相應(yīng)的產(chǎn)生式右邊的末尾。設(shè)計翻譯模式時，我們必須注意某些限制以保證當(dāng)某個動作引用一個屬性時它必須是有定義的。例如，假設(shè)有下面的產(chǎn)生式和語義規(guī)則：產(chǎn)生式語義規(guī)則

T→T1*FT.val∶＝T1.val×F.val5我們建立產(chǎn)生式和語義動作：

T→T1*F{T.val∶＝T1.val×F.val}當(dāng)前84頁，總共141頁。如果既有綜合屬性又有繼承屬性，在建立翻譯模式時就必須特別小心。后面我們將看到滿足這三個條件的翻譯模式是如何在一般的自上而下和自下而上分析器中實現(xiàn)的。產(chǎn)生式右部的符號的繼承屬性必須在這個符號以前的動作中計算出來。一個動作不能引用這個動作右邊的符號的綜合屬性。產(chǎn)生式左部非終結(jié)符的綜合屬性只有在它所引用的所有屬性都計算出來以后才能計算。計算這種屬性的動作通?？煞旁诋a(chǎn)生式右端的末尾。當(dāng)前85頁，總共141頁。在第五章我們知道，為了構(gòu)造不帶回溯的自頂向下語法分析，必須消除文法中的左遞歸?，F(xiàn)在我們把前面討論過的消除左遞歸的算法加以擴(kuò)充，當(dāng)消除一個翻譯模式的基本文法的左遞歸時同時考慮屬性。這種方法適合帶綜合屬性的翻譯模式。這樣，許多屬性文法可以使用自頂向下分析來實現(xiàn)。下面舉一個例子。下面，我們討論L-屬性文法在自頂向下分析中的實現(xiàn)。為了便于說明動作的順序和屬性計算的順序，我們用翻譯模式進(jìn)行描述。當(dāng)前86頁，總共141頁。例8.17對圖8.21消除左遞歸。E→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}圖8.21帶左遞歸的文法的翻譯模式當(dāng)前87頁，總共141頁。對圖8.21消除左遞歸，構(gòu)造新的翻譯模式如圖8.22所示。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∶＝R1.s}T→（E）{T.val∶＝E.val}T→num{T.val∶＝num.val}圖8.22消除左遞歸后的翻譯模式E→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}圖8.21帶左遞歸的文法的翻譯模式當(dāng)前88頁，總共141頁。在圖8.22中的翻譯模式中，每個數(shù)都是由T產(chǎn)生的，并且T.val的值就是由屬性num.val給出的數(shù)的詞法值。子表達(dá)式9－5中的數(shù)字9是由最左邊的T生成的，但是減號和5是由根的右子結(jié)點R生成的。繼承屬性R.i從T.val得到值9。計算9－5并把結(jié)果4傳遞到中間的R結(jié)點，這是通過產(chǎn)生式中嵌入的下面動作實現(xiàn)：

{R1.i∶＝R.i－T.val}新的翻譯模式產(chǎn)生的表達(dá)式9－5＋2的帶注釋的語法樹如圖8.23所示。圖中箭頭指明了對表達(dá)式計算的順序。圖8.23計算表達(dá)式9－5＋2num.val=5T.val=2R.i=6R.i=4R.i=9T.val=5num.val=9T.val=9E－＋num.val=2ε當(dāng)前89頁，總共141頁。一般轉(zhuǎn)換左遞歸翻譯模式的方法簡述如下:假定翻譯模式為：

A→A1Y{A.a∶＝g(A1.a，Y.y)}