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

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

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

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

是A或產(chǎn)生式右邊任何文法符號(hào)的屬性，b是X的繼承屬性； 屬性b依賴(lài)于屬性c1,c2,…,ck。第七頁(yè)，共二十三頁(yè)，2022年，8月28日產(chǎn)生式

L→En E→E1+T E→T T→T1*F T→F F→(E) F→digit語(yǔ)義規(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簡(jiǎn)單臺(tái)式計(jì)算器的屬性文法第八頁(yè)，共二十三頁(yè)，2022年，8月28日記號(hào)表示對(duì)于某個(gè)文法符號(hào)X∈VT∪VN，用

X.type（X的類(lèi)型），X.cat（X的種別），X.val（X的值或地址）等表示它的屬性。用下標(biāo)（上角標(biāo)）區(qū)分同一產(chǎn)生式中相同符號(hào)的多次出現(xiàn)。第九頁(yè)，共二十三頁(yè)，2022年，8月28日綜合屬性在語(yǔ)法樹(shù)中，一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語(yǔ)義規(guī)則計(jì)算綜合屬性的值僅僅使用綜合屬性的屬性文法稱(chēng)S－屬性文法第十頁(yè)，共二十三頁(yè)，2022年，8月28日3*5+4n的帶注釋的語(yǔ)法樹(shù)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)生式語(yǔ)義規(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第十一頁(yè)，共二十三頁(yè)，2022年，8月28日繼承屬性在語(yǔ)法樹(shù)中，一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性確定用繼承屬性來(lái)表示程序設(shè)計(jì)語(yǔ)言結(jié)構(gòu)中的上下文依賴(lài)關(guān)系很方便第十二頁(yè)，共二十三頁(yè)，2022年，8月28日 產(chǎn)生式

語(yǔ)義規(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的屬性文法第十三頁(yè)，共二十三頁(yè)，2022年，8月28日句子realid1，id2，id3的帶注釋的語(yǔ)法樹(shù)id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real產(chǎn)生式 語(yǔ)義規(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)第十四頁(yè)，共二十三頁(yè)，2022年，8月28日說(shuō)明終結(jié)符只有綜合屬性，由詞法分析器提供非終結(jié)符既可有綜合屬性也可有繼承屬性，文法開(kāi)始符號(hào)的所有繼承屬性作為屬性計(jì)算前的初始值對(duì)出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性都必須提供一個(gè)計(jì)算規(guī)則。屬性計(jì)算規(guī)則中只能使用相應(yīng)產(chǎn)生式中的文法符號(hào)的屬性出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算或者由屬性計(jì)算器的參數(shù)提供語(yǔ)義規(guī)則所描述的工作可以包括屬性計(jì)算、靜態(tài)語(yǔ)義檢查、符號(hào)表操作、代碼生成等等。第十五頁(yè)，共二十三頁(yè)，2022年，8月28日例.考慮非終結(jié)符A，B和C，其中，

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

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

的形式依賴(lài)圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn)，如果屬性b依賴(lài)于屬性c，則從屬性c的結(jié)點(diǎn)有一條有向邊連到屬性b的結(jié)點(diǎn)。第十九頁(yè)，共二十三頁(yè)，2022年，8月28日依賴(lài)圖構(gòu)造算法for語(yǔ)法樹(shù)中每一結(jié)點(diǎn)ndo for結(jié)點(diǎn)n的文法符號(hào)的每一個(gè)屬性ado

為a在依賴(lài)圖中建立一個(gè)結(jié)點(diǎn)；for語(yǔ)法樹(shù)中每一個(gè)結(jié)點(diǎn)ndo for結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)的每一個(gè)語(yǔ)義規(guī)則

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

從ci結(jié)點(diǎn)到b結(jié)點(diǎn)構(gòu)造一條有向邊；第二十頁(yè)，共二十三頁(yè)，2022年，8月28日

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

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