TP1 de compilation

TP n°1 de Compilation

durée prévue : 3h (2h pour les autres TP)

Exercice 1

1.1.
Avec un éditeur, construire un fichier exc1.lex contenant le texte suivant :


%%

.|\n     ECHO;

%%

Taper : lex -t exc1.lex
pour voir à l'écran l'allure du fichier créé par lex (l'option -t affiche le code C produit au lieu de créer le fichier lex.yy.c).

On voit ainsi la taille importante d'un analyseur qui se contente de transmettre le flot d'entrée inchangé au flot de sortie. Les courageux pourront essayer de comprendre le code C produit...

1.2.
Modifier ensuite le fichier exc1.lex comme suit :


%%

[aeiou]     {printf("!");}

.|\n     ECHO;

%%

Taper successivement :
lex exc1.lex
gcc lex.yy.c -o exc1 -ll

pour créer le code source lex.yy.c de l'analyseur, puis compiler ce code source et créer l'exécutable exc1

Pour lancer ce premier analyseur syntaxique, taper exc1. Saisir une ligne, une autre ligne... que fait l'analyseur ?
N.B. Le système doit reconnaitre le chemin menant à cet exécutable, si ce n'est pas le cas, écrire : ./exc1

Pour interrompre l'analyseur : Ctrl-C ou Ctrl-D.

Remarque : si on ne veut pas utiliser la librairie Lex ou Flex (option de compilation -ll ou -lfl selon les systèmes) ou si elle est absente (parfois le cas pour Flex), il faut alors définir les fonctions yywrap et main dans le fichier Lex. Pour l'exercice ci-dessus, le fichier-lex pourrait s'écrire différemment. Voici trois possibilités, de la plus simple à la plus sophistiquée :

%% [aeiou] {printf("!");} .|\n ECHO; %% yywrap() {return 1;} main() {return yylex();} %option noyywrap %% [aeiou] {printf("!");} .|\n ECHO; %% main() {return yylex();} %% [aeiou] {printf("!");} .|\n ECHO; %% #ifndef yywrap yywrap() {return 1;} #endif #ifndef main main() {return yylex();} #endif

Notez qu'un des codes peut ne pas fonctionner dans une des variantes de Lex (Unix-ATT, Unix-Berkeley, Linux-Lex, Linux-Flex, Cygwin-Flex, ...).

Une bonne habitude : Effacer lex.yy.c (et l'exécutable) avant chaque modification du fichier lex et avant chaque nouvel exercice, on peut vérifier ainsi, en cas d'erreur de compilation, que les fichiers n'ont pas été créés et éviter de lancer un code ne correspondant pas au code Lex créé.

1.3.
Simplifions l'analyseur :


%%

[aeiou]   {printf("!");}

%%

Pourquoi cet analyseur a-t-il le même comportement que le précédent ?

1.4.
Pour que l'analyseur sache s'arrêter, rajouter après la première ligne %% du fichier exc1.lex :

^FIN$ {printf("bye \n") ; return 0 ;}

Tester son effet.

1.5.
Essayons maintenant de mettre deux lignes de commande de fin :


^FIN$   {printf("premiere fin \n") ; return 0 ;}

^FIN$   {printf("seconde fin \n") ; return 0 ; }

Expliquer l'affichage final. Bien évidemment, on n'écrira par la suite qu'une seule ligne de fin de saisie !

1.6. Comment ferait-on pour que la commande d'arrêt de l'analyseur soit une ligne vide ?

Exercice 2

2.1.
Compiler et exécuter le fichier exc2.lex suivant, que fait cet analyseur ? Comment s'arrête-t-il ?

%{

int c ;

%}

%%

^\n     { return 0 ;}

.       { c++ ; }

\n      { printf("total ligne %d\n",c) ; }

%%

main() {

  c=0 ;

  yylex() ;

  printf("total final : %d\n",c) ;

}

2.2.
Modifier ce fichier-lex pour qu'il affiche correctement le nombre de caractères saisis de chaque ligne en plus du nombre cumulé.
N.B. Que se passe-t-il si , au lieu de gcc lex.yy.c -ll, on utilise pour compiler la commande: gcc -ll lex.yy.c ? (le résultat peut varier selon les systèmes)

2.3. Modifier encore ce fichier pour compter en parallèle le nombre de chiffres (0 à 9), de points (caractère '.'), ainsi que le nombre d'opérateurs (+ - * /).

Exercice 3

3.1.
Ecrire un analyseur lexical qui supprime les espaces et les tabulations inutiles (redoublés ou en fin de ligne) du texte saisi en entrée et qui compte le nombre de mots (séparés par un (des) espacement ou une ponctuation).

3.2.
Ecrire un analyseur qui met en majuscule le premier caractère de chaque ligne d'entrée.

3.3.
Ecrire un analyseur qui combine les opérations des deux questions précédentes.
Comment aurait-on pu combiner les deux opérations sans créer un troisième opérateur ?

Exercice 4

Ecrire un analyseur qui reconnait si une phrase est bien parenthésée. (On rappelle qu'un mot d'un langage donné est bien parenthésé quand : 1°) il a autant de parenthèses ouvrantes que de parenthèses fermantes et 2°) tout préfixe du mot ne contient pas plus de parenthèses fermantes que de parenthèses ouvrantes.

Exercice 5

Le décodeur biologique

Un brin d'ADN peut être vu comme un mot sur l'alphabet {A,T,G,C} et un brin d'ARN comme un mot sur l'alphabet {A,U,G,C}.
La réplication de l'ADN donne un brin anti-complémentaire en changeant les lettres (A->T,T->A,C->G,G->C).
La transcription de l'ADN donne un brin d'ARN messager (A->U,T->A,C->G,G->C). La translation de l'ARN messager donne une protéine (suite d'amino-acides) selon le procédé décrit dans la question 5.3.

5.1.
Ecrire un analyseur qui reconnait les quatre bases de l'ADN, représentées par leur initiale (A pour Adénine, T pour Thymine, G pour Guanine, C pour Cytosine), et retourne leur nom en toutes lettres. Comment gérer les caractères non reconnus ?

Exemple :
flot d'entrée : AaTCAGg...
flot de sortie : Adénine Adénine Thymine Cytosine Adénine Guanine Guanine ...

5.2.
Ecrire un analyseur qui crée le brin d'ARN messager à partir d'un brin d'ADN (la lettre U représente l'Uracile).

5.3.
Chaque groupe de trois bases de l'ARN forme une unité de codage (un codon), selon le code dégénéré ci-dessous (premier tableau) qui donne les amino-acides correspondants (codes des lettres dans le deuxième tableau). La partie comprise entre un codon START et un codon STOP de l'ARN donne une protéine.

**Tableau 1 : Les codons**
	U	C	A	G
U**	UUU Phe UUC Phe UUA Leu UUG Leu	UCU Ser UCC Ser UCA Ser UCG Ser	UAU Tyr UAC Tyr UAA *Stop* UAG *Stop*	UGU Cys UGC Cys UGA *Stop* UGG Trp
C**	CUU Leu CUC Leu CUA Leu CUG Leu	CCU Pro CCC Pro CCA Pro CCG Pro	CAU His CAC His CAA Gln CAG Gln	CGU Arg CGC Arg CGA Arg CGG Arg
A**	AUU Ile AUC Ile AUA Ile AUG Start	ACU Thr ACC Thr ACA Thr ACG Thr	AAU Asn AAC Asn AAA Lys AAG Lys	AGU Ser AGC Ser AGA Arg AGG Arg
G**	GUU Val GUC Val GUA Val GUG Val	GCU Ala GCC Ala GCA Ala GCG Ala	GAU Asp GAC Asp GAA Glu GAG Glu	GGU Gly GGC Gly GGA Gly GGG Gly

**Tableau 2 : Les vingt amino-acides**
code L1	code L3	Nom
A	Ala	Alanine
C	Cys	Cystéine
D	Asp	Aspartate
E	Glu	Glutamate
F	Phe	Phénylalanine
G	Gly	Glycine
H	His	Histidine
I	Ile	Isoleucine
K	Lys	Lysine
L	Leu	Leucine
M	Met	Méthionine
N	Asn	Asparagine
P	Pro	Proline
Q	Gln	Glutamine
R	Arg	Arginine
S	Ser	Sérine
T	Thr	Thréonine
V	Val	Valine
W	Trp	Tryptophane
Y	Tyr	Tyrosine

Ecrire un analyseur qui décode, dans l'ARN, les lignes qui commencent par un codon START suivi d'un nombre indéfini de codons de Phénylalanine, Leucine ou Sérine, avant de terminer par un codon STOP.
L'analyseur serait-il très différent si le codon START n'était pas forcément le premier codon et le codon STOP pas forcément le dernier ?

* 5.4. (Pour les plus rapides, qui ont le temps)
* 5.4.a. Compléter le programme précédent pour reconnaître tous les amino-acides. Pour éviter un travail trop fastidieux, il faut bien évidemment optimiser la reconnaissance des motifs en les factorisant... et il y a des choix à faire pour gérer les erreurs ou incertitudes.
* 5.4.b. Utiliser les analyseurs 5.2 et 5.4.a pour "fabriquer" la/les protéines codées par un brin d'ADN.

* Exercice 6

(Pour aller plus loin, après le TP)
Le brin complémentaire d'un ADN se lit dans le sens inverse du brin initial. Créer un programme de réplication de l'ADN qui tienne compte de cette nouvelle contrainte.