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.

Exemples (fichier test)

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é

1. Ecrire un analyseur syntaxique qui évalue (imprime VRAI ou FAUX) des expressions logiques d'ordre 0 écrites ligne à ligne.
2. 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.
3. 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é

1. 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.
2. 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.
3. 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".

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é

1. Décrire la famille des mots MeuMeu grâce à une grammaire context-free non ambiguë.
2. 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 : {, [, ], }.