如何在C＃中为抽象语法树编写访问者模式？ [英] How to write Visitor Pattern for a Abstract Syntax Tree in C#?

问题描述

我必须写一个访问者模式来浏览AST。谁能告诉我更多我将如何开始写它？
据我了解，AST中的每个Node都有visit（）方法（？），该方法将以某种方式被调用（从何处？）。到此结束我的理解。
为简化所有操作，假设我有节点Root，Expression，Number，Op，并且树看起来像这样：

I have to write a visitor pattern to navigate the AST. Can anyone tell me more how would I start writing it? As far as I understand, each Node in AST would have visit() method (?) that would somehow get called (from where?). That about concludes my understanding. To simplify everything, suppose I have nodes Root, Expression, Number, Op and the tree looks like this:

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

推荐答案

模式访问者是一种设计模式，可让您在分析树上实现
任意操作（作为访问者实现）（例如，类型检查），而无需修改

Pattern visitor is a design pattern that allows you to implement arbitrary operations (implemented as visitors) on the parse tree( eg. Type-checking ) without having to modify the implementation of the nodes of the parse tree.

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

It can be implemented in the following way (i am using pseudocode):

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

First you need to define the base-class of the tree's nodes that all nodes have to implement.

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

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

The only method that node classes must implement is the accept method.

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

Then you should define the base-class of a visitor node of your parse-tree.

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

请注意，访问者的基类仅用于您的解析树，并且应该对于您在解析树中定义的每种节点类型，都有一个visit方法。

Note that visitor's base-class is made for your parse tree only, and should have one visit method for every node type you define in your parse tree.

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

Then, you should let your node classes implementation extend the VisitableNode class in the following way:

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

现在您拥有了不应该使用的解析树结构更改，您就可以自由地实现任意数量的访问者（操作）。

Now you have your parse-tree structure that should not change, and you are free to implement as many visitors (operations) as you like.

要进行类型检查，您必须在Number内存储一个类型类和您的值一起使用，或者对您支持的每种类型都有一个Number类：NumberFloat，NumberInteger，NumberDouble等。

In order to do type checking, you will have to store a type inside the Number class together with your value, or otherwise have a Number class for every type you support: NumberFloat, NumberInteger, NumberDouble, etc.

作为示例，假设您拥有一种从Number类推断值的静态类型的方法。

As an example, let's assume that you have a way to infer the static type of the value from your Number class.

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

I will also assume that you can access to node's children by method getChild(int childIndex).

最后，我将使用一个类Type，它简单地表示您要支持的静态Type（例如Float，Integer等）。

Finally, i will use a class Type that trivially represents a static Type you intend to support (like Float, Integer, etc...).

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类实现为枚举的方式类似于：

Then, you would implement the Type class probably as an enum in a way similar to:

enum Type {
   Double,
   Float,
   Integer;

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

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

And finally you only need to implement your type tables and operator tables.

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

In the visit recursion, it is actually correct to recur using the accept method of the nodes on which you want to recur.

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

As for the usage, you can perform type checking on the root node of the parse tree (and simultaneously determine the expression's type) by:

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

您还可以用相同的方式对与根不同的语法分析树的任意节点进行类型检查

You can also type-check an arbitrary node of the parse tree different from the root in the same way.

这篇关于如何在C＃中为抽象语法树编写访问者模式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！