|
IFT2030 Concepts des langages de programmation Automne 2002 |
TP1: Vers un mini compilateur d'un mini Pascal (MiniPasc)
Cadre généralLe but de ce travail est de vous faire programmer en langage C (ou C++) la réalisation d'un analyseur de codes sources programmés à l'aide d'un sous-ensemble du langage Pascal appelé MiniPasc dans la suite.Un exécutable de ce qui vous est demandé de faire est installé sur
le compte cat /u/dift2030/Ressources/source1.mp | /u/dift2030/Ressources/tp1 -i -v La grammaire de MiniPasc est décrite sous forme BNF comme
suit (une version ascii de cette grammaire est disponible ici), l'axiome de départ est (vous l'avez
deviné):
Les éléments en vert sont les symboles du métalangage:
Les éléments en caractères gras sont les mots réservés du langage (que votre analyseur lexical aura à charge de reconnaître); les éléments en rouge indiquent des unités (tokens) reconnues par l'analyseur lexical que vous devez écrire:
Enfin une règle de la forme: Cahier des chargesLa réalisation d'un compilateur est un travail incrémental, nous vous proposons de procéder dans l'ordre suivant (le détail de chaque étape suit):
La suite de cette section vous donne les spécifications de chacune des étapes. Étape 1 - Analyse lexicaleVotre analyseur a à charge d'éliminer les commentaires qui en MiniPasc commencent par une accolade ouvrante{ ,
peuvent courir sur plusieurs lignes, et se terminent par une accolade
fermante } . Il doit également être insensible à
l'indentation. En particulier, le résultat de l'analyse
lexicale doit être le même pour les fichiers sources source1.mp et source2.mp qui sont deux versions différemment
indentées du même code source.
Il est possible que le code source à analyser soit incorrect du
point de vue lexical, auquel cas votre analyseur doit l'indiquer à
l'utilisateur et sortir proprement (pas de coredump). C'est par
exemple le cas pour le code source source3.mp
(un commentaire est ouvert mais pas fermé), ainsi que pour le code source4.mp (le symbole À titre indicatif, voici la trace produite par un analyseur lexical qui reconnaît les lexèmes de MiniPasc pour les quatre fichiers sources mentionnés; les codes des tokens et leurs noms vous appartiennent, en revanche, les lexèmes retournés par cet analyseur sont ceux que votre analyseur devrait également retourner.
Étape 2 - Analyse syntaxiqueCette étape à pour but de vérifier qu'une suite de tokens (tels qu'identifiés par votre analyseur lexical), est bien conforme à la grammaire BNF de MiniPasc. Si tel n'est pas le cas, votre programme s'arrête à la première erreur rencontrée en indiquant le numéro de ligne dans le fichier source où le problème est rencontré (ou du moins détecté), suivi d'un court message spécifiant l'erreur.À titre indicatif, voici la trace d'exécution de cette étape 2 pour un ensemble de fichiers:
Voici d'autres sources qui possèdent tous des erreurs de syntaxe: [source6.mp], [source7.mp], [source8.mp], [source9.mp], [source10.mp] Notez que l'étape 2 ne présuppose aucun traitement sémantique. Par exemple le source numéro 5 passe le test de syntaxe alors qu'il contient de nombreuses erreurs qui sont indiquées à même le code et expliquées dans la section qui suit. Étape 3 - Vérification sémantiqueLe but de cette étape est de détecter certaines incohérences sémantiques (c'est à dire de sens) dans le code source analysé. Les incohérences que votre programme doit rechercher sont décrites ci-après. Votre analyseur sémantique doit s'arrêter dès la première erreur rencontrée en indiquant à l'utilisateur le numéro de ligne où l'erreur a été détectée et la nature de l'erreur.Voici la liste des erreurs sémantiques que votre programme doit détecter:
Il existe d'autres types d'incohérence qu'il faudrait gérer pour réaliser un véritable compilateur, il ne vous est pas demandé de les détecter (rien ne vous empêche cependant d'y travailler). Exemple de vérification envisageable mais absolument pas demandée: vérification de la correspondance des types entre les paramètres d'appels d'une méthode et les paramètres formels de cette méthode. Attention Vous pourriez être tenté(e) d'écrire un analyseur qui recherche ces erreurs de manière ad-hoc avec un succès possible pour certaines erreurs vu que MiniPasc est un langage très simple. Par exemple vous pourriez à l'aide de Table des symbolesUne table de symboles est une structure dans laquelle sont rangés tous les identificateurs rencontrés lors de l'analyse syntaxique. Chaque identificateur est accompagné de sa nature (ici variable, tableau ou procedure), ainsi que d'informations spécifiques (borne inférieure et supérieure pour un tableau, nombre de paramètres formels pour une procédure).D'autres informations sont normalement stockées dans la table de symboles, comme par exemple le type de chaque identificateur (integer, float, etc.), mais il ne vous est pas demandé dans ce travail de faire de la vérificaion de type. Le plus gros du travail de l'étape 3 consiste à alimenter cette table avec les identificateurs rencontrés dans les déclarations et à vérifier lorsqu'un identificateur est utilisé dans une instruction si cela est fait de manière cohérente. Plus à ce sujet en démonstration 4 (commencez déjà par coder les deux premières étapes). ConsignesUne partie de la correction sera automatisée (la compilation ainsi que l'exécution de votre programme sur un ensemble de codes sources), aussi devez-vous respecter les consignes qui suivent.L'interface de votre programmeVous devez remettre un seul programme exécutable tp1 qui accomplit toutes les étapes que vous avez codées. Voici le synopsis (descriptif) que doit suivre votre programme. Tester l'exécutable mis à votre disposition pour plus de détails.
Notez qu'un exemple de code permettant de gérer proprement la ligne de commande vous a été remis dans un solutionnaire. Codes d'erreurLorsque votre programme détecte une erreur (lexicale, syntaxique ou sémantique), il doit s'arrêter après avoir affiché un message adéquat. Vous devez sortir à l'aide de l'appelexit(x) où
x est un entier qui vaut -2 en cas d'erreur lexicale
(étape 1), -4 en cas d'erreur syntaxique (étape 2) et -8 en cas
d'erreur sémantique (étape 3). Lorsque le code est correctement
analysé, votre programme doit retourner 0 (return 0; en dernière
instruction de la méthode main ).
CompilationVotre travail sera compilé sur les machines linux du département. Il vous appartient de vérifier que votre code fonctionne sur cet environnement. Vous devez fournir un fichier Makefile qui sera utilisé pour compiler votre travail (cela facilitera également votre travail). Pour simplifier à l'extrème, prenons un exemple (vos démonstrateurs vous en diront plus sur les makefiles en démonstration):J'ai réalisé ce TP à l'aide des 4 fichiers C++ suivants:
g++ -o tp1 tp1.cc lex.cc sem.cc syn.ccJe peux également mettre cette ligne dans un fichier de nom Makefile et taper à la place la commande:
make (nous utiliserons make pour compiler
votre programme).
Travail en binômeVous devez travailler en groupe de deux. Le nom et le login de chaque personne doivent être reportés en entête de chaque source remis !.Vous devez remettre un seul travail par binôme (vérifiez que le nom
et le login des deux personnes apparaît dans toutes les entêtes de vos
codes). N'oubliez pas de remettre également le fichier
Procédure de remise, date limite, barêmeLa commande de remise est la suivante (prenez garde de remettre sous pift2030 et pas dift2030):remise pift2030 TP1 mesSources MakefilePour ceux qui ne sont pas familiés avec la commande remise, tapez man remise dans un terminal.
Vous avez jusqu'à lundi 21 octobre 2002 midi pour remettre votre travail. Le barême est en partie indiqué dans le sujet. Vous êtes notés sur 15 points, 4 points sont donnés (étape 1), 8 points sont très accessibles (étape 2); des 3 points restants (étape 3), certains sont faciles à prendre (ex: vérifier que les bornes d'un tableau sont dans le bon ordre). N'oubliez pas que la notation dépend toujours de critères comme: la qualité (pertinence) du code, son organisation (structuration), sa lisibilité (commentaires, indentation, etc.), sa justesse (le code est-il conforme aux consignes ?). De plus, des consignes vous sont spécifiées, le fait de ne pas les suivre est forcément pénalisant. Prenez le temps de lire ce sujet, et n'oubliez pas que vos démonstrateurs et moi-même sommes là pour toutes vos questions (évitez cependant avec moi celles du genre: "euh, c'est trop long le sujet, vous ne pouvez pas me faire un résumé ?"). |