Discussion :

[sikin1989]

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

[cob59]

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

[sikin1989]

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

[cob59]

Je ne peux malheureusement pas

Pour quelle raison ?

[sikin1989]

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

[Flob90]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

ou

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

?

[JolyLoic]

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 ?

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

[koala01]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Ekleog]

Pourquoi ne pas avoir un AST classique ?
Style :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[sikin1989]

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 !