java - 表达式树和访问者模式的实现

Question

我有一个层次结构的对象来表示算术表达式。类似于以下内容:

      TreeNode
     /        \
    /          \
   /            \ 
NumericNode    BinaryOpNode
              /  |    \    \
             /   |     \    \
            /    |      \    \   
      AddNode MulNode DivNode ...etc  

我有词法分析器和解析器在工作。现在我正试图找出以实用且易于适应的方式对生成的 AST 执行操作的最佳方法。 现在我已经实现了带有 Visitor 和 Visitable 接口(interface)的 Visitor 模式，但我不确定我是否真的需要所有具体类来实现 Visitable 接口(interface)。

由于我想控制访问者中的遍历顺序，我发现自己重复了很多代码。例如，对于 PrintInOrder 访问者，我有如下方法:

    public void visit(AddNode node) { 
       node.getLeft().accept(this);
       System.out.print(node + " ");
       node.getRight().accept(this);
    }

对于代表某种算术运算的每个具体节点。

但我可以在父类(super class)中实现相同的 Visitable 实现。例如，相同的 PrintInOrder 访问者看起来像:

    public void visit(BinaryOpNode node) { 
       node.getLeft().accept(this);
       System.out.print(node + " ");
       node.getRight().accept(this);
    }

但是，我不知道这项任务最常用的方法是什么。

问题 1:如果我想让我的设计让我通过 AST 做几乎任何我想做的事，我真的需要访问所有具体节点并编写所有重复代码吗？。

问题 2:假设一个访问者可以返回某种类型，例如:

public interface Visitor<T> {
    public T visit(AddNode node);
    public T visit(MulNode node);
        ...
}

这看起来比普通的 void 版本更通用。但它有有用的好处吗？并且可以和void版一样使用？

Answer 1

答案 1:您可以使用抽象父类(super class)访问方法和任何通用功能，这在每个具体类中都是相同的，因此每个具体类都可以从这个抽象类派生并使用该方法而无需实现这是一种多余的方式。

如图所示，您可以在单独的类中实现访问者逻辑。这样你就可以解耦遍历顺序，以及从 Node 实现中访问节点的实现。如果您根据算术运算优先级构建了抽象语法树，则不必更改不同类型节点的实现。您可以为它们中的每一个使用相同的 ConcreteVisitor。

答案 2:是的，使用泛型类在很多方面都是有益的。这样你就可以在编译时进行类型检查。如果你没有这个机会，你可能隐藏了 bug，很难发现，但是如果你可以检查类型有效性编译时间，你可以确保你的系统中没有这种类型的 bug。