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 3ème Année Licence en Informatique SUPPORT DE COURS REALISE PAR PR

COMPILATION 3ème Année Licence en Informatique SUPPORT DE COURS REALISE PAR PR SOUICI-MESLATI LABIBA souici_labiba@yahoo.fr 2012-2013 MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE BADJI MOKHTAR-ANNABA UNIVERSITY UNIVERSITE BADJI MOKHTAR-ANNABA وزارة اﻟﺘﻌﻠﻴﻢ اﻟﻌﺎﻟﻲ و اﻟﺒﺤﺚ اﻟﻌﻠﻤﻲ ﺟﺎﻣﻌﺔ ﺑﺎﺟﻲ ﻣﺨﺘﺎر – ﻋﻨﺎﺑـــــــــــــــﺔ FACULTE DES SCIENCES DE L’INGENIORAT DEPARTEMENT D’INFORMATIQUE آﻠﻴﺔ ﻋﻠــــــــــــﻮم اﻟﻬﻨﺪﺳـــــــــﺔ ﻗﺴﻢ اﻹﻋـــــــــﻼم اﻷﻟـــــــــــــﻲ Compilation, L3 Informatique , Pr Souici-Meslati L., Université d’Annaba, 2012/2013 2 Compilation, L3 Informatique , Pr Souici-Meslati L., Université d’Annaba, 2012/2013 3 SYLLABUS (DESCRIPTIF OFFICIEL) Domaine: Mathématique et Informatique Filière: Informatique Spécialité: Licence Informatique (L3) Semestre: 1, Année 2012-2013 Unité d’enseignement: UEI13 Matière: COMPILATION Nombre de Crédits: 6 Volume horaire hebdomadaire total : 6h00 Cours : 3h TD : 1h30 TP : 1h30 Evaluation Examen final : 50% TD : 25% (50% : présence et participation et 50% : micro interrogation) TP : 25% (50% : présence et participation et 50% : évaluations sur machine) Objectifs 1. Compréhension du cheminement d'un programme (texte) source vers un programme (code). 2. Etude des étapes du processus de compilation d’un langage évolué. 3. Etude de méthodes et techniques utilisées en analyse lexicale, syntaxique et sémantique. 4. Familiarisation, en TP, avec des outils de génération d’analyseurs lexicaux et syntaxiques (LEX et YACC). Contenu 1 Introduction à la compilation • Les différentes étapes de la compilation • Compilation, interprétation, traduction 2 Analyse Lexicale • Expressions régulières • Grammaires • Automates d’états finis • Un exemple de générateur d’analyseurs lexicaux : LEX 3 Analyse Syntaxique • Définitions : grammaire syntaxique, récursivité gauche, factorisation d’une grammaire, grammaire ε-libre • Calcul des ensembles des débuts et suivants • Méthodes d’analyse descendante : la descente récursive, LL(1) • Méthodes d’analyse ascendante : SLR(1), LR(1), LALR(1) (méthode des items) • Un exemple de générateur d’analyseurs syntaxiques : YACC 4 Traduction dirigée par la syntaxe (Analyse sémantique) 5 Formes intermédiaires • Forme postfixée • Quadruplés • Triplés directs et indirects • Arbre abstrait 6 Allocation - Substitution – Organisation des données à l’exécution Références Bibliographiques Ouvrages existants au niveau de la bibliothèque de l’université, la référence 1 est vivement recommandée 1. Aho A., Sethi R., Ullman J., "Compilateurs : Principes, techniques et outils", Inter-éditions, 1991 et Dunod, 2000 2. Drias H., "Compilation: Cours et exercices", OPU, 1993 3. Wilhem R., Maurer D., "Les compilateurs: Théorie, construction, génération", Masson, 1994 Compilation, L3 Informatique , Pr Souici-Meslati L., Université d’Annaba, 2012/2013 4 CHAPITRE 1 : INTRODUCTION AUX COMPILATEURS 1.1 Définition Un compilateur est un programme qui a comme entrée un code source écrit en langage de haut niveau (langage évolué) est produit comme sortie un code cible en langage de bas niveau (langage d’assemblage ou langage machine). La traduction ne peut être effectué que si le code source est correct car, s’il y a des erreurs, le rôle du compilateur se limitera à produire en sortie des messages d’erreurs (voir figure 1.1). Compilateur Code Cible Code Source Messages d’erreurs Figure 1.1. Rôle du compilateur Un compilateur est donc un traducteur de langage évolué qu’on ne doit pas confondre avec un interpréteur qui est un autre type de traducteur. En effet, au lieu de produire un programme cible comme dans le cas d’un compilateur, un interpréteur exécute lui-même au fur et à mesure les opérations spécifiées par le programme source. Il analyse une instruction après l’autre puis l’exécute immédiatement. A l’inverse d’un compilateur, il travaille simultanément sur le programme et sur les données. L’interpréteur doit être présent sur le système à chaque fois que le programme est exécuté, ce qui n’est pas le cas avec un compilateur. Généralement, les interpréteurs sont assez petits, mais le programme est plus lent qu’avec un langage compilé. Un autre inconvénient des interpréteurs est qu’on ne peut pas cacher le code, et donc garder des secrets de fabrication : toute personne ayant accès au programme peut le consulter et le modifier comme elle le veut. Par contre, les langages interprétés sont souvent plus simples à utiliser et tolèrent plus d’erreurs de codage que les langages compilés. Des exemples de langages interprétés sont : BASIC, scheme, CaML, Tcl, LISP, Perl, Prolog Il existe des langages qui sont à mi-chemin de l’interprétation et de la compilation. On les appelle langages P- code ou langages intermédiaires. Le code source est traduit (compilé) dans une forme binaire compacte (du pseudo-code ou p-code) qui n’est pas encore du code machine. Lorsqu’on exécute le programme, ce P-code est interprété. Par exemple en Java, le programme source est compilé pour obtenir un fichier (.class) « byte code » qui sera interprété par une machine virtuelle. Un autre langage p-code : Python. Les interpréteurs de p-code peuvent être relativement petits et rapides, si bien que le p-code peut s’exécuter presque aussi rapidement que du binaire compilé. En outre les langages p-code peuvent garder la flexibilité et la puissance des langages interprétés. Compilation, L3 Informatique , Pr Souici-Meslati L., Université d’Annaba, 2012/2013 5 1.2 Structure générale d’un compilateur Un compilateur est généralement composé de modules correspondant aux phases logiques de l’opération de compilation (voir figure 1.2). Compilateur Code Source Messages d’erreurs Analyseur Lexical Analyseur Syntaxique Analyseur Sémantique Optimiseur de Code Générateur de Code Intermédiaire Générateur de Code Unités lexicales Arbre Syntaxique Décoré Arbre Syntaxique Code Intermédiaire Optimisé Code Intermédiaire Gestionnaire des erreurs Code Cible Gestionnaire de la Table des Symboles Figure 1.2. Phases et modules de compilation Chacun des modules de la figure 1.2 (excepté les modules gestionnaires de table de symboles et d’erreurs), représente une phase logique qui reçoit en entrée une représentation de code source et la transforme en une autre forme de représentation. La structure représentée par la figure 1.2 est purement conceptuelle. Elle correspond à l’organisation logique d’un compilateur. En pratique, plusieurs phases peuvent être regroupées en une seule passe qui reçoit en entrée une certaine représentation et donne en sortie une autre. Par exemple, les phases d’analyses lexicale, syntaxique, sémantique et la génération du code intermédiaire peuvent correspondre à seule passe dans laquelle l’analyseur syntaxique est le module maître qui appelle, à chaque fois, l’analyseur lexical pour obtenir une unité lexicale, puis déterminer graduellement la structure syntaxique du code et enfin appelle le générateur de code qui effectue l’analyse sémantique et produit une partie du code intermédiaire. 1.2.1 L’analyseur lexical Connu aussi sous l’appellation Scanner, l’analyseur lexical a pour rôle principal la lecture du texte du code source (suite de caractères) puis la formation des unités lexicales (appelées aussi entités lexicales, lexèmes, jetons, tokens ou encore atomes lexicaux). Exemple Considérons l’expression d’affectation a := b + 2 * c ; Les unités lexicales qui apparaissent dans cette expression sont : Compilation, L3 Informatique , Pr Souici-Meslati L., Université d’Annaba, 2012/2013 6 Unité lexicale Sa nature a Identificateur de variable := Symbole d’affectation b Identificateur de variable + Opérateur d’addition 2 Valeur entière * Opérateur de multiplication c Identificateur de variable ; Séparateur L’analyseur a aussi comme rôle l’élimination des informations inutiles pour l’obtention du code cible, le stockage des identificateurs dans la table des symboles et la transmission d’une entrée à l’analyseur syntaxique. Concernant les informations inutiles, il s’agit généralement du caractère espace et des commentaires. 1.2.2 L’analyseur syntaxique L’analyseur syntaxique (appelé Parser en anglais) a pour rôle principal la vérification de la syntaxe du code en regroupant les unités lexicales suivant des structures grammaticales qui permettent de construire une représentation syntaxique du code source. Cette dernière a souvent une structure en arbre. Notons que durant cette phase, des informations, telles que le type des identificateurs, sont enregistrées dans la table des symboles Exemple La représentation sous forme d’arbre syntaxique de l’expression « a := b + 2 * c ; » est donnée par la figure 1.3. Dans cette structure d’arbre, les nœuds représentent des opérateurs et les feuilles de l’arbre représentent les valeurs et les variables sur lesquelles s’effectuent les opérations. La figure donne aussi le parcours qui est fait sur cet arbre lors de l’évaluation. D’autre parcours peuvent être envisagés pour réaliser différentes tâches, cependant ces parcours ont lieu dans les phases ultérieures de la compilation. := * + a b 2 c := + a b Valeur de 2*c 1ère étape : évaluation de 2*c Arbre syntaxique := a Valeur de b+ 2*c 2ème étape : évaluation de b+ (2*c) 3ème étape : affectation du résultat à a Figure 1.3. Arbre syntaxique et parcours d’évaluation 1.2.3 L’analyseur sémantique Il comme rôle principal le contrôle du code source, pour détecter éventuellement l’existence d’erreurs sémantiques, et la collecte des informations destinées à la production du code intermédiaire. Un des constituants importants de la phase d’analyse sémantique est le contrôle du type qui consiste à vérifier si les opérandes de chaque opérateur sont conformes aux spécifications du langage utilisé pour le code source. Exemple Dans l’analyse sémantique de « a := b + 2 * c ; », il faut vérifier que, si a est de type entier, alors b et c le sont aussi, sinon il faut signaler une erreur. Compilation, L3 Informatique , Pr Souici-Meslati L., Université d’Annaba, 2012/2013 7 Si on suppose que a, uploads/S4/ chap-1-introduction-aux-compilateurs.pdf