Remerciez-le!

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

Licence Universitaire Professionnelle G´ enie Logiciel & Th´ eorie des Langages

Licence Universitaire Professionnelle G´ enie Logiciel & Th´ eorie des Langages Techniques et outils pour la compilation Henri Garreta Facult´ e des Sciences de Luminy - Universit´ e de la M´ editerran´ ee Janvier 2001 Table des mati` eres 1 Introduction 3 1.1 Structure de principe d’un compilateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Analyse lexicale 5 2.1 Expressions r´ eguli` eres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 D´ eﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.2 Ce que les expressions r´ eguli` eres ne savent pas faire . . . . . . . . . . . . . . . . . . . . . 7 2.2 Reconnaissance des unit´ es lexicales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Diagrammes de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Analyseurs lexicaux programm´ es en dur . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.3 Automates ﬁnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Lex, un g´ en´ erateur d’analyseurs lexicaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.1 Structure d’un ﬁchier source pour lex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.2 Un exemple complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.3 Autres utilisations de lex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3 Analyse syntaxique 19 3.1 Grammaires non contextuelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.1 D´ eﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.2 D´ erivations et arbres de d´ erivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1.3 Qualit´ es des grammaires en vue des analyseurs . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1.4 Ce que les grammaires non contextuelles ne savent pas faire . . . . . . . . . . . . . . . . . 24 3.2 Analyseurs descendants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2.2 Analyseur descendant non r´ ecursif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.3 Analyse par descente r´ ecursive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Analyseurs ascendants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.2 Analyse LR(k) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.4 Yacc, un g´ en´ erateur d’analyseurs syntaxiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.1 Structure d’un ﬁchier source pour yacc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.2 Actions s´ emantiques et valeurs des attributs . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4.3 Conﬂits et ambigu¨ ıt´ es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1 4 Analyse s´ emantique 37 4.1 Repr´ esentation et reconnaissance des types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.2 Dictionnaires (tables de symboles) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2.1 Dictionnaire global & dictionnaire local . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2.2 Tableau ` a acc` es s´ equentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2.3 Tableau tri´ e et recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2.4 Arbre binaire de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.2.5 Adressage dispers´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 uploads/Management/ mi-compilation-techniques-outils.pdf