Как красиво распечатать AST, используя шаблон Visitor? - PullRequest
Новая
       35

Как красиво распечатать AST, используя шаблон Visitor?

0 голосов
/ 25 мая 2019

Я пытаюсь создать простой интерпретатор, используя шаблон Visitor.Я с трудом пытаюсь понять, как с помощью этого шаблона можно реализовать такую ​​задачу, как красивая печать дерева.

Результат, который я пытаюсь получить, - это печать AST с правильным отступом: 

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

Я определил количество классов, представляющих узлы в AST: 

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 Visitor
    def visit(subject)
        method_name = "visit_#{subject.class}".intern
        send(method_name, subject)
    end
end

Наконец,посетитель для печати АСТ: 

class PrintVisitor < Visitor
    def visit_ExprNode(subject)
    end

    def visit_AbstrNode(subject)
    end

    ...
end

1 Ответ

1 голос
/ 26 мая 2019

Существует две версии шаблона посетителя: одна версия выполняет только двойную диспетчеризацию, а другая - итерацию, автоматически посещая дочерние элементы узла. Последняя версия менее гибкая, потому что вы решаете, какой тип обхода (предзаказ или постзаказ) вы хотите заблаговременно, а не оставляете это решение для отдельного посетителя. Это также вынуждает вас посещать все узлы ровно один раз (что вам не нужно во многих случаях, например, при реализации интерпретатора AST).

В вашем коде вы на самом деле реализуете обе эти версии: ваш Visitor#visit метод реализует шаблон простого посетителя, а ASTNode#accept реализует шаблон с итерацией. Это странное использование метода accept, потому что обычно работа метода accept заключается в простом вызове определенного метода visit (например, visit_whatever) для посетителя, чтобы заставить работать двойную диспетчеризацию. Поскольку вы использовали отражение для реализации двойной диспетчеризации, вам совершенно не нужен метод accept.

Я предполагаю, что печать должна быть реализована в методах посещения (субъекта) PrintVisitor

Это правильно.

Для печати каждого узла требуется дополнительный контекст для определения правильного уровня отступа.

Также правильно. Вы можете отслеживать уровень отступов, сохраняя его в переменной экземпляра. Затем данный метод посетителя распечатывает его содержимое с заданным количеством отступов, увеличивает уровень отступа, посещает его дочерние заметки, а затем снова уменьшает отступ. Примерно так: 

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) и просто вызывать его для тех случаев, когда вы хотите выполнить одно и то же действие для всех детей (как указано выше).

Если вы хотите избежать этого изменяемого состояния, вы также можете настроить свой класс посетителя, чтобы разрешить передачу аргументов в visit следующим образом: 

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

Затем вы можете добавить параметр для уровня отступа в ваши методы и передать увеличенный уровень отступа до visit при посещении ваших детей.

...