Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Ann´ ee universitaire 2018/2019 Site : ⊠Luminy □St-Charles □St-J´ erˆ ome □Cht-

Ann´ ee universitaire 2018/2019 Site : ⊠Luminy □St-Charles □St-J´ erˆ ome □Cht-Gombert ⊠Aix-Montperrin □Aubagne-SATIS Sujet de : □1er semestre ⊠2` eme semestre □Session 2 Dur´ ee de l’´ epreuve : 2h Examen de : L3 Nom du diplˆ ome : Licence d’Informatique Code du module : ENSIN6U1 Libell´ e du module : Compilation Calculatrices autoris´ ees : NON Documents autoris´ es : NON 1 Grammaires attribu´ ees (10pt) Soit la grammaire G, dont les arbres de d´ erivation repr´ esentent des arbres abstraits de L : 1. P →LD1 LD2 2. LD →D LD1 3. LD →null 4. D →fct id LD1 LD2 LI 5. D →var id 6. D →var id taille 7. V →simple id 8. V →indicee id E 9. LI →I LI1 10. LI →null 11. I →aff V E 12. I →si E LI1 LI2 13. I →tq E LI 14. I →app APP 15. I →ret E 16. I →ecr E 17. APP →id LE 18. LE →E LE1 19. LE →null 20. E →op2 E1 E2 21. E →op1 E1 22. E →V 23. E →entier 24. E →APP 25. E →lire Dans cette grammaire, les terminaux sont repr´ esent´ es par des symboles compos´ es de lettres minuscules et les non terminaux par des symboles compos´ es de lettres MAJUSCULES. Quand des non terminaux apparaissent plusieurs fois dans une r` egle, ils sont indic´ es. Par exemple, LD1 LD2 contient deux instances du mˆ eme non terminal LD. Les terminaux id, entier, op1 et op2 poss` edent des valeurs auxquelles on peut avoir acc` es par l’interm´ ediaire de l’attribut val. Ainsi id.val est la valeur d’un identiﬁant particulier. Dans chacune des questions suivantes on cherche ` a r´ epondre ` a une question concernant un arbre abstrait, qui est aussi un arbre de d´ erivation g´ en´ er´ e par G. Pour chacune, il vous est demand´ e de d´ eﬁnir un ou plusieurs attributs ainsi que les actions s´ emantiques associ´ ees aux r` egles de G permettant de calculer la valeur des attributs. Pour chaque attribut d´ eﬁni, indiquer : sont type, ce qu’il repr´ esente et s’il est h´ erit´ e ou synth´ etis´ e. Pour chaque question, vous pourrez utiliser les attributs d´ eﬁnis dans les questions pr´ ec´ edentes. Il est inutile d’´ ecrire les r` egles qui ne sont pas concern´ ees par les attributs de la question. Q1.1 Combien d’instructions comporte un programme ? (2pt) 1. P →LD1 LD2 P.n = LD2.n 2. LD →D LD1 LD.n = D.n + LD1.n 3. LD →null LD.n = 0 4. D →fct id LD1 LD2 LI D.n = LI.n 9. LI →I LI1 LI.n = I.n + LI1.n 10. LI →null LI.n = 0 11. I →aff V E I.n = 1 12. I →si E LI1 LI2 I.n = LI1.n + LI2.n + 1 13. I →tq E LI I.n = LI.n + 1 14. I →app APP I.n = 1 15. I →ret E I.n = 1 16. I →ecr E I.n = 1 1 Q1.2 Quelle est la longueur de la fonction la plus longue 1 d’un programme ? (1pt) 1. P →LD1 LD2 P.m = LD2.m 2. LD →D LD1 LD.m = max(D.n, LD1.m) 3. LD →null LD.m = 0 Q1.3 Quelle est la port´ ee de chaque variable (globale, locale, argument) d’un programme ? (2pt) 1. P →LD1 LD2 LD1.portee = global 2. LD →D LD1 D.portee = LD1.portee = LD.portee 4. D →fct id LD1 LD2 LI LD1.portee = locale LD2.portee = arg Q1.4 Pour chacune des variables locales et des param` etres de fonction, dire si elle masque une variable globale. (2pt) 1. P →LD1 LD2 LD2.vg = LD1.vg 2. LD →D LD1 si(LD.portee = global)alorsLD.vg = D.vg ∪LD1.vg 3. LD →null LD.vg = {} 4. D →fct id LD1 LD2 LI LD1.vg = D.vg LD2.vg = D.vg 5. D →var id si(D.portee == global)alorsD.vg = {id.val} . → sinonD.masque = id.val ∈D.vg 6. D →var id taille D.vg = {id.val} D.masque = faux Q1.5 Une fonction est dite ferm´ ee, si toute ex´ ecution possible de la fonction se termine par une instruction retour. Pour chacune de trois fonctions suivantes, dire si elle est ferm´ ee ou pas. f() {si a alors {retour 1;}} g() {si a alors {retour 1;} retour 0;} h() {si a alors {retour 1;} sinon {retour 0;}} (1pt) f non ferm´ ee, g ferm´ ee, h ferm´ ee Q1.6 D´ eﬁnir un attribut et les actions s´ emantiques associ´ ees pour d´ eterminer si chacune des fonctions du programme est ferm´ ee ? (2pt) 4. D →fct id LD1 LD2 LI D.ferme = LI.ferme 9. LI →I LI1 LI.ferme = I.ferme ∨LI1.ferme 10. LI →null LI.ferme = faux 11. I →aff V E I.ferme = faux 12. I →si E LI1 LI2 I.ferme = LI1.ferme ∧LI2.ferme 13. I →tq E LI I.ferme = faux 14. I →app APP I.ferme = faux 15. I →ret E I.ferme = vrai 16. I →ecr E I.ferme = faux 2 Arbres abstraits (2pt) Dessiner l’arbre abstrait du programme suivant en utilisant la grammaire de la question pr´ ec´ edente. Q2.1 somme(entier b) entier s;{i = 0; s = 0; tantque i < b faire{s = s + i; i = i + 1;}} main(){ecrire(somme(10));} 1. La longueur d’une fonction est le nombre d’instruction qu’elle comporte. 2 (2pt) 3 P LD null LD D fct id (somme) LD D var id (b) LD null LD D var id (s) LD null LI I AFF V simple id (i) E entier (0) LI I AFF V simple id (s) E entier (0) LI I tq E op2 (<) E V simple id (i) E V simple id (b) LI I AFF V var id (s) E op2 (+) E V simple id (s) E V simple id (i) LI I AFF V var id (i) E op2 (+) E V simple id (i) E entier (1) LI null LI null LD D fct id (main) LD null LD null LI I ecr E APP id (somme) LE E entier (10) LE null LI null 4 3 Code trois adresses (4pt) Pour chacun des fragments de programmes suivants, donner le code trois adresses lui correspondant. Q3.1 ( ( a + b ) < ( 3 * c ) ) & ! ( c < 10 ) (2,5pt) : t0 = va + vb : t1 = 3 * vc : t2 = -1 : if t0 < t1 goto e0 : t2 = 0 e0 : t3 = -1 : if vc < 10 goto e1 : t3 = 0 e1 : t4 = -1 : if t3 == 0 goto e2 : t4 = 0 e2 : if t2 == 0 goto e3 : if t4 == 0 goto e3 : t5 = -1 : goto e4 e3 : t5 = 0 e4 : ... Le r´ esultat est dans t5 Q3.2 tantque i < 10 faire { i = i + 1;} (1,5pt) e0 : t0 = -1 : if vi < 10 goto e2 : t0 = 0 e2 : if t0 == 0 goto e1 : t1 = vi + 1 : vi = t1 : goto e0 e1 : ... 4 Assembleur (4pt) Dans chacun des deux exercices suivants, un court programme en code trois adresses est donn´ e. L’objet de ces exercices est d’´ ecrire le code en assembleur x86 issu de la traduction du code trois adresses 2, ainsi que, l’information contenue dans chacun des quatre registres eax, ebx, ecx et edx ` a tout moment de la g´ en´ eration. Pour cela, on pr´ esentera la solution sous la forme d’un tableau contenant pour chaque instruction en code trois adresses l’instruction ou les instructions en assembleur lui correspondant. Ce tableau contient aussi quatre colonnes repr´ esentant le descripteur de chacun des quatre registres, comme dans l’exemple suivant : 2. Il est inutile d’´ ecrire le code assembleur qui pr´ ec` ede l’´ etiquette fmain, ` a l’exception de la d´ eclaration des variables globales. 5 C3A a b c d X86 t7 = 45 + 12 t7 mov eax, 45 t7 add eax, 12 t8 = 3 * t7 t7 t8 mov ebx, 3 t7 t8 imul ebx, eax ... ... Q 4.1 Q 4.2 fmain: fbegin alloc 1 va alloc 1 va ff: fbegin alloc 1 vb alloc 1 vd alloc 1 vc t0 = vb + vc alloc 1 vdisc vd = t0 t0 = va * va ret vd t1 = 2 * va fend t2 = t1 * vb fmain: fbegin t3 = t0 + t2 alloc 1 vb t4 = vb * vb alloc 1 t5 = t3 + t4 param vb vdisc = t5 param 3 fend t1 = call ff va = t1 fend Q4.1 (2pt) C3A a b c d X86 fmain: fbegin fmain: push ebp mov ebp, esp alloc 1 va sub esp, 4 uploads/S4/ exam-compil-2018-2019.pdf