第6章 屬性文法

1、1詞法分析與語法分析是編譯程序的一部分。在早期的一些編譯程序中，是在語法分析的基礎(chǔ)上根據(jù)源程序中各語法成份的語義，直接產(chǎn)生機器語言或匯編語言形式的目標代碼目標代碼。現(xiàn)在的編譯系統(tǒng)一般都將經(jīng)過語法分析的源程序先翻譯為某種形式的中間語言代碼中間語言代碼，然后再將其翻譯為目標代碼。 ：使編譯程序各組成部分功能更單一;使得編譯程序的邏輯結(jié)構(gòu)更為清晰，從而使編譯程序更易于編寫與調(diào)整;同時為代碼優(yōu)化和程序的可移植性提供了條件 后面要討論的中間代碼生成中間代碼生成，是指把單詞符號串形式的源程序轉(zhuǎn)換為另一種等價的便于代碼優(yōu)化處理和目標代碼生成的表示方法。 目前常見的中間語言有逆波蘭表示逆波蘭表示、三元式三元式

2、、四元式四元式等等。 遺憾的是，中間代碼生成與語言的語義密切相關(guān)，而語義的形式化描述是一件非常困難的事情; 存在一種稱為語法制導翻譯的模式，這種模式實際上是對上下文無關(guān)文法的一種擴充。 :對文法中的每個產(chǎn)生式都附加一個語義動作或語義子程序,在語法分析過程中，每當需要使用一個產(chǎn)生式進行推導或歸約，語法分析程序除執(zhí)行相應的語法分析動作外，還要執(zhí)行相應的語義動作或調(diào)用相應的語義子程序。 這種模式既把語法分析與語義處理分開，又令其平行地進行，讓其在同一遍掃描中同時完成語法分析和語義處理兩項工作。 由此可見，抽象文法符號的具體語義信息，是在。 文法符號X的語義信息我們稱之為或簡稱為（Attributes

3、）。 我們用形如X.ATTR的記號來表示文法符號X的相關(guān)。 如果一個文法符號X在一產(chǎn)生式中多次出現(xiàn)，為了在語義上能夠?qū)ζ溥M行區(qū)分，可添加不同的上標。 文法符號及其語義屬性 例如,文法GEGE:EE(1)+TE.Val=E(1).val+T.val;ET E.Val=T.Val;TdigitT.Val=digit; 為了能在語法分析過程中平行地進行語義處理，可在語法分析棧旁邊并行地設(shè)置一個 語法分析棧語義分析棧TT.Val+E#源語言程序源語言程序中間代碼中間代碼匯編代碼匯編代碼詞法分析詞法分析語義分析語義分析語法分析語法分析中間代碼生成中間代碼生成代碼生成代碼生成在編譯中的邏輯階段在編譯中的邏

4、輯階段前端處理前端處理后端處理后端處理語義處理語義處理語義處理（語義分析和中間代碼生成）源語言程序源語言程序匯編代碼匯編代碼詞法分析詞法分析語義分析語義分析語法分析語法分析代碼生成代碼生成前端處理前端處理后端處理后端處理 語義處理語義處理語義處理7第六章屬性文法和語法制導翻譯第六章屬性文法和語法制導翻譯6.1 屬性文法屬性文法6.2 基于屬性文法的處理方法基于屬性文法的處理方法6.3 S S屬性文法的自下而上計算屬性文法的自下而上計算6.4 L屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯6.5 自下而上計算繼承屬性自下而上計算繼承屬性86.1 屬性文法屬性文法一、基本概念一、基本概念1.1.屬

5、性屬性廣義：廣義：用以描述事物或人的特征、性質(zhì)、品質(zhì)等等。用以描述事物或人的特征、性質(zhì)、品質(zhì)等等。狹義：狹義：代表與文法符號相關(guān)的信息，其信息值即為代表與文法符號相關(guān)的信息，其信息值即為 屬性值。屬性值。例如：例如：其類型、值、代碼序列、符號表內(nèi)容等。其類型、值、代碼序列、符號表內(nèi)容等。9（1）屬性與變量一樣，可以進行屬性與變量一樣，可以進行計算計算和和傳遞傳遞。6.1 屬性文法屬性文法（2）屬性加工的過程即是屬性加工的過程即是語義處理的過程語義處理的過程。（3）屬性屬性 綜合屬性：綜合屬性：繼承屬性：繼承屬性：用于用于“自上而下自上而下”傳遞信息。傳遞信息。用于用于“自下而上自下而上”傳遞信

6、息。傳遞信息。注注: :102. 語義規(guī)則語義規(guī)則 為文法的每一個產(chǎn)生式配備的為文法的每一個產(chǎn)生式配備的計算屬性的計計算屬性的計算規(guī)則算規(guī)則，稱為語義規(guī)則。，稱為語義規(guī)則。3. 屬性文法屬性文法在上下文無關(guān)文法的基礎(chǔ)上，為在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符每個文法符號號（終結(jié)符或非終結(jié)符）引進（終結(jié)符或非終結(jié)符）引進一組屬性一組屬性，且讓該文，且讓該文法中的法中的重寫規(guī)則重寫規(guī)則附加上附加上語義規(guī)則語義規(guī)則時，稱該上下文無時，稱該上下文無關(guān)文法為屬性文法。關(guān)文法為屬性文法。6.1 屬性文法屬性文法注：語法制導翻譯是指在語法分析的過程中，完成附加在所使注：語法制導翻譯是指在語法分析的過程中，

7、完成附加在所使用的產(chǎn)生式上的語義規(guī)則所描述的動作。用的產(chǎn)生式上的語義規(guī)則所描述的動作。屬性文法屬性文法屬性文法(attribute grammar)是一個三元組： A=(G,V,F),A=(G,V,F),其中 G:是一個上下文無關(guān)文法V:有窮的屬性集,每個屬性與文法的一個終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號相關(guān)信息，如它的類型、值、代碼序列、符號表內(nèi)容等等 .屬性與變量一樣，可以進行計算和傳遞。屬性加工的過程即是語義處理的過程。F:關(guān)于屬性的屬性斷言或一組屬性的計算規(guī)則(稱為語義規(guī)則) . 斷言或語義規(guī)則與一個產(chǎn)生式相聯(lián),引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性. 12二、基

8、本規(guī)則二、基本規(guī)則1. 語義規(guī)則的形式：語義規(guī)則的形式：產(chǎn)生式產(chǎn)生式A的語義規(guī)則的形式為的語義規(guī)則的形式為b:=f(c1,c2,ck)其中其中:(1) f是一個是一個函數(shù)函數(shù); ;通常以表達式的形式出現(xiàn)通常以表達式的形式出現(xiàn) 屬性屬性b依賴于依賴于屬性屬性c1,c2,ck(2) 或者或者bA的的綜合屬性綜合屬性，且，且c1,c2,ck是是中中文法文法 符號的屬性符號的屬性; ;6.1 屬性文法屬性文法(3) 或者或者b中中某個文法符號的某個文法符號的繼承屬性繼承屬性, , 且且c1,c2,ck是是A或或中任何文法符號的屬性中任何文法符號的屬性. .b有兩種可能132.VTVN的屬性的屬性(1)

9、 VT 只有只有綜合屬性綜合屬性, ,由詞法分析器提供由詞法分析器提供. .6.1 屬性文法屬性文法(2) VN 既可有綜合屬性也可有繼承屬性既可有綜合屬性也可有繼承屬性; ; 開始符號開始符號S S的所有繼承屬性作為屬性計算的所有繼承屬性作為屬性計算 前的前的初始值初始值. .出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給定的產(chǎn)生式的屬性計算規(guī)則進行計算，它們由其它產(chǎn)生式的屬性規(guī)則計算或者由屬性計算器的參數(shù)提供。 AX1 X2 XnA的綜合屬性S(A)計算公式 S(A):=f(I(X1),I(Xn)Xj的繼承屬性T(Xj)計算公式 T(Xj):=f(I(A),. I(Xn)

10、1)非終結(jié)符既可有綜合屬性也可有繼承屬性 2)終結(jié)符只有綜合屬性,它們由詞法程序提供.153.屬性的計算屬性的計算/ /獲得獲得(1) 產(chǎn)生式產(chǎn)生式右邊右邊的的繼承繼承屬性屬性 產(chǎn)生式產(chǎn)生式左邊左邊的的綜合綜合屬性屬性(2) 產(chǎn)生式產(chǎn)生式左邊左邊的的繼承繼承屬性屬性 產(chǎn)生式產(chǎn)生式右邊右邊的的綜合綜合屬性屬性由該產(chǎn)生式提供的計由該產(chǎn)生式提供的計算規(guī)則計算獲得算規(guī)則計算獲得由其它產(chǎn)生式的屬性由其它產(chǎn)生式的屬性規(guī)則計算或由屬性計規(guī)則計算或由屬性計算器的參數(shù)提供算器的參數(shù)提供6.1 屬性文法屬性文法16例例6.1:考慮非終結(jié)符考慮非終結(jié)符，和和，其中，其中，有一個繼承屬性有一個繼承屬性 和一個綜合屬性

11、和一個綜合屬性，有綜合屬性有綜合屬性，有繼承屬有繼承屬 性性。C.d:=B.c+1A.b:=A.a+B.c產(chǎn)生式產(chǎn)生式ABC可能有規(guī)則：可能有規(guī)則：屬性屬性A.a和和B.c在其它地方計算。在其它地方計算。A.a左部繼承屬性左部繼承屬性A.b左部綜合屬性左部綜合屬性B.c右部綜合屬性右部綜合屬性C.d右部繼承屬性右部繼承屬性6.1 屬性文法屬性文法17例例6.2: 一個簡單臺式計算器的屬性文法一個簡單臺式計算器的屬性文法產(chǎn)生式語義規(guī)則LEnEE1+TETTT1*FTFF(E)FdigitPrint (E.val)E.val:= E1.val+T.valE.val:= T.valT.val:= T

12、1.val*F.valT.val:= F.valF.val:= E.valF.val:= digit.lexval6.1 屬性文法屬性文法18三、綜合屬性三、綜合屬性1. .語法樹中語法樹中, ,一個結(jié)點的一個結(jié)點的綜合屬性綜合屬性的值由其的值由其子結(jié)點的子結(jié)點的 屬性值屬性值確定確定; ;2. .通常使用通常使用自底向上自底向上的方法在每一個結(jié)點處使用語義的方法在每一個結(jié)點處使用語義 規(guī)則計算綜合屬性的值規(guī)則計算綜合屬性的值. .S屬性文法：屬性文法：僅使用綜合屬性的屬性文法僅使用綜合屬性的屬性文法.6.1 屬性文法屬性文法19例例6.3:例例6.2的表中定義的屬性文法說明了一個臺式計算器，

13、該的表中定義的屬性文法說明了一個臺式計算器，該計算器讀入一個可含數(shù)字、括號和計算器讀入一個可含數(shù)字、括號和+ +、* *運算符的算術(shù)表達式，運算符的算術(shù)表達式，并打印表達式的值，每個輸入行以并打印表達式的值，每個輸入行以n作為結(jié)束。假設(shè)表達作為結(jié)束。假設(shè)表達式為式為3*5+4，后跟一個換行符，后跟一個換行符n。程序打印數(shù)值程序打印數(shù)值1919其帶注釋的語法樹其帶注釋的語法樹6.1 屬性文法屬性文法20 L L E.val=19 E.val=19 n nE.val=15 +E.val=15 +T.val=4T.val=4T.val=15T.val=15T.val=3 T.val=3 * *F.v

14、al=5F.val=5F.val=3F.val=3digit.lexval=3digit.lexval=3digit.lexval=5digit.lexval=5digit.lexval=4digit.lexval=4F.val=4F.val=4返回返回*+的帶注釋的語法樹的帶注釋的語法樹21四、繼承屬性四、繼承屬性1. 語法樹中語法樹中, ,一個結(jié)點的一個結(jié)點的繼承屬性繼承屬性由此結(jié)點的由此結(jié)點的父結(jié)點父結(jié)點 和或兄弟結(jié)點和或兄弟結(jié)點的某些屬性確定的某些屬性確定; ; 2. 用繼承屬性來表示程序設(shè)計語言結(jié)構(gòu)中的用繼承屬性來表示程序設(shè)計語言結(jié)構(gòu)中的上下文上下文 依賴關(guān)系依賴關(guān)系很方便很方便.

15、.6.1 屬性文法屬性文法22例例6.:帶繼承屬性帶繼承屬性L.in的屬性文法的屬性文法產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(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輸入串輸入串: :real id1,id2,id3 的帶注釋的語法樹的帶注釋的語法樹D DT.type=realT.type=realL.in=realL.in=realrealrealL.in=realL.i

16、n=realL.in=realL.in=real，id2id2id3id3，id1id124基于屬性文法的處理過程基于屬性文法的處理過程: :單詞符號串單詞符號串語法分析語法分析語法分析樹語法分析樹遍歷遍歷計算計算例例: :輸入串輸入串語法樹語法樹依賴圖依賴圖語義規(guī)則的計語義規(guī)則的計算次序算次序進行語義規(guī)則計算，得到翻譯結(jié)果進行語義規(guī)則計算，得到翻譯結(jié)果6.2 基于屬性文法的處理方法基于屬性文法的處理方法25語法制導翻譯法語法制導翻譯法語義規(guī)則的計算將有下列作用：語義規(guī)則的計算將有下列作用： 產(chǎn)生代碼，在符號表中存放信息，給出錯產(chǎn)生代碼，在符號表中存放信息，給出錯誤信息或執(zhí)行其它動作。誤信息或

17、執(zhí)行其它動作。由源程序的語法結(jié)構(gòu)所驅(qū)動的處理方法。由源程序的語法結(jié)構(gòu)所驅(qū)動的處理方法。6.2 基于屬性文法的處理方法基于屬性文法的處理方法對輸入符號串的對輸入符號串的翻譯翻譯也就是根據(jù)語義規(guī)則進也就是根據(jù)語義規(guī)則進行行計算計算的結(jié)果。的結(jié)果。 6.2 基于屬性文法的處理方法基于屬性文法的處理方法依賴圖依賴圖樹遍歷樹遍歷一遍掃描一遍掃描27一、依賴圖一、依賴圖1.1.定義：定義：一個表示一棵語法樹中結(jié)點的繼承屬性和一個表示一棵語法樹中結(jié)點的繼承屬性和綜合屬性之間的綜合屬性之間的相互依賴關(guān)系的有向圖相互依賴關(guān)系的有向圖。6.2 基于屬性文法的處理方法基于屬性文法的處理方法282.2.依賴圖的構(gòu)造方

18、法依賴圖的構(gòu)造方法（1 1）構(gòu)造依賴圖以前，先為每一個）構(gòu)造依賴圖以前，先為每一個包含過程調(diào)包含過程調(diào)用用的語義規(guī)則引入一個的語義規(guī)則引入一個虛綜合屬性虛綜合屬性b b，在每，在每一個語義規(guī)則均寫成一個語義規(guī)則均寫成b=fb=f（c c1 1,c,c2 2, ,c,ck k） 的形式的形式. .（2 2）在依賴圖中為每一個）在依賴圖中為每一個屬性屬性設(shè)置一個設(shè)置一個結(jié)點結(jié)點. .（3 3）若）若屬性屬性b b依賴于屬性依賴于屬性c c，則從，則從屬性屬性c c的結(jié)點有的結(jié)點有一條一條有向邊有向邊連到連到屬性屬性b b的結(jié)點。的結(jié)點。程序程序6.2 基于屬性文法的處理方法基于屬性文法的處理方法2

19、9依賴圖的構(gòu)造方法依賴圖的構(gòu)造方法for 語法樹中每一結(jié)點語法樹中每一結(jié)點n do for 結(jié)點結(jié)點n的文法符號的每一個屬性的文法符號的每一個屬性 a do 為為a在依賴圖中建立一個結(jié)點在依賴圖中建立一個結(jié)點；for 語法樹中每一結(jié)點語法樹中每一結(jié)點n do for 結(jié)點結(jié)點n所用產(chǎn)生式對應的每一個語義規(guī)則所用產(chǎn)生式對應的每一個語義規(guī)則 b := f（C1,C2,Ck）do fori :=1 to k do 從從 Ci 結(jié)點到結(jié)點到 b 結(jié)點構(gòu)造一條有向邊結(jié)點構(gòu)造一條有向邊；返回6.2 基于屬性文法的處理方法基于屬性文法的處理方法30例例6.5: AXY A.a:=f (X.x, Y.y) X

20、.i:=g (A.a, Y.y)A.aX.iX.xY.y6.2 基于屬性文法的處理方法基于屬性文法的處理方法313.例題例題例例6.6: 將下面的產(chǎn)生式應用于語法樹中將下面的產(chǎn)生式應用于語法樹中產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則EE1+E2E.val:=E1.val+E2.valE EE E1 1 + +E E2 2 valvalval E.Val是從是從 E1.val和和E2.val綜合得出綜合得出6.2 基于屬性文法的處理方法基于屬性文法的處理方法句子句子real id1，id2，id3的的帶注釋的語法樹的依賴圖帶注釋的語法樹的依賴圖id1L,id2L,id3LrealTD4type5in6 -

21、 addtype(id.entry, L.in)7in8 addtype9in10addtype1entry2entry3entry產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 則則 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 例例6.7: 例例6.4中中語法分語法分析樹的析樹的依賴圖依賴圖33. 屬性的計算次序：屬性的計算次序：6.2 基于屬性文法的處理方法基于屬性文法的處理方

22、法 一個依賴圖的任何拓撲排序都給出一個語法樹一個依賴圖的任何拓撲排序都給出一個語法樹中結(jié)點的語義規(guī)則計算的中結(jié)點的語義規(guī)則計算的有效順序有效順序。注注: :在拓撲排序中在拓撲排序中, ,在一個結(jié)點上，語義規(guī)則在一個結(jié)點上，語義規(guī)則 b:=f(c1,c2,ck)中的屬性中的屬性c1,c2,ck 在計算在計算b以前是以前是可用的可用的。良定義的：良定義的：若一個屬性文法不存在屬性之間的循若一個屬性文法不存在屬性之間的循 環(huán)依賴關(guān)系，則稱該文法為良定義的。環(huán)依賴關(guān)系，則稱該文法為良定義的。屬性的計算次序?qū)傩缘挠嬎愦涡?一個依賴圖的任何拓撲排序都給出一個語法樹一個依賴圖的任何拓撲排序都給出一個語法樹中

23、結(jié)點的語義規(guī)則計算的有效順序中結(jié)點的語義規(guī)則計算的有效順序?qū)傩晕姆ㄕf明的翻譯是很精確的屬性文法說明的翻譯是很精確的 基礎(chǔ)文法用于建立輸入符號串的語法分析樹基礎(chǔ)文法用于建立輸入符號串的語法分析樹 根據(jù)語義規(guī)則建立依賴圖根據(jù)語義規(guī)則建立依賴圖 從依賴圖的拓撲排序中，我們可以得到計算語義從依賴圖的拓撲排序中，我們可以得到計算語義規(guī)則的順序規(guī)則的順序 輸入串輸入串語法樹語法樹依賴圖依賴圖語義規(guī)則計算次序語義規(guī)則計算次序句子句子real id1，id2，id3的帶注釋的語法樹的帶注釋的語法樹的依賴圖的依賴圖id1L,id2L,id3LrealTD4type5in67in89in101entry2entr

24、y3entrya4:=real;a5:=a4addtype (id3.entry,a5);a7:=a5;addtype (id2.entry,a7);a9:=a7addtype (id1.entry,a9);6.2 基于屬性文法的處理方法基于屬性文法的處理方法依賴圖依賴圖樹遍歷樹遍歷一遍掃描一遍掃描37二、樹遍歷的屬性計算方法二、樹遍歷的屬性計算方法1.1.方法方法A.前提：前提：假設(shè)語法樹已經(jīng)建立起來了，且樹中已假設(shè)語法樹已經(jīng)建立起來了，且樹中已 有如下信息：有如下信息：開始符號開始符號繼承屬性繼承屬性 終結(jié)符終結(jié)符綜合屬性綜合屬性B.遍歷：遍歷：以以某種次序遍歷語法樹某種次序遍歷語法樹，直

25、至計算出所，直至計算出所 有屬性有屬性. .遍歷方法：深度優(yōu)先，從左到右遍歷方法：深度優(yōu)先，從左到右6.2 基于屬性文法的處理方法基于屬性文法的處理方法382.算法算法While 還有未被計算的屬性還有未被計算的屬性 doVisitNode (S) / /* *S是開始符號是開始符號* */ /procedure VisitNode (N:Node);begin If N是一個非終結(jié)符是一個非終結(jié)符 then / /* *假設(shè)它的產(chǎn)生式為假設(shè)它的產(chǎn)生式為NX1Xm* */ / for i:=1 to m do if not XiVT then / /* *即即Xi是非終結(jié)符是非終結(jié)符* */

26、/ begin 計算計算Xi的所有能夠計算的繼承屬性的所有能夠計算的繼承屬性; ; VisitNode (Xi) end; 計算計算N的所有能夠計算的的所有能夠計算的綜合屬性綜合屬性end396.2 基于屬性文法的處理方法基于屬性文法的處理方法注：注：只要文法的屬性只要文法的屬性是是非循環(huán)定義的非循環(huán)定義的，則每次掃，則每次掃 描描至少至少有有一個屬性值一個屬性值被計算出來。被計算出來。40其中，其中，S有繼承屬性有繼承屬性a，綜合屬性，綜合屬性b；X有繼承屬有繼承屬性性c，綜合屬性，綜合屬性d；Y有繼承屬性有繼承屬性e，綜合屬性，綜合屬性f；Z有繼承屬性有繼承屬性h，綜合屬性，綜合屬性g。

27、3.舉例舉例例例6.9: 考慮下表所給的屬性文法考慮下表所給的屬性文法G。產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(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

28、：h=0g=1xyz(d)假設(shè)假設(shè)S.a的初始值為的初始值為0，輸入串為，輸入串為xyzS:a=0XYZxyzZ:h=0 g=1X:c=1 d=2S:a=0, b=0Y:e=0 f=0產(chǎn)產(chǎn) 生生 式式語語 義義 規(guī)規(guī) 則則 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.bXx X.d :=2*X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1 6.2 基于屬性文法的處理方法基于屬性文法的處理方法依賴圖依賴圖樹遍歷樹遍歷一遍掃描一遍掃描45三、一遍掃描的處理方法三、一遍掃描的處理方法1.1.特點特點 在在語法分析的同時語法分析的

29、同時計算屬性值計算屬性值，而不是而不是語法分語法分析構(gòu)造語法樹析構(gòu)造語法樹之后之后進行屬性的計算進行屬性的計算，而且，而且無需構(gòu)造無需構(gòu)造實際的語法樹實際的語法樹。注：注：采用該處理方法，當一個屬性值不再用于計算采用該處理方法，當一個屬性值不再用于計算 其它屬性值時，編譯程序就不必再保留這個屬性其它屬性值時，編譯程序就不必再保留這個屬性 值。如果需要，可把語義值存到文件中。值。如果需要，可把語義值存到文件中。6.2 基于屬性文法的處理方法基于屬性文法的處理方法462. 相關(guān)因素：相關(guān)因素：（1 1）所使用的語法分析方法）所使用的語法分析方法 L- -屬性文法屬性文法一遍掃描的自上而下分析一遍掃

30、描的自上而下分析 S- -屬性文法屬性文法一遍掃描的自下而上分析一遍掃描的自下而上分析6.2 基于屬性文法的處理方法基于屬性文法的處理方法（2 2）屬性的計算次序）屬性的計算次序473. 語法制導翻譯語法制導翻譯A. 在語法規(guī)則的制導下，在語法規(guī)則的制導下，通過計算語義規(guī)則，完成對輸通過計算語義規(guī)則，完成對輸 入符號串的翻譯入符號串的翻譯。6.2 基于屬性文法的處理方法基于屬性文法的處理方法 該產(chǎn)生式相應的語義規(guī)則被計算，完成有關(guān)的語義分析該產(chǎn)生式相應的語義規(guī)則被計算，完成有關(guān)的語義分析和代碼產(chǎn)生工作。和代碼產(chǎn)生工作。 由此可見，在該情況下，語法分析工作和語義規(guī)則的計由此可見，在該情況下，語法

31、分析工作和語義規(guī)則的計算是算是穿插進行穿插進行的。的。即：即：自上而下分析中，一個產(chǎn)生式匹配輸入串成功時自上而下分析中，一個產(chǎn)生式匹配輸入串成功時 語義規(guī)則語義規(guī)則 自下而上分析中，一個產(chǎn)生式被用于進行規(guī)約時自下而上分析中，一個產(chǎn)生式被用于進行規(guī)約時被計算的時機被計算的時機B. 為文法中為文法中每個產(chǎn)生式配上一組語義規(guī)則每個產(chǎn)生式配上一組語義規(guī)則，并，并在語法分析在語法分析 的同時執(zhí)行這些語義規(guī)則的同時執(zhí)行這些語義規(guī)則。48四、抽象語法樹四、抽象語法樹Abstract Syntax Tree1.定義：定義：注：注：抽象語法樹中，抽象語法樹中，操作符操作符和和關(guān)鍵字關(guān)鍵字都不作為葉結(jié)點出現(xiàn)都不作

32、為葉結(jié)點出現(xiàn), ,而是而是把它們作為內(nèi)部結(jié)點把它們作為內(nèi)部結(jié)點, ,即這些葉結(jié)點的父結(jié)點即這些葉結(jié)點的父結(jié)點. .6.2 基于屬性文法的處理方法基于屬性文法的處理方法 在語法樹中在語法樹中去掉那些對翻譯不必要的信息去掉那些對翻譯不必要的信息，從而，從而獲得更有效的源程序中間表示，這種經(jīng)變換后的語法獲得更有效的源程序中間表示，這種經(jīng)變換后的語法樹稱之為樹稱之為抽象語法樹抽象語法樹。BS1S2if_then_elseSif B then S1 else S23*5+4*54+3四、抽象語法樹四、抽象語法樹Abstract Syntax Tree6.2 基于屬性文法的處理方法基于屬性文法的處理方法5

33、02.如何建立表達式的抽象語法樹如何建立表達式的抽象語法樹（1）方法：方法：通過為每一個通過為每一個運算分量運算分量或或運算符號運算符號都都 建立一個結(jié)點來為子表達式建立子樹；建立一個結(jié)點來為子表達式建立子樹；6.2 基于屬性文法的處理方法基于屬性文法的處理方法 運算符號結(jié)點運算符號結(jié)點的的各個子結(jié)點各個子結(jié)點分別是表示該運算分別是表示該運算符號的符號的各個運算分量各個運算分量的子表達式組成的子樹的根。的子表達式組成的子樹的根。51（2）抽象語法樹中每個結(jié)點可由包含幾個域的記錄抽象語法樹中每個結(jié)點可由包含幾個域的記錄來實現(xiàn)來實現(xiàn)6.2 基于屬性文法的處理方法基于屬性文法的處理方法運算符號結(jié)點：

34、運算符號結(jié)點： 一個域一個域 運算符號運算符號 其它域其它域 指向運算符號分量的結(jié)點的指針指向運算符號分量的結(jié)點的指針結(jié)點：結(jié)點： 附加的域附加的域存放結(jié)點的屬性值存放結(jié)點的屬性值/ /指向?qū)傩灾档闹羔?。指向?qū)傩灾档闹羔槨?2（3）建立帶有二目算符的表達式的抽象語法樹結(jié)點建立帶有二目算符的表達式的抽象語法樹結(jié)點的函數(shù)：的函數(shù)： mknode (op, left, right)建立一個運算符號結(jié)點，標號是建立一個運算符號結(jié)點，標號是op，兩個域兩個域left 和和right分別指向左子樹和右子樹分別指向左子樹和右子樹。 mkleaf (id, entry)建立一個標識符結(jié)點，標號為建立一個標識符

35、結(jié)點，標號為id，一個域一個域entry指向標識符指向標識符在符號表中的入口。在符號表中的入口。 mkleaf (num, ral)建立一個數(shù)結(jié)點，標號為建立一個數(shù)結(jié)點，標號為num，一個域一個域val用于存放數(shù)的值。用于存放數(shù)的值。 每個函數(shù)均返回一個指向新建立結(jié)點的指針。每個函數(shù)均返回一個指向新建立結(jié)點的指針。6.2 基于屬性文法的處理方法基于屬性文法的處理方法53例例6.10:下面一系列函數(shù)調(diào)用建立了表達式下面一系列函數(shù)調(diào)用建立了表達式a-4+c的抽象語法樹的抽象語法樹（如圖）。在這個序列中，（如圖）。在這個序列中，p1,p2,p5是指向結(jié)點的指針，是指向結(jié)點的指針，entrya和和en

36、tryc分別是指向符號表中的標識符分別是指向符號表中的標識符a和和c的指針。的指針。 + -num 4 id to entry for c6.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) idTo entry for a 54產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則E E1+TE E1-TE TT (E)T idT numE.nptr:=mkNode(+,E1.n

37、ptr, 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)為表達式建立抽象語法樹的屬性文法為表達式建立抽象語法樹的屬性文法6.2 基于屬性文法的處理方法基于屬性文法的處理方法55E nptrTnptrE nptrET nptrnumTnptrid+id ididnum4 4帶注釋的語法分析樹帶注釋的語法分析樹To entry for aTo entry for c566.3 S屬性文法的自下而上

38、計算屬性文法的自下而上計算1. S屬性文法屬性文法 定義定義: :（1）所有非終結(jié)符所有非終結(jié)符只具有只具有綜合屬性綜合屬性； （2）在一個產(chǎn)生式中，每個符號的各個綜合屬性在一個產(chǎn)生式中，每個符號的各個綜合屬性 的定義的定義互不依賴互不依賴。2. 綜合屬性的計算綜合屬性的計算 在分析輸入符號串的同時由自下而上的分析器來計算，分在分析輸入符號串的同時由自下而上的分析器來計算，分析器可以析器可以保存保存與棧中文法符號有關(guān)的與棧中文法符號有關(guān)的綜合屬性值綜合屬性值，每當進行歸，每當進行歸約時，約時，新的屬性值新的屬性值就由棧中正在歸約的就由棧中正在歸約的產(chǎn)生式右邊符號的屬性產(chǎn)生式右邊符號的屬性值來計

39、算值來計算. .573. S-屬性文法的翻譯器通?？山柚趯傩晕姆ǖ姆g器通?？山柚贚R分析器實現(xiàn)分析器實現(xiàn) 在在S-屬性文法的基礎(chǔ)上，屬性文法的基礎(chǔ)上，LR分析器可以改造為一分析器可以改造為一個翻譯器，在對輸入串進行語法分析的同時對屬性進個翻譯器，在對輸入串進行語法分析的同時對屬性進行計算。行計算。6.3 S屬性文法的自下而上計算屬性文法的自下而上計算產(chǎn)生式 語義規(guī)則） （.）1 . 1.） . .l）1* . 1. ）F . F.）（）（） . . ）ii .:.LR分析器可以改造為一個翻譯器,增加增加語義棧語義棧 ，在對輸入串進行語法分析的同時對屬性進行計算。 分析分析器模型總控程序o

40、utputInput#S1 XmS1X1S0 #棧 狀態(tài) 符號ACTIONGOTOLR分析表產(chǎn)生式表VmV1- 語義S1S0VmV1- *的分析和計值過程步驟 動作 狀態(tài)棧 語義棧(值棧) 符號棧 余留輸入串） 3*） 2 3 *） *） *） *） *） *） *） *） * ） * ） （）（） * #） （）（） ） （）（） ）接受）接受614. 分析棧分析棧Stateval6.3 S屬性文法的自下而上計算屬性文法的自下而上計算自底向上分析法中：自底向上分析法中：棧棧存放已經(jīng)分析過的子樹的內(nèi)容存放已經(jīng)分析過的子樹的內(nèi)容 附加域附加域存放綜合屬性值存放綜合屬性值數(shù)組數(shù)組State: 元素

41、一個指向元素一個指向LR(1)LR(1)分析表的指針分析表的指針( (索引）索引）, , 指向表中某個文法符號指向表中某個文法符號. .數(shù)組數(shù)組Val: 存放語法樹中與結(jié)點對應的屬性值存放語法樹中與結(jié)點對應的屬性值. .注注: (1)假定綜合屬性剛好在每次歸約前計算假定綜合屬性剛好在每次歸約前計算. . (2)若一個符號無綜合屬性若一個符號無綜合屬性, ,則數(shù)組則數(shù)組val中相應的元素就不定義中相應的元素就不定義. .625.舉例舉例L En E E1+TE TT T1*FT FF ( E )F digit 輸入輸入stateval產(chǎn)生式產(chǎn)生式輸入串輸入串 3*5+4n3*5+4n *5+4n

42、 3 3 *5+4n F 3 *5+4n T 3 5+4n T* 3 +4n T*5 3 5 +4n T 15 +4n E 15 4n E+ 15 +4n T*F 3 5F digitT FF digitT T*FE T63L En E E1+TE TT T1*FT FF ( E )F digit 輸入串輸入串 3*5+4n輸入輸入stateval產(chǎn)生式產(chǎn)生式 4n E+ 15 n E+4 15 4 n E+F 15 4 n E+T 15 4 n E 19 En 19 L 19 F digitT FE E+TL En5.舉例舉例646.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯L-屬

43、性文法屬性文法1.1.定義定義: :若屬性文法中每個若屬性文法中每個產(chǎn)生式產(chǎn)生式AX1X2Xn, , 其相關(guān)的每個語義規(guī)則中的每個屬性其相關(guān)的每個語義規(guī)則中的每個屬性: :或者是或者是綜合屬性綜合屬性; ;或者是或者是Xj的一個繼承屬性且的一個繼承屬性且該繼承屬性該繼承屬性僅依賴于僅依賴于 Xj左邊符號左邊符號X1,X2,Xj-1的屬性和的屬性和A的繼承屬性。的繼承屬性。則稱該屬性文法為則稱該屬性文法為L-屬性文法屬性文法. .652. 特點特點: :6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯L-屬性文法屬性文法A. 該類屬性文法允許我們通過一次遍歷就計算出所該類屬性文法允許我們

44、通過一次遍歷就計算出所 有屬性值有屬性值. .B. 可在自上而下語法分析的同時實現(xiàn)可在自上而下語法分析的同時實現(xiàn)L-L-屬性文法的屬性文法的 計算計算. .C. S-屬性文法一定是屬性文法一定是L-屬性文法屬性文法. .666.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯 一個非一個非L-屬性文法屬性文法產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(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. 翻譯模式的定義：翻譯模式的定義： 一種適合語法制導翻譯的語義描述形式一種適合語法制導翻譯的語義描述形式,

45、 ,給出了給出了使用語義規(guī)則進行計算的次序使用語義規(guī)則進行計算的次序, ,可把某些實現(xiàn)細節(jié)表可把某些實現(xiàn)細節(jié)表示出來示出來. . 形式形式: :在翻譯模式中在翻譯模式中, ,和文法符號相關(guān)的屬性和語義規(guī)和文法符號相關(guān)的屬性和語義規(guī) 則則, ,用用 括起來括起來, ,插入到產(chǎn)生式右部的合適位置上插入到產(chǎn)生式右部的合適位置上. .例例: :E TR R addop T pr(addop.lex) R1| T num pr(num.val) 6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯68 為每一個語義規(guī)則建立一個包含賦值的動作為每一個語義規(guī)則建立一個包含賦值的動作, ,并并把這個動作放

46、在相應的產(chǎn)生式右邊的末尾把這個動作放在相應的產(chǎn)生式右邊的末尾. .6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯2. 翻譯模式的設(shè)計：翻譯模式的設(shè)計： A. 只有綜合屬性時只有綜合屬性時, ,可以按如下方式建立翻譯模式可以按如下方式建立翻譯模式: :69B.若若既有綜合屬性又有繼承屬性時既有綜合屬性又有繼承屬性時, ,則按如下方式建立則按如下方式建立 翻譯模式翻譯模式: : 產(chǎn)生式產(chǎn)生式右邊的符號的右邊的符號的繼承屬性繼承屬性必須在這個符號必須在這個符號以前以前的動作中計算出來的動作中計算出來. . 一個動作一個動作不能引用不能引用這個動作這個動作右邊右邊的的符號符號的的綜合屬性綜合

47、屬性. 產(chǎn)生式產(chǎn)生式左邊非終結(jié)符的綜合屬性左邊非終結(jié)符的綜合屬性只有在它所引用的只有在它所引用的所有屬性都計算出來以后才能計算所有屬性都計算出來以后才能計算.計算這種屬性的計算這種屬性的動作通?？煞旁趧幼魍ǔ？煞旁诋a(chǎn)生式右端的末尾產(chǎn)生式右端的末尾. 6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯2. 翻譯模式的設(shè)計：翻譯模式的設(shè)計： 70舉例舉例:E TR R addop Tpr(addop.lex)R1| T num pr(num.val) 輸入輸入：952深度優(yōu)先遍歷后深度優(yōu)先遍歷后輸出輸出：952ETRRR9Pr(9) T Pr() T Pr()5Pr(5)2Pr(2)71二二

48、. .自頂向下翻譯自頂向下翻譯1.討論討論: : L-屬性文法在自頂向下分析中的實現(xiàn)屬性文法在自頂向下分析中的實現(xiàn)6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯自頂向下語法分析的自頂向下語法分析的前提前提是是消除文法中的左遞歸消除文法中的左遞歸. .72EE1+T E.val:=E1.val+T.val EE1T E.val:=E1.valT.val ET E.val:=T.val T(E) T.val:=E.val Tnum T.val:=num.valET R.i := T.val R E.val:=R.s R+ T R1.i := R.i +T.val R1 R.s := R1

49、.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 Tnum T.val:=num.val 2.例題例題: : 73計算表達式計算表達式 952帶注釋語法樹帶注釋語法樹i: 繼承屬性繼承屬性s : 綜合屬性綜合屬性ET.val=9R.i=9R.i=4R.i=6Num.val=9T.val=5+T.val=2Num.val=2Num.val=56.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯E.valR.sR.sR.s74AA1Y A.a=g(A1.a ,Y.y AX A.a= f (X.x) A

50、X R.i:=f (X.x) R A.a:=R.s RY R1.i =g (R.i, Y.y) R1 R.s:=R1.s R R.s := R.i 6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯3. 轉(zhuǎn)換左遞歸翻譯模式的一般方法：轉(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.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯帶注釋語法樹帶注釋語法樹R.i=g(g(f(X.x),Y1.y),Y2.y)Y2R.i=g(

51、f(X.x),Y1.y)R.i=f(X.x)AXY1R.sR.sR.sA.aP 155-15676 遞歸下降分析器的構(gòu)造 p156 舉例 AST:Abstract Syntax Tree 三三. .遞歸下降翻譯器的設(shè)計遞歸下降翻譯器的設(shè)計6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯77 L-屬性文法的自上而下分析翻譯方法，適用于屬性文法的自上而下分析翻譯方法，適用于所有基于所有基于LL(1)文法和許多基于文法和許多基于LR(1)文法的文法的L-屬性屬性文法，是文法，是S-屬性文法自下而上翻譯技術(shù)的一般化。屬性文法自下而上翻譯技術(shù)的一般化。（1）從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作）從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作（2