Remerciez-le!

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

Compilation : théorie, techniques et outils Exercices HABIB ABDULRAB (INSTITUT

Compilation : théorie, techniques et outils Exercices HABIB ABDULRAB (INSTITUT NATIONAL DES SCIENCES APPLIQUÉES DE ROUEN) CLAUDE MOULIN (UNIVERSITÉ DE TECHNOLOGIE DE COMPIÈGNE) SID TOUATI (UNIVERSITÉ DE VERSAILLES SAINT-QUENTIN EN YVELINES) Table des matières I - TD 0 - Introduction à la programmation assembleur 7 A.Pré-requis du TD 0.....................................................................................7 B.Exercice 1.................................................................................................7 C.Exercice 2.................................................................................................9 D.Exercice 3...............................................................................................10 E.Exercice 4...............................................................................................10 F.Exercice 5................................................................................................10 II - TD1 - Analyse lexicale 13 A.Exercice 1...............................................................................................13 B.Exercice 2...............................................................................................14 C.Exercice 3...............................................................................................14 D.Exercice 4...............................................................................................15 E.Exercice 5...............................................................................................15 III - TD 2 - Analyse syntaxique 17 A.Exercice 1 : Analyse descendante...............................................................17 B.Exercice 2 : Grammaire............................................................................17 C.Exercice 3 : IF ... THEN ... ELSE (LL)..........................................................18 D.Exercice 4 : IF ... THEN ... ELSE (LR)........................................................19 E.Exercice 5 : SLR, LALR..............................................................................19 IV - TD3 - Analyse sémantique 21 A.Exercice 1 : Grammaire LR d'expressions arithmétiques................................21 B.Exercice 2 : Grammaire LL d'expressions arithmétiques................................21 V - TD 4 - Actions sémantiques et Yacc (table Aes symboles simple) 23 3 A.Pré-requis du TD4....................................................................................23 B.Exercice 1...............................................................................................23 C.Exercice 2 : Utilisation de Yacc...................................................................24 D.Exercice 3 : Utilisation de Yacc (suite)........................................................24 VI - TD 5 - Actions sémantiques et Yacc (Gestion des types) 27 A.Pré-requis du TD 5 ..................................................................................27 B.Exercice 1...............................................................................................27 C.Exercice 2...............................................................................................28 VII - TD 6 - Tables de symboles et types. 29 A.Pré-requis du TD 6 ..................................................................................29 B.Exercice 1...............................................................................................29 C.Exercice 2...............................................................................................30 VIII - TD 7 - Génération de code 31 A.Pré-requis du TD 7...................................................................................31 B.Exercice 1...............................................................................................31 C.Exercice 2...............................................................................................32 IX - TD 8 - Génération de code 35 A.Pré-requis du TD 8 ..................................................................................35 B.Exercice 1...............................................................................................35 C.Exercice 2...............................................................................................36 D.Exercice 3...............................................................................................36 X - TD 9 - Génération de code et optimisation. 39 A.Pré-requis du TD 9...................................................................................39 B.Exercice 1...............................................................................................39 C.Exercice 2...............................................................................................40 Solution des exercices rédactionnels 43 TD 0 - Introduction à la programmation assembleur 4 I - TD 0 - Introduction à la programmation assembleur I Pré-requis du TD 0 7 Exercice 1 7 Exercice 2 9 Exercice 3 10 Exercice 4 10 Exercice 5 10 A.Pré-requis du TD 0  Avoir suivi le cours d'introduction à la compilation qui explique les rudiments de la programmation assembleur (x86).  Pour l'architecture i386, avoir étudié les différences entre la syntaxe asm AT&T et la syntaxe intel. Voir le document donné en annexe (cf. Annexe TD0).  Pour faire l'exercice 1, il faudrait étudier le document donné en annexe décrivant la sémantique de chaque instruction asm i386. Attention, il y a une différence entre la syntaxe intel et la syntaxe AT&T (adoptée par gnu gcc). B.Exercice 1 Traduire le programme assembleur ci-dessous en langage C. Q u e s t i o n [Solution n°1 p 37] 5 TD 0 - Introduction à la programmation assembleur 6 C.Exercice 2 Générer le code assembleur du programme C ci-dessous. Q u e s t i o n [Solution n°2 p 39] TD 0 - Introduction à la programmation assembleur 7 D.Exercice 3 Générer le code assembleur du programme C ci-dessous. Q u e s t i o n [Solution n°3 p 40] E.Exercice 4 Générer le code assembleur du code C ci-dessous. On supposera que le tableau est rangé e, lignes. Q u e s t i o n [Solution n°4 p 40] F.Exercice 5 Dans la déclaration suivante, déterminez la formule donnant l'adresse de la case mémoire référencée par l'expression: tab[i][j][k]. Q u e s t i o n [Solution n°5 p 41] TD 0 - Introduction à la programmation assembleur 8 II - TD1 - Analyse lexicale II Exercice 1 13 Exercice 2 14 Exercice 3 14 Exercice 4 15 Exercice 5 15 A.Exercice 1 Trouver un automate reconnaissant : Q u e s t i o n 1 [Solution n°6 p 42] Le langage ; où L est le langage des mots ayant une seule occurrence de Q u e s t i o n 2 [Solution n°7 p 42] L'ensemble de nombres entiers (signés ou non) sur l'alphabet . Q u e s t i o n 3 [Solution n°8 p 42] L'ensemble de nombres rationnels (signés ou non) sur l'alphabet . Les langages suivants sont-ils reconnaissables ? Q u e s t i o n 4 [Solution n°9 p 42] = l'ensemble des mots sur terminant par . i.e. . Q u e s t i o n 5 [Solution n°10 p 43] l'ensemble des mots sur qui sont des représentations binaires des entiers naturels multiples de 3. Un automate est complet si pour chaque état de , et chaque lettre de , il existe une flèche de la forme , où est un état de l'automate. Q u e s t i o n 6 [Solution n°11 p 43] 9 Montrer que pour chaque automate on peut associer un automate noté t.q.: B.Exercice 2 Les langages suivants sont-ils réguliers ? Q u e s t i o n 1 [Solution n°12 p 44] Le langage ; où est le langage des mots ayant une seule occurrence de Q u e s t i o n 2 [Solution n°13 p 44] L'ensemble de nombres entiers (signés ou non) sur l'alphabet . Q u e s t i o n 3 [Solution n°14 p 44] L'ensemble de nombres rationnels (signés ou non) sur l'alphabet . Q u e s t i o n 4 [Solution n°15 p 44] l'ensemble des mots sur terminant par . i.e. . Q u e s t i o n 5 [Solution n°16 p 44] 1.10) C.Exercice 3 Déterminiser les automates suivants Q u e s t i o n 1 [Solution n°17 p 44] Q u e s t i o n 2 [Solution n°18 p 44] TD1 - Analyse lexicale 10 D.Exercice 4 Si et sont deux langages réguliers: Q u e s t i o n 1 [Solution n°19 p 45] Calculer l'automate qui reconnaît . En déduire l'automate reconnaissant: . Q u e s t i o n 2 [Solution n°20 p 46] Calculer l'automate qui reconnait . En déduire l'automate reconnaissant: . Q u e s t i o n 3 [Solution n°21 p 46] En déduire que et sont réguliers. E.Exercice 5 Q u e s t i o n [Solution n°22 p 46] Trouver un scanner non déterministe qui associe à chaque mot de , de longueur , le mot si est pair, le mot sinon. TD1 - Analyse lexicale 11 III - TD 2 - Analyse syntaxique III Exercice 1 : Analyse descendante 17 Exercice 2 : Grammaire 17 Exercice 3 : IF ... THEN ... ELSE (LL) 18 Exercice 4 : IF ... THEN ... ELSE (LR) 19 Exercice 5 : SLR, LALR 19 A.Exercice 1 : Analyse descendante Soit la grammaire : Q u e s t i o n 1 [Solution n°23 p 47] Construire les ensembles PREMIER et SUIVANT pour cette grammaire. Q u e s t i o n 2 [Solution n°24 p 47] Établir la table d'analyse et montrer que cette grammaire n'est pas LL(1) B.Exercice 2 : Grammaire Soit la grammaire d'expressions arithmétiques définie par les productions suivantes : Q u e s t i o n 1 [Solution n°25 p 47] Les terminaux de la grammaire sont : 13 Donner les dérivations les plus à gauche pour les chaînes et Q u e s t i o n 2 [Solution n°26 p 48] Cette grammaire est-t-elle récursive à gauche ? Si oui, transformez-la en grammaire récursive à droite. Q u e s t i o n 3 [Solution n°27 p 48] On cherche maintenant à écrire un analyseur syntaxique descendant pour cette grammaire. Quelle grammaire utiliser ? Q u e s t i o n 4 [Solution n°28 p 48] Simuler l'analyse de l'expression par un analyseur de type descendant. C.Exercice 3 : IF ... THEN ... ELSE (LL) Soit la grammaire : Les terminaux sont : L'axiome est Q u e s t i o n 1 [Solution n°29 p 50] Cette grammaire est-elle LL(1) ? Q u e s t i o n 2 [Solution n°30 p 50] Comment lève-t-on généralement l'ambiguïté rencontrée ? Q u e s t i o n 3 [Solution n°31 p 51] Analyser l'instruction suivante en utilisant le choix de la question précédente : D.Exercice 4 : IF ... THEN ... ELSE (LR) Soit la grammaire : TD 2 - Analyse syntaxique 14 Les terminaux sont : Q u e s t i o n 1 [Solution n°32 p 51] Cette grammaire est-elle LR(0) ? Q u e s t i o n 2 [Solution n°33 p 51] Cette grammaire est-elle SLR(1) ? Q u e s t i o n 3 [Solution n°34 p 52] S'il existe des conflits quelle convention utiliser pour les supprimer ? E.Exercice 5 : SLR, LALR Considérons la grammaire G suivante : Q u e s t i o n [Solution n°35 p 52] Montrer que cette grammaire est LALR(1) mais pas SLR(1). TD 2 - Analyse syntaxique 15 IV - TD3 - Analyse sémantique IV Exercice 1 : Grammaire LR d'expressions arithmétiques. 21 Exercice 2 : Grammaire LL d'expressions arithmétiques. 21 A.Exercice 1 : Grammaire LR d'expressions arithmétiques. uploads/Management/ exercices-corrige-compilation.pdf