Discussion :

[Paniez]

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 :

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

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:

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

[lalystar]

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

Code :

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

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 :

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

[benratti]

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 )

[Paniez]

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

[Paniez]

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

[gangsoleil]

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.

[benratti]

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

[gangsoleil]

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
Pour ce qui est du jury, non ils n'ont rien dit. Ils n'ont pas du lire les codes du rapport

[Paniez]

Merci pr cet exemple concret.

[progfou]

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