[C] Calcul Formel

Bonjour,
J'aimerais faire un programme qui puisse faire du calcul formel (limité à l'addition et multiplication).
Pour se faire, j'ai créé une sorte d'arbre binaire en liste chainée:

Code:

---

1 2 3 4 5 6 7 8

typedef struct noeud { char symbole; int ID; struct noeud *pere; struct noeud *droite; struct noeud *gauche; } NOEUD, *pt_noeud;

---

Ainsi, la racine représente l'operateur (* ou +) et les 2 feuilles les variables (a et b par exemple); ID sert d'identifiant unique (1=gauche,2=racine,3=droite).
Jusqu'ici, çà fonctionne bien, mais je me heurte à un probleme dans le cas de formules plus complexes: "(a+b)*c".

Le forum C m'a conseillé sur celui-ci en me disant qu'il fallait:

Citation:

---

que tu écrives une grammaire simplifiée des expressions arithmétiques, ensuite un analyseur syntaxique qui construira l'arbre associé à ton expression.

---

Le problème, c'est que je vois pas du tout comment faire une telle chose.

Merci d'avance

Mes cours de compilation remontent à assez loin, mais je pense que tu peux essayer qqchose comme grammaire :

Code:

---

1 2 3 4

Expr = Terme | Terme*Expr Term = ExprSimple | ExprSimple + Term ExprSimple = N | (Expr)

---

N est un entier, un nombre à virgule...
* est une multiplication, une division
+ est une addition, une soustraction
C'est pour le respect des priorités


Ensuite au point du vue algo :

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

proc Expr Terme si caractère lu = * alors avancer Expr fsi fin   proc Term ExprSimple si caractère lu = + alors avancer Term fsi fin   proc ExprSimple si caractère lu est un entier alors lire entier sinon si caractère lu est ( alors avancer Expr si caractère lu est ) alors avancer sinon Erreur fsi fsi fin

---

A toi de faire les transformations en arbre dans chaque procédure.


Laly.

Tu as besoin de parser du texte et de l'analyser pour le transformer en arbre binaire. Pour cela, il existe des outils qui s'appellent lex et yacc .... ca te permet de faire une analyse lexical (lex) puis syntaxique(yacc) te ton texte pour construire ton arbre ....

Perso, je n'ai jamais utiliser ces deux outils mais des outils tres proche basé en fait sur le caml ( camllex et camlyacc) .... mais bon, le fonctionnement doit etre le meme.

Dans ton fichier lex, tu decris les differents caracteres que tu peut trouver ( Chiffre + et - en ce qui te concerne ) et ca te renvoie des token (CHIFFRE, PLUS, MULT ). Ensuite, dans ton fichier yacc, tu vas analyser la suite des token suivant une grammaire que tu auras defini. Et a chaque regle tu defini une action a effectue ( c'est la que tu construits ton arbre )....

Bref, si tu veux vraiment faire de la compilation c'est sur cette voie que tu dois aller.

si tu veux, voici un cours de compilation assez interessant ( c'est le cours que j'ai suivi en maitrise :) )

Merci benratti de m'avoir bien orienté, j'ai trouvé également quelque chose; j'ai "plus qu'à" étudier tout çà.

Salut,
après avoir potassé la doc, je vois le principe de la décomposition et etc, mais je vois pas trop comment joindre (eventuellement la librairie "y.tab.h") les algo généraux, et mon programme; en gros, il me manque un exemple concret d'application.

Merci d'avance

Salut,

Un exemple de lexeur/parseur . je n'ai pas les ficheirs là, mais ca doit pouvoir se retrouver en quelques jours au pire ;)

Les codes sont à partir de la page 50.

Attention, dans le parseur, je ne construit pas d'arbre syntaxique si je me souviens bien.

lol ... tu as reussi a glisser la phrase "C'est de la merde" dans ton rapport de stage :) ... le jury a rien dit ??

Citation:

---

Envoyé par benratti

lol ... tu as reussi a glisser la phrase "C'est de la merde" dans ton rapport de stage :) ... le jury a rien dit ??

---

Oups ! Il reste effectivement quelques affichage de debug qui auraient du passer à la trappe... Comme quoi il faut toujorus faire attention quand on reprend un code :D
Pour ce qui est du jury, non ils n'ont rien dit. Ils n'ont pas du lire les codes du rapport ;)

Merci pr cet exemple concret. :lol:

Je pense qu'effectivement c'est LA solution, car recréer un analyseur syntaxique n'a pas tellement d'intérêt...
J'avais un document là-dessus, mais je n'arrive pas à remettre la main dessus, ça permettait de créer une "bibliothèque syntaxique", en gros, un fichier contenant les symboles et leur utilisation, afin de faire un système de plugins (en JAVA)...