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 Samir MBARKI Département d’Informatique, Faculté des Sciences, KENI

COMPILATION Samir MBARKI Département d’Informatique, Faculté des Sciences, KENITRA Année Universitaire : 2014-2015 S. MBARKI Compilation 2014-2015 1 / 184 Sommaire 1 Introduction à la compilation 2 Analyse lexicale 3 Analyse syntaxique 4 Analyse sémantique 5 Séries d’exercies S. MBARKI Compilation 2014-2015 2 / 184 Sommaire 1 Introduction à la compilation Pourquoi étudier la compilation ? Déﬁnition de Compilateur/Interpréteur Traitement effectué par un compilateur Phases d’un compilateur 2 Analyse lexicale 3 Analyse syntaxique 4 Analyse sémantique 5 Séries d’exercies S. MBARKI Compilation 2014-2015 3 / 184 Introduction à la compilation Pourquoi étudier la compilation ? Pour mieux comprendre les erreurs de compilation. Pour mieux comprendre le fonctionnement d’un compilateur. Les algorithmes et les outils de compilations sont repris dans d’autres domaines informatiques : ▶Traitement automatique des langages naturels (TALN). ▶Parser des documents (.XML). ▶GED (Gestion éléctronique de documents). Analyse lexicale : Scanner Analyse syntaxique : Parser S. MBARKI Compilation 2014-2015 4 / 184 Introduction à la compilation Rôle du compilateur Comment l’utilisateur communique avec l’ordinateur ? Compilateur/Interpréteur S. MBARKI Compilation 2014-2015 5 / 184 Introduction à la compilation Déﬁnition de compilateur Déﬁnition Le compilateur est un programme (fonction) qui prend en entrée un programme écrit dans un langage L1 et produit en sortie un programme équivalent écrit dans un langage L2. Exemple : C, C++, Java, ... S. MBARKI Compilation 2014-2015 6 / 184 Introduction à la compilation Déﬁnition d’interpréteur Déﬁnition L ’ interpéteur est un programme (fonction) qui prend en entrée un programme écrit dans un langage source L1 et produit en sortie le résultat d’exécution de ce programme. Exemple : Shell Unix, VB, PL/SQL, ... S. MBARKI Compilation 2014-2015 7 / 184 Introduction à la compilation Traitement effectué par un compilateur Exemple S. MBARKI Compilation 2014-2015 8 / 184 Introduction à la compilation Phases d’un compilateur Exercice Ecrire un programme qui afﬁche les statistiques d’un ﬁchier texte en comptant le nombre de mots, d’entiers, de réels et le nombre de caractères de ponctuation. S. MBARKI Compilation 2014-2015 9 / 184 Introduction à la compilation Analyse lexicale Le ﬂot de caractères est lu de gauche à droite. Les caractères formant un sens sont groupés en unités lexicales (Tokens). Les séparateurs (espace, tabulation, retour à la ligne) sont supprimés. Les commentaires sont ignorés. L ’analyseur lexical doit déterminer si chaque lexème (mot) est connu. Une unité lexicale est une suite de caractères ayant une signiﬁcation collective. S. MBARKI Compilation 2014-2015 10 / 184 Introduction à la compilation Analyse lexicale Exemple Soit l’instruction : Surf := base * hauteur / 2 Les unités lexicales sont : <Identiﬁcateur> Surf <Affectation> <Identiﬁcateur> base <Mult> <Identiﬁcateur> hauteur <Divis> <Nombre> 2 S. MBARKI Compilation 2014-2015 11 / 184 Introduction à la compilation Analyse syntaxique L ’unité syntaxique constitue l’arbre syntaxique. Appliquer la grammaire du langage source pour vériﬁer la syntaxe du programme source. La grammaire du langage source est formé par un ensemble de règle de production. S. MBARKI Compilation 2014-2015 12 / 184 Introduction à la compilation Analyse syntaxique Exemple <Identiﬁcateur> <Affectation> <Identiﬁcateur> <Mult> <Identiﬁcateur> <Divis><Nombre> S. MBARKI Compilation 2014-2015 13 / 184 Introduction à la compilation Analyse sémantique Vériﬁe si le programme source contient des erreurs sémantiques. Collecte des informations de type pour la génération de code cible. Parmi les tâches de l’analyseur sémantique : ▶Vériﬁcation de type. ▶Vériﬁcation des incompatibilités de types. ▶Conversion implicite de type. Exemple conversion implicite de type : 2 →2.0 S. MBARKI Compilation 2014-2015 14 / 184 Sommaire 1 Introduction à la compilation 2 Analyse lexicale Introduction et spéciﬁcation Concepts et outils L ’outil Flex 3 Analyse syntaxique 4 Analyse sémantique 5 Séries d’exercies S. MBARKI Compilation 2014-2015 15 / 184 Analyse lexicale I- Introduction et spéciﬁcation L ’analyseur lexical (Scanner) fusionne les caractères lus dans le code source en groupes de mots qui forment logiquement des unités lexicales (tokens) du langage. S. MBARKI Compilation 2014-2015 16 / 184 Analyse lexicale Interaction avec les autres modules S. MBARKI Compilation 2014-2015 17 / 184 Analyse lexicale Terminologie Trois termes majeurs sont utilisés en analyse lexicale : ▶Unité lexicale : un couple constitué d’un nom d’unité lexicale et d’une valeur d’attribut optionnelle (facultatif). ▶Motif : est une description de la forme que les lexèmes d’une unité lexicale peuvent prendre. Il peut être simple ou complexe. ▶Lexème : est une séquence de caractères dans le programme source qui est reconnue par le motif d’une unité lexicale. Exemple S. MBARKI Compilation 2014-2015 18 / 184 Analyse lexicale Terminologie Exemple Symboles (Unités lexicales) : ▶Identiﬁcateur, Chaine, Constante numérique. ▶Mot-clé (IF , WHILE, DO, ...) ▶Opérateur (symbole spéciale) : <, >=,<=, ==, =, ... Analyser les phrases suivantes : ▶A+15+B => A, +, 15, B ▶test+3148 => test, +, 3148 S. MBARKI Compilation 2014-2015 19 / 184 Analyse lexicale Terminologie Input de l’analyseur lexical : WHILE A>3*B DO A<A-1 END Output de l’analyseur lexical : Une variable C de tye couleur qui peut prendre les valeurs : VERT, BLEU, ROUGE, JAUNE. Affecter à la variable la valeur rouge. typedef enum {VERT, BLEU, ROUGE, JAUNE} couleur; couleur C; C = ROUGE; //C=2 S. MBARKI Compilation 2014-2015 20 / 184 Analyse lexicale Terminologie Question Comment déﬁnir formellement les symboles d’un langage ? Réponse Les meilleurs modèles déﬁnissant les unités lexicales auxquelles appartiennent les lexèmes sont les langages réguliers. Il existe deux façons de décrire les langages réguliers : ▶Les expressions régulières ▶Les automates ﬁnis S. MBARKI Compilation 2014-2015 21 / 184 Analyse lexicale Concepts et outils Alphabet : On appelle alphabet Σ un ensemble ﬁni non vide. Les elements de l’alphabet s’appellent symboles. Exemple Σ = {a, b, ..., z} Σ = {α,β,...,ϕ,+,∗,−,/} Mot : Un mot est une suite de symboles appartenant à un alphabet Σ. Exemple Sur l’alphabet Σ = {0, 1}, on peut construire les mots : 101001, 11, 100. ε est le mot vide. La concaténation de deux mots est un mot. S. MBARKI Compilation 2014-2015 22 / 184 Analyse lexicale Langage formel Exemple (suite) Soit Σ = {0, 1}, si α = 100 et β = 1010 alors αβ = 1001010. α2 = αα = 100100 α3 = ααα = 100100100 Langage formel : Un langage sur un alphabet Σ est un ensemble de mots construits sur Σ. Exemple Σ∗est l’ensemble de tous les mots construits sur Σ. Remarque Un langage construit sur un alphabet Σ est une partie de Σ∗. On distingue deux langages particuliers : ∅, Σ. S. MBARKI Compilation 2014-2015 23 / 184 Analyse lexicale Exemple de langages Exemple de langages soit Σ={a, .., z} L0 = {a}. L1 = {aa,ab}. L2 = {αaα/α ∈Σ∗} = {a, bab, cdacd, ...}. L3 = {α ∈Σ∗/|α|a <= 10} : l’ensemble de tous les mots dont le nombre d’occurences de a <= 10. |.|x∈Σ : Σ∗→IN , |.|x calcule le nombre d’occurences de x dans un mot. S. MBARKI Compilation 2014-2015 24 / 184 Analyse lexicale Opérations sur les langages formels L’union. ▶L1 S L2 = {x / x ∈L1 ou x ∈L2} L’intersection. ▶L1 T L2 = {x / x ∈L1 et x ∈L2} La différence. ▶L1 - L2 = {x / x ∈L1 et x / ∈L2} ▶¯ L1 =Σ∗−L1 La concaténation. ▶L1L2 = {xy / x ∈L1 et y ∈L2} ▶Ln = LL.....L | {z } n fois ▶L1={a, b, c} ; L2={1, 2} ▶L1L2={a1, a2, b1, b2, c1, c2} ▶L2L1={1a, 1b, 1c, 2a, 2b, 2c} S. MBARKI Compilation 2014-2015 25 / 184 Analyse lexicale Fermeture de Kleene Soit L un langage : L∗=S K>=0 Lk Exemple L1={a, b} L∗ 1=L0 1 SL1 1 SL1 2 SL1 3 S ... ={ε, a, b, aa, ab, ba, bb, ...} L+ est appelé fermeture de Kleene positive de L : L+=L∗-{ε} Proposition. Les identités suivantes sont vraies pour tous les langages (X, Y, Z) : X(YZ)=(XY)Z Xε=εX=X X(YSZ)=XYSXZ (XSY)Z=XZSYZ (X ∗)∗= X ∗ S. MBARKI Compilation 2014-2015 26 / 184 Analyse lexicale Langages réguliers Déﬁnition Un langage régulier L sur un alphabet Σ est déﬁni récursivement comme suit : {ε} est un langage régulier sur Σ. Soit a ∈Σ alors {a} est un langage régulier sur Σ . Si R est un langage régulier, alors Rk et R∗sont des langages réguliers sur Σ . Si R1 et R2 sont deux langages réguliers alors R1 S R2 et R1R2 sont des langages réguliers. S. MBARKI Compilation 2014-2015 27 / 184 Analyse lexicale Les expressions régulières (ER) Soit Σ un alphabet, les expressions régulières et les langages qu’ils décrivent sont déﬁni comme suit : Soit a ∈Σ, alors a est une ER qui décrit le langage {a} . ε est une ER qui décrit le langage {ε} . Si α et β sont deux ER décrivant les langages A et B alors : α + β ( α | β) est une ER qui décrit le langage A S B . - αβ est une ER qui décrit le langage AB. - α∗est une ER qui décrit le langage A∗. S. MBARKI Compilation 2014-2015 28 / 184 Analyse lexicale Les expressions régulières (ER) Exemple d’ER Numérique : (0|1|2|...9) Alphabétique : (a|b|c|...|z|A|...Z) Opérateur uploads/Management/ compilation-2.pdf