使用访问者模式的树转换

Question

（免责声明：这些例子是在构建编译器的背景下给出的，但这个问题主要是关于访问者模式，并不需要任何编译器理论的知识。）我正在阅读安德鲁·阿佩尔的《现代编译器实现（Java版）》，试图自学编译器理论（所以这不是作业），但我在理解他如何使用访问者模式将抽象语法树（AST）转换为中间表示树（IR树）时遇到了困难。（注意：我在用Python做这个，以便同时学习Python，所以接下来的例子不是用Java写的。）我理解访问者模式中的visit和accept方法设计上是没有返回值的，所以如果我有这样的代码：

class PlusExp(Exp):
    def __init__(self, exp_left, exp_right):
        self.exp_left = exp_left
        self.exp_right = exp_right

    def accept(self, v):
        v.visit_plus_exp(self)

那么我希望能够写一个访问者方法，比如：

def visit_plus_exp(self, plus_exp):
    return BINOP(BinOp.PLUS, 
                 plus_exp.exp_left.accept(self), 
                 plus_exp.exp_right.accept(self))

这个方法可以把两个子表达式转换成IR，然后把它们和表示加法的BINOP连接起来。当然，除非我修改所有的accept函数让它们返回额外的信息，否则这是不可能的。而且这样做也很麻烦，因为有时候你只想要一个不返回任何东西的打印访问者。不过，这段文字坚持认为使用访问者是正确的方式，而且是在Java中，这意味着即使没有Python的灵活性也能做到。我想不出任何不是非常 hacky 的解决方案——有没有人能给我解释一下预期的设计？

Answer 1

注意：我没有读过那本书。

这个方法可能是“无返回值”的类型，但在Java（这本书是为Java写的）中，它也是一个对象的一部分。所以，访问者方法可以在一个本地的成员变量中构建结构，这样在多次调用之间就能保持必要的上下文。

举个例子，你的打印访问者可以把内容添加到一个作为成员变量的StringBuilder中（或者作为一个最终的本地变量在创建访问者对象的方法中，这在Java中很常见，因为创建小的匿名内部类对象是一种常见的习惯）。

在Python中，你也可以让访问者方法访问一个非方法本地的变量，以保持上下文并构建结构。比如，使用闭包或者一个小对象。

更新 -- 添加了一小段代码作为下面评论的例子

result = new Node();
result.left.add(n1.accept(this)); 
result.right.add(n2.accept(this)); 
return result;

或者

result = new Node(); 
this.nextLoc.add(result); 
this.nextLoc = result.left; 
n1.accept(this); 
this.nextLoc = result.right; 
n2.accept(this); 

第一个例子看起来更好（虽然还是个糟糕的注释示例代码），但第二个例子如果你真的需要的话，可以让你保持无返回值的类型。

Answer 2

看看这个编译器的源代码。我觉得这个作者使用了访问者模式。

Answer 3

SAX解析器是一种访问者模式。为了避免在方法中添加返回值，你可以使用一个栈：

class Visitor {
    Stack<Node> stack = new Stack<Node>();

//    . . .

    void visitPlus(PlusExp pe) {
        pe.left.accept(this);
        pe.right.accept(this);
        Node b = stack.pop();
        Node a = stack.pop();
        stack.push(new BinOp(BinOp.PLUS, a, b));
    }