Sébastien Ros
Evaluation d’Expressions Mathématiques avec MGrammar
Cet article permet de comprendre comment utiliser le langage Microsoft M Grammar en créant un DSL (Domain Specific Language) textuel pour l’évaluation d’expressions mathématiques.
Par Sébastien Ros publié le 14/12/2008 à 23:48, lu 4315 fois, 6 pages
 3 | Exécution de l’environnement d’édition
Pour lancer Intellipad il faut charger la logique de l’analyseur de grammaire en utilisant la ligne de commande suivante :
"c:\program files\Microsoft Oslo SDK 1.0\bin\Intellipad\ipad.exe" /c:ipad-vs-samples.xaml
Ensuite, il faut ouvrir un fichier de grammaire existant (un fichier .mg) en utilisant la combinaison de touches CTRL + SHIFT + T. L’objectif de ces démarches est de complexifier un peu plus la tâche du développeur sinon cela serait trop facile. Peut être s’agit-il aussi simplement de contraintes de la version CTP actuelle.
L’élément principal dans un fichier de grammaire est la déclaration du nom de celle-ci :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image2.png
 
Un module peut contenir plusieurs langages pour par exemple partager des éléments entre ceux-ci. Ici nous en créant un seul, nommé MCalc.
Pour commencer simplement, nous allons essayer d’analyser un nombre. Ceux-ci sont représentés par la présence d’un ou plusieurs chiffres. Un nombre est un élément terminal de notre grammaire, comme les mots le sont pour les langues parlées. Ces éléments terminaux sont appelés token. La notion de règle de grammaire, est nommée syntax, et représente des règles d’enchaînement et de présence des token.
Le premier token défini est Digit qui décrit comment analyser un chiffre. Les caractères sont notés entre simple cotes, et une plage peut être décrite en utilisant deux points successifs « .. ».
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image3.png
 
Ensuite un nombre entier est défini comme un ou plusieurs chiffres en utilisant le suffixe +. Le token Integer est défini.
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image4.png
 
Finalement, notre langage contient la règle syntaxique principale définie comme contenant un Integer. Voici le langage ainsi créé :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image5.png
 
En tapant « 42 » dans la fenêtre de gauche, celle de droite nous montre le résultat analysé :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image6.png
 
De la même manière on peut définir le tokenNumber décrivant un nombre à virgule flottante. Il doit obligatoirement contenir un point « . » suivi de chiffres. Les chiffres avant le point sont facultatifs. On
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image7.png
 
On peut remarquer l’utilisation du suffixe « ? » pour représenter le fait que Integer peut apparaître zéro ou une fois, c'est-à-dire de manière optionnelle.
Les nombres peuvent parfois être plus complexes s’ils contiennent un exposant comme par exemple « 2e10 ». La règle peut donc être complétée pour gérer ces cas :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image8.png
 
La notion d’expression mathématique peut maintenant être abordée. Une expression est définie en utilisant des opérateurs. L’opération d’addition est par exemple représentée par un nombre (un élément Number dans notre cas) suivi du signe « + » et d’un autre nombre.
La syntaxe de cette expression peut être décrite comme ceci :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image9.png
 
L’analyse de la chaîne « 42.1+2e10 » donne le graphe suivant :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image10.png
 
Pour la simplification de l’évaluation mathématique, le graphe doit être différent. La grammaire Mg nous permet d’interférer sur celui-ci lors de l’analyse syntaxique.
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image11.png
 
Le graphe est alors modifié pour faire apparaître un élément racine de type Plus avec comme enfants les valeurs nommées l et r comme ceci :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image12.png
 
Si vous essayez de saisir les différents éléments syntaxiques séparés par des espaces, le texte saisi n’est plus reconnu. Pour pouvoir espacer chacun des éléments d’une façon plus souple, il faut expliquer à l’analyseur que les espaces doivent être ignorés. Cela est fait en utilisant le mot clé interleave.
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image13.png
 
En précisant l’ensemble de ces caractères, on peut même écrire les expressions sur plusieurs lignes.
Les opérations mathématiques peuvent se succéder les unes derrières les autres, même celles de différents types. Cela paraît évident, mais informatiquement, il faut définir cette logique. En analyse syntaxique il s’agit d’un pattern très courant. Cette récursivité peut être exprimée en redéfinissant la règle d’addition la manière suivante :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image14.png
 
Une addition est alors analysée récursivement, jusqu’aux éléments finaux que sont les nombres. Ceux-ci sont eux-mêmes projeté pour supprimer un niveau inutile dans l’arbre.
L’expression « 1 + 2 + 3 » peut alors être représentée par le graphe suivant.
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image15.png
 
La précédence est le principe mathématique décrivant la priorité d’évaluation des différents opérateurs. Par exemple une opération telle que « 1 + 2 + 3 » peut être évaluée comme « ( 1 + 2 ) + 3 » ou bien «  1 + ( 2 + 3 ) ». Evidemment l’arbre généré sera différent suivant les cas, et cela peut poser un problème pour d’autres opérateurs.
Dans les langages autres que M, cela serait géré en définissant plusieurs règles, et en précisant comment celles-ci s’enchaînes. Avec la grammaire M, ceci s’effectue grâce aux mots clés right ou left.
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image16.png
 
Cette modification permet alors de supprimer l’avertissement généré par Intellipad.
De la même manière l’opérateur de puissance est évalué à droite prioritairement. Il faut donc utiliser le mot clé right pour déclarer cette règle.
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image17.png
 
Ainsi l’expression « 2 ^ 3 ^ 4 » est évaluée comme « 2 ^ ( 3 ^ 4 ) » ceci :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image18.png
 
En plus de la notion de précédence, il faut prendre en compte le fait que des opérateurs différents doivent être évalués dans un ordre particulier en fonction de leur type. Par exemple « 3 + 5 * 2 » doit d’abord évaluer « 5 * 2 » et non pas « 3 + 5 ».
Commençons par déclarer le nouvel opérateur de multiplication, en modifiant la règle contenant l’addition :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image19.png
 
Avec cette règle, si l’expression « 1 + 2 * 3 » est évaluée, le graphe suivant est généré :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image20.png
 
Bien évidemment ceci est faux. Mais Mg propose un moyen simple de préciser qu’une règle d’évaluation et prioritaire sur les autres. Il s’agit du facteur de précédence qui vaut actuellement 1 dans les règles. En affectant 2 pour la règle de multiplication, on précise que c’est cette règle qui doit être évaluée en premier lieu.
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image21.png
 
Le graphe créé est alors correct.
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image22.png
 
Pour forcer l’ordre d’évaluation des parties d’une expression il faut utiliser les parenthèses. Les parenthèses sont le moyen de définir les éléments les plus prioritaires, au même titre que l’évaluation d’une expression multiplicative est plus prioritaires qu’une expression additive. En suivant la même règle que nous avons pu le faire pour les multiplications, nous ajoutons une nouvelle règle prenant une expression entre parenthèses.
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image23.png
 
L’évaluation de « 1 * ( 2 + 3 ) » donne le résultat correct suivant :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image24.png
 
Les opérateurs unaires ne fonctionnent pas en utilisant deux arguments comme l’addition ou la multiplication mais un seul. Ces opérateurs sont aussi les plus prioritaires dans une expression après les parenthèses. L’opérateur unaire utilisé dans les expressions mathématiques est le moins « - » permettant d’inverser le signe d’une autre expression.
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image25.png
 
Ainsi l’expression « 1 * (2 + -3) » est analysée en :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image26.png
 
La grammaire peut être alors complétée pour ajouter l’ensemble des opérateurs mathématiques :
Soustraction
Division
Division entière
La grammaire complète est alors celle-ci :
 
/content/a9c04ba4-5aa7-4c80-b6ec-7400580f78fb/image27.png
 
A ce niveau notre grammaire peut interpréter n’importe quelle opération. Cependant l’utilisation telle qu’elle ne sert strictement à rien. Ceci nécessite l’utilisation d’un outil permettant à une application quelconque d’exploiter la grammaire ainsi définie.
 
» Démarrer une discussion
 
Discussion démarée par zunk86 le 22/05/2012 à 09:07, 1 commentaire(s).