Remerciez-le!

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

14/10/2015 1 Pr. Ghizlane BENCHEIKH A.U. 2015 - 2016 Cours de compilation Chapi

14/10/2015 1 Pr. Ghizlane BENCHEIKH A.U. 2015 - 2016 Cours de compilation Chapitre I Introduction aux compilateurs 2 I. Qu’est ce qu’un compilateur ? 1.1) Définition : Un compilateur est un programme exécutable (logiciel) qui permet de : Lire un programme écrit en un langage de haut niveau (langage source) et le traduit vers un programme écrit en un langage de plus bas niveau (langage cible). Signaler des erreurs de syntaxe, de sémantique (par exemple via une vérification de type) Dans certains cas, faire des optimisations qui peuvent viser plusieurs objectifs parfois contradictoires : vitesse d’exécution, taille du code, utilisation de la mémoire, etc. 3 1.2) Exemples Exemples de langage compilés : Fortran, C, C++, Pascal, ADA, … Exemples de compilateurs pour le langage C : Dev – C++, LCC Win32, Code block, Borland C++, Visual C++, … 4 II. La structure d’un compilateur La compilation se décompose en deux phases, contenant chacune plusieurs modules : Une phase d’analyse, qui va reconnaître les variables, les instructions, les opérateurs, détecter les erreurs et élaborer une représentation intermédiaire, Une phase de synthèse et de production qui devra produire le code cible à partir de cette représentation intermédiaire. 5 Définition : Un arbre abstrait est constitué de nœuds qui représentent les opérations et les fils des nœuds qui représentent les arguments des opérations. Exemple : Soit l'instruction: A = B1 + B2 * 60 Son arbre abstrait est : Dessiner l’arbre abstrait des expressions 1) A = B+C+D, 2) A = B*C*D, 3) A = B*(C+D), 4) A=B*C+2*D*E 6 14/10/2015 2 2.1) Phase d’analyse La phase d’analyse, est réalisée par la partie frontale du compilateur, elle permet de : découper le programme source en ses constituants (variables, instructions, …) : Analyse lexicale; détecter des erreurs de syntaxe : Analyseur syntaxique; détecter des erreurs de sémantique : Analyse sémantique; produire une représentation intermédiaire du programme source : Générateur de code intermédiaire; conserver dans une table des symboles diverses informations sur les procédures et variables du programme source. 7 2.1.1) Analyse lexicale Elle lit le programme source lettre par lettre et le décompose en unités lexicales appelées lexèmes (Token en anglais) Spécifie la nature de chaque unité lexicale, qu’il s’agisse d’identificateurs, de constantes réelles, entières, chaînes de caractères, des opérateurs (affectation, addition), des séparateurs (parenthèses, points virgules), les mots clés du langage (if, else, while, int, float, …) Elimine les caractères superflus (commentaires, espaces, passages à la ligne). Exemple : considérons le code C suivant : 8 if ( i < a + b ) // ceci est un commentaire x = 2 * x; L’analyseur lexical déterminera la suite de token : MOT_CLÉ SÉPARATEUR IDENTIFICATEUR OPÉRATEUR_REL IDENTIFICATEUR OPÉRATEUR_ARITH IDENTIFICATEUR SÉPARATEUR IDENTIFICATEUR AFFECTATION CONSTANTE OPÉRATEUR_ARITH IDENTIFICATEUR SÉPARATEUR 9 if ( i < a + b ) // ceci est un commentaire x = 2 * x; Mot_clé Séparateur identificateur Op_rel identificateur Op_arith À éliminer 2.1.2) Analyse syntaxique Il s agit de vérifier que les unités lexicales sont dans le bon ordre défini par le langage. L’analyseur syntaxique sait comment doivent être construites les expressions, les instructions, les déclarations de variables, les appels de fonctions, … Exemple : En C, une sélection simple doit se présenter sous la forme : if (expression) instruction Si l’analyseur syntaxique reçoit la suite d’unités lexicales MOT_CLÉ_IF IDENT OP_REL ENTIER … il doit signaler une erreur car il n’y a pas de « ( » juste après le if L’analyseur syntaxique produit un arbre syntaxique abstrait 10 2.1.3) Analyse sémantique Dans cette phase, on opère certains contrôles (contrôles de type, par exemple) afin de vérifier que l’assemblage des constituants du programme a un sens. On ne peut pas, par exemple, additionner un réel avec une chaîne de caractères, ou affecter une variable à un nombre. 11 2.2) Phase de synthèse La phase de synthèse est réalisée par la partie finale du compilateur, elle construit le programme cible à partir de la représentation intermédiaire et de la table des symboles, elle comprend : Optimisation du code : Il s’agit d’améliorer le code produit afin que le programme résultant soit plus rapide, comme l’élimination de calculs inutiles (faits en double), extraction des boucles des invariants de boucle, … Génération de code : Il s’agit de produire les instructions en langage cible. 12 14/10/2015 3 2.3) Résumé 13 Programme source Représentation intermédiaire Programme cible Analyse Synthèse Compilateur 14 Programme source Représentation intermédiaire Programme cible Analyse Synthèse Compilateur Analyse Lexicale Analyse Syntaxique Analyse Sémantique Générateur de code intermédiaire 15 Programme source Représentation intermédiaire Programme cible Analyse Synthèse Compilateur Optimisateur du code Générateur du code cible Chapitre II Analyse lexicale 16 I. Introduction 17 L’analyseur lexical constitue la première étape d’un compilateur. Sa tâche principale est de lire les caractères d’entrée et de produire comme résultat une suite de lexèmes que l’analyseur syntaxique aura à traiter. Il élimine les caractères superflus (commentaires, tabulations, fin de lignes, …) Il gère les numéros de ligne dans le programme source pour pouvoir associer à chaque erreur rencontrée par la suite la ligne dans laquelle elle intervient Pour effectuer ces analyse, on fait appel aux notions de théorie de langage, les expressions régulières et les automates. Définitions 18 Une unité lexicale est une suite de caractères qui a une signification collective. Exemples : les chaînes ≤, ≥, <, > sont des opérateurs relationnels. L’unité lexicale est OPREL, par exemple. Les chaînes toto, ind, tab, ajouter sont des identificateurs (de variables ou de fonctions). Les chaînes if, else, while sont des mots clés. Les symboles ; ( ) . sont des séparateurs. 14/10/2015 4 19 Un lexème est une suite de caractères du programme source qui concorde avec le modèle d'une unité lexicale Exemple : L’unité lexicale correspondant à la chaîne « ≤ » est OPREL, alors que le lexème est « ≤ » . Un modèle est une règle associée à une unité lexicale qui décrit l’ensemble des chaînes du programme qui peuvent correspondre à cette unité lexicale. pour les caractères spéciaux simples et doubles et les mots réservés, le lexème et le modèle coïncident, le modèle d'un nombre est « une suite de chiffres, éventuellement précédée d'un signe », Le modèle d'un identificateur est une suite de lettres, de chiffres et du caractère « _ », commençant par une lettre. 20 Exemples: L'unité lexicale IDENT (identificateurs) en C a pour modèle : toute suite non vide de caractères composée de chiffres, lettres ou du symbole "_" et qui commencent par une lettre. Des exemples de lexèmes pour cette unité lexicale sont : max, i, a1, ajouter_valeur ... L'unité lexicale NOMBRE (entier signé) a pour modèle : toute suite non vide de chiffres précédée éventuellement d'un seul caractère parmi. Comme par exemple : -12, 83204, +0 … Attributs : informations concernant le lexème (champs dans la table des symboles) ; II. Expressions régulières 21 Définitions Un alphabet est un ensemble de symboles. {0,1} est un alphabet {A,T,C,G} est un alphabet {1,M,0,5} est un alphabet Un mot (ou chaîne) sur un alphabet Σ est une séquence finie de symboles de Σ. 00011011 est un mot sur {0,1} ACCAGTTGAAGTGGACCTTT est un mot sur {A,T,C,G}. Soit l’alphabet { aa, b, c} aba n’est pas un mot sur Σ. baab, caa, bc, aaaa sont des mots sur Σ. 22 On note  le mot vide Si x et y sont deux mots, la concaténation de x et y, notée xy, est le mot obtenu en écrivant y immédiatement après x. Par exemple, la concaténation des mots abc et le mot rst est le mot abcrst. Si x est une chaîne, on définit x0 = ε Pour n > 0, xn = xn-1x =xxn-1. On a donc x1 = x, x2 = xx, x3 = xxx, etc. 23 Un langage sur un alphabet Σ est un ensemble de mots construits sur Σ. Exemple : Soit l’alphabet  = {a,b,1}, soit L l’ensemble des mots qui se terminent par 1. L1 est le langage infini : {a1, b1, aa1, ab1, aaabb1, ….} Soit l’alphabet français, l’ensemble des mots du dictionnaire constitue un langage sur cet alphabet. Les opérations sur les langages Soient L et M deux langages, on définit : Dénomination Notation Définition l'union de L et M L U M { x | x є L ou x є M} la concaténation de L et M LM {xy | x є L et y є M} la fermeture de Kleene de L L* { x1x2…xn | xi є L, n є N et n ≥0} la fermeture positive de L L+ { x1x2…xn | xi є L, n є N et n >0} 24 Exemple : On se donne les alphabets L = {A,B…Z, a, b… z}, ensemble des lettres, et C ={0,1… 9}, ensemble des chiffres. Définir les langages suivants : L U C, LC, L4, L*, C+ et L(L U C)*. L U C est l'ensemble des lettres et des chiffres, LC est l'ensemble des chaînes formées d'une lettre suivie d'un chiffre, L4 est l'ensemble des chaînes de quatre lettres, L* est l'ensemble uploads/s3/ cours-compilation.pdf