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 de compilation 1 Introduction Un compilateur est un logiciel de traductio

Cours de compilation 1 Introduction Un compilateur est un logiciel de traduction d’un langage source vers un langage cible. D’ordi- naire le langage source est un langage de programmation ´ evolu´ e, comme C++ ou Java par exemple, le langage cible un code machine pr´ evu pour programmer un ordinateur en particulier. Un compilateur contient plusieurs modules : – analyseur lexical – analyseur syntaxique – analyseur s´ emantique – g´ en´ erateur de code interm´ ediaire – optimiseur de code – g´ en´ erateur de code Il g` ere une table des symboles, d´ etecte et signale un ensemble d’erreurs ` a chaque niveau d’analyse et produit le code qui servira ` a la programmation. Le compilateur entre dans un processus d’´ elaboration des programmes et n’est qu’un des rouages permettant de construire un programme. Nous distinguons le compilateur des outils qui sont utilis´ es en amont : Editeur, Pr´ eprocesseur, et des outils qui sont utilis´ es en aval : Assembleur, lieur, chargeur. Sources →Pr´ eprocesseur →Programme source →Compilateur →programme cible → Assembleur →Lieur-chargeur Fig. 1 – Contexte du compilateur Les phases et le r´ esultat peuvent ˆ etre diﬀ´ erents d’un compilateur ` a un autre : – Interpr´ etation plutˆ ot que compilation proprement dite : Postscript, Shell, HTML – Production de code portable (bytecode) pour machine virtuelle, et non de code d´ edi´ e ` a une machine en particulier : P-code, java, NET – Langages sources plus ou moins structur´ es. L’assembleur par exemple est tr` es peu structur´ e, il pr´ esente des instructions machines, des directives, des ´ etiquettes. – Optimisations plus ou moins pouss´ ees – Analyse des erreurs plus ou moins pouss´ ees Exemple : PGCD int PGCD( int a , int b) { 1 while (b != a ) { i f ( a > b) a=a−b ; else { /∗Echanger a et b ∗/ int tmp ; tmp=a ; a=b ; b=tmp ; } return a ; } 1. Analyse lexicale : commentaires, mots r´ eserv´ es, constantes, identiﬁcateurs 2. Analyse syntaxique : Transforme le code en arbre fonction pgcd type int parametres type int type int contenu while != b a if return SUCC > b a = a - a b Fig. 2 – arbre syntaxique 3. Analyse s´ emantique, g´ en´ eration de code interm´ ediaire : – Types : 2 PGCD int × int →int a int b int – Instructions : SUCC(WHILE(TEST(̸=, a, b), IF(TEST(<, a, b), AFF(a, OP(−, a, b)), SUCC(BLOC(V AR(tmp, int), AFF(tmp, a), SUCC(AFF(a, b), AFF(b, tmp)))))), RETURN(a)) 2 Analyse lexicale 2.1 Entit´ es lexicales (token) D´ eﬁnition par des expressions rationnelles L’analyseur est un automate ﬁni dont les ´ etats terminaux sont associ´ es ` a des actions 2.2 Expression rationnelle Soit un alphabet A, un ensemble rationnel est : 1. Ensemble ﬁni de mots 2. Concat´ enation d’ensembles rationnels R1R2 3. It´ eration d’ensembles rationnels R⋆ 4. Union d’ensembles rationnels R1 ∪R2 Exemple : Alphabet = [A-Z][a-z][0-9]"_" Lettre = [A-Z][a-z] Chiﬀre = [0-9] Identiﬁcateur = Lettre (Lettre ∪Chiffre ∪"_")⋆ Entier = {0} ∪[1-9] (Chiffre)⋆ 2.3 Automate Un analyseur lexical s’impl´ emente ` a l’aide d’un automate 2.4 JFLEX Construit un automate qui applique les actions ` a eﬀectuer sur chaque entit´ e d´ ecrite par les expressions rationnelles. Fichier ﬂex →JFlex →Lexer.java →Java →Lexer.class java JFlex pseudocode.jﬂex javac Lexer.java java Lexer programme.pseudocode Un exemple 3 f i o Identiﬁcateur Lettre u mot clef r Lettre mot clef f Lettre Lettre ChiffreUnderscore Lettre Lettre n Lettre Lettre c Lettre t Lettre i Lettre o Lettre mot clef n Fig. 3 – fsa 4 import java.io.*; %% %public %class Lexer %standalone %8bit %{ StringBuffer str = new StringBuffer(); %} LineTerminator = \r|\n|\r\n InputCharacter = [^\n\r] WhiteSpace = {LineTerminator}|[ \f\t] %% /* Keywords */ if {System.out.printf("KEYWORD:%s\n", yytext());} else {System.out.printf("KEYWORD:%s\n", yytext());} /* Operators */ "+" {System.out.printf("OPERATOR:%s\n", yytext());} /* Literals */ /* Comments and whitespace */ {WhiteSpace} {/* Nothing */} 3 Analyse syntaxique Quelques rappels exemple avec ETF, a + a ∗(a + a) E →E + T E →T T →T * F T →F F →( E ) F →IDENTIFIER arbre de d´ erivation dessiner D´ erivation 5 a + b ∗(c + d) F + b ∗(c + d) T + b ∗(c + d) E + b ∗(c + d) E + F ∗(c + d) E + T ∗(c + d) E + T ∗(F + d) E + T ∗(T + d) E + T ∗(E + d) E + T ∗(E + F) E + T ∗(E + T) E + T ∗(E) E + T ∗F E + T E M´ ethode descendante M´ ethode ascendantes M´ ethodes tabulaires – Principe de l’analyse LR 1. E →• E + T E →• T T →• T * F T →• F F →• ( E ) F →• IDENTIFIER 2. F →IDENTIFIER • 3. F →( • E ) E →• E + T E →• T T →• T * F T →• F F →• ( E ) F →• IDENTIFIER (a) F →( E • ) E →E • + T (b) E →T • T →T • * F 4. E →E • + T 6 5. E →T• T →T • * F 6. T →F • . . . – Arbre d’analyse syntaxique D´ erivation gauche Probl` eme d’ambigu¨ ıt´ e Revenons ` a la grammaire ifthenelse instr →si expr alors instr instr →si expr alors instr sinon instr autre analyse de si E1 alors S1 sinon si E2 alors S2 sinon S3 On pr´ ef` ere le ”alors” le plus proche (p.201) Grammaire ´ equivalente : instr →instr close instr →instr non close instr close →si expr alors instr close sinon instr close autre instr non close →si expr alors instr instr non close →si expr alors instr close sinon instr non close – Notions de grammaire attribu´ ee chaque production A →α poss` ede un ensemble de r` egles b = f(c1, c2, . . . , ck) f fonction b attribut synth´ etis´ e de A b attribut h´ erit´ e d’un des symboles en partie droite de la production c1, c2, . . . , ck attributs de symboles quelconques de la production L →E imprimer(E.val) E →E + T E.val = E1.val + T.val E →T E.val = T.val T →T * F E.val = E1.val × T.val T →F T.val = F.val F →( E ) F.val = E.val F →IDENTIFIER F.val = IDENTIFIER.vallex – Principe d’arbre de syntaxe abstraite Attributs : Valeurs attach´ ees – CUP 7 4 Arbres de syntaxe abstraite – D´ eﬁnition – Classes abstraites – Langage C 5 Types, v´ eriﬁcation de type – Environnement G B Z G B A C Fig. 4 – fonction ajouter (x :nom, t : type , u : Arbre ) : Arbre d´ ebut si (u== NULL) retourner new Arbre (x , t , NULL, NULL) ; sinon si (x < u .nom) retourner new Arbre (u .nom, u . type , ajouter (x , t , u . gauche ) , u . droit ) ; sinon si (x > u .nom) retourner new Arbre (u .nom, u . type , u . gauche , ajouter (x , t , u . droit ) ) ; sinon si (x==u .nom) retourner new Arbre (u .nom, u . type , u . gauche , u . droit ) ; fin – Repr´ esentation des types 1. Type de base (bool´ een, caract` ere, entier, r´ eel), void, error 2. Nom de type 8 3. Constructeur : (a) Tableaux (I, T) (b) Produits (c) Structures (d) Pointeurs (e) Fonctions 4. Variables de type Lors de la compilation : statique, lors de l’ex´ ecution : dynamique langages fortement typ´ e : programmes sans erreur de type. Graphe de repr´ esentation des expressions de type Par un arbre si pas types r´ ecursifs ➔ × caractère caractère pointeur entier Fig. 5 – struct { int x ; int y ; int z [ ] ; } – Types du langage pseudo C P →D ; E D →D ; D | id : T T →char | int | T[] | T* E →litt´ eral | integer | identiﬁer E mod E | E[E] | *E – V´ eriﬁcation dans les expressions 9 array array array int Fig. 6 – int a[][][] ; struct array int int int Fig. 7 – 10 5.1 Equivalence des expressions de type Dans quelle mesure peut-on dire que deux types sont ´ equivalents ? Solution simple : fonction Equiv ( s , t ) : bool´ een d´ ebut si s et t sont l e mˆ eme type de base alors retourner vrai sinon si s = tableau (s1 , s2 ) et t = tableau (t1 , t2 ) alors retourner Equiv (s1 , s2 ) et Equiv (t1 , t2 ) sinon si s = s1 uploads/S4/ compilation-cours-en-17-pages.pdf