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 COURS, EXERCICES ET PROJETS DE PROGRAMMATION Professeur Faissal OUA

COMPILATION COURS, EXERCICES ET PROJETS DE PROGRAMMATION Professeur Faissal OUARDI Courriel : f.ouardi@um5r.ac.ma Licence Fondamentale en Sciences Mathématiques et Informatique Année universitaire 2020-2021 Contents Liste des ﬁgures ii Liste des tables et algorithmes iv Introduction 2 À l’attention des lecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Contexte d’apparition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Structure générale d’un compilateur . . . . . . . . . . . . . . . . . . . . 4 1 Rappel sur les langages formels 9 1.1 Fondements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Alphabet, mots et langages . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Grammaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Automates ﬁnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.1 Automates ﬁnis déterministes . . . . . . . . . . . . . . . . 15 1.4.2 Automates ﬁnis non déterministes . . . . . . . . . . . . . . 17 1.4.3 Automates ﬁnis non déterministes avec ε-transitions . . . . 19 1.5 Expressions régulières . . . . . . . . . . . . . . . . . . . . . . . . 21 1.6 Langages réguliers et propriétés de fermeture . . . . . . . . . . . . 22 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2 Analyse lexicale 28 2.1 Rôle de l’analyseur lexical . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Table des symboles . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3 Spéciﬁcation lexicale . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.1 Classes des unités lexicales . . . . . . . . . . . . . . . . . . 30 2.3.2 Expressions régulières notation étendue . . . . . . . . . . . 31 2.4 Reconnaissance des unités lexicales . . . . . . . . . . . . . . . . . 33 2.4.1 Quelque problèmes dans la reconnaissance des tokens . . . 33 2.4.2 Approche de reconnaissance . . . . . . . . . . . . . . . . . 34 2.4.3 Conventions . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.5 Implémentation d’analyseurs lexicaux . . . . . . . . . . . . . . . . 36 ii Contents 2.5.1 Analyseur lexical en dur . . . . . . . . . . . . . . . . . . . 36 2.5.2 Implémentation d’automates ﬁnis . . . . . . . . . . . . . . 36 2.5.3 Générateurs d’analyseurs lexicaux cas de Flex . . . . . . . . 40 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3 Analyse syntaxique 47 3.1 Rôle de l’analyseur syntaxique . . . . . . . . . . . . . . . . . . . . 47 3.2 Spéciﬁcation syntaxique . . . . . . . . . . . . . . . . . . . . . . . 47 3.2.1 Grammaires hors contexte et dérivation vs réduction . . . . 49 3.2.2 Qualités et formes particulières des grammaires . . . . . . 50 3.3 Analyse syntaxique descendante . . . . . . . . . . . . . . . . . . . 55 3.3.1 Analyse par la descente récursive . . . . . . . . . . . . . . 55 3.3.2 Analyse LL(k) . . . . . . . . . . . . . . . . . . . . . . . . 59 3.4 Analyse syntaxique ascendante . . . . . . . . . . . . . . . . . . . . 66 3.4.1 Analyse LR(0) . . . . . . . . . . . . . . . . . . . . . . . . 69 3.4.2 Analyse SLR . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.4.3 Analyse LR(1) canonique . . . . . . . . . . . . . . . . . . 75 3.4.4 Analyse LALR(1) . . . . . . . . . . . . . . . . . . . . . . 78 3.5 Générateurs d’analyseurs syntaxiques avec Bison . . . . . . . . . . 79 3.5.1 Partie déclaration C . . . . . . . . . . . . . . . . . . . . . . 81 3.5.2 Partie déclaration Bison . . . . . . . . . . . . . . . . . . . 81 3.5.3 Partie règles de la grammaire . . . . . . . . . . . . . . . . . 81 3.5.4 Partie code additionnel . . . . . . . . . . . . . . . . . . . . 82 3.6 Gestion des erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.6.1 Récupération en mode panique . . . . . . . . . . . . . . . . 85 3.6.2 Récupération au niveau du syntagme . . . . . . . . . . . . . 85 3.6.3 Production d’erreurs . . . . . . . . . . . . . . . . . . . . . 85 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 Travaux pratiques 90 Bibliography vi Liste des ﬁgures 1 Code héxadécimal du programme d’Eclid calculant le PGCD de deux entiers [29] . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Portion de code en C++ et l’équivalent en assembleur . . . . . . . . 3 3 Aire d’un triangle abc en Assembleur et Java [11] . . . . . . . . . . 4 4 Architecture générale d’un compilateur . . . . . . . . . . . . . . . 5 5 Programme source du PGCD en C [29] . . . . . . . . . . . . . . . 6 6 Quelques unités lexicales du code source PGCD . . . . . . . . . . 6 7 Arbre syntaxique d’une portion du code PGCD . . . . . . . . . . . 7 1.1 Illustration de la hiérarchie de Chomsky . . . . . . . . . . . . . . . 14 1.2 Exemple d’un AFD . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Exemple d’un AFN uploads/Management/ cours-compilation.pdf