Analyse et calcul d'une expression mathématique

Bonjour à tous,

Je suis en train d'apprendre (enfin plutôt "essayer d'apprendre") la théorie de la compilation par moi même :aie:
Je souhaite donc m'entrainer sur un petit langage : les expressions mathématiques avec les opérateurs courants +, -, *, /. Peut-être rajouter par la suite le traitement des fonctions (cos, sin...).


Voici mon "problème" :bug:

J'ai un programme de ce style :

Code:

---

1 2 3 4

a = 1; b = 3*(a+4); print b;

---

D'après les cours et les exemples que j'ai pu trouver sur internet, la "compilation" se déroule en plusieurs étapes (n'hésitez pas à me corriger si nécessaire !) :

1. L'analyse lexicale : dans laquelle on "découpe" le programme en lexèmes.
   Exemple : "a = 1;" devient IDENTIFICATEUR(a) EGAL NOMBRE(1) FIN_EXPRESSION
   
2. L'analyse syntaxique : on vérifie la syntaxe grâce à une grammaire.
   Exemple pour les lexèmes précédents : IDENTIFICATEUR peut-être suivi de EGAL qui peut-être suivi de NOMBRE qui peut-être suivi de FIN_EXPRESSION.
   Dans mon projet, j'utilise une méthode descendante :
   Pour la formule "3+4", j'ai ce fonctionnement :
   
   Code:

   ---

   1 2 3 4 5 6 7 8 9

   expression(); // appelé par le programme principal |- term(); // analyse le premier token NOMBRE(3) |- factor(); |- retourne 3; // token suivant : PLUS, dans la grammaire on attend un nombre ou un identificateur juste après. |- term(); // analyse le token suivant NOMBRE(4) |- factor(); |- retourne 4;

   ---

   On se retrouve ensuite dans expression avec le token FIN sur la pile.
   La grammaire a bien été vérifiée (pour ce projet, j'utilise une méthode descendante vu que construire une méthode ascendante à la main est un peu "ardu").
   
3. L'analyse sémantique : on vérifie la portée des variables, etc...
   Dans mon cas (pour le moment), il n'y a pas de portée de variable. Je ne pense pas avoir besoin de cette étape. Ou peut-être que j'ai loupé quelque chose ?
   
4. Et là, c'est l'étape de la compilation. Mais normalement, je n'en ai pas besoin non plus vu que je fais un "interpréteur".

Voilà ce que j'ai compris...
Je n'ai utilisé que les étapes 1) et 2). Mais vient ensuite le calcul de l'expression...
Et là je ne sais pas trop comment faire :(

Donc moi en tant que programmeur, je me dis : "Tiens si je faisais un arbre pour évaluer simplement mes expressions ?".
Voici un exemple de ce que je veux faire :

Code:

---

1 2 3

= / \ a 1

---

Ou, pour une expression plus complexe "b = 3*(a+4)" :

Code:

---

1 2 3 4 5 6 7

= / \ b * / \ 3 + / \ a 4

---

(Ouaaaaa, l'ascii-art :oops:)

Ensuite après les différentes validations (analyses), je n'ai plus qu'à appeler getValue() sur la racine de l'arbre (ici '='). Cette fonction appelle elle-même getValue() sur ces fils et fait les opérations nécessaires. Lorsqu'on arrive sur une feuille on renvoie juste la valeur du nombre ou de l'identificateur.

Est-ce une bonne manière de procéder de cette façon ?
Existe-t-il une autre méthode pour créer un interpréteur ?

Et voici la question fatidique : Où et comment créer cet arbre ?
Après quelle analyse ? lexicale ? syntaxique ? Où tout à la fin du processus ?


Donc voilà ou j'en suis !
Pour résumer : j'ai extrait les lexèmes et vérifier la grammaire de mon "langage". Mais je ne sais pas comment évaluer (calculer) mon expression.


Merci d'avoir lu jusqu'au bout, je n'ai pas pu faire plus court O_o

Tipoun

Normalement on crée l'arbre de syntaxe abstraite lors de l'analyse syntaxique, puis on lui applique des optimisations avant de soit l'évaluer (dans un interpréteur), soit le traduire dans un autre langage (dans un compilateur).
Il est aussi possible, pour des langages très simples de faire l'interprétation en même temps que l'analyse syntaxique.

--
Jedaï

J'avais exactement le même probléme lorsque j'étais étudiant. Le plus simple est de créer l'arbre en même temps que tu fais l'analyse lexicale et syntaxique.

Ok, merci pour vos réponses !

Alors par exemple pour la formule "3+4" :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

expression(); // appelé par le programme principal { exp1 = |- term(); // analyse le premier token NOMBRE(3) |- factor(); |- retourne 3; op = + exp2 = |- term(); // analyse le token suivant NOMBRE(4) |- factor(); |- retourne 4; retourne exp1 op exp2; }

---

Globalement, c'est de cette manière ?

Bonjour,

en général on part plutôt d'une grammaire.
Pour chaque membre de la grammaire, on crée une méthode/fonction (tout dépend du langage) qui fait les vérifications et crée une partie de l'arbre (ton cas) ou de la pile (compilation).

Désolé pour le retard (je suis sur plusieurs projet en simultané ^^).

Pour la grammaire, je l'ai rédigée de cette façon :

Code:

---

1 2 3 4 5

S -> Expr Expr -> Term { (* | /) Term} Term -> Factor { (+ | -) Factor} Factor -> [-|+] number | identificator | "(" Expr ")"

---

Citation:

---

Pour chaque membre de la grammaire, on crée une méthode/fonction (tout dépend du langage) qui fait les vérifications et crée une partie de l'arbre...

---

Merci, c'est exactement la réponse que je cherchais ^^
Donc, la création de l'arbre s'effectue directement lors de la vérification de la grammaire.

Au début, je pensais qu'il y avait une méthode qui suivait l'analyse grammaticale (et donc complètement séparée) pour créer seulement l'arbre.

Merci à vous !