Comment écrire un motif de visiteur pour un arbre de syntaxe abstraite en C #?

Je dois écrire un modèle de visiteur pour naviguer dans l’AST. Quelqu’un peut-il me dire plus comment je commencerais à l’écrire? Pour autant que je sache, chaque nœud dans AST aurait une méthode visit () (?) Qui serait en quelque sorte appelée (de quel endroit?). Cela conclut ma compréhension. Pour tout simplifier, supposons que j’ai les nœuds Root, Expression, Number, Op et que l’arborescence ressemble à ceci:

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

    Motif visiteur est un motif de conception qui vous permet d’implémenter des opérations arbitraires (implémentées en tant que visiteurs) sur l’arbre d’parsing (par exemple, Vérification du type) sans avoir à modifier l’implémentation des nœuds de l’arbre d’parsing.

    Il peut être implémenté de la manière suivante (j’utilise un pseudocode):

    Tout d’abord, vous devez définir la classe de base des nœuds de l’arborescence que tous les nœuds doivent implémenter.

     abstract class VisitableNode { abstract void accept( Visitor v ); } 

    La seule méthode que les classes de noeud doivent implémenter est la méthode accept.

    Ensuite, vous devez définir la classe de base d’un nœud visiteur de votre arbre d’parsing.

     abstract class Visitor { abstract void visit( Root rootNode ); abstract void visit( Op opNode ); abstract void visit( Number number ); } 

    Notez que la classe de base du visiteur est faite pour votre arbre d’parsing uniquement et doit avoir une méthode de visite pour chaque type de nœud que vous définissez dans votre arbre d’parsing.

    Ensuite, vous devez laisser votre implémentation de classes de nœud étendre la classe VisitableNode de la manière suivante:

     class Root : VisitableNode { [...] void accept( Visitor v ) { v.visit(this); } } class Op : VisitableNode { [...] void accept( Visitor v ) { v.visit(this); } } class Number : VisitableNode { [...] void accept( Visitor v ) { v.visit(this); } } 

    Maintenant, vous avez une structure d’arbre d’parsing qui ne devrait pas changer et vous êtes libre d’implémenter autant de visiteurs (opérations) que vous le souhaitez.

    Pour effectuer la vérification de type, vous devez stocker un type dans la classe Number avec votre valeur ou disposer d’une classe Number pour chaque type pris en charge: NumberFloat, NumberInteger, NumberDouble, etc.

    À titre d’exemple, supposons que vous disposiez d’un moyen d’inférer le type statique de la valeur à partir de votre classe Number.

    Je vais également supposer que vous pouvez accéder aux enfants du noeud par la méthode getChild (int childIndex).

    Enfin, je vais utiliser une classe Type qui représente sortingvialement un type statique que vous avez l’intention de prendre en charge (comme Float, Integer, etc …).

     class TypeCheckVisitor : Visitor { // Field used to save resulting type of a visit Type resultType; void visit( Root rootNode ) { rootNode.getChild(0).accept( this ); } void visit( Op opNode ) { opNode.getChild(0).accept( this ); Type type1 = resultType; opNode.getChild(1).accept( this ); Type type2 = resultType; // Type check if( !type1.isCompatible( type2 ) ){ // Produce type error } // Saves the return type of this OP (ex. Int + Int would return Int) resultType = typeTableLookup( opNode.getOperator(), type1, type2 ); } void visit( Number number ) { // Saves the type of this number as result resultType = number.getType(); } } 

    Ensuite, vous implémenterez probablement la classe Type en tant qu’énumération de la manière suivante:

     enum Type { Double, Float, Integer; boolean isCompatible(Type type1, Type type2){ // Lookup some type table to determine types compatibility } } 

    Enfin, il vous suffit d’implémenter vos tables de types et vos tables d’opérateurs.

    EDIT: lors de la récursion de visites, il est en fait correct de se reproduire à l’aide de la méthode accept des noeuds sur lesquels vous souhaitez faire une récurrence.

    En ce qui concerne l’utilisation, vous pouvez effectuer une vérification de type sur le nœud racine de l’arbre d’parsing (et déterminer simultanément le type de l’expression) en:

     TypeCheckVisitor v = new TypeCheckVisitor(); rootNode.accept( v ); print( "Root type is: " + v.resultType ); 

    Vous pouvez également vérifier de la même manière un nœud arbitraire de l’arbre d’parsing différent de la racine.