標籤：

符號表和抽象語法樹是什麼關係？兩者在編譯器設計中是否必需？

01-04

最近讀了兩本書，差異比較大。希望大神給予一些幫助啊。

一：《兩周自製腳本語言》([日]千葉滋)【摘要 書評 試讀】

這本書作者在詞法分析後，直接在語法分析階段構建抽象語法樹ast，然後執行eval，遍歷語法樹，得到結果。沒有用到符號表管理。

二：《自己動手寫編譯器、鏈接器》(王博俊，張宇)【摘要 書評 試讀】

這本書作者在詞法分析語法分析後，創建符號表，大多數工作都是以符號表為主，書中，本菜鳥並沒有發現抽象語法樹AST。

可能是本人太菜，沒有讀出來，希望大牛給予一些講解。

謝謝大家。

我只讀過第一本書。這本書我有大力推薦出版社引進，感覺我有義務回答一些跟它相關的問題?

簡單粗暴回答題主的原始問題：

符號表和抽象語法樹是什麼關係？

它們是正交的——它們之間沒關係。

兩者在編譯器設計中是否必需？

兩者都不是必需，雖然確實在編譯器中很常見。

AST方面，如果通過語法制導翻譯（SDT）來一趟過完成語義分析和代碼生成的話，那就沒必要真的構建出AST。

符號表方面，如果編譯過程中每個「符號」能自己記住自己的屬性信息，而中間表示（AST或其它IR）能正確規範化（canonicalize）符號的使用的話，那就不需要額外的符號表。 @邵成 的回答舉的GHC的例子就是這種。

純粹娛樂一下：還有別的情況也可以不用符號表。不過其實不是不用符號表而是用更複雜的東西。

Martin Odersky在JVMLS 2015上介紹Dotty Scala Compiler的實現思路時提到了dsc不使用符號表：JVMLS 2015 - Compilers are Databases（打不開請自備工具），31:00左右開始。然而替代它的基本上是一個functional database?

================================================

題主說的第一本書是「2週間でできる! スクリプト言語の作り方」（的中文版《兩周自製腳本語言》）。

這本書描述了一種名為Stone的腳本語言，使用Java實現，運行在JVM上。書中的Stone語言經歷了多輪進化，下面把線索簡單介紹一下：

  • 第2～6章：最初Stone是一門非常簡單的腳本語言，只支持if、while、塊語句、表達式語句，表達式也只支持簡單的二元表達式、一元表達式，然後是變數與數字、字元串字面量。此時的Stone語言只有單一作用域——全局作用域；也還沒有變數聲明這麼一說——變數名直接拿來就用。
    • 這個版本主要是引導讀者把編程語言從輸入到能執行的流程簡單走一遍。採用的實現也很簡單：用正則表達式實現的詞法分析器，用parser combinator實現的語法分析器，構建出AST之後在AST上解釋執行。解釋執行時，使用HashMap&來實現環境記錄（Environment），維持變數名與變數值之間的映射關係。這個BasicEnv類就是符號表的雛形。
  • 第7章：給Stone語言添加「函數」結構的支持。第7.2小節介紹了變數的作用域概念，引入了全局作用域與函數作用域——而塊語句沒有獨立的作用域，這與JavaScript的var變數的設計類似。
    • 這個版本開始Environment的實現進化為NestedEnv類，支持作用域嵌套了。執行方式還是AST解釋器。
  • 第7.2小節：進一步支持嵌套函數定義 / 閉包。
  • 第8章：支持與Java語言交互，可以調用Java定義的方法。
  • 第9章：添加基於類的面向對象支持。第9.4小節介紹了藉助閉包來實現對象的思路，圖9.3清晰的展現了如何通過NestedEnv構成的嵌套作用域來統一實現 局部變數/參數、對象欄位、全局變數 的訪問。
  • 第10章：添加數組支持
  • 第11章：優化變數的訪問性能。
    • 到此為止環境記錄都是通過HashMap&來實現的，而從這一章開始環境記錄ArrayEnv類則通過數組方式實現，變數訪問從哈希查找變為數組下標。
    • 為了計算一個變數到底要分配到哪個嵌套層次（nest）的哪個下標（index），代碼11.3引入的Symbols類就是跟傳統編譯器對應的實現，緊接著第11.3小節就介紹了如何遞歸遍歷AST來計算變數的位置。
  • 第12章：優化對象操作的性能。這章開始對象的實現不再通過閉包方式實現，而是通過更傳統的方式，把欄位放在一個數組裡。
    • 第12.5章進一步介紹了藉助內聯緩存（inline cache）來優化欄位訪問的速度。
  • 第13章：解釋方式從AST解釋器改為生成線性中間代碼，並實現一個基於虛擬寄存器的虛擬機來解釋執行。
    • 這個版本利用了第11章引入的符號表，藉助它在生成中間代碼時計算變數要分配到哪個虛擬寄存器或者全局變數位置。
  • 第14章：給Stone語言添加靜態類型標註。
    • 第14.2小節介紹的類型檢查器也用上了符號表，配合它單獨實現的TypeEnv來實現了靜態類型檢查。
    • 第14.4小節進一步實現了簡易類型推導。
    • 第14.5小節進一步實現了從AST生成Java位元組碼。

從這條線索可以看到，Stone語言在從簡易的AST解釋器進化到位元組碼編譯器的過程中，「環境記錄」逐步進化，在優化的過程中引入了「符號表」來輔助靜態分析。

這本書獨特的代碼組織方式可能讓題主沒發現到其符號表實現的地方。這個不怪題主嗯。

我第一次讀這本書的時候，讀到第5章看到語法分析是用parser combinator實現時還覺得作者挺大膽的，敢在入門書里用這麼前衛的做法；而讀到第6章的時候看到基於Reviser思路的GluonJ的時候我忍不住噴了！寫成這樣能行嗎（掀桌

但後來多讀了幾次心情平靜下來之後，覺得其實這種做法也挺有趣的，未嘗不是一種好玩的代碼組織方式——只看局部功能的增量式實現時，這種做法可以把新功能都包裝在一起，而不必在源碼層面改動已有的代碼。

當然確定也很明顯：為了理解某段代碼，還得從頭開始把相關代碼都讀一遍才能知道這次增量修改之後的整體效果是怎樣的。

雙向傳送門：適合用於入門的書 (評論: 2週間でできる! スクリプト言語の作り方)

================================================

第二本書看來是國內的新書，這邊入手困難?咋破？

有誰能多介紹介紹第二本書不？多謝！

給自己放幾個傳送門備用：

自己動手寫編譯器

自己動手寫編譯器、鏈接器目錄結構

================================================

另一個回答下的評論里有人提到「プログラミング言語を作る」（中譯版《自製編程語言》）的Diksam語言。它的編譯器的符號表實現在書的第6-3-4小節有講，Declaration / DeclarationList是也。

diksam/compiler/fix_tree.c做的事情就是把符號對應的屬性信息填入符號表。

給這本書也放個傳送門吧：《自製編程語言》集中討論帖

謝邀。

要解答這個問題，首先我們需要弄清楚符號表（Symbol Table）和抽象語法樹（Abstract Syntax Tree，簡稱AST）是什麼。

Symbol Table，簡單的來說是用於編譯器或者解釋器的一種數據結構，通常是用HashTable實現。它所記載的信息通常是標識符（identifier）的相關信息，如類型，作用域等。那麼，它通常會在語義分析（Semantic Analysis）階段運用到，如我們在語法分析（Syntax Analysis）階段是不會處理這樣的情況的：

int a;
a = "Hello,World!";

而這種情況，我們則可以在語義分析分析階段，利用Symbol Table進行處理，識別出類型的不匹配情況。

AST，簡單的來說，是對我們程序代碼抽象語法的一種樹形表示，並且去除掉一些不需要的信息，如下面的代碼：

if (i &> 1) {
body
}

現在回到你的問題

一：符號表和抽象語法樹的關係？

這個已經在上文闡述了，它們其實沒有什麼關係，作用也不相同。

二：兩者是否在編譯器的製作中都不是必須的？

若你製作的是簡單的編譯器，其實都並非必須。如你不需要去記錄標識符的類型信息等，那麼就不需要符號表。如你語法分析結束時不需要樹形表示，你也不必構建出AST。當然對於大多數編譯器來說，語法分析階段都會創建AST。

@藍色說得沒錯，符號表和AST二者沒有什麼關係，而且都不是必須。我就補充一個例子，即使是production-level的編譯器，也可以不用符號表，ghc就是一個例子（以下摘自The Architecture of Open Source Applications (Volume 2): The Glasgow Haskell Compiler）

No Symbol Table

Compilers usually have one or more data structures known as symbol tables, which are mappings from symbols (e.g., variables) to some information about the variable, such as its type, or where in the source code it was defined.

In GHC we use symbol tables quite sparingly; mainly in the renamer and type checker. As far as possible, we use an alternative strategy: a variable is a data structure that contains all the information about itself. Indeed, a large amount of information is reachable by traversing the data structure of a variable: from a variable we can see its type, which contains type constructors, which contain their data constructors, which themselves contain types, and so on. For example, here are some data types from GHC (heavily abbreviated and simplified):

data Id = MkId Name Type
data Type = TyConApp TyCon [Type]
| ....
data TyCon = AlgTyCon Name [DataCon]
| ...
data DataCon = MkDataCon Name Type ...

An Id contains its Type. A Type might be an application of a type constructor to some arguments (e.g., Maybe Int), in which case it contains the TyCon. A TyCon can be an algebraic data type, in which case it includes a list of its data constructors. EachDataCon includes its Type, which of course mentions the TyCon. And so on. The whole structure is highly interconnected. Indeed it is cyclic; for example, a TyCon may contain a DataCon which contains a Type, which contains the very TyCon we started with.

This approach has some advantages and disadvantages:

  • Many queries that would require a lookup in a symbol table are reduced to a simple field access, which is great for efficiency and code clarity.
  • There is no need to carry around extra symbol tables, the abstract syntax tree already contains all the information.
  • The space overheads are better: all instances of the same variable share the same data structure, and there is no space needed for the table.
  • The only difficulties arise when we need to change any of the information associated with a variable. This is where a symbol table has the advantage: we would just change the entry in the symbol table. In GHC we have to traverse the abstract syntax tree and replace all the instances of the old variable with the new one; indeed the simplifier does this regularly, as it needs to update certain optimisation-related information about each variable.

It is hard to know whether it would be better or worse overall to use symbol tables, because this aspect of the design is so fundamental that it is almost impossible to change. Still, avoiding symbol tables is a natural choice in the purely functional setting, so it seems likely that this approach is a good choice for Haskell.

我剛剛寫的一個小編譯器: Xiang1993/jack-compiler · GitHub

一般的編譯器可能包含下面這些模塊:

1, 詞法分析器:

輸入: 源代碼

輸出: token

2, 語法分析器:

輸入: token

輸出: AST

在這個過程中, 可以識別出不符合語法規則的語句, 就可以報syntax錯誤, 如果有syntax錯誤, 編譯結束

3, 語義分析器:

輸入: AST

輸出: 無

在這個過程中, 根據語言的語義規則來識別語義錯誤, 要識別語義錯誤 就必須編譯AST, 因為是樹的遍歷, 假如你先遍歷到了int a 這個節點, 接著又遍歷到了一個表達式a = 4這個節點, 你需要檢查變數a有沒有聲明啊, 變數a和4的類型批不匹配呢? 這時你如果沒有保存變數a的信息, 那麼你怎麼檢查? 所以就需要符號表來保存這些信息了.

4, 代碼優化:

最簡單的就是常量摺疊優化了, 比如: a = 1 + 2 這個語句可以直接換成: a = 3了, 也就是說在編譯階段就把一些必要的運算先計算完成, 在程序運行的時候就不需要計算這些了, 就提高了程序的運行效率. 這部分是最複雜的了, 還有各種各樣各樣的優化

5, 代碼生成:

輸入: AST

輸出: 可以是虛擬機代碼, 可以是本地彙編代碼

正好你說的兩本書我都讀過。

第一本作者是實實在在的構造了語法樹，第二本作者是利用語法規則遞歸的構造語法樹，仔細研究代碼你會發現，其實和第一本書的語法樹規則一樣。只是第一本書的語法樹更加具體。

符號表和語法樹其實並沒有什麼關係，第二本書在遞歸構造抽象語法樹的同時生成了符號表。

如果是你自己寫的編譯器，我建議你還是構造符號表和具體的語法樹比較好，不至於太抽象，自己無法理解。方便後面的語義分析和代碼生成。

最好的學習方式就是把書上的代碼自己親手打一遍，組合起來。理解每一行的含義，最後很多問題都會迎刃而解。源碼面前，了無秘密。

AST的作用應該主要是用來記錄語法分析的結果，用來反映代碼的結構。但它不應該保存過多細節性的東西，如果細節性的東西都放到AST的結點屬性中，會造成AST臃腫，遍歷AST可能需要更多時間以及更多控制代碼。比如遇到一個類的token，它繼承自哪個類，有哪些子類，有哪些私有和公共屬性，有哪些成員函數，虛函數等等，這些信息不適合放到AST的結點中，完全可以放到符號表中，然後在結點保留一個指向符號表的指針，或者直接把符號表作為全局變數。另外符號表可以被當作一個大型的臨時變數，可以動態的對其進行插入，刪除修改操作，以實現具有動態性的語法特性比如嵌套作用域。

推薦閱讀：

※程序設計中，堆和棧比較重要。棧存取速度大於堆，而且編譯器可以修改棧大小，這個值可以隨意設置嗎?
※GPU編譯器開發怎麼樣，前景如何？
※Android 中的 LLVM 主要做什麼？
※C++特性問題？
※編譯器本身是如何進行測試的？

TAG:編譯原理 | 編譯器 |