(Ré)introduction à La Compilation - Unistra.fr
(Ré)introduction à la compilationCédric Bastoulcedric.bastoul@unistra.frUniversité de Strasbourg
Introduction(Ré)introduction à la compilationCompilateurDéfinition[Wikipédia]Un compilateur est un programme informatique qui transformeun code source écrit dans un langage (le langage source) en unautre langage (le langage cible)I Traducteur d’un code vers un autreI Humains et machines n’utilisent pas les mêmes langagesI Différents langages et niveaux de langages coexistentI Source et cible peuvent se confondre (pour optimiser)I Rapporteur des erreurs contenues dans le code sourceI Identificateurs mal formésI Constructions syntaxiques incorrectesI Expressions mal typées, etc.C2
Introduction(Ré)introduction à la compilationObjectifs de la présentationI (Re)découvrir l’intérêt de l’étude de la compilationI (Re)comprendre le fonctionnement et la construction descompilateursI (Re)prendre connaissance des outils fondamentaux pour letravail sur fichiers formatésI (Re)visiter les aspects ouverts au niveau rechercheC3
Introduction(Ré)introduction à la compilationNiveaux de langagesI Langages spécifiques (ex. : Matlab, Halide, Shell scripts.)I Langages spécialisés disposant de constructions (donnéeset/ou contrôle) spécifiques à un domaine en particulierI Langage de haut niveau (ex. : Java, C#, C/C .)I Langages généralistes adaptés aux algorithmes et donnéesévolués indépendamment de l’architecture cibleI Langages intermédiaires (ex. : GIMPLE, Bytecode Java.)I Langages internes aux compilateurs, communs à tous leslangages supportés et adaptés à leur optimisationI Langages d’assemblage (ex. : assembleur x86 ou ARM.)I Langage proche du langage machine mais où instructionset adresses sont remplacées par des noms lisiblesI Langages machine (ex. : x86, ARM.)I Suite binaire directement interprétable par l’architectureC4
Introduction(Ré)introduction à la compilationFormes de traductionI Compilation : traduction d’unprogramme en un autre telque pour toutes données enentrée, le résultat des deuxprogrammes est le mêmeProgramme sourceCompilateurDonnéesI Interprétation : utilisationd’un programme qui, étantdonné un programme sourceet des données, calcule lerésultat du programme sourceProgramme cibleProgramme sourceDonnéesI Machine virtuelle :compilation vers un langageintermédiaire puisinterprétation de ce langageExemples :C, C , InterpréteurProgramme sourceRésultatsExemples :Python,Javascript,Shell, RésultatsExemples :Java, C#, CompilateurDonnéesInterpréteurRésultatsC5
Introduction(Ré)introduction à la compilationCompilation vs interprétationI Le compilateur peut produire un code directementexécutable fonctionnant pour toutes les données en entréeI Processus de traduction complexeI Code produit généralement très efficaceI Optimisation principalement durant la compilation (statique)I L’interpréteur est le code directement exécutable quirecalcule le résultat à chaque foisI Processus de traduction simpleI Calcul du résultat généralement peu efficaceI Optimisation exclusivement durant l’exécution (dynamique)C6
Introduction(Ré)introduction à la compilationPourquoi étudier la compilation ?I Écrire un compilateur : rite de passage des informaticiensIIIISollicite des prérequis de la théorie à la technique avancéeApporte une compréhension générale de la programmationForme à des techniques et outils largement réutilisablesConstitue un projet conséquent et relativement difficileLangages formels- Alphabet, langages- Expressions régulières- Automates, grammaires- Algorithmique etstructures de données- Tables de hachage- Arbres, graphes- COMPILATEURSLangages deprogrammation- Structures de contrôle- Typage- Architecture- Jeu d’instructions- Assembleur- Hiérarchie mémoire- Systèmes d’exploitation- Organisation mémoire- Contexte d’exécution- C7
Introduction(Ré)introduction à la compilationExemples de problèmes pratiquesIIIIIIIIIPasser de fichiers d’entrée à des structures de donnéesPasser de structures de données à des fichiers de sortieFormater un code selon un style définiGénérer la documentation technique d’un code existantAppliquer une tâche répétitive à une base de codeFaire de la coloration syntaxique pour votre format préféréRepérer des constructions particulières dans un codeCréer le langage/format spécialisé idéal pour votre activitéRéutiliser l’infrastructure d’un compilateur existantI Pour compiler depuis votre langage particulierI Pour compiler vers votre architecture particulièreC8
Introduction(Ré)introduction à la compilationRéférencesC9
Introduction(Ré)introduction à la compilationQualités d’un compilateurPlus importantI Correction : le programme compilé doit avant toutcorrespondre au même calcul que le programme originalI Optimisation : le programme généré doit être rapideI Efficacité : le compilateur lui-même doit être rapideI Productivité : le compilateur doit signaler les erreurs et lesrisques de manière compréhensibleI Portabilité : le compilateur doit être extensible facilement àde nouveaux langages source et architectures ciblesI Prévisibilité : les optimisations doivent être cohérentes etprévisibles (hahaha)Moins importantC 10
Introduction(Ré)introduction à la compilationArchitecture des compilateurs modernesI Traitement organisé en phasesI Grande modularité pour maintenir, réutiliser et étendreFrontenddépendant du langageLangage1Analyselexicale 1Analysesyntaxique 1Langage2Analyselexicale 2Analysesyntaxique 2LangagenAnalyselexicale nAnalysesyntaxique nSuite decaractèresSuite d’unitéslexicales (tokens)Backenddépendant de l’architectureMiddle-endpartie communeAnalysesémantiqueGénérationde codeintermédiaireArbre deArbre desyntaxe abstraite syntaxe nde codefinal 1Codeobjet 1Générationde codefinal 2Codeobjet 2Générationde codefinal mCodeobjet mCodeintermédiaireCode binaireC 11
Introduction(Ré)introduction à la compilationPhases de la compilation1Analyse lexicale : traduit un flot de caractères en un flotd’unités lexicales représentant des suites de caractères2Analyse syntaxique : vérifie que la suite correspond à uneconstruction permise et produit l’arbre de syntaxe abstraite3Analyse sémantique : effectue les vérifications sur lasémantique du programme (typage, résolution des noms.)4Génération de code intermédiaire : traduit l’arbre desyntaxe abstraite en un code pour une machine abstraite5Optimisation : tente d’améliorer le code intermédiaire6Génération de code final : traduit le code intermédiairegénérique en code natif dépendant de l’architecture cibleC 12
Introduction(Ré)introduction à la compilationPrincipaux compilateurs libresI GCC, GNU Compiler CollectionIIIIICréé en 1987 par le projet GNULangages : C/C /Java/Objective-C/Fortran etc.Architectures cibles : plus de 20Représentations : GIMPLE, GENERIC, RTLPlus de 15 millions de lignes de code (Linux : 19)I Clang/LLVMIIIIICréé en 2005, rendu libre en 2007 par AppleLangages : C/C /Objective-C (CUDA/OpenCL)Architectures cibles : x86 et ARMReprésentations : LLVM-IR, BitcodePlus de 4 millions de lignes de codeC 13
Introduction(Ré)introduction à la compilationExemple : compilation du langage ArithI Langage source : « Arith » expressions arithmétiquesExemple de code source Arithx 12;y (5 x) * 10 3;print x y;I Langage cible : langage machine d’une architecture à pileInstructionPUSH MPOP MADDMULPRINTDescriptionEmpile la donnée à l’adresse MDépile et place la donnée dépilée à l’adresse MDépile deux données, fait leur addition et empile le résultatDépile deux données, fait leur multiplication et empile le résultatAffiche la donnée en sommet de pileC 14
Analyse lexicale(Ré)introduction à la compilationAnalyse lexicaleFrontenddépendant du langageLangage1Analyselexicale 1Analysesyntaxique 1Langage2Analyselexicale 2Analysesyntaxique 2LangagenAnalyselexicale nAnalysesyntaxique nSuite decaractèresSuite d’unitéslexicales (tokens)Backenddépendant de l’architectureMiddle-endpartie communeAnalysesémantiqueGénérationde codeintermédiaireArbre deArbre desyntaxe abstraite syntaxe nde codefinal 1Codeobjet 1Générationde codefinal 2Codeobjet 2Générationde codefinal mCodeobjet mCodeintermédiaireCode binaireC 15
Analyse lexicale(Ré)introduction à la compilationNotions de langages formelsVocabulaireI Alphabet : ensemble fini de symbolesI Mot : séquence finie de symboles d’un alphabet (vide : ε)I Langage : ensemble de motsExpressions rationnellesI Décrit un ensemble de mots possibles selon une syntaxeUn caractèrecle caractère c[c1 c2 .cn ] c1 ou c2 . ou cn[c1 c2 ] un caractère entre c1 et c2 comprisUne séquence de caractèresαβconcaténationα βalternativeα répétition zero ou plusieurs foisα répétition au moins une foisC 16
Analyse lexicale(Ré)introduction à la compilationAnalyse lexicaleL’analyse lexicale découpe le texte du code source en « mots »appelés « tokens » pour faciliter le travail de la phase suivanteI Décrit les tokens avec des expressions rationnellesI Utilise des automates finis pour les reconnaîtreI Générés à partir des expressions rationnellesI Ignore le texte superflu (commentaires, espaces)I Émet un couple (type, valeur) et réalise éventuellement desactions supplémentaires pour chaque tokenI Exemples : (identificateur, i) ; (nombre, 42)I Les types des tokens sont les symboles terminaux de lagrammaire du langageL’analyseur lexical est un automate fini pour l’union de toutes lesexpressions régulières définissant les tokensC 17
Analyse lexicale(Ré)introduction à la compilationReconnaissance des tokensTokenExpression rationnellemot clé printprintsymbole « » Automate0p1r200nombre0 [1-9][0-9]*i 0[a-zA-Z ][a-zA-Z 0-9]*0a.zA.Zn4t511.91identificateur320.91a.zA.Z 0.9C 18
Analyse lexicale(Ré)introduction à la compilationGénérateur d’analyseur lexical LexI Créé en 1975 par AT&T pour Unix, version libre Flex (1987)I Lit une spécification de l’analyseur et génére son code CI Utilise une spécification en 3 parties séparées par « %% »123Déclarations :I Déclarations C entre « %{ » et « %} »I Options et commandes spécifiques à LexI Définitions d’expressions rationnellesRègles de traduction : suite ordonnée de couples« regex {action} » où regex est une expressionrationnelle Lex et action est un bloc de code CFonctions auxilliaires : définitions de fonctions CStructure d’un ficher Lex (extension .l)/* Section des déclarations C et/ou Lex */%%/* Section des règles de traduction */%%/* Section des fonctions C */C 19
Analyse lexicale(Ré)introduction à la compilationFonctionnement de LexGénère une fonction yylex() lançant l’analyse lexicale sur lefichier pointé par la variable globale yyin de type FILE*I Reconnaît le plus long mot correspondant à une regexI Choisit la première regex dans la liste en cas d’égalitéI Exécute l’action associée à la regex, où on a accès à :I yytext : la chaine correspondant au mot reconnuI yyleng : la taille du mot reconnuI yylval : la valeur à associer au tokenI Affiche sur la sortie standard les caractères non reconnusI Termine dans un des cas suivants (hors erreur) :I le fichier est parcouru entièrementI une action effectue return (retourne le code du token)I la fonction yyterminate() est appeléeC 20
Analyse lexicale(Ré)introduction à la compilationExemple : compilation du langage ArithCode Lex pour l’analyse lexicale du langage Arith[code]%{#include stdio .h #include stdlib .h %}identifier [a -zA - Z ] [0 -9a -zA - Z ]*number[0 -9] %%print{ identifier }{ number }[() * ;][ \t\n].{{{{{{printf ("[L]printf ("[L]printf ("[L]printf ("[L]}printf ("[L]keyword :identifier :number :symbol :%s\n" , yytext ); }%s\n" , yytext ); }%s\n" , yytext ); }’%s ’\n" , yytext ); }ERROR : unknown character %s\n" , yytext ); }%%int main () {yylex ();return 0;}C 21
Analyse lexicale(Ré)introduction à la compilationL’analyse lexicale aujourd’huiI Dans la vie d’informaticien de tous les jours :I Extrêmement utileI Lex existe en Java (JLex), OCaml (ocamllex), Python (PLY)I Couteau suisse pour le traitement des textesI Dans la recherche :I 1960 : algorithme de conversion des expressionsrationnelles en automates finis déterministes parMcNaughton et YamadaI Théorie suffisamment solide et performanteI Recherche très active en amont au niveau des langagesC 22
Analyse syntaxique(Ré)introduction à la compilationAnalyse syntaxiqueFrontenddépendant du langageLangage1Analyselexicale 1Analysesyntaxique 1Langage2Analyselexicale 2Analysesyntaxique 2LangagenAnalyselexicale nAnalysesyntaxique nSuite decaractèresSuite d’unitéslexicales (tokens)Backenddépendant de l’architectureMiddle-endpartie communeAnalysesémantiqueGénérationde codeintermédiaireArbre deArbre desyntaxe abstraite syntaxe nde codefinal 1Codeobjet 1Générationde codefinal 2Codeobjet 2Générationde codefinal mCodeobjet mCodeintermédiaireCode binaireC 23
Analyse syntaxique(Ré)introduction à la compilationNotions de langages formelsI Grammaire : spécification de la structure syntaxique d’unlangage, composée d’un ensemble de productions mettanten jeu des terminaux et non-terminauxIIIITerminal : symbole élémentaire du langage (token)Non-terminal : variable représentant une liste de terminauxAxiome : non-terminal représentant le symbole de départProduction : règle de réécriture pour un non-terminalI Notée « partie gauche partie droite » oùI partie gauche est un non-terminalI partie droite est une liste de terminaux et non-terminauxI Dérivation : application d’une productionI Notée « partie gauche partie droite » oùI partie gauche est une liste de terminaux et non-terminauxI partie droite est la liste après application de la réécritureC 24
Analyse syntaxique(Ré)introduction à la compilationGrammaire d’expressions arithmétiquesEETTFFFIIIII E TTT*FF(E)identificateurnombreListe de 7 productionsAxiome : E, apparait en premier par conventionNon-terminaux : E, T, FTerminaux : , *, (, ), identificateur, nombreExemples de dérivations :E T F ( E ) ( T ) ( F ) ( nombre )C 25
Analyse syntaxique(Ré)introduction à la compilationAnalyse syntaxiqueL’analyse syntaxique cherche dans une grammaire une séquencede dérivations de l’axiome jusqu’à la liste de tokens en entréeI Décrit la syntaxe avec une grammaireI Utilise un automate à pile pour trouver les dérivationsI Généré à partir de la grammaireI Exécute éventuellement des actions à chaque dérivationI Chaque terminal et non-terminal peut porter une valeurI Peut construire l’arbre de syntaxe abstrait durant l’analyseI Émet une erreur de syntaxe si la séquence n’existe pasI Demande les tokens au fur et à mesure à l’analyseur lexicalCodesourcecaractère suivantrequête caractère suivantAnalyseurlexicaltoken suivantrequête token suivantAnalyseursyntaxiqueASTC 26
Analyse syntaxique(Ré)introduction à la compilationReconnaissance des listes de dérivationsTokencourantFlux d’entréeÉtatcourantPileAlgorithme d’analysedéterministeSortieTable d’analysecalculée à partir de lagrammaireI Automate à pile analysant le flux de tokens en entréeI L’algorithme et la table dépendent du type de grammaireI La table se construit directement à partir de la grammaireI La sortie dépend des actions associées aux dérivationsI Arbre de dérivation : représente une liste de dérivationsI Arbre de syntaxe abstraite : représente le code utileI Résultat direct (calcul, code intermédiaire.)C 27
Analyse syntaxique(Ré)introduction à la compilationGénérateur d’analyseur syntaxique YaccI Créé en 1970 par AT&T pour Unix, version libre Bison (1988)I Lit une spécification de l’analyseur et génére son code CI Utilise une spécification en 3 parties séparées par « %% »123Déclarations :I Déclarations C entre « %{ » et « %} »I Déclaration des tokens et du type de leurs valeursI Options et commandes spécifiques à YaccRègles de traduction : suite ordonnée de couples« production {action} » où production est uneproduction Yacc et action est un bloc de code CFonctions auxilliaires : définitions de fonctions CStructure d’un ficher Yacc (extension .y)/* Section des déclarations C et/ou Lex */%%/* Section des règles de traduction */%%/* Section des fonctions C */C 28
Analyse syntaxique(Ré)introduction à la compilationFonctionnement de YaccGénère une fonction yyparse() lançant l’analyse syntaxiquesur le fichier pointé par la variable globale yyin de type FILE*I Reconnaît les productions selon un mode « LALR »I ascendant : des feuilles de l’arbre de dérivation à l’axiomeI dérivation la plus à droite : cherche les dérivations del’élément le plus à droite des productions d’abordI Exécute l’action associée à la production, où on a :I : la valeur associée au non-terminal de gaucheI i : la valeur associée au ième élément de la partie droiteI Termine dans un des cas suivants (hors erreur) :I le fichier est parcouru entièrementI une action effectue returnI la macro YYABORT ou YYERROR ou YYACCEPT est utiliséeC 29
Analyse syntaxique(Ré)introduction à la compilationExemple : compilation du langage ArithI Le code Lex retourne les tokensI Code conforme si Yacc peut remonter à l’axiomeExtrait de code Yacc pour l’analyse syntaxique d’Arith[code]%%axiom :statement list{ printf ("[Y] Match : -) !\ n" ); return 0; };statement list :statement statement list{ printf ("[Y] stmt lst - stmt stmt lst \n" ); } statement{ printf ("[Y] stmt lst - stmt \n" ); };statement :IDENTIFIER ’ ’ expression ’; ’{ printf ("[Y] stmt - ID (% s) expr ;\ n" , 1 );} PRINT expression ’; ’{ printf ("[Y] stmt - PRINT expr ;\ n" ); };expression :expression ’ ’ expression{ printf ("[Y] expr - expr expr \n" ); } expression ’* ’ expression{ printf ("[Y] expr - expr * expr \n" ); } ’( ’ expression ’) ’{ printf ("[Y] expr - ( expr )\ n" ); } IDENTIFIER{ printf ("[Y] expr - ID (% s )\ n" , 1 ); } NUMBER{ printf ("[Y] expr - NUMBER (% d )\ n" , 1 ); };%%C 30
Analyse syntaxique(Ré)introduction à la compilationArbre de syntaxe abstraite (AST)Représentation de la structure syntaxique d’un code sous laforme d’une structure de données d’arbreI AST construit durant l’analysesyntaxique par les actionsI Chaque action peut créer unnouveau noeud (opérateur) oufeuille (opérande)I Yacc : construction depuis lesfeuilles vers la racinewhile (b ! 0) {if (a b)a a - b;elseb b - a;}return a;C 31
Analyse syntaxique(Ré)introduction à la compilationExemple : compilation du langage ArithI Les attributs des non-terminaux sont des noeuds de l’ASTI L’AST est construit durant l’analyse de YaccExtrait de code Yacc pour l’analyse syntaxique d’Arith[code]%%axiom :statement list{ parser ast 1 ; return 0; };statement list :statement statement list{ ast concat ( 1 , 2 ); } statement{ 1 ; };statement :IDENTIFIER ’ ’ expression ’; ’{ ast new statement ( 1 , 3 ); } PRINT expression ’; ’{ ast new statement ( NULL , 2 ); };expression :expression ’ ’ expression{ ast new operation ( ast type add , 1 , 3 );} expression ’* ’ expression{ ast new operation ( ast type mul , 1 , 3 );} ’( ’ expression ’) ’{ 2 ; } IDENTIFIER{ ast new identifier ( 1 ); } NUMBER{ ast new number ( 1 ); };%%C 32
Analyse syntaxique(Ré)introduction à la compilationL’analyse syntaxique aujourd’huiI Dans la vie d’informaticien de tous les jours :I Yacc en Java (CUP), OCaml (ocamlyacc), Python (PLY)I Passage de données formatées en structures de donnéesI Couteau suisse universel pour le traitement des textesI Dans la recherche :I 1962-1963 démonstration d’équivalence entre grammaire àcontexte libre et grammaires reconnues par les automatesà piles par Chomsky, Evey, et Schutzenberger(indépendamment)I Théorie solide et performante depuis ces annéesI Recherche active au niveau de l’arbre de syntaxe abstraiteI Représentation des langages parallèlesI Traitement rapide, extraction d’informationsC 33
Analyse sémantique(Ré)introduction à la compilationAnalyse séman
Introduction (Ré)introduction à la compilation Objectifs de la présentation I (Re)découvrir l’intérêt de l’étude de la compilation I (Re)comprendre le fonctionnement et la construction des compilateurs I (Re)prendre connaissance des outils fondamentaux pour le travail sur fichiers formatés I (Re)visiter les aspects ouverts au niveau recherche C 3
About this compilation This compilation This is a compilation of the Migration Act 1958 that shows the text of the law as amended and in force on 17 April 2019 (the compilation date). The notes at the end of this compilation (the endnotes) include information about amending laws and the amendment history of provisions of the compiled
Oracle Database 10g Release 2 delivers a new PL/SQL language feature: conditional compilation. The feature is elegant and easy to understand. Conditional compilation delivers many benefits and is well known in programming environments other than PL/SQL1. Broadly speaking, it allows
APES 315 Compilation of Financial Information contains material from International Standard on Related Services (ISRS) 4410 Compilation Engagements (2012) of the Handbook of the International Quality Control, Auditing, Review, Other Assurance,
Compilation for Scale-Up Architectures and Medium-Size Data Gregory Essertel, Ruby Tahboub, . level parallelization or network primitives. However, many workloads of practical importance are . by query compilation techniques from main-memory database systems, Flare incorporates a code genera- .
4 Stages of Compilation Process 1.Preprocessing (Those with # ) -Expansion of Header files (#include ) -Substitute macros and inline functions (#define ) 2.Compilation -Generates assembly language, .s file -Verification of functions usage using prototypes -Header files: Prototypes declaration 3.Assembling
Appendix 5.2: Exercise 5.2 on the compilation of supply and use tables 115 Appendix 5.3: Exercise 5.3 on balancing the table using RAS 116 Chapter 6. Evaluation of the three approaches to GDP and the use of benchmarking for revisions 117 A. Review of GDP compilation using the three approaches 117 The production approach 117
Langages de programmation et compilation Jean-Christophe Filli atre Cours 1 / 23 septembre 2016 Jean-Christophe Filli atre Langages de programmation et compilation 2016{2017 / cours 1 1. pr esentation du cours cours le vendredi, 8h30{10h30 en salle UV polycopi e ensemble des transparents TD le jeudi/vendredi, 10h30{12h15 en salle Info 4 NIR avec L elio Brun (lelio.brun@inria.fr) a partir d .
API CJ-4 developed as a result of changes in North American emissions regulation: – ten-fold reduction in NOx and particulate matter vs. October 2002 limits – exhaust after treatment (DPF, SCR) required for virtually all engines, and on-highway diesel sulfur reduced from 500 ppm to 15 ppm API CJ-4 specification highlights:
