7

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

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

生成如下所示的 AST： 在此处输入图像描述

或这个： 在此处输入图像描述

在第一个中，“向右”main node将引导您完成程序，但在第二个中，只需跟随next每个节点上的指针即可。

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

4

5 回答 5

5

第一种表示是更典型的一种，尽管第二种与将树构造为​​递归数据结构兼容，当实现平台是功能性而不是命令性时可以使用它。

考虑：

在此处输入图像描述

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

int[] arr = {1, 2}

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

在此处输入图像描述

这里，array-literal-type 节点也有多个相同类型的子节点，它们的顺序很重要。

于 2011-05-27T18:30:05.070 回答
4

在第一个中，在主节点上“向右”将引导您完成程序，但在第二个中，只需跟随每个节点上的 next 指针即可。

似乎第二个会更正确，因为您不需要像特殊节点类型这样的东西，第一个节点的指针数组可能非常长

我几乎总是更喜欢第一种方法，而且我认为当您不需要维护指向下一个节点的指针时，您会发现构建 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)),
        });
于 2011-05-27T18:44:17.277 回答
1

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

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

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

于 2011-05-27T18:21:38.010 回答
1

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

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

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

于 2011-05-27T18:29:51.410 回答
0

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

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

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

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

  // ...

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

干杯。

于 2011-05-27T18:24:42.667 回答