如何使用访客模式漂亮地打印 AST？

Question

我正在尝试使用访问者模式构建一个简单的解释器。我很难理解如何使用这种模式来实现诸如漂亮打印树之类的任务。

我试图获得的结果是打印带有适当缩进的 AST：

Expr
'---Abstr
    |---Id
    '---Expr
        '---App
            '---Atom
                '---Id

我在 AST 中定义了一些 classes 表示节点：

class ASTNode
    attr_reader :children, :pos

    def initialize(children, pos)
         @children = children
         @pos = pos
    end

    def accept(visitor)
        visitor.visit(self)
        @children.each { |child| child.accept(visitor) } unless @children.nil?
    end
end

class ExprNode < ASTNode
    def initialize(children, pos)
         super(children, pos)
    end
end

...

和一个基本访问者 class 执行双重调度：

class Visitor
    def visit(subject)
        method_name = "visit_#{subject.class}".intern
        send(method_name, subject)
    end
end

最后，打印AST的访问者：

class PrintVisitor < Visitor
    def visit_ExprNode(subject)
    end

    def visit_AbstrNode(subject)
    end

    ...
end

Answer 1

访问者模式有两个版本：一个版本只负责双重调度，另一个版本还通过自动访问节点的 children 来处理迭代。后一个版本不太灵活，因为您可以提前决定您想要哪种遍历（pre-order 或 post-order），而不是将决定权留给个别访问者。它还会强制您只访问所有节点一次（在许多情况下您不希望这样做，例如在实现 AST 解释器时）。

在您的代码中，您实际上实现了这两个版本：您的 Visitor#visit 方法实现了普通访问者模式，ASTNode#accept 实现了迭代模式。这是 accept 方法的一种奇怪用法，因为通常 accept 方法的工作只是在访问者上调用特定的 visit 方法（如 visit_whatever）以使双重分派工作.由于您已经使用反射来实现双重分派，因此您根本不需要 accept 方法。

I assume that the printing should be implemented in visit_*Node(subject) methods of PrintVisitor

没错。

Printing each node requires additional context to determine the right indentation level.

也正确。您可以通过将缩进级别存储在实例变量中来跟踪缩进级别。然后，给定的访问者方法将使用给定的缩进量打印其内容，增加缩进级别，访问其 child 注释，然后再次减少缩进。像这样：

def visit_SomeNode(some_node)
    puts "#{@indent * " "}---SomeNode"
    @indent += 4
    some_node.children.each {|child| visit(child)}
    @indent -= 4
end

您也可以将 some_node.children.each {|child| visit(child)} 放入它自己的 visit_children(node) 方法中，并在您希望对所有 children 执行相同操作的情况下调用它（如上所述） .

如果您想避免这种可变状态，您还可以调整访问者 class 以允许将参数传递给 visit，如下所示：

class Visitor
    def visit(subject, *args)
        method_name = "visit_#{subject.class}".intern
        send(method_name, subject, *args)
    end
end

然后您可以将缩进级别的参数添加到您的方法中，并在访问您的 children.

时将增加的缩进级别传递给 visit

如何使用访客模式漂亮地打印 AST？

How to pretty-print an AST using Visitor pattern?

ruby

abstract-syntax-tree

interpreter

visitor-pattern