c# - 如何在 C# 中为抽象语法树编写访问者模式？

Question

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

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

Answer 1

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

可以通过以下方式实现(我使用的是伪代码):

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

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

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