Salut, j´ai l´intention de me lancer dans un petit projet qui pourrait s´apparenter à une sorte de calculatrice, et j´aimerai savoir si vous ne connaitriez pas un tutoriel expliquant comment fonctionne l´analyse syntaxique ( car c´est je crois ce dont j´ai besoin )
En clair je voudrais pouvoir entrer une expression du genre :

1+(3*4-2)

Et que mon programme l´évalue en tenant bien sur compte de la préséance des opérateurs qui la compose.

Non c´est pas l´analyse lexicale, mais disons l´évaluation d´expressions

J avais fait un prog comme ca en C, en licence, je t enverrai le code si tu veux, mais il est sale.
L idee est simple : tu geres ca dans un ARBRE BINAIRE :

chaque noeud est un signe +-*/
et chaque feuille est un nombre ( ou un inconnu genre x si tu veux aller plus loin)
le bordel c est pour les nombres negatifs : mais astuce :
-5 < => 0-5 ce qui vire l exception...

Pour construire l arbres, lit de gauche a droite : il te fait une fonction qui soit capable de reconnaitre si le caractere sur lequel tu es est une parenthese, un signe ou un nombre...
Si c est un nombre, tu break
si c est une parenthese, tu crees un nouveau fils...
Etc etc...

tu vois le principe ?

Ouai merci JYY, je vais faire un essai

http://www710.univ-lyon1.fr/~ameyer/teaching/l3-algo/tp/tp6_l3algo.html

Ca donne des pistes de réflexion sur le sujet.

Je travaille avec de la logique combinatoire, donc c´est encore plus simple

Le plus simple c´est de faire ca avec une grammaire.
Tu peux chercher des infos sur les grammaires LL1, comment on construit une table d´analyse...etc
Apres cherches ds google traduction dirigee par la syntaxe / attributs herites, synthetises..etc

En general on trouve toujours l´arithmetique de base dans les exemples de cours.

1ers liens sur google :
http://fastnet.univ-brest.fr/~gire/COURS/COMPIL_IUP/node37.html

http://fastnet.univ-brest.fr/~gire/COURS/COMPIL_IUP/node60.html

ça doit etre chaud a faire!

i_am_the_law > Grammaire ? Pour des expression type mathématique ? La solution de JYY me semble plus adaptée, mais j´ai pas encore fini.

neimos_007 > Avec un arbre binaire ca ddevient tout de suite beaucoup plus simple

Dans les langages de programmations les expressions mathematiques sont reconnues avec une grammaire.
L´avantage c´est que tu peux facilement rajouter des choses. Par ex pour rajouter les fonctions ( sin(..) ln(..)) si tu as deja la grammaire des expressions arithmetiques, c´est tres facile. Tu rajoues 2-3 regles et ca roule tout seul.

ya ce tuto qui est vraiment très bon : http://www.dil.univ-mrs.fr/~garreta/Polys/PolyCompil.pdf

et j´en connaissais un qui était carrément excellent, mais je n´arrive pas à la retrouver, il expliquait comment passé d´une notation infixé ( la notation normale pour les math) à une notation postfixé ( ce qui estplus simple pour l´interprétation) donc exactement ce qu´il te faut.

je l´avais trouvé en faisant une recherche sur le RPN, bon, si qqn retrouve ça, ça serait parfait pour ici.

I am the law te propose la solution grammaire qui est tres bonne : elle generalise tout, les compilateurs marchent par analyse avec de la grammaire d expression.
La solution que je te propose n est ni plus ni moins qu une grammaire ( assez) simplifiee dans le cas des expressions regulieres, sans l etre vraiment, mais il y a la notion d arbre et de recursivite

sinon le TP sur lequel tu te bases, lol !
http://www710.univ-lyon1.fr
C est la que j ai fait mes etudes ! ! ( avec I am the law)
Le TP dont j ai la source est presque le meme, puisqu en 2 ans, ca a un peu change mais bon.

PS perso pour I am the law : Comment vas tu I am the law ? Quand est ce que tu remontes sur Lyon qu on aille se faire un mac do ?

Vi ta methode c´est un peu du bidouillage, est-ce qu´on cree rajoute un fils a droite a gauche, ou en tant que pere...etc
Avec une grammaire c´est plus intuitif je trouve. On se prend moins la tete avec l´ordre des operations, le bon parenthesage..etc

JYY> D´ici une semaine ou deux, t´es rentre toi? t´as fini de bronzer? ; )

Je regarderai tout ca ce week-end

Bon j´ai déjà un petit bout de programme qui me construit un arbre à partir d´une expression entrée, mais j´aimerai savoir à présent quelle est la meilleure manière de procéder afin d´évaluer/calculer la dite exprssion contenue dans l´arbre.
J´ai pensé à 2 manières de procéder :

A l´aide d´une fonction récursive à laquelle je passe la racine de l´arbre puis qui se charge de s´appeler elle même jusqu´à ce qu´elle parvienne aux feuilles : cela fonctionne très bien, mais dès que l´arbre est trop volumineux, ca plante : problème de mémoire lié à la récursivité.

Ou alors j´ai eu l´idée d´un truc que je n´ai pas encore testé mais qui m´a l´air pas mal : associer à chaque noeud une variable " niveau" qui renferme sa " hauteur" au sein de l´arbre : le noeud principal/racine a ainsi le niveau 0, les noeuds principaux de l´arbre fils gauche et de l´arbre fils droit 1, etc...
Et évaluer chaque expression noeud en commencant par celles qui occupent les niveaux les plus hauts dans l´arbre jusqu´aux plus basses.
Cette dernière m´a l´air assez chouette et je vais m´y mettre, mais j´aurais aimé savoir s´il n´existait pas par hasard une " méthode ultime"

Ehm, sinon concernant la préséance des opérateurs, quelle est la manière la plus élégante de procéder ( ex : * prime sur l´addition/est exécutée avant)
J´utilise un truc pas très propre qui est obligé de lire 2 fois l´expression...

tu dit que l´arbre plante s´il est trop gros, ça me semble étrange.

car dans un cas comme ça, il n´y aura pas plus d´appel sur la pile que de niveaudans l´arbre, et même une très grosse expression, ferait peut-être une centaine d´opérateur ( et encore, c´est vraiment bcp), donc on pourrait dire quelque chose comme 10 ou peut-être 50 au maximum de niveau dans l´arbre ( par niveau, j´appel le le plus long chemin entre la racine et l´une des feuille). de là à faire planter un PC moderne ça m´étonerait.

t´es sur qu´il y a pas un bug dans ta récursivité ?

tu fait du camL chez toi ( en prépa je veux dire) ? ou du pascal ?

Pour le plantage : certes il ne survient qu´avec de très grosses expresions, mais pour tester le générateur d´arbre, j´avais écrit un générateur d´exprssion aléatoires
Et dès qu´on a une très grosse expression ( ce qui n´arrive pr)

[je continue] ( ce qui n´arrive pratiquement jamais dans la réalité) ca plante lorsqu´il faut générer les appels récursifs de la fonction de résolution afin d´obtenir la valeur de l´expression.

Je pourrais me contenter d´un truc itératif, maisje veux un truc beau

Et sinon dès janvier je ferais du CAML si je prends option infos

up