編譯原理課件 第6章 屬性文法及語(yǔ)法制導(dǎo)翻譯

本章在編譯程序中的地位

表格管理詞法分析器語(yǔ)法分析器語(yǔ)義分析與中間代碼產(chǎn)生優(yōu)化器目標(biāo)代碼生成器源程序單詞符號(hào)語(yǔ)法單位中間代碼中間代碼目標(biāo)代碼出錯(cuò)處理1教學(xué)要求掌握：兩種屬性:綜合屬性，繼承屬性基于屬性文法的處理方法---語(yǔ)法制導(dǎo)翻譯方法2教學(xué)內(nèi)容6.1屬性文法綜合屬性，繼承屬性，語(yǔ)義規(guī)則，屬性文法6.2基于屬性文法的處理方法語(yǔ)法制導(dǎo)翻譯，依賴(lài)圖法計(jì)算屬性，樹(shù)遍歷計(jì)算屬性，一遍掃描的處理方法，抽象語(yǔ)法樹(shù)3

CH.6屬性文法和語(yǔ)法制導(dǎo)翻譯在分析-綜合模式的編譯器中,語(yǔ)義分析是分析過(guò)程的最后一個(gè)步驟，只有在這一步才真正開(kāi)始考慮程序語(yǔ)言的意義，并著手把它們翻譯成某種中間代碼。這一過(guò)程通常采用的方法是屬性文法和語(yǔ)法制導(dǎo)翻譯方法。語(yǔ)法制導(dǎo)翻譯方法的基本思想是，根據(jù)翻譯的需要設(shè)置文法符號(hào)的屬性，用屬性描述語(yǔ)法結(jié)構(gòu)的語(yǔ)義，用屬性的計(jì)算完成翻譯。屬性文法使文法符號(hào)屬性值的計(jì)算和產(chǎn)生式相聯(lián)系。隨著語(yǔ)法分析的進(jìn)行，執(zhí)行屬性值的計(jì)算，從而完成語(yǔ)義分析和翻譯的任務(wù)。46.1屬性文法屬性文法,也稱(chēng)屬性翻譯文法或語(yǔ)法制導(dǎo)定義,是Knuth在1968年首先提出來(lái)的。屬性：在上下文無(wú)關(guān)文法的基礎(chǔ)上為每個(gè)文法符號(hào)X(終結(jié)符或非終結(jié)符)配備若干個(gè)相關(guān)的“值”---這些“值”就稱(chēng)為文法符號(hào)X的屬性。屬性值的設(shè)置和語(yǔ)法結(jié)構(gòu)的語(yǔ)義以及翻譯程序的需要有關(guān)。屬性代表與文法符號(hào)相關(guān)語(yǔ)義信息，如類(lèi)型、值、代碼序列、符號(hào)表內(nèi)容等5屬性、語(yǔ)義規(guī)則、屬性文法屬性一般分為兩類(lèi)：綜合屬性和繼承屬性。屬性和變量一樣，可以在語(yǔ)法分析過(guò)程中進(jìn)行計(jì)算和傳遞。語(yǔ)義規(guī)則：屬性的計(jì)算規(guī)則。屬性的加工和計(jì)算的過(guò)程即是語(yǔ)義處理的過(guò)程。屬性文法：以一個(gè)上下文無(wú)關(guān)文法為基礎(chǔ),為每個(gè)文法符號(hào)引進(jìn)一組屬性，對(duì)文法的每個(gè)產(chǎn)生式都配備一組與之相關(guān)聯(lián)的屬性的計(jì)算規(guī)則(語(yǔ)義規(guī)則),這樣得到的文法。屬性文法是對(duì)上下文無(wú)關(guān)文法的推廣。6屬性文法、語(yǔ)義規(guī)則(1)屬性文法的形式：產(chǎn)生式語(yǔ)義規(guī)則.

Ab:=f(c1,c2,…,ck)這里,f是一個(gè)函數(shù),表示屬性b依賴(lài)于屬性c1,c2,…,ck，而且規(guī)定b:(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)的屬性

。7屬性文法的說(shuō)明(1)P136(1)終結(jié)符只有綜合屬性,它由詞法分析器提供例如digit.lexval

表示單詞符號(hào)“數(shù)”的詞法值

id.entry表示單詞符號(hào)“標(biāo)識(shí)符”的符號(hào)表入口(2)非終結(jié)符既可以有綜合屬性也可以有繼承屬性，在屬性文法的語(yǔ)義規(guī)則中計(jì)算(3)關(guān)于屬性計(jì)算的規(guī)定①文法的開(kāi)始符號(hào)的所有繼承屬性作為屬性計(jì)算前的初始值。②一般來(lái)講，對(duì)出現(xiàn)在產(chǎn)生式AX1X2…Xn左邊的非終結(jié)符A的綜合屬性和出現(xiàn)在產(chǎn)生式右部的符號(hào)Xi的繼承屬性都必須提供一個(gè)計(jì)算規(guī)則。8屬性文法的說(shuō)明(2)③與產(chǎn)生式AX1X2…Xn

相關(guān)聯(lián)的屬性計(jì)算不能有A的繼承屬性和Xi的綜合屬性的計(jì)算規(guī)則。④出現(xiàn)在產(chǎn)生式左邊非終結(jié)符A的繼承屬性和出現(xiàn)在產(chǎn)生式右邊符號(hào)Xi的綜合屬性由其它產(chǎn)生式的屬性規(guī)則計(jì)算或者由屬性計(jì)算器的參數(shù)提供。9屬性文法、語(yǔ)義規(guī)則(2)屬性文法的形式：產(chǎn)生式語(yǔ)義規(guī)則.

Ab:=f(c1,c2,…,ck)例如P137.表6.1的屬性文法:

EE1+TE.val:=E1.val+T.val例如P139.表6.2的屬性文法:

DTLL.in:=T.typeLL1,idL1.in:=L.in綜合屬性綜合屬性繼承屬性繼承屬性繼承屬性10例,P137.

假設(shè)：產(chǎn)生式語(yǔ)義規(guī)則ABCA.b:=A.a+B.cC.d:=B.c+1

A有綜合屬性b和繼承屬性aB有綜合屬性cC有繼承屬性d繼承屬性A.a和綜合屬性B.c在其他適當(dāng)?shù)牡胤接?jì)算。11語(yǔ)義規(guī)則所描述的工作語(yǔ)義規(guī)則所描述的工作可以是任何希望的翻譯工作，如:屬性計(jì)算、靜態(tài)語(yǔ)義檢查、符號(hào)表操作、中間代碼生成、報(bào)告出錯(cuò)，等等。語(yǔ)義規(guī)則可能產(chǎn)生副作用(如產(chǎn)生代碼)，也可能不是變?cè)膰?yán)格函數(shù)b:=f(c1,c2,…,ck)，如某個(gè)規(guī)則給出可用的下一個(gè)數(shù)據(jù)單元的地址。這樣的語(yǔ)義規(guī)則通常寫(xiě)成過(guò)程調(diào)用或過(guò)程段---這時(shí)認(rèn)為定義了一個(gè)虛屬性。12屬性文法舉例：P137.表6.1一個(gè)簡(jiǎn)單的臺(tái)式計(jì)算器的屬性文法。輸入一個(gè)含+、*、(、)和數(shù)字的算術(shù)表達(dá)式(文法的句子),計(jì)算并輸出其值,輸入行以n結(jié)束。產(chǎn)生式語(yǔ)義規(guī)則LEn

Print(E.val)

EE1+T

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

E.val:=T.valTT1*FT.val:=T1.val*F.valTF

T.val:=F.valF(E)

F.val:=E.valFdigit

F.val:=digit.lexval1.

非終結(jié)符E,T,F有綜合屬性val---表達(dá)式值2.

終結(jié)符digit有綜合屬性lexval---數(shù)的二進(jìn)制值，由詞法分析器提供3.注：同一個(gè)產(chǎn)生式的相同非終結(jié)符加上下標(biāo)，以區(qū)分這些非終結(jié)符的屬性值引用的二義性13兩種屬性：綜合屬性綜合屬性用于“自下而上”傳遞信息。綜合屬性：在語(yǔ)法樹(shù)中，一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。通常結(jié)合使用自下而上的分析方法在每一個(gè)結(jié)點(diǎn)處使用語(yǔ)義規(guī)則計(jì)算綜合屬性的值---由下層子結(jié)點(diǎn)的屬性值計(jì)算上層父結(jié)點(diǎn)的綜合屬性值，隨著自下而上語(yǔ)法分析的進(jìn)行，最終可計(jì)算出開(kāi)始符號(hào)的綜合屬性值。AX1X2…XnA.bX1.c1X2.c2…Xn.

ckAX1X2…Xnb:=f(c1,c2,…,ck)帶注釋的語(yǔ)法樹(shù)14綜合屬性舉例：例6.1綜合屬性的使用及其自下而上的計(jì)算過(guò)程P137.表6.1臺(tái)式計(jì)算器的屬性文法，輸入一個(gè)表達(dá)式(以n結(jié)尾)，計(jì)算并打印其值。例如：輸入表達(dá)式3*5+4n，輸出數(shù)值19。P138.圖6.1給出了輸入串3*5+4n的帶注釋的語(yǔ)法樹(shù)–屬性化的語(yǔ)法樹(shù)。綜合屬性X.val值隨著自下而上語(yǔ)法分析的進(jìn)行，自下而上的計(jì)算、傳遞和流動(dòng)---在每次歸約時(shí)執(zhí)行語(yǔ)義規(guī)則，計(jì)算屬性值，最終計(jì)算出開(kāi)始符號(hào)的綜合屬性值，打印出來(lái)完成翻譯。見(jiàn)下頁(yè)圖15digitlexvaldigitlexvaldigitlexvalFvalT1valFvalTval*E1valFvalTval+EvalLnPrint(E.val)翻譯3*5+4n求表達(dá)式值=3=3=5=5=15=15=4=4=4=19=316兩種屬性：繼承屬性繼承屬性用于“自上而下”傳遞信息。繼承屬性：在語(yǔ)法樹(shù)中，一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和(或)兄結(jié)點(diǎn)的某些屬性確定。可以用繼承屬性來(lái)表示程序語(yǔ)言結(jié)構(gòu)中的上下文依賴(lài)關(guān)系。繼承屬性的計(jì)算可以結(jié)合自上而下的語(yǔ)法分析進(jìn)行。A

X1…X

…XnA.ck

X1.c1…X.b…XnAX1X2…Xnb:=f(c1,c2,…,ck)17表6.2帶有繼承屬性L(fǎng).in的屬性文法

產(chǎn)生式語(yǔ)義規(guī)則

DTLLin:=TtypeTintTtype:=integerTrealTtype:=realLL1,idL1

in:=Linaddtype(identry,Lin)Lidaddtype(identry,Lin)

例6.2說(shuō)明句的帶有繼承屬性計(jì)算的屬性文法T.type是綜合屬性---標(biāo)識(shí)符的類(lèi)型L.in為繼承屬性---傳遞類(lèi)型信息18繼承屬性的使用和計(jì)算：例6.2繼承屬性的使用及其自上而下的計(jì)算過(guò)程P137.表6.2的屬性文法，用繼承屬性L(fǎng).in

為說(shuō)明語(yǔ)句中的各個(gè)標(biāo)識(shí)符提供類(lèi)型信息。例如：說(shuō)明語(yǔ)句reala,b,c;inti,j,k;T.type是綜合屬性,由說(shuō)明語(yǔ)句中的關(guān)鍵字real/int確定,結(jié)合產(chǎn)生式Tint或Treal

賦值T.type:=integer或real。TintT.type:=integerTreal

T.type:=realT.typeintT.typereal19繼承屬性的使用和計(jì)算：例6.2續(xù)例6.2,

P137.表6.2屬性文法，用繼承屬性in為說(shuō)明語(yǔ)句中的各個(gè)標(biāo)識(shí)符提供類(lèi)型信息。L.in繼承屬性,在DTLL.in:=T.typeLL1,id

L1.in:=L.in中計(jì)算。D

T.type

L.inL.inL1.in，id

依賴(lài)于兄依賴(lài)于父Addtype(id.entry,L.in)把標(biāo)識(shí)符的類(lèi)型信息填入符號(hào)表,入口為id.entry---這個(gè)過(guò)程定義了一個(gè)虛屬性。20圖6.2說(shuō)明語(yǔ)句

realid1,id2,id3

的帶有繼承屬性的語(yǔ)法樹(shù)繼承屬性in的值自上而下從左到右計(jì)算、傳遞和流動(dòng)。三個(gè)L結(jié)點(diǎn)的L.in分別給出標(biāo)識(shí)符id1、id2和id3的類(lèi)型。過(guò)程addtype(id.entry,L.in)把id的類(lèi)型填入符號(hào)表。id3T.type=realDL.in=realL.in=realrealL.in=real,id1id2,216.2基于屬性文法的處理方法屬性文法：產(chǎn)生式語(yǔ)義規(guī)則.

Aα

b:=f(c1,c2,…,ck)

語(yǔ)義規(guī)則的計(jì)算可以執(zhí)行任何翻譯動(dòng)作。對(duì)輸入串的翻譯也就是根據(jù)語(yǔ)義規(guī)則進(jìn)行計(jì)算得出結(jié)果。屬性文法是比較抽象的翻譯說(shuō)明，隱藏了一些實(shí)現(xiàn)細(xì)節(jié),主要是無(wú)須指明翻譯時(shí)語(yǔ)義規(guī)則的計(jì)算次序。本節(jié)討論語(yǔ)義規(guī)則的計(jì)算方法，指明屬性文法中語(yǔ)義規(guī)則的計(jì)算次序，從而把語(yǔ)義規(guī)則改造為計(jì)算屬性的語(yǔ)義程序，把靜態(tài)的語(yǔ)義規(guī)則改寫(xiě)為可動(dòng)態(tài)執(zhí)行的語(yǔ)義動(dòng)作---語(yǔ)法制導(dǎo)翻譯方法。22語(yǔ)法制導(dǎo)翻譯法語(yǔ)法制導(dǎo)翻譯法：由源程序的語(yǔ)法結(jié)構(gòu)所驅(qū)動(dòng)的處理辦法。這種處理方法是基于屬性文法的處理過(guò)程：①對(duì)單詞符串進(jìn)行語(yǔ)法分析,構(gòu)造帶屬性的語(yǔ)法樹(shù)②根據(jù)需要遍歷語(yǔ)法樹(shù),并在語(yǔ)法樹(shù)的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算即得翻譯結(jié)果。P139.圖6.3語(yǔ)法制導(dǎo)翻譯的輪廓:

輸入串語(yǔ)法樹(shù)(帶屬性注釋)語(yǔ)法分析深度優(yōu)先樹(shù)遍歷對(duì)輸入串的翻譯結(jié)果進(jìn)行計(jì)算拓?fù)渑判蛘Z(yǔ)義規(guī)則計(jì)算次序結(jié)點(diǎn)屬性間依賴(lài)關(guān)系的依賴(lài)圖構(gòu)造23所謂遍歷是指沿著某條搜索路線(xiàn)，依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪(fǎng)問(wèn)。訪(fǎng)問(wèn)結(jié)點(diǎn)所做的操作依賴(lài)于具體的應(yīng)用問(wèn)題。

24一遍掃描的語(yǔ)法制導(dǎo)翻譯一個(gè)具體的語(yǔ)法制導(dǎo)翻譯的實(shí)現(xiàn)不一定非要按圖6.3的輪廓不可。在某些情況下可用一遍掃描實(shí)現(xiàn)屬性文法的語(yǔ)義規(guī)則計(jì)算---即在語(yǔ)法分析的同時(shí)完成語(yǔ)義規(guī)則的計(jì)算。無(wú)須明顯地構(gòu)造語(yǔ)法樹(shù)或依賴(lài)圖。此節(jié)以后的各節(jié)以及CH7.都討論這種特殊方法---一遍掃描的語(yǔ)法制導(dǎo)翻譯方法。一遍掃描的語(yǔ)法制導(dǎo)翻譯輪廓:

輸入串───翻譯結(jié)果語(yǔ)法分析的同時(shí)完成語(yǔ)義規(guī)則的計(jì)算256.2.1依賴(lài)圖語(yǔ)義規(guī)則建立了屬性之間的依賴(lài)關(guān)系，這些關(guān)系可以用圖來(lái)表示，這樣的圖稱(chēng)為屬性依賴(lài)圖。語(yǔ)法樹(shù)結(jié)點(diǎn)屬性的依賴(lài)圖是一個(gè)有向圖：結(jié)點(diǎn)：語(yǔ)法樹(shù)結(jié)點(diǎn)的屬性(綜合屬性或繼承屬性)有向邊：屬性的依賴(lài)關(guān)系，如果屬性b依賴(lài)于屬性c，即b:=f(c)，則:語(yǔ)義規(guī)則b:=f(c1,c2,…,ck)，b可能是一個(gè)虛綜合屬性(即沒(méi)有b,f是一個(gè)過(guò)程)，其依賴(lài)圖見(jiàn)右圖。依賴(lài)圖構(gòu)造方法見(jiàn)P140.bcbc1ckc2…26依賴(lài)圖：例6.3簡(jiǎn)例:下面屬性文法的依賴(lài)圖：AXYA.a:=f(X.x,Y.y)X.i:=g(A.a,Y.y)

例6.3:下面的屬性文法的依賴(lài)圖EE1+E2

E.val:=E1.val+E2.val語(yǔ)法樹(shù)EE1+E2依賴(lài)圖

P141.圖6.4E.valE1.valE2.valA.aX.iX.xY.yA

XY27例6.4圖6.5句子

realid1,id2,id3

的語(yǔ)法樹(shù)及依賴(lài)圖TLLid3Lid2Did1real,,4typein5L.in:=T.typein7L1.in:=L.inin9L1.in:=L.in3entry6addtype(id.entry,L.in)2entry8addtype(id.entry,L.in)1entry10addtype(id.entry,L.in)結(jié)點(diǎn)1、2、3是id.entry屬性結(jié)點(diǎn)6、8、10代表虛屬性有向邊表示屬性的依賴(lài)關(guān)系數(shù)字標(biāo)識(shí)結(jié)點(diǎn)表示計(jì)算次序28良定義的屬性文法對(duì)語(yǔ)義規(guī)則b:=f(c1,c2,…,ck)來(lái)說(shuō),只有在屬性c1,c2,…,ck均已知的情況才可以使用來(lái)計(jì)算b。但，有時(shí)會(huì)出現(xiàn)一個(gè)屬性對(duì)另一個(gè)屬性的循環(huán)依賴(lài)關(guān)系。如果一屬性文法不存在屬性之間的循環(huán)依賴(lài)關(guān)系，那么該屬性文法為良定義的。為了設(shè)計(jì)編譯程序，我們只處理良定義的屬性文法。例如設(shè)p，c1，c2都是屬性，以下計(jì)算規(guī)則就無(wú)法對(duì)p求值。p:=f1(c1)c1:=f2(c2)c2:=f3(p)DAG圖：良定義屬性文法的依賴(lài)圖，

無(wú)環(huán)有向圖(DirectedAcyclicGraph)pc2c129依賴(lài)圖法：屬性的計(jì)算次序1.一個(gè)有向非循環(huán)圖(DAG圖)的拓?fù)湫?是圖中結(jié)點(diǎn)的任何順序m1,m2,…,mk,使得有向邊必須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)。也就是說(shuō)，如果mimj

是mi

到mj

的一條邊，那么在序列中mi必須出現(xiàn)在mj

之前。2.一個(gè)依賴(lài)圖(DAG圖)的任何拓?fù)渑判蚨冀o出一個(gè)語(yǔ)法樹(shù)中結(jié)點(diǎn)的語(yǔ)義規(guī)則計(jì)算的有效順序。這就是說(shuō)，在拓?fù)渑判蛑?，在一個(gè)結(jié)點(diǎn)上，語(yǔ)義規(guī)則b:=f(c1,c2,…ck)中的屬性c1,c2,…ck在計(jì)算b以前都是可用的。30例6.5

P141.圖6.5的依賴(lài)圖的一個(gè)拓?fù)渑判蚴牵?/p>

1，2，3，4，5，6，7，8，9，10由此拓?fù)湫蚩梢缘玫较旅娴某绦?an代表與n有關(guān)的屬性),該程序把3個(gè)標(biāo)識(shí)符a,b,c的類(lèi)型信息(real)填入符號(hào)表中每個(gè)標(biāo)識(shí)符對(duì)應(yīng)的符號(hào)表項(xiàng)中。程序

a4:=real;語(yǔ)義規(guī)則

T.type:=reala5:=a4;L.in:=T.typeaddtype(id3entry,a5);虛屬性6a7:=a5;L1.in:=L.inaddtype(id2entry,a7);虛屬性8a9:=a7;L1.in:=L.inaddtype(id1entry,a9);虛屬性10依賴(lài)圖法屬性的計(jì)算次序：例

31屬性文法說(shuō)明的語(yǔ)法制導(dǎo)翻譯是很精確的：(1)基礎(chǔ)文法用于建立輸入串的語(yǔ)法分析樹(shù)(可帶屬性注釋);(2)構(gòu)造對(duì)應(yīng)語(yǔ)法樹(shù)的依賴(lài)圖;(3)對(duì)依賴(lài)圖進(jìn)行拓?fù)渑判?(4)從拓?fù)湫虻玫接?jì)算語(yǔ)義規(guī)則的次序;(5)按此次序計(jì)算語(yǔ)義規(guī)則便得到輸入串的翻譯結(jié)果。依賴(lài)圖法屬性的計(jì)算次序：說(shuō)明

326.2.2樹(shù)遍歷的屬性計(jì)算方法通過(guò)語(yǔ)法樹(shù)遍歷計(jì)算屬性值的方法有很多種。這些方法都假設(shè)：1.語(yǔ)法樹(shù)已經(jīng)建立起來(lái)了，并且樹(shù)中已帶有開(kāi)始符號(hào)的繼承屬性和終結(jié)符的綜合屬性。2.然后以某種次序遍歷語(yǔ)法樹(shù)，直至計(jì)算出所有結(jié)點(diǎn)的屬性值。最常用的遍歷方法是深度優(yōu)先，對(duì)語(yǔ)法樹(shù)自上而下從左到右遍歷的方法。對(duì)遍歷到的結(jié)點(diǎn)計(jì)算其所有能夠計(jì)算的屬性值?？赡苄枰褂枚啻螛?shù)遍歷，直到把所有的結(jié)點(diǎn)的所有屬性都計(jì)算出來(lái)。P142.有一個(gè)深度優(yōu)先樹(shù)遍歷的算法，對(duì)任何良定義的屬性文法進(jìn)行屬性的計(jì)算。用例子說(shuō)明。33深度優(yōu)先樹(shù)遍歷計(jì)算屬性：例6.6

P143.表6.3的屬性文法。屬性S.a(=0)繼,S.b綜;X.c繼,X.d綜;Y.e繼,Y.f綜;Z.h繼,Z.g綜圖6.6產(chǎn)生式語(yǔ)義規(guī)則SXYZX.c:=Z.gY.e:=S.bZ.h:=S.aS.b:=X.d-2Xx

X.d:=2*X.cYy

Y.f:=Y.e*3Zz

Z.g:=Z.h+1xyz.h=0第一次遍歷S.a=0

XYZ.g=1.d=2.c=1.b=0第二次遍歷.e=0.f=0第三次遍歷346.2.3一遍掃描的處理方法與樹(shù)遍歷的屬性計(jì)算方法不同，一遍掃描的處理方法是在語(yǔ)法分析的同時(shí)計(jì)算屬性值。這種屬性計(jì)算方法與兩個(gè)因素密切相關(guān):1.所采用的語(yǔ)法分析方法(自上而下或自下而上)。2.屬性的計(jì)算次序，即語(yǔ)法分析到什么時(shí)候計(jì)算屬性。一遍掃描的處理方法語(yǔ)義規(guī)則執(zhí)行的時(shí)間:1.在自上而下語(yǔ)法分析中，若一個(gè)產(chǎn)生式匹配輸入串成功時(shí)執(zhí)行與此產(chǎn)生式相應(yīng)的語(yǔ)義規(guī)則。2.在自下而上語(yǔ)法分析中，當(dāng)一個(gè)產(chǎn)生式被用于進(jìn)行歸約時(shí)，此產(chǎn)生式相應(yīng)的語(yǔ)義規(guī)則就被計(jì)算。35一遍掃描的處理方法按一遍掃描的編譯程序模型來(lái)理解語(yǔ)法制導(dǎo)翻譯方法，直觀(guān)上說(shuō)是為基礎(chǔ)文法的每個(gè)產(chǎn)生式配上一組語(yǔ)義規(guī)則，并且在語(yǔ)法分析的同時(shí)執(zhí)行這些語(yǔ)義規(guī)則。一遍掃描的屬性計(jì)算方法是語(yǔ)法分析工作和語(yǔ)義規(guī)則的計(jì)算穿插進(jìn)行。但以語(yǔ)法分析作主導(dǎo)。S-屬性文法(僅含綜合屬性的屬性文法)可用于一遍掃描的自下而上分析。L-屬性文法(含有繼承屬性的屬性文法)可用于一遍掃描的自上而下分析。366.2.4抽象語(yǔ)法樹(shù)語(yǔ)法制導(dǎo)翻譯以語(yǔ)法樹(shù)作基礎(chǔ),實(shí)際上,語(yǔ)法樹(shù)可以作為一種合適的中間語(yǔ)言形式?，F(xiàn)在對(duì)語(yǔ)法樹(shù)進(jìn)行改造，去掉那些對(duì)翻譯不必要的信息，將語(yǔ)法樹(shù)進(jìn)行抽象---抽象語(yǔ)法樹(shù)。在表達(dá)式的抽象語(yǔ)法樹(shù)中，運(yùn)算符、關(guān)鍵字不作葉子結(jié)點(diǎn)而作為內(nèi)部結(jié)點(diǎn)，葉子結(jié)點(diǎn)只是運(yùn)算量。抽象語(yǔ)法樹(shù)也可以屬性化，給結(jié)點(diǎn)加上屬性變成帶附注的抽象語(yǔ)法樹(shù)。語(yǔ)法制導(dǎo)翻譯既可以基于語(yǔ)法分析樹(shù)也可以基于抽象語(yǔ)法樹(shù)進(jìn)行，采用的基本方法是一樣的。37抽象語(yǔ)法樹(shù)：簡(jiǎn)例例，為下面文法的句子a-4+c

建立抽象語(yǔ)法樹(shù)。EE+T|E－T|TT(E)Tid|num為每個(gè)運(yùn)算量或運(yùn)算符號(hào)都建立一個(gè)結(jié)點(diǎn)。可以根據(jù)表達(dá)式的運(yùn)算順序自下而上的構(gòu)造---手工構(gòu)造。a－+c4抽象語(yǔ)法樹(shù)運(yùn)算符作內(nèi)部結(jié)點(diǎn)id(a)EE－TE+TTnum(4)id(c)語(yǔ)法樹(shù)38抽象語(yǔ)法樹(shù)的實(shí)現(xiàn)抽象語(yǔ)法樹(shù)中的每一個(gè)結(jié)點(diǎn)可以由包含幾個(gè)域的記錄來(lái)實(shí)現(xiàn)；有向邊用指針實(shí)現(xiàn)。在一個(gè)運(yùn)算量對(duì)應(yīng)的結(jié)點(diǎn)(葉結(jié))中,一個(gè)域標(biāo)識(shí)運(yùn)算量，另一個(gè)域是該運(yùn)算量的屬性值(或指針)。在一個(gè)運(yùn)算符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)中,一個(gè)域標(biāo)識(shí)運(yùn)算符號(hào)，其它域包含指向運(yùn)算分量的結(jié)點(diǎn)的指針。運(yùn)算符號(hào)通常叫做這個(gè)結(jié)點(diǎn)的標(biāo)號(hào)。進(jìn)行翻譯時(shí)，抽象語(yǔ)法樹(shù)中的結(jié)點(diǎn)可能會(huì)用附加域來(lái)存放結(jié)點(diǎn)的屬性值(或指向?qū)傩缘闹羔槪?。numvalid.op..Toentryofid右子樹(shù)根結(jié)左子樹(shù)根結(jié)39建立表達(dá)式的抽象語(yǔ)法樹(shù)使用的函數(shù),這些函數(shù)返回新建立結(jié)點(diǎn)的指針。1.mknode(op,left,right)

建立一個(gè)運(yùn)算符號(hào)結(jié)點(diǎn)，標(biāo)號(hào)是op,兩個(gè)域