CSC 4508 - Traduction: TP noté 2014 Corrigé
0 - Consignes
Rendre sur la plate-forme Moodle, une archive nom.tar.gz (ou .tgz) contenant uniquement
les fichiers utiles. C'est-à-dire :
- les spécifications *.flex, *.bison
- le ou les fichiers makefile
- les éventuels fichiers *.c pour le code principal ou complémentaire de l'analyseur.
- des fichiers d'exemples ou de test (*.data)
- un fichier README.txt pour les explications et les commentaires éventuels.
Par contre :
- pas de binaire (a.out,..)
- pas de backup de l'éditeur (foo~, #bar...)
- pas de fichiers intermédiaires (lex.yy.c, gram.tab.h ....).
Le TP comprend 3 exercices totalement indépendants et de difficultés différentes.
On utilisera des directories différents pour chaque exercice.
1 - Analyse syntaxique d'expressions booléennes
(source Michel Meynard)
L'objectif de cet exercice est d'écrire une calculette capable de reconnaître et
d'évaluer des expressions logique d'ordre 0.
De manière similaire aux expressions arithmétiques, les expressions logiques d'ordre 0 sont construites à partir des composants suivants :
- Constantes : "0" ou "false" ou "faux" et "1" ou "true" ou "vrai".
- Opérateurs binaires : conjonction "&" ou "et" ou "and", disjonction "|" ou "or" ou "ou", implication "=>", équivalence "<=>", et le OU exclusif "^".
- Opérateur unaire : négation "!" ou "not" ou "non".
- Parenthèses : "(" et ")" .
Les expressions logiques sont évaluées de gauche à droite. L'ordre de priorité des opérateurs est : {"|", "=>", "<=>", "^"} << "&" << "!". Les associativités droites ou gauches des opérateurs sont à préciser.
Pour la lisibilité des expressions, on ajoutera :
- Ecriture ligne à ligne : une expression est écrite sur une même ligne et on a au plus une expression par ligne.
- Blancs : les espaces ou les tabulations sont possibles et sans effet.
- Commentaires : tout texte commençant par "#" et se terminant à la fin de la même ligne est sans effet.
0 | 1 # == VRAI
( vrai | 0 ) & false # == FAUX
1 | ( 0 & faux) # == VRAI
vrai | 0 & false # == VRAI si priorités correctes
faux => vrai # == VRAI; NB A=>B == Non A ou B
faux <=> vrai # == FAUX
t = ( 1 ^ 0 ) & not 0 # Affectation variable t (a VRAI)
0 | t # == VRAI car t==VRAI
t & ! t | 1 # == VRAI
( 0 | (1 & 1 ) # erreur syntaxique
0 <= 1 # erreur lexicale
t & u # erreur execution : variable u non initialisee
u = t ^ u # idem
Travail demandé
- Ecrire un analyseur syntaxique qui évalue (imprime VRAI ou FAUX) des expressions logiques d'ordre 0 écrites ligne à ligne.
- Ajouter à cette calculette la fonctionnalité suivante :
- 26 variables logiques, nommées de "a" à "z", permettent de conserver le résultat de calculs précédents.
- L'affectation de ces variables et leur utilisation ressemblera à la syntaxe C. par exemple "a = 0 | 1 => 0" puis "b = a => (0|1)".
- Les variables seront implantées dans un tableau global de 26 entiers, réalisant une table des symboles rudimentaire.
- Ajouter enfin le traitement des erreurs avec génération de messages comme : "Expression incorrecte", "Utilisation de variable non initialisée", "Warning, affectation de variable déjà initialisée" ...
2 - Analyse de Messages Internet (mail) au format RFC822
L'objectif est de pouvoir analyser la structure d'un mail Internet afin de produire un rapport sommaire
sur les entêtes utilisées et les tailles des constituants du message.
La syntaxe d'un email est décrite dans le RFC822 (Syntaxe BNF complète en annexe D, version simplifiée en annexe B).
Elle peut être synthétisée comme suit :
- Un message complet est la concaténation d'un nombre quelconque de "champs-entête", d'une ligne vide
("\n\n"), et d'un "corps" de message.
Contrairement au RFC, on pourra supposer qu'il y a toujours au moins 1 "champs-entêtes" et que le "corps" est non vide.
- Un "champs-entête" est la concaténation d'un "nom-champs", du caractère ":", est d'un
"corps-champs".
- Un "champs-entête" commence sur un début de ligne et termine sur une fin de ligne, mais peut occuper plusieurs lignes. Pour éviter les ambiguïtés, les lignes de continuation dans un "corps-champs" doivent obligatoirement
commencer par un caractère "blanc" ou un caractère "tabulation".
- Le "corps" d'un message et les "corps-champs" sont constituées de caractères ASCII 7-bits quelconques.
- Les "nom-champs" contiennent au moins un caractère et sont constituées des caractères "imprimables" (ASCII de 33 à 126) à l'exception du caractère "blanc" et du caractère ":".
Exemples
Un exemple court (petit mail):
Return-Path: <Pascal.Hennequin@telecom-sudparis.eu>
Received: from alambix.int-evry.fr (alambix [157.159.100.57])
by lor.int-evry.fr (8.8.0/jtpda-5.3) with ESMTP id KAA10453
for <pascal@hugo>; Mon, 29 Apr 2013 10:48:43 +0200 (MET DST)
Received: (from pascal@localhost)
by alambix.int-evry.fr (8.11.7p3+Sun/8.11.7) id r3T8mh021663
for pascal; Mon, 29 Apr 2013 10:48:43 +0200 (MEST)
Date: Mon, 29 Apr 2013 10:48:43 +0200 (MEST)
From: Pascal Hennequin (LOR-AIGRI) <Pascal.Hennequin@telecom-sudparis.eu>
Message-Id: <201304290848.r3T8mh021663@alambix.int-evry.fr>
To: pascal@alambix.int-evry.fr.int-evry.fr
Subject: Juste un mail pour ce qu'il est
Status: O
Je suis un petit mail ...
Entete_rfc822: Non, je ne suis pas une entete
From / je ne suis pas un separateur du format Mbox
fin
Un exemple plus long : Mail Plus Long
Travail demandé
- Ecrire un analyseur lexical qui lit un mail et identifie les unités lexicales "champs-entête" et "corps" de message. Pour les "\n" qui séparent ces unités lexicales, on pourra librement décider de
les inclure ou non dans les unités lexicales.
- Compléter l'analyseur afin de produire un rapport avec la liste des "nom-champs", et la taille en nombre de caractères du "corps" du message.
- Ecrire un second analyseur qui pourra identifier des "mots" dans le "corps" du message et dans les "corps-champs". L'analyseur produira un rapport avec pour chaque champs d'entête et pour le corps de message le nombre de caractères, le nombre de mots et le nombre de lignes correspondant. Indication : utiliser les start-conditions de flex "%x" ou "%s".
Corrigé
- Fichiers Makefile générique
- Fichiers de test mail-petit.txt et mail.txt
- Fichier readme decrivant les différentes versions
- Specification flex pour le Parsing rigoureux des unités Champs_entete et Corps mail0.flex
- Idem mais en utilisant des "start-conditions" mail1.flex
- Specification flex pour extraction de Noms de Champs et Taille du Corps mail2.flex
- Specification flex pour extraction des nombres de char, mot, ligne... mail3.flex
3 - Les mots MEUMEU chez les Shadoks
(remerciements à Walther Franz Anton von Dyck)
Le peuple shadok ne connaît que quatre syllabes : "GA", "BU", "ZO" et "MEU".
La transcription dans notre alphabet latin autorise indifféremment l'utilisation des minuscules ou des
majuscules dans ces syllabes : "GA" == "ga" == "gA".
Tout les mots de la langue shadok sont obtenus par concaténation de ces syllabes fondamentales.
Par exemple selon Wikipedia, "ZoGa" signifie pomper, "ZoBuGa" signifie pomper avec une petite pompe,
et "ZoBuBuGa" signifie pomper avec une grosse pompe.
Le professeur Shadoko a défini la famille des mots "MeuMeu" comme suit :
- "GaMeu" et "Buzo" sont des mots MeuMeu.
- La concaténation de deux mots MeuMeu est un mot MeuMeu.
- En ajoutant, en même temps, "Ga" au début et "Meu" à la fin d'un mot MeuMeu, on obtient un mot MeuMeu.
- En ajoutant, en même temps, "Bu" au début et "Zo" à la fin d'un mot MeuMeu, on obtient un mot MeuMeu.
- Précisions du rédacteur : le mot vide inconnu des shadoks est aussi MeuMeu; et les shadoks écrivent comme nous de gauche à droite.
Exemples
Le lecteur vérifiera en exercice les exemples suivants : (fichier test)
- Mots MeuMeu : "Gameugameu", "GagaMeumeu", "gaBuzomEu", "gabuzogameumeu", ...
- Mots Pas MeuMeu : "GaBumeuZo", "Meumeu" !, "gagameumeumeu", "gagaGameumeu", ...
Travail demandé
- Décrire la famille des mots MeuMeu grâce à une grammaire context-free non ambiguë.
- Ecrire un analyseur (syntaxique+lexical) permettant de reconnaître les mots MeuMeu.
Indication
Le peuple Gibi, ennemi des shadoks, semble avoir un ensemble de mots comparable,
mais à la place des syllabes Ga, Bu, Zo et Meu, ils utilisent des symboles ésotériques : {, [, ], }.
Corrigé
Le langage considéré est communement appelé l'ensemble des "mots bien parenthésés" (ici avec 2 paires de parentheses). En théorie des langages, Il s'agit des langages de Dyck qui jouent un rôle particulier dans le mesure où le théorème de Chomsky Schützenberger stipule qu'ils permettent de générer n'importe quel langage algébrique ("tout langage algébrique est une image homomorphe de l'intersection d'un langage rationnel avec une image homomorphe inverse du langage de Dyck sur deux paires de parenthèses" )
CSC 4508, Télécom SudParis, Pascal Hennequin
Last modified: Fev 2015