问AST的树形结构

EN

有许多技术，从单一的“节点”类型-带有“类型”标签的大桶字段-到特定类的细粒度层次结构。重要的是要考虑如何使遍历代码简单和健壮，因为您将需要一遍又一遍地遍历此数据结构。

然而，退一步说，解释并不严格需要AST。许多早期的解释器会在遇到代码时直接读取每一行代码，通过基于堆栈的书签系统实现的动态解析和执行它，使用循环等。我怀疑像bash和cmd.exe这样的shell语言今天仍然像这样工作。

我建议您继续使用List<object>，直到您清楚地了解这会带来什么限制以及您的需求是什么。或者，由于您正在编写LISP解释器，因此可以创建一个成对的类并将其与object一起使用，null相当于'()

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

将您的输入直接解析为S表达式，并让您的解释器直接使用它。毕竟，LISP在AST之前就已经存在了！

大多数AST节点的实现都非常简单。

它们是一个结构(ok，ok，"class")，包含一个节点类型(通常是一个整数)，一个子节点列表(List是OK的；高性能实现有一组统计上常见的第一个，第二个，第三个子节点的成员)，以及一些额外的字段来携带特定于AST节点实例的值(例如，AST节点“整型常量”的值为"5“)。为了能够有效地将树从任何节点导航回到父节点，通常需要对父节点进行特殊的引用。

更难的是决定应该拥有哪一组AST节点。对于一个大的语法，这是不方便的，因为你必须定义一个几百个语法的集合，并且在你试图正确修改语法时会有混乱。

一个简单的技巧就是为每个语法规则定义一个AST节点。(这被大多数人称为“具体语法树”)。但它是愚蠢的，你不会错过任何东西。

我们的DMS Software Reengineering Toolkit遵循这个“简单技巧”的想法，直接从语法规则生成AST节点类型。它还优化了:不带值的叶AST节点不存在于树中，一元结果的节点不存在于树中，列表形成的结果具有子节点的列表样式，而其他节点类型具有子节点的固定槽类型。无论如何，最终的结果是非常接近于“抽象”语法树。所有这些都是由DMS的解析器生成器自动构建的，所以您根本不需要思考。

DMS也有一个完整的、经过良好测试的C# 4.0前端。一旦你克服了定义AST的麻烦，你就会想要分析/转换/生成它，然后DMS的其余部分就会突然变得有价值。