編譯原理-第二章 一個簡單的語法指導編譯器-2.4 語法制導翻譯
- 2020 年 3 月 7 日
- 筆記
語法制導翻譯:
- 定義:語法制導翻譯是通過向一個文法的產生式附加一些規則或程式片段而得到的
- 功能:給定詞法單元流,通過向一個文法產生式附加一些語義動 作,語法制導分析產生語法分析樹,並實現翻譯動作
- 相關概念:
- 屬性:表示與某個程式構造相關的任意的量,因為用文法符號(終結符號或非終結符號)來表示程式構造,所以可將屬性的概念從程式構造擴展到表示這些構造的文法符號上
- 綜合屬性:如果某個屬性在語法分析樹節點N上的值由N的子節點和N本身的屬性值確定,則該屬性為綜合屬性,其性質為只需對語法分析樹進行一次自底向上的遍歷,就可以計算出屬性的值
- 繼承屬性:如果某個屬性由語法分析樹中該節點本身、父節點以及兄弟節點的屬性值決定,則該屬性為繼承屬性
- 後綴表達式:
- 歸納定義:
- 歸納定義:
- 書寫規則:出現在頭產生式中的非終結符號沒有下標,而在產生式體中的非終結符號帶有不同的下標,同一個非終結符的所有出現都按照這種方式區分,並且下標不是名字的組成部分
- 屬性:表示與某個程式構造相關的任意的量,因為用文法符號(終結符號或非終結符號)來表示程式構造,所以可將屬性的概念從程式構造擴展到表示這些構造的文法符號上
- 種類:
- 語法制導定義:
- 性質:
- 每個文法符號和一個屬性集合相關聯
- 每個產生式和一組語義規則相關聯,這些規則用於計算與該產生式中符號相關聯的屬性值
- 相關概念:
- 注釋語法分析樹(注釋分析樹):各個結點標記了相應的屬性值的語法分析樹,通過增加結點屬性來獲取語義資訊
- 例:
- 將表達式翻譯為相應的後綴表示形式
- 其中屬性t與非終結符號expr和term相關聯
- 圖中每個非終結符有一個值為字元串的屬性t,它表示由該非終結符生成的表達式的後綴表示形式。語義規則中的符號 || 表示字元串的連接運算符。一個數位的後綴形式是該數位本身。
- 性質:
- 語法指導翻譯方案:
- 定義:將程式片段附加到一個文法的各個產生式上的一種表示方法,通過增加結點獲取語義資訊
- 相關概念:
- 語義動作:被嵌入到產生式體中的程式片段,用花括弧括起來
- 例1:
- 非終結符號rest代表:一個表達式中除第一個項之外的一切
- 在構造語法分析樹時,為每個語義動作構造一個額外的子結點,並使用虛線將它和該產生式頭部對應的結點相連,對應於語義動作的結點沒有子結點,因此在第一次訪問該結點時就會執行這個動作
- 例2:
- 將表達式翻譯為相應的後綴表示形式
- 通過語義動作把翻譯結果依增量方式列印出來
- 語法制導定義:
- 樹的遍歷:
- 作用:將用於描述屬性的求值過程,以及描述一個翻譯方案中的各個程式碼片段的執行過程
- 過程:一個樹的遍歷(traversal)從根結點開始,並按照某個順序訪問樹的各個結點
- 例:
參考——《編譯原理(第二版)》