DEUG MIAS 2ième année
MIO2-2
Option Informatique Approfondie
Projet Réécriture -- Cahier des charges
1998-99

Pascal Manoury








§ I  --  La bibliothèque
On constitue une bibliothèques de types, fonctions et procédures nécessaires àla réalisation du projet. Cette bibliothèque comporte trois unités décrites ci-dessous.










1.  Termes
 
(* Types pour les termes et listes de termes *)
Type TSym        (* Categorie de symboles *)
     Term        (* Termes *) 
     TList       (* Listes de termes *)

(* -- Constructeurs : *)

(* Termes - constantes *)
Function TCst(c : String) : Term;
(* Termes - variables *)
Function TVar(x : String) : Term;
(* Termes - application de fonction *)
Function TFun(f : String; ts : TList) : Term;

(* Listes de termes *)
Function ConsTList(t:Term; ts:TList) : TList;

(* -- Accesseurs *)
(* Termes : nom du symbole *)
Function nameOf(t : Term) : String;
(* Termes : type de symbole *)
Function symOf(t : Term) : TSym;
(* Termes : arguments *)
Function argsOf(t : Term) : TList;
 
(* Listes de termes : tete de liste *)
Function hdTList(ts:TList) : Term;
(* Listes de termes : queue de liste *)
Function tlTList(ts:TList) : TList;

(* -- Utilitaires *)
(* Egalite structurelle (termes et listes de termes *)
Function eqT(t:Term; u:Term) : Boolean;
Function itEqT(ts:TList; us:TList) : Boolean;

(* Affichage *)
Procedure writeTerm(t:Term);
Procedure writeArgs(ts:TList);

(* Duplication *)
Function cloneT(t : Term) : Term;
Function itCloneT(ts : TList) : TList;

(* Desallosation *)
Procedure disposeT(Var t : Term);
Procedure itDisposeT(Var ts :  TList);

(* Affectation *)
Procedure setTerm(Var t : Term; u : Term);





2.  Substitutions
 
Type STPair          (* Couples : String*Term *)
     LSubsts         (* Listes d'association : (String * Term) List *)
     

(* -- Constructeurs : *)
(* Couples *)
Function newSTPair(x : String; t : Term) : STPair;

(* Liste d'association *)
Function ConsLSubst(xt:STPair; xts:LSubst) : LSubst;

(* -- Accesseurs *)
(* Couples : 1iere projection *)
Function keyOf(xt : STPair) : String;
(* Couples : 2nde projection *)
Function valOf(xt :  STPair) : Term;

(* Listes d'association : tete de liste *)
Function hdLSubst(xts:LSubst) : STPair;
(* Listes d'association : queue de liste *)
Function tlLSubst(xts:LSubst) : LSubst;

(* -- Utilitaires *)
(* Listes d'association : affichage *)
Procedure writeLSubst(xts:LSubst);

(* Listes d'association : desallocation *)
Procedure disposeLSubst(Var xts:LSubst);

(* Listes d'association : acces *)
Function assocLSubst(x:String; xts:LSubst) : Term;

(* Listes d'association : ajout (avec controle de compatibilite) *)
Procedure addLSubst(Var clash:boolean; Var xts:LSubst; xt:STPair);

(* -- Substitution (application de la) *)
Procedure subst(t:Term; xts:LSubst);
Procedure itSubst(ts:TList; xts:LSubst);





3.  Filtrage
 
(* -- Filtrage de 1ier niveau : 't' filtre 'u' ? *)
Procedure match(t:Term; u:Term; Var s:LSubst; Var clash:Boolean);

(* -- Filtrage en profondeur :                           *)
(* 'u' contient un sous terme 'v' tel que 't' filtre 'v' *)
Procedure tryMatch(t : Term; u:Term; Var s:LSubst; Var clash:boolean; Var v:Term);
Procedure itTryMatch(t : Term; us:TList; Var s:LSubst; Var clash:boolean; Var v:Term);
§ II  --  Noyau pour la réécriture
Types, fonctions et procedures nécessaires àla réalisation des systèmes de réécriture. 
Type RRule               (* Couples : (Term * Term) *)
     RRList              (* Systeme de regles : (Term * Term) List *)

(* -- Constructeurs *)
(* Couples *)
Function newRRule(l:Term; r:Term) : RRule;

(* Systeme de regles *)
Function ConsRRList(rr:RRule; rrs:RRList) : RRList;

(* -- Accesseurs *)
(* Couples : 1iere projection *)
Function leftOf(rr : RRule) : Term;
(* Couples : 2nde projection *)
Function rightOf(rr : RRule) : Term;

(* Systeme de regles : tete de liste*)
Function hdRRList(rrs:RRList) : RRule;
(* Systeme de regles : queue de liste*)

(* -- Utilitaire *)
(* Systeme de regles : affichage *)
Procedure writeRRList(rrs:RRList);

Nous suggérons, pour avoir plus de souplesse, d'ajouter une procédure rewrite1 effectuant (si possible) une étape de réécriture du terme t avec la règle rr 
Procedure rewrite1(Var t:Term; rr : RRule);
§ III  --  Aller plus loin
Il s'agit maintenant d'utiliser le matériel développépour réaliser une petite application maintant en oeuvre le processus de r'eécriture. Nous vous demanderons de
  1. définir une interface permettant de
    1. saisir (ou lire dans un fichier) un systéme de réécriture
    2. saisir un terme (ou lire dans un fichier) àréécrire
  2. intégrer l'utilisation de la réécriture dans un des deux systèmes suivants :
    1. programme de simplification de contraintes arithmétiques
    2. simplification d'expression arithmétiques traitant la commutativitéet l'associativité
    3. procédure de décision du calcul des propositions
Remarques :

- la réalisation de l'interface est obligatoire

- on pourra se contenter de la seule réalisation de l'interface accompagnée d'un jeu de tests conséquents

-


Nous donnons dans les paragraphes suivants quelques pistes << pour aller plus loin >>










4.  Interface, analyse syntaxique
 Le noyau de l'interface consiste àpasser de l'écriture mathématique usuelle des termes àleur représentation en machine sous forme d'arbres (type Term) L'écriture usuelle des termes est appelée leur syntaxe concrète, leur représentation arborescente est appelée syntaxe abstraite Pour passer de l'une àl'autre, on met en oeuvre des outils d'analyse syntaxique


On réalisera donc, in fine, une fonction 
Function parseT(s:String) : Term;
Sur la base de cette fonction, on pourra réaliser deux fonctions supplémentaires : 
Function parseRR(s:String) : RRule;
Function parseRS(s:String) : RRList;
Le première analyse une r`egle de réécriture, la seconde, un ensemble de règles (ie : un système de réécriture)







(4.a)  Analyse lexicale
L'analyse lexicale est le préalable de l'analyse syntaxique. Elle consiste àdécouper le flot (ou la chaîne) de caractères en unités syntaxiques (ou lexèmes) Dans notre cas, les unités syntaxiques sont au nombre de quatre : les identificateurs (pour noms de variables, constantes et fonction) la parenthèse ouvrante, la virgule et la parenthèse fermante.


On réalisera une procedure 
Procedure nextToken(Var s:String, Var tok:Token);
oùs est la chaîne àtraiter et tok le résultat. Cette procédure doit isoler dans s la première unitélexicale. Elle est renvoyée dans l'argument tok et on supprime de s les caractères correspondant àcette unitélexicale.
La définition du type tt Token est laissée àvotre sagacité; pensez que dans le cas des identificateurs, il faut savoir récupérer la chaîne correspondant au nom du symbole.


Exemple : si s est la chaîne 'f1(a, f2(x))', aprés appel de nextToken(s, tok), la variable s contient '(a, f2(x))' et la variable tok contient les informations : on a un symbole de fonction; son nom est 'f1'







(4.b)  Algorithme
Voici une description d'un algorithme possible d'analyse syntaxique. On définit deux fonctions qui retournent soit un terme, soit une liste de termes. On suppose connue la procédure Lire-lexème(s, tok)
  Analyser-terme (s) :
    Tant que s est non vide, faire :
      Lire-lex`eme(s, tok);
      Si tok est une constante c alors
        Retourner la constante c.
      Si tok est une variable x alors
        Retourner variable x.
      Si tok est une fonction f alors
        Lire-lex`eme(s, tok);
        Si tok n'est pas une ouvrante : Erreur
        sinon
          Soit t1, .., tn = Analyser-arguments(s),
            Retourner le terme f(t1, .., tn).
    Fin-tant-que
 
  Analyser-arguments(s) :
    Soit t = Analyser-terme (s),
      Lire-lex`eme(s, tok);
      Si tok est une virgule alors
        Soit t1, .., tn = Analyser-arguments(s),
          Retourner la liste (t, t1, .., tn)
      Si tok est une parenth`ese fermante alors
        Retourner la liste (t)








5.  Applications
 Nous proposons trois applications. Selon les applications, il sera sans doute profitable de ne pas appliquer les règles àl'aveugle et de déterminer une stratégie : par exemple, on peut commencer par un groupe de règles données, puis passer àun autre, puis revenir au groupe 1, etc... Ainsi, il n'est pas nécessaire de reprendre la procédure généraliste rewrite vue en cours. Vous devrez plutôt chercher àdéfinir une stratégie particulière au problème traité.







(5.a)  Simplification de contraintes
Cette première application est une mise en oeuvre de la réécriture pure.


On a un langage de contraintes comportant les opérations arithmétiques usuelles, les six relations d'égalité, inégalité, inférioritéstricte et large, supérioritéstricte et large et le connecteurs logiques : << et >> << ou >> << non >>. On veut ramener toutes les contraintes àune forme restreinte oùl'on a plus que l'égalité, la relation d'inférioritéet les trois connecteurs logiques.
  1. Définir un système de réécriture réalisant la traduction des contraintes
  2. Implanter et donner quelques exemples pertinants.
Remarque : on mettra ici l'accent sur le traitement des relations plutôt que sur la simplification des expressions.







(5.b)  Simplification d'expressions arithmétiques
On se restreint aux seules opérations d'addition et de multiplication avec leur élément neutre. L'idée est d'utiliser au maximum les propriétés de distributivité, d'associativitéet de commutativitépour donner aux expressions arithmétiques la forme particulière d'une somme n-aire de produits n-aires.


Pour utiliser correctement la commutativité, on sort de la réécriture pure en introduisant un ordre sur les symboles. On n'applique alors la commutativitéque si le premier terme est supérieur au second. Il devient alors facile d'utiliser la commutativitésur les sommes et produits n-aires : c'est un tri de la liste des termes (d'une somme) ou des facteurs.


Enfin, on peut encore polluer la réécriture en évaluant les (sous) termes ne comportant que des constantes et des opérations pour les remplacer par la constante représentant leur valeur.

  1. Définissez (sous forme de termes) la somme et le produit n-aires
  2. Définissez un système de règles transformant une expression usuelle (avec somme et produit binaire) en une expression équivalente sous forme de somme de produits n-aires
  3. Implantez, en tenant compte des suggestions d'utilisation de la commutativitéet de l'évaluation des expressions constantes, et donner des exemples




(5.c)  Décision du calcul propositionnel
On considére le langage du calcul des propositions constituédes constante logiques << vrai>> et << faux >> d'un ensemble de variables propositionnelles et des connecteurs << non >> << et >> << ou >> << implique >>


Une formule du calcul des propositions et dite tautologie si et seulement si sa valeur est << vrai >> lorsque l'on remplace alternativement toutes ses variables par la constante << vrai >> puis par la constante << faux >> Il est facile de définir les règles d'évaluation des connecteurs (ie leur table de vérité) par un système de réécriture. Dés lors, on propose la procédure suivante qui permet de déterminer si une formule est tautologique on non.
  Calculer la liste des variables de la formule p;
  Par chaque variable x :
    Remplacer x par << vrai >> dans p;
    Simplifier (on obtient p1);
    Si le r'esultat de la simplification est << faux >>
      La formule n'est pas une tautologie : on sort.
    Sinon,
      Remplacer x par << faux >>;
      Simplifier (on obtient p2);
      Si le r'esultat de la simplification est << faux >>
        La formule n'est pas une tautologie : on sort.
      Sinon,
        Recommencer pour p1 et p2.

  1. Définir un système de réécriture pour l'évaluation des connecteurs propositionneles
  2. Implanter la procédure de décision proposée et donner des exemples comportant des formules qui sont des tautologies et d'autres qui n'en sont pas
This document was translated from LATEX by HEVEA.