9

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

在决定对应用程序中使用的迷你语言的处理进行重大重构之前，我正在玩弄 AST 等。我已经构建了一个 Lexer/Parser 并且可以很好地获得 AST。还有一个访问者，作为具体实现，我制作了一个 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 非常简单：所有抽象的访问者方法只是打印出终端的名称或值成员。对于非终端，它取决于；使用默认的访问者遍历打印作业可以正常工作，因为需要有条件的额外代码：

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

因此可以看出，Visitor 中的条件访问方法和 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?
  }
};

问题：这种方法不适合我的情况，还是我忽略了一些重要的东西？是否有共同的设计来应对这些问题？如果我还需要在不同的方向遍历怎么办？

4

3 回答 3

6

有两个问题：

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

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

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

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

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

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

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

语法规则告诉您必须拥有哪些节点类型。属性计算告诉你什么值被传递到树下（对method.symboltable的引用是来自父级的东西），在树上（对declarations.symbol表的引用是由那个孩子计算的东西），或者跨越树（statements.symboltable 从由 declarations.symboltable 计算的值向下传递给语句子项）。属性计算定义了访问者。执行的计算称为“属性评估”。

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

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

于 2011-02-25T18:09:28.283 回答
1

对于树的递归通用遍历，Visitor 和 Composite 通常一起使用，就像在（第一个相关的 google 链接）那里一样。我在那里第一次读到了这个想法。还有访客组合器，这是一个不错的主意。

顺便说一下...

这就是函数式语言凭借其代数数据类型和模式匹配而大放异彩的地方。如果可以，请切换到函数式语言。由于缺乏对 ADT 和模式匹配的语言支持，Composite 和 Visitor 只是丑陋的解决方法。

于 2011-02-25T17:56:21.820 回答
0

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

于 2011-02-25T17:20:01.417 回答