-------------------------------------------------------------------------------- EXAMEN DE TRAVAUX PRATIQUES DE COMPILATION Wed Apr 11 20:46:16 2012 nom : pl host: microbe.rts.fr L'objectif de l'exercice est de faire evoluer une calculette, un interpreteur d'expressions arithmetiques dont les termes sont des nombres entiers ou des identificateurs a une lettre pour adresser 26 memoires. Vous repondrez aux questions dans ce fichier par des copier/coller adequates, en evitant les caracteres ascii de code > 127. Duree de l'epreuve : 3 H 00 Temps estimer pour repondre aux questions : 2 H 15 A la fin de l'examen, vous lancerez la commande: $ /home/partage/validexam compil pour valider votre travail. Prevoir 5 minutes pour cette ultime tache. Documents autorises : vos sources, ainsi que les documents populaires sur le langage C, gcc, make, flex, bison, graphiz, dot. -------------------------------------------------------------------------------- Exercice 1 : 15 minutes -------------------------------------------------------------------------------- Apres avoir consulter les differents fichiers sources, faire les modifications necessaires pour que la compilation de calc.exe se termine correctement sans pour autant que la calculette ne soit operationnelle. [a] Preciser la nature des corrections effectuees : Le repertoire contient trois sources : scan.l : analyseur lexical calc.y : analyseur syntaxique node.c : une source C On commence par voir les dependances : [pl@microbe calc]$ grep include calc.y #include "commun.h" #include "node.h" #include "calc.h" [pl@microbe calc]$ grep include scan.l #include "commun.h" #include "calc.h" #include "node.h" bison -vd calc.y -o calc.c calc.y:62.9-10: le symbole NB est utilisé mais ce Il faut declarer NB, il s'agit du token pour les nombres, on modifie calc.y en consequence : %token PG PD NL MEM QUIT EGAL NB [pl@microbe calc]$ make bison -vd calc.y -o calc.c gcc -Wall -g -c calc.c flex -o scan.c scan.l cc -c -o scan.o scan.c cc -c -o node.o node.c gcc -Wall -g calc.o scan.o node.o -o calc -lfl [b] Inserer ici les resultats des commandes : $ cat make [pl@microbe calc]$ cat makefile cf=-Wall -g calc : calc.o scan.o node.o gcc $(cf) calc.o scan.o node.o -o calc -lfl calc.c : calc.y bison -vd calc.y -o calc.c calc.o : calc.c gcc $(cf) -c calc.c scan.o: calc.c scan.c gcc $(cf) -c scan.c scan.c : scan.l flex -o scan.c scan.l node.o: node.c gcc $(cf) -c node.c clean : rm -rf *.o $ make clean $ make [pl@microbe calc]$ make gcc -Wall -g -c scan.c scan.c:1131: attention : ‘yyunput’ defined but not used scan.c:1172: attention : ‘input’ defined but not used gcc -Wall -g -c node.c gcc -Wall -g calc.o scan.o node.o -o calc -lfl -------------------------------------------------------------------------------- Exercice 2 : 15 minutes -------------------------------------------------------------------------------- [a] Decrire le role des champs de la variable yylval. Revenez plus tard sur cette question si le role d'un des champs vous echappe. [pl@microbe calc]$ grep YYSTYPE *.h calc.h:#if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED calc.h:typedef int YYSTYPE; calc.h:# define YYSTYPE_IS_TRIVIAL 1 calc.h:# define yystype YYSTYPE /* obsolescent; will be withdrawn */ calc.h:# define YYSTYPE_IS_DECLARED 1 calc.h:extern YYSTYPE yylval; commun.h:#define YYSTYPE NODE yylval est de type NODE [pl@microbe calc]$ cat commun.h #ifndef COMMUN_H #define COMMUN_H struct node { int valeur, numero; }; typedef struct node NODE; #define YYSTYPE NODE #endif Les champs de yylval sont : numero et valeur. [pl@microbe calc]$ grep numero -B2 -A3 scan.l "*" return FOIS; [0-9]+ { yylval.numero = newnode("nb"); yylval.valeur = atoi( yytext); return NB; } Le champ valeur contient la valeur des expressions. [b] En utilisant l'option -E de gcc et la commande grep, sans utiliser la commande make, mettre en evidence le type de la variable yylval. copier/coller les commandes et le resultat de ces commandes : [pl@microbe calc]$ gcc -E -c calc.c | grep yylval extern NODE yylval; NODE yylval; *++yyvsp = yylval; yytoken, &yylval); *++yyvsp = yylval; yytoken, &yylval); -------------------------------------------------------------------------------- Exercice 3 : 15 minutes -------------------------------------------------------------------------------- Completer la calculette pour gerer les operations habituelles : addition, soustraction, multiplication, division et affectation. Les operandes seront des nombres ou bien des identifcateurs reduits a une lettre. [ a ] Donner la grammaire utilisee : PROG -> LI QUIT LI -> LI INSTR NL | INSTR -> EXP | MEM EGAL EXP EXP -> ( EXP ) | EXP + EXP |...| NB | MEM Un programme est une suite d'instructions separees par des sauts de lignes, terminee par "quit". Une terminaison doit etre placee sur la regle : PROG : LI QUIT { return 0; } [ b ] Inserer une demonstration : On commence gerer les nombres, rien a faire au niveau lexical. Deux modifications au niveau syntaxique : INSTR : EXP { $$.valeur = $1.valeur; } EXP : | NB { $$.valeur = $1.valeur; } [pl@microbe calc]$ cat essai.txt 1 2 quit [pl@microbe calc]$ ./calc < essai.txt Erreur de segmentation (core dumped) On a un probleme. (gdb) run < essai.txt Starting program: /home/pl/calc/calc < essai.txt Program received signal SIGSEGV, Segmentation fault. 0x00b15fed in vfprintf () from /lib/libc.so.6 Missing separate debuginfos, use: debuginfo-install glibc-2.12.2-1.i686 (gdb) bt #0 0x00b15fed in vfprintf () from /lib/libc.so.6 #1 0x00b2074f in fprintf () from /lib/libc.so.6 #2 0x0804a6af in newnode (s=0x804b0ea "nb") at node.c:30 #3 0x08049041 in yylex () at scan.l:16 #4 0x08048a29 in yyparse () at calc.c:1271 #5 0x08048e0d in main (argc=1, argv=0xbffff454) at calc.y:74 le probleme vient de newnode, une fonction de node.c PREMIERE APPROCHE : vu que l'utilisation champ numero n'est pas claire, on peut se contenter de commenter : [0-9]+ { // yylval.numero = newnode("nb"); yylval.valeur = atoi( yytext); return NB; } SECONDE APPROCHE : on debogue ! REMARQUE : tenter un DEBOGAGE avec des printf n'est pas une bonne approche... (gdb) break newnode Breakpoint 1 at 0x804a67b: file node.c, line 29. (gdb) run < essai.txt The program being debugged has been started already. Start it from the beginning? (y or n) y Starting program: /home/pl/calc/calc < essai.txt Breakpoint 1, newnode (s=0x804b0ea "nb") at node.c:29 29 node++; (gdb) n 30 fprintf(out, "\nnode_%d[label=\"%s\"] ;", node, s); (gdb) n Program received signal SIGSEGV, Segmentation fault. 0x00b15fed in vfprintf () from /lib/libc.so.6 (gdb) display out 1: out = (FILE *) 0x0 En effet, le fichier out doit etre initialise, c'est visiblement le role de opendot/dotclose. A placer dans le main ! int main( int argc, char *argv[] ) { opendot(); yyparse(); dotclose(); return 0; [pl@microbe calc]$ cat essai.txt | ./calc resultat : 1 resultat : 2 ou encore [pl@microbe calc]$ ./calc < essai.txt resultat : 1 resultat : 2 On gere les memoires et l'affectation : au niveau lexical : "=" return EGAL; [a-zA-Z]+ { yylval.numero = newnode("var"); *yytext = tolower(*yytext); yylval.valeur = *yytext - 'a'; return MEM; } Au niveau syntaxique : INSTR : EXP { $$.valeur = $1.valeur; } | MEM EGAL EXP { mem[ $1.valeur ] = $3.valeur; $$.valeur = $3.valeur; } ; EXP : | MEM { $$.valeur = mem[ $1.valeur ]; } ; [pl@microbe calc]$ cat essai.txt a = 1 b = 2 a + b quit [pl@microbe calc]$ ./calc < essai.txt resultat : 1 resultat : 2 resultat : 3 Pour le reste c'est de la routine : EXP : PG EXP PD { $$.valeur = $2.valeur; } | EXP PLUS EXP { $$.valeur = $1.valeur + $3.valeur; } | EXP SUB EXP { $$.valeur = $1.valeur - $3.valeur; } | EXP DIV EXP { $$.valeur = $1.valeur / $3.valeur; } | EXP FOIS EXP { $$.valeur = $1.valeur * $3.valeur; } | NB { $$.valeur = $1.valeur; } | MEM { $$.valeur = mem[ $1.valeur ]; } ; [pl@microbe calc]$ cat essai.txt 1 1+1 1*3 (4) 7-2 12/2 quit [pl@microbe calc]$ ./calc < essai.txt resultat : 1 resultat : 2 resultat : 3 resultat : 4 resultat : 5 resultat : 6 -------------------------------------------------------------------------------- Exercice 4 : 15 minutes -------------------------------------------------------------------------------- Ajouter l'operateur ternaire : X ? Y : Z où X, Y, Z sont trois expressions, et le resultat vaut Y si X n'est pas nul, et Z sinon. [a] Preciser les proprietes souhaitables de l'operateur : Celle du langage C, faible priorite, associatif a droite. [b] Decrire la nature des modifications : %token PG PD NL MEM QUIT EGAL NB %right PI DP %left PLUS SUB %left FOIS DIV %start PROG EXP : EXP PI EXP DP EXP { $$.valeur = $1.valeur ? $3.valeur : $5.valeur; } [c] Inserer une demonstration : [pl@microbe calc]$ cat essai.txt a = 1 a ? 2 : 0 a-1 ? 0 : 3 quit [pl@microbe calc]$ ./calc < essai.txt resultat : 1 resultat : 2 resultat : 3 -------------------------------------------------------------------------------- Exercice 5 : 15 minutes -------------------------------------------------------------------------------- Modifier l'analyseur pour gerer les termes : mem[ exp ] i.e. une expression designant la variable d'adresse v, ou la valeur v de exp est inferieure ou egale a 26. En particuler, si v = 0 alors le terme correspond la variable A. [ a ] Decrire les modifications : Les tokens crochets, au niveau lexical et les regles : EXP : CG EXP CD { $$.valeur = mem[ $2.valeur ]; } INSTR : | CG EXP CD EGAL EXP { mem[ $2.valeur ] = $5.valeur; $$.valeur = $5.valeur; } [ b ] Inserer une demonstration : [pl@microbe calc]$ ./calc [5] = 7 resultat : 7 f resultat : 7 [pl@microbe calc]$ ./calc a=123 resultat : 123 [0] resultat : 123 [[1]] resultat : 123 -------------------------------------------------------------------------------- Exercice 6 : 15 minutes -------------------------------------------------------------------------------- Modifier les analyseurs pour proteger le programme contre les divisions par zero. En cas de division par zero, le programme devra s'arrêter avec le message d'erreur : division par zero en ligne où represente le numero de la ligne. [ a ] Decrire les modifications : Pour gerer les lignes, un compteur : numligne, declare dans calc.y, puis extern dans common.h #ifndef COMMUN_H #define COMMUN_H struct node { int valeur, numero; }; typedef struct node NODE; #define YYSTYPE NODE extern int numligne; #endif Action lexicale : \n numligne++; return NL; Action semantique : EXP : | EXP DIV EXP { if ( $3.valeur ) $$.valeur = $1.valeur / $3.valeur; else { printf("%d : division par zero", numligne); return 0; } } [ b ] Inserer une demonstration : [pl@microbe calc]$ ./calc a=0 resultat : 0 b=1 resultat : 1 b/a 3 : division par zero -------------------------------------------------------------------------------- Exercice 7 : 15 minutes -------------------------------------------------------------------------------- Modifier les sources pour alerter l'utilisateur sur les l'utilisation d'une memoire non initialisee. La encore, il conviendra de preciser la ligne d'avertissement, mais sans pour autant stopper l'execution du programme. avertissement : non initialisee Decrire les modifications : On utilise une variable : int flag[26] = {0} pour tracer les initialisations : INSTR : EXP { $$.valeur = $1.valeur; } | MEM EGAL EXP { mem[ $1.valeur ] = $3.valeur; $$.valeur = $3.valeur; init[ $1.valeur ] = 1; } et faire des controles : EXP : | MEM { if ( ! init[ $1.valeur ] ) { fprintf(stderr, "ligne %d : %c non initialisee", numligne, $1.valeur+'a'); } [pl@microbe calc]$ ./calc a=4 resultat : 4 c=3 resultat : 3 a+b+c ligne 3 : b non initialisee resultat : 7 -------------------------------------------------------------------------------- Exercice 8 : 30 minutes -------------------------------------------------------------------------------- Le fichier file/exemple.png a ete obtenu par la commande : $ dot -Tpng exemple.dot -o exemple.png Observer le fichier source file/exemple.dot. Modifier les sources de l'analyseur pour creer un fichier calc.dot utilisable par la commande dot obtenir une image de l'arbre syntaxique. Vous pouvez utiliser ou vous inspirer des les fonctions de node.c pour arriver a vos fins. A cet effet, notez que l'emploi de la fonction variadique mknode, et de la fonction newnode peuvent suffire. [ a ] Resumer les modifications : C'est ici que l'on comprend l'utilisation du champ numero, chaque noeud de l'arbre syntaxique est numerote avec la fonction newnode. La fonction variadique mknode s'occupe des fleches, pour l'addition : "+" yylval.numero=newnode("+");return PLUS; EXP : | EXP PLUS EXP { $$.valeur = $1.valeur + $3.valeur; $$.numero = newnode("exp"); mknode( $$, "yny", $1, $2, $3); } [ b ] Inserer une demonstration : [pl@microbe calc]$ cat calc.dot graph arbre { node_1[label="nb"] ; node_2[label="+"] ; node_3[label="nb"] ; node_4[label="exp"] ; node_4 -- node_1 [ label = "1" ]; {rank=same; node_1 node_2 } node_1 -- node_2 [color="white"] ; node_4 -- node_2 {rank=same; node_2 node_3 } node_2 -- node_3 [color="white"] ; node_4 -- node_3 [ label = "2" ]; } -------------------------------------------------------------------------------- 0