Université Blaise Pascal - UFR ST - Master-1 informatique - TP de Compilation

PROJET NOTÉ 2017
Sujet à réaliser en binômes (groupes de 2 étudiants). L'évaluation prendra en compte la réalisation du projet ainsi que sa présentation orale.

REALISER UNE CALCULATRICE LOGIQUE
(analyseur lexico-syntaxique avec Flex & Yacc)

Le cahier des charges du projet de base est le suivant.

1. Dans le projet de base, une ligne saisie par l'utilisateur correspond soit à une expression  booléenne à évaluer soit à une instruction d'affectation d'une variable.
—
2. Chaque "token" (unité lexicale) correspond à un unique caractère :
  1. 1 pour vrai et 0 pour faux,
  2. Opérateurs :  − (NON unaire),  *  (ET),  +  (OU),  #  (ou exclusif(2) : XOR),  >  (IMPLIQUE),  =  (EQUIVALENT),
    (2) Rappel : A=B correspond à (A>B)*(B>A), A>B correspond à (−A)+B, et A#B correspond à ((-A)*B)+(A+(-B)).
  3. 26 variables de A à Z, sans distinction entre majuscules et minuscules ('A' et 'a' correspondent à une même variable),
  4. @ est le symbole d'affectation (l'instruction X@1, par exemple, placera la valeur 1 dans la variable X, l'instruction X@expression placera dans X le résultat (0 ou 1) de l'évaluation de l'expression).
  5. Les parenthèses ouvrante et fermante.
—
3. Les chiffres de 2 à 9 sont aussi interprétés comme vrai. Les autres caractères, qui ne correspondent pas à un "token", sont interprétés comme faux.
—
4. Les expressions n'auront pas besoin d'être totalement parenthésées. On pourra utiliser comme ordre décroissant de priorité sur les opérateurs logiques : NON (unaire), ET, OU (XOR au même niveau), IMPLIQUE, EQUIVALENT. Associativité à gauche pour tous les opérateurs binaires.

Ce projet de base sera amélioré – au choix – dans une ou plusieurs des directions suivantes.
N.B. Toutes les directions d'amélioration ne sont pas forcément intercompatibles, il faudra veiller à maintenir la cohérence globale du projet. Toute fonctionnalité déficiente sera comptée négativement : ne réaliser que ce que vous maitrisez !

5. Une affectation correspond à une expression ; par exemple X@0+Y@1 affecte 1 à Y, affecte 0+1 à X, et est interprétée comme 1 (1=0+1) en tant qu'expression − associativité à droite donc pour @.
—
6. Robustesse, souplesse et convivialité : un analyseur robuste accepte n'importe quelle entrée de l'utilisateur sans défaillir ; un analyseur souple gère les erreurs sans perturber le fonctionnement global du programme, il peut même corriger certaines erreurs ; un analyseur convivial sait en plus indiquer (succinctement) à l'utilisateur quelle erreur il a commise.
Exemple 6.a. : Toute suite de caractères inconnus est interprétée comme un faux.
Exemple 6.b. : L'analyseur autorise les opérateurs ET implicites : 10G et GH sont respectivement interprétés comme 1*0*G et G*H.
Exemple 6.c. : En cas d'erreur, l'analyseur indique les variables qui ont été modifiées par la ligne de commande erronée, soit automatiquement, soit grâce à une instruction spécifique pouvant être saisie après la commande.
Exemple 6.d. : Ajout d'un token '?' correspondant à une valeur de vérité inconnue et qui sera contenue par défaut dans les variables non encore utilisées.
N.B. il faudra établir les tables de vérité pour cet opérande : 1+?=1, 0+?=?, etc.
—
7. Les noms des variables sont de la forme [A-Za-z]+ (la gestion de la table des symboles sera faite − autant que possible − au niveau lexical.
Exemple 7.a. : seule la première lettre du motif est prise en compte, il y a toujours 26 variables.
Exemple 7.b. : la taille du nom des variables n'est pas limité, mais leur nombre l'est (comment gérer un dépassement de capacité en nombre de variables ?).
Exemple 7.c. : (plus difficile) ni la taille ni le nombre des variables n'est limité ; pour retrouver plus rapidement les variables, on utilise une table de hachage basée sur la première lettre de la variable.
—
8. L'analyseur accepte l'écriture "A−B" pour "A+(−B)".
—
9. L'analyseur accepte l'affectation combinée à une opération (X+@1 pour X@X+1).
—
10. (* plus difficile) L'analyseur syntaxique fonctionne aussi en mode vectoriel : par exemple [0,1,1]*[1,0,1]=[0*1,1*0,1*1]=[0,0,1] ; on pourra choisir d'écrire [011] pour [0,1,1].
On peut choisir en plus d'opérer sur des vecteurs de taille différente en ajoutant des 0 à la fin du vecteur le plus court : [0,1,1]*[1,0,1,1,0,1] sera calculé comme [0,1,1,0,0,0]*[1,0,1,1,0,1].
—
11. (* plus difficile) L'interpréteur construit à la demande l'arbre syntaxique associé à une ligne de calcul. Une commande spéciale basculera donc entre un mode calcul du résultat et un mode affichage de l'arbre.