属性文法和语法制导翻译
??截至到上一章，說完了語法分析的全部內容。從第一章的結構圖可以了解到，緊接著語法分析的是語義分析與中間代碼的生成。書中用了兩章講述該內容（屬性文法和語法制導翻譯、語義分析和中間代碼生成）。本節描述的主要是進行語法分析與中間代碼的生成的一些儲備知識。
??先聊聊語法分析和本章的關系：在第一章的時候，我們講述了“遍”的概念。之前只是簡單的說了可將語法分析與中間代碼生成放到一遍中完成，這章的內容就會解釋到其原因。也可分為自上而下和自下而上兩種類型。會在后續的內容里慢慢體現。
??回到本章來，希望通過看完這篇文章能夠明白以下幾個問題：
????1. 什么是屬性文法及屬性文法的構造方法
????2. 什么是語法制導翻譯及特殊類型“翻譯模式”的構造
??本章有許多概念性的東西，我先在此進行列舉作為關鍵詞：語法制導翻譯、屬性文法、綜合屬性、繼承屬性、抽象語法樹、S-屬性文法、L-屬性文法、翻譯模式。
語法制導翻譯
??通過對語法制導翻譯名字的由來的解釋可明白其與語法分析的關系了吧！我理解的語法制導翻譯就是在原來語法分析的各個節點賦予其獨特的含義，該含義就是語義。有這么一個例子說明語法和語義之間的關系：名字和標識符的區別。標識符是語法的概念、名字是語義的概念。一個標識符比如Jordan，可能是籃球運動員邁克爾喬丹的名字，也可能是國家約旦的名字。不過如果賦予其含義，比如籃球運動員，Jordan就變成了獨特意義的球星名。
屬性文法
??在上下文無關文法的基礎上，為每個文法符號（終結符和非終結符）配備若干相關的“值”（也稱屬性），對于文法的每個產生式都配備了一組屬性的計算規則（語義規則），這種文法稱為屬性文法。
??從上面的定義看到核心內容就是屬性，什么叫屬性呢？比如變量的類型（int/char…），變量的值(1,2…)等等都可算作屬性。所以屬性是各種各樣的，組合起來也是極其復雜的。屬性文法依托于上下無關文法，即文法是由產生式所定義的，各個屬性間的關系也離不開產生式。課本上為了內容直觀，只介紹了兩種屬性：綜合屬性和繼承屬性（屬性不止這兩類，但這兩種比較基礎）。
??屬性文法一般的表示方法如下（一條規則對應的語義規則可以不唯一）：
綜合屬性
??用于自下而上傳遞信息；在語法樹中，一個結點的綜合屬性由其子結點的屬性值確定，因此，通常使用自底向上的方法在每一個結點處使用語義規則計算綜合屬性的值。
繼承屬性
??用于自上而下傳遞信息；在語法樹中，一個結點的繼承屬性由此結點的父結點或兄弟結點的某些屬性確定。
綜合屬性和繼承屬性的主要區別是依賴關系不同。一般來說，綜合屬性在自底向上的語法分析過程中計算，而繼承屬性在自上而下的語法分析過程中計算。其實繼承屬性也可以在自底向上的語法分析過程計算，但應用較少。
??再形式化的說明下屬性的計算規則吧：
??從上面可以看出一個普遍規律就是：繼承屬性總是由位于產生式右邊的字符定義，而綜合屬性由左邊定義。其實這個是封裝性的要求。限制了在一個產生式范圍內只能計算產生式左邊非終結符的綜合屬性，只能計算產生式右邊非終結符的繼承屬性。后面的例題會著重體現這點！
??在屬性文法中有一些是需要特別注意的，我放張圖上來，對容易混淆的做特別解釋：
??注意最后一點中：綜合屬性由子節點決定，繼承屬性由父節點及兄弟節點決定。那在語法分析樹中，葉子節點沒有子節點，根節點也沒有兄弟或父節點。所有做了一些特殊規定：葉子結點的綜合屬性事先準備好（由詞法分析器提供，葉子節點一般都是變量值這類的），根節點不是無繼承屬性，而是根節點的繼承屬性只能預先給出。
??前面說到了語法制導翻譯，下面結合屬性文法做更為詳細的說明：
??基于屬性文法的處理過程通常是：對單詞符號串進行語法分析，構造語法分析樹，然后根據需要遍歷語法分析樹，并在語法分析樹的各結點處按語義規則進行計算。
??看完上面這段話，需要明白一個事兒，疑惑一個事兒。明白的是屬性文法的構造是根據具體的輸入字符串，建立相應的語法分析樹決定的。疑惑的是選擇什么樣的方式去遍歷語法分析樹呢？（答案是深度優先搜索）
??該圖是整個語法制導翻譯的步驟圖，我們先來解釋下依賴圖：
??依賴圖：一種有向圖，在一顆語法樹中表示結點的繼承屬性和綜合屬性之間的相互依賴關系（這種屬性之間的依賴關系由文法的語義規則確定）。
??依賴圖構造的算法如下：
??其實依賴圖很直觀，就是當前要求的那個值是哪里傳送過來的（有點類似，需要的數據都傳過來，匯總到一起進行運算）。
??依賴圖中有一類特殊情況：兩個節點相互依賴，形成循環（這其實是不利于我們進行分析的）。
??如果屬性文法不存在屬性之間循環的依賴關系，那么稱該文法為良定義。像下面這樣：
??下面舉個例子，對上面內容進行一個整合：
??第一眼看上去有點凌亂（例6.4和例6.5在一起了，我們的目標是例6.4哈），我們梳理一下啊~先分清我們有什么？要求什么？已知的是屬性文法（即產生式及語義規則的對應）和輸入的一個字符串(real id1, id2, id3)。要求的是這個字符串對應的分析樹中各節點的屬性。
??首先按照輸入的字符及產生式把語法分析樹畫出來（這就考驗前面的基礎了）。接著需要求出每個節點的屬性（或是綜合屬性，或是繼承屬性）。按照前面的判斷法則，可知T.type是綜合屬性(產生式2，3)，L.in是繼承屬性（產生式1，4 特別注意第四個產生式的兩個L進行標號區分。接著從下往上，對于最底層的葉子節點按照已知（L->id 中id entry即為已知），在使用時直接賦值即可。
??每個節點可能會有屬性，也可以有多個屬性。每個屬性都要進行計算，按照什么樣子的順序呢？這就是拓撲排序，如果a依賴b，則b排在a的前面。本質就是被依賴的屬性要先被計算出來。
??前面提到遍歷樹是通過深度優先搜索實現的，但有兩個前提條件：
??滿足前提條件，即可用下面的算法執行：
抽象語法樹
??（為什么需要抽象語法樹呢？其實抽象語法樹是一種中間代碼形式，很多編譯器為了優化都先生成抽象語法樹，然后在此基礎上進行優化）
??需要在此提前說明抽象語法樹不同于語法分析樹，經常叫其簡稱。對應關系如下：
????抽象語法樹——語法樹
????語法分析樹——分析樹
??抽象語法樹概念如下：
???表示程序層次結構的樹，它把分析樹中對語義無關緊要的成分去掉，是語法樹的抽象形式，也稱作語法結構樹，或結構樹。抽象語法樹是常用的一種中間表示形式。
??特別注意：在抽象語法樹中，運算符號和關鍵字都不在葉結點，而是在內部結點中出現。
??舉個例子：
??建立抽象語法樹主要有三個函數（利用該三個函數就可以完成整個抽象語法樹的構造）：
??用抽象語法樹來表示的屬性文法就像下面這樣（使用節點的構造表示語義規則）：
注意下：對于T->(E)這種情況，可忽略()的存在，直接賦值
S-屬性文法(simple)
??S-屬性文法是只包含綜合屬性，所以對于S屬性文法的計算是結合著自下而上進行的。實際實現時S-屬性文法是結合LR分析器完成的（再次體現了一遍的思想），不同的地方是在棧中增加了一個存放屬性的域，結構如下：
??規約時，就把產生式右邊符號出棧規約為左側符號，并把對應屬性放入域中：
??對于S-屬性文法，主要存在一種提醒，就是伴隨著LR分析，填充棧表信息。我這里放一道完整的例題了。
L-屬性文法
??L-屬性文法的定義如下：
??如果?A→X1X2…Xn?P，其每一個語義規則中的每一個屬性都是一個綜合屬性，或是Xj(1?j ? n)的一個繼承屬性，這個繼承屬性僅依賴于：
????a．產生式中Xj的左邊符號X1，X2，…Xj-1的屬性；
????b．A的繼承屬性。
??S屬性文法和L屬性文法的關系：S屬性文法是L屬性文法中的一種，即無繼承屬性參與。
??舉一個例子說明什么樣的不是L屬性文法：
??原因在于Q.i的計算使用其右側的R.s屬性，違背了定義a的要求。由定義判斷是否為L-屬性文法也是需要掌握的。
翻譯模式
??之前一直讓我很苦惱，翻譯模式到底是什么？其實翻譯模式就是語法制導翻譯中比較特殊的一種，根據翻譯模式，可以讓人更明白到了哪步需要干哪件事。翻譯模式穿插在產生式中，當下一項是翻譯模式時就執行該翻譯模式的動作。也可認為翻譯模式就是動作。（以上是我自己的一些想法，可以回過頭來再看一看）。
??形式化的概念定義如下：
??我還是舉個例子，用圖說話吧~
??在上面的翻譯模式中，會不斷執行動作，最終得到后綴式。
??那如何構造翻譯模式呢？
???有前提條件：一定要是L-屬性文法并且保證語義動作不會引用還沒有計算的屬性值（其實就是正確的文法吧~）
??分了兩種可能性：
??前面介紹到屬性文法基礎是上下無關文法，在使用翻譯模式構造自上而下的時候也會存在熟悉的兩個問題：左遞歸和提取公共左因子
??對兩種問題的處理方式與之前相同，都是通過引入非終結符將左遞歸變為右遞歸或者提取出公共因子。體現在翻譯模式上也大同小異，舉個例子，了解其構造過程即可：
??原始產生式如下：
??消除左遞歸后產生式如下：
??構造其語法分析樹并計算各屬性值：
??推廣到一般情況如下：
??如果用抽象語法樹來表示以上的翻譯模式就是這個樣子的：
??看了幾個例題，可以發現翻譯模式構造的一個小規律：綜合屬性都位于產生式末，繼承屬性位于緊鄰所求符號的前面（即先進行動作求值再引用）
遞歸下降翻譯器（作用：進行翻譯，形成中間代碼）：
??從翻譯模式里看到，部分的動作嵌入在產生式中。都放在末尾（這個問題其實是放在末尾就能非常容易的在自底向上的語法分析過程中完成屬性運算）的方法就是引入新的非終結符，并指向空字：
??模擬繼承屬性的計算（**想表達什么呢？**關鍵要看前面一節，分析棧中的繼承屬性。某些繼承屬性的計算一般是復寫規則，在自底向上分析過程中我們可以根據其在分析棧中的位置來訪問它，而不需要實際去計算。模擬繼承屬性的計算是因為下面這種列子，開始設計的屬性文法繼承屬性在需要時在分析棧中位置不固定，因此可以通過一些改造來使其固定）
??明顯可以看出，綜合屬性的計算比繼承屬性方便直觀不少。那能不能將繼承屬性向綜合屬性進行一下轉化呢？方法如下：
??那具體是怎么改變的呢？
????這個地方上課是畫了兩個語法分析樹來解釋的，第一個類型在左子樹，id在右子樹。第二個 類型和id都在一邊
??這章主要是一些基礎概念，現在學完了所有內容意識到，前后兩章聯系是很緊密的。對于基本的概念還是要掌握扎實，繼續加油吧！
感謝編譯原理課程謝老師對本文的耐心修改，因作者水平有限，如有錯誤之處，請在評論區下方指出，謝謝！
總結
以上是生活随笔為你收集整理的属性文法和语法制导翻译的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Linux系统编程：使用semaphor
- 下一篇： python从excel中读取数据