屬性文法和語法制導翻譯第八周

屬性文法和語法制導翻譯第八周第一頁，共二十三頁，2022年，8月28日程序語言語義的形式化描述

——形式語義學1962年美國斯坦福大學麥克阿瑟（Mcarthur）教授在國際信息加工聯(lián)合會年會上作了著名的報告——“通往計算機的數(shù)學科學”，系統(tǒng)地論述了程序設計語言語義形式化的重要性，以及和程序正確性、語言的正確實施等的關系，并提出在形式語言研究中使用抽象語法和狀態(tài)向量等基本方法——形式語義學。第二頁，共二十三頁，2022年，8月28日形式語義學分類根據(jù)形式化的側重面和所使用的數(shù)學工具的不同，形式語義學可分成：操作語義學——著重模擬數(shù)據(jù)加工過程中計算機系統(tǒng)的操作。指稱語義學——主要描述數(shù)據(jù)加工的結果而不是加工過程的細節(jié)。公理語義學——用公理化的方法描述程序對數(shù)據(jù)的加工。代數(shù)語義學——把程序設計語言看作是刻劃數(shù)據(jù)和加工數(shù)據(jù)的一種抽象數(shù)據(jù)類型，使用研究抽象數(shù)據(jù)類型的代數(shù)方法，來描述程序設計語言的形式語義。第三頁，共二十三頁，2022年，8月28日語義分析方法丹麥的科學家曾經運用指稱語義學理論成功地實現(xiàn)了Ada語言的編譯系統(tǒng)。形式語義學方法缺點：符號系統(tǒng)比較復雜，其描述文本不易讀，不能借助這些形式系統(tǒng)自動完成語義處理任務。目前實際應用中比較流行的語義描述和語義處理方法是屬性文法和語法制導翻譯的方法第四頁，共二十三頁，2022年，8月28日內容線索屬性文法基于屬性文法的處理方法語法制導翻譯第五頁，共二十三頁，2022年，8月28日屬性文法Knuth在1968年提出在上下文無關文法的基礎上，在描述語義動作時，為每個文法符號（終結符和非終結符）配備若干相關的“值”，如“類型”，“地址”等，稱為屬性。對文法的每個產生式配備一組屬性計算規(guī)則稱為語義規(guī)則，它的描述形式為b:=f(c1,c2,…ck)，其中b,c1,c2…ck為文法符號的屬性，f是一個函數(shù)。每個文法符號聯(lián)系于一組屬性，且對每個產生式都給出其語義規(guī)則的文法稱為屬性文法。第六頁，共二十三頁，2022年，8月28日屬性和語義規(guī)則屬性代表與文法符號相關信息，如類型、值、代碼序列、符號表內容等；屬性可以進行計算和傳遞；在一個屬性文法中，對應于每個產生式A→都有一組與之相關聯(lián)的語義規(guī)則，每條規(guī)則的形式為：b:=f(c1,c2,…,ck)

這里，f是一個函數(shù)（1）b是A的一個屬性，并且c1,c2,…,ck是產生式右邊文法符號的屬性，則b是A的綜合屬性；（2）b是產生式右邊某個文法符號X的一個屬性，并且c1,c2,…,ck

是A或產生式右邊任何文法符號的屬性，b是X的繼承屬性； 屬性b依賴于屬性c1,c2,…,ck。第七頁，共二十三頁，2022年，8月28日產生式

L→En E→E1+T E→T T→T1*F T→F F→(E) F→digit語義規(guī)則print(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval簡單臺式計算器的屬性文法第八頁，共二十三頁，2022年，8月28日記號表示對于某個文法符號X∈VT∪VN，用

X.type（X的類型），X.cat（X的種別），X.val（X的值或地址）等表示它的屬性。用下標（上角標）區(qū)分同一產生式中相同符號的多次出現(xiàn)。第九頁，共二十三頁，2022年，8月28日綜合屬性在語法樹中，一個結點的綜合屬性的值由其子結點的屬性值確定。使用自底向上的方法在每一個結點處使用語義規(guī)則計算綜合屬性的值僅僅使用綜合屬性的屬性文法稱S－屬性文法第十頁，共二十三頁，2022年，8月28日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產生式語義規(guī)則L→Enprint(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第十一頁，共二十三頁，2022年，8月28日繼承屬性在語法樹中，一個結點的繼承屬性由此結點的父結點和/或兄弟結點的某些屬性確定用繼承屬性來表示程序設計語言結構中的上下文依賴關系很方便第十二頁，共二十三頁，2022年，8月28日 產生式

語義規(guī)則

D→TL L.in:=T.type T→int T.type:=integer T→real T.type:=real L→L1,id L1.in:=L.in

addtype(id.entry,L.in)

L→id addtype(id.entry,L.in)帶繼承屬性L.in的屬性文法第十三頁，共二十三頁，2022年，8月28日句子realid1，id2，id3的帶注釋的語法樹id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real產生式 語義規(guī)則D→TLL.in:=T.typeT→int T.type:=integerT→realT.type:=realL→L1,idL1.in:=L.inaddtype(id.entry,L.in)L→id addtype(id.entry,L.in)第十四頁，共二十三頁，2022年，8月28日說明終結符只有綜合屬性，由詞法分析器提供非終結符既可有綜合屬性也可有繼承屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值對出現(xiàn)在產生式右邊的繼承屬性和出現(xiàn)在產生式左邊的綜合屬性都必須提供一個計算規(guī)則。屬性計算規(guī)則中只能使用相應產生式中的文法符號的屬性出現(xiàn)在產生式左邊的繼承屬性和出現(xiàn)在產生式右邊的綜合屬性不由所給的產生式的屬性計算規(guī)則進行計算，它們由其它產生式的屬性規(guī)則計算或者由屬性計算器的參數(shù)提供語義規(guī)則所描述的工作可以包括屬性計算、靜態(tài)語義檢查、符號表操作、代碼生成等等。第十五頁，共二十三頁，2022年，8月28日例.考慮非終結符A，B和C，其中，

A有一個繼承屬性a和一個綜合屬性b;B有綜合屬性c;C有繼承屬性d。產生式A→BC可能有語義規(guī)則

C.d:=B.c+1A.b:=A.a+B.c而屬性A.a和B.c在其它地方計算第十六頁，共二十三頁，2022年，8月28日內容線索屬性文法基于屬性文法的處理方法語法制導翻譯第十七頁，共二十三頁，2022年，8月28日概述由源程序的語法結構所驅動的處理辦法就是語法制導翻譯法依賴圖樹遍歷一遍掃描輸入串語法樹依賴圖語義規(guī)則計算次序基于屬性文法的處理過程第十八頁，共二十三頁，2022年，8月28日依賴圖在一棵語法樹中的結點的繼承屬性和綜合屬性之間的相互依賴關系可以由稱作依賴圖的一個有向圖來描述為每一個包含過程調用的語義規(guī)則引入一個虛綜合屬性b，這樣把每一個語義規(guī)則都寫成b:=f(c1,c2,…,ck)

的形式依賴圖中為每一個屬性設置一個結點，如果屬性b依賴于屬性c，則從屬性c的結點有一條有向邊連到屬性b的結點。第十九頁，共二十三頁，2022年，8月28日依賴圖構造算法for語法樹中每一結點ndo for結點n的文法符號的每一個屬性ado

為a在依賴圖中建立一個結點；for語法樹中每一個結點ndo for結點n所用產生式對應的每一個語義規(guī)則

b:=f(c1,c2,…,ck)do fori:=1tokdo

從ci結點到b結點構造一條有向邊；第二十頁，共二十三頁，2022年，8月28日

E→E1＋E2 E.val:=E1.val+E2.valE1+E2Evalvalval第二十一頁，共二十三頁，2022年，8月28日句子realid1，id2，id3的帶注釋的語法樹的依賴圖id1L,id2L,id3LrealTD4type5in6-addtype(id.entry,L.in)7in8addtype9in10

addtype1entry2entry3entry產生式 語義規(guī)則D→TLL.in:=T.typeT→int T.type:=integerT→realT.type: