AST 遍历是在访问者中还是在节点中？

Question

更新接受了Ira Baxter的回答，因为它为我指明了正确的方向：我首先通过开始编译阶段的实现来弄清楚我实际需要什么，并且很快就很明显，节点内的遍历使得这是一个不可能的方法。并非所有节点都应该被访问，其中一些节点的顺序相反（例如，首先访问赋值的 rhs，以便编译器可以检查类型是否与 rhs/operator 匹配）。将遍历放入访问者中使这一切变得非常容易。

在决定对应用程序中使用的迷你语言的处理进行主要重构之前，我正在尝试 AST 等。 我已经构建了一个 Lexer/Parser，并且可以很好地获取 AST。还有一个 Visitor，作为具体实现，我制作了一个 ASTToOriginal，它只是重新创建原始源文件。最终将会有某种编译器也实现 Vsisitor 并在运行时创建实际的 C++ 代码，所以我想确保一切从一开始就是正确的。 虽然现在一切正常，但由于遍历顺序是在访问者本身中实现的，因此存在一些类似/重复的代码。

当查找更多信息时，似乎某些实现更喜欢在访问的对象本身中保留遍历顺序，以免在每个具体访问者中重复此操作。 即使 GoF 也只是简单地谈论这一点，以同样的方式。所以我也想尝试这种方法，但很快就陷入困境......让我解释一下。

示例源代码行和相应的 AST 节点：

if(t>100?x=1;sety(20,true):x=2)
Conditional
  BinaryOp
    left=Variable [name=t], operator=[>], right=Integer [value=100]
  IfTrue
    Assignment
      left=Variable [name=x], operator=[=], right=Integer [value=1] 
    Method
      MethodName [name=sety], Arguments( Integer [value=20], Boolean [value=true] )
  IfFalse
    Assignment
      left=Variable [name=x], operator=[=], right=Integer [value=1]

一些代码：

class BinaryOp {
  void Accept( Visitor* v ){ v->Visit( this ); }
  Expr* left;
  Op* op;
  Expr* right;
};    
class Variable {
  void Accept( Visitor* v ){ v->Visit( this ); }
  Name* name;
};
class Visitor { //provide basic traversal, terminal visitors are abstract
  void Visit( Variable* ) = 0;
  void Visit( BinaryOp* p ) {
    p->left->Accept( this );
    p->op->Accept( this );
    p->right->Accept( this );        
  }
  void Visit( Conditional* p ) {
    p->cond->Accept( this );
    VisitList( p->ifTrue ); //VisitList just iterates over the array, calling Accept on each element
    VisitList( p->ifFalse );
  }
};

实现 ASTToOriginal 非常简单：所有抽象 Visitor 方法都只是打印出终端的名称或值成员。 对于非终结符，这取决于；打印分配可以在默认的访问者遍历中正常工作，因为需要条件额外的代码：

class ASTToOriginal {
  void Visit( Conditional* p ) {
    str << "if(";
    p->cond->Accept( this );
    str << "?";
      //VisitListWithPostOp is like VisitList but calls op for each *except the last* iteration
    VisitListWithPostOp( p->ifTrue, AppendText( str, ";" ) );
    VisitListWithPostOp( p->ifFalse, AppendText( str, ";" ) );
    str << ")";
  }
};

因此可以看到访问者和 ASTToOriginal 中条件的访问方法确实非常相似。 然而，试图通过遍历节点来解决这个问题不仅使事情变得更糟，而且变得一团糟。 我尝试了一种使用 PreVisit 和 PostVisit 方法的方法，它解决了一些问题，但只是在节点中引入了越来越多的代码。 它也开始看起来像我必须跟踪访问者内部的许多状态才能知道何时添加右括号等。

class BinaryOp {
  void Accept( Conditional* v ) { 
    v->Visit( this );
    op->Accept( v )
    VisitList( ifTrue, v );
    VisitList( ifFalse, v );
};
class Vistor {
  //now all methods are pure virtual
};
class ASTToOriginal {
  void Visit( Conditional* p ) {
    str << "if(";
    //now what??? after returning here, BinaryOp will visit the op automatically so I can't insert the "?"
    //If I make a PostVisit( BinaryOp* ), and call it it BinaryOp::Accept, I get the chance to insert the "?",
    //but now I have to keep a state: my PostVisit method needs to know it's currently being called as part of a Conditional
    //Things are even worse for the ifTrue/ifFalse statement arrays: each element needs a ";" appended, but not the last one,
    //how am I ever going to do that in a clean way?
  }
};

问题：这种方法是否不适合我的情况，或者我忽略了一些重要的事情？有没有一个通用的设计来解决这些问题？如果我还需要不同方向的遍历怎么办？

Answer 1

这里有两个问题：

• 哪些子节点可以访问？
• 您应该以什么顺序拜访他们？

可以说，实际的子节点应该通过节点类型来了解；实际上，它应该被语法所了解，并从语法“反映”到一般访问者中。

访问节点的顺序完全取决于您需要执行的操作。如果您正在进行漂亮打印，则从左到右的子顺序是有意义的（如果子节点按语法顺序列出，但它们可能不是）。如果您正在构建符号表，那么您肯定希望在访问语句主体子级之前访问声明子级。

此外，您还需要担心哪些信息在树上向上或向下流动。变量访问列表将沿树向上流动。构造的符号表从声明沿树向上流动，并向下返回到语句体子级。而这个信息流强制访问顺序；为了将符号表向下传递到语句主体中，首先必须构造一个符号表并从声明子级向上传递。

我认为这些问题会让你感到悲伤。您试图对访问者强加单一结构，而实际上访问顺序完全依赖于任务，并且您可能对树执行许多不同的任务，每个任务都有自己的信息流，因此具有顺序依赖性。

解决这个问题的方法之一是使用 attribute(d) 语法 (AG) 的概念，其中用各种类型的属性以及它们的计算/使用方式来装饰语法规则。您实际上将计算编写为语法规则的注释，例如：

  method = declarations statements ;
  <<ResolveSymbols>>: { declarations.parentsymbols=method.symboltable;
                        statements.symboltable = declarations.symboltable;
                      }

语法规则告诉您必须具有哪些节点类型。属性计算告诉您什么值正在沿着树向下传递（对 method.symboltable 的引用是来自父级的某些值），向上传递给树（对 statements.symbol 表的引用是由该子级计算的某些值），或者跨树传递什么值。树（statements.symboltable 从由 statements.symboltable 计算的值向下传递到 statements 子级）。属性计算定义访问者。所执行的计算称为“属性评估”。

此特定属性语法的表示法是我们 DMS 软件重新工程工具包 的一部分。其他 AG 工具使用类似的符号。与所有（AG）方案一样，特定规则用于为特定节点（“方法”）制造特定目的（“ResolveSymbols”）访问者。通过每个节点的一组此类规范，您将获得一组可以执行的特定目的访问者。
AG 方案的价值在于您可以轻松编写此方案，并且会生成所有样板文件。

您可以像这样抽象地思考您的问题，然后像您一直在做的那样，简单地手动生成特定目的的访问者。

Answer 2

对于树的递归通用遍历，访问者和复合体通常一起使用，例如（第一个相关的谷歌链接）那里。我第一次读到这个想法是在那里。还有访问者组合器一个好主意。

顺便说一句......

这就是函数式语言的闪光点，它具有代数数据类型和模式匹配。如果可以的话，切换到函数式语言。 Composite 和 Visitor 只是丑陋的解决方法，因为分别缺乏对 ADT 和模式匹配的语言支持。

Answer 3

IMO，我会让每个具体类（例如 BinaryOp、Variable）扩展 Visitor 类。这样，创建 BinaryOp 对象所需的所有逻辑都将驻留在 BinaryOp 类中。此方法类似于 Walkabout 模式。它可能会让你的任务变得更容易。