Expression tree - Bonnes pratiques ?

Bonjour,


J'essaye de générer des expressions sous forme d'arbre. J'ai donc crée plusieurs classes abstraites :

Expression -> Operator -> UnaryOperator -> Exp2, Incr, ..
Expression -> Operator -> BinaryOperator -> Add, Sub, ..
Expression -> Operand -> Variable, Constant, ..

De ces classes découlent des opérateurs unaires/binaires et des variables/constantes (comme vous pouvez vous en douter :))

Je me pose deux questions :

1) Comment créer de manière efficace un arbre d'expression ? Pour l'instant, j'ai une autre classe ExpressionNode qui retient à chaque fois l'Expression qui lui appartient et la ou les ExpressionNode qui la précède. J'ai cependant l'impression que ce n'est pas très efficace puisque je dois du coup instancier deux classes pour chaque noeud de mon arbre...

2) Je dois pouvoir évaluer mon Expression pour plusieurs valeurs de plusieurs variables. En gros, si e est mon expression, e.eval(1, 2, 3) devra me retourner le résultat de mon expression avec x = 1, y = 2 et z =3.
Je ne vois pas comment faire ça proprement.
Soit je fais une fonction eval qui prends 3 arguments pour chacune de mes expressions et qui ne fais que de les propager jusqu'à tomber sur une variable (mais je trouve ça vraiment pas propre du tout),
Soit je passe les 3 arguments à mes ExpressionNode pour les propager jusqu'aux feuilles et je fais une fonction eval pour chaque Expression qui prend un ou deux double en fonction de si c'est un UnaryOperator ou un BinaryOperator.
Mais je ne trouve aucune de ces deux méthodes très élégantes.


Voila, si vous avez de bons conseils à me donner, n'hésitez pas !

Un grand merci d'avance et bonne journée :-)

Mon conseil : utiliser Boost.Proto qui sert précisément à cela. :)

Je ne peux malheureusement pas :(


C'est vraiment pour la résolution de l'Expression que je galère. Je dois passer à coté de quelque chose d'évident ... mais je ne vois vraiment pas quoi :s.
La manière élégante de le faire serait de commencer par les feuilles de l'arbre, mais ce n'est pas possible dans mon cas.

Merci quand meme pour la réponse :-)

Citation:

---

Envoyé par sikin1989

Je ne peux malheureusement pas :(

---

Pour quelle raison ? :?

C'est un projet .. Le but est d'implémenter et pas d'utiliser les choses existantes :-)

Ton arbre d'expression doit être construit à la compilation ou à l'execution ? Dit autrement tu veux faire :

Code:

---

1 2 3

auto expr = num(1)+var(1); eval(expr,1);

---

ou

Code:

---

1 2 3

auto expr = load("file"); eval(expr,1);

---

?

A l'exécution..

Je pense que tu devrais te pencher sur les mécanismes servant à réaliser des variant (ceux de boost ou de Qt), c'est à dire type erasure, et sur les visiteurs qu'on peut leur associer (comme boost::static_visitor).

A partir de ca tu pourras définir ton arbre comme étant :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

struct Node; struct Leaf;   struct Node { T _value; std::vector<Variant<Node,Leaf> > _leafs; };   struct Leaf { T _value; };   struct VisitorEval { R operator(Node&) { /*...*/ } R operator(Leaf&) { /*...*/ } };   //utilisation Node n; //on remplit n //comme le ferais boost::spirit par exemple //tu lis ton expression et selon ta grammaire //tu remplis les vectors des noeuds VisitorEval v(x,y,z); v(n);

---

(C'est juste l'idée, il peut y avoir plusieurs types de feuilles et le Visitor doit faire le bon boulot).

Citation:

---

Envoyé par sikin1989

1) Comment créer de manière efficace un arbre d'expression ? Pour l'instant, j'ai une autre classe ExpressionNode qui retient à chaque fois l'Expression qui lui appartient et la ou les ExpressionNode qui la précède. J'ai cependant l'impression que ce n'est pas très efficace puisque je dois du coup instancier deux classes pour chaque noeud de mon arbre...

---

Désolé, je ne comprends pas cette question... Qu'est-ce qu'expression par rapport à ExpressionNode, et quelles sont les deux classes que tu dois instancier ?

Citation:

---

Envoyé par sikin1989

2) Je dois pouvoir évaluer mon Expression pour plusieurs valeurs de plusieurs variables. En gros, si e est mon expression, e.eval(1, 2, 3) devra me retourner le résultat de mon expression avec x = 1, y = 2 et z =3.
Je ne vois pas comment faire ça proprement.
Soit je fais une fonction eval qui prends 3 arguments pour chacune de mes expressions et qui ne fais que de les propager jusqu'à tomber sur une variable (mais je trouve ça vraiment pas propre du tout),

---

Moi non plus. Le plus gros problème que je vois est ce 3. A mon avis, il serait intéressant qu'au niveau de l'expression elle même, tu possède une liste des variables mentionnées, afin de t'assurer au moment de l'évaluation qu'il y a bien correspondance. Ensuite, je verrais bien la fonction eval prendre un seul paramètre représentant le contexte d'évaluation et qui regroupe l'ensemble des valeurs des différentes variables concernées (par exemple dans une map).

Salut,

Pour ne pas devoir créer une instance de Node / Leaf et une instance de Expression, tu pourrais (car je crois que c'est ce que tu demandes ;)) envisager de gérer ton arbre syntaxique de manière intrusive: Les opérateurs binaires hériteraient directement de Node, les opérateurs unaires et les opérandes héritant directement de Leaf.

Au final, cela pourrait ressembler à quelque chose comme

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

class Tree { public: Tree(Tree * parent = NULL): parent_(parent), : siblin_(NULL){} virtual ~Tree(){ delete siblin_;} Tree * parent() {return parent_;} size_t level() const{return parent_ ? parent_->level() +1 : 0;} virtual Tree * next(){return siblin_;}   virtual void evaluate( Evaluator const &) = 0; virtual void evaluate( Evaluator const & ) const = 0; private: Tree * parent_; Tree * siblin_; }; class Leaf : public Tree { public: Leaf (Tree * parent_):Tree(parent_){} }; class Node : public Tree { public: Node (Tree * parent_):Tree(parent), child_(NULL){} virtual ~Node(){delete child_;} private: Tree * child_; }; class Constant : public Leaf { /*...*/ }; class Variable : public Leaf { /*... */ }; class BinaryOperator : public Node { /* ... */ };   /* ... */

---

(hé oui, un arbre binaire peut, parfaitement, suffire pour représenter un arbre syntaxique ;))

Cependant, je reste mitigé vis à vis de cette solution d'un point de vue conceptuel car cela implique que tes classes réelles se retrouvent systématiquement avec deux responsabilités :

1. Celle de représenter l'information syntaxique et...
2. Celle de représenter l'arbre syntaxique en lui-même :aie:

Pourquoi ne pas avoir un AST classique ?
Style :

Code:

---

1 2 3 4 5 6 7 8 9 10

class Expression { // Membres herites si necessaire }; struct Plus : Expression { std::unique_ptr<Expression> lhs, rhs; }; struct Minus : Expression { std::unique_ptr<Expression> lhs, rhs; }; // ...

---

(J'ai fait quelque chose de similaire à ça ici, c'est un peu moins moche que cette méthode, mais ça date. Et puis, je ne sais même plus vraiment ce que j'avais codé dedans, donc ... !)

Pour évaluer l'arbre, on peut, au choix, soit coller une méthode virtuelle dans chaque noeud (il me semble que c'est ce que j'avais fait) ou, si il le fonctionnement est trop complexe dans ce cas (multiples méthodes virtuelles à ajouter), alors le DP visitor comme proposé par Flob80 peut être utile.

Merci beaucoup pour vos réponses !

Je suis un peu occupé pour l'instant, mais je regarde plus précisément à tout ça demain !
Je reviendrai poster si j'ai encore des questions par rapport à ce que vous m'avez donné. Mais à priori, ça semble tout à fait répondre à mes besoins. (j'espère ne pas parler trop vite :-))

Merci beaucoup !