Remerciez-le!

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

Toute reproduction sans autorisation du Centre français d’exploitation du droit

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite. © Techniques de l’Ingénieur, traité Informatique H 3 168 − 1 Compilateurs par Bernard LORHO Professeur à l’Université d’Évry Val d’Essonne Département d’informatique a compilation, c’est-à-dire la traduction automatisée d’un texte écrit dans un langage de programmation en un texte équivalent dans un autre langage de programmation, est née avec l’informatique. En effet, il est très vite apparu qu’il n’était pas raisonnable de programmer des applications d’une certaine taille et d’une certaine complexité dans les langages rudimentaires que sont les lan- gages machines ou les langages d’assemblage. La raison de base de cette difﬁ- culté est simple : ces langages sont modelés sur la structure des machines et sur leur organisation, alors que les utilisateurs ont besoin de mécanismes d’expression qui soient du plus haut niveau possible et adaptés à la formulation de leurs problèmes. De plus, la nécessité est vite apparue de viser une certaine portabilité qui permette d’écrire des programmes qui soient indépendants d’une machine donnée pour pouvoir les transporter facilement sur une autre machine. La porta- bilité est devenue une réalité économique forte condamnant la programmation de bas niveau. Celle-ci n’a pas complètement disparu mais se cantonne à des domaines tout à fait spécialisés où il est indispensable de maîtriser le fonction- nement intime d’une machine. 1. Généralités................................................................................................. H 3 168 - 2 1.1 Phase et passe ............................................................................................. — 2 1.2 Notions de grammaires .............................................................................. — 2 2. Analyse lexicographique........................................................................ — 3 2.1 Expressions régulières, déﬁnitions régulières.......................................... — 3 2.2 Automates d’états ﬁnis ............................................................................... — 4 2.3 Mise en œuvre ............................................................................................. — 4 2.4 Constructeurs lexicographiques................................................................. — 4 3. Analyse syntaxique ................................................................................. — 5 3.1 Grammaires algébriques ou non contextuelles........................................ — 5 3.2 Principes....................................................................................................... — 5 3.3 Analyse ascendante : principe et mise en œuvre ..................................... — 6 3.4 Constructeurs syntaxiques ......................................................................... — 7 4. Adressage des objets.............................................................................. — 8 4.1 Taille des objets ........................................................................................... — 8 4.2 Bloc d’activation .......................................................................................... — 8 4.3 Mise en œuvre ............................................................................................. — 9 5. Modèle d’exécution................................................................................. — 9 5.1 Principe......................................................................................................... — 9 5.2 Exemple........................................................................................................ — 10 5.3 Activation d’une fonction............................................................................ — 10 6. Génération de code ................................................................................. — 11 6.1 Langage cible............................................................................................... — 11 6.2 Générateur de code..................................................................................... — 12 6.3 Adressage des instructions......................................................................... — 12 7. Conclusion ................................................................................................. — 13 Pour en savoir plus........................................................................................... Doc. H 3 168 L COMPILATEURS _______________________________________________________________________________________________________________________ Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite. H 3 168 − 2 © Techniques de l’Ingénieur, traité Informatique On peut en fait dire qu’il y a nécessairement compilation dès qu’un programme est écrit. Cela implique que tout utilisateur de l’informatique compile, sans en être conscient dans la plupart des cas, comme M. Jourdain faisait de la prose... Les langages de programmation ont commencé à se multiplier dès les débuts de l’informatique, certains se spécialisant dans des domaines d’application parti- culiers, d’autres essayant d’atteindre une certaine universalité. Tous ces langages « de haut niveau » constituent les langages que les compilateurs doivent être capables de traiter. Subsistent bien entendu les langages « de bas niveau » évoqués précédemment, qui sont incontournables car ce sont les seuls langages « natifs » des machines. Le rôle des compilateurs est, en fait, à partir de programmes écrits dans un langage source, de les transformer en des programmes écrits dans un langage cible, qui peut être un langage de bas niveau ou un autre langage de haut niveau. Ce processus de traduction doit satisfaire une contrainte très légitime qui est que les programmes cibles résultats de la compilation soient sémantiquement équivalents aux programmes sources, c’est-à-dire que leurs exécutions fournissent les mêmes résultats. Arrêtons-nous un instant sur le fait qu’il peut paraître étrange de traduire un langage de haut niveau en un autre langage de haut niveau. Il y a d’excellentes raisons à une telle démarche : par exemple si, sur une machine donnée, on dispose d’un compilateur du langage C mais pas d’un compilateur d’un langage L et si l’on souhaite malgré tout prendre en compte des programmes écrits en L, il peut être plus facile d’écrire un compilateur de L vers C plutôt que d’écrire complètement un compilateur pour L. On constate cette tendance croissante à considérer que le langage C (dont un compilateur est présent sur quasiment toutes les machines) constitue un langage cible privilégié pour de nombreux compilateurs car l’universalité de C permet de simpliﬁer la compilation de nombreux langages. Cette démarche a l’avantage supplémentaire d’être indépendante de la machine support et donc de permettre la portabilité d’un compilateur sur plusieurs machines. 1. Généralités 1.1 Phase et passe Dans le processus de compilation que nous allons décrire, nous distinguerons différentes étapes qui constituent des composantes logiques du traitement. Cette décomposition a pour but essentiel de bien faire comprendre les mécanismes. Nous les appellerons des phases. Ce découpage n’implique nullement que ces phases se succèdent en constituant autant de traitements qui nécessiteraient une relecture complète du texte du programme source, et cela pour des raisons évidentes d’efﬁcacité. Dans la réalité, les phases coopèrent les unes avec les autres et la tendance actuelle dans la conception des langages de programmation récents est de faire en sorte que leur compilation ne nécessite qu’une seule passe sur le texte source, c’est-à-dire une seule lecture du texte source. En parti- culier, cette contrainte est impérative si on vise un compilateur « rapide » (et même « turbo »...) dont les performances nécessitent un traitement qui se déroule intégralement en mémoire centrale, sans jamais nécessiter des échanges de ﬁchiers avec le disque qui sont grands consommateurs de temps, ou alors en les limitant très fortement. 1.2 Notions de grammaires Écrire un programme dans un langage de programmation consiste d’abord à se conformer strictement aux règles du langage telles qu’on peut les lire dans les documents le décrivant. Parmi ces docu- ments ﬁgure de manière quasi systématique la grammaire du lan- gage, où sont décrites, de manière plus ou moins formelle et précise, les règles à respecter pour construire des phrases (instructions ou déclarations) du langage. De nombreux formalismes de description de grammaires ont été introduits dans la littérature. Un d’entre eux est le plus souvent utilisé, la Forme de Backus-Naur (BNF). Celle-ci a été introduite en 1960 à l’occasion de la déﬁnition normalisée du langage Algol 60. En BNF, on apporte une distinction entre les composants élémen- taires d’une phrase et les constructions plus élaborées. Ainsi, on trouve des symboles de base, comme les signes de ponctuation du langage « + – / * , ; : () [] {} », composants qui vont ponctuer les phrases avec une signiﬁcation bien particulière. Par exemple, les symboles «[« et »]» encadrent les indices de tableau dans de nombreux lan- gages, le symbole « ; » étant souvent le signe qui termine une ins- truction. Certains de ces symboles de base nécessitent plusieurs caractè- res successifs, comme « : = » « .. » « < = » « / * » et même des mots entiers, comme « if » « else ». Cela est dû sans doute à la trop grande pauvreté des claviers que nous utilisons et au souci de ren- dre les programmes lisibles car un programme doit souvent être relu après sa création et il est important de faciliter cette opération. _______________________________________________________________________________________________________________________ COMPILATEURS Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite. © Techniques de l’Ingénieur, traité Informatique H 3 168 − 3 Mais il est évident que ces symboles de base ne peuvent être juxtaposés n’importe comment. Il est indispensable de donner les règles de composition de constructions plus complexes, par exemple dire comment est constituée une déclaration ou une instruction. Cela se fait essentiellement par assemblage de signes et d’entités éla- borées. Par exemple, dans le langage C, l’instruction conditionnelle se construit de la manière suivante : le mot réservé « if » est suivi d’une parenthèse ouvrante « ( » suivie d’une expression suivie d’une parenthèse fermante « ) » suivie d’une instruction éventuellement suivie du mot « else » qui, s’il est présent, doit être suivi d’une ins- truction. En BNF, cette déﬁnition s’écrit : <instruction-conditionnelle> : : = if (<expression> ) <instruction> | if (<expression> ) <instruction> else <instruction> Les entités dénotées entre les chevrons < et > sont appelées symboles non terminaux et correspondent à des notions plus complexes que les symboles de base : elles doivent être explicitées jusqu’à obtenir des symboles de base, ce qui justiﬁe leur nom de symboles non terminaux. Les symboles de base (appelés symboles terminaux) ne peuvent être explicités davantage. Le signe : : = indique en BNF que la déﬁnition de l’entité située à sa gauche est composée de ce qui ﬁgure à droite où peuvent apparaître une succession de symboles non terminaux (qui devront être expli- cités) et de symboles terminaux. De plus, lorsqu’il y a des variantes, les différentes solutions de remplacement peuvent être précisées à l’aide du signe uploads/s3/ compilateurs.pdf