抽象语法树的构建和遍历

Question

我不清楚抽象语法树的结构。如果要在AST表示的程序源中“向下（前进）”，是要在最上面的节点右移还是向下移？例如，下面这个示例程序：

a = 1
b = 2
c = 3
d = 4
e = 5

生成如下所示的抽象语法树：

或者如下：

在第一个示例中，从main node向右移动将带您通过程序，但是在第二个示例中，仅跟随每个节点上的next指针即可完成相同的操作。

似乎第二种方法更正确，因为您不需要像第一种方法那样使用特殊的节点类型，并且需要具有可能非常长的指针数组。虽然，当涉及到for循环、if分支和更复杂的内容时，第二个示例可能会比第一个更复杂。

- Seth Carnegie

Answer 1

第一个表示法更为典型，虽然第二个对于将树构建为递归数据结构的情况是兼容的，当实现平台是函数式而不是命令式时可能会使用这种方法。

考虑： 这是你的第一个例子，缩短并更恰当地将“主”节点（一个概念性的替代品）命名为“块”，以反映在命令式编程语言中包含一系列语句的常见构造。不同类型的节点具有不同类型的子节点，有时这些子节点包括重要的子节点集合，如“block”的情况。同样的问题可能出现在，比如数组初始化中：

int[] arr = {1, 2}

考虑如何在语法树中表示它：

图中，数组字面量类型节点也有多个相同类型的子节点，其顺序很重要。

- Jollymorphic

Answer 2

在第一个例子中，沿着主节点向“右”移动将使您通过程序前进，但在第二个例子中，仅需按照每个节点上的下一个指针进行操作即可完成相同的操作。似乎第二种方法更正确，因为您不需要像第一个节点那样拥有潜在的极长指针数组的特殊节点类型。

我几乎总是更喜欢第一种方法，并且当您不需要维护对下一个节点的指针时，构建AST会更容易。

我认为通常最好让所有对象都从一个共同的基类派生，就像这样：

abstract class Expr { }

class Block : Expr
{
    Expr[] Statements { get; set; }
    public Block(Expr[] statements) { ... }
}

class Assign : Expr
{
    Var Variable { get; set; }
    Expr Expression { get; set; }
    public Assign(Var variable, Expr expression) { ... }
}

class Var : Expr
{
    string Name { get; set; }
    public Variable(string name) { ... }
}

class Int : Expr
{
    int Value { get; set; }
    public Int(int value) { ... }
}

生成的AST如下：

Expr program =
    new Block(new Expr[]
        {
            new Assign(new Var("a"), new Int(1)),
            new Assign(new Var("b"), new Int(2)),
            new Assign(new Var("c"), new Int(3)),
            new Assign(new Var("d"), new Int(4)),
            new Assign(new Var("e"), new Int(5)),
        });

- Juliet

Answer 3

这取决于语言。在C语言中，你必须使用第一种形式来捕获一个块的概念，因为一个块有一个变量作用域：

{
    {
        int a = 1;
    }
    // a doesn't exist here
}

变量作用域将是您所谓的“主节点”的属性。

- Fred Foo

---

抱歉，我不理解“二进制主节点”，也无法从您的Lisp示例中真正理解它（可能是因为我从未使用过Lisp）。您能详细说明一下吗？ - Seth Carnegie

@Seth：那么 Lisp 风格的例子就不要紧了。我已经发布了一个类 C 的例子，解释为什么你需要第一种形式。 - Fred Foo

所以你需要使用一个具有_n_个子节点的节点来作为根节点（用于保存主程序和其他内容），还有什么？我不知道AST被用来显示块作用域或其他什么。 - Seth Carnegie

@Seth：AST代表程序的语法结构。其中包括语法/词法作用域。 - Fred Foo

Answer 4

我认为你的第一个版本更有意义，原因有几个。

首先，第一个版本更清晰地展示了程序的“嵌套性”，并且明确实现为根树（这是树的通常概念）。

第二个，更重要的原因是，你的“主节点”实际上可以是一个“分支节点”（例如），它只是一个更大的AST中的另一个节点。这样，你的AST可以在递归意义下被视为一个节点，其子节点是其他AST。这使得第一个设计更简单、更通用、更均匀。

- Ken Wayne VanderLinde

Answer 5

建议：在处理树形数据结构时，无论是编译器相关的AST还是其他类型，请始终使用单个“根”节点，这可能有助于您执行操作并具有更多控制：

class ASTTreeNode {
  bool isRoot() {...}

  string display() { ... }  
  // ...
}

void main ()
{
  ASTTreeNode MyRoot = new ASTTreeNode();

  // ...

  // prints the root node, plus each subnode recursively
  MyRoot.Show();
}

干杯。

- umlcat