什麼是抽象語法樹/是否需要？

Question

我一直感興趣的編譯器/解釋器設計/實施，只要我一直在編程（只有5年了），它總是看起來像「魔術師」在幕後，沒有人真正談論（我知道的至少2個操作系統開發論壇，但我不知道任何社區的編譯器/解釋器/語言開發）。無論如何，最近我決定開始自己的工作，希望能夠擴展我對整體編程的知識（嘿，這很有趣:)。所以，基於我有限的閱讀材料和維基百科，我已經爲編譯器/解釋器開發了這個組件概念：

源代碼 - >詞法分析 - >抽象語法樹 - >句法分析 - >語義分析 - >代碼生成 - >可執行代碼。

（我知道有更多的代碼生成和可執行代碼，但我還沒有得到那麼遠，:)

有了這樣的認識，我創建了一個非常基本的詞法分析器（在Java中）取從源文件輸入，並將令牌輸出到另一個文件中。樣品輸入/輸出應該是這樣的：

輸入：

int a := 2 
if(a = 3) then 
    print "Yay!" 
endif 

輸出（從詞法分析器）：

INTEGER 
A 
ASSIGN 
2 
IF 
L_PAR 
A 
COMP 
3 
R_PAR 
THEN 
PRINT 
YAY! 
ENDIF 

個人而言，我認爲這將是很容易從那裏去語法/語義分析，甚至可能產生代碼，這引起了我的質疑：爲什麼使用AST，似乎我的詞法分析器的工作做得很好？然而，我用來研究這個主題的100％的資料似乎都堅信這是任何編譯器/解釋器的必要組成部分。我是否錯過了AST的真正意義（一個顯示程序邏輯流程的樹）？

TL; DR：目前在航線開發編譯器，完成了詞法分析，在我看來，像輸出將使容易句法分析/語義分析，而不是做一個AST。那爲什麼要用一個？我是否錯過了一點？

謝謝！

Answer 1

首先，有一件事對你的組件列表是沒有意義的。構建AST 是（幾乎）句法分析，所以要麼不應該在那裏，或的AST前至少來。

你有什麼有一個詞法分析器。它給你的只是個別的令牌。在任何情況下，您都需要一個實際的解析器，因爲常規語言對編程沒有任何樂趣。甚至不能（正確）嵌套表達式。哎呀，你甚至無法處理運營商的優先級。令牌流不會給你：

1. 一個想法，其中語句和表達式開始和結束。
2. 一個想法語句是如何分成塊。
3. 一個想法表達式的哪一部分具有哪些優先級，關聯性等。
4. 在程序的實際結構上的一個清晰，整齊的視圖。
5. 一種可以通過無數次轉換的結構，沒有每一次通過都知道並且代碼可以容納表示if中的條件被圓括號括起來。
6. ...更一般地說，任何類型的理解超出單個標記的水平。

假設你有你的編譯器兩個通道可以優化某些種類的運營商適用於某些參數（比如，常量摺疊和代數簡化像x - x -> 0）。如果你把他們的代幣交給x - x * 1這個表達式，這些代碼就會很混亂，因爲x * 1部分最先出現。他們有知道，以免轉換不正確（考慮1 + 2 * 3）。

這些事情足夠棘手以至於無法正常工作，所以您也不希望被解析問題所困擾。這就是爲什麼您在單獨的解析步驟中解決解析問題第一個。 然後你可以用它的定義替換一個函數調用，而不必擔心添加括號，因此意義保持不變。您可以節省時間，分離問題，避免重複，在其他許多地方啓用更簡單的代碼等。

解析器計算出所有結果，並構建AST，從而保存所有信息。沒有任何關於節點的更多數據，AST的形狀就會讓你不知道。 1，2，3，等等，免費。 沒有隨後的bazillion通行證不得不擔心它。

這並不是說你總是必須有一個AST。對於足夠簡單的語言，你可以做一個單通編譯器。在解析過程中，不是生成AST或其他中間表示，而是隨時發出代碼。然而，對於不那麼簡單的語言來說，這會變得更加困難，並且你不能合理地做很多事情（例如所有優化和診斷的70％ - 而且我只是把這個數字提高了）。一般來說，我不會建議你這樣做。單通編譯器大部分已經死亡的原因很充分。即使是允許它們的語言（例如C）現在也可以通過多次通過和AST來實現。這是一種簡單的入門方法，但會在以後嚴重限制您（以及語言，如果您設計的話）。

Answer 2

您已經在您的流程圖中的錯誤點獲得了AST。通常，詞法分析器的輸出是一系列的標記（就像您在輸出中一樣），然後將這些標記輸入到生成AST的解析器/語法分析器。因此，詞法分析器的輸出與AST不同，因爲它們在編譯過程中的不同位置使用並實現不同的目的。

下一個邏輯問題是：那麼，什麼是AST？那麼，解析/語法分析的目的就是將由詞法分析器生成的一系列標記轉換爲AST（或解析樹）。 AST是一種中間表示形式，它以一種更易於以編程方式工作的方式來捕獲語法元素之間的關係。考慮這一點的一種方式是，文本程序是一維構造，並且只能將想法表示爲一系列元素，而AST從這個約束中被釋放，並且可以表示這些元素之間在二維（如通常繪製的那樣）或任何更高維空間，如果您選擇這樣想的話。例如，二元運算符有兩個操作數，我們稱它們爲A和B.在代碼中，這可能拼寫爲'A * B'（假設中綴運算符 - AST的另一個優點是隱藏了這樣的區別，可能在語法上很重要，但語義上不重要），但是爲了讓編譯器「理解」這個表達式，它必須順序讀取5個字符，並且即使是小語言，這種邏輯也可能很快變得麻煩。然而，在AST表示中，我們有一個「二元運算符」節點，其值爲'*'，並且該節點有兩個子元素，值爲'A'和'B'。

隨着您的編譯器項目的進展，我認爲您會開始看到這種表示的優點。