Compiler - Compiler

In Computing , ein Compiler ist ein Computerprogramm , das übersetzt in einer geschriebenen Computercode Programmiersprache (die Quellsprache) in einer anderen Sprache (die Zielsprache). Der Name "Compiler" wird hauptsächlich für Programme verwendet, die Quellcode von einer höheren Programmiersprache in eine niedrigere Programmiersprache (zB Assemblersprache , Objektcode oder Maschinencode ) übersetzen, um ein ausführbares Programm zu erstellen .

Es gibt viele verschiedene Arten von Compilern, die Ausgaben in verschiedenen nützlichen Formen erzeugen. Ein Cross-Compiler erzeugt Code für eine andere CPU oder ein anderes Betriebssystem als das, auf dem der Cross-Compiler selbst läuft. Ein Bootstrap-Compiler ist in der Sprache geschrieben, die er kompilieren möchte. Ein Programm, das von einer niedrigeren Sprache in eine höhere Sprache übersetzt, ist ein Decompiler . Ein Programm, das zwischen höheren Sprachen übersetzt, wird normalerweise als Source-to-Source-Compiler oder Transpiler bezeichnet . Ein Sprachumschreiber ist normalerweise ein Programm, das die Form von Ausdrücken ohne Sprachwechsel übersetzt. Ein Compiler-Compiler ist ein Compiler, der einen Compiler (oder einen Teil davon) erzeugt.

Ein Compiler führt wahrscheinlich einige oder alle der folgenden Operationen durch, die oft als Phasen bezeichnet werden: Vorverarbeitung , lexikalische Analyse , Parsing , semantische Analyse ( syntaxgerichtete Übersetzung ), Umwandlung von Eingabeprogrammen in eine Zwischendarstellung , Codeoptimierung und Codegenerierung . Compiler implementieren diese Phasen im Allgemeinen als modulare Komponenten, wodurch ein effizientes Design und die Korrektheit der Transformationen der Quelleingabe in die Zielausgabe gefördert werden. Programmfehler, die durch falsches Compilerverhalten verursacht werden, können sehr schwer aufzuspüren und zu umgehen sein; Daher investieren Compiler-Implementierer erhebliche Anstrengungen, um die Korrektheit des Compilers sicherzustellen .

Compiler sind nicht der einzige Sprachprozessor, der verwendet wird, um Quellprogramme zu transformieren. Ein Interpreter ist eine Computersoftware, die die angegebenen Operationen umwandelt und dann ausführt. Der Übersetzungsprozess beeinflusst das Design von Computersprachen, was zu einer bevorzugten Kompilierung oder Interpretation führt. Theoretisch kann eine Programmiersprache sowohl einen Compiler als auch einen Interpreter haben. In der Praxis werden Programmiersprachen meist nur mit einer (einem Compiler oder einem Interpreter) assoziiert.

Geschichte

Ein Diagramm der Funktionsweise eines typischen mehrsprachigen Compilers mit mehreren Zielen

Theoretische Computerkonzepte, die von Wissenschaftlern, Mathematikern und Ingenieuren entwickelt wurden, bildeten während des Zweiten Weltkriegs die Grundlage für die Entwicklung des digitalen modernen Computers. Primitive Binärsprachen haben sich entwickelt, weil digitale Geräte nur Einsen und Nullen und die Schaltungsmuster in der zugrunde liegenden Maschinenarchitektur verstehen. In den späten 1940er Jahren wurden Assemblersprachen entwickelt, um eine praktikablere Abstraktion der Computerarchitekturen anzubieten. Die begrenzte Speicherkapazität früher Computer führte bei der Entwicklung der ersten Compiler zu erheblichen technischen Herausforderungen. Daher musste der Kompilierungsvorgang in mehrere kleine Programme aufgeteilt werden. Die Front-End-Programme produzieren die Analyseprodukte, die von den Back-End-Programmen verwendet werden, um Zielcode zu generieren. Da die Computertechnologie mehr Ressourcen bereitstellte, konnten Compilerdesigns besser auf den Kompilierungsprozess abgestimmt werden.

Normalerweise ist es für einen Programmierer produktiver, eine Hochsprache zu verwenden, daher folgte die Entwicklung von Hochsprachen natürlich auf die Fähigkeiten digitaler Computer. Hochsprachen sind formale Sprachen , die durch ihre Syntax und Semantik streng definiert sind und die Hochsprachenarchitektur bilden. Elemente dieser formalen Sprachen sind:

  • Alphabet , eine endliche Menge von Symbolen;
  • String , eine endliche Folge von Symbolen;
  • Sprache , ein beliebiger Satz von Zeichenfolgen in einem Alphabet.

Die Sätze in einer Sprache können durch eine Reihe von Regeln definiert werden, die als Grammatik bezeichnet werden.

Die Backus-Naur-Form (BNF) beschreibt die Syntax von "Sätzen" einer Sprache und wurde für die Syntax von Algol 60 von John Backus verwendet . Die Ideen leiten sich von den kontextfreien Grammatikkonzepten des Linguisten Noam Chomsky ab . "BNF und seine Erweiterungen sind zu Standardwerkzeugen geworden, um die Syntax von Programmiernotationen zu beschreiben, und in vielen Fällen werden Teile von Compilern automatisch aus einer BNF-Beschreibung generiert."

In den 1940er Jahren entwarf Konrad Zuse eine algorithmische Programmiersprache namens Plankalkül . Obwohl bis in die 1970er Jahre keine tatsächliche Implementierung erfolgte, wurden Konzepte vorgestellt, die später in APL von Ken Iverson in den späten 1950er Jahren zu sehen waren. APL ist eine Sprache für mathematische Berechnungen.

Das Hochsprachendesign während der prägenden Jahre des Digital Computing lieferte nützliche Programmierwerkzeuge für eine Vielzahl von Anwendungen:

  • FORTRAN (Formula Translation) für ingenieur- und naturwissenschaftliche Anwendungen gilt als erste Hochsprache.
  • COBOL (Common Business-Oriented Language) entwickelte sich aus A-0 und FLOW-MATIC zur dominierenden Hochsprache für Geschäftsanwendungen.
  • LISP (List Processor) für die symbolische Berechnung.

Die Compiler-Technologie hat sich aus der Notwendigkeit einer streng definierten Transformation des High-Level-Quellprogramms in ein Low-Level-Zielprogramm für den digitalen Computer entwickelt. Der Compiler könnte als Front-End betrachtet werden, um die Analyse des Quellcodes zu erledigen, und als Back-End, um die Analyse in den Zielcode zu synthetisieren. Eine Optimierung zwischen Frontend und Backend könnte einen effizienteren Zielcode erzeugen.

Einige frühe Meilensteine ​​in der Entwicklung der Compiler-Technologie:

  • 1952 : Ein Autocode- Compiler, der von Alick Glennie für den Manchester Mark I- Computer an der University of Manchester entwickelt wurde, wird von einigen als die erste kompilierte Programmiersprache angesehen.
  • 1952 : Das Team von Grace Hopper bei Remington Rand schrieb den Compiler für die Programmiersprache A-0 (und prägte den Begriff Compiler , um ihn zu beschreiben), obwohl der A-0-Compiler eher als Loader oder Linker fungierte als der moderne Begriff von a vollständiger Compiler.
  • 1954–1957 : Ein Team unter der Leitung von John Backus bei IBM entwickelt FORTRAN, das normalerweise als die erste Hochsprache gilt. 1957 stellten sie einen FORTRAN-Compiler fertig, von dem allgemein anerkannt wird, dass er den ersten eindeutig vollständigen Compiler eingeführt hat.
  • 1959 : Die Conference on Data Systems Language (CODASYL) leitet die Entwicklung von COBOL ein . Das COBOL-Design basierte auf A-0 und FLOW-MATIC. In den frühen 1960er Jahren wurde COBOL auf mehreren Architekturen kompiliert.
  • 1958–1962 : John McCarthy am MIT entwarf LISP . Die Symbolverarbeitungsfunktionen boten nützliche Funktionen für die Forschung zu künstlicher Intelligenz. Im Jahr 1962 wurden in der Veröffentlichung von LISP 1.5 einige Tools erwähnt: ein von Stephen Russell und Daniel J. Edwards geschriebener Interpreter, ein von Tim Hart und Mike Levin geschriebener Compiler und Assembler.

Frühe Betriebssysteme und Software wurden in Assembler geschrieben. In den 1960er und frühen 1970er Jahren war die Verwendung von Hochsprachen für die Systemprogrammierung aufgrund von Ressourcenbeschränkungen noch umstritten. Mehrere Forschungs- und Industriebemühungen begannen jedoch den Übergang zu höheren Systemprogrammiersprachen, zum Beispiel BCPL , BLISS , B und C .

BCPL (Basic Combined Programming Language) wurde 1966 von Martin Richards an der University of Cambridge entwickelt und wurde ursprünglich als Compiler-Schreibwerkzeug entwickelt. Mehrere Compiler wurden implementiert, Richards' Buch bietet Einblicke in die Sprache und ihren Compiler. BCPL war nicht nur eine einflussreiche Systemprogrammiersprache, die noch in der Forschung verwendet wird, sondern lieferte auch eine Grundlage für das Design von B- und C-Sprachen.

BLISS (Basic Language for Implementation of System Software) wurde vom Forschungsteam der Carnegie Mellon University (CMU) von WA Wulf für einen PDP-10-Computer der Digital Equipment Corporation (DEC) entwickelt. Ein Jahr später, 1970, entwickelte das CMU-Team den BLISS-11-Compiler.

Multics (Multiplexed Information and Computing Service), ein Timesharing-Betriebssystemprojekt, an dem das MIT , Bell Labs , General Electric (später Honeywell ) beteiligt war und von Fernando Corbató vom MIT geleitet wurde. Multics wurde in der PL/I- Sprache geschrieben, die von IBM und der IBM User Group entwickelt wurde. Das Ziel von IBM war es, geschäftliche, wissenschaftliche und Systemprogrammierungsanforderungen zu erfüllen. Es gab andere Sprachen, die in Betracht gezogen worden wären, aber PL/I bot die umfassendste Lösung, obwohl sie nicht implementiert war. In den ersten Jahren des Multics-Projekts konnte eine Teilmenge der Sprache mit dem Early PL/I (EPL)-Compiler von Doug McIlory und Bob Morris von Bell Labs in Assembler kompiliert werden. EPL unterstützte das Projekt, bis ein Bootstrapping-Compiler für das vollständige PL/I entwickelt werden konnte.

Bell Labs verließ das Multics-Projekt 1969: "Im Laufe der Zeit wurde die Hoffnung durch Frustration ersetzt, da die Gruppenanstrengungen zunächst nicht zu einem wirtschaftlich sinnvollen System führten." Eine fortgesetzte Teilnahme würde die Kosten für die Projektunterstützung in die Höhe treiben. Also wandten sich die Forscher anderen Entwicklungsbemühungen zu. Eine auf BCPL-Konzepten basierende Systemprogrammiersprache B wurde von Dennis Ritchie und Ken Thompson geschrieben . Ritchie erstellte einen Boot-Strapping-Compiler für B und schrieb das Betriebssystem Unics (Uniplexed Information and Computing Service) für eine PDP-7 in B. Unics wurde schließlich Unix geschrieben.

Bell Labs begann mit der Entwicklung und Erweiterung von C basierend auf B und BCPL. Der BCPL-Compiler wurde von Bell Labs zu Multics transportiert und BCPL war eine bevorzugte Sprache bei Bell Labs. Anfänglich wurde ein Front-End-Programm für den B-Compiler von Bell Labs verwendet, während ein C-Compiler entwickelt wurde. 1971 stellte eine neue PDP-11 die Ressource bereit, um Erweiterungen für B zu definieren und den Compiler neu zu schreiben. 1973 war das Design der C-Sprache im Wesentlichen abgeschlossen und der Unix-Kernel für eine PDP-11 wurde in C umgeschrieben. Steve Johnson begann mit der Entwicklung des Portable C Compiler (PCC), um die Neuausrichtung von C-Compilern auf neue Maschinen zu unterstützen.

Die objektorientierte Programmierung (OOP) bot einige interessante Möglichkeiten für die Anwendungsentwicklung und -pflege. OOP-Konzepte gehen weiter zurück, waren aber Teil der LISP- und Simula- Sprachwissenschaft. Bei Bell Labs interessierte sich die Entwicklung von C++ für OOP. C++ wurde erstmals 1980 für die Systemprogrammierung verwendet. Das ursprüngliche Design nutzte die Programmierfähigkeiten von C-Sprachsystemen mit Simula-Konzepten. Objektorientierte Einrichtungen wurden 1983 hinzugefügt. Das Cfront-Programm implementierte ein C++-Frontend für den C84-Sprachcompiler. In den folgenden Jahren wurden mehrere C++-Compiler entwickelt, als C++ immer beliebter wurde.

In vielen Anwendungsdomänen hat sich die Idee, eine höhere Sprache zu verwenden, schnell durchgesetzt. Aufgrund der erweiterten Funktionalität, die von neueren Programmiersprachen unterstützt wird, und der zunehmenden Komplexität von Computerarchitekturen wurden Compiler komplexer.

DARPA (Defense Advanced Research Projects Agency) sponserte 1970 ein Compiler-Projekt mit dem CMU-Forschungsteam von Wulf. Das PQCC- Design des Production Quality Compiler-Compilers würde einen Production Quality Compiler (PQC) aus formalen Definitionen der Quellsprache und des Ziels erzeugen. PQCC versuchte ohne großen Erfolg , den Begriff Compiler-Compiler über die traditionelle Bedeutung als Parser-Generator (zB Yacc ) hinaus zu erweitern. PQCC könnte besser als Compiler-Generator bezeichnet werden.

Die PQCC-Forschung zum Codegenerierungsprozess zielte darauf ab, ein wirklich automatisches Compiler-Schreibsystem aufzubauen. Die Bemühungen entdeckten und gestalteten die Phasenstruktur des PQC. Der BLISS-11-Compiler lieferte die anfängliche Struktur. Die Phasen umfassten Analysen (Front-End), Zwischenübersetzung in die virtuelle Maschine (Middle-End) und Übersetzung ins Ziel (Back-End). TCOL wurde für die PQCC-Forschung entwickelt, um sprachspezifische Konstrukte in der Zwischendarstellung zu handhaben. Variationen von TCOL unterstützten verschiedene Sprachen. Das PQCC-Projekt untersuchte Techniken der automatisierten Compilerkonstruktion. Die Entwurfskonzepte erwiesen sich bei der Optimierung von Compilern und Compilern für die objektorientierte Programmiersprache Ada als nützlich .

Das Ada-Stoneman-Dokument formalisierte die Programmunterstützungsumgebung (APSE) zusammen mit dem Kernel (KAPSE) und Minimal (MAPSE). Ein Ada-Interpreter NYU/ED unterstützte die Entwicklungs- und Standardisierungsbemühungen mit dem American National Standards Institute (ANSI) und der International Standards Organization (ISO). Die anfängliche Entwicklung des Ada-Compilers durch die US-Militärdienste umfasste die Compiler in einer vollständig integrierten Designumgebung nach dem Vorbild des Stoneman-Dokuments. Armee und Marine arbeiteten am Ada Language System (ALS)-Projekt, das auf die DEC/VAX-Architektur abzielte, während die Air Force an der Ada Integrated Environment (AIE) für die IBM 370-Serie begann. Obwohl die Projekte nicht die gewünschten Ergebnisse lieferten, trugen sie doch zu den Gesamtanstrengungen bei der Entwicklung von Ada bei.

Andere Bemühungen um einen Ada-Compiler begannen in Großbritannien an der University of York und in Deutschland an der Universität Karlsruhe. In den USA lieferte Verdix (später von Rational übernommen) das Verdix Ada Development System (VADS) an die Armee. VADS stellte eine Reihe von Entwicklungswerkzeugen einschließlich eines Compilers zur Verfügung. Unix/VADS könnte auf einer Vielzahl von Unix-Plattformen wie DEC Ultrix und Sun 3/60 Solaris für Motorola 68020 in einer CECOM-Evaluierung der Armee gehostet werden. Bald standen viele Ada-Compiler zur Verfügung, die die Ada-Validierungstests bestanden haben. Das GNU-Projekt der Free Software Foundation hat die GNU Compiler Collection (GCC) entwickelt, die eine Kernfähigkeit zur Unterstützung mehrerer Sprachen und Ziele bietet. Die Ada-Version GNAT ist einer der am weitesten verbreiteten Ada-Compiler. GNAT ist kostenlos, aber es gibt auch kommerziellen Support, zum Beispiel wurde AdaCore 1994 gegründet, um kommerzielle Softwarelösungen für Ada bereitzustellen. GNAT Pro enthält das auf GNU GCC basierende GNAT mit einer Tool-Suite, um eine integrierte Entwicklungsumgebung bereitzustellen .

Hochsprachen haben die Compiler-Forschung und -Entwicklung weiter vorangetrieben. Schwerpunkte waren Optimierung und automatische Codegenerierung. Trends in Programmiersprachen und Entwicklungsumgebungen beeinflussten die Compilertechnologie. Weitere Compiler wurden in Sprachdistributionen (PERL, Java Development Kit) und als Bestandteil einer IDE (VADS, Eclipse, Ada Pro) aufgenommen. Die Wechselbeziehung und gegenseitige Abhängigkeit von Technologien wuchs. Das Aufkommen von Webdiensten förderte das Wachstum von Websprachen und Skriptsprachen. Skripte gehen auf die Anfänge von Command Line Interfaces (CLI) zurück, wo der Benutzer Befehle eingeben konnte, die vom System ausgeführt werden sollten. Benutzer-Shell-Konzepte, die mit Sprachen entwickelt wurden, um Shell-Programme zu schreiben. Frühe Windows-Designs boten eine einfache Stapelprogrammierungsfunktion. Die konventionelle Transformation dieser Sprache verwendet einen Dolmetscher. Obwohl sie nicht weit verbreitet sind, wurden Bash- und Batch-Compiler geschrieben. In jüngerer Zeit wurden anspruchsvolle interpretierte Sprachen Teil des Entwickler-Toolkits. Moderne Skriptsprachen umfassen PHP, Python, Ruby und Lua. (Lua wird häufig in der Spieleentwicklung verwendet.) Alle haben Interpreter- und Compiler-Unterstützung.

„Als das Compiler-Gebiet Ende der 50er Jahre begann, beschränkte sich sein Fokus auf die Übersetzung von Hochsprachenprogrammen in Maschinencode ... Das Compiler-Gebiet wird zunehmend mit anderen Disziplinen wie Computerarchitektur, Programmiersprachen, formalen Methoden, Softwareentwicklung und Computersicherheit." Der Artikel "Compiler Research: The Next 50 Years" weist auf die Bedeutung von objektorientierten Sprachen und Java hin. Als zukünftige Forschungsziele wurden Sicherheit und Parallel Computing genannt.

Compileraufbau

Ein Compiler implementiert eine formale Transformation von einem High-Level-Quellprogramm zu einem Low-Level-Zielprogramm. Compiler-Design kann eine End-to-End-Lösung definieren oder eine definierte Untermenge angehen, die mit anderen Kompilierungswerkzeugen, zB Präprozessoren, Assemblern, Linkern, verbunden ist. Designanforderungen umfassen streng definierte Schnittstellen sowohl intern zwischen Compilerkomponenten als auch extern zwischen unterstützenden Toolsets.

In der Anfangszeit wurde der Ansatz für das Compiler-Design direkt von der Komplexität der zu verarbeitenden Computersprache, der Erfahrung der Person(en) und den verfügbaren Ressourcen beeinflusst. Ressourcenbeschränkungen führten dazu, dass der Quellcode mehr als einmal durchlaufen werden musste.

Ein Compiler für eine relativ einfache Sprache, die von einer Person geschrieben wurde, kann ein einzelnes, monolithisches Stück Software sein. Mit zunehmender Komplexität der Quellsprache kann das Design jedoch in mehrere voneinander abhängige Phasen aufgeteilt werden. Separate Phasen bieten Designverbesserungen, die die Entwicklung auf die Funktionen im Kompilierungsprozess konzentrieren.

One-Pass- oder Multi-Pass-Compiler

Das Klassifizieren von Compilern nach der Anzahl der Durchläufe hat seinen Hintergrund in den Hardwareressourcenbeschränkungen von Computern. Das Kompilieren erfordert viel Arbeit, und frühe Computer hatten nicht genug Speicher, um ein Programm zu enthalten, das all diese Arbeit erledigte. Daher wurden Compiler in kleinere Programme aufgeteilt, von denen jedes die Quelle (oder eine Darstellung davon) durchging und einige der erforderlichen Analysen und Übersetzungen durchführte.

Die Fähigkeit, in einem einzigen Durchlauf zu kompilieren , wurde klassischerweise als Vorteil angesehen, da sie das Schreiben eines Compilers vereinfacht und Compiler mit einem Durchlauf Kompilierungen im Allgemeinen schneller ausführen als Compiler mit mehreren Durchläufen . Daher wurden, teilweise getrieben durch die Ressourcenbeschränkungen früherer Systeme, viele frühe Sprachen speziell so entworfen, dass sie in einem einzigen Durchlauf kompiliert werden konnten (zB Pascal ).

In einigen Fällen kann es beim Entwurf einer Sprachfunktion erforderlich sein, dass ein Compiler mehr als einen Durchgang über die Quelle durchführt. Betrachten Sie zum Beispiel eine Deklaration in Zeile 20 der Quelle, die die Übersetzung einer Aussage in Zeile 10 beeinflusst. In diesem Fall müssen im ersten Durchgang Informationen über Deklarationen gesammelt werden, die nach Aussagen erscheinen, die sie betreffen, wobei die eigentliche Übersetzung stattfindet bei einem weiteren Durchgang.

Der Nachteil des Kompilierens in einem einzigen Durchlauf besteht darin, dass es nicht möglich ist, viele der ausgeklügelten Optimierungen durchzuführen, die erforderlich sind, um qualitativ hochwertigen Code zu generieren. Es kann schwierig sein, genau zu zählen, wie viele Durchläufe ein optimierender Compiler macht. Beispielsweise können verschiedene Optimierungsphasen einen Ausdruck viele Male analysieren, einen anderen Ausdruck jedoch nur einmal analysieren.

Das Aufteilen eines Compilers in kleine Programme ist eine Technik, die von Forschern verwendet wird, die daran interessiert sind, nachweislich korrekte Compiler zu erstellen. Der Nachweis der Korrektheit einer Reihe kleiner Programme erfordert oft weniger Aufwand als der Nachweis der Korrektheit eines größeren, einzelnen gleichwertigen Programms.

Dreistufige Compilerstruktur

Compiler-Design

Unabhängig von der genauen Anzahl der Phasen im Compiler-Design können die Phasen einer von drei Stufen zugeordnet werden. Die Stufen umfassen ein Front-End, ein Middle-End und ein Back-End.

  • Das Frontend scannt die Eingabe und überprüft Syntax und Semantik gemäß einer bestimmten Quellsprache. Für statisch typisierte Sprachen führt es eine Typprüfung durch , indem es Typinformationen sammelt. Wenn das Eingabeprogramm syntaktisch inkorrekt ist oder einen Typfehler aufweist, generiert es Fehler- und/oder Warnmeldungen, die normalerweise die Stelle im Quellcode angeben, an der das Problem erkannt wurde; in einigen Fällen kann der eigentliche Fehler (viel) früher im Programm liegen. Aspekte des Frontends umfassen lexikalische Analyse, Syntaxanalyse und semantische Analyse. Das Frontend wandelt das Eingabeprogramm in eine Zwischenrepräsentation (IR) für die weitere Verarbeitung durch das Middleend um. Diese IR ist normalerweise eine untergeordnete Darstellung des Programms in Bezug auf den Quellcode.
  • Das mittlere Ende führt Optimierungen an der IR durch, die unabhängig von der angestrebten CPU-Architektur sind. Diese Unabhängigkeit von Quellcode/Maschinencode soll ermöglichen, dass generische Optimierungen zwischen Versionen des Compilers geteilt werden, die verschiedene Sprachen und Zielprozessoren unterstützen. Beispiele für Middle-End-Optimierungen sind das Entfernen von nutzlosem ( Totcode-Eliminierung ) oder unerreichbarem Code ( Erreichbarkeitsanalyse ), Entdeckung und Weitergabe von konstanten Werten ( konstante Ausbreitung ), Verlagerung der Berechnung an einen weniger häufig ausgeführten Ort (z. B. außerhalb einer Schleife) oder Spezialisierung der Berechnung basierend auf dem Kontext. Schließlich wird die "optimierte" IR erzeugt, die vom Back-End verwendet wird.
  • Das Backend übernimmt die optimierte IR vom mittleren Ende. Es kann weitere Analysen, Transformationen und Optimierungen durchführen, die spezifisch für die Ziel-CPU-Architektur sind. Das Backend generiert den zielabhängigen Assemblercode und führt dabei die Registerzuordnung durch. Das Back-End führt eine Befehlsplanung durch , die Befehle neu anordnet, um parallele Ausführungseinheiten zu beschäftigen, indem Verzögerungsschlitze gefüllt werden . Obwohl die meisten Optimierungsprobleme NP-schwer sind , sind heuristische Techniken zu ihrer Lösung gut entwickelt und derzeit in Compilern in Produktionsqualität implementiert. Typischerweise ist die Ausgabe eines Back-Ends Maschinencode, der auf einen bestimmten Prozessor und ein bestimmtes Betriebssystem spezialisiert ist.

Dieser Front/Middle/Back-End-Ansatz ermöglicht es, Frontends für verschiedene Sprachen mit Backends für verschiedene CPUs zu kombinieren und gleichzeitig die Optimierungen des Middle-Ends zu teilen. Praktische Beispiele für diesen Ansatz sind die GNU Compiler Collection , Clang ( LLVM- basierter C/C++-Compiler) und das Amsterdam Compiler Kit , die über mehrere Frontends, gemeinsame Optimierungen und mehrere Backends verfügen.

Vorderes Ende

Lexer- und Parser- Beispiel für C . Ausgehend von der Zeichenfolge " if(net>0.0)total+=net*(1.0+tax/100.0);" stellt der Scanner eine Folge von Token zusammen und kategorisiert diese jeweils zB als Bezeichner , reserviertes Wort , Zahlenliteral oder Operator . Letztere Sequenz wird vom Parser in einen Syntaxbaum transformiert , der dann von den restlichen Compiler-Phasen behandelt wird. Der Scanner und Parser handhabt die regulären bzw. richtig kontextfreien Teile der Grammatik für C .

Das Frontend analysiert den Quellcode, um eine interne Darstellung des Programms zu erstellen, die als Zwischendarstellung (IR) bezeichnet wird. Es verwaltet auch die Symboltabelle , eine Datenstruktur, die jedes Symbol im Quellcode auf zugehörige Informationen wie Ort, Typ und Umfang abbildet.

Während das Frontend eine einzelne monolithische Funktion oder ein einzelnes Programm sein kann, wie bei einem scannerlosen Parser , wurde es traditionell als mehrere Phasen implementiert und analysiert, die sequentiell oder gleichzeitig ausgeführt werden können. Diese Methode wird aufgrund ihrer Modularität und Trennung der Belange bevorzugt . Am häufigsten wird das Frontend heute in drei Phasen unterteilt: lexikalische Analyse (auch als Lexing oder Scanning bekannt), Syntaxanalyse (auch als Scanning oder Parsing bekannt) und semantische Analyse . Lexing und Parsen umfassen die syntaktische Analyse (Wortsyntax bzw. Phrasensyntax), und in einfachen Fällen können diese Module (der Lexer und der Parser) automatisch aus einer Grammatik für die Sprache generiert werden, obwohl diese in komplexeren Fällen eine manuelle Änderung erfordern . Die lexikalische Grammatik und die Phrasengrammatik sind normalerweise kontextfreie Grammatiken , was die Analyse erheblich vereinfacht, wobei die Kontextsensitivität in der semantischen Analysephase behandelt wird. Die semantische Analysephase ist in der Regel komplexer und von Hand geschrieben, kann aber mithilfe von Attributgrammatiken teilweise oder vollständig automatisiert werden . Diese Phasen selbst lassen sich weiter untergliedern: Lexing als Scannen und Auswerten und Parsing als Aufbau eines konkreten Syntaxbaums (CST, Parse-Baum) und dann dessen Transformation in einen abstrakten Syntaxbaum (AST, Syntaxbaum). In einigen Fällen werden zusätzliche Phasen verwendet, insbesondere die Linienrekonstruktion und die Vorverarbeitung, aber diese sind selten.

Die Hauptphasen des Frontends umfassen die folgenden:

  • Die Zeilenrekonstruktion wandelt die eingegebene Zeichenfolge in eine kanonische Form um, die für den Parser bereit ist. Sprachen, dieihre Schlüsselwörterstreichenoder beliebige Leerzeichen innerhalb von Bezeichnern zulassen, benötigen diese Phase. Dietop-down,rekursiven Abstieg, tabellengesteuerte Parser in den 1960er Jahren verwendeten typischerweise die Quelle eines Zeichen in einer Zeit gelesen und haben keine separate Tokenisieren Phase erfordern. Atlas AutocodeundImp(und einige Implementierungen vonAlgolundCoral 66) sind Beispiele für stropped Sprachenderen Compiler würde eine habenLinie WiederaufbauPhase.
  • Die Vorverarbeitung unterstützt die Makroersetzung und die bedingte Kompilierung . Typischerweise erfolgt die Vorverarbeitungsphase vor der syntaktischen oder semantischen Analyse; zB im Fall von C manipuliert der Präprozessor eher lexikalische Token als syntaktische Formen. Einige Sprachen wie Scheme unterstützen jedoch Makrosubstitutionen basierend auf syntaktischen Formen.
  • Die lexikalische Analyse (auch als Lexing oder Tokenisierung bekannt ) zerlegt den Quellcodetext in eine Folge kleiner Teile, die als lexikalische Token bezeichnet werden . Diese Phase kann in zwei Phasen unterteilt werden: das Scannen , das den eingegebenen Text in syntaktische Einheiten, die Lexeme genannt werden , segmentiertund ihnen eine Kategorie zuweist; und das Auswerten , das Lexeme in einen verarbeiteten Wert umwandelt. Ein Token ist ein Paar, das aus einem Tokennamen und einem optionalen Tokenwert besteht . Gängige Token-Kategorien können Bezeichner, Schlüsselwörter, Trennzeichen, Operatoren, Literale und Kommentare umfassen, obwohl der Satz von Token-Kategorien in verschiedenen Programmiersprachen variiert. Die Lexemsyntax ist normalerweise eine reguläre Sprache , sodass einaus einem regulären Ausdruck konstruierter endlicher Automat verwendet werdenkann, um sie zu erkennen. Die Software, die eine lexikalische Analyse durchführt, wird als lexikalischer Analysator bezeichnet . Dies ist möglicherweise kein separater Schritt – er kann mit dem Parsing-Schritt beim scannerlosen Parsing kombiniert werden, in diesem Fall wird das Parsing auf Zeichenebene und nicht auf Token-Ebene durchgeführt.
  • Bei der Syntaxanalyse (auch als Parsing bezeichnet ) wird die Tokensequenz analysiert , um die syntaktische Struktur des Programms zu identifizieren. Diese Phase erstellt typischerweise einen Parse-Baum , der die lineare Sequenz von Token durch eine Baumstruktur ersetzt, die gemäß den Regeln einer formalen Grammatik aufgebaut ist , die die Syntax der Sprache definieren. Der Parse-Baum wird oft durch spätere Phasen im Compiler analysiert, erweitert und transformiert.
  • Semantische Analyse fügt semantische Informationen an den Parse - Baum und baut die Symboltabelle . In dieser Phase werden semantische Prüfungen wie Typprüfung (Prüfen auf Typfehler) oder Objektbindung (Verknüpfen von Variablen- und Funktionsreferenzen mit ihren Definitionen) oder definitive Zuweisung (erfordert, dass alle lokalen Variablen vor der Verwendung initialisiert werden müssen), das Zurückweisen falscher Programme oder das Ausgeben von Warnungen. Semantische Analyse erfordertRegel einen kompletten ParseBaum, was bedeutetedass diese Phase logisch die folgenden Parsing - Phase und geht logischerweise die Code - Generierung Phase, obwohl es oft möglich istmehrere Phasen in einen Durchgang über den Code in einer Compiler Implementierung zu falten.

Mittleres Ende

Das mittlere Ende, auch Optimierer genannt, führt Optimierungen an der Zwischendarstellung durch, um die Leistung und die Qualität des erzeugten Maschinencodes zu verbessern. Das mittlere Ende enthält die Optimierungen, die unabhängig von der angestrebten CPU-Architektur sind.

Die Hauptphasen des mittleren Endes umfassen die folgenden:

Die Compileranalyse ist die Voraussetzung für jede Compileroptimierung und sie arbeiten eng zusammen. Beispielsweise ist die Abhängigkeitsanalyse für die Schleifentransformation von entscheidender Bedeutung .

Der Umfang der Compileranalyse und -optimierungen variiert stark; ihr Umfang kann von der Arbeit innerhalb eines Basisblocks bis hin zu ganzen Prozeduren oder sogar dem gesamten Programm reichen . Es gibt einen Kompromiss zwischen der Granularität der Optimierungen und den Kosten der Kompilierung. Beispielsweise sind Guckloch-Optimierungen während der Kompilierung schnell durchzuführen, betreffen jedoch nur ein kleines lokales Fragment des Codes und können unabhängig von dem Kontext durchgeführt werden, in dem das Codefragment erscheint. Im Gegensatz dazu benötigt die interprozedurale Optimierung mehr Kompilierzeit und Speicherplatz, ermöglicht aber Optimierungen, die nur durch die Berücksichtigung des Verhaltens mehrerer Funktionen gleichzeitig möglich sind.

Interprozedurale Analysen und Optimierungen sind in modernen kommerziellen Compilern von HP , IBM , SGI , Intel , Microsoft und Sun Microsystems üblich . Der freien Software GCC wurde lange Zeit das Fehlen leistungsfähiger interprozeduraler Optimierungen vorgeworfen, doch in dieser Hinsicht ändert sie sich. Ein weiterer Open-Source-Compiler mit vollständiger Analyse- und Optimierungsinfrastruktur ist Open64 , der von vielen Organisationen für Forschungs- und kommerzielle Zwecke verwendet wird.

Aufgrund des zusätzlichen Zeit- und Platzbedarfs für Compileranalysen und -optimierungen überspringen einige Compiler diese standardmäßig. Benutzer müssen Kompilierungsoptionen verwenden, um dem Compiler explizit mitzuteilen, welche Optimierungen aktiviert werden sollen.

Back-End

Das Backend ist für die CPU-Architektur spezifischen Optimierungen und für die Codegenerierung zuständig .

Die Hauptphasen des Backends umfassen die folgenden:

  • Maschinenabhängige Optimierungen : Optimierungen, die von den Details der CPU-Architektur abhängen, auf die der Compiler abzielt. Ein prominentes Beispiel sind Guckloch-Optimierungen , die kurze Sequenzen von Assembler-Befehlen in effizientere Befehle umschreiben.
  • Codegenerierung : Die transformierte Zwischensprache wird in die Ausgabesprache übersetzt, normalerweise die native Maschinensprache des Systems. Dies beinhaltet Ressourcen- und Speicherentscheidungen, wie z. B. die Entscheidung, welche Variablen in Register und Speicherpassen,und die Auswahl und Planung geeigneter Maschinenbefehle zusammen mit ihren zugehörigen Adressierungsmodi (siehe auch Sethi-Ullman-Algorithmus ). Debug-Daten müssen möglicherweise auch generiert werden, um das Debuggen zu erleichtern.

Compiler-Korrektheit

Compiler Correctness ist der Zweig der Softwaretechnik, der sich damit beschäftigt, zu zeigen, dass sich ein Compiler gemäß seiner Sprachspezifikation verhält . Zu den Techniken gehören die Entwicklung des Compilers unter Verwendung formaler Methoden und die Verwendung strenger Tests (oft als Compilervalidierung bezeichnet) an einem vorhandenen Compiler.

Kompilierte versus interpretierte Sprachen

Höhere Programmiersprachen erscheinen normalerweise mit Blick auf eine Art der Übersetzung : entweder als kompilierte Sprache oder als interpretierte Sprache konzipiert . In der Praxis gibt es jedoch selten etwas an einer Sprache, das eine ausschließliche Kompilierung oder ausschließliche Interpretation erfordert , obwohl es möglich ist, Sprachen zu entwerfen, die zur Laufzeit auf Neuinterpretation angewiesen sind. Die Kategorisierung spiegelt normalerweise die beliebtesten oder am weitesten verbreiteten Implementierungen einer Sprache wider – zum Beispiel wird BASIC manchmal als interpretierte Sprache und C als kompilierte Sprache bezeichnet, obwohl es BASIC-Compiler und C-Interpreter gibt.

Die Interpretation ersetzt die Kompilierung nicht vollständig. Es verbirgt es nur vor dem Benutzer und macht es schrittweise. Auch wenn ein Interpreter selbst interpretiert werden kann, wird irgendwo unten im Ausführungsstapel ein direkt ausgeführtes Programm benötigt (siehe Maschinensprache ).

Darüber hinaus können Compiler zur Optimierung Interpreterfunktionalität enthalten, und Interpreter können Vorabkompilierungstechniken enthalten. Wenn beispielsweise ein Ausdruck während der Kompilierung ausgeführt und die Ergebnisse in das Ausgabeprogramm eingefügt werden können, dann wird verhindert, dass er bei jedem Programmlauf neu berechnet werden muss, was das endgültige Programm erheblich beschleunigen kann. Moderne Trends zur Just-in-Time-Kompilierung und Bytecode-Interpretation verwischen manchmal die traditionellen Kategorisierungen von Compilern und Interpretern noch weiter.

Einige Sprachspezifikationen buchstabieren , dass Implementierungen müssen eine Kompilation Einrichtung umfassen; zum Beispiel Common Lisp . Die Definition von Common Lisp enthält jedoch nichts, was ihre Interpretation verhindert. Andere Sprachen haben Funktionen, die in einem Interpreter sehr einfach zu implementieren sind, aber das Schreiben eines Compilers viel schwieriger machen; zum Beispiel, APL , SNOBOL4 und viele Skriptsprachen erlauben Programme beliebige Quellcode zur Laufzeit mit regulären String - Operationen zu konstruieren, und dann diesen Code ausführen , indem sie auf eine spezielle vorbeie Bewertungsfunktion . Um diese Funktionen in einer kompilierten Sprache zu implementieren, müssen Programme normalerweise mit einer Laufzeitbibliothek geliefert werden , die eine Version des Compilers selbst enthält.

Typen

Eine Klassifizierung von Compilern erfolgt nach der Plattform, auf der ihr generierter Code ausgeführt wird. Dies wird als Zielplattform bezeichnet.

Ein nativer oder gehosteter Compiler ist ein Compiler, dessen Ausgabe direkt auf demselben Computer- und Betriebssystemtyp ausgeführt werden soll, auf dem der Compiler selbst ausgeführt wird. Die Ausgabe eines Cross-Compilers ist für die Ausführung auf einer anderen Plattform ausgelegt. Cross-Compiler werden häufig bei der Entwicklung von Software für eingebettete Systeme verwendet , die keine Softwareentwicklungsumgebung unterstützen sollen.

Die Ausgabe eines Compilers, der Code für eine virtuelle Maschine (VM) erzeugt, kann auf derselben Plattform wie der Compiler, der sie erstellt hat, ausgeführt werden oder nicht. Aus diesem Grund werden solche Compiler normalerweise nicht als native oder Cross-Compiler klassifiziert.

Die untergeordnete Sprache, die das Ziel eines Compilers ist, kann selbst eine höhere Programmiersprache sein . C, von manchen als eine Art portable Assemblersprache angesehen, ist häufig die Zielsprache solcher Compiler. Zum Beispiel Cfront , die Original - Compiler für C ++ , verwenden C als Zielsprache. Der von einem solchen Compiler generierte C-Code ist normalerweise nicht dafür gedacht, von Menschen gelesen und gewartet werden zu können, daher werden Einrückungsstile und das Erstellen von hübschem C-Zwischencode ignoriert. Zu den Merkmalen von C, die es zu einer guten Zielsprache machen, gehören die #lineDirektive, die vom Compiler generiert werden kann, um das Debuggen der Originalquelle zu unterstützen , und die breite Plattformunterstützung, die mit C-Compilern verfügbar ist.

Während ein gängiger Compilertyp Maschinencode ausgibt, gibt es viele andere Typen:

  • Source-to-Source-Compiler sind ein Compilertyp, der eine Hochsprache als Eingabe verwendet und eine Hochsprache ausgibt. Beispielsweise nimmt ein automatischer parallelisierender Compiler häufig ein Hochsprachenprogramm als Eingabe auf und transformiert dann den Code und kommentiert ihn mit parallelen Codeannotationen (zB OpenMP ) oder Sprachkonstrukten (zB Fortrans DOALLAnweisungen). Andere Begriffe für Source-to-Source-Compiler sind Sprachübersetzer, Sprachkonverter oder Sprachumschreiber . Der letzte Begriff wird normalerweise für Übersetzungen verwendet, die keinen Sprachwechsel beinhalten.
  • Bytecode- Compiler kompilieren in die Assemblersprache einer theoretischen Maschine, wie einige Prolog- Implementierungen
  • Just-in-Time-Compiler (JIT-Compiler) verschieben die Kompilierung bis zur Laufzeit. JIT - Compiler gibt es für viele moderne Sprachen , darunter Python , JavaScript , Smalltalk , Java , Microsoft .NET ‚s Common Intermediate Language (CIL) und andere. Ein JIT-Compiler läuft im Allgemeinen innerhalb eines Interpreters. Wenn der Interpreter erkennt, dass ein Codepfad "heiß" ist, was bedeutet, dass er häufig ausgeführt wird, wird der JIT-Compiler aufgerufen und kompiliert den "heißen" Code, um die Leistung zu erhöhen.
    • Für einige Sprachen wie Java werden Anwendungen zunächst mit einem Bytecode-Compiler kompiliert und in einer maschinenunabhängigen Zwischendarstellung ausgeliefert . Ein Bytecode-Interpreter führt den Bytecode aus, aber der JIT-Compiler übersetzt den Bytecode in Maschinencode, wenn eine höhere Leistung erforderlich ist.
  • Hardware-Compiler (auch als Synthese-Tools bekannt) sind Compiler, deren Eingabe eine Hardware-Beschreibungssprache ist und deren Ausgabe eine Beschreibung einer Hardware-Konfiguration in Form einer Netzliste oder anderweitig ist.
    • Die Ausgabe dieser Compiler zielt auf sehr niedrigem Niveau auf Computerhardware ab , beispielsweise ein feldprogrammierbares Gate-Array (FPGA) oder eine strukturierte anwendungsspezifische integrierte Schaltung (ASIC). Solche Compiler werden als Hardware-Compiler bezeichnet, da der Quellcode, den sie kompilieren, effektiv die endgültige Konfiguration der Hardware und ihre Funktionsweise steuert. Die Ausgabe der Zusammenstellung ist nur eine Verschaltung von Transistoren oder Lookup-Tabellen .
    • Ein Beispiel für einen Hardware-Compiler ist XST, das Xilinx-Synthese-Tool zum Konfigurieren von FPGAs. Ähnliche Tools sind von Altera, Synplicity, Synopsys und anderen Hardwareanbietern erhältlich.
  • Ein Assembler ist ein Programm, das von Menschen lesbare Assemblersprache in Maschinencode kompiliert , die eigentlichen Anweisungen, die von der Hardware ausgeführt werden. Das inverse Programm, das Maschinencode in Assembler übersetzt, wird Disassembler genannt .
  • Ein Programm, das von einer niedrigeren Sprache in eine höhere Sprache übersetzt, ist ein Decompiler .
  • Ein Programm, das in ein Objektcodeformat übersetzt, das von der Kompilierungsmaschine nicht unterstützt wird, wird Cross-Compiler genannt und wird üblicherweise verwendet, um Code für eingebettete Anwendungen vorzubereiten.
  • Ein Programm, das Objektcode zurück in denselben Typ von Objektcode umschreibt, während es Optimierungen und Transformationen anwendet, ist ein binärer Recompiler .

Siehe auch

Verweise

Weiterlesen

Externe Links