Le mécanisme d'un logiciel de calcul formel - Page 1

Bonjour @ tous !!!

Pour préparer un dossier sur les logiciels de calcul formel, je dois en expliquer le mécanisme.
Le point de départ est le suivant : un utilisateur saisie une expression mathématique contenant des symboles (opérateurs, fonctions mathématiques, lettres latines ou grecques, ...). Cette expression est de type chaine de caractères et non numérique bien entendu.
L'utilisateur valide sa formule et le logiciel lui retourne un résultat fomel (sous forme réduite ou développée ; conservations des symboles mathématiques tel les fractions, les racines carrés, les exposants, etc. ; les fonctions ...). Ce résultat apparait sous forme de chaine également.
Alors comment à partir d'une chaine de caractère on peut obtenir un résultat.

D'après mes recherches, j'ai trouvé un seul site traitant le fonctionnement d'un logiciel de calcul formel (http://www.studyvox.ups-tlse.fr/mathweb/mathweb_3.html). Certes il explique les grandes lignes mais c'est très flou.
Je comprends que la chaine est sauvegardé dans uen variable. Cette variable est analysée caractère par caractère (de gauche à droite). L’étape suivante consiste à trouver dans la formule : les constantes, les fonctions, les nombres et les opérateurs. La recherche est effectuée en utilisant un pointeur sur la chaîne, puis en analysant successivement les symboles rencontrés, en incrémentant le pointeur.
On place dans une liste les symboles mathématiques comme les opérateurs (+-÷⁄×*( )[ ]{ }) qui permet de séparer la formule mathématique. Quand on
rencontre un symbole mathématique qui ne joue pas le rôle de séparateur, on passe aux caractères suivant jusqu’au prochain séparateur (un opérateur mathématique).
L’expression mathématique est séparée en 3 types :
[*] En nombres entiers ou décimaux
[*] En nom de constantes
[*] En symbole mathématique ou le nom de la fonction suivie par une parenthèse ouvrante.
Par cette convention, il est possible de traiter les formules mathématiques. Par exemple, l’écriture d’une fraction fait intervenir 2 nombres, séparés par l’opérateur slash « / ». Pour effectuer des calculs relationnels, il faut bien reconnaitre les fractions avec leur numérateur et leur dénominateur.
Pour les puissances, il faut choisir une convention pour écrire la puissance d’une expression. On peut convenir un seul symbole de puissante tel que "^" suivi d’un entier.
Une fois que les conventions d’écriture des symboles mathématiques, il faut mettre en place des subroutines qui permettront d’effectuer les calculs numériques et les calculs formels.
Les calculs nécessitent de retrouver les parenthèses imbriquées, les fonctions et les opérateurs qui opèrent sur ces parenthèses, trouver les résultats partiels et les imbriquer pour trouver le résultat final. Ces opérations sont délicates car elles nécessitent de simplifier les résultats partiels et de les normaliser, pour que l’écriture de la formule mathématique soit toujours conforme aux conventions adoptées. Cette simplification nécessite le plus gros des travails en termes de programmation des calculs numériques et formels.

Voilà mais là je ne comprends plus trôt où va ce mécanisme.
Si l'un d'entre vous peux m'expliquer en terme claire et aussi avec des termes informatiques (c'est pour ma culture :P) ou me communiquer des liens WEB qui traite du mécanisme. Je serai ravi.

Pour info, le mécanisme n'est pas uniquement bordé aux logiciels de calcul formel mais ils peuvent concernés des logiciels développés en C/C++/ Pascal objet etc...

En attendant des réponses, je vous souhaite de passer une très bonne journée.
David

renseigne toi sur
-la compilation
-l'analyse lexicale (que tu as décrit)
-l'analyse syntaxique (traduction d'un texte en arbre de symboles, puis utilisation de cet arbre pour simplifier la formule de proche en proche)

Squalyl merci pour ta réponse.
Le fait est que je ne suis pas programmeur même si j'ai vu ça dans les langages C/c++. Ces choses là remontent loin.

Connaitrais-tu des sites qui évoquent ce que tu m'énonces sur l'analyse lexicale et l'analyse syntaxique ?
Merci

google

et c'est pas de la programmation, mais de l'algorithmique

et te mets pas le doigt dans l'oeil, si tu veux étudier ce domaine en pratique, tu vas devoir programmer... sévère!

Si je ne me trompe pas dans les termes :

L'analyse lexicale est relativement simple (le module qui fait cela s'appelle le "lexer"). L'analyse syntaxique, qui est grosso modo l'étape suivante, sert à faire une représentation abstraite des étapes du calcul (le module est appelé "parser"). Cette représentation est un arbre (les noeuds sont les opérateurs, les feuilles des variables et des constantes). L'analyse sémantique se charge ensuite de traiter cet arbre pour calculer le résultat.

1/ T'as pas besoin de savoir programmer pour savoir comment ca marche
2/ cf la reponse de Thibaut, et regarde ce qu'est une grammaire (wikipedia toussa), la representation par arbre c'est qqch de tres naturel, tu fais la mm chose qunad tu decomposes une formule
3/ Ca se trouve generalemnet pas mal des trucs sur le calcul formel... Certaines librairies sont bien documentees (GiNaC si je me rappelle bien a une bonne doc)

Voici un cours très bien fait, qui explique comment fonctionne la transformation en arbre abstrait d'une chaîne : http://sjrd.ftp-developpez.com/tutoriels/compilation/analyseurs-syntaxiques.pdf

En fait, c'est assez sympa à faire.
par exemple tu as:
32*5+b/c-sqrt(474)

Tu parses la chaine de caractère pour construire les tokens.
En gros, ca permet d'avoir des "paquets" comme suit:

[32] [*] [5] [+] [b] [/] [c] [-] [sqrt] [(] [474] [)]

et ensuite, avec ces paquets, tu construits l'arbre de l'expression en tenant compte de la priorité des opérateurs:

             +-<sqrt >-(
             |         +-<474 >
      +-<- >-|
      |      |      +-<c >
      |      +-</ >-|
      |             +-<b >
-<+ >-|
      |      +-<5 >
      +-<* >-|
             +-<32 >

Il te reste "plus qu'à" bidouiller cet arbre. Genre quand tu vois une branche

             +-<sqrt >-(
             |         +-<4 >

tu remplaces par

             +-<2 >
             |         

Là j'ai utilisé le parser d'ETP-Basic Compiler, que tu peux regarder aussi quand j'aurai publié les sources, en mettant #define _DEBUGARBRES dans verisyn.cpp

Ca y est c'est open-source now: http://code.google.com/p/etpbasiccompiler/
il faut avoir un client svn pour chopper le code, et tu regardes le fichier dont je t'ai parlé, dans: bool VeriSyn::VerifyExpression, je construit l'arbre a partir des tokens.

Enfin, je ne suis pas sûr que ton code (presque) sans commentaires, avec scanner et parseur bidouillés (pas de Flex ni Bison) soit vraiment le meilleur exemple pour lui apprendre.

justement si, mon code est largement plus compréhensible que du code généré horrible par un outil générique.

On ne lit évidemment pas le code généré , mais la description pour cet outil, qui est beaucoup plus lisible qu'un code maison.

mais par contre le résultat... ça ne vaut pas un parseur fait à la main ^^ (enfin *correctement* fait à la main, je n'ai pas regardé le code d'onur donc autant ne pas trop m'avancer ^^)

Zephyr (./13) :
mais par contre le résultat... ça ne vaut pas un parseur fait à la main ^^ (enfin *correctement* fait à la main, je n'ai pas regardé le code d'onur donc autant ne pas trop m'avancer ^^)

entièrement d'accord

Je pense que Flex et Bison sont utiles lorsqu'on n'arrive pas à faire le parseur à la main. Et donc, pour parser des expressions mathématiques, je n'en vois pas l'intérêt. (Le parseur de PrettyPrint est fait à la main, bien sûr )

pour faire un lexer, antlr est vraiment sympa
my $0.02

Non mais les troll de KK voilà quoi..
Mon parser n'est pas un bidouillage, il suffit de regarder. (c'est la version vb6 qui était du bidouillage)

mais qui était de la même qualité. Quand on prend la peine de faire une grammaire LL(1) on n'a pas besoin de yacc, et encore moins de flex quand on sait trouver les tokens à la main. C'est loin d'être du bidouillage.

Je me souviens au projet compil, on avait utilisé lex et yacc justement (toi aussi squalyl je suppose), le truc était incapable de dire où était l'erreur de syntax (y) (à moins de réecrire la grammaire en LL1 justement je crois)

Bison est capable de te dire "syntax error before `foo'". Bien sûr, si ta ligne ressemble à foo+foo*foo-foo*foo foo-foo+foo, trouver l'erreur (les 2 foo qui se suivent) avec juste ça ne sera pas simple.

bison n'est pas capable de générer une grammaire parsable en regardant seulement un token a l'avance.

si tu arranges ta grammaire pour qu'elle le soit, alors il devient inutile d'utiliser bison.

Non. Bison fait du LALR(1), les parseurs maison courants (recursive descent) font du LL(1). Le LALR(1) est plus puissant, en particulier il n'a pas le problème de la récurrence à gauche qui plante le parseur.

Enfin bon, le but c'est de lui expliquer comment on fait un truc de calcul symbolique, j'espere que c'est plus clair maintenant.

Une grammaire LL(1) peut être organisée de manière à se passer de la récurrence gauche

un analyseur LALR a besoin d'une pile de tokens, ce qui est inutile en LL(1)

on verra vite l'intéret quand il y aura un compilateur on calc. oui, ça c'est un vapor, mais quand elle se condensera, elle sera contente d'avoir un analyseur maison!

KK.
C'est quand meme bien pratique Bison/Yacc. Le code genere est inchiable, y'a des warnings a la compil etc. mais pour parser une grammer relativement complexe, c'est tres bien.
Y'a aussi boost::spirit qui est bien

Ceci dit, dans ce cas précis, on n'a pas une grammaire complexe, on a des expressions :s Donc je prefererais que le monsieur n'ait pas de warning dans tous les sens et qu'il comprenne ce qu'il fait. Maintenant s'il veut faire un compilo c++, on peut lui proposer les outils, oui.

nEUrOO (./25) :
Y'a aussi boost::spirit qui est bien

Beurk! L'abus de l'operator overloading pour représenter l'EBNF en C++. Il est beaucoup plus plus pratique d'avoir un vrai générateur.

onur (./26) :
Ceci dit, dans ce cas précis, on n'a pas une grammaire complexe, on a des expressions :s

J'ai déjà fait 2 parseurs d'expressions avec Yacc/Bison (légèrement différents parce que c'était pour 2 projets différents), ils étaient tous les deux plus simples et plus lisibles que ce que tu nous as pondu là (et je ne parle pas de ton tokéniseur ).

On n'a pas la même définition de "lisible" alors.

C'est quoi qui te dérange dans le tokéniseur? Ceci dit, le projet est open-source, tu peux porter tes améliorations plutôt que troller sans fondement.

Magical42 doit avoir le cerveau en train de bouillir ! ^^