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

Ответ 1

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

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

Ответ 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,

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

Ответ 3

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

• Индивидуальный перевод примера из книги шаблонов Desigh от Gamma и др.
• Использование дополнительных модулей для двойной отправки

Переведенный пример из книги шаблонов Desigh

Этот вариант использует методы 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')))

Посетитель Infix Print

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

Префикс Print Visitor

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

Test

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() decorator (доступен в стандартной библиотеке 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')))

Посетитель Infix Print

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

Префикс Print Visitor

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

Test

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

Выход

5 + 2 * 444.1
+ 5 * 2 444.1

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

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