Histoire de la construction du compilateur - History of compiler construction

En informatique , un compilateur est un programme informatique qui transforme le code source écrit dans un langage de programmation ou un langage informatique (le langage source ), en un autre langage informatique (le langage cible , ayant souvent une forme binaire connue sous le nom de code objet ou code machine ). La raison la plus courante pour transformer le code source est de créer un programme exécutable .

Tout programme écrit dans un langage de programmation de haut niveau doit être traduit en code objet avant de pouvoir être exécuté, de sorte que tous les programmeurs utilisant un tel langage utilisent un compilateur ou un interpréteur . Ainsi, les compilateurs sont très importants pour les programmeurs. Les améliorations apportées à un compilateur peuvent conduire à un grand nombre de fonctionnalités améliorées dans les programmes exécutables.

Le compilateur-compilateur de qualité de production , à la fin des années 1970, a introduit les principes d'organisation du compilateur qui sont encore largement utilisés aujourd'hui (par exemple, une syntaxe et une sémantique de gestion frontale et un code machine de génération de back-end).

Premiers compilateurs

Les logiciels des premiers ordinateurs étaient principalement écrits en langage assembleur , et avant cela directement en code machine . Il est généralement plus productif pour un programmeur d'utiliser un langage de haut niveau, et les programmes écrits dans un langage de haut niveau peuvent être réutilisés sur différents types d'ordinateurs . Même ainsi, il a fallu du temps aux compilateurs pour s'établir, car ils généraient du code qui ne fonctionnait pas aussi bien que l'assembleur écrit à la main, ils étaient des projets de développement intimidants à part entière, et la capacité de mémoire très limitée des premiers ordinateurs a créé de nombreux problèmes techniques pour les implémentations pratiques du compilateur.

Le premier compilateur pratique a été écrit par Corrado Böhm , en 1951, pour sa thèse de doctorat . Le premier compilateur implémenté a été écrit par Grace Hopper , qui a également inventé le terme "compilateur", faisant référence à son système A-0 qui fonctionnait comme un chargeur ou un éditeur de liens , et non la notion moderne de compilateur. Le premier Autocode et compilateur au sens moderne du terme ont été développés par Alick Glennie en 1952 à l' Université de Manchester pour l' ordinateur Mark 1 . L' équipe FORTRAN dirigée par John W. Backus chez IBM a introduit le premier compilateur disponible dans le commerce, en 1957, dont la création a nécessité 18 années-personnes.

Le premier compilateur ALGOL 58 a été achevé fin 1958 par Friedrich L. Bauer , Hermann Bottenbruch, Heinz Rutishauser et Klaus Samelson pour l' ordinateur Z22 . Bauer et al. avait travaillé sur la technologie du compilateur pour la Sequentielle Formelübersetzung (c'est- à- dire la traduction de formules séquentielles ) au cours des années précédentes.

En 1960, un compilateur Fortran étendu, ALTAC, était disponible sur le Philco 2000, il est donc probable qu'un programme Fortran ait été compilé pour les architectures informatiques IBM et Philco au milieu des années 1960. Le premier langage de haut niveau multiplateforme connu et démontré était COBOL . Lors d'une démonstration en décembre 1960, un programme COBOL a été compilé et exécuté à la fois sur l' UNIVAC II et le RCA 501.

Compilateurs auto-hébergés

Comme tout autre logiciel, il y a des avantages à implémenter un compilateur dans un langage de haut niveau. En particulier, un compilateur peut être auto-hébergé , c'est-à-dire écrit dans le langage de programmation qu'il compile. Construire un compilateur auto-hébergé est un problème d' amorçage , c'est-à-dire que le premier compilateur de ce type pour un langage doit être soit du code machine écrit à la main, soit compilé par un compilateur écrit dans un autre langage, soit compilé en exécutant le compilateur dans un interpréteur .

Thèse de doctorat de Corrado Böhm

Corrado Böhm a développé un langage, une machine et une méthode de traduction pour compiler ce langage sur la machine dans sa thèse de doctorat de 1951. Il a non seulement décrit un compilateur complet, mais a également défini pour la première fois ce compilateur dans son propre langage. Le langage était intéressant en soi, car chaque instruction (y compris les instructions d'entrée, les instructions de sortie et les instructions de contrôle) était un cas particulier d' instruction d'affectation .

NÉLIAC

Le Navy Electronics Laboratory International ALGOL Compiler ou NELIAC était un dialecte et une implémentation du compilateur du langage de programmation ALGOL 58 développé par le Naval Electronics Laboratory en 1958.

NELIAC a été conçu par Harry Huskey - alors président de l' ACM et informaticien bien connu (et plus tard superviseur académique de Niklaus Wirth ), et soutenu par Maury Halstead, le chef du centre de calcul du NEL. La première version a été mise en œuvre sur le prototype d' ordinateur USQ-17 (appelé la comtesse) au laboratoire. C'était le premier compilateur auto-compilé au monde - le compilateur a d'abord été codé sous une forme simplifiée en langage assembleur (le bootstrap ), puis réécrit dans son propre langage et compilé par le bootstrap, et finalement recompilé par lui-même, rendant le bootstrap obsolète.

Zézayer

Un autre compilateur auto-hébergé a été écrit pour Lisp par Tim Hart et Mike Levin au MIT en 1962. Ils ont écrit un compilateur Lisp en Lisp, le testant dans un interpréteur Lisp existant. Une fois qu'ils avaient amélioré le compilateur au point où il pouvait compiler son propre code source, il s'auto-hébergeait.

Le compilateur tel qu'il existe sur la bande de compilation standard est un programme en langage machine qui a été obtenu en faisant fonctionner la définition de l' expression S du compilateur sur elle-même via l'interpréteur. (Mémo IA 39)

Cette technique n'est possible que lorsqu'un interpréteur existe déjà pour le même langage à compiler. Il emprunte directement à la notion d'exécution d'un programme sur lui-même en entrée, qui est également utilisée dans diverses preuves en informatique théorique , comme la preuve que le problème d'arrêt est indécidable .

En avant

Forth est un exemple de compilateur auto-hébergé. Les fonctionnalités d' auto-compilation et de compilation croisée de Forth sont généralement confondues avec la métacompilation et les métacompilateurs . Comme Lisp , Forth est un langage de programmation extensible . Ce sont les fonctionnalités de langage de programmation extensible de Forth et Lisp qui leur permettent de générer de nouvelles versions d'eux-mêmes ou de se porter vers de nouveaux environnements.

Grammaires et analyseurs sans contexte

Un analyseur est un composant important d'un compilateur. Il analyse le code source d'un langage de programmation informatique pour créer une forme de représentation interne. Les langages de programmation ont tendance à être spécifiés en termes de grammaire sans contexte, car des analyseurs rapides et efficaces peuvent être écrits pour eux. Les analyseurs peuvent être écrits à la main ou générés par un générateur d' analyseur . Une grammaire sans contexte fournit un mécanisme simple et précis pour décrire comment les constructions du langage de programmation sont construites à partir de blocs plus petits . Le formalisme des grammaires sans contexte a été développé au milieu des années 1950 par Noam Chomsky .

La structure par blocs a été introduite dans les langages de programmation informatique par le projet ALGOL (1957-1960), qui, par conséquent, comportait également une grammaire sans contexte pour décrire la syntaxe ALGOL résultante.

Les grammaires sans contexte sont suffisamment simples pour permettre la construction d'algorithmes d'analyse efficaces qui, pour une chaîne donnée, déterminent si et comment elle peut être générée à partir de la grammaire. Si un concepteur de langage de programmation est prêt à travailler dans des sous-ensembles limités de grammaires sans contexte, des analyseurs syntaxiques plus efficaces sont possibles.

Analyse LR

L' analyseur LR (de gauche à droite) a été inventé par Donald Knuth en 1965 dans un article intitulé "Sur la traduction des langues de gauche à droite". Un analyseur LR est un analyseur qui lit l' entrée de L auche à droite (comme il semble si visuellement affiché) et produit une R dérivation de ightmost . Le terme analyseur LR( k ) est également utilisé, où k fait référence au nombre de symboles d'entrée d' anticipation non consommés qui sont utilisés pour prendre des décisions d'analyse.

Knuth a prouvé que les grammaires LR( k ) peuvent être analysées avec un temps d'exécution essentiellement proportionnel à la longueur du programme, et que chaque grammaire LR( k ) pour k > 1 peut être transformée mécaniquement en une grammaire LR(1) pour le même Langue. En d'autres termes, il n'est nécessaire d'avoir qu'un seul symbole d'anticipation pour analyser toute grammaire sans contexte déterministe (DCFG).

Korenjak (1969) a été le premier à montrer que des analyseurs syntaxiques pour les langages de programmation pouvaient être produits en utilisant ces techniques. Frank DeRemer a conçu les techniques plus pratiques LR simple (SLR) et Look-ahead LR (LALR), publiées dans sa thèse de doctorat au MIT en 1969. Ce fut une percée importante, car les traducteurs LR(k), tels que définis par Donald Knuth, étaient beaucoup trop volumineux pour être mis en œuvre sur des systèmes informatiques dans les années 1960 et 1970.

En pratique, LALR offre une bonne solution ; la puissance supplémentaire des analyseurs LALR(1) par rapport aux analyseurs SLR(1) (c'est-à-dire que LALR(1) peut analyser des grammaires plus complexes que SLR(1)) est utile et, bien que LALR(1) ne soit pas comparable à LL( 1)(Voir ci-dessous) (LALR(1) ne peut pas analyser toutes les grammaires LL(1)), la plupart des grammaires LL(1) rencontrées en pratique peuvent être analysées par LALR(1). Les grammaires LR(1) sont encore plus puissantes que LALR(1) ; cependant, une grammaire LR(1) nécessite un analyseur LR canonique qui serait extrêmement volumineux et n'est pas considéré comme pratique. La syntaxe de nombreux langages de programmation est définie par des grammaires qui peuvent être analysées avec un analyseur LALR(1), et pour cette raison, les analyseurs LALR sont souvent utilisés par les compilateurs pour effectuer une analyse syntaxique du code source.

Un analyseur de remontée récursive implémente un analyseur LALR en utilisant des fonctions mutuellement récursives plutôt que des tables. Ainsi, l'analyseur est directement encodé dans le langage hôte similaire à la descente récursive . L'encodage direct produit généralement un analyseur qui est plus rapide que son équivalent piloté par table pour la même raison que la compilation est plus rapide que l'interprétation. Il est également (en principe) possible d'éditer manuellement un analyseur d'ascension récursive, alors qu'une implémentation tabulaire est presque illisible pour l'homme moyen.

L'ascension récursive a été décrite pour la première fois par Thomas Pennello dans son article "Very fast LR parsing" en 1986. La technique a ensuite été exposée par GH Roberts en 1988 ainsi que dans un article de Leermakers, Augusteijn, Kruseman Aretz en 1992 dans la revue Theoretical Informatique .

Analyse LL

Un analyseur LL analyse l'entrée de L auche à droite, et construit un L dérivation eftmost de la phrase ( et donc LL, par opposition à LR). La classe de grammaires qui sont analysables de cette manière est connue sous le nom de grammaires LL . Les grammaires LL sont une classe encore plus restreinte de grammaires sans contexte que les grammaires LR. Néanmoins, ils présentent un grand intérêt pour les auteurs de compilateurs, car un tel parseur est simple et efficace à mettre en œuvre.

Les grammaires LL(k) peuvent être analysées par un analyseur de descente récursive qui est généralement codé à la main, bien qu'une notation telle que META II puisse également être utilisée.

La conception d'ALGOL a suscité une enquête sur la descente récursive, puisque le langage ALGOL lui-même est récursif. Le concept d'analyse de descente récursive a été discuté dans le numéro de janvier 1961 de Communications of the ACM dans des articles séparés par AA Grau et Edgar T. "Ned" Irons . Richard Waychoff et ses collègues ont également implémenté la descente récursive dans le compilateur Burroughs ALGOL en mars 1961, les deux groupes ont utilisé des approches différentes mais étaient au moins en contact informel.

L'idée des grammaires LL(1) a été introduite par Lewis et Stearns (1968).

La descente récursive a été popularisée par Niklaus Wirth avec PL/0 , un langage de programmation pédagogique utilisé pour enseigner la construction de compilateurs dans les années 1970.

L'analyse LR peut gérer un plus grand nombre de langages que l' analyse LL et est également meilleure pour le rapport d'erreurs (ceci est discutable, REFERENCE est requis), c'est-à-dire qu'elle détecte les erreurs syntaxiques lorsque l'entrée n'est pas conforme à la grammaire dès que possible.

Analyseur d'Earley

En 1970, Jay Earley a inventé ce qui allait être connu sous le nom d' analyseur syntaxique Earley . Les analyseurs syntaxiques d'Earley sont attrayants car ils peuvent analyser toutes les langues sans contexte de manière raisonnablement efficace.

Langages de description grammaticale

John Backus a proposé des « formules métalinguistiques » pour décrire la syntaxe du nouveau langage de programmation IAL, connu aujourd'hui sous le nom d' ALGOL 58 (1959). Le travail de Backus était basé sur le système canonique de Post conçu par Emil Post .

Le développement ultérieur d'ALGOL a conduit à ALGOL 60 ; dans son rapport (1963), Peter Naur a nommé la notation de Backus Backus forme normale (BNF), et l'a simplifiée pour minimiser le jeu de caractères utilisé. Cependant, Donald Knuth a fait valoir que BNF devrait plutôt être lu comme la forme Backus-Naur , et c'est devenu l'usage communément accepté.

Niklaus Wirth a défini la forme étendue de Backus-Naur (EBNF), une version raffinée de BNF, au début des années 1970 pour PL/0. La forme Backus-Naur augmentée (ABNF) est une autre variante. EBNF et ABNF sont tous deux largement utilisés pour spécifier la grammaire des langages de programmation, en tant qu'entrées des générateurs d'analyseurs, et dans d'autres domaines tels que la définition de protocoles de communication.

Générateurs d'analyseurs

Un générateur d'analyseur génère la partie d'analyse lexicale d'un compilateur. C'est un programme qui prend une description d'une grammaire formelle d'un langage de programmation spécifique et produit un analyseur pour ce langage. Cet analyseur peut être utilisé dans un compilateur pour ce langage spécifique. L'analyseur détecte et identifie les mots et symboles réservés de la langue spécifique à partir d'un flux de texte et les renvoie sous forme de jetons au code qui met en œuvre la validation syntaxique et la traduction en code objet. Cette deuxième partie du compilateur peut également être créée par un compilateur-compilateur utilisant une description de syntaxe de règles de préséance formelle comme entrée.

Le premier compilateur-compilateur à utiliser ce nom a été écrit par Tony Brooker en 1960 et a été utilisé pour créer des compilateurs pour l' ordinateur Atlas à l' Université de Manchester , y compris le compilateur Atlas Autocode . Cependant, il était assez différent des compilateurs-compilateurs modernes, et aujourd'hui, il serait probablement décrit comme se situant quelque part entre un compilateur générique hautement personnalisable et un langage de syntaxe extensible . Le nom "compilateur-compilateur" était bien plus approprié pour le système de Brooker qu'il ne l'est pour la plupart des compilateurs-compilateurs modernes, qui sont plus précisément décrits comme des générateurs d'analyseurs. Il est presque certain que le nom "Compilateur-Compilateur" est entré dans l'usage courant en raison du souvenir de Yacc plutôt que du travail de Brooker.

Au début des années 1960, Robert McClure de Texas Instruments a inventé un compilateur-compilateur appelé TMG , nom tiré de « transmogrification ». Au cours des années suivantes, TMG a été porté sur plusieurs ordinateurs centraux UNIVAC et IBM.

Le projet Multics , une joint-venture entre le MIT et les Bell Labs , a été l'un des premiers à développer un système d'exploitation dans un langage de haut niveau. PL/I a été choisi comme langage, mais un fournisseur externe n'a pas pu fournir un compilateur fonctionnel. L'équipe Multics a développé son propre dialecte de sous-ensemble de PL/I connu sous le nom de Early PL/I (EPL) comme langage d'implémentation en 1964. TMG a été porté sur la série GE-600 et utilisé pour développer EPL par Douglas McIlroy , Robert Morris et d'autres. .

Peu de temps après que Ken Thompson ait écrit la première version d' Unix pour le PDP-7 en 1969, Douglas McIlroy a créé le premier langage de niveau supérieur du nouveau système : une implémentation du TMG de McClure. TMG était également l'outil de définition de compilateur utilisé par Ken Thompson pour écrire le compilateur pour le langage B sur son PDP-7 en 1970. B était l'ancêtre immédiat de C .

Un premier générateur d'analyseur LALR s'appelait « TWS », créé par Frank DeRemer et Tom Pennello.

XPL

XPL est un dialecte du langage de programmation PL/I , utilisé pour le développement de compilateurs de langages informatiques. Il a été conçu et mis en œuvre en 1967 par une équipe composée de William M. McKeeman , James J. Horning et David B. Wortman à l'Université de Stanford et à l' Université de Californie à Santa Cruz . Il a été annoncé pour la première fois lors de la conférence informatique conjointe d'automne de 1968 à San Francisco.

XPL comportait un système d'écriture de traducteur relativement simple appelé ANALYZER , basé sur une technique d'analyse de précédence de compilateur ascendante appelée MSP (précédence de stratégie mixte). XPL a été amorcé via Burroughs Algol sur l' ordinateur IBM System/360 . (Certaines versions ultérieures de XPL utilisées sur les projets internes de l'Université de Toronto utilisaient un analyseur SLR(1), mais ces implémentations n'ont jamais été distribuées).

Yacc

Yacc est un générateur d'analyseur syntaxique (en gros, compilateur-compilateur ), à ne pas confondre avec lex , qui est un analyseur lexical fréquemment utilisé comme première étape par Yacc. Yacc a été développé par Stephen C. Johnson chez AT&T pour le système d' exploitation Unix . Le nom est un acronyme pour « Yet Another Compiler Compiler ». Il génère un compilateur LALR(1) basé sur une grammaire écrite dans une notation similaire à la forme Backus-Naur.

Johnson a travaillé sur Yacc au début des années 1970 chez Bell Labs . Il était familier avec TMG et son influence peut être vue dans Yacc et la conception du langage de programmation C. Parce que Yacc était le générateur de compilateur par défaut sur la plupart des systèmes Unix, il était largement distribué et utilisé. Des dérivés tels que GNU Bison sont toujours utilisés.

Le compilateur généré par Yacc nécessite un analyseur lexical . Les générateurs d'analyseurs lexicaux, tels que lex ou flex sont largement disponibles. La norme IEEE POSIX P1003.2 définit les fonctionnalités et les exigences pour Lex et Yacc.

Coco/R

Coco/R est un générateur d'analyseur qui génère des analyseurs LL(1) dans Modula-2 (avec des plug-ins pour d'autres langages) à partir de grammaires d'entrée écrites dans une variante d'EBNF. Il a été développé par Hanspeter Mössenböck à l'Ecole polytechnique fédérale de Zurich (ETHZ) en 1985.

ANTLR

ANTLR est un générateur d'analyseur qui génère des analyseurs LL(*) en Java à partir de grammaires d'entrée écrites dans une variante d'EBNF. Il a été développé par Terence Parr à l'Université de San Francisco au début des années 1990 en tant que successeur d'un générateur antérieur appelé PCCTS.

Métacompilateurs

Les métacompilateurs diffèrent des générateurs d'analyseurs syntaxiques, prenant en entrée un programme écrit dans un métalangage . Leur entrée consiste en une formule d'analyse grammaticale combinée à des opérations de transformation intégrées qui construisent des arbres de syntaxe abstraite, ou simplement en sortie des chaînes de texte reformatées qui peuvent être du code machine de pile.

Beaucoup peuvent être programmés dans leur propre métalangage, ce qui leur permet de se compiler eux-mêmes, ce qui en fait des compilateurs de langage extensible auto-hébergés.

De nombreux métacompilateurs s'appuient sur les travaux de Dewey Val Schorre . Son compilateur META II , publié pour la première fois en 1964, a été le premier métacompilateur documenté. Capable de définir son propre langage et d'autres, META II a accepté une formule de syntaxe ayant une sortie intégrée (production de code) . Cela s'est également traduit par l'une des premières instances d'une machine virtuelle . L'analyse lexicale a été effectuée par des fonctions de reconnaissance de jetons intégrées : .ID, .STRING et .NUMBER. Les chaînes entre guillemets dans la formule de syntaxe reconnaissent les lexèmes qui ne sont pas conservés.

TREE-META , un métacompilateur Schorre de deuxième génération, est apparu vers 1968. Il a étendu les capacités de META II, en ajoutant des règles non analysées séparant la production de code de l'analyse grammaticale. Les opérations de transformation d'arbre dans la formule de syntaxe produisent des arbres de syntaxe abstraits sur lesquels opèrent les règles d'analyse. La correspondance de modèle d'arbre non analysé a fourni une capacité d' optimisation de judas .

CWIC , décrit dans une publication ACM de 1970, est un métacompilateur Schorre de troisième génération qui a ajouté des règles de lexage et des opérateurs de retour en arrière à l'analyse grammaticale. LISP 2 a été marié avec les règles non analysées de TREEMETA dans le langage générateur CWIC. Avec le traitement LISP 2[[]], CWIC peut générer un code entièrement optimisé. CWIC a également fourni la génération de code binaire dans des sections de code nommées. Les compilations en une seule et plusieurs passes pourraient être implémentées à l'aide de CWIC.

CWIC a compilé des instructions de code machine adressables par octet 8 bits principalement conçues pour produire du code IBM System/360.

Les générations ultérieures ne sont pas documentées publiquement. Une caractéristique importante serait l'abstraction du jeu d'instructions du processeur cible, générant dans un jeu d'instructions pseudo-machine, des macros, qui pourraient être définies séparément ou mappées sur les instructions d'une machine réelle. Les optimisations s'appliquant aux instructions séquentielles pourraient alors être appliquées à la pseudo-instruction avant leur extension au code machine cible.

Compilation croisée

Un compilateur croisé s'exécute dans un environnement mais produit du code objet pour un autre. Les compilateurs croisés sont utilisés pour le développement embarqué, où l'ordinateur cible a des capacités limitées.

Un premier exemple de compilation croisée était AIMICO, où un programme FLOW-MATIC sur un UNIVAC II a été utilisé pour générer un langage d'assemblage pour l' IBM 705 , qui a ensuite été assemblé sur l'ordinateur IBM.

Le compilateur ALGOL 68C a généré une sortie ZCODE , qui pouvait ensuite être soit compilée dans le code machine local par un traducteur ZCODE, soit exécutée interprétée. ZCODE est un langage intermédiaire basé sur des registres. Cette capacité à interpréter ou à compiler ZCODE a encouragé le portage d'ALGOL 68C sur de nombreuses plates-formes informatiques différentes.

Optimiser les compilateurs

L'optimisation du compilateur est le processus d'amélioration de la qualité du code objet sans modifier les résultats qu'il produit.

Les développeurs du premier compilateur FORTRAN visaient à générer un code meilleur que l'assembleur moyen codé à la main, afin que les clients utilisent réellement leur produit. Dans l'un des premiers vrais compilateurs, ils ont souvent réussi.

Les compilateurs ultérieurs, comme le compilateur Fortran IV d' IBM , ont accordé plus de priorité à de bons diagnostics et à une exécution plus rapide, au détriment de l' optimisation du code objet . Ce n'est qu'avec la série IBM System/360 qu'IBM a fourni deux compilateurs distincts : un vérificateur de code à exécution rapide et un plus lent et optimisé.

Frances E. Allen , travaillant seule et conjointement avec John Cocke , a introduit de nombreux concepts d'optimisation. L'article d'Allen en 1966, Program Optimization, a introduit l'utilisation de structures de données graphiques pour coder le contenu du programme pour l'optimisation. Ses articles de 1970, Control Flow Analysis et A Basis for Program Optimization, ont établi les intervalles comme contexte pour une analyse et une optimisation efficaces et efficientes des flux de données. Son article de 1971 avec Cocke, A Catalog of Optimizing Transformations , a fourni la première description et systématisation des transformations d'optimisation. Ses articles de 1973 et 1974 sur l'analyse des flux de données interprocédurales ont étendu l'analyse à des programmes entiers. Son article de 1976 avec Cocke décrit l'une des deux principales stratégies d'analyse utilisées aujourd'hui pour optimiser les compilateurs.

Allen a développé et mis en œuvre ses méthodes dans le cadre de compilateurs pour l' IBM 7030 Stretch - Harvest et le Advanced Computing System expérimental . Ce travail a établi la faisabilité et la structure des optimiseurs modernes indépendants de la machine et du langage. Elle a ensuite créé et dirigé le projet PTRAN sur l'exécution parallèle automatique de programmes FORTRAN. Son équipe PTRAN a développé de nouveaux schémas de détection de parallélisme et créé le concept de graphe de dépendance de programme, la principale méthode de structuration utilisée par la plupart des compilateurs de parallélisation.

Langages de programmation et leurs compilateurs de John Cocke et Jacob T. Schwartz , publiés au début des années 1970, consacraient plus de 200 pages aux algorithmes d'optimisation. Il comprenait de nombreuses techniques désormais familières telles que l' élimination du code redondant et la réduction de la force .

Optimisation du judas

L'optimisation du judas est une technique d'optimisation simple mais efficace. Il a été inventé par William M. McKeeman et publié en 1965 dans CACM. Il a été utilisé dans le compilateur XPL que McKeeman a aidé à développer.

Optimiseur d'investissement COBOL

Capex Corporation a développé le "COBOL Optimizer" au milieu des années 1970 pour COBOL . Ce type d'optimiseur dépendait, dans ce cas, de la connaissance des "faiblesses" du compilateur IBM COBOL standard et remplaçait (ou corrigeait ) des sections du code objet par un code plus efficace. Le code de remplacement peut remplacer une recherche de table linéaire par une recherche binaire par exemple ou parfois simplement remplacer une instruction relativement "lente" par une instruction plus rapide connue qui était par ailleurs fonctionnellement équivalente dans son contexte. Cette technique est maintenant connue sous le nom de " Réduction de force ". Par exemple, sur le matériel IBM System/360 , l' instruction CLI était, selon le modèle particulier, entre deux et cinq fois plus rapide qu'une instruction CLC pour les comparaisons d'un seul octet.

Les compilateurs modernes fournissent généralement des options d'optimisation pour permettre aux programmeurs de choisir d'exécuter ou non une passe d'optimisation.

Diagnostique

Lorsqu'un compilateur reçoit un programme syntaxiquement incorrect, un bon message d'erreur clair est utile. Du point de vue de l'auteur du compilateur, il est souvent difficile à réaliser.

Le compilateur WATFIV Fortran a été développé à l' Université de Waterloo , au Canada, à la fin des années 1960. Il a été conçu pour donner de meilleurs messages d'erreur que les compilateurs Fortran d'IBM de l'époque. De plus, WATFIV était beaucoup plus utilisable, car il combinait la compilation, la liaison et l'exécution en une seule étape, alors que les compilateurs d'IBM avaient trois composants distincts à exécuter.

PL/C

PL/C était un langage de programmation informatique développé à l'Université Cornell au début des années 1970. Alors que PL/C était un sous-ensemble du langage PL/I d'IBM, il a été conçu dans le but spécifique d'être utilisé pour l'enseignement de la programmation. Les deux chercheurs et enseignants universitaires qui ont conçu PL/C étaient Richard W. Conway et Thomas R. Wilcox. Ils ont soumis le célèbre article "Conception et implémentation d'un compilateur de diagnostic pour PL/I" publié dans les Communications de l'ACM en mars 1973.

PL/C a éliminé certaines des fonctionnalités les plus complexes de PL/I et a ajouté des fonctions étendues de débogage et de récupération d'erreurs. Le compilateur PL/C avait la capacité inhabituelle de ne jamais manquer de compiler un programme, grâce à l'utilisation d'une correction automatique étendue de nombreuses erreurs de syntaxe et en convertissant toutes les erreurs de syntaxe restantes en instructions de sortie.

Compilation juste à temps

La compilation juste à temps (JIT) est la génération de code exécutable à la volée ou aussi près que possible de son exécution réelle, pour tirer parti des métriques d' exécution ou d'autres options d'amélioration des performances.

Représentation intermédiaire

La plupart des compilateurs modernes ont un lexer et un analyseur qui produisent une représentation intermédiaire du programme. La représentation intermédiaire est une simple séquence d'opérations qui peut être utilisée par un optimiseur et un générateur de code qui produit des instructions dans le langage machine du processeur cible. Étant donné que le générateur de code utilise une représentation intermédiaire, le même générateur de code peut être utilisé pour de nombreux langages de haut niveau différents.

Il existe de nombreuses possibilités pour la représentation intermédiaire. Le code à trois adresses , également appelé quadruple ou quadruple, est une forme courante, où il y a un opérateur, deux opérandes et un résultat. Le code à deux adresses ou les triplets ont une pile dans laquelle les résultats sont écrits, contrairement aux variables explicites du code à trois adresses.

L'affectation unique statique (SSA) a été développée par Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman et F. Kenneth Zadeck , chercheurs chez IBM dans les années 1980. En SSA, une variable ne reçoit une valeur qu'une seule fois. Une nouvelle variable est créée plutôt que de modifier une existante. SSA simplifie l'optimisation et la génération de code.

Génération de code

Un générateur de code génère des instructions en langage machine pour le processeur cible.

Attribution du registre

L'algorithme Sethi-Ullman ou la numérotation Sethi-Ullman est une méthode pour minimiser le nombre de registres nécessaires pour contenir des variables.

Compilateurs notables

Kit de compilation Amsterdam par Andrew Tanenbaum et Ceriel Jacobs
Berkeley Pascal, écrit par Ken Thompson en 1975. Bill Joy et d'autres à l'Université de Californie, Berkeley ont ajouté des améliorations
GNU Compiler Collection , anciennement le compilateur GNU C. Créé à l'origine par Richard Stallman en 1987, GCC est un compilateur moderne majeur qui est utilisé pour compiler de nombreux projets de logiciels libres, notamment Linux .
LLVM , anciennement connu sous le nom de machine virtuelle de bas niveau
Petit-C par Ron Cain et James E Hendrix
Turbo Pascal , créé par Anders Hejlsberg , sorti pour la première fois en 1983.
WATFOR , créé à l' Université de Waterloo . L'un des premiers compilateurs éducatifs populaires, bien que maintenant largement obsolète.

Voir également

Histoire des langages de programmation
Lex (et l'analyseur lexical Flex ), l'analyseur de jetons couramment utilisé avec yacc (et Bison).
BNF , une métasyntaxe utilisée pour exprimer une grammaire sans contexte : c'est-à-dire une manière formelle de décrire les langages formels.
Auto-interprète , un interprète écrit dans une langue qu'il peut interpréter.

Les références

Lectures complémentaires

Backus, John , et al., "The FORTRAN Automatic Coding System" , Actes de la Western Joint Computer Conference, Los Angeles, Californie, février 1957. Décrit la conception et l'implémentation du premier compilateur FORTRAN par l'équipe IBM.
Knuth, DE, RUNCIBLE-traduction algébrique sur un ordinateur limité , Communications de l'ACM, Vol. 2, p. 18, (novembre 1959).
Irons, Edgar T., Un compilateur orienté syntaxe pour ALGOL 60 , Communications of the ACM, Vol. 4, p. 51. (janvier 1961)
Dijkstra, Edsger W. (1961). " ALGOL 60 Translation: An ALGOL 60 Translator for the X1 and Making a Translator for ALGOL 60 (PDF) (Rapport technique). Amsterdam: Mathematisch Centrum. 35.
Conway, Melvin E. , Conception d'un compilateur de diagramme de transition séparable , Communications de l'ACM, Volume 6, Numéro 7 (Juillet 1963)
Floyd, RW , Analyse syntaxique et priorité des opérateurs , Journal of the ACM, Vol. 10, p. 316. (juillet 1963).
Cheatham, TE, et Sattley, K., compilation dirigée par la syntaxe , SJCC p. 31. (1964).
Randell, Brian ; Russell, Lawford John, Implémentation d'ALGOL 60 : La traduction et l'utilisation des programmes ALGOL 60 sur un ordinateur , Academic Press, 1964
Knuth, DE (juillet 1965). "Sur la traduction des langues de gauche à droite" (PDF) . Informations et contrôle . 8 (6) : 607-639. doi : 10.1016/S0019-9958(65)90426-2 . Archivé de l'original (PDF) le 15 mars 2012 . Consulté le 29 mai 2011 .
Cocke, John ; Schwartz, Jacob T. , Programming Languages and their Compilers: Preliminary Notes , rapport technique du Courant Institute of Mathematical Sciences , Université de New York , 1969.
Bauer, Friedrich L. ; Eickel, Jürgen (Eds.), Compiler Construction, An Advanced Course , 2e éd. Notes de cours en informatique 21, Springer 1976, ISBN 3-540-07542-9
Gries, David , Compiler Construction for Digital Computers , New York : Wiley, 1971. ISBN 0-471-32776-X

Liens externes

Construction du compilateur avant 1980 - Liste de littérature annotée par Dick Grune
"Une histoire d'écriture de compilateurs" (PDF) . Informatique et Automatisation . XI (12) : 8-10, 12, 14, 24-25. décembre 1962.

Languages

In other projects