抽象语法树的构建和遍历

Question

我不清楚抽象语法树的结构。要在 AST 代表的程序源代码中“向下（向前）”，是直接进入最顶层的节点，还是向下？例如，示例程序会

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

产生如下所示的 AST：

或这样：

在第一个节点中，在主节点上“向右”将推进您完成该程序，但在第二个程序中，只需跟随每个节点上的 next 指针即可执行相同的操作。

似乎第二个会更正确，因为您不需要像特殊节点类型这样的东西，并且第一个节点可能具有非常长的指针数组。尽管如此，当您进入 for 循环和 if 分支以及更复杂的事情时，我可以看到第二个变得比第一个更复杂。

Answer 1

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

考虑：

这是您的第一个示例，除了缩短并带有“主”节点（概念性的稻草人） ）更恰当地命名为“块”，以反映包含命令式编程语言中的语句序列的“块”的常见构造。不同类型的节点有不同类型的子节点，有时这些子节点包括顺序很重要的辅助节点的集合，就像“块”的情况一样。例如，数组初始化也可能会产生同样的情况：

int[] arr = {1, 2}

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

这里，数组文字类型节点还具有多个相同类型的子节点，其顺序很重要。

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

Answer 3

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

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

变量范围将是您所谓的“主节点”的属性。

Answer 4

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

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

第二个也是更重要的原因是，您的“主节点”实际上可能是一个“分支节点”（例如），它可以只是更大的 AST 中的另一个节点。这样，您的 AST 就可以以递归的方式查看，其中每个 AST 都是一个节点，其他 AST 作为它的子节点。这使得第一个设计更加简单、更加通用并且非常同质。

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

干杯。