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

1、第六章 屬性文法和語 法制導(dǎo)翻譯程序語言語義的形式化描述形式語義學(xué)n1962年美國斯坦福大學(xué)麥克阿瑟（年美國斯坦福大學(xué)麥克阿瑟（Mcarthur）教）教授在國際信息加工聯(lián)合會(huì)年會(huì)上作了著名的報(bào)授在國際信息加工聯(lián)合會(huì)年會(huì)上作了著名的報(bào)告告“通往計(jì)算機(jī)的數(shù)學(xué)科學(xué)通往計(jì)算機(jī)的數(shù)學(xué)科學(xué)”，系統(tǒng)地論述了，系統(tǒng)地論述了程序設(shè)計(jì)語言語義形式化的重要性，以及和程序程序設(shè)計(jì)語言語義形式化的重要性，以及和程序正確性、語言的正確實(shí)施等的關(guān)系，并提出在形正確性、語言的正確實(shí)施等的關(guān)系，并提出在形式語言研究中使用抽象語法和狀態(tài)向量等基本方式語言研究中使用抽象語法和狀態(tài)向量等基本方法法形式語義學(xué)形式語義學(xué) 。形式語義學(xué)分

2、類n根據(jù)形式化的側(cè)重面和所使用的數(shù)學(xué)工具的不根據(jù)形式化的側(cè)重面和所使用的數(shù)學(xué)工具的不同，形式語義學(xué)可分成：同，形式語義學(xué)可分成：操作語義學(xué)操作語義學(xué)著重模擬數(shù)據(jù)加工過程中計(jì)算機(jī)系統(tǒng)著重模擬數(shù)據(jù)加工過程中計(jì)算機(jī)系統(tǒng)的操作。的操作。指稱語義學(xué)指稱語義學(xué)主要描述數(shù)據(jù)加工的結(jié)果而不是加工主要描述數(shù)據(jù)加工的結(jié)果而不是加工過程的細(xì)節(jié)。過程的細(xì)節(jié)。公理語義學(xué)公理語義學(xué)用公理化的方法描述程序?qū)?shù)據(jù)的加用公理化的方法描述程序?qū)?shù)據(jù)的加工。工。 代數(shù)語義學(xué)代數(shù)語義學(xué)把程序設(shè)計(jì)語言看作是刻劃數(shù)據(jù)和加把程序設(shè)計(jì)語言看作是刻劃數(shù)據(jù)和加工數(shù)據(jù)的一種抽象數(shù)據(jù)類型，使用研究抽象數(shù)據(jù)類型工數(shù)據(jù)的一種抽象數(shù)據(jù)類型，使用研究抽象數(shù)

3、據(jù)類型的代數(shù)方法，來描述程序設(shè)計(jì)語言的形式語義。的代數(shù)方法，來描述程序設(shè)計(jì)語言的形式語義。語義分析方法n丹麥的科學(xué)家曾經(jīng)運(yùn)用指稱語義學(xué)理論成功地實(shí)丹麥的科學(xué)家曾經(jīng)運(yùn)用指稱語義學(xué)理論成功地實(shí)現(xiàn)了現(xiàn)了Ada語言的編譯系統(tǒng)語言的編譯系統(tǒng) 。n形式語義學(xué)方法缺點(diǎn)：符號(hào)系統(tǒng)比較復(fù)雜，其描形式語義學(xué)方法缺點(diǎn)：符號(hào)系統(tǒng)比較復(fù)雜，其描述文本不易讀，不能借助這些形式系統(tǒng)自動(dòng)完成述文本不易讀，不能借助這些形式系統(tǒng)自動(dòng)完成語義處理任務(wù)。語義處理任務(wù)。n目前實(shí)際應(yīng)用中比較流行的語義描述和語義處理目前實(shí)際應(yīng)用中比較流行的語義描述和語義處理方法是方法是屬性文法屬性文法和和語法制導(dǎo)翻譯語法制導(dǎo)翻譯的方法的方法內(nèi)容線索n屬性

4、文法屬性文法n基于屬性文法的處理方法基于屬性文法的處理方法 n語法制導(dǎo)翻譯語法制導(dǎo)翻譯 屬性文法nKnuth在在1968年提出年提出n在上下文無關(guān)文法的基礎(chǔ)上，在描述語義動(dòng)作時(shí)，為在上下文無關(guān)文法的基礎(chǔ)上，在描述語義動(dòng)作時(shí)，為每個(gè)文法符號(hào)（終結(jié)符和非終結(jié)符）配備若干相關(guān)的每個(gè)文法符號(hào)（終結(jié)符和非終結(jié)符）配備若干相關(guān)的“值值”，如，如“類型類型”，“地址地址”等，稱為等，稱為屬性屬性。n對(duì)文法的每個(gè)產(chǎn)生式配備一組屬性計(jì)算規(guī)則稱為對(duì)文法的每個(gè)產(chǎn)生式配備一組屬性計(jì)算規(guī)則稱為語義語義規(guī)則規(guī)則，它的描述形式為，它的描述形式為b:=f(c1,c2,ck)，其中，其中b,c1,c2ck為文法符號(hào)的屬性，為文

5、法符號(hào)的屬性，f是一個(gè)函數(shù)。是一個(gè)函數(shù)。n每個(gè)文法符號(hào)聯(lián)系于一組屬性，且每個(gè)文法符號(hào)聯(lián)系于一組屬性，且對(duì)每個(gè)產(chǎn)生式都給對(duì)每個(gè)產(chǎn)生式都給出其語義規(guī)則的文法稱為出其語義規(guī)則的文法稱為屬性文法屬性文法。屬性和語義規(guī)則n屬性代表與文法符號(hào)相關(guān)信息，如類型、值、代碼序列、符號(hào)表內(nèi)容屬性代表與文法符號(hào)相關(guān)信息，如類型、值、代碼序列、符號(hào)表內(nèi)容等等；n屬性可以進(jìn)行計(jì)算和傳遞屬性可以進(jìn)行計(jì)算和傳遞；n在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A 都有都有一組一組與之相關(guān)聯(lián)的與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為：語義規(guī)則，每條規(guī)則的形式為：b:=f(c1,c2,ck)這里，這里，f是

6、一個(gè)函數(shù)是一個(gè)函數(shù) （1）b是是A的一個(gè)屬性的一個(gè)屬性，并且并且c1,c2,ck是產(chǎn)生式右邊文法符號(hào)的屬是產(chǎn)生式右邊文法符號(hào)的屬性，性，則則b是是A的的綜合屬性綜合屬性； （2）b是產(chǎn)生式右邊某個(gè)文法符號(hào)是產(chǎn)生式右邊某個(gè)文法符號(hào)X的一個(gè)屬性的一個(gè)屬性，并且并且c1,c2,ck 是是A或產(chǎn)生式右邊任何文法符號(hào)的屬性或產(chǎn)生式右邊任何文法符號(hào)的屬性， b是是X的的繼承屬性繼承屬性；屬性屬性b依賴于屬性依賴于屬性c1,c2,ck。 產(chǎn)產(chǎn) 生生 式式 LEn EE1+T ETTT1*FTFF (E)Fdigit語語 義義 規(guī)規(guī) 則則print(E.val) E.val := E1.val+T.val E

7、.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval簡(jiǎn)單臺(tái)式計(jì)算器的屬性文法記號(hào)表示n對(duì)于某個(gè)文法符號(hào)對(duì)于某個(gè)文法符號(hào)XVT VN，用，用 X . type（X的類型），的類型），X . cat（X的種的種別），別），X .val（X的值或地址）等表示它的值或地址）等表示它的的屬性屬性。n用用下標(biāo)下標(biāo)（上角標(biāo)）區(qū)分同一產(chǎn)生式中（上角標(biāo)）區(qū)分同一產(chǎn)生式中相相同符號(hào)的多次出現(xiàn)同符號(hào)的多次出現(xiàn)。綜合屬性n在語法樹中，一個(gè)結(jié)點(diǎn)的在語法樹中，一個(gè)結(jié)點(diǎn)的綜合屬性綜合屬性的值由的值由其其子結(jié)點(diǎn)子

8、結(jié)點(diǎn)的屬性值確定。的屬性值確定。n使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語義規(guī)則計(jì)算綜合屬性的值語義規(guī)則計(jì)算綜合屬性的值n僅僅使用綜合屬性的屬性文法稱僅僅使用綜合屬性的屬性文法稱S屬性文屬性文法法3*5+4n的帶注釋的語法樹的帶注釋的語法樹 digit.lexval=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)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 則則LEn print(E.val) EE1+T E.val := E1.v

9、al+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繼承屬性n在語法樹中，一個(gè)結(jié)點(diǎn)的在語法樹中，一個(gè)結(jié)點(diǎn)的繼承屬性繼承屬性由此結(jié)由此結(jié)點(diǎn)的點(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.ty

10、pe := integer TrealT.type := real LL1, idL1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in)帶繼承屬性L.in的屬性文法句子real id1，id2，id3的帶注釋的語法樹 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.i

11、n :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 說明n終結(jié)符終結(jié)符只有綜合屬性，由詞法分析器提供只有綜合屬性，由詞法分析器提供n非終結(jié)符非終結(jié)符既可有綜合屬性也可有繼承屬性，文法開始符號(hào)的所有繼承既可有綜合屬性也可有繼承屬性，文法開始符號(hào)的所有繼承屬性作為屬性計(jì)算前的初始值屬性作為屬性計(jì)算前的初始值n對(duì)出現(xiàn)在對(duì)出現(xiàn)在產(chǎn)生式右邊的繼承屬性產(chǎn)生式右邊的繼承屬性和出現(xiàn)在和出現(xiàn)在產(chǎn)生式左邊的綜合屬性產(chǎn)生式左邊的綜合屬性都必都必須提供一個(gè)計(jì)算規(guī)則。屬性計(jì)算規(guī)則中只能使用相應(yīng)產(chǎn)生式中的文法須提供一個(gè)計(jì)算規(guī)則。屬性計(jì)算規(guī)則中只能使用相

12、應(yīng)產(chǎn)生式中的文法符號(hào)的屬性符號(hào)的屬性n出現(xiàn)在出現(xiàn)在產(chǎn)生式左邊的繼承屬性產(chǎn)生式左邊的繼承屬性和出現(xiàn)在和出現(xiàn)在產(chǎn)生式右邊的綜合屬性產(chǎn)生式右邊的綜合屬性不由所不由所給的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則給的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算或者由屬性計(jì)算器的參數(shù)提供計(jì)算或者由屬性計(jì)算器的參數(shù)提供n語義規(guī)則所描述的工作可以包括屬性計(jì)算、靜態(tài)語義檢查、符號(hào)表操語義規(guī)則所描述的工作可以包括屬性計(jì)算、靜態(tài)語義檢查、符號(hào)表操作、代碼生成等等。作、代碼生成等等。例例. 考慮非終結(jié)符考慮非終結(jié)符A，B和和C，其中，其中， A有一個(gè)繼承屬性有一個(gè)繼承屬性a和一個(gè)綜合屬

13、性和一個(gè)綜合屬性b; B有綜合屬性有綜合屬性c; C有繼承屬性有繼承屬性d。 產(chǎn)生式產(chǎn)生式ABC可能可能有語義有語義規(guī)則規(guī)則 C.d:=B.c+1 A.b:=A.a+B.c而屬性而屬性A.a和和B.c在其它地方計(jì)算在其它地方計(jì)算 內(nèi)容線索屬性文法屬性文法n基于屬性文法的處理方法基于屬性文法的處理方法 n語法制導(dǎo)翻譯語法制導(dǎo)翻譯 概述n由源程序的語法結(jié)構(gòu)所驅(qū)動(dòng)的處理辦法就由源程序的語法結(jié)構(gòu)所驅(qū)動(dòng)的處理辦法就是是語法制導(dǎo)翻譯法語法制導(dǎo)翻譯法依賴圖依賴圖樹遍歷樹遍歷一遍掃描一遍掃描輸入串輸入串語法樹語法樹依賴圖依賴圖語義規(guī)則計(jì)算次序語義規(guī)則計(jì)算次序n基于屬性文法的處理過程基于屬性文法的處理過程依賴圖

14、n在一棵語法樹中的結(jié)點(diǎn)的繼承屬性和綜合屬性之間的相互在一棵語法樹中的結(jié)點(diǎn)的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以由稱作依賴關(guān)系可以由稱作依賴圖依賴圖的一個(gè)有向圖來描述的一個(gè)有向圖來描述n為每一個(gè)包含過程調(diào)用的語義規(guī)則引入一個(gè)為每一個(gè)包含過程調(diào)用的語義規(guī)則引入一個(gè)虛綜合屬性虛綜合屬性b，這樣把每一個(gè)語義規(guī)則都寫成這樣把每一個(gè)語義規(guī)則都寫成b:=f(c1,c2,ck)的形式的形式n依賴圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn)，如果屬性依賴圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn)，如果屬性b依賴于依賴于屬性屬性c，則從屬性，則從屬性c的結(jié)點(diǎn)有一條有向邊連到屬性的結(jié)點(diǎn)有一條有向邊連到屬性b的結(jié)點(diǎn)。的結(jié)點(diǎn)。依賴圖構(gòu)造算法fo

15、r 語法樹中每一結(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)到結(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