langevin@licinfo7.1 04/09/14 ****************************************** * THEORIE DES LANGAGES ET COMPILATION * * EXAMEN DE TRAVAUX - PRATIQUES * * 10 Avril 2014 de 09:00 -- 12:00 * ****************************************** ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Vous repondrez aux questions posees directement dans ce fichier en precisant sommairement les commandes exactes qui vous ont permis d'aboutir a vos reponses. Vous respecterez les noms de sources et de cibles requises dans l'enonce : le répertoire d'examen contiendra un et un seul fichier makefile. Vous pouvez utiliser les informations presentes sur votre compte, la documentation en ligne de commande : -- aucun autre document n'est autorise. Le sujet contient beaucoup de question, il n'est pas necessaire de tout faire pour avoir une note maximale. /\ / \ Pour validez votre travail a la fin de l'examen : / !! \ ------ /home/partage/pl/validexam -m I61 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ========================= 1. Expression Rationnelle ========================= repertoire : reg [a] Implanter en langage C un filtre pour mettre en capitale les chaines correspondant à un motif passé par la ligne de commande. La sortie de la commande se fera sur la sortie standard. Par exemple : $> echo 'abracadabra' | ./cap.exe '[^a-d]+' abRacadabRa [ source reg/cap.c ] int main (int argc, char *argv[]) { char line[1024]; FILE *src = stdin; regex_t r; int i, s; regmatch_t pos; if (regcomp (&r, argv[1], REG_EXTENDED) != 0) { printf ("\nbad regular expression"); return 1; } if ( argc > 2 ) src = fopen (argv[2], "r"); if ( ! src ) { printf ("\nbad file"); return 1; } while (fgets ( line, 1024, src)) { s = 0; while (0 == regexec (&r, &(line[s]), 1, &pos, 0)) { i = pos.rm_so; while (i--) putchar ( line[s++] ); i = pos.rm_eo - pos.rm_so; while (i--) putchar ( toupper(line[s++]) ); } puts( &line[s] ); } regfree (&r); return 0; } [b] Placer une cible capito dans votre makefile, pour faire une demonstration, puis inserer ici le resultat de : make capito echo 'helloworld !' | ./cap.exe '[lo]+' heLLOwOrLd ! [c] Donner une solution basee sur un filtre standard de votre choix. sed 's/[return]/\U&/g' cap.c | tail -5 } REgfREE (&R); pRiNTf ("\N"); RETURN 0; } ===================== 2. Cadre de pile ===================== repertoire : mem Ecrire un programme en langage C pour mettre en evidence : [ a ] Le sens d'empilement, adresse croissante ou decroissante. Il faut ecrire du code qui provoque un empilement d'appel de fonction... Par exemple, proc ( 3 ) avec int proc( int d ) { int x; printf("d=%d %p\n", d, &x ); if ( d > 0 ) proc( d-1 ); return d; } [ b ] Inserer une demonstration gcc -Wall stack.c -o stack.exe ./stack.exe d=3 0x7fff48da7b3c d=2 0x7fff48da7b0c d=1 0x7fff48da7adc d=0 0x7fff48da7aac conclusion : empilage suivant les adresses decroissantes. ======================= 3. Automate ======================= Repertoire : auto [a] Le lancement de make bug plante. Expliquer pourquoi ? make bug echo "load U;push U;dot;eps;det;min;dot;" | ./auto.exe ./auto.exe : interface pour afnd.c 6 etats 1 : push U (6 states) dot -Tpng 'U.dot' > 'U.png' sh: 1: gthumb: not found 1 : push U_e (6 states) auto.exe: epsdet.c:17: isnew: Assertion `A->nbs < 16' failed. La determinisation d'un automate a n etats peut demander 2^n etats. Ici, U possede 6 etats, et la limite du nombre d'etats est depassee. [b] Réparer le code par une intervention minimale sur afnd.h : il suffit de changer 2 lignes. Lesquelles ? #define MAX 64 typedef unsigned long long set; make bug echo "load U;push U;dot;eps;det;min;dot;" | ./auto.exe ./auto.exe : interface pour afnd.c 6 etats 1 : push U (6 states) dot -Tpng 'U.dot' > 'U.png' sh: 1: gthumb: not found 1 : push U_e (6 states) 1 : push U_e_d (32 states) 1 : push U_e_d_m (33 states) dot -Tpng 'U_e_d_m.dot' > 'U_e_d_m.png' sh: 1: gthumb: not found La derniere erreur peut etre corrigee en remplacant gthumb par geeqie dans le makefile mais ce n'est pas utile pour la suite. [c] Quelle est la taille de l'automate minimal qui reconnait les nombres ecrits en base 2 qui sont des multiples de 16 ? Les commandes ne sont pas renseignees dans l'analyseur... $ grep modulo *.l mod{SP}{NB} push( modulo(ytoi(yytext) ) , &stack); ./auto.exe : interface pour afnd.c mod 16 1 : push M16 (16 states) eps 1 : push M16_e (16 states) det 1 : push M16_e_d (16 states) min 1 : push M16_e_d_m (6 states) 6 etats d'apres le programme avec un etat puit isole, au final 5. ======================= 4. Analyseur lexical ======================= Repertoire : flex [ a ] Completer le script canevas.sh pour obtenir une commande qui realise le meme travail que l'exercice 1. *** Dans l'etat cannevas.sh construit une source flex /tmp/canevas.l. *** Il s'agit d'un analyseur qui replique l'entree standard sur la *** sortie standard ! *** Le tout est compile par le script en une commande canevas.exe *** le script termine par l'execution de : cat $2 | canevas.exe *** Il suffit alors d'inserer la ligne : $1 ptr = yytext; while (*ptr) printf("%c", toupper(*ptr++) ); putchar('\n'); *** pour obtenir le filtre desire. Par exemple, le resultat de $ ./canevas.sh 'y{2}' canevas.sh |& grep Y pourrait etre : YYlex(); [ source canevas.sh ] [ b ] Inserer une demonstration. make canevas flex$ ./canevas.sh '^.*ptr.*$' canevas.sh 2>/dev/null CHAR *PTR; $1 PTR = YYTEXT; WHILE (*PTR) PRINTF("%C", TOUPPER(*PTR++) ); PUTCHAR('\N'); ======================== 5. Analyseur syntaxique ======================== Repertoire : yacc On considère la grammaire d'expressions rationnelles : SRC --> [ EXP ] EXP --> EXP + EXP EXP --> EXP * EXP --> EXP . EXP EXP --> ( EXP ) EXP --> ALPHA ou le token terminal ALPHA désigne une lettre de [a-z]. Au non terminal SRC on associe deux parametres : la profondeur et la taille de l'arbre syntaxique. La profondeur est la longueur maximale d'un chemin de SRC vers une feuille. La taille est le nombre de noeuds de l'arbre syntaxique. [ a ] Implanter un analyseur syntaxique re.y qui verifie la syntaxe des expressions rationnelles presentent dans une source sans faire d'action semantique. [ source re.y ] Inserer le resultat d'une demonstration [ make re ] [ b ] Implanter un analyseur syntaxique qui realise le travail de re.y tout en precisant les parametres des arbres syntaxiques. [ source parms.y ] Inserer le resultat d'une demonstration [ make parms ] *** Je repond directement a [c] [ c ] Mettre en oeuvre un analyseur qui filtre un fichier texte et qui affiche les positions (ligne, colonne) ou se trouve une expressions rationnelles, en precisant ses parametres. [ source repos.y ] %{ #include #include #include int num = 1, pos=0, cpt=0, col=0; int node= 0; int yylval ; int yylex( void ); int yyerror( char*s ); int max ( int x, int y ){ return (x= 'a' && car <= 'z' ) return ALPHA; switch ( car ) { case EOF : fflush(stdout);return FIN; case '+' : return PLUS; case '.' : return FOIS; case '*' : return STAR; case '[' : col=pos;return CG; case ']' : return CD; case '(' : return PG; case ')' : return PD; case '\n': pos=0; num++; } } } int yyerror(char *msg) { //printf("\n%s\n", msg); return 0; } Inserer le resultat d'une demonstration yacc]$ make repos cat re.txt Quelques exemples d'expressions regulieres sont : [ a ], [a+b], ou encore [ (a+b)*.c ]... echo '---' --- ./re.exe < re.txt Quelques exemples d'expressions regulieres sont : [ a ] cpt=1 li=2 co=19 node=5 ht=3 , [a+b] cpt=2 li=2 co=26 node=9 ht=4 , ou encore [ (a+b)*.c ] cpt=3 li=3 co=11 node=18 ht=7 S / | \ [ E ] / | \ E . E /\ | E * A / | \ ( E ) / | \ E + E | | A A ... ---------------------------------------------------------------- langevin@licinfo7.1