編譯原理-劉善梅-第6章 屬性文法和語法制導(dǎo)翻譯5ppt課件

1、編譯原理第六章第六章 屬性文法和語法制導(dǎo)翻譯屬性文法和語法制導(dǎo)翻譯第六章第六章 屬性文法和語法制導(dǎo)翻譯屬性文法和語法制導(dǎo)翻譯n屬性文法屬性文法n基于屬性文法的處理方法基于屬性文法的處理方法nS-屬性文法的自下而上計(jì)算屬性文法的自下而上計(jì)算nL-屬性文法和自頂向下的翻譯屬性文法和自頂向下的翻譯6.1 6.1 屬性文法屬性文法n屬性文法也稱屬性翻譯文法）屬性文法也稱屬性翻譯文法）nKnuth在在1968年提出年提出 經(jīng)典巨著：經(jīng)典巨著：The Art of Computer Programming計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù)計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù)計(jì)劃出七計(jì)劃出七卷卷第一卷第一卷于于1968年出版，年出版，第

2、二卷第二卷于于1969年出版，年出版，第三卷第三卷于于1973年出版，年出版，第四卷第四卷A已于已于2019年出版。年出版。TEX6.1 6.1 屬性文法屬性文法n屬性文法也稱屬性翻譯文法）屬性文法也稱屬性翻譯文法）nKnuth在在1968年提出年提出n在上下文無關(guān)文法的基礎(chǔ)上，為每個(gè)文在上下文無關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)終結(jié)符或非終結(jié)符配備若干法符號(hào)終結(jié)符或非終結(jié)符配備若干相關(guān)的相關(guān)的“值值”（稱為屬性）。（稱為屬性）。n屬性代表與文法符號(hào)相關(guān)信息，如類型、屬性代表與文法符號(hào)相關(guān)信息，如類型、值、代碼序列、符號(hào)表內(nèi)容等值、代碼序列、符號(hào)表內(nèi)容等n屬性可以進(jìn)行計(jì)算和傳遞屬性可以進(jìn)行計(jì)算和傳

3、遞n語義規(guī)則：對(duì)于文法的每個(gè)產(chǎn)生式都配語義規(guī)則：對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則備了一組屬性的計(jì)算規(guī)則 產(chǎn)產(chǎn) 生生 式式 LEn EE1+T ETTT1*FTFF (E)Fdigit語語 義義 規(guī)規(guī) 那么那么print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexvaln屬性屬性n綜合屬性：綜合屬性：“自下而上傳遞信息自下而上傳遞信息n繼承屬性：繼承屬性：“自上而下傳遞信息自上而下傳遞信息n在一個(gè)屬性文法中

4、，對(duì)應(yīng)于每個(gè)產(chǎn)生式在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為：形式為：nb:=f(c1,c2,ck)n這里，這里，f是一個(gè)函數(shù)，而且或者是一個(gè)函數(shù)，而且或者n1. b是是A的一個(gè)綜合屬性并且的一個(gè)綜合屬性并且c1,c2,ck是產(chǎn)是產(chǎn)生式右邊文法符號(hào)的屬性，或者生式右邊文法符號(hào)的屬性，或者n2. b是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且性并且c1,c2,ck 是是A或產(chǎn)生式右邊任何文法或產(chǎn)生式右邊任何文法符號(hào)的屬性。符號(hào)的屬性。n屬性屬性b依賴于屬性依賴于屬性c1,c2,ck。

5、 產(chǎn)產(chǎn) 生生 式式 LEn EE1+T ETTT1*FTFF (E)Fdigit語語 義義 規(guī)規(guī) 那么那么print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexvaln闡明闡明n終結(jié)符只有綜合屬性，由詞法分析器提終結(jié)符只有綜合屬性，由詞法分析器提供供n F digit n digit .lexvaln非終結(jié)符既可有綜合屬性也可有繼承屬非終結(jié)符既可有綜合屬性也可有繼承屬性，文法開始符號(hào)的所有繼承屬性為屬性，文法開始符號(hào)的

6、所有繼承屬性為屬性計(jì)算前的初始值。性計(jì)算前的初始值。n F digit n F.val， digit .lexval屬性文法屬性文法n闡明闡明n對(duì)出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)對(duì)出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性都必須提供一在產(chǎn)生式左邊的綜合屬性都必須提供一個(gè)計(jì)算規(guī)則。屬性計(jì)算規(guī)則中只能使用個(gè)計(jì)算規(guī)則。屬性計(jì)算規(guī)則中只能使用相應(yīng)產(chǎn)生式中的文法符號(hào)的屬性相應(yīng)產(chǎn)生式中的文法符號(hào)的屬性n F digit n F.val= digit .lexvaln出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給的產(chǎn)生產(chǎn)生式右邊的綜合屬性不由所給

7、的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算或者由屬性計(jì)它產(chǎn)生式的屬性規(guī)則計(jì)算或者由屬性計(jì)算器的參數(shù)提供算器的參數(shù)提供n語義規(guī)則所描述的工作可以包括屬性計(jì)語義規(guī)則所描述的工作可以包括屬性計(jì)算、靜態(tài)語義檢查、符號(hào)表操作、代碼算、靜態(tài)語義檢查、符號(hào)表操作、代碼生成等等。生成等等。n例，考慮非終結(jié)符例，考慮非終結(jié)符A，B和和C，其中，其中，A有一個(gè)繼承屬性有一個(gè)繼承屬性a和一個(gè)綜合屬性和一個(gè)綜合屬性b，B有綜合屬性有綜合屬性c，C有繼承屬性有繼承屬性d。產(chǎn)生式。產(chǎn)生式ABC可能有規(guī)則可能有規(guī)則n C.d:=B.c+1n A.b:=A.a+B.cn而

8、屬性而屬性A.a和和B.c在其它地方計(jì)算在其它地方計(jì)算 產(chǎn)產(chǎn) 生生 式式 LEn EE1+T ETTT1*FTFF (E)Fdigit語語 義義 規(guī)規(guī) 那么那么print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval屬性文法舉例屬性文法舉例n綜合屬性綜合屬性n在語法樹中，一個(gè)結(jié)點(diǎn)的綜合屬性的值由在語法樹中，一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)和它本身的屬性值確定。其子結(jié)點(diǎn)和它本身的屬性值確定。n使用自底向上的方法在每一

9、個(gè)結(jié)點(diǎn)處使用使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語義規(guī)則計(jì)算綜合屬性的值語義規(guī)則計(jì)算綜合屬性的值n僅僅使用綜合屬性的屬性文法稱僅僅使用綜合屬性的屬性文法稱S屬性屬性文法文法 產(chǎn)產(chǎn) 生生 式式 LEn EE1+T ETTT1*FTFF (E)Fdigit語語 義義 規(guī)規(guī) 那么那么print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexvalS屬性文法屬性文法3*5+4n的帶注釋的語法樹的帶注釋的語法樹 digit.lexv

10、al=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19nL 產(chǎn) 生 式 語 義 規(guī) 那么 LEn print(E.val) EE1+T E.val := E1.val+T.val ET E.val :=T.val TT1*F T.val :=T1.val* F.val TF T.val :=F.val F (E) F.val :=E.val Fdigit F.val :=digit.lexvaln繼承屬性繼承屬性n在語法樹中，一個(gè)結(jié)點(diǎn)的繼承屬性由此在語法樹中，一個(gè)

11、結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)和其本身的或兄弟結(jié)點(diǎn)和其本身的某些屬性確定某些屬性確定n用繼承屬性來表示程序設(shè)計(jì)語言結(jié)構(gòu)中用繼承屬性來表示程序設(shè)計(jì)語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便的上下文依賴關(guān)系很方便產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 那么那么 DTLL.in := T.type TintT.type := integer TrealT.type := real LL1, idL1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 句子句子real id1，id2，id3的帶注釋的語法的帶注釋的

12、語法樹樹 id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real產(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) 第六章第六章 屬性文法和語法制導(dǎo)翻譯屬性文法和語法制導(dǎo)翻譯n屬性文法屬性文法n基于屬性文法的處理方法基于屬性文法的處理方法nS-屬性文法的自下而上計(jì)算屬性文

13、法的自下而上計(jì)算nL-屬性文法和自頂向下的翻譯屬性文法和自頂向下的翻譯6.2 基于屬性文法的處理方法基于屬性文法的處理方法 n這種由源程序的語法結(jié)構(gòu)所驅(qū)動(dòng)的處理辦法就這種由源程序的語法結(jié)構(gòu)所驅(qū)動(dòng)的處理辦法就是語法制導(dǎo)翻譯法是語法制導(dǎo)翻譯法n語義規(guī)則的計(jì)算語義規(guī)則的計(jì)算n產(chǎn)生代碼產(chǎn)生代碼n在符號(hào)表中存放信息在符號(hào)表中存放信息n給出錯(cuò)誤信息給出錯(cuò)誤信息n執(zhí)行任何其它動(dòng)作執(zhí)行任何其它動(dòng)作n對(duì)輸入符號(hào)串的翻譯也就是根據(jù)語義規(guī)則進(jìn)行對(duì)輸入符號(hào)串的翻譯也就是根據(jù)語義規(guī)則進(jìn)行計(jì)算的結(jié)果。計(jì)算的結(jié)果。 輸入串輸入串語法樹語法樹按照語義規(guī)則計(jì)算屬性按照語義規(guī)則計(jì)算屬性基于屬性文法的處理過程通常為：基于屬性文法的

14、處理過程通常為：6.2 基于屬性文法的的處理方法基于屬性文法的的處理方法 n依賴圖依賴圖n樹遍歷樹遍歷n一遍掃描一遍掃描6.2.1 依賴圖依賴圖 n在一棵語法樹中的結(jié)點(diǎn)的繼承屬性和綜合屬性在一棵語法樹中的結(jié)點(diǎn)的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以由依賴圖有向圖之間的相互依賴關(guān)系可以由依賴圖有向圖來描述。來描述。n為每一個(gè)包含過程調(diào)用的語義規(guī)則引入一個(gè)虛為每一個(gè)包含過程調(diào)用的語義規(guī)則引入一個(gè)虛綜合屬性綜合屬性b，這樣把每一個(gè)語義規(guī)則都寫成，這樣把每一個(gè)語義規(guī)則都寫成nb:=f(c1,c2,ck)n的形式。的形式。n依賴圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn)，如果屬依賴圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn)，如果

15、屬性性b依賴于屬性依賴于屬性c，則從屬性，則從屬性c的結(jié)點(diǎn)有一條有向的結(jié)點(diǎn)有一條有向邊連到屬性邊連到屬性b的結(jié)點(diǎn)。的結(jié)點(diǎn)。對(duì)于一棵給定的語法樹，依賴圖按以下步驟構(gòu)造：對(duì)于一棵給定的語法樹，依賴圖按以下步驟構(gòu)造：for 語法樹中每一結(jié)點(diǎn)語法樹中每一結(jié)點(diǎn)n do for 結(jié)點(diǎn)結(jié)點(diǎn)n的文法符號(hào)的每一個(gè)屬性的文法符號(hào)的每一個(gè)屬性a do 為為a在依賴圖中建立一個(gè)結(jié)點(diǎn)；在依賴圖中建立一個(gè)結(jié)點(diǎn)；for語法樹中每一個(gè)結(jié)點(diǎn)語法樹中每一個(gè)結(jié)點(diǎn)n do for 結(jié)點(diǎn)結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)的每一個(gè)語義規(guī)則所用產(chǎn)生式對(duì)應(yīng)的每一個(gè)語義規(guī)則b:=f(c1,c2,ck ) dofor i:=1 to k do 從從ci結(jié)點(diǎn)到

16、結(jié)點(diǎn)到b結(jié)點(diǎn)構(gòu)造一條有向邊；結(jié)點(diǎn)構(gòu)造一條有向邊； EE1E2 E.val:=E1.val+E2.val E1+E2Evalvalval句子句子real id1，id2，id3的帶注釋的語法樹的依賴的帶注釋的語法樹的依賴圖圖id1L,id2L,id3LrealTD4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10 addtype1entry2entry3entry產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 那么那么 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1,

17、id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 良定義的屬性文法良定義的屬性文法n如果一屬性文法不存在屬性之間的循環(huán)依如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么稱該文法為良定義的賴關(guān)系，那么稱該文法為良定義的 屬性的計(jì)算次序?qū)傩缘挠?jì)算次序 n一個(gè)依賴圖的任何拓?fù)渑判蚨冀o出一個(gè)語法樹中一個(gè)依賴圖的任何拓?fù)渑判蚨冀o出一個(gè)語法樹中結(jié)點(diǎn)的語義規(guī)則計(jì)算的有效順序結(jié)點(diǎn)的語義規(guī)則計(jì)算的有效順序n屬性文法說明的翻譯是很精確的屬性文法說明的翻譯是很精確的n基礎(chǔ)文法用于建立輸入符號(hào)串的語法分析樹基礎(chǔ)文法用于建立輸入符號(hào)串

18、的語法分析樹n根據(jù)語義規(guī)則建立依賴圖根據(jù)語義規(guī)則建立依賴圖n從依賴圖的拓?fù)渑判蛑?，我們可以得到?jì)算語義從依賴圖的拓?fù)渑判蛑?，我們可以得到?jì)算語義規(guī)則的順序規(guī)則的順序 。用這個(gè)順序計(jì)算語義規(guī)則就得到輸。用這個(gè)順序計(jì)算語義規(guī)則就得到輸入串的翻譯入串的翻譯輸入串輸入串語法樹語法樹依賴圖依賴圖語義規(guī)則計(jì)算次序語義規(guī)則計(jì)算次序n拓?fù)湫颍阂粋€(gè)有向非循環(huán)圖的拓?fù)渑判蚴菆D中結(jié)拓?fù)湫颍阂粋€(gè)有向非循環(huán)圖的拓?fù)渑判蚴菆D中結(jié)點(diǎn)的任何順序點(diǎn)的任何順序m1，m2， ，mk，使得邊必，使得邊必須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)。須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)。句子句子real id1，id2，id3的帶注釋的語法樹

19、的帶注釋的語法樹的依賴圖的依賴圖id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entrya4:=real;a5:=a4addtype (id3.entry,a5);a7:=a5;addtype (id2.entry,a7);a9:=a7addtype (id1.entry,a9);6.2 基于屬性文法的的處理方法基于屬性文法的的處理方法 n依賴圖依賴圖n樹遍歷樹遍歷n一遍掃描一遍掃描6.2.2 樹遍歷的屬性計(jì)算方法樹遍歷的屬性計(jì)算方法n通過樹遍歷的方法計(jì)算屬性的值通過樹遍歷的方法計(jì)算屬性的值 n假設(shè)語法樹已建立，且樹中已帶有開始符假設(shè)語法

20、樹已建立，且樹中已帶有開始符號(hào)的繼承屬性和終結(jié)符的綜合屬性號(hào)的繼承屬性和終結(jié)符的綜合屬性 n以某種次序遍歷語法樹，直至計(jì)算出所有以某種次序遍歷語法樹，直至計(jì)算出所有屬性屬性n深度優(yōu)先，從左到右的遍歷深度優(yōu)先，從左到右的遍歷 產(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 例例 考慮屬性的文法考慮屬性的文法G。其中，。其中，S有繼承屬性有繼承屬性a，綜，綜合屬性合屬性b；X有繼承屬性有繼承屬性c、綜合屬性、綜合屬

21、性d；Y有繼承屬有繼承屬性性e、綜合屬性、綜合屬性f；Z有繼承屬性有繼承屬性h、綜合屬性、綜合屬性g 假設(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 基于屬性文法的的處理方法基于屬性文法的的處理方法 n依賴圖依賴圖n樹遍歷樹遍歷n一遍掃描一遍掃描6

22、.2.3 一遍掃描的處理方法一遍掃描的處理方法 n一遍掃描的處理方法是在語法分析的同時(shí)計(jì)算一遍掃描的處理方法是在語法分析的同時(shí)計(jì)算屬性值屬性值 n一遍掃描的處理方法與語法分析器相互作用，一遍掃描的處理方法與語法分析器相互作用，它與以下兩個(gè)因素密切相關(guān)：它與以下兩個(gè)因素密切相關(guān)：n所采用的語法分析方法所采用的語法分析方法n屬性的計(jì)算次序?qū)傩缘挠?jì)算次序nL屬性文法適合于一遍掃描的自上而下分析屬性文法適合于一遍掃描的自上而下分析nS屬性文法適合于一遍掃描的自下而上分析屬性文法適合于一遍掃描的自下而上分析 按照一遍掃描的編譯程序模型理解語法制導(dǎo)按照一遍掃描的編譯程序模型理解語法制導(dǎo)翻譯法翻譯法n語法制

23、導(dǎo)翻譯法：為文法中每個(gè)產(chǎn)生式語法制導(dǎo)翻譯法：為文法中每個(gè)產(chǎn)生式配上一組語義規(guī)則，并且在語法分析的配上一組語義規(guī)則，并且在語法分析的同時(shí)執(zhí)行這些語義規(guī)則同時(shí)執(zhí)行這些語義規(guī)則 n語義規(guī)則被計(jì)算的時(shí)機(jī)語義規(guī)則被計(jì)算的時(shí)機(jī)n在自上而下語法分析中，一個(gè)產(chǎn)生式匹在自上而下語法分析中，一個(gè)產(chǎn)生式匹配輸入串成功時(shí)配輸入串成功時(shí)n在自下而上分析中，當(dāng)一個(gè)產(chǎn)生式被用在自下而上分析中，當(dāng)一個(gè)產(chǎn)生式被用于進(jìn)行歸約時(shí)于進(jìn)行歸約時(shí)一遍掃描的處理方法一遍掃描的處理方法 n一遍掃描的處理方法是在語法分析的同一遍掃描的處理方法是在語法分析的同時(shí)計(jì)算屬性值時(shí)計(jì)算屬性值 n所采用的語法分析方法所采用的語法分析方法n屬性的計(jì)算次序?qū)?/p>

24、性的計(jì)算次序nL屬性文法適合于一遍掃描的自上而下屬性文法適合于一遍掃描的自上而下分析分析nS屬性文法適合于一遍掃描的自下而上屬性文法適合于一遍掃描的自下而上分析分析 6.3 S-屬性文法的自下而上計(jì)算屬性文法的自下而上計(jì)算 nS-屬性文法：只含有綜合屬性屬性文法：只含有綜合屬性n綜合屬性可以在分析輸入符號(hào)串的同時(shí)由綜合屬性可以在分析輸入符號(hào)串的同時(shí)由自下而上的分析器來計(jì)算。自下而上的分析器來計(jì)算。n分析器可以保存與棧中文法符號(hào)有關(guān)的綜分析器可以保存與棧中文法符號(hào)有關(guān)的綜合屬性值，每當(dāng)進(jìn)行歸約時(shí)，新的屬性值合屬性值，每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號(hào)的屬就由棧中正在歸約的

25、產(chǎn)生式右邊符號(hào)的屬性值來計(jì)算。性值來計(jì)算。 n在分析棧中使用一個(gè)附加的域來存放綜合在分析棧中使用一個(gè)附加的域來存放綜合屬性值屬性值 n假設(shè)語義規(guī)則假設(shè)語義規(guī)則A.a:=f(X.x,Y.y,Z.z)是對(duì)應(yīng)是對(duì)應(yīng)于產(chǎn)生式于產(chǎn)生式AXYZ的的 6.3 S-屬性文法的自下而上計(jì)算屬性文法的自下而上計(jì)算 產(chǎn)生式產(chǎn)生式 代代 碼碼 段段 LEnLEnprint(valtop) print(valtop) EE1+TEE1+Tvalntop := valtop-valntop := valtop-2+valtop 2+valtop ETETTT1TT1* *F Fvalntop := valtop-valn

26、top := valtop-22* *valtop valtop TFTFF (E)F (E)valntop :=valtop-1valntop :=valtop-1Fdigit Fdigit 產(chǎn) 生 式 語 義 規(guī) 那么 LEn print(E.val) EE1+T E.val := E1.val+T.val ET E.val :=T.val TT1*F T.val :=T1.val* F.val TF T.val :=F.val F (E) F.val :=E.val Fdigit F.val :=digit.lexval產(chǎn)生式產(chǎn)生式 代代 碼碼 段段 (0)LEn(0)LEnprint(

27、valtop) print(valtop) (1)EE1+T(1)EE1+Tvalntop := valtop-valntop := valtop-2+valtop 2+valtop (2)ET(2)ET(3)TT1(3)TT1* *F Fvalntop := valtop-valntop := valtop-22* *valtop valtop (4)TF(4)TF(5)F (E)(5)F (E)valntop :=valtop-1valntop :=valtop-1(6)Fdigit (6)Fdigit 輸入輸入 statesym val 用到的產(chǎn)生式用到的產(chǎn)生式 3*5+4n 0 # -

28、 *5+4n 05#3 -3 *5+4n 03 #F -3 Fdigit *5+4n 02 #T -3 TF 5+4n 027#T* -3 - +4n 0275 #T*5 -3 - 5產(chǎn)生式產(chǎn)生式 代代 碼碼 段段 (0)LEn(0)LEnprint(valtop) print(valtop) (1)EE1+T(1)EE1+Tvalntop := valtop-valntop := valtop-2+valtop 2+valtop (2)ET(2)ET(3)TT1(3)TT1* *F Fvalntop := valtop-valntop := valtop-22* *valtop valtop

29、 (4)TF(4)TF(5)F (E)(5)F (E)valntop :=valtop-1valntop :=valtop-1(6)Fdigit (6)Fdigit 輸入輸入 statesym val 用到的產(chǎn)生式用到的產(chǎn)生式 +4n 0275 #T*5 -3 - 5 +4n 02710#T*F -3 - 5 Fdigit +4n 02 #T -15 TT*F +4n 01 #E -15 ET 4n 016 #E+ -15- n 0165 #E+4 -15- 4產(chǎn)生式產(chǎn)生式 代代 碼碼 段段 (0)LEn(0)LEnprint(valtop) print(valtop) (1)EE1+T(1)

30、EE1+Tvalntop := valtop-valntop := valtop-2+valtop 2+valtop (2)ET(2)ET(3)TT1(3)TT1* *F Fvalntop := valtop-valntop := valtop-22* *valtop valtop (4)TF(4)TF(5)F (E)(5)F (E)valntop :=valtop-1valntop :=valtop-1(6)Fdigit (6)Fdigit 輸入輸入 statesym val 用到的產(chǎn)生式用到的產(chǎn)生式 n 0165 #E+4 -15- 4 n 0163 #E+F -15- 4Fdigit n

31、 0169 #E+T -15- 4TF n 01#E -19EE+T #En -19- #L -19 LEn產(chǎn)生式產(chǎn)生式 代代 碼碼 段段 (0)LEn(0)LEnprint(valtop) print(valtop) (1)EE1+T(1)EE1+Tvalntop := valtop-valntop := valtop-2+valtop 2+valtop (2)ET(2)ET(3)TT1(3)TT1* *F Fvalntop := valtop-valntop := valtop-22* *valtop valtop (4)TF(4)TF(5)F (E)(5)F (E)valntop :=v

32、altop-1valntop :=valtop-1(6)Fdigit (6)Fdigit 第六章第六章 屬性文法和語法制導(dǎo)翻譯屬性文法和語法制導(dǎo)翻譯n屬性文法屬性文法n基于屬性文法的處理方法基于屬性文法的處理方法nS-屬性文法的自下而上計(jì)算屬性文法的自下而上計(jì)算nL-屬性文法和自頂向下的翻譯屬性文法和自頂向下的翻譯一遍掃描的處理方法一遍掃描的處理方法 n一遍掃描的處理方法是在語法分析的同一遍掃描的處理方法是在語法分析的同時(shí)計(jì)算屬性值時(shí)計(jì)算屬性值 n所采用的語法分析方法所采用的語法分析方法n屬性的計(jì)算次序?qū)傩缘挠?jì)算次序nS屬性文法適合于一遍掃描的自下而上屬性文法適合于一遍掃描的自下而上分析分析

33、n L屬性文法適合于一遍掃描的自上而屬性文法適合于一遍掃描的自上而下分析下分析6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯 n通過深度優(yōu)先的方法對(duì)語法樹進(jìn)行遍歷，通過深度優(yōu)先的方法對(duì)語法樹進(jìn)行遍歷，從而計(jì)算屬性文法的所有屬性值。從而計(jì)算屬性文法的所有屬性值。nL-屬性文法允許一次遍歷就計(jì)算出所有屬屬性文法允許一次遍歷就計(jì)算出所有屬性值性值nLL(1)：自上而下分析方法，深度優(yōu)先建立：自上而下分析方法，深度優(yōu)先建立語法樹語法樹n我們可以在自上而下語法分析的同時(shí)實(shí)現(xiàn)我們可以在自上而下語法分析的同時(shí)實(shí)現(xiàn)L屬性文法的計(jì)算屬性文法的計(jì)算n一個(gè)屬性文法稱為一個(gè)屬性文法稱為L-屬性文法，如果對(duì)于

34、屬性文法，如果對(duì)于每個(gè)產(chǎn)生式每個(gè)產(chǎn)生式AX1X2Xn，其每個(gè)語義規(guī)，其每個(gè)語義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是則中的每個(gè)屬性或者是綜合屬性，或者是Xj(1jn)的一個(gè)繼承屬性且這個(gè)繼承屬性的一個(gè)繼承屬性且這個(gè)繼承屬性僅依賴于：僅依賴于：n(1) 產(chǎn)生式產(chǎn)生式Xj的左邊符號(hào)的左邊符號(hào)X1，X2，Xj-1的屬性；的屬性；n(2) A的繼承屬性。的繼承屬性。nS-屬性文法一定是屬性文法一定是L-屬性文法屬性文法 L-屬性文法屬性文法非非L-屬性文法例子屬性文法例子產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 那么那么 ALM L.i := l(A.i) M.i :=m(L.s) AQR R.i := r

35、(A.i) Q.i :=q(R.s) A.s :=f(Q.s) 6.4.1 翻譯模式翻譯模式 n語義規(guī)則：給出了屬性計(jì)算的定義，沒有屬性計(jì)語義規(guī)則：給出了屬性計(jì)算的定義，沒有屬性計(jì)算的次序等實(shí)現(xiàn)細(xì)節(jié)算的次序等實(shí)現(xiàn)細(xì)節(jié)n翻譯模式：給出了使用語義規(guī)則進(jìn)行計(jì)算的次序，翻譯模式：給出了使用語義規(guī)則進(jìn)行計(jì)算的次序，這樣就可把某些實(shí)現(xiàn)細(xì)節(jié)表示出來這樣就可把某些實(shí)現(xiàn)細(xì)節(jié)表示出來n在翻譯模式中，和文法符號(hào)相關(guān)的屬性和語義規(guī)在翻譯模式中，和文法符號(hào)相關(guān)的屬性和語義規(guī)則這里我們也稱語義動(dòng)作），用花括號(hào)則這里我們也稱語義動(dòng)作），用花括號(hào) 括起括起來，插入到產(chǎn)生式右部的合適位置上來，插入到產(chǎn)生式右部的合適位置上產(chǎn)生式

36、產(chǎn)生式 語義規(guī)則語義規(guī)則 ETR Raddop T R1 | print(addop.lexeme) Tnum print(num.val) ETR Raddop T print(addop.lexeme) R1 | Tnum print(num.val)q翻譯模式示例：它把帶加號(hào)和減號(hào)的中翻譯模式示例：它把帶加號(hào)和減號(hào)的中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式 ETR Raddop T print(addop.lexeme) R1 | Tnum print(num.val) 例：例：9-5+2-ETR9print(9)TR5print(5)print(-)+T2prin

37、t(2)Rprint(+) 設(shè)計(jì)翻譯模式的原則設(shè)計(jì)翻譯模式的原則n設(shè)計(jì)翻譯模式時(shí)，必須保證當(dāng)某個(gè)動(dòng)作引設(shè)計(jì)翻譯模式時(shí)，必須保證當(dāng)某個(gè)動(dòng)作引用一個(gè)屬性時(shí)它必須是有定義的。用一個(gè)屬性時(shí)它必須是有定義的。nL-屬性文法本身就能確保每個(gè)動(dòng)作不會(huì)引屬性文法本身就能確保每個(gè)動(dòng)作不會(huì)引用尚未計(jì)算出來的屬性。用尚未計(jì)算出來的屬性。 n如何將屬性文法改造成翻譯模式？如何將屬性文法改造成翻譯模式？n將屬性文法改造成翻譯模式實(shí)際上是把語將屬性文法改造成翻譯模式實(shí)際上是把語義規(guī)則用括起來，放在正確的位置義規(guī)則用括起來，放在正確的位置建立翻譯模式建立翻譯模式n當(dāng)只需要綜合屬性時(shí)：為每一個(gè)語義規(guī)則當(dāng)只需要綜合屬性時(shí)：為每

38、一個(gè)語義規(guī)則建立一個(gè)包含賦值的動(dòng)作，并把這個(gè)動(dòng)作建立一個(gè)包含賦值的動(dòng)作，并把這個(gè)動(dòng)作放在相應(yīng)的產(chǎn)生式右邊的末尾放在相應(yīng)的產(chǎn)生式右邊的末尾n 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則n TT1*FT.val:=T1.valF.valn建立產(chǎn)生式和語義動(dòng)作：建立產(chǎn)生式和語義動(dòng)作：n TT1*F T.val:=T1.valF.val建立翻譯模式建立翻譯模式n如果既有綜合屬性又有繼承屬性，在建立翻譯模如果既有綜合屬性又有繼承屬性，在建立翻譯模式時(shí)就必須保證：式時(shí)就必須保證：n1. 產(chǎn)生式右邊的符號(hào)的繼承屬性必須在這個(gè)符號(hào)產(chǎn)生式右邊的符號(hào)的繼承屬性必須在這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來。以前的動(dòng)作中計(jì)算出來。n2.

39、一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號(hào)的綜合一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號(hào)的綜合屬性。屬性。n3. 產(chǎn)生式左邊非終結(jié)符的綜合屬性只有在它所引產(chǎn)生式左邊非終結(jié)符的綜合屬性只有在它所引用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通?？煞旁诋a(chǎn)生式右端的末尾。種屬性的動(dòng)作通?？煞旁诋a(chǎn)生式右端的末尾。n SA1A2A1.in:=1; A2.in:=2n Aa print(A.in)建立翻譯模式建立翻譯模式nSA1A2A1.in:=1; A2.in:=2n Aa print(A.in)n不滿足第不滿足第1條：產(chǎn)生式右邊的符號(hào)的繼承屬性必條：產(chǎn)生式右邊的符

40、號(hào)的繼承屬性必須在這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來須在這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來n修改如下：修改如下：n S A1.in:=1; A1 A2.in:=2 A2n Aa print(A.in)排版軟件排版軟件TeXTeX、LaTeXLaTeXaacbb242 基于數(shù)學(xué)格式語言基于數(shù)學(xué)格式語言EQN n給定輸入給定輸入n E sub n .valnEQN語言把語言把E, n 和和.val分別按不同的大分別按不同的大小放在相關(guān)的位置上小放在相關(guān)的位置上En.val識(shí)別輸入并進(jìn)行格式安放的識(shí)別輸入并進(jìn)行格式安放的L-屬性文法屬性文法 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 SB SB B.ps :=10B.ps

41、 :=10 S.ht :=B.htS.ht :=B.htBB1B2BB1B2 B1.ps :=B.psB1.ps :=B.ps B2.ps :=B.psB2.ps :=B.ps B.ht := max(B1.ht, B.ht := max(B1.ht, B2.ht)B2.ht)BB1 sub B2BB1 sub B2B1.ps :=B.psB1.ps :=B.ps B2.ps :=shrink(B.ps)B2.ps :=shrink(B.ps) B.ht :=disp(B1.ht, B.ht :=disp(B1.ht, B2.ht)B2.ht)Btext Btext B.ht :=text.h

42、B.ht :=text.hB.psB.psEn.valE sub n .val翻譯模式翻譯模式S B.ps:=10 B S.ht:=B.ht B B1.ps:=B.ps B1 B2.ps:=B.ps B2 B.ht:=max(B1.ht,B2.ht) B B1.ps:=B.ps B1 sub B2.ps:=shrink(B.ps) B2 B.ht:=disp(B1.ht,B2.ht) B textB.ht:=text.hB.ps1. 產(chǎn)生式右邊的符號(hào)的繼承屬性必須在這個(gè)符產(chǎn)生式右邊的符號(hào)的繼承屬性必須在這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來。號(hào)以前的動(dòng)作中計(jì)算出來。2. 一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符

43、號(hào)的綜一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號(hào)的綜合屬性。合屬性。3. 產(chǎn)生式左邊非終結(jié)符的綜合屬性只有在它所產(chǎn)生式左邊非終結(jié)符的綜合屬性只有在它所引用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)引用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通常放在產(chǎn)生式右端的末尾。算這種屬性的動(dòng)作通常放在產(chǎn)生式右端的末尾。n剛剛講的翻譯模式中有很多時(shí)候把語義規(guī)剛剛講的翻譯模式中有很多時(shí)候把語義規(guī)則放在產(chǎn)生式的中間，我們能不能建立一則放在產(chǎn)生式的中間，我們能不能建立一種翻譯模式，把所有的語義動(dòng)作都放在產(chǎn)種翻譯模式，把所有的語義動(dòng)作都放在產(chǎn)生式的末尾呢？生式的末尾呢？建立翻譯模式建立翻譯模式E T RR + T p

44、rint(+) R | - T print(-) R | T numprint(num.val)第六章第六章 屬性文法和語法制導(dǎo)翻譯屬性文法和語法制導(dǎo)翻譯n屬性文法屬性文法n基于屬性文法的處理方法基于屬性文法的處理方法nS-屬性文法的自下而上計(jì)算屬性文法的自下而上計(jì)算nL-屬性文法和自頂向下的翻譯屬性文法和自頂向下的翻譯6.4.2 自頂向下翻譯自頂向下翻譯 n為了構(gòu)造不帶回溯的自頂向下語法分析，為了構(gòu)造不帶回溯的自頂向下語法分析，必須消除文法中的左遞歸必須消除文法中的左遞歸n當(dāng)消除一個(gè)翻譯模式的基本文法的左遞歸當(dāng)消除一個(gè)翻譯模式的基本文法的左遞歸時(shí)同時(shí)考慮屬性時(shí)同時(shí)考慮屬性適合帶綜合屬性的翻適

45、合帶綜合屬性的翻譯模式譯模式 n動(dòng)作是在處于相同位置上的符號(hào)被展開動(dòng)作是在處于相同位置上的符號(hào)被展開匹配成功時(shí)執(zhí)行的。匹配成功時(shí)執(zhí)行的。 自頂向下翻譯自頂向下翻譯n關(guān)于算術(shù)表達(dá)式的左遞歸文法相應(yīng)的翻譯關(guān)于算術(shù)表達(dá)式的左遞歸文法相應(yīng)的翻譯模式模式nEE1+T E.val:=E1.val+T.valnEE1-T E.val:=E1.val-T.valnET E.val:=T.valnT(E)T.val:=E.valnTnum T.val:=num.valE T RR + T R1R - T R1R T ( E )T numn消除左遞歸，構(gòu)造新的翻譯模式消除左遞歸，構(gòu)造新的翻譯模式 n E T R.

46、i:=T.valn RE.val:=R.snR +n TR1.i:=R.i+T.valn R1R.s:=R1.snR -n TR1.i:=R.i-T.valn R1R.s:=R1.snR R.s:=R.inT ( E ) T.val:=E.valnT num T.val:=num.valE T RR +TR1R -TR1R T ( E )T numR.i: R前面子表達(dá)式前面子表達(dá)式 的值的值R.s: 分析完分析完R時(shí)子表時(shí)子表 達(dá)式的值達(dá)式的值計(jì)算表達(dá)式計(jì)算表達(dá)式952 ETRnumnum.val=9T.val=9R.i=9-TRnumnum.val=5T.val=5R.i=4+TRnumn

47、um.val=2T.val=2R.i=6 R.s=6R.s=6R.s=6E.val=6E 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 一般方法一般方法n假設(shè)有翻譯模式：假設(shè)有翻譯模式：n AA1Y A.a:=g(A1.a,Y.y) n AXA.a:=f(X.x)n它的每個(gè)文法符號(hào)都有一個(gè)綜合屬性，用小它的每個(gè)文法符號(hào)都有一個(gè)綜合屬性，用小寫

48、字母表示，寫字母表示，g和和f是任意函數(shù)。是任意函數(shù)。q消除左遞歸：消除左遞歸：q AXRq RYR | q翻譯模式變?yōu)榉g模式變?yōu)?：qA XR.i:=f (X.x)q R A.a:=R.sqR Y R1.i:=g(R.i,Y.y) R1R.s:=R1.sqR R.s:=R.iR.i: R前面子表達(dá)式前面子表達(dá)式 的值的值R.s: 分析完分析完R時(shí)子表時(shí)子表 達(dá)式的值達(dá)式的值XA A.a=f(X.x)Y1A A.a=g(f(X.x),Y1.y)Y2A A.a=g(g(f(X.x),Y1.y), Y2.y) AA1YA.a:=g(A1.a,Y.y)AXA.a:=f(X.x)句型句型XYY的翻譯

49、過的翻譯過程程依據(jù)沒消除左依據(jù)沒消除左遞歸的翻譯模式自底遞歸的翻譯模式自底向上翻譯向上翻譯句型句型XYY的翻譯過程的翻譯過程依依據(jù)消除左遞歸的翻譯模式自據(jù)消除左遞歸的翻譯模式自頂向下翻譯頂向下翻譯 AXR R.i=f(X.x)Y1R R.i= g(f(X.x),Y1.y)Y2R R.i= g(g(f(X.x),Y1.y), Y2.y) R.s= g(g(f(X.x),Y1.y), Y2.y) R.s= g(g(f(X.x),Y1.y), Y2.y)R.s= g(g(f(X.x),Y1.y), Y2.y)A.a= g(g(f(X.x),Y1.y), Y2.y)A X R.i:=f (X.x) R

50、 A.a:=R.sR Y R1.i:=g(R.i,Y.y) R1 R.s:=R1.sR R.s:=R.i作業(yè)作業(yè)nP203 -3，76.4.3 遞歸下降翻譯器的設(shè)計(jì)遞歸下降翻譯器的設(shè)計(jì) n介紹如何在遞歸下降分析中實(shí)現(xiàn)翻譯模式，介紹如何在遞歸下降分析中實(shí)現(xiàn)翻譯模式，構(gòu)造遞歸下降翻譯器構(gòu)造遞歸下降翻譯器 n（這部分內(nèi)容自學(xué)）（這部分內(nèi)容自學(xué)）設(shè)計(jì)遞歸下降翻譯器的方法設(shè)計(jì)遞歸下降翻譯器的方法n 1. n對(duì)每個(gè)非終結(jié)符對(duì)每個(gè)非終結(jié)符A構(gòu)造一個(gè)函數(shù)過程，對(duì)構(gòu)造一個(gè)函數(shù)過程，對(duì)A的每個(gè)繼的每個(gè)繼承屬性設(shè)置一個(gè)形式參數(shù)承屬性設(shè)置一個(gè)形式參數(shù)n函數(shù)的返回值為函數(shù)的返回值為A的綜合屬性作為記錄，或指向記的綜合屬性作為記錄，或指向記錄的一個(gè)指針，記錄中有若干域，每個(gè)屬性對(duì)應(yīng)一個(gè)錄的一個(gè)指針，記錄中有若干域，每個(gè)屬性對(duì)應(yīng)一個(gè)域）。為了簡單，我們假設(shè)每個(gè)非終結(jié)只有一個(gè)綜合域）。為了簡單，我們假設(shè)每個(gè)非終結(jié)只