18

我必须编写一个访问者模式来导航 AST。谁能告诉我更多我将如何开始写它？据我了解，AST 中的每个节点都会有 visit() 方法（？），它会以某种方式被调用（从哪里？）。我的理解到此结束。为了简化一切，假设我有节点 Root、Expression、Number、Op，树看起来像这样：

      Root
        |
       Op(+)
      /   \
     /     \
 Number(5)  \
             Op(*)
             /   \
            /     \
           /       \
       Number(2)   Number(444)
4

1 回答 1

35

模式访问者是一种设计模式，它允许您在解析树上实现任意操作（作为访问者实现）（例如类型检查），而无需修改解析树节点的实现。

它可以通过以下方式实现（我使用的是伪代码）：

首先，您需要定义所有节点都必须实现的树节点的基类。

abstract class VisitableNode {
   abstract void accept( Visitor v );
}

节点类必须实现的唯一方法是 accept 方法。

然后，您应该定义分析树的访问者节点的基类。

abstract class Visitor {
   abstract void visit( Root rootNode );
   abstract void visit( Op opNode );
   abstract void visit( Number number );
}

请注意，访问者的基类仅适用于您的解析树，并且应该为您在解析树中定义的每个节点类型提供一个访问方法。

然后，您应该让您的节点类实现以下列方式扩展 VisitableNode 类：

class Root : VisitableNode {
   [...]
   void accept( Visitor v ) {
      v.visit(this);
   }
}

class Op : VisitableNode {
   [...]
   void accept( Visitor v ) {
      v.visit(this);
   }
}

class Number : VisitableNode {
   [...]
   void accept( Visitor v ) {
      v.visit(this);
   }
}

现在您拥有不应更改的解析树结构，并且您可以随意实现任意数量的访问者（操作）。

为了进行类型检查，您必须将类型与您的值一起存储在 Number 类中，或者为您支持的每种类型都有一个 Number 类：NumberFloat、NumberInteger、NumberDouble 等。

例如，假设您有一种方法可以从 Number 类中推断出值的静态类型。

我还将假设您可以通过 getChild(int childIndex) 方法访问节点的子节点。

最后，我将使用一个简单地表示您打算支持的静态类型的类 Type（如 Float、Integer 等......）。

class TypeCheckVisitor : Visitor {

   // Field used to save resulting type of a visit
   Type resultType;


   void visit( Root rootNode )
   {
      rootNode.getChild(0).accept( this );
   }

   void visit( Op opNode )
   {
      opNode.getChild(0).accept( this );
      Type type1 = resultType;

      opNode.getChild(1).accept( this );
      Type type2 = resultType;

      // Type check
      if( !type1.isCompatible( type2 ) ){
         // Produce type error
      }

      // Saves the return type of this OP (ex. Int + Int would return Int)
      resultType = typeTableLookup( opNode.getOperator(), type1, type2 );
   }

   void visit( Number number )
   {
      // Saves the type of this number as result
      resultType = number.getType();
   }
}

然后，您可能会以类似于以下方式将 Type 类实现为枚举：

enum Type {
   Double,
   Float,
   Integer;

   boolean isCompatible(Type type1, Type type2){
      // Lookup some type table to determine types compatibility
   }
}

最后，您只需要实现您的类型表和运算符表。

编辑：在访问递归中，使用要递归的节点的接受方法进行递归实际上是正确的。

至于用法，您可以通过以下方式对解析树的根节点进行类型检查（并同时确定表达式的类型）：

TypeCheckVisitor v = new TypeCheckVisitor();
rootNode.accept( v );
print( "Root type is: " + v.resultType );

您还可以以相同的方式对不同于根的解析树的任意节点进行类型检查。

于 2013-08-03T19:00:20.257 回答