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

我必须写一个访客模式来浏览AST.任何人都可以告诉我更多如何开始写作？
据我所知,AST中的每个节点都会有访问()方法(？),这将以某种方式被调用(从哪里？).那就是我的理解.
为了简化一切,假设我有节点Root,Expression,Number,Op和树如下所示：

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

解决方法

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

它可以通过以下方式实现(我正在使用伪代码)：

首先,您需要定义所有节点必须实现的树节点的基类.

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)方法访问节点的子节点.

最后,我将使用一个类型,它们代表一个静态类型(如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
   }
}

最后你只需要实现你的类型表和操作符表.

编辑：在访问递归中,重复使用要重复的节点的accept方法实际上是正确的.

对于使用,您可以通过以下方式对解析树的根节点执行类型检查(并同时确定表达式的类型)：

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

您也可以以相同的方式键入检查与根不同的解析树的任意节点.

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

解决方法

猜你在找的C#相关文章