抽象语法树构造和遍历

Question

我不清楚抽象语法树的结构.要在AST代表的程序源中"向下(向前)",你是在最顶层的节点上走,还是走下去？例如,是示例程序

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

导致AST看起来像这样:

或这个:

在第一个中,在右边的"右边" main node将推进你通过程序,但在第二个中,只需跟随next每个节点上的指针将执行相同的操作.

似乎第二个更正确,因为您不需要像第一个节点那样具有可能极长的指针数组的特殊节点类型.虽然,当你进入for循环和if分支以及更复杂的事情时,我可以看到第二个变得比第一个变得复杂.

Answer 1

第一种表示是更典型的表示,尽管第二种表示与树的构造兼容,作为递归数据结构,可以在实现平台功能性而非命令性时使用.

考虑:

这是你的第一个例子,除了缩短和"主"节点(一个概念性的稻草人)更恰当地命名为"块",以反映在命令式编程语言中包含一系列语句的"块"的通用构造.不同种类的节点具有不同种类的子节点,并且有时这些子节点包括其顺序很重要的辅助节点的集合,如"块"的情况.例如,数组初始化可能会产生同样的结果:

int[] arr = {1, 2}

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

这里,array-literal-type节点还有多个相同类型的子节点,其顺序很重要.

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)),
        });