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

问题描述

我必须编写一个访问者模式来导航 AST.谁能告诉我更多我将如何开始写作?据我了解，AST 中的每个节点都会有访问()方法(?)，该方法会以某种方式被调用(从哪里?).我的理解到此结束.为了简化一切，假设我有节点 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)

推荐答案

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

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

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

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，它简单地表示您打算支持的静态类型(如 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屋！