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: Concepts de base SMI 2017 1 A. SOUHAR Un compilateur Logiciel qui

Compilation: Concepts de base SMI 2017 1 A. SOUHAR Un compilateur Logiciel qui transforme un programme écrit dans un langage de haut niveau en instructions exécutables. Outil de base de toute réalisation informatique. Compiler = lire une suite de caractères exprimant une information selon une syntaxe , puis construire une autre représentation de cette information. Historique Programmation en langage machine (chiffres hexadécimaux). Programmation en langage d’assemblage (notation symbolique). Branchement dans le programme (utilisation des étiquettes). Notion de variable (manipulation symbolique des cases mémoires au lieu des @). Elaboration des langages de haut niveau (s’affranchir complétement de la machine). Définition Traduction d’un programme écrit dans un langage de haut niveau (abstraction sur la structure et les détails du calculateur) en instructions exécutables (élémentaires de cet ordinateur). Un compilateur traduit un programme écrit dans un langage source (exprimant un alg) en un pg (spécifiant le même alg) dans un langage cible. Environnement d’un compilateur Effectue des substitutions de définition, de marcos … préprocesseur compilateur assembleur Edition des liens Pg source Pg objet Code relogeable Pg cible Référence à des appels de routine, compilation séparée… Erreurs de compilation Erreurs d’editions des liens Librairie Processeur Résultats Données Erreur d’exécution Interpréteur vs Compilateur Un compilateur est un programme de traduction automatique. Le fichier résultant est un exécutable. (Pascal, C , C++, …) Un interpréteur exécute lui-même au fur et à mesure. IL analyse une instruction après l’autre puis l’exécute immédiatement. (Basic, Lisp , Prolog, …) Langage d’implémentation Texte source du compilateur en langage d’implémentation Compilateur Code exécutable du compilateur Texte source du Programme en langage source Compilateur Code exécutable du programme pour la machine cible Entrée dans une forme quelconque Programme Sortie dans une forme quelconque Compilation Compilateur Interpréteur Principes fondamentaux Le compilateur doit conserver le sens du programme compilé. Le compilateur doit améliorer le code. Donc la réalisation d’un compilateur est un travail difficile. D’où la nécessité d’une structure conceptuelle modulaire. Structure d’un compilateur Compilateur Texte source Texte source Face Avant (Analyse) Représentation Intermédiaire (Sémantique) Face Arrière (Synthèse) Architecture d’un Compilateur Un compilateur est donc découpé en plusieurs phases. Chaque phase constitue une partie de la traduction. 1. Face avant: la première tâche est de comprendre la structure du langage source, se fait en 3 étapes. Analyseur lexical. Analyseur syntaxique. Analyseur sémantique. Analyseur lexical Inspecte le texte source caractère par caractère et élimine les superflus. Regroupe ces caractères pour former les unités lexicales. Ce sont les mots du langage (plus la ponctuation). Donc c’est une lecture améliorée. Analyseur syntaxique Vérifie si l’ordre des unités lexicales correspond à l’ordre définit par le langage. IL vérifie la syntaxe du langage à partir de la définition de sa grammaire. Donc c’est la reconnaissance des phrases. Analyseur sémantique Vérifie que les phrases en un sens dans le langage. Analyse la portée des identificateurs, Analyse des types, … Donc c’est chercher si la signification de la phrase est correcte. 1 Compilation: Concepts de base (suite) SMI 2017 A. SOUHAR Structure d’un compilateur Compilateur Texte source Texte source Face Avant (Analyse) Représentation Intermédiaire (Sémantique) Face Arrière (Synthèse) Représentation intermédiaire Un compilateur analyse ses données, en construit une représentation sémantique et synthétise ses résultats à partir de cette représentation. 2. Cette tâche (la représentation intermédiaire) comprend 2 étapes: Génération du code intermédiaire. Optimisation du code. Génération du code intermédiaire Le paradigme analyse - synthèse est très puissant et d’application générale. Face avant ne dépend que de L1 Face arrière ne dépend que de L2 Texte source en L1 Texte en langage Intermédiaire Texte cible en L2 Traduction de L1 vers L2 Génération du code intermédiaire Pour L langages et M machines, ou n’a besoin que de L parties avant et M parties arrières: L+M modules au lieu de L*M.. Langage 1 Représentation Intermédiaire Langage 2 Langage L Machine 1 Machine 2 Machine M . . . . . . Génération du code intermédiaire En pratique pour plus de portabilité, la face arrière est remise à l’exécution. Code en langage Intermédiaire Machine Virtuelle Face avant ne dépend que de L1 Code source en L1 Exécution Optimisation du code Elimination des opérations inutiles pour produire un code plus efficace. Exemples: Détecter l’inutilité de recalculer des expressions dont la valeur est connue, Transporter à l’extérieur des boucles des expressions dont les opérandes ont la même valeur à toutes les itérations. Supprimer les expressions inutiles. Face arrière Un compilateur traverse la structure de donnes qui représente le code et génère un code équivalent dans le langage cible. 3. Cette tâche est communément appelée génération de code: Sélection d’instructions : Il doit choisir les instructions à utiliser pour implémenter chaque opérations. Ordonnancement d’instructions :Il doit choisir l’ordre d’exécution pour ses instructions choisies. Exemple de compilation d’une instruction 2 Compilation: Analyse lexicale SMI 2017 A. SOUHAR Analyse lexicale Consiste à lire des caractères d’entrée et de produire une suite des mots (unités lexicales). Détecte et supprime les caractères superflus (espaces, fin de lignes , …) L’unité lexicale : suite de caractères qui a une signification collective. Le modèle: règle associé à une unité lexicale qui décrit toutes les chaines du pg correspondantes à cette unité lexicale. Le lexème: suite de caractères du programme qui respect le modèle d’une unité lexicale. Exemple L’unité lexicale vitesse, calculer et i : sont des identificateurs. <=, < et >= : sont des operateurs relationnels. if, for et else : sont des mots clés. 1, 123 et 13.4 : sont des nombres. Le modèle: lettre(lettre|chiffre)* , <= et if Le lexème: ‘‘vitesse’’, ‘‘<=’’ et ‘‘if’’ Exemple d’analyse Pour le texte suivant : position = posInitiale + 60 * vitesse; l’analyseur lexical doit être capable de reconnaitre les lexèmes suivants: Unité lexicale lexème Identificateur position affectation = Identificateur posInitiale Operateur + nombre 60 Operateur * Identificateur Séparateur Vitesse ; L’analyseur lexical produira le code: identif1 ’=’ identif2 ’+’ nombre(60) ’*’ identif3 ’;’ Representation des unités lexicales Mots-clés et symboles doubles #define INFEG 256 #define IF 257 Identificateur: #define IDENTIF 300 Nombre: #define NOMBRE 301 Symboles simples: chacun est son propre représentation ’+’ ’,’ ’=’ Analyseur lexical Le problème donc est d’écrire un pg qui reconnait les unités lexicales dans le texte source : IL se réduit à une fonction qui retourne à chaque appel l’unité lexicale suivante trouvée On dispose de 3 solutions : 1. l’écrire à la main, 2. Formalisée par un automate fini, 3.Utiliser un générateur d’analyseur. 3 Compilation: Concepts de base SMI 2017 A. SOUHAR Langage Dans cette section, nous introduisons la notion formelle d'un langage, et le problème fondamental de la reconnaissance des chaînes d'une langue. Définitions de base Un alphabet Σ est un ensemble fini et non vide de symboles. Une chaîne ou mot sur un alphabet Σ est une juxtaposition finie de symboles de Σ. La longueur d'une chaîne w (le nombre des caractères qui la composent) est notée |w|. le vide ou la chaîne nulle est notée e. (C'est est la chaîne unique satisfaisant |e|= 0.) Notion d’alphabet L'ensemble de toutes les chaînes sur Σ est noté Σ*. Pour chaque n ≥ 0 nous définissons : Nous définissons: donc Pour un symbole ou une chaine x, xn concaténé avec elle- même n fois. Avec x0 = e. Notion de langage Un langage L sur un alphabet Σ est un ensemble de chaines construites sur Σ : L1 = L2 si et seulement si Soient L et M deux langages, on définit les opérations sur les langages comme suit: Notion d’expression régulière Propriété algébrique des expressions régulières Axiome Description r|s = s|r | est commutative r|(s|t) = (r|s)|t | associative r(st) = (rs)t Concaténation est associative r(s|t) = rs|rt (s|t)r= sr|tr Concaténation est distributive par rapport à | er= r re= r e est neutre pour la concaténation (r|e)* = r* Relation entre * et e r**= r* * est idempotent Définition d’expression régulière (Exemple de définition des identificateurs et des nombres) Notation Abrégée d’expression régulière Notation Abrégée d’expression régulière désigne désigne désigne représente l’ensemble des chaînes des a et des b (e inclus) désigne Soit Analyseur lexical  le problème de la reconnaissance des unités lexicales INFEG, DIFF, INF, EGAL, SUPEG, SUP, IDENTIF, respectivement définies par les expressions régulières <=, <>, <, =, >=, > et lettre(lettre|chiffre)*  #define IDENTIF 1 #define NOMBRE 2 #define SI 3 #define ALORS 4 #define SINON 5 etc. int uniteSuivante(void) { char c; c = lireCar(); while (estBlanc(c)) c = lireCar(); if (c == '<') { c = lireCar(); if (c == '=') return INFEG; else if (c == '>') return DIFF; else { delireCar(c); return INF; } } else if (c == '=') return EGAL; else if (c == '>') { c = lireCar(); if (c == '=') return SUPEG; else { delireCar(c); return SUP; } } else if (estLettre(c)) { lonLex = 0; lexeme[lonLex++] = c; c = lireCar(); while (estLettre(c) || estChiffre(c)) { lexeme[lonLex++] = c; c = lireCar(); } delireCar(c); return IDENTIF; } else { delireCar(c); return NEANT;} } Analyseur lexical L’utilisation des automates L’idée : on considère que lire un caractère peut faire passer d’un uploads/Industriel/ compil1-2-3.pdf