Remerciez-le!

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

Th´ eorie des langages Th´ eorie des langages et compilation Elise Bonzon http:

Th´ eorie des langages Th´ eorie des langages et compilation Elise Bonzon http://web.mi.parisdescartes.fr/∽bonzon/ elise.bonzon@parisdescartes.fr 1 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Th´ eorie des langages et compilation Structure d’un compilateur Analyse lexicale Analyse syntaxique Analyse s´ emantique Conclusion 2 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Th´ eorie des langages et compilation Structure d’un compilateur Analyse lexicale Analyse syntaxique Analyse s´ emantique Conclusion 3 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Un compilateur, c’est quoi? Un compilateur est un programme qui prend en entr´ ee une donn´ ee textuelle source (programme, donn´ ee xml, ﬁchier de conﬁguration, etc) la reconnaˆ ıt (l’analyse) pour v´ eriﬁer sa correction ´ emet ´ eventuellement un message d’erreur le traduit dans un langage cible programme source Compilateur programme cible messages d’erreur 4 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Les diﬀ´ erentes ´ etapes de la compilation Table des symboles Programme source Analyseur lexical Analyseur syntaxique Analyseur s´ emantique G´ en´ erateur de code interm´ ediaire Optimisateur de code G´ en´ erateur de code Programme cible Erreurs 5 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Les diﬀ´ erentes ´ etapes de la compilation Table des symboles Programme source Analyseur lexical Analyseur syntaxique Analyseur s´ emantique G´ en´ erateur de code interm´ ediaire Optimisateur de code G´ en´ erateur de code Programme cible Erreurs Partie analyse: s´ epare les ̸= constituants du prog. source et produit une repr´ esentation interm´ ediaire 5 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Les diﬀ´ erentes ´ etapes de la compilation Table des symboles Programme source Analyseur lexical Analyseur syntaxique Analyseur s´ emantique G´ en´ erateur de code interm´ ediaire Optimisateur de code G´ en´ erateur de code Programme cible Erreurs Partie analyse: s´ epare les ̸= constituants du prog. source et produit une repr´ esentation interm´ ediaire Partie synth` ese: g´ en` ere le prog. cible ` a partir de la repr´ esentation interm´ ediaire 5 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Analyse lexicale Table des symboles Programme source Analyseur lexical Analyseur syntaxique Analyseur s´ emantique G´ en´ erateur de code interm´ ediaire Optimisateur de code G´ en´ erateur de code Programme cible Erreurs 6 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Analyse lexicale Seul module au contact avec le texte source Son but est de reconnaˆ ıtre les unit´ es lexicales ou lex` emes les identiﬁcateurs et les mots clefs du langage l’aﬀectation et les op´ erateurs Utilise des expressions r´ eguli` eres : automates ﬁnis ab := y * x + 20 identiﬁcateur aﬀectation operateur nombre 7 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Analyse syntaxique Table des symboles Programme source Analyseur lexical Analyseur syntaxique Analyseur s´ emantique G´ en´ erateur de code interm´ ediaire Optimisateur de code G´ en´ erateur de code Programme cible Erreurs 8 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Analyse syntaxique Regroupe les unit´ es lexicales en structures grammaticales en suivant les r` egles ﬁgurant dans une grammaire R´ esultat repr´ esent´ e par un arbre syntaxique La structure hi´ erarchique d’un programme est exprim´ ee ` a l’aide de r` egles Tout identiﬁcateur est une expression Tout nombre est une expression Si expr1 et expr2 sont des expressions alors expr1 ∗expr2 est une expression Grammaires hors contexte : automates ` a pile ab := y * x + 20 9 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Analyse s´ emantique Table des symboles Programme source Analyseur lexical Analyseur syntaxique Analyseur s´ emantique G´ en´ erateur de code interm´ ediaire Optimisateur de code G´ en´ erateur de code Programme cible Erreurs 10 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Analyse s´ emantique V´ eriﬁe la pr´ esence d’erreurs d’ordre s´ emantique V´ eriﬁcation de typage V´ eriﬁcation des d´ eclarations Par exemple, si x et y sont des r´ eels : ab := y * x + conversion entier -> r´ eel 20 11 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Partie synth` ese Table des symboles Programme source Analyseur lexical Analyseur syntaxique Analyseur s´ emantique G´ en´ erateur de code interm´ ediaire Optimisateur de code G´ en´ erateur de code Programme cible Erreurs 12 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Partie synth` ese G´ en´ eration du code interm´ ediaire Utilisation de variables temporaires Choix de l’ordre pour faire un calcul Optimisation du code Am´ elioration du code interm´ ediaire R´ eduction du nombre de variables et d’instructions G´ en´ eration du code Choix des emplacements m´ emoire pour les variables Assignation de variables aux registres 13 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Table des symboles Table des symboles Programme source Analyseur lexical Analyseur syntaxique Analyseur s´ emantique G´ en´ erateur de code interm´ ediaire Optimisateur de code G´ en´ erateur de code Programme cible Erreurs 14 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Table des symboles Enregistre les identiﬁants et les attributs (emplacement m´ emoire, type, port´ ee) Chaque identiﬁant (variable) a une entr´ ee dans la table des symboles L’analyseur lexical cr´ ee une entr´ ee dans la table des symboles ` a chaque fois qu’il rencontre un nouvel identiﬁcateur Par contre, les attributs seront calcul´ es plus tard L’analyseur s´ emantique se sert de la table des symboles pour v´ eriﬁer la concordance des types 15 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation D´ etection des erreurs Table des symboles Programme source Analyseur lexical Analyseur syntaxique Analyseur s´ emantique G´ en´ erateur de code interm´ ediaire Optimisateur de code G´ en´ erateur de code Programme cible Erreurs 16 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation D´ etection des erreurs Erreur lexicale : le ﬂot de caract` eres n’est pas reconnu Erreur syntaxique : construction non reconnue par le langage Erreur s´ emantique : probl` eme de typage,... 17 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Th´ eorie des langages et compilation Structure d’un compilateur Analyse lexicale Analyse syntaxique Analyse s´ emantique Conclusion 18 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Analyseur lexical et analyseur syntax- ique L’analyse lexicale produit des lex` emes En g´ en´ eral ` a la vol´ ee ` a la demande de l’analyseur syntaxique L’analyseur syntaxique demande le prochain lex` eme ` a l’analyseur lexical, qui le reconnaˆ ıt et retourne un code identiﬁant ce lex` eme On pourrait imaginer que l’analyse lexicale travaille ind´ ependamment et fournisse une suite de lex` emes mais on n’a pas besoin, en g´ en´ eral, d’avoir reconnu tous les lex` emes pour faire l’analyse syntaxique : la connaissance du lex` eme courant suﬃt pour la plupart des m´ ethodes utilis´ ees et malheureusement, pour certains langages (C notamment), la reconnaissance d’un lex` eme d´ epend du contexte grammatical dans lequel il se trouve 19 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Analyse lexicale Chaque lex` eme est un mot d’un langage Dans la plupart des cas, langage qui peut ˆ etre repr´ esent´ e par une expression r´ eguli` ere, par exemple ((A −Z) + (a −z))((A −Z) + (a −z) + (0 −9))∗pour reconnaˆ ıtre des identiﬁcateurs du genre X, Compteur, i3, R2D2, . . . Langage ﬁni pour de nombreux lex` emes : +, ==, for, . . . L’analyseur lexical est donc un (gros) automate ﬁni d´ eterministe qui reconnaˆ ıt l’union des langages des lex` emes un ´ etat terminal correspond ` a la reconnaissance d’un mot d’un des langages des lex` emes 20 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Fragment d’automate lexical q0 q1 q2 q3 q4 q5 q6 q7 q8 i a-z sauf i 0-9 = f a-z sauf f a-z a-z . 0-9 0-9 0-9 = 21 / 59 Th´ eorie des langages ▲ Th´ eorie des langages et compilation Analyse lexicale Analyseur lexical : En g´ en´ eral pas tout ` a fait un automate d´ eterministe Certains lex` emes sont pr´ eﬁxes d’un autre +, +=, ++ ; = et == mots-cl´ es et identiﬁcateurs (for et forme) entiers et r´ eels (3 et 3.14) Le principe est de reconnaˆ ıtre le mot le plus long Un ´ etat terminal n’implique donc pas toujours l’arrˆ et de l’automate : il peut continuer, et ´ eventuellement revenir en arri` ere au dernier ´ etat ﬁnal rencontr´ e 22 / 59 Th´ uploads/Management/ compilation.pdf