Comment écrire le motif de visiteur pour arbre de syntaxe abstraite en Python?

Question

Mon collègue m'a suggéré d'écrire un modèle de visiteur pour naviguer dans l'AST. Quelqu'un peut-il me dire plus comment pourrais-je commencer à écrire?

Pour autant que je comprends, chaque nœud AST aurait méthode visit() (?) Qui serait en quelque sorte appelée (où?). Qu'environ conclut ma compréhension.

Pour tout simplifier, supposons que je nœuds Root, Expression, Number, Op et l'arbre ressemble à ceci:

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

Quelqu'un peut-il penser à la façon dont le modèle des visiteurs visiterait cet arbre pour produire une sortie:

 5 + 2 * 444

Merci, Boda Cydo.

Answer 1

Wikipédia a un grand aperçu de comment le modèle des visiteurs fonctionne, bien que la mise en œuvre de l'échantillon qu'ils utilisent est en Java. Vous pouvez facilement port à Python, cependant, non?

En gros, vous voulez mettre en place un mécanisme pour le double envoi accept() (pas une méthode de visit()). La méthode prend comme argument, un objet de visiteur. Dans la mise en œuvre de cette méthode de accept(), vous appelez une méthode de visit() de l'objet visiteur (il y aura un pour chaque type de nœud AST, en Java, vous utilisez la surcharge des paramètres, en Python Je suppose que vous pouvez utiliser différentes méthodes de visit_*()). Le visiteur correct sera alors envoyé avec le type de nœud correct comme argument.

Answer 2

Voir les docs pour ast.NodeVisitor, par exemple peut-être une possibilité brute:

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,

Bien sûr, cela ne produit pas entre parenthèses, même en cas de besoin, etc., donc il y a effectivement plus de travail, mais il est un début; -).

Answer 3

Les deux variantes pour mettre en œuvre le modèle de visiteur en Python que je rencontrais sur Internet le plus souvent:

• One-to-one traduction de l'exemple du livre de modèles Desigh par Gamma et al.
• Utilisation de modules supplémentaires pour double expédition

Traduction Exemple du Patterns Desigh Livre

Cette variante utilise des méthodes de accept() dans les classes de structure de données et méthodes de visit_Type() correspondantes dans les visiteurs.

La structure de données

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

Imprimer Infix visiteur

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

Imprimer Prefix visiteur

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)

Sortie

5 + 2 * 444.1
+ 5 * 2 444.1

Utilisation de modules supplémentaires

Cette variante utilise @functools.singledispatch() décorateur (disponible dans le Python standard Library depuis Python v3.4).

La structure de données

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

Imprimer Infix visiteur

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

Imprimer Prefix visiteur

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

Sortie

5 + 2 * 444.1
+ 5 * 2 444.1

La raison pour laquelle je préfère cette variante est qu'elle élimine les méthodes de accept() et sépare complètement la structure de données des opérations mises en œuvre dans les visiteurs. L'extension de la structure de données avec de nouveaux éléments ne nécessite pas de modifier les visiteurs. Les visiteurs ignorent les types d'éléments inconnus par défaut (voir les définitions avec le mot-clé pass). Un inconvénient de cette méthode est que décorateur singledispatch ne peut pas être utilisée avec des méthodes d'instance directement, bien que, il y a des façons de le faire fonctionner .

Pour Python avant le module v3.4 Multiméthodes peut être utilisé similaire au décorateur singledispatch. Un inconvénient du module Multiméthodes est que le procédé de visiteur qui est appliqué à un élément de structure de données donnée est choisi non seulement en fonction du type de l'élément, mais aussi sur l'ordre dans lequel les méthodes sont déclarées. Garder les définitions de méthode dans le bon ordre peut être fastidieux et source d'erreurs pour les structures de données avec une hiérarchie d'héritage complexe.