Remerciez-le!

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

Cours compilation 2011-2012 1 D. Barthou Cours de compilation Denis Barthou dba

Cours compilation 2011-2012 1 D. Barthou Cours de compilation Denis Barthou dbarthou@enseirb.fr Cours compilation 2011-2012 2 D. Barthou Sujets abordés en compilation ●Description d'un compilateur ●Description des langages de programmation ●Analyse de code, optimisation ●Méthodes de typage ●Problèmes théoriques (graphes, langages) et pratiques (faire un compilateur) Cours compilation 2011-2012 3 D. Barthou Sujets abordés en compilation ●Description d'un compilateur ●Description des langages de programmation ●Analyse de code, optimisation ●Méthodes de typage ●Problèmes théoriques (graphes, langages) et pratiques (faire un compilateur) Dans ce module: ●Cours et TD sur les aspects théoriques, sur les méthodes de compilation ●Scéances pratiques sur les outils de compilation, sur l'asm x86 ●Projet de compilation Cours compilation 2011-2012 4 D. Barthou 1- Introduction Intérêt de la compilation ●Outil incontournable, quelque soit le langage ●Meilleure connaissance des compilateurs → meilleure programmation ●Techniques de compilation réutilisables dans nombreux contextes (notamment analyse de code) ●Sujet actif de recherche: – Langages pour le parallélisme, pour les machines avec accélérateurs matériels – Domain Specific Languages – Compilation pour l'embarqué Cours compilation 2011-2012 5 D. Barthou 1- Introduction Description d'un compilateur ●Definitions: Un compilateur est un programme qui prend en entrée un programme et le transforme en un autre programme. Un interpréteur est un programme qui prend en entrée un programme et l'exécute. Le compilateur est un traducteur. L'interpréteur une machine virtuelle. Cours compilation 2011-2012 6 D. Barthou 1- Introduction Description d'un compilateur ●Definitions: Un compilateur est un programme qui prend en entrée un programme et le transforme en un autre programme. Un interpréteur est un programme qui prend en entrée un programme et l'exécute. Le compilateur est un traducteur. L'interpréteur une machine virtuelle. ●Langages compilés ou interprétés ? C, Java, perl, lisp, sql, assembleur ●Compilateur, interpréteur ou autre chose ? LaTeX, make, visualiseur postscript, matlab Cours compilation 2011-2012 7 D. Barthou 1- Introduction Objectifs possibles du compilateur ●Préserver la sémantique (obligatoire) ●Générer un code le plus rapidement possible ●Trouver toutes les erreurs lexicales, syntaxiques et sémantiques – Prouver que le code généré est correct, que le code d'entrée respecte une spec. ●Générer un code – S'exécutant le plus rapidement possible – Consommant le moins d'énergie possible – Le plus petit possible Cours compilation 2011-2012 8 D. Barthou 1- Structure du compilateur Analyse lexicale Analyse syntaxique Analyse sémantique Génération de representation intermédiaire (RI) Optimisation de RI Génération de code Optimisation Décomposition en couches ●Analyse lexicale: lit le programme, reconnait chaque mot ●Analyse syntaxique: vérifie la grammaire ●Analyse sémantique: vérifie le sens du programme (ex: types) ●RI: une interface séparant les front-end, middle-end et back- end du compilateur Exécutable langage B Exécutable langage A Cours compilation 2011-2012 9 D. Barthou 1- Structure du compilateur Analyse lexicale Analyse syntaxique Analyse sémantique Génération de representation intermédiaire (RI) Optimisation de RI Génération de code Optimisation Décomposition en couches Changement de langage d'entrée ●On ne change que le front-end Exécutable langage B Exécutable langage C Cours compilation 2011-2012 10 D. Barthou 1- Structure du compilateur Analyse lexicale Analyse syntaxique Analyse sémantique Génération de representation intermédiaire (RI) Optimisation de RI Génération de code Optimisation Décomposition en couches Changement de langage cible ●On ne change que le back-end Exécutable langage D Exécutable langage A Cours compilation 2011-2012 11 D. Barthou 1- Structure du compilateur Analyse lexicale Analyse syntaxique Analyse sémantique Génération de representation intermédiaire (RI) Optimisation de RI Génération de code Optimisation Exemples de décomposition Gcc: ●Langage d'entrée: C, C++, Java, Fortran, … ●Asm cible: x86 (multiples variantes), arm, mips, ... Deux RI bien distinctes ●Tree-ssa (gimple): plutot haut niveau ●RTL: pour la génération de code asm (lisp-like) Exécutable langage B Exécutable langage A Cours compilation 2011-2012 12 D. Barthou 1- Bibliographie pour le cours ●Compilateurs, principes, techniques et outils, Aho, Sethi et Ullman, Interéditions ●Modern Compiler Design, Grune, Bal, Jacobs, Langendoen, Wiley ●Modern Compiler, Implementation in C. Appel, Ginsburg, Cambridge U. Press Pour aller plus loin ●Optimizing compilers for modern architectures, Allen, Kennedy, Morgan-Kaufman ●Advanced compiler design implementation, Muchnick, Morgan- Kaufman Cours compilation 2011-2012 13 D. Barthou 2- Analyse lexicale Objectif: ●Lecture du programme d'entrée ●Reconnaissance des lexèmes (tokens): éléments constitutifs du langage, mots clés, noms de variables, symboles de ponctuation... Analyse lexicale Analyse syntaxique Analyse sémantique Génération de representation intermédiaire (RI) Optimisation de RI Génération de code Optimisation Exécutable langage B Exécutable langage A Cours compilation 2011-2012 14 D. Barthou 2- Langages réguliers Cadre théorique pour l'analyse lexicale ●Alphabet: ensemble fini de symboles (lettres) ●Mot: suite finie de lettres, operation: concaténation. Mot vide: ϵ ●Langage: ensemble de mots ●Expressions régulières (rappels) – Décrivent les langages réguliers (ou rationnels) – Formées avec les opérateurs *, | , la concaténation et ϵ Cours compilation 2011-2012 15 D. Barthou 2- Langages réguliers Automates réguliers ●Reconnaissent les expressions régulières ●Distinction importante: automates déterministes et automates non- déterministes ●Schémas d'equivalences Cours compilation 2011-2012 16 D. Barthou 2- Automate fini déterministe Exemple d'automate fini déterministe ●Reconnaissance de “lol” Cours compilation 2011-2012 17 D. Barthou 2- Automates finis Exemple d'automate fini non déterministe ●Reconnaissance de “skate” Cours compilation 2011-2012 18 D. Barthou 2- Expression regulière → Automate Construction de Thompson Méthode simple de construction d'automate non déterministe ●Construction de R1 . R2 Cours compilation 2011-2012 19 D. Barthou 2- Expression régulière → Automate ●Construction de R1 | R2 Cours compilation 2011-2012 20 D. Barthou 2- Expression régulière → Automate ●Construction de R* Cours compilation 2011-2012 21 D. Barthou 2- Déterminisation de l'automate Algo de déterminisation On part d'un automate (N,Σ,Δ,n0,NF) On construit un automate (Q,Σ,δ,q0,QF) ● Les états du nouvel automate sont des ensembles d'état de l'ancien. ●Algo par calcul de point fixe ●Complexité exponentielle au pire. q0 = ϵ-fermeture(n0) Initialiser Q avec q0 Worklist = q0 Tant que (Worklist != empty) Choisir qi dans Worklist Pour chaque caractère c Є Σ q = ϵ-fermeture(δ(qi,c)) δ(qi,c) = q Si q pas dans Q, ajouter q à Worklist et Ajouter q à Q QF est l'ensemble des états contenant un état final de NF Cours compilation 2011-2012 22 D. Barthou 2- Minimisation de l'automate Algo de minimisation ●Part d'une partition des états: – Etats finaux, – Etats non finaux ●Raffine la partition en séparant les états qui n'ont pas le même comportement ●Algorithme par calcul de point fixe ●Exemple complet Cours compilation 2011-2012 23 D. Barthou 2- Génération de lexèmes Objectif de l'analyseur lexical: ●Reconnaissance de tous les lexèmes du langage ●Un lexème: – Un type (verbe, nom, mot clé, identificateur, …) – Une valeur (manger, lion, for, toto, ...) ●Action à chaque reconnaissance de lexème: transmettre le lexème pour l'analyse syntaxique Difficultés: ●Lexèmes prefixes d'autres: on prend les plus longs ●Ambiguité entre lexèmes: résolution contextuelle (avec analyse syntaxique) ou préférence donnée à un type de lexème Cours compilation 2011-2012 24 D. Barthou 3- Analyse syntaxique Objectifs: ●Vérifier que le programme est bien formé, appartient au langage de programmation → la grammaire du langage peut générer ce programme ●Si ok, génère un arbre syntaxique ●Sinon, génére des messages d'erreurs appropriés Analyse lexicale Analyse syntaxique Analyse sémantique Génération de representation intermédiaire (RI) Optimisation de RI Génération de code Optimisation Exécutable langage B Exécutable langage A Cours compilation 2011-2012 25 D. Barthou 3- Grammaires algébriques Grammaire: ●Variables (non terminaux) et symboles terminaux (lexèmes) ●Symbole initial (S) ●Règles de production du type A → ω Avec ω un mot de variables/lexèmes Cours compilation 2011-2012 26 D. Barthou 3- Grammaires algébriques Grammaire: ●Variables (non terminaux) et symboles terminaux (lexèmes) ●Symbole initial (S) ●Règles de production du type A → ω Avec ω un mot de variables/lexèmes Exemple: S → E E → E + E| E – E|E * E|T T → id | n | (E) Avec ●S,E,T les variables de la grammaire, ●+,-,*,(,),$,id,n les lexèmes de la grammaire Cours compilation 2011-2012 27 D. Barthou 3- Grammaires algébriques Rappels: Dérivation: application d'une règle à un mot Ex: id + E * T → id + T * T Arbre de dérivation: représentation des dérivations sous forme d'arbre. Les feuilles: les lexèmes. Racine: S Grammaire ambigüe: il existe un mot reconnu par la grammaire, avec 2 arbres de dérivation Ex: n + n * n Dérivation à gauche/droite: Application d'une règle sur la variable la plus à gauche/droite du mot. Ex: n + E + T*id → n + T + T*id Cours compilation 2011-2012 28 D. Barthou 3- Reconnaissance de mots Reconnaissance de mots: ●Construction d'automate à pile ●Grammaire algébrique → automate à pile non déterministe (vu l'année dernière) Cours compilation 2011-2012 29 D. Barthou 3- Reconnaissance de mots Reconnaissance de mots: ●Construction d'automate à pile ●Grammaire algébrique → automate à pile non déterministe (vu l'année dernière) Problème: ●Pas d'algo de déterminisation d'automates à pile ! ●Certains langages algébriques pas reconnus par automates déterministes... Solution: ●Restreindre les langages à des langages non ambigus ●Sous classe des langages algébriques pour avoir algo de reconnaissance efficaces. – Deux classes d'algo: analyse descendante et ascendante Cours compilation 2011-2012 30 D. Barthou 3- Analyse descendante Principe: ●Partir de S, ●Trouver la règle à appliquer en fonction de la prochaine lettre (lexème) à lire Classe LL d'analyse: ●Left to right parsing, leftmost derivation Exemple uploads/Industriel/ cours-compilation.pdf