Geschichte des Compilerbaus - History of compiler construction

In der Informatik ist ein Compiler ein Computerprogramm , das Quellcode , der in einer Programmiersprache oder Computersprache (der Quellsprache ) geschrieben ist, in eine andere Computersprache (die Zielsprache , die oft eine binäre Form hat, die als Objektcode oder Maschinencode bekannt ist ), umwandelt . Der häufigste Grund für die Transformation von Quellcode ist die Erstellung eines ausführbaren Programms.

Jedes Programm, das in einer höheren Programmiersprache geschrieben wurde, muss in Objektcode übersetzt werden, bevor es ausgeführt werden kann, sodass alle Programmierer, die eine solche Sprache verwenden, einen Compiler oder einen Interpreter verwenden . Daher sind Compiler für Programmierer sehr wichtig. Verbesserungen an einem Compiler können zu einer großen Anzahl verbesserter Funktionen in ausführbaren Programmen führen.

Der Production Quality Compiler-Compiler führte in den späten 1970er Jahren die Prinzipien der Compiler-Organisation ein, die heute noch weit verbreitet sind (zB ein Front-End, das Syntax und Semantik behandelt, und ein Back-End, das Maschinencode erzeugt).

Erste Compiler

Software für frühe Computer wurde hauptsächlich in Assembler geschrieben und davor direkt in Maschinencode . Für einen Programmierer ist es normalerweise produktiver, eine Hochsprache zu verwenden, und in einer Hochsprache geschriebene Programme können auf verschiedenen Computertypen wiederverwendet werden . Trotzdem dauerte es eine Weile, bis sich Compiler etablierten, da sie Code generierten, der nicht so leistungsfähig war wie handgeschriebene Assembler, sie selbst entmutigende Entwicklungsprojekte waren und die sehr begrenzte Speicherkapazität früherer Computer viele erzeugte technische Probleme für praktische Compiler-Implementierungen.

Der erste praktische Compiler wurde 1951 von Corrado Böhm für seine Doktorarbeit geschrieben . Der erste implementierte Compiler wurde von Grace Hopper geschrieben , die auch den Begriff "Compiler" prägte und sich auf ihr A-0-System bezog, das als Loader oder Linker fungierte , nicht auf den modernen Begriff eines Compilers. Der erste Autocode und Compiler im modernen Sinne wurden 1952 von Alick Glennie an der University of Manchester für den Mark 1 Computer entwickelt. Das FORTRAN- Team unter der Leitung von John W. Backus bei IBM stellte 1957 den ersten kommerziell erhältlichen Compiler vor, dessen Erstellung 18 Personenjahre dauerte.

Der erste ALGOL 58- Compiler wurde Ende 1958 von Friedrich L. Bauer , Hermann Bottenbruch, Heinz Rutishauser und Klaus Samelson für den Z22- Rechner fertiggestellt. Baueret al. gearbeitet hatte , auf Compiler - Technologie für die sequentielle Formelübersetzung (dh sequentielle Formel Übersetzung ) in den Jahren zuvor.

1960 war ein erweiterter Fortran-Compiler, ALTAC, auf dem Philco 2000 verfügbar , daher ist es wahrscheinlich, dass Mitte 1960 ein Fortran-Programm sowohl für IBM- als auch für Philco- Computerarchitekturen kompiliert wurde . Die erste bekannte demonstrierte plattformübergreifende Hochsprache war COBOL . Bei einer Demonstration im Dezember 1960 wurde ein COBOL-Programm kompiliert und sowohl auf der UNIVAC II als auch auf der RCA 501 ausgeführt.

Selbsthostende Compiler

Wie bei jeder anderen Software bietet die Implementierung eines Compilers in einer Hochsprache Vorteile. Insbesondere kann ein Compiler selbst gehostet werden , also in der Programmiersprache geschrieben werden, die er kompiliert. Das Erstellen eines selbsthostenden Compilers ist ein Bootstrapping- Problem, dh der erste derartige Compiler für eine Sprache muss entweder handgeschriebener Maschinencode sein oder von einem in einer anderen Sprache geschriebenen Compiler kompiliert werden oder durch Ausführen des Compilers in einem Interpreter kompiliert werden .

Corrado Böhm Doktorarbeit

Corrado Böhm entwickelte in seiner Dissertation von 1951 eine Sprache, eine Maschine und eine Übersetzungsmethode, um diese Sprache auf der Maschine zu kompilieren. Er beschrieb nicht nur einen vollständigen Compiler, sondern definierte diesen Compiler erstmals auch in seiner eigenen Sprache. Die Sprache war an sich interessant, weil jede Anweisung (einschließlich Eingabeanweisungen, Ausgabeanweisungen und Kontrollanweisungen) ein Sonderfall einer Zuweisungsanweisung war .

NELIAC

Der Navy Electronics Laboratory International ALGOL Compiler oder NELIAC war eine Dialekt- und Compiler-Implementierung der Programmiersprache ALGOL 58, die 1958 vom Naval Electronics Laboratory entwickelt wurde.

NELIAC war die Idee von Harry Huskey – damals Vorsitzender des ACM und ein bekannter Informatiker (und später akademischer Betreuer von Niklaus Wirth ) und unterstützt von Maury Halstead, dem Leiter des Rechenzentrums bei NEL. Die früheste Version wurde auf dem Prototyp des USQ-17- Computers (genannt Countess) im Labor implementiert . Es war der erste selbstkompilierende Compiler der Welt - der Compiler wurde zunächst in vereinfachter Form in Assembler (dem Bootstrap ) codiert , dann in seiner eigenen Sprache neu geschrieben und vom Bootstrap kompiliert und schließlich selbst neu kompiliert, wodurch die Bootstrap obsolet.

Lispeln

Ein weiterer früher selbsthostender Compiler wurde 1962 von Tim Hart und Mike Levin am MIT für Lisp geschrieben . Sie schrieben einen Lisp-Compiler in Lisp und testeten ihn in einem vorhandenen Lisp-Interpreter. Nachdem sie den Compiler so weit verbessert hatten, dass er seinen eigenen Quellcode kompilieren konnte, war er selbst-hosting.

Der Compiler, wie er auf dem Standard-Compilerband existiert, ist ein Maschinensprachenprogramm, das erhalten wurde, indem die S-Ausdrucksdefinition des Compilers durch den Interpreter an sich selbst arbeiten ließ. (KI-Memo 39)

Diese Technik ist nur möglich, wenn bereits ein Interpreter für dieselbe zu kompilierende Sprache vorhanden ist. Es leiht sich direkt aus dem Begriff auf sich selbst als Eingabe ein Programm ausgeführt wird , die auch in verschiedenen Beweise verwendet wird , der theoretischen Informatik , wie der Beweis dafür , dass das Halteproblem ist unentscheidbar .

Weiter

Forth ist ein Beispiel für einen selbsthostenden Compiler. Die Selbstkompilierungs- und Kreuzkompilierungsfunktionen von Forth werden häufig mit Metakompilierung und Metacompilern verwechselt . Wie Lisp ist Forth eine erweiterbare Programmiersprache . Es sind die erweiterbaren Programmiersprachenfunktionen von Forth und Lisp, die es ihnen ermöglichen, neue Versionen von sich selbst zu generieren oder sich auf neue Umgebungen zu portieren.

Kontextfreie Grammatiken und Parser

Ein Parser ist ein wichtiger Bestandteil eines Compilers. Es parst den Quellcode einer Computerprogrammiersprache, um eine Form der internen Repräsentation zu erstellen. Programmiersprachen werden in der Regel im Sinne einer kontextfreien Grammatik spezifiziert, weil für sie schnelle und effiziente Parser geschrieben werden können. Parser können von Hand geschrieben oder von einem Parser-Generator generiert werden . Eine kontextfreie Grammatik bietet einen einfachen und präzisen Mechanismus, um zu beschreiben, wie Programmiersprachenkonstrukte aus kleineren Blöcken aufgebaut werden . Der Formalismus kontextfreier Grammatiken wurde Mitte der 1950er Jahre von Noam Chomsky entwickelt .

Die Blockstruktur wurde durch das ALGOL-Projekt (1957–1960) in Computerprogrammiersprachen eingeführt, das folglich auch eine kontextfreie Grammatik zur Beschreibung der resultierenden ALGOL-Syntax aufwies.

Kontextfreie Grammatiken sind einfach genug, um effiziente Parsing-Algorithmen zu konstruieren, die für einen gegebenen String bestimmen, ob und wie er aus der Grammatik generiert werden kann. Wenn ein Programmiersprachendesigner bereit ist, innerhalb einiger begrenzter Teilmengen kontextfreier Grammatiken zu arbeiten, sind effizientere Parser möglich.

LR-Parsing

Der LR-Parser (von links nach rechts) wurde 1965 von Donald Knuth in einem Artikel "On the Translation of Languages from Left to Right" erfunden . Ein LR Parser ein Parser, der eine Eingabe von liest L inks nach rechts und erzeugt eine (wie es bei optisch angezeigt erscheinen würde) R ightmost Ableitung . Der Begriff LR( k )-Parser wird auch verwendet, wobei sich k auf die Anzahl nicht verbrauchter Lookahead- Eingabesymbole bezieht, die beim Treffen von Parsing-Entscheidungen verwendet werden.

Knuth bewies, dass LR( k )-Grammatiken mit einer zur Programmlänge im Wesentlichen proportionalen Ausführungszeit geparst werden können, und dass jede LR( k )-Grammatik für k > 1 mechanisch in eine LR(1)-Grammatik für dasselbe umgewandelt werden kann Sprache. Mit anderen Worten, es ist nur ein Symbol-Lookahead erforderlich, um jede deterministische kontextfreie Grammatik (DCFG) zu parsen .

Korenjak (1969) zeigte als erster, dass mit diesen Techniken Parser für Programmiersprachen erzeugt werden können. Frank DeRemer entwickelte die praktischeren Techniken Simple LR (SLR) und Look-ahead LR (LALR), die 1969 in seiner Doktorarbeit am MIT veröffentlicht wurden. Dies war ein wichtiger Durchbruch, da LR(k)-Übersetzer, wie von Donald Knuth definiert, waren in den 1960er und 1970er Jahren viel zu groß für die Implementierung auf Computersystemen.

In der Praxis bietet LALR eine gute Lösung; die zusätzliche Leistung von LALR(1)-Parsern gegenüber SLR(1)-Parsern (d. h. LALR(1) kann komplexere Grammatiken analysieren als SLR(1)) ist nützlich, und obwohl LALR(1) nicht mit LL( 1)(Siehe unten) (LALR(1) kann nicht alle LL(1)-Grammatiken parsen), die meisten in der Praxis angetroffenen LL(1)-Grammatiken können von LALR(1) geparst werden. LR(1)-Grammatiken sind wieder mächtiger als LALR(1); eine LR(1)-Grammatik erfordert jedoch einen kanonischen LR-Parser, der extrem groß wäre und als nicht praktikabel angesehen wird. Die Syntax vieler Programmiersprachen wird durch Grammatiken definiert, die mit einem LALR(1)-Parser geparst werden können, und aus diesem Grund werden LALR-Parser oft von Compilern verwendet, um eine Syntaxanalyse des Quellcodes durchzuführen.

Ein rekursiver Ascent-Parser implementiert einen LALR-Parser, der wechselseitig rekursive Funktionen anstelle von Tabellen verwendet. Somit wird der Parser direkt in der Hostsprache kodiert, ähnlich wie beim rekursiven Abstieg . Die direkte Codierung liefert normalerweise einen Parser, der schneller ist als sein tabellengesteuertes Äquivalent, aus dem gleichen Grund, aus dem die Kompilierung schneller ist als die Interpretation. Es ist auch (im Prinzip) möglich, einen rekursiven Ascent-Parser von Hand zu bearbeiten, während eine tabellarische Implementierung für den Durchschnittsmenschen nahezu unlesbar ist.

Der rekursive Aufstieg wurde erstmals 1986 von Thomas Pennello in seinem Artikel "Very fast LR parsing" beschrieben. Die Technik wurde später von GH Roberts 1988 sowie in einem Artikel von Leermakers, Augusteijn, Kruseman Aretz 1992 in der Zeitschrift Theoretical . erläutert Informatik .

LL-Parsing

Ein LL - Parser parst den Eingang von L inks nach rechts, und konstruiert eine L eftmost Ableitung des Satzes (daher LL, LR zu gegen). Die Klasse von Grammatiken, die auf diese Weise geparst werden können, wird als LL-Grammatik bezeichnet . LL-Grammatiken sind eine noch eingeschränktere Klasse kontextfreier Grammatiken als LR-Grammatiken. Dennoch sind sie für Compiler-Autoren von großem Interesse, da ein solcher Parser einfach und effizient zu implementieren ist.

LL(k)-Grammatiken können mit einem rekursiven Descent-Parser geparst werden, der normalerweise von Hand codiert wird, obwohl alternativ eine Notation wie META II verwendet werden könnte.

Das Design von ALGOL hat die Untersuchung des rekursiven Abstiegs ausgelöst, da die ALGOL-Sprache selbst rekursiv ist. Das Konzept des rekursiven Descent-Parsings wurde in der Januar-Ausgabe 1961 von Communications of the ACM in separaten Artikeln von AA Grau und Edgar T. "Ned" Irons diskutiert . Richard Waychoff und Kollegen implementierten im März 1961 auch rekursiven Abstieg in den Burroughs ALGOL Compiler, die beiden Gruppen verwendeten unterschiedliche Ansätze, standen aber zumindest in informellem Kontakt.

Die Idee der LL(1)-Grammatik wurde von Lewis und Stearns (1968) eingeführt.

Die rekursive Abstammung wurde von Niklaus Wirth mit PL/0 populär gemacht , einer pädagogischen Programmiersprache , die in den 1970er Jahren zum Lehren des Compilerbaus verwendet wurde.

LR-Parsing kann mit einem größeren Sprachumfang umgehen als LL-Parsing und ist auch besser bei der Fehlerberichterstattung (dies ist umstritten, REFERENCE ist erforderlich), dh es erkennt syntaktische Fehler, wenn die Eingabe nicht der Grammatik entspricht, so schnell wie möglich.

Früher Parser

1970 erfand Jay Earley den sogenannten Earley-Parser . Early-Parser sind attraktiv, weil sie alle kontextfreien Sprachen einigermaßen effizient parsen können .

Sprachen zur Grammatikbeschreibung

John Backus schlug "metallinguistische Formeln" vor, um die Syntax der neuen Programmiersprache IAL zu beschreiben, die heute als ALGOL 58 (1959) bekannt ist. Die Arbeit von Backus basierte auf dem kanonischen System der Post, das von Emil Post entwickelt wurde .

Die Weiterentwicklung von ALGOL führte zu ALGOL 60 ; Peter Naur nannte in seinem Bericht (1963) die Notation von Backus Backus Normalform (BNF) und vereinfachte sie, um den verwendeten Zeichensatz zu minimieren. Allerdings Donald Knuth argumentiert , dass BNF eher als gelesen wird Backus-Naur Form , und das hat die allgemein akzeptierte Nutzung worden.

Niklaus Wirth definierte Anfang der 1970er Jahre die erweiterte Backus-Naur-Form (EBNF), eine verfeinerte Version von BNF, für PL/0. Eine weitere Variante ist die Augmented Backus-Naur-Form (ABNF). Sowohl EBNF als auch ABNF werden häufig verwendet, um die Grammatik von Programmiersprachen zu spezifizieren, als Eingaben für Parser-Generatoren und in anderen Bereichen wie der Definition von Kommunikationsprotokollen.

Parser-Generatoren

Ein Parser-Generator generiert den lexikalischen Analysator-Teil eines Compilers. Es ist ein Programm, das eine Beschreibung einer formalen Grammatik einer bestimmten Programmiersprache nimmt und einen Parser für diese Sprache erzeugt. Dieser Parser kann in einem Compiler für diese spezielle Sprache verwendet werden. Der Parser erkennt und identifiziert die reservierten Wörter und Symbole der spezifischen Sprache aus einem Textstrom und gibt diese als Token an den Code zurück, der die syntaktische Validierung und Übersetzung in Objektcode implementiert. Dieser zweite Teil des Compilers kann auch von einem Compiler-Compiler erstellt werden, der eine formale Syntaxbeschreibung nach Vorrangregeln als Eingabe verwendet.

Der erste Compiler-Compiler , der diesen Namen verwendet, wurde 1960 von Tony Brooker geschrieben und wurde verwendet, um Compiler für den Atlas- Computer an der University of Manchester zu erstellen , einschließlich des Atlas Autocode- Compilers. Es unterschied sich jedoch ziemlich von modernen Compiler-Compilern und würde heute wahrscheinlich als irgendwo zwischen einem hochgradig anpassbaren generischen Compiler und einer erweiterbaren Syntaxsprache beschrieben . Der Name "Compiler-Compiler" war für Brookers System viel passender als für die meisten modernen Compiler-Compiler, die genauer als Parser-Generatoren bezeichnet werden. Es ist fast sicher, dass der Name "Compiler-Compiler" gebräuchlich ist, weil Yacc und nicht Brookers Arbeit in Erinnerung geblieben ist.

In den frühen 1960er Jahren erfand Robert McClure von Texas Instruments einen Compiler-Compiler namens TMG , der Name stammt von "Transmogrification". In den folgenden Jahren wurde TMG auf mehrere UNIVAC und IBM Großrechner portiert .

Das Multics- Projekt, ein Joint Venture von MIT und Bell Labs , war eines der ersten, das ein Betriebssystem in einer Hochsprache entwickelte. Als Sprache wurde PL/I gewählt, aber ein externer Anbieter konnte keinen funktionierenden Compiler liefern. Das Multics-Team entwickelte 1964 einen eigenen Untergruppendialekt von PL/I, bekannt als Early PL/I (EPL) als Implementierungssprache. TMG wurde auf die GE-600-Serie portiert und von Douglas McIlroy , Robert Morris und anderen zur Entwicklung von EPL verwendet .

Nicht lange nachdem Ken Thompson 1969 die erste Unix- Version für die PDP-7 geschrieben hatte, schuf Douglas McIlroy die erste höhere Sprache des neuen Systems: eine Implementierung von McClures TMG. TMG war auch das Compiler - Definition - Tool von Ken Thompson verwendet , um den Compiler für die schreiben B Sprache auf seinem PDP-7 im Jahr 1970 B war der unmittelbare Vorfahr C .

Ein früher LALR-Parser-Generator wurde "TWS" genannt und von Frank DeRemer und Tom Pennello entwickelt.

XPL

XPL ist ein Dialekt der PL/I- Programmiersprache , der für die Entwicklung von Compilern für Computersprachen verwendet wird. Es wurde 1967 von einem Team mit William M. McKeeman , James J. Horning und David B. Wortman an der Stanford University und der University of California, Santa Cruz entworfen und implementiert . Es wurde erstmals auf der Fall Joint Computer Conference 1968 in San Francisco angekündigt .

XPL verfügte über ein relativ einfaches Übersetzer-Schreibsystem namens ANALYZER , das auf einer Bottom-up-Compiler- Vorrang-Parsing-Technik namens MSP (Mixed Strategy Precedence) basiert . XPL wurde durch Burroughs Algol auf den IBM System/360- Computer gebootet . (Einige spätere Versionen von XPL, die in internen Projekten der University of Toronto verwendet wurden , verwendeten einen SLR(1)-Parser, aber diese Implementierungen wurden nie verteilt).

Yacc

Yacc ist ein Parser-Generator (kurz: Compiler-Compiler ), nicht zu verwechseln mit lex , einem lexikalischen Analysator, der häufig als erste Stufe von Yacc verwendet wird. Yacc wurde von Stephen C. Johnson bei AT&T für das Unix- Betriebssystem entwickelt. Der Name ist ein Akronym für „ Noch Another Compiler Compiler “. Es generiert einen LALR(1)-Compiler basierend auf einer Grammatik, die in einer Notation ähnlich der Backus-Naur-Form geschrieben ist.

Johnson arbeitete in den frühen 1970er Jahren bei Bell Labs an Yacc . Er war mit TMG vertraut und sein Einfluss zeigt sich in Yacc und dem Design der Programmiersprache C. Da Yacc auf den meisten Unix-Systemen der Standard-Compiler-Generator war, wurde er weit verbreitet und verwendet. Derivate wie GNU Bison werden noch verwendet.

Der von Yacc generierte Compiler erfordert einen lexikalischen Analysator . Lexikalische Analysegeneratoren wie lex oder flex sind weit verbreitet. Der Standard IEEE POSIX P1003.2 definiert die Funktionalität und Anforderungen sowohl für Lex als auch für Yacc.

Coco/R

Coco/R ist ein Parser-Generator , der LL(1)-Parser in Modula-2 (mit Plug-Ins für andere Sprachen) aus Eingabegrammatiken generiert, die in einer Variante von EBNF geschrieben wurden. Es wurde 1985 von Hanspeter Mössenböck an der Eidgenössischen Technischen Hochschule Zürich (ETHZ) entwickelt.

ANTLR

ANTLR ist ein Parser-Generator , der LL(*)-Parser in Java aus Eingabegrammatiken generiert, die in einer Variante von EBNF geschrieben wurden. Es wurde Anfang der 1990er Jahre von Terence Parr an der University of San Francisco als Nachfolger eines früheren Generators namens PCCTS entwickelt.

Metacompiler

Metacompiler unterscheiden sich von Parser-Generatoren und nehmen als Eingabe ein in einer Metasprache geschriebenes Programm . Ihre Eingabe besteht aus grammatikalischen Formeln, die mit eingebetteten Transformationsoperationen kombiniert werden, die abstrakte Syntaxbäume konstruieren, oder einfach neu formatierte Textstrings ausgeben, die Stack-Maschinencode sein können.

Viele können in ihrer eigenen Metasprache programmiert werden, sodass sie sich selbst kompilieren können, was sie zu selbsthostenden erweiterbaren Sprachcompilern macht.

Viele Metacompiler bauen auf der Arbeit von Dewey Val Schorre auf . Sein 1964 erstmals veröffentlichter META II- Compiler war der erste dokumentierte Metacompiler. In der Lage, seine eigene Sprache und andere zu definieren, akzeptierte META II eine Syntaxformel mit eingebetteter Ausgabe (Codeproduktion) . Es wurde auch in eine der frühesten Instanzen einer virtuellen Maschine übersetzt . Die lexikalische Analyse wurde durch eingebaute Token-Erkennungsfunktionen durchgeführt: .ID, .STRING und .NUMBER. Strings in Anführungszeichen in der Syntaxformel erkennen Lexeme, die nicht beibehalten werden.

TREE-META , ein Schorre- Metacompiler der zweiten Generation, erschien um 1968. Er erweiterte die Fähigkeiten von META II und fügte Unparse-Regeln hinzu, die die Codeproduktion von der Grammatikanalyse trennen. Baumtransformationsoperationen in der Syntaxformel erzeugen abstrakte Syntaxbäume, auf denen die Unparse-Regeln arbeiten. Die Entparse-Baummusterübereinstimmung lieferte die Fähigkeit zur Guckloch-Optimierung .

CWIC , beschrieben in einer ACM-Veröffentlichung von 1970, ist ein Schorre-Metacompiler der dritten Generation, der Lexing-Regeln und Backtracking-Operatoren zur Grammatikanalyse hinzufügte. LISP 2 wurde mit den Unparse-Regeln von TREEMETA in der CWIC-Generatorsprache verheiratet. Mit der LISP 2-Verarbeitung[[]] kann CWIC vollständig optimierten Code generieren. CWIC ermöglichte auch die Generierung von Binärcode in benannte Codeabschnitte. Single- und Multipass-Compilierungen könnten unter Verwendung von CWIC implementiert werden.

CWIC kompiliert zu 8-Bit-Byte-adressierbaren Maschinencode-Befehlen, die hauptsächlich entwickelt wurden, um IBM System/360-Code zu erzeugen.

Spätere Generationen sind nicht öffentlich dokumentiert. Ein wichtiges Merkmal wäre die Abstraktion des Befehlssatzes des Zielprozessors, der Makros zu einem Pseudomaschinenbefehlssatz erzeugt, die separat definiert oder auf die Befehle einer realen Maschine abgebildet werden könnten. Optimierungen, die auf sequentielle Befehle angewendet werden, könnten dann auf den Pseudobefehl angewendet werden, bevor er auf den Zielmaschinencode erweitert wird.

Cross-Zusammenstellung

Ein Cross-Compiler läuft in einer Umgebung, erzeugt aber Objektcode für eine andere. Cross-Compiler werden für die eingebettete Entwicklung verwendet, bei der der Zielcomputer über begrenzte Fähigkeiten verfügt.

Ein frühes Beispiel für Kreuzkompilierung war AIMICO, bei dem ein FLOW-MATIC-Programm auf einem UNIVAC II verwendet wurde, um eine Assemblersprache für die IBM 705 zu generieren , die dann auf dem IBM-Computer assembliert wurde.

Der ALGOL 68C- Compiler generierte eine ZCODE- Ausgabe, die dann entweder von einem ZCODE- Übersetzer in den lokalen Maschinencode kompiliert oder interpretiert ausgeführt werden konnte. ZCODE ist eine registerbasierte Zwischensprache. Diese Fähigkeit, ZCODE zu interpretieren oder zu kompilieren, förderte die Portierung von ALGOL 68C auf zahlreiche verschiedene Computerplattformen.

Compiler optimieren

Compileroptimierung ist der Prozess der Verbesserung der Qualität von Objektcode, ohne die Ergebnisse zu ändern, die er erzeugt.

Die Entwickler des ersten FORTRAN- Compilers wollten Code generieren, der besser ist als der durchschnittliche handcodierte Assembler, damit die Kunden ihr Produkt auch tatsächlich nutzen. In einem der ersten echten Compiler gelang ihnen oft.

Spätere Compiler, wie der Fortran IV- Compiler von IBM , legten auf Kosten der Objektcodeoptimierung mehr Wert auf eine gute Diagnose und eine schnellere Ausführung . Erst mit der IBM System/360-Serie stellte IBM zwei separate Compiler zur Verfügung – einen schnell ausführenden Code-Checker und einen langsameren, optimierenden.

Frances E. Allen stellte allein und gemeinsam mit John Cocke viele der Optimierungskonzepte vor. Allens 1966 erschienenes Papier, Program Optimization, führte die Verwendung von Graphdatenstrukturen ein , um Programminhalte für die Optimierung zu codieren. Ihre Veröffentlichungen von 1970, Control Flow Analysis und A Basis for Program Optimization, etablierten Intervalle als Kontext für eine effiziente und effektive Datenflussanalyse und -optimierung. Ihr Artikel von 1971 mit Cocke, A Catalogue of Optimizing Transformations , lieferte die erste Beschreibung und Systematisierung von Optimierungstransformationen. Ihre Arbeiten von 1973 und 1974 zur interprozeduralen Datenflussanalyse erweiterten die Analyse auf ganze Programme. Ihr Artikel von 1976 mit Cocke beschreibt eine der beiden wichtigsten Analysestrategien, die heute bei der Optimierung von Compilern verwendet werden.

Allen entwickelt und implementiert ihre Methoden als Teil der Compiler für die IBM 7030 Stretch - Ernte und der experimentellen Advanced Computing Systems . Diese Arbeit stellte die Machbarkeit und Struktur moderner maschinen- und sprachunabhängiger Optimierer her. Anschließend gründete und leitete sie das PTRAN- Projekt zur automatischen parallelen Ausführung von FORTRAN-Programmen. Ihr PTRAN-Team entwickelte neue Parallelismus-Erkennungsschemata und schuf das Konzept des Programmabhängigkeitsgraphen, der primären Strukturierungsmethode, die von den meisten parallelisierenden Compilern verwendet wird.

Programmiersprachen und ihre Compiler von John Cocke und Jacob T. Schwartz , veröffentlicht Anfang 1970, widmeten mehr als 200 Seiten Optimierungsalgorithmen. Es beinhaltete viele der heute bekannten Techniken wie die Eliminierung von redundantem Code und die Reduzierung der Stärke .

Guckloch-Optimierung

Die Peephole-Optimierung ist eine einfache, aber effektive Optimierungstechnik. Es wurde von William M. McKeeman erfunden und 1965 in CACM veröffentlicht. Es wurde im XPL-Compiler verwendet, den McKeeman mitentwickelt hat.

Capex COBOL-Optimierer

Die Capex Corporation entwickelte Mitte der 1970er Jahre den "COBOL Optimizer" für COBOL . Dieser Optimierertyp hing in diesem Fall von der Kenntnis der "Schwächen" des Standard-IBM-COBOL-Compilers ab und ersetzte (oder korrigierte ) Abschnitte des Objektcodes tatsächlich durch effizienteren Code. Der Ersetzungscode kann beispielsweise eine lineare Tabellensuche durch eine binäre Suche ersetzen oder manchmal einfach einen relativ "langsamen" Befehl durch einen bekannten schnelleren Befehl ersetzen, der ansonsten in seinem Kontext funktionell äquivalent war. Diese Technik wird heute als „ Kraftabbau “ bezeichnet. Auf der IBM System/360- Hardware war der CLI- Befehl beispielsweise je nach Modell zwischen doppelt und fünfmal so schnell wie ein CLC- Befehl für Einzelbyte-Vergleiche.

Moderne Compiler bieten normalerweise Optimierungsoptionen, damit Programmierer wählen können, ob sie einen Optimierungsdurchlauf ausführen möchten oder nicht.

Diagnose

Wenn einem Compiler ein syntaktisch fehlerhaftes Programm übergeben wird, ist eine gute, klare Fehlermeldung hilfreich. Aus der Sicht des Compiler-Autors ist dies oft schwer zu erreichen.

Der WATFIV Fortran-Compiler wurde Ende der 1960er Jahre an der University of Waterloo in Kanada entwickelt. Es wurde entwickelt, um bessere Fehlermeldungen auszugeben als die damaligen Fortran-Compiler von IBM. Darüber hinaus war WATFIV weitaus benutzerfreundlicher, da es Kompilieren, Linken und Ausführen in einem Schritt kombinierte , während die Compiler von IBM drei separate Komponenten zum Ausführen hatten.

PL/C

PL/C war eine Computerprogrammiersprache, die Anfang der 1970er Jahre an der Cornell University entwickelt wurde. Obwohl PL/C eine Teilmenge der PL/I-Sprache von IBM war, wurde es mit dem spezifischen Ziel entwickelt, für den Programmierunterricht verwendet zu werden. Die beiden Forscher und akademischen Lehrer, die PL/C entworfen haben, waren Richard W. Conway und Thomas R. Wilcox. Sie legten den berühmten Artikel "Design and Implementation of a Diagnostic Compiler for PL/I" vor, der im März 1973 in den Communications of ACM veröffentlicht wurde.

PL/C eliminierte einige der komplexeren Funktionen von PL/I und fügte umfangreiche Debugging- und Fehlerbehebungsfunktionen hinzu. Der PL/C-Compiler hatte die ungewöhnliche Fähigkeit, jedes Programm zu kompilieren, indem er viele Syntaxfehler umfassend automatisch korrigierte und alle verbleibenden Syntaxfehler in Ausgabeanweisungen umwandelte.

Just-in-time-Zusammenstellung

Zusammenstellung Just-in-Time (JIT) ist die Erzeugung von ausführbarem Code on-the-fly oder so nah wie möglich an die tatsächlichen Ausführung, unter Ausnutzung der Laufzeit zu nehmen Metriken oder anderer leistungssteigernde Optionen.

Zwischenvertretung

Die meisten modernen Compiler verfügen über einen Lexer und einen Parser, die eine Zwischendarstellung des Programms erzeugen. Die Zwischendarstellung ist eine einfache Folge von Operationen, die von einem Optimierer und einem Codegenerator verwendet werden kann, der Anweisungen in der Maschinensprache des Zielprozessors erzeugt. Da der Codegenerator eine Zwischendarstellung verwendet, kann derselbe Codegenerator für viele verschiedene Hochsprachen verwendet werden.

Für die Zwischendarstellung gibt es viele Möglichkeiten. Drei-Adress-Code , auch als Quadrupel oder Quad bekannt, ist eine gebräuchliche Form, bei der es einen Operator, zwei Operanden und ein Ergebnis gibt. Zwei-Adress-Code oder Tripel haben einen Stack, auf den die Ergebnisse geschrieben werden, im Gegensatz zu den expliziten Variablen des Drei-Adress-Codes.

Static Single Assignment (SSA) wurde in den 1980er Jahren von Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman und F. Kenneth Zadeck , Forschern bei IBM, entwickelt . In SSA wird einer Variablen nur einmal ein Wert zugewiesen. Es wird eine neue Variable erstellt, anstatt eine vorhandene zu ändern. SSA vereinfacht die Optimierung und Codegenerierung.

Codegenerierung

Ein Codegenerator erzeugt Maschinensprachbefehle für den Zielprozessor.

Registerzuordnung

Der Sethi-Ullman-Algorithmus oder die Sethi-Ullman-Nummerierung ist eine Methode, um die Anzahl der Register zu minimieren, die zum Halten von Variablen erforderlich sind.

Bemerkenswerte Compiler

Amsterdam Compiler Kit von Andrew Tanenbaum und Ceriel Jacobs
Berkeley Pascal, geschrieben von Ken Thompson im Jahr 1975. Bill Joy und andere von der University of California, Berkeley fügten Verbesserungen hinzu
GNU Compiler Collection , früher GNU C Compiler. GCC wurde ursprünglich 1987 von Richard Stallman verfasst und ist ein bedeutender moderner Compiler, der zum Kompilieren vieler freier Softwareprojekte , insbesondere Linux, verwendet wird .
LLVM , früher bekannt als Low Level Virtual Machine
Small-C von Ron Cain und James E. Hendrix
Turbo Pascal , erstellt von Anders Hejlsberg , erstmals 1983 veröffentlicht.
WATFOR , erstellt an der University of Waterloo . Einer der ersten populären pädagogischen Compiler, obwohl er heute weitgehend veraltet ist.

Siehe auch

Geschichte der Programmiersprachen
Lex (und Flex lexical Analyzer ), der Token-Parser, der häufig in Verbindung mit yacc (und Bison) verwendet wird.
BNF , eine Metasyntax, die verwendet wird, um kontextfreie Grammatik auszudrücken , dh eine formale Art, formale Sprachen zu beschreiben.
Selbstdolmetscher , ein Dolmetscher, der in einer Sprache geschrieben ist, die er interpretieren kann.

Verweise

Weiterlesen

Backus, John et al., "The FORTRAN Automatic Coding System" , Proceedings of the Western Joint Computer Conference, Los Angeles, Kalifornien, Februar 1957. Beschreibt den Entwurf und die Implementierung des ersten FORTRAN-Compilers durch das IBM-Team.
Knuth, DE, RUNCIBLE-algebraic translation on a limited computer , Communications of the ACM, Vol. 2 , No. 2, s. 18, (Nov. 1959).
Irons, Edgar T., A Syntax-directed Compiler for ALGOL 60 , Communications of the ACM, Vol. 2, No. 4, s. 51. (Januar 1961)
Dijkstra, Edsger W. (1961). "ALGOL 60 Translation: An ALGOL 60 Translator for the X1 and Making a Translator for ALGOL 60 (PDF) (Technical report). Amsterdam: Mathematisch Centrum. 35.
Conway, Melvin E. , Entwurf eines trennbaren Übergangsdiagramm-Compilers , Mitteilungen des ACM, Band 6, Ausgabe 7 (Juli 1963)
Floyd, RW , Syntaktische Analyse und Operator-Präzedenz , Journal of the ACM, Vol. 2, No. 10, s. 316. (Juli 1963).
Cheatham, TE, und Sattley, K., Syntax-directed Compilation , SJCC p. 31. (1964).
Randell, Brian ; Russell, Lawford John, ALGOL 60 Implementation: The Translation and Use of ALGOL 60 Programs on a Computer , Academic Press, 1964
Knuth, DE (Juli 1965). "Über die Übersetzung von Sprachen von links nach rechts" (PDF) . Information und Kontrolle . 8 (6): 607–639. doi : 10.1016/S0019-9958(65)90426-2 . Archiviert vom Original (PDF) am 15. März 2012 . Abgerufen am 29. Mai 2011 .
Cocke, John ; Schwartz, Jacob T. , Programming Languages and their Compilers: Preliminary Notes , Courant Institute of Mathematical Sciences Technical report, New York University , 1969.
Bauer, Friedrich L. ; Eickel, Jürgen (Hrsg.), Compilerbau, An Advanced Course , 2. Aufl. Vorlesungsskript in Informatik 21, Springer 1976, ISBN 3-540-07542-9
Gries, David , Compilerkonstruktion für Digitalcomputer , New York: Wiley, 1971. ISBN 0-471-32776-X

Externe Links

Compilerbau vor 1980 — Kommentierte Literaturliste von Dick Grune
"Eine Geschichte des Schreibens von Compilern" (PDF) . Computer und Automatisierung . XI (12): 8–10, 12, 14, 24–25. Dezember 1962.

Languages

In other projects