使用访客模式的树转换

Question

(免责声明:这些示例是在构建编译器的上下文中给出的,但是这个问题都是关于访问者模式的,并且不需要任何编译器理论知识.)我将通过Andrew Appel的Java中的现代编译器实现来尝试自学编译器理论(所以不,这不是家庭作业),我无法理解他想如何使用访客模式将AST转换为IR树.(注意:我在Python中这样做,所以我也可以学习Python,这就是为什么即将推出的示例不是Java的原因.)据我所知,访问者模式中的访问和接受方法是无效的设计类型,所以,如果我有类似的东西

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链接起来.当然,这是不可能的,除非我修改所有的接受函数以返回额外的信息,这也很麻烦,因为有时你只是想要一个不返回任何内容的打印访问者.然而,本文坚持认为访问者是正确的方式,而在Java中,这意味着它可以在没有Python灵活性的情况下完成.我想不出任何不太令人难以置信的解决方案 - 任何人都可以启发我的预期设计吗？

Answer 1

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