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 Chapitre 1: Introduction à la compilation Chapitre 2: Analy

Compilation : Cours Chapitre 1: Introduction à la compilation Chapitre 2: Analyse lexicale Unités lexicales, modèles et lexèmes Chaînes et langages (définitions) Opérations sur les langages Expressions régulières Diagramme de transition Automates Finis Automates finis déterministes Automates avec sortie (Transducteurs) Lex : langage de spécification d’analyseurs lexicaux 1 Chapitre 3: Analyse syntaxique descendante Dérivation Qualités des grammaires Ambigüités Récursivité à gauche Factorisation à gauche Analyseurs descendants Principe Analyse par descente récursive Construction de la table d’analyse 2 3 Chapitre 4: Langages réguliers Grammaires régulières Graphe orienté d'une grammaire algébrique Lemme de l‘étoile pour les grammaires régulières Lemme de l‘étoile pour les langages réguliers : (critères de régularité)  Automates et grammaires régulières Transformation des grammaires algébriques Forme normale de Chomsky Forme normale de Greibach Forme presque Greibach ≪ ≫ 4 Chapitre 5: Analyse syntaxique ascendante Grammaires LR(k) Langages R0(A) R0(i) et grammaires LR(0) Construction de l’automate LR(0) Fonctionnement de l’analyseur Méthode des 0-items Grammaires SLR(1) Construction des tables d’analyse SLR(1) Algorithme d’analyse SLR(1) Grammaires LR(1) Construction des ensembles d’items LR(1) Construction des tables canoniques LR(1) Construction des tables d’analyse LALR(1) Bison et utilisation des grammaires ambigües Chapitre 1: Introduction à la compilation Les principes et techniques de compilation sont si généraux qu’ils utilisent les idées de la plupart des domaines fondamentaux de l’informatique: - Langages de programmation - Algorithmique - Architecture des machines - Théorie des langages - Génie logiciel 5 Les compilateurs Définition simplifiée: compilateur Programme source Programme cible Messages d’erreurs 6 Il existe des milliers de langages source Un langage source peut être un langage de programmation traditionnel: (Pascal, c, fortran) ou un langage spécialisé. Il existe presque autant de langages cible que source Un langage cible peut être un autre langage de programmation ou bien un langage machine Classes : compilateurs en une passe compilateurs multi-passes compilateurs-exécuteurs compilateurs optimisants Malgré cette diversité, on utilise généralement les mêmes techniques fondamentales pour construire un compilateur 7 Modèle de compilation par analyse et synthèse Deux parties: 1- Analyse: Partitionnement du programme source en constituants et création d’une représentation intermédiaire 2- Synthèse: Construction du programme cible à partir de la représentation intermédiaire De ces deux parties c’est la synthèse qui nécessite les techniques les plus spécialisées 8 Environnement du compilateur Préprocesseur Compilateur Assembleur Relieur-chargeur Programme cible en langage assemblage programme source Squelette du programme source Code machine translatable Code machine absolu Bibliothèque, fichiers objets translatables 9 Analyse du programme source En compilation l’analyse comprend trois phases: L’analyse linéaire: le flots de caractères formant le programme source est lu de gauche à droite et groupé en unités lexicales ; L’analyse hiérarchique: les unités lexicales sont regroupées hiérarchiquement dans des collections imbriquées; l’analyse sémantique: contrôle pour s’assurer que l’assemblage des constituants du programme a un sens. 10 Analyse lexicale Dans un compilateur l’analyse linéaire est appelée analyse lexicale. Exemple: position := initiale + vitesse * 60 Les caractères formants cette instruction sont regroupés dans les unités lexicales suivantes: 1 – l’identificateur position 2 – le symbole d’affectation := 3 – l’identificateur initiale 4 – le symbole plus 5 – l’identificateur vitesse 6 – le symbole de multiplication 7 – le nombre 60 Les espaces sont éliminés lors de l’analyse lexicale. 11 Analyse syntaxique Dans un compilateur l’analyse hiérarchique est appelée analyse syntaxique ou grammaticale. Les unités lexicales sont regroupées en structures grammaticales qui sont généralement représentées par des arbres syntaxiques. La structure hiérarchique d’un programme est généralement exprimée par des règles récursives. 12 Exemple : définition des expressions: 1 – tout identificateur est une expression 2 – tout nombre est une expression 3 – si e1 et e2 sont des expressions, alors: e1 + e2 est une expression e1 * e2 est une expression (e1) est une expression Les règles 1 et 2 sont des règles de base (non récursives) tandis que la règle 3 définit des expressions en terme d’opérateurs appliqués à d’autres expressions 13 position := initiale + vitesse * 60 1 : position , initiale et vitesse sont des expressions 2 : 60 est une expression 3 : vitesse * 60 est une expression 3 : initiale + vitesse * 60 est une expression Instruction d’affectation identificateur expression nombre expression expression expression expression identificateur identificateur position initiale vitesse 60 * := + Arbre syntaxique 14 On peut définir les instructions récursivement par des règles comme les suivantes 1 – si id1 est un identificateur et e2 est une expression alors id1 := e2 est une instruction 2 – si e1 est une expression et i2 est une instruction alors tant que (e1) faire i2 si (e1) alors i2 sont des instructions 15 Analyse sémantique Cette phase contrôle si le programme source contient des erreurs sémantiques et Collecte des informations destinées à la production de code Exemple: contrôle de type: position initiale vitesse 60 * := + Arbre abstrait position initiale vitesse 60 * := + EntierVersRéel L’analyse sémantique insère une conversion d’entier vers réel 16 Phases d’un compilateur Analyseur lexical Analyseur syntaxique Analyseur sémantique Générateur de code intermédiaire Optimiseur de code Générateur de code Programme source Programme cible Gestionnaire de la table des symboles Gestionnaire d’erreurs Organisation logique 17 Regroupement de phases Phase frontale: Front-End Dépend du langage source et comprend: l’analyse lexicale, l’analyse syntaxique la création de la table des symboles, l’analyse sémantique la création de code intermédiaire. Phase intermédiaire: Middle-End optimisation de code Phase finale : Back-End Dépend de la machine cible et du langage intermédiaire et comprend la production de code 18 19 20 Chapitre 2: Analyse lexicale Unités lexicales, modèles et lexèmes Chaînes et langages (définitions) Opérations sur les langages Expressions régulières Diagramme de transition Automates Finis Automates finis déterministes Automates avec sortie (Transducteurs) Lex : langage de spécification d’analyseurs lexicaux Chapitre 2: Analyse lexicale L’analyseur lexical constitue la première phase d’un compilateur. Sa tâche principale est de lire Les caractères d’entrée et de produire comme résultats des entités lexicales. analyseur lexical analyseur syntaxique Table des symboles Programme source Unité lexicale Obtenir prochaine unité lexicale Interaction entre un analyseur lexical et un analyseur syntaxique 21 On divise souvent les analyseurs lexicaux en deux phases successives: Phase de lecture: « Lecteur » (amélioration de l’interface avec l’utilisateur) - élimination des espaces et commentaires (blanc, \t, \n…) - relation entre les messages d’erreurs et le programme source - numérotation des lignes - copie du programme source en y intégrant les messages d’erreurs - implantation des mécanismes de préprocesseur Phase d’analyse lexicale: mécanismes plus complexes. 22 Unités lexicales, modèles et lexèmes Exemple: const pi = 3.1416; Unités lexicales Lexèmes description des Modèles const const const if if if Oprel < <= > >= <> = < <= > >= <> = id pi compte a1 lettre suivie de lettres ou de chiffres nb 3.1416 0 6.02E23 toute constante numérique littéral bonjour  tous caractères entre etsauf  23 Attributs des unités lexicales Exemple: Soit l’instruction fortran suivante: E = M * C ** 2 Les unités lexicales et les valeurs d’attributs sont données sous forme de couples: <id, pointeur vers l’entrée de la table des symboles associée à E> <op_affectation, > <id, pointeur vers l’entrée de la table des symboles associée à M> <op_multiplication, > <id, pointeur vers l’entrée de la table des symboles associée à C> <op_exponentiation, > <nb, valeur entière 2> 24 Spécification des unités lexicales Chaînes et langages (définitions) * Un alphabet est un ensemble fini de symboles. • Une chaîne (mot ou phrase) sur un alphabet est une séquence de symboles extraits de cet ensemble. * La chaine vide  est une chaine spéciale de longueur 0. * préfixe d’une chaine s: une chaine obtenue en supprimant un nombre quelconque (éventuellement nul) de symboles en fin de s suffixe d’une chaine s: une chaine obtenue en supprimant un nombre quelconque (éventuellement nul) de symboles en début de s sous-chaine de s: une chaine obtenue en supprimant un préfixe et un suffixe de s * tout préfixe et tout suffixe de s est une sous-chaine de s mais toute sous-chaine n’est pas forcement préfixe ou suffixe 25 * préfixe, suffixe ou sous-chaine propre de s: Toute chaine non vide x qui est respectivement, préfixe, suffixe ou sous-chaine de s telle que s  x • sous-suite de s: toute chaine obtenue en supprimant un nombre quelconque (éventuellement nul) de symboles non nécessairement consécutifs de s. * Un langage est un ensemble quelconque de chaines construites sur un alphabet fixé. exemples: {} ou  ensemble des programmes c syntaxiquement bien écrits phrases françaises grammaticalement correctes. * concaténation: soient a et b deux chaines: ab est la concaténation de a et de b s = s = s (est l’élément neutre pour la concaténation) * Exponentiation de chaine: s0 =  s1 = s Et pour i>0 si = si-1s 26 Opérations sur les langages Opération Définition Union L U M = {s | s  L ou s  M} concaténation LM = {st | s  L et t  M} fermeture de Kleene de L fermeture positive de L i i L L   uploads/Management/ part1-analyse-lexicale.pdf