Как написать шаблон посетителя для абстрактного синтаксического дерева в Python?

Question

Мой коллега предложил мне написать шаблон посетителей для навигации по AST. Может кто-нибудь сказать мне больше, как бы я начал писать это?

Насколько я понимаю, каждый узел в AST будет иметь visit() метод (?), который каким-то образом вызывается (откуда?). Это о заключении моего понимания.

Чтобы упростить все, предположим, у меня есть узлы Root, Expression, Number, Op и дерево выглядит так:

       Root
        |
       Op(+)
      /   \
     /     \
 Number(5)  \
             Op(*)
             /   \
            /     \
           /       \
       Number(2)   Number(444)

Может кто-нибудь подумать о том, как шаблон посетителя посетит это дерево для получения вывода:

 5 + 2 * 444

Спасибо, Бода Кидо.

Answer 1

В Википедии есть отличный обзор того, как работает шаблон Visitor, хотя пример реализации, который они используют, находится на Java. Вы можете легко перенести это на Python, хотя, нет?

По сути, вы хотите реализовать механизм двойной отправки. Каждый узел в вашем AST должен был бы реализовать accept() метод (НЕ visit() метод). Метод принимает в качестве аргумента объект посетителя. В реализации этого accept() метод, вы называете visit() метод объекта посетителя (будет один для каждого типа узла AST; в Java вы будете использовать перегрузку параметров, в Python, я полагаю, вы можете использовать разные visit_*() методы). Правильный посетитель будет отправлен с правильным типом узла в качестве аргумента.

Answer 2

Смотрите документы для ast.NodeVisitorНапример, грубая возможность может быть:

import ast

class MyVisitor(ast.NodeVisitor):
  def visit_BinaryOp(self, node):
    self.visit(node.left)
    print node.op,
    self.visit(node.right)
  def visit_Num(self, node):
    print node.n,

конечно, это не выводит скобки даже там, где это необходимо, и т. д., так что на самом деле больше работы сделано, но это только начало;-).

Answer 3

Два варианта реализации шаблона Visitor в Python, с которыми я чаще всего сталкивался в Интернете:

• Индивидуальный перевод примера из книги "Образцы Дези" Гаммы и соавт.
• Использование дополнительных модулей для двойной отправки

Переведенный пример из книги Desigh Patterns

Этот вариант использует accept() методы в классах структуры данных и соответствующих visit_Type() методы у посетителей.

Структура данных

class Operation(object):
    def __init__(self, op, arg1, arg2):
        self.op = op
        self.arg1 = arg1
        self.arg2 = arg2
    def accept(self, visitor):
        visitor.visitOperation(self)

class Integer(object):
    def __init__(self, num):
        self.num = num
    def accept(self, visitor):
        visitor.visitInteger(self)

class Float(object):
    def __init__(self, num):
        self.num = num
    def accept(self, visitor):
        visitor.visitFloat(self)

expression = Operation('+', Integer('5'),
                            Operation('*', Integer('2'), Float('444.1')))

Инфикс Принт Посетитель

class InfixPrintVisitor(object):
    def __init__(self):
        self.expression_string = ''
    def visitOperation(self, operation):
        operation.arg1.accept(self)
        self.expression_string += ' ' + operation.op + ' '
        operation.arg2.accept(self)
    def visitInteger(self, number):
        self.expression_string += number.num
    def visitFloat(self, number):
        self.expression_string += number.num

Префикс Печать Посетитель

class PrefixPrintVisitor(object):
    def __init__(self):
        self.expression_string = ''
    def visitOperation(self, operation):
        self.expression_string  += operation.op + ' '
        operation.arg1.accept(self)
        self.expression_string  += ' '
        operation.arg2.accept(self)
    def visitInteger(self, number):
        self.expression_string += number.num
    def visitFloat(self, number):
        self.expression_string += number.num

Тестовое задание

infixPrintVisitor = InfixPrintVisitor()
expression.accept(infixPrintVisitor)
print(infixPrintVisitor.expression_string)
prefixPrintVisitor = PrefixPrintVisitor()
expression.accept(prefixPrintVisitor)
print(prefixPrintVisitor.expression_string)

Выход

5 + 2 * 444.1
+ 5 * 2 444.1

Использование дополнительных модулей

Этот вариант использует @functools.singledispatch() декоратор (доступен в стандартной библиотеке Python начиная с Python v3.4).

Структура данных

class Operation(object):
    def __init__(self, op, arg1, arg2):
        self.op = op
        self.arg1 = arg1
        self.arg2 = arg2

class Integer(object):
    def __init__(self, num):
        self.num = num

class Float(object):
    def __init__(self, num):
        self.num = num

expression = Operation('+', Integer('5'), 
                            Operation('*', Integer('2'), Float('444.1')))

Инфикс Принт Посетитель

from functools import singledispatch

@singledispatch
def visitor_print_infix(obj):
    pass
@visitor_print_infix.register(Operation)
def __(operation):
    return visitor_print_infix(operation.arg1) + ' ' \
               + operation.op + ' ' \
               + visitor_print_infix(operation.arg2)
@visitor_print_infix.register(Integer)
@visitor_print_infix.register(Float)
def __(number):
    return number.num

Префикс Печать Посетитель

from functools import singledispatch

@singledispatch
def visitor_print_prefix(obj):
    pass
@visitor_print_prefix.register(Operation)
def __(operation):
    return operation.op + ' ' \
               + visitor_print_prefix(operation.arg1) + ' ' \
               + visitor_print_prefix(operation.arg2)
@visitor_print_prefix.register(Integer)
@visitor_print_prefix.register(Float)
def __(number):
    return number.num

Тестовое задание

print(visitor_print_infix(expression))
print(visitor_print_prefix(expression))

Выход

5 + 2 * 444.1
+ 5 * 2 444.1

Причина, по которой я предпочитаю этот вариант, состоит в том, что он устраняет accept() методы и полностью отделяет структуру данных от операций, осуществляемых в посетителях. Расширение структуры данных новыми элементами не требует смены посетителей. По умолчанию посетители игнорируют неизвестные типы элементов (см. Определения с pass ключевое слово). Недостатком этого метода является то, что singledispatch Декоратор нельзя использовать напрямую с методами экземпляра, хотя есть способы заставить его работать.

Для Python до версии v3.4 может использоваться модуль мультиметодов, аналогичный оформителю singledispatch. Один из недостатков модуля multimethods состоит в том, что метод посетителя, который применяется к данному элементу структуры данных, выбирается не только на основе типа элемента, но также и в порядке, в котором методы объявлены. Хранение определений методов в правильном порядке может быть обременительным и подверженным ошибкам для структур данных со сложной иерархией наследования.