première traversée d'un arbre en utilisant des générateurs en python

Question

Actuellement, je suis en train de programmer un compilateur pour un très petit sous-ensemble de Python en Python. J'ai déjà réussi à construire un arbre de syntaxe mais j'ai eu quelques problèmes avec le codage de la traversée de l'arbre (qui est essentiel pour générer du code). Je vais d'abord aller de pair avec vous montrer mes structures de données:

class AbstractSyntaxTree(object): 
    def __init__(self, startSymbol): 
     self.root = Node(startSymbol, val=None) 
     self.nodes = [self.root] 

    def addNode(self, name, val, parentId): 
     parent = self.nodes[parentId] 
     self.nodes.append(Node(name=name, val=val, parent=parent)) 
     return len(self.nodes)-1 

    def getLastId(self): 
     return len(self.nodes)-1 

    def __iter__(self): 
     for node in self.root: 
      yield node 

C'est ma définition de noeud:

class Node: 
    def __init__(self, name, val, parent=None): 
     self.name = name 
     self.val = val 
     self.parent = parent 
     self.children = [] 

     if parent: 
      parent.children.append(self) 

    def __iter__(self): 
     yield self 
     for child in self.children: 
      for node in child: 
       yield node 

Mon analyseur est un analyseur de descente récursive, où chaque symbole de grammaire est un appel de fonction autres symboles de grammaire. program est mon symbole de début.

def program(self, indentLvl=0): 
    parent = self.synTree.getLastId() 
    if self.smellAndConsume(TOK.EOF, parentId=parent): return 
    self.smellAndConsume(TOK.NEWL, parentId=parent) 
    self.synTree.addNode(name=VAR.statement, val=None, parentId=parent) 
    self.statement() 
    while self.accept and not self.isConsumable(TOK.EOF): 
     self.consume(TOK.NEWL, parentId=parent) 
     self.synTree.addNode(name=VAR.statement, val=None, parentId=parent) 
     self.statement() 
    self.consume(TOK.EOF, parentId=parent) 

Il est maintenant était curieux, si après analyse je serais succesful capable d'imprimer tous mes noeuds dans l'arbre de syntaxe par itérer de la profondeur en utilisant d'abord mon générateur __iter__ défini dans Node et AbstractSyntaxTree. Mais

def test_tree_traversal(): 
    for node in miniPyGrammar.synTree: 
     print(node) 

n'imprime pas tous les nœuds! Quand j'ai débogué mon code, j'ai réalisé que mon noeud racine n'avait pas d'enfants dans sa liste d'enfants, bien que j'appelle addNode avec l'ID des noeuds racine. Est-ce que quelqu'un a une idée de ce qui se passe ici?

Si vous avez besoin de plus d'informations ou de plus d'extraits de code, n'hésitez pas à demander.

edit: je viens de trouver la solution (bien que je trouve toujours bizarre ce qui se passe ici.) Ce code se comporte maintenant comme prévu:

def test_tree_traversal(code): 
    grammar = Grammar() 
    grammar.parse(code) 
    for node in grammar.synTree: 
     print(node) 

def execute_tests(): 
    for name, code in programs.items(): 
     parse_test(name, code) 
     test_tree_traversal(code) 

Avant d'avoir un objet global grammaire et execute_tests appellerais analyser le cette grammaire, après quoi j'ai exécuté test_tree_traversal, qui accède à l'objet grammar-synTree. Bizarrement, entre les appels, la collecte des ordures supprimait certains nœuds de l'AST. Pourquoi je suppose que c'est la collecte des ordures? Parce que le comportement était non déterministe.

edit: c'était le code sujette aux erreurs: notez que la seule différence est que j'instancie un nouvel objet de grammaire avant d'exécuter un test. La grammaire a une méthode'parse 'qui renvoie true si le programme est syntaxiquement correct et construit un AST qui est accessible via Grammar.synTree.

miniPyGrammar = Grammar() 

def parse_test(
    programName: str, 
    programCode: str): 
    success = miniPyGrammar.parse(programCode) 
    if success: 
     print('{} is a valid miniPyProgram :)'.format(programName)) 
    else: 
     print('{} is not a valid miniPyProgram'.format(programName)) 
    print(miniPyGrammar.synTree) 

def tree_traversal(code): 
    for node in miniPyGrammar.synTree: 
     print(node) 

def execute_tests(): 
    for name, code in programs.items(): 
     parse_test(name, code) 
     tree_traversal(code) 

if __name__ == '__main__': 
    execute_tests() 

Answer 1

Plutôt que d'essayer d'itérer sur votre arbre, je recommande d'utiliser le Visitor pattern à la place. Cette approche vous permet de modulariser facilement votre traversée d'arbre de syntaxe abstraite.

Notez qu'avec l'utilisation de cette approche, vous devez créer des classes spécifiques pour chaque type de nœud dans l'arborescence. Par exemple, vous pouvez avoir une classe Operator pour les noeuds d'opérateur, une classe FunctionCall pour les noeuds d'appel de fonction, etc.

Voici un exemple très simple du modèle de vistor pour un AST qui devrait vous aider à démarrer.L'AST est constitué de Operator noeuds pour les opérateurs, et Number noeuds pour les numéros:

class Node: 
    pass 


class Operator(Node): 
    def __init__(self, op, left, right): 
     self.op = op 
     self.left = left 
     self.right = right 


class Number(Node): 
    def __init__(self, value): 
     self.value = value 


class AstWalker: 
    def visit(self, node): 
     name = 'visit_' + node.__class__.__name__ 
     vistor = getattr(self, name, self.missing) 
     vistor(node) 

    def missing(self, node): 
     name = node.__class__.__name__ 
     raise Exception('No visitor method for node type: ' + name) 

    def visit_Operator(self, node): 
     print('operator:', node.op) 
     self.visit(node.left) 
     self.visit(node.right) 

    def visit_Number(self, node): 
     print('number:', node.value) 


# The ast represents the expression: 
# 
# (1 * 5) - (3/5) 
# 
ast = Operator(op='-', 
     left=Operator(op='*', 
        left=Number(1), 
        right=Number(5) 
     ), 

     right=Operator(op='/', 
        left=Number(3), 
        right=Number(5) 
     ) 
) 

walker = AstWalker() 
walker.visit(ast) 

La sortie du code ci-dessus est:

operator: - 
operator: * 
number: 1 
number: 5 
operator:/
number: 3 
number: 5 

La partie intéressante du code ci-dessus est la classe AstWalker. C'est ici que nous mettons en œuvre le modèle. Voici un aperçu rapide. La méthode visit est la viande du code ci-dessus. C'est là que la magie se passe. Pour garder une longue histoire courte, visit prend un argument node. Ce sera un nœud Operator ou un Number. Il prend ensuite le nom de la classe du nœud en utilisant node.__class__.__name__. Comme vous pouvez le voir, j'ai rempli le nom avec visit puisque la méthode de visiteur pour chaque nœud dans l'arbre - visit_Operator et visit_Number ont la visite.

Enfin dans self.visit, j'utilise getattr pour obtenir la bonne méthode de visite de la classe. Si le nœud est Numbergetattr, la méthode visit_Number sera renvoyée. La même chose s'applique à Operator. La méthode visiteur est ensuite appelée et node est transmise.

Si nous constatons que l'objet node transmis n'a pas de méthode de visiteur, nous renvoyons self.missing et l'appelons. self.missing rapports simples quel objet nœud que nous avons rencontré n'a pas une méthode de visiteur.

Comme indiqué ci-dessus, chaque méthode de visiteur prend un argument node. Le nœud actuel était en visite. Dans l'exemple ci-dessus, j'imprime simplement les attributs de chaque node. Il pourrait cependant être facilement modifié pour générer du bytecode.