AST的樹結構

我想在C＃中編寫一個解釋器，並且我處於解析階段。我發現此時我必須生成抽象語法樹，但我不知道如何在C＃中表示它。AST的樹結構

目前我只是使用List<object>，但我有一種感覺，我做錯了。

非常感謝。

來源

2011-02-01 Oleg

那裏有一個具體問題嗎？編寫AST並不是一個小問題...... – 2011-02-01 09:26:21

查看`System.Linq.Expressions。*`，它可能會給你一個提示 – Nekresh 2011-02-01 09:28:19

正確的數據結構就是滿足你需求的數據結構。一旦你有了AST，你會用AST做什麼？你預計要做什麼樣的操作？ – 2011-02-01 15:12:12

有許多技術，從單一的「節點」類型 - 包含「類型」標籤的大量字段到特定類的細粒度層次結構。重要的是要考慮如何使遍歷代碼簡單和健壯，因爲您將需要反覆遍歷這個數據結構。

但是，退一步說，解釋並不嚴格要求AST。很多較早的解釋器會在他們遇到它時逐字讀取每行代碼，通過基於堆棧的書籍標記系統實現解析和執行它，並帶有循環等。我懷疑像bash和cmd.exe這樣的shell語言今天仍然像這樣工作。

來源

2011-02-01 09:39:43

大多數AST節點的實現非常簡單。

它們是包含節點類型（通常爲整數），子列表（列表正常;高性能實現有一組統計通用第一，第二組成員的結構（好的，好的，「類」），第三個孩子）以及一些額外的字段來攜帶特定於AST節點實例的值（例如，AST節點「整數常量」的值「5」）。爲了能夠將樹從任何節點高效導航回父節點，通常會有一個特殊的引用返回到父節點。

更難的是決定什麼你應該有一組AST節點。對於一個大的語法來說，這很不方便，因爲你必須定義一組數百個語法，並且當你嘗試正確地修改語法時會出現流失。

一個簡單的技巧就是根據語法規則簡單地定義一個AST節點。（大多數情況下這將被稱爲「具體語法樹」）。但它是無腦的，你不會錯過任何東西。

我們的DMS Software Reengineering Toolkit遵循這個「簡單的技巧」的想法，從語法規則直接生成AST節點類型。它另外優化：樹中不存在沒有值的葉AST節點，樹中不存在一元生產的節點，並且列表形成產品具有子類型的列表樣式，而其他節點類型具有兒童固定插槽類型。最終的結果是你無論如何都非常接近「抽象」語法樹。所有這些都是由DMS的解析器生成器自動構建的，因此您根本沒有想到。

DMS還有一個完整的，測試良好的C＃4.0前端。一旦你經歷了定義AST的頭痛之後，你就會想要從中分析/轉換/生成，其餘的DMS會突然變得非常有價值。

來源

2011-02-02 18:55:38

我建議你繼續使用List<object>，直到你清楚地明白這是什麼限制以及你的要求是什麼。或者，因爲你正在編寫一個LISP解釋，打造一雙類，並使用與object，null是的'()相當於：

public sealed class Pair 
{ 
    public object Car ; 
    public object Cdr ; 
}

直接解析您的輸入S-表達，並直接與有你的翻譯工作那。畢竟，LISP存在於AST之前！

來源

2011-02-08 10:57:12

AST的樹結構

回答

相關問題