Rendre sur la plate-forme Moodle, une archive nom.tar.gz (ou .tgz) contenant uniquement les fichiers utiles. C'est-à-dire :
Par contre :
Le TP comprend 2 exercices courts (~ 4 points * 2) et un problème long (~ 12 points). Ces 3 éléments sont totalement indépendants et on utilisera des directories différents pour chaque exercice.
Le langage Ada autorise une écriture "aérée" des constantes entières avec l'utilisation du caractère "_"
non significatif entre des chiffres du nombre. Par exemple : 1234 ou 1_234 ou 12_34 ...
Un usage courant en particulier dans le monde anglo-saxon est d'aérer l'écriture des grands nombres avec des
séparateurs (blanc ou point ou virgule ...) pour les milliers et les puissances de milliers.
Pour les explications, cf. "man cat" .
NB: on considère la commande "cat" comme un filtre, c'est-à-dire sans arguments, avec lecture sur stdin et écriture sur stdout : cat < file_in > file_out
L'objectif de cet exercice est d'écrire un interpreteur capable de reconnaître et d'évaluer des expressions ensemblistes.
On considerera des ensembles d'entiers pris dans un intervalle [0,N] (N= 31, ou 63 ou autres) et l'on utilisera
la réalisation de la structure de données Ensemble fournie avec les fichiers
set.h et
set.c .
Pour la lecture, on a aussi un "pretty-print" HTML des fichiers set.h et set.c .
NB: Pour eviter des problèmes de compilation, le fichier "set.h" devra être inclus dans le lexer avant l'include partagé flex/bison ("yyparse.h"), ainsi
que dans le parser.
Les expressions ensemblistes que l'on desire reconnaître sont construites à partir des composants suivants :
Pour la lisibilité des expressions, on ajoutera :
L'exercise laisse le choix entre 2 versions de réalisation:
Les opérations sont écrites sous forme de fonctions avec une notation usuelle nom_fonction( arg1 , arg2, ..).
La fonction comp aura 1 seul argument, diff aura 2 arguments, union et inter auront dans un premier temps 2 arguments et seront étendues ensuite à n arguments (n>=1)
{ 1 , 2 , 3 } # == {1,2,3} { 1 , 2 , 3 , 2 , 1} # == {1,2,3} inter( {1,2} , {1,3} ) # == {1} inter( union({1,2},{1,3}) , {3,4,5} ) # == {3} union( {1,2}, inter({1,3} , {3,4,5})) # == {1,2,3} diff( {0,1,2,3,4,5} , {1,3,5}) # == {0,2,4} S_2 = {1,2,4,8,16,32,64,128} # == ca depend des bornes S_2 # inter(S_2 , comp(S_2)) # == {} quelque soit S_2 union(S_2 , comp(S_2)) # == All elem S_3 = S_2 # union( {1}, {1,2}, {2,3}) # union a n arguments =={1,2,3} {1,} # Error S_111 # Error diff({}) # Error comp({)} # Error {1} # verif resynchro apres erreur == {1}
Les opérations sont écrites sous forme d'opérateurs en notation infixe.
Les opérateurs union, inter, diff sont binaires, comp est unaire.
Les parenthèses servent alors a gerer l'ambiguité et la priorité entre les opérateurs.
NB: "union" et "inter" sont totalement associatifs et "inter" est usuellement prioritaire sur "union".
{ 1 , 2 , 3 } # == {1,2,3} { 1 , 2 , 3 , 2 , 1} # == {1,2,3} {1,2} inter {1,3} # == {1} ({1,2} union {1,3}) inter {3,4,5} # == {3} {1,2} union {1,3} inter {3,4,5} # == {1,2,3} {0,1,2,3,4,5} diff {1,3,5} # == {0,2,4} S_2 = {1,2,4,8,16,32,64,128} # == ca depend des bornes S_2 # S_2 inter comp S_2 # == {} quelque soit S_2 comp S_2 union S_2 # == All elem S_3 = S_2 # {1} union {1,2} union {} # =={1,2} {1,} # Error S_111 # Error S_2 comp S_3 # Error {1} # verif resynchro apres erreur == {1}
Ecrire un analyseur syntaxique (lexer + parser) qui valide et évalue des expressions ensemblistes selon l'une des
2 versions de syntaxe. Le lexer est a priori identique pour les 2 versions.
On prendra soin de procéder de façon itérative par étape. Par exemple :