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的树结构

回答

相关问题