Compléments d'information






Je me propose d'ajouter dans cette page, des informations et des réponses aux questions qui m'ont été posées relativement au projet de programmation d'intégration formelle. J'indiquerais par mail et en tête de page les ajouts ou modifications successives. Pour l'instant, la page est crée le 17 mars.

1   Analyse Syntaxique

L'objet de ce projet n'est pas l'ecriture de l'analyseur syntaxique, mais ce dernier est relativement indispensable. Voici donc quelques indications sur comment en implanter un de manière (à mon avis) aussi simple que possible.

Ce qui suit est inspiré du TD3 de Luc Maranget.

Vous pouvez également vous inspirer du code du corrigé de son TD-9, en particulier pour l'analyse lexicale.

1.1   Analyse lexicale

Au début il n'y a même pas de verbe.

On part d'une suite de caractère (soit une chaîne de caractère -ou string, soit d'un flux -ou stream). L'analyse lexicale consiste a reconnaître les mots (ou lexème), et à transformer l'input brut en suite de lexèmes.

A priori, vous avez besoin des lexèmes sin, cos, (, ), +, *, -, x, etc.

1.2   shift et reduce

Il faut ensuite faire une analyse syntaxique. C'est-à-dire transformer la suite de lexèmes en arbre syntaxique.

On parcourt la suite de lexèmes. A chaque étape, on a le choix entre deux opérations, shift et reduce. L'idée est que l'on suppose l'expression analysée suffisemment parenthésée pour éviter de se poser des questions par rapport aux précédences entre opérations. On sait alors que l'on doit faire reduce lorsque l'on tombe sur une parenthèse fermante, si l'on tombe sur un opérateur sans argument (comme x) ou bien s'il reste un opérateur (comme * ou sin) en tête de stackL après un reduce. Par exemple pour
sin(2*x+3)
on partira de
sin((2*x)+3)
et le parsing se déroule alors comme suit. Rappellez-vous bien que stackL est une liste de lexème, alors que stackT est une liste d'expressions déja analysées.
prochaine lexème stackL stackT opération
sin [] [] s
( [sin] [] s
( [sin; (] [] s
2 [sin; (; (] [] r
* [sin; ( ; ( ] [2] s
x [sin; ( ; (; * ] [2] r
) [sin; ( ;; *] [2; x] r
+ [sin; ( ] [2*x] s
3 [sin; ( ; + ] [2*x] r
) [sin; ( ; + ] [2*x; 3] r
) [sin; ( ] [(2*x)+3] r
  [] [sin((2*x)+3)]  

On peut encore simplifier l'analyse en supposant qu'il y ait encore plus de parenthèses. On ne fait alors qu'un seul reduce à la fois, et seulement quand on ferme une parenthèse. Mais il faudrait alors partir d'une expression comme
(sin(((2)*(x))+(3))).

1.3   Ajouter des parenthèses pour les précédences

Une astuce pour gérer les précédences entre opérations est de parcourir une fois l'expression après l'analyse lexicale et avant l'analyse syntaxique en rajoutant des parenthèses. On fait comme ceci: On peut ensuite utiliser l'algo précédant sans danger.

1.4   L'opposé et la soustraction

Il reste un point délicat. Le signe ``-'' peut être utilisé soit pour désigner la soustraction, soit pour désigner l'opposé. Dans le premier cas, il s'agit d'un opérateur binaire, dans le second cas, d'un opérateur unaire.

En fait, ``-'' doit être compris comme un opérateur unaire si et seulement si Une solution simple consiste donc à parcourir l'expression après l'analyse lexicale, et à remplacer les ``-'' qui correspondent au cas unaire par un autre lexème comme ``--''. On a alors complètement désambiguée l'expression pour permettre une analyse lexicale facile.

2   A propos de la commutativité

Cette question a été posée par Florin Cremenescu. Il fait remarquer que a+b+a ne se réécrit pas naturellement en 2*a (à supposer que vous vouliez considérer des facteurs entiers). En fait le problème se pose aussi pour simplifier a+b-a par exemple.

Comme je l'indiquais dans le sujet, il est difficile de traiter l'associativité-commutativité. Je suggère donc de ne pas trop passer de temps là-dessus, surtout dans un premier temps (et on ne vous en voudra donc pas beaucoup si votre programme ``rate'' quelques simplifications).

Cela-dit, on peut essayer de se débrouiller à peu près avec des moyens simples. Ce qui suit est une suggestion pour ratrapper un peu le coup. Mais encore une fois, traiter ce problème dans toute sa généralité est difficile; sachez ne pas être trop difficiles ou trop exigeant avec vous-même.

Un premier point est d'orienter l'associativité, par exemple les expressions ci-dessus peuvent être toutes lues comme a+(b+a), et plus géneralement comme a+(b+(c+(d+...))) par exemple.

Ensuite, on peut essayer de retrouver les termes identiques dans une somme en orientant la régle de commutativité. Vous pouvez pour cela définir une fonction de ``mesure'' (en fait plutôt une fonction de hash ou hachage, voir le poly) h sur vos expressions. Une fois que vos expressions sont normalisées par rapport aux règles usuelles, on peut alors appliquer des transformations comme
a+(b+c) ® b+(a+c)    si h(a)>h(b)
ce qui revient à ordonner les termes de la somme par rapport à la valeur que leur attribue h. Les membres idientiques de la somme doivent alors se retrouver ensembles.

Il y a sans doute d'autres possibilités. Mais encore une fois, faites attention à ne pas passer trop de temps sur ce genre de problèmes, au moins au début du travail.

3   A propos de l'unification (10 avril)

Je rajoute quelques remarques à propos de l'unification; j'en porfite pour vous donner un peu de vocabulaire et répondre à une question de Franck Guo et Mathieu Perrin.

L'opération d'unification se fait toujours pour un langage donné. C'est-à-dire un certain nombre de symboles de fonctions. Dans notre cas, ces symboles sont sin, cos, +, 0, etc. Chacun de ces symboles à une arité; c'est le nombre de ses arguments. Par exemple, + est d'arité 2.

Remarquez que les constantes sont des fonctions d'arité 0: 0 et 1 sont des constantes d'arité 0.

Pour faire de l'unification, on travaille sur des expressions construites à partir des symboles de fonctions et de variables. Une variable est une expression (encore) inderterminée. L'unification consiste essentiellement à résoudre une équation entre deux expressions avec des variables.

Le résultat de l'opération d'unification est soit: L'unification échoue pour sin+yº cos.

Pour sin+yºsin+cos, elle réussit, et retourne [y¬ cos].

Pour sin+yº x+cos, elle réussit et retourne [y¬cos; x¬ sin].

Pour x+xºsin+sin, elle réussit et retourne [x¬ sin].

Pour x+xºsin+cos, elle échoue.

On peut remarquer que certains de ces exemples sont ``plus simples'' que d'autres. Plus exactement, voici deux cas particuliers:


définition 1   On appelle filtrage (ou pattern-matching) l'opération d'unification dans le cas ou seul un des deux membres de l'équation contient des variables.


Ci-dessus, seule la troisième équation ne rentre pas dans le cas particulier du filtrage.


définition 2   On appelle motif (ou pattern) un membre d'une équation, c'est-à-dire une exporession qui peut contenir des variables.



définition 3   Un motif linéaire est un motif où chaque variable n'apparait au plus qu'une fois.
 On remarque ici que seul le motif x+x des deux dernières équations n'est pas linéaire.

L'unification est un tout petit peu plus facile à programmer dans le cas linéaire. Un exemple de régle non linéaire est typiquement:
a+a |® 2*a
ou plus généralement:
a+n*a |® (n+1)*a
n*a+ m*a |® (n+m)*a .
Si vous voulez effectivement programmer de telles règles, notez qu'alors le ``+'' dans n+1 ou n+m désigne vraiment l'opération d'addition et pas le symbole de fonction correspondant.

This document was translated from LATEX by HEVEA.