如何構建抽象語法樹

Question

我的AST是什麼一般的想法，但我想知道如何構建一個。

如果給出了語法和分析樹，那麼如何構建AST？

你怎麼做，如果你給一個語法和表達？

Answer 1

嗯，首先，語法是用於從表達構建解析樹。所以如果你已經有一個分析樹，你不需要語法。

根據解析器的工作量，通過解析表達式生成的結果樹可能已經是抽象語法樹。或者它可能是一個簡單的解析樹，需要第二遍來構建ast。

要從語法和表達式構造分析樹，首先必須將語法轉換爲有效代碼。通常情況下，你將工作分成其將代表表達成標記列表中輸入流，並且解析器這需要憑證清單，並從中構建解析樹\ AST一個標記。

所以表達式1 + 2*(3+4)可能被分成標記列表如下：

1 - int 
+ - add_operator 
2 - int 
* - mul_operator 
(- lparen 
3 - int 
+ - add_operator 
4 - int 
) - rparen 

第一列是實際的文本值。第二個表示令牌類型。這些令牌被送入分析器，它是從你的語法建成並識別記號，並建立解析樹。

那麼，如何編寫詞法標記器和實際的解析器？您可以手動推出自己的產品。或者更常見的是使用像coco或antlr或lex/yacc這樣的解析器生成器。這些工具會描述您的語法並生成令牌和解析器的代碼。 （代碼生成器對於大多數流行語言都是存在的，一些不受歡迎的語言也存在。）

構建解析器的方式很大程度上取決於您使用的語言。你怎麼會寫在Haskell解析器是你將如何在，說完全不同，C

• 這裏有一個教程將告訴您如何build your own recursive descent parser。

• Coco是各種語言的解析器生成器，其中 附帶有關如何入門的文檔。

• 如果Python是你的東西，那麼pyparsing也許適合你。

Answer 2

我會從一般的角度回答這個問題，而不是試圖談論詞法分析器和解析器。

解析樹包含非終端符號，它們是上下文無關語法的一部分，並顯示產生鏈以遞歸方式或非遞歸方式獲取由終端符號組成的字符串。所以當你有解析樹時，你不需要語法 - 你可以從解析樹中派生語法。

的AST不包含任何非末端符號。它只包含符號。

例子：

E 
| 
E + T 
| | 
T M * M 
| | | 
M a b 
| 
a 

該圖是a+a*b的一個非常快速的版本。注意，抽象語法樹的解釋方式取決於樹的優先順序，你做什麼類型的遍歷（按順序，預定順序，後順序）這將是你編碼到你的搜索樹中的一個通用函數。但是，一般來說，該分析樹的AST可能如下所示：

+ 
| | 
a * 
    | | 
    a b