代码之家 › 专栏 › 技术社区 › danben

使用访问者模式的树转换

visitor-pattern abstract-syntax-tree tree python java

danben · 技术社区 · 15 年前

(免责声明:这些例子是在编译一个编译器的情况下给出的,但是这个问题是关于访问者模式的,不需要任何编译器理论的知识。)我要通过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将它们链接起来。当然,除非我修改所有的accept函数来返回额外的信息,否则这是不可能的,而且这也很混乱,因为有时您只需要一个不返回任何内容的打印访问者。然而,这篇文章坚持认为访问者是正确的方式,在Java中,这意味着它可以在没有Python灵活性的情况下完成。我想不出任何解决方案都不是那么简单——有人能告诉我设计意图吗?

3 回复 | 直到 15 年前

Maurice Perry 15 年前

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

Pratik Deoghare 15 年前

查看的源代码 THIS 编译器。我认为那个人使用了访客模式。

William Billingsley 15 年前

警告:我还没读过那本书。

该方法可以是空类型的,但在Java中(它是为该书编写的),它也是对象的一部分。因此,visitor方法可以在局部成员变量中构建结构,从而在调用之间维护必要的上下文。

因此,例如,您的打印访问者将追加到作为成员变量(或创建访问者对象的方法中的最终本地变量)的StrugBuudor中,这在爪哇相当常见,其中创建小的匿名内部类对象是一种常见习惯。

在Python中,同样可以让visitor方法访问非方法局部变量来维护上下文和构建结构。例如,封闭物或小物体。

update——下面的注释中作为示例添加的一小部分代码

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

第一个是更漂亮的(尽管仍然是糟糕的注释示例代码),但第二个则允许您保留void返回类型(如果确实需要的话)。