抽象语法树的构造和遍历

| 我不清楚抽象语法树的结构。要在AST表示的程序的源代码中“向下(前进)”,您是直接在最顶层的节点上还是向下移动?例如,示例程序
a = 1
b = 2
c = 3
d = 4
e = 5
生成一个如下所示的AST: 或这个: 在第一个中,在
main node
上向“右”前进将使您进入程序,但在第二个中,仅跟随每个节点上的
next
指针将执行相同的操作。 似乎第二种方法会更正确,因为您不需要像特殊的节点类型之类的东西,因为第一个节点的指针数组可能非常长。虽然,当您进入
for
循环和
if
分支以及更复杂的事物时,我可以看到第二个比第一个更加复杂。     
已邀请:
        第一种表示形式较为典型,尽管第二种表示形式与作为递归数据结构的树的构造兼容,如在实现平台功能正常而非强制性使用时可以使用。 考虑: 这是您的第一个示例,只是它有所缩短,并且\“ main \”节点(概念上是个稻草人)更恰当地命名为\“ block \”,以反映包含以下语句序列的\“ block \”的通用构造:一种命令式编程语言。不同种类的节点具有不同种类的子节点,有时这些子节点包含其顺序很重要的子节点的集合,例如\“ block。\”的情况。例如,数组初始化可能会产生相同的结果:
int[] arr = {1, 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)),
        });
    
        这取决于语言。在C语言中,您必须使用第一种形式来捕获块的概念,因为块具有可变范围:
{
    {
        int a = 1;
    }
    // a doesn\'t exist here
}
变量作用域将是您称为“主节点”的属性。     
        我相信您的第一个版本更有意义,原因有两个。 首先,第一个更清楚地说明了程序的“嵌套”,并且也清楚地实现为有根树(这是树的通常概念)。 第二个也是更重要的原因是您的“主节点”实际上可能是“分支节点”(例如),它可以只是较大AST中的另一个节点。这样,您的AST可以以递归方式查看,其中每个AST都是其他AST的子节点。这使第一个设计变得更加简单,通用和非常统一。     
        建议:在处理树数据结构时,无论是与编译器相关的AST还是其他类型,始终使用单个\“ root \”节点,它可以帮助您执行操作并拥有更多控制权:
class ASTTreeNode {
  bool isRoot() {...}

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

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

  // ...

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

要回复问题请先登录注册