Projet TP compilation 2016

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

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.

Au plus tard la veille de l'exposé oral à midi (mardi 15 mars 2016 à 12h00, envoyer dans la rubrique Travaux du support de TP sur l'ENT le compte-rendu qui sera un diaporama PDF en deux parties :
1. Présentation orale (ce qui a été réalisé / choix faits / exemples bien choisis d'exécution / limites du programme) – au plus 5 diapositives en tout,
2. Code source Lex / Yacc / éventuel code additionnel – a priori au plus trois diapositives équivalentes à trois pages A4 en Arial 12pt ;
L'exposé oral (4 minutes) aura lieu à la dernière séance de TP (mercredi 16 mars 2016 à partir de 13h30) selon un planning qui sera affiché sur l'ENT ; cet exposé sera immédiatement suivi de questions du jury et d'une démonstration sur machine (4 minutes) – prévoir de laisser votre projet sur votre compte SCI et prévoir des exemples d'exécution bien choisis.

REALISER UN ANALYSEUR DE GRAMMAIRE
(analyseur lexico-syntaxique avec Lex/Flex & Yacc/Bison)

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

Dans le projet de base, une ligne saisie par l'utilisateur correspond soit à règle de grammaire soit à une instruction d'affichage ou de suppression.
Chaque "token" (unité lexicale) correspond à un ou plusieurs caractères :
- (#1a) Chaque lettre minuscule est un symbole terminal,
- (#1b) Chaque lettre majuscule est un symbole non-terminal, le symbole de départ de la grammaire sera par défaut S.
- (#1c) Le symbole ε est représenté par &,
- (#1d) Opérateur : -> pour une règle de grammaire,
- (#2a) Instruction ?? pour l'affichage de la grammaire (chaque règle sous la forme X->α avec α∈N∪T),
  (#2b) Instruction -- pour l'effacement de la grammaire,
- (#3) Les autres caractères, qui ne correspondent pas à un "token", sont ignorés.
(#4) Une ligne d'instruction mal formée sera ignorée.
(#5) Les règles de grammaire seront conservées dans un tableau à deux dimensions, la première dimension correspondant à la partie gauche de la règle (26 valeurs de 'A' à 'Z') et la deuxième dimension au premier caractère de la partie droite (53 valeurs donc de 'A' à 'Z' et de 'a' à 'z', plus '&'). Une case du tableau contiendra la partie droite de la règle : par exemple, pour la règle S→aAbZe, on stockera dans la case [S,a] du tableau la valeur "aAbZe".
Une règle impossible à ajouter sera ignorée.

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 et peuvent changer les choix de base ; il faudra donc 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 !

(#1e) Le token | permet de construire plusieurs règles ayant même partie gauche.
(#1f) Le symbole de départ est par défaut la partie gauche de la première règle de grammaire saisie, il peut être changée pour tout autre non-terminal X avec l'instruction depart=X et demandé par l'instruction depart.
(#9) Les instructions ne sont pas forcément sur des lignes successives.
(#2c) L'instruction ?X affiche toutes les règles ayant X pour partie gauche, (#2d) l'instruction -X supprime toutes les règles ayant X pour partie gauche.
(#10 à #19) 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 #10 : Eviter les messages inutiles ou trop verbeux.
Exemple #11 : Toute suite de caractères inconnus est interprétée comme ε.
Exemple #12 : Ajout d'un token -! qui supprime la dernière règle saisie.
Exemple #13 : En cas d'erreur en milieu de ligne, l'analyseur indique ce qui a été accepté et/ou refusé dans la ligne et donne à l'utilisateur la possibilité de supprimer les effets de la ligne.
Exemple #14 : Si la saisie d'une règle contredit la factorisation de la grammaire, le choix est laissé à l'utilisateur de choisir parmi les règles en conflit.
Exemple #15 : si l'utilisateur choisit un symbole de départ qui n'est pas le membre gauche d'une règle déjà saisie, la demande est refusée (alternative : l'analyseur demande une règle commençant par ce symbole).
(#20) Le stockage des règles se fera suivant le principe des tables de hachage : les règles ayant même partie droite sont stockées dans une liste chainée, et il y aura une liste chainée par membre gauche de règle (càd par terminal). Cette structure respectera l'ordre de saisie des règles.
N.B. le code de la structure correspondante et des fonctions associées pourra être placé dans un fichier séparé.
(#21) L'analyseur accepte l'opérateur -?> pour n'ajouter la règle que si elle maintient la factorisation.
(plus difficile) (#22a) Après chaque ajout de règle, l'analyseur met à jour toutes les valeurs de FIRST nécessaires. La commande first affiche toutes les valeurs de FIRST.
(plus difficile) (#22b) Mêmes questions pour follow.
(plus difficile et long) (#30) La commande table affiche la table d'analyse LL(1) de la grammaire ou indique le premier conflit rencontré empêchant la création d'une table LL.
(trop difficile) (#40) En cas de conflit, l'analyseur donne le choix entre plusieurs solutions, la solution qu'il juge la meilleure étant placée en premier.
(trop difficile et trop long) (#50) La commande analyse bascule dans un mode analyseur où la table est utilisée pour vérifier la reconnaissance d'un mot par la grammaire. La commande grammaire revient en mode grammaire.