Compiler

Historisches Beispiel anhand von CBASIC

Ein Compiler (auch Übersetzer oder Kompilierer genannt) ist ein Computerprogramm, das ein in einer Quellsprache geschriebenes Programm (Quelltext/Quellprogramm, meist von einem Programmierer in einer Programmiersprache geschriebenen) in ein semantisch äquivalentes Programm einer Zielsprache umwandelt. Diese ist meist Assemblersprache, Bytecode oder Maschinensprache. Das Übersetzen wird auch als Kompilierung bezeichnet. Zur Steuerung des Übersetzens kann der Quelltext neben den Anweisungen der Programmiersprache zusätzliche spezielle Compiler-Anweisungen enthalten.

Die Bezeichnung Compiler geht zurück auf englisch compile „zusammentragen“ und lateinisch compilare „ausbeuten“. Compiler sollen die im Quelltext enthaltenen Informationen zusammentragen, um selbständig möglichst effizienten Programmcode zu erzeugen.

Heute unterscheidet man traditionelle Ahead-of-time-Compiler und Just-in-time-Compiler, die erst bei Programmstart aktiv werden, und somit Gemeinsamkeiten mit Interpretern haben. Vorläufer der Compiler sind Assembler; sie verlangen jedoch Kenntnisse des Benutzers über Details der Rechnerarchitektur. Ein Interpreter übersetzt ein Programm nicht in die Zielsprache, sondern führt es Schritt für Schritt direkt aus.

Früher bezeichnete das Wort Compiler auch Programme, die Unterprogramme zusammenfügen (etwa mit heutigen Linkern vergleichbar).^[1] Dies geht an der heutigen Kernaufgabe eines Compilers vorbei.

Aufbau eines Compilers

Der Compilerbau, also die Programmierung eines Compilers, ist eine eigenständige Disziplin innerhalb der Informatik.

Moderne Compiler werden in verschiedene Phasen gegliedert, die jeweils verschiedene Teilaufgaben des Compilers übernehmen. Einige dieser Phasen können als eigenständige Programme realisiert werden (s. Precompiler, Präprozessor). Sie werden sequentiell ausgeführt. Im Wesentlichen lassen sich zwei Phasen unterscheiden: das Frontend (auch Analysephase), das den Quelltext analysiert und daraus einen attributierten Syntaxbaum erzeugt, sowie das Backend (auch Synthesephase), das daraus das Zielprogramm erzeugt.

Frontend (auch „Analysephase“)

Im Frontend wird der Code analysiert, strukturiert und auf Fehler geprüft. Es ist auch selbst wieder in Phasen gegliedert:

Lexikalische Analyse

Die lexikalische Analyse zerteilt den eingelesenen Quelltext in zusammengehörende Token verschiedener Klassen, zum Beispiel Schlüsselwörter, Bezeichner, Zahlen und Operatoren. Dieser Teil des Compilers heißt Scanner oder Lexer.

Ein Scanner benutzt gelegentlich einen separaten Screener, um Whitespace (Leerraum, also Leerzeichen, Tabulatorzeichen, Zeilenenden, usw.) und Kommentare zu überspringen.

Syntaktische Analyse

Die syntaktische Analyse überprüft, ob der eingelesene Quellcode ein korrektes Programm der zu übersetzenden Quellsprache ist, das heißt der Syntax (Grammatik) der Quellsprache entspricht. Dabei wird die Eingabe in einen Syntaxbaum umgewandelt. Der syntaktische Analysierer wird auch als Parser bezeichnet. Falls der Quellcode nicht zur Grammatik der Quellsprache passt, gibt der Parser einen Syntaxfehler aus.

Semantische Analyse

Die semantische Analyse überprüft die statische Semantik, also über die syntaktische Analyse hinausgehende Bedingungen an das Programm. Zum Beispiel muss eine Variable in der Regel deklariert worden sein, bevor sie verwendet wird, und Zuweisungen müssen mit kompatiblen (verträglichen) Datentypen erfolgen. Dies kann mit Hilfe von Attributgrammatiken realisiert werden. Dabei werden die Knoten des vom Parser generierten Syntaxbaums mit Attributen versehen, die Informationen enthalten. So kann zum Beispiel eine Liste aller deklarierten Variablen erstellt werden. Die Ausgabe der semantischen Analyse nennt man dann dekorierten oder attributierten Syntaxbaum.

Backend (auch „Synthesephase“)

Das Backend erzeugt aus dem vom Frontend erstellten attributierten Syntaxbaum den Programmcode der Zielsprache.

Zwischencodeerzeugung

Viele moderne Compiler erzeugen aus dem Syntaxbaum einen Zwischencode, der schon relativ maschinennah sein kann und führen auf diesem Zwischencode zum Beispiel Programmoptimierungen durch. Das bietet sich besonders bei Compilern an, die mehrere Quellsprachen oder verschiedene Zielplattformen unterstützen. Hier kann der Zwischencode auch ein Austauschformat sein.

Programmoptimierung

Der Zwischencode ist Basis vieler Programmoptimierungen. Siehe Programmoptimierung.

Codegenerierung

Bei der Codegenerierung wird der Programmcode der Zielsprache entweder direkt aus dem Syntaxbaum oder aus dem Zwischencode erzeugt. Falls die Zielsprache eine Maschinensprache ist, kann das Ergebnis direkt ein ausführbares Programm sein oder eine sogenannte Objektdatei, die durch das Linken mit der Laufzeitbibliothek und evtl. weiteren Objektdateien zu einer Bibliothek oder einem ausführbaren Programm führt.

Einordnung verschiedener Compiler-Arten

• Native Compiler

Compiler, der Programmcode für die Plattform erzeugt, auf der er selbst läuft.

• Cross-Compiler

Compiler, der auf einer Plattform ausgeführt wird und Programmcode für eine andere Plattform, zum Beispiel ein anderes Betriebssystem oder eine andere Prozessorarchitektur, erzeugt.

Eine typische Anwendung ist die Erstellung von Programmen für ein eingebettetes System, das selbst keine oder keine guten Werkzeuge zur Softwareerstellung enthält, sowie die Erstellung oder Portierung eines Betriebssystems auf einer neuen Plattform.

• Single-pass-Compiler

Compiler, der in einem einzigen Durchlauf aus dem Quellcode den Zielcode erzeugt (im Gegensatz zum Multi-pass-Compiler). Üblicherweise ist ein derartiger Compiler sehr schnell, aber kann nur einfache Optimierungen durchführen. Nur für bestimmte Programmiersprachen, zum Beispiel Pascal, kann ein Single-Pass-Compiler erstellt werden.

• Multi-pass-Compiler

Bei diesem Compilertyp wird der Quellcode in mehreren Schritten in den Zielcode übersetzt. In den Anfangszeiten des Compilerbaus wurde der Übersetzungsprozess hauptsächlich deshalb in mehrere Durchläufe zerlegt, weil die Kapazität der Computer oft nicht ausreichte, um den vollständigen Compiler und das zu übersetzende Programm gleichzeitig im Hauptspeicher zu halten. Heutzutage dient ein Multi-pass-Compiler vor allem dazu, Vorwärtsreferenzen (Deklaration eines Bezeichners nach dessen erster Verwendung) aufzulösen und aufwändige Optimierungen durchzuführen.

Sonderformen

• Bei einem Transcompiler (auch als Transpiler bezeichnet) handelt es sich um einen speziellen Compiler, der Quellcode von einer Programmiersprache in den Quellcode einer anderen Programmiersprache übersetzt, zum Beispiel von Pascal in C.^[2]
  Da jedoch viele Programmiersprachen besondere Eigenschaften und Leistungsmerkmale besitzen, kann es, wenn diese nicht vom Transcompilern berücksichtigt werden, zu Effizienzverlusten kommen. Da Programmiersprachen meist unterschiedlichen Programmierparadigmen folgen, ist der neu generierte Quelltext oft nur schwer für Entwickler lesbar. Manchmal ist auch eine manuelle Nachbearbeitung des Codes nötig, da die automatische Übersetzung nicht in allen Fällen zu hundert Prozent funktioniert.
• Compiler-Compiler und Compilergeneratoren sind Hilfsprogramme zur automatischen Generierung von Compilerteilen oder vollständigen Compilern. Siehe auch: ANTLR, Coco/R, JavaCC, Lex, Yacc
• Just-in-time-Compiler (oder JIT-Compiler) übersetzen Quellcode oder Bytecode erst bei der Ausführung des Programms in Maschinencode. Dabei werden meist nur die benötigten Programmteile übersetzt und von der Maschine nativ ausgeführt.
• Beim Compreter wird der Programm-Quellcode zunächst in einen Zwischencode übersetzt, der dann zur Laufzeit interpretiert wird. Compreter sollten die Vorteile des Compilers mit den Vorteilen des Interpreters verbinden. Effektiv sind viele heutige Interpreter zur Verringerung der Ausführungszeit intern als Compreter implementiert, die den Quellcode zur Laufzeit übersetzen, bevor das Programm ausgeführt wird.

Geschichte

Grace Hopper (1984)

Der erste Compiler (A-0) wurde 1952 von der Mathematikerin Grace Hopper entwickelt. Programmierer reihten ausschließlich Nullen und Einsen aneinander, bis Grace Hopper den Compiler erfand und damit Symbolik der Mathematik sowie natürliche Sprache für die Programmierung erschloss.^[3] Am 3. Mai 1952 stellte Hopper erstmals öffentlich den ersten Compiler A-0 vor, der Algorithmen aus einem Katalog abrief, Code umschrieb, in passender Reihenfolge zusammenstellte, Speicherplatz reservierte und die Zuteilung von Speicheradressen organisierte.^[4] Anfang 1955 präsentierte Hopper bereits einen Prototyp des Compilers B-0, der nach englischen, französischen oder deutschen Anweisungen Programme erzeugte.^[5] Hopper nannte ihren Vortrag zum ersten Compiler „The Education of a Computer“ („Die Ausbildung eines Computers“).

Die Geschichte des Compilerbaus wurde von den jeweils aktuellen Programmiersprachen (vgl. Zeittafel der Programmiersprachen) und Hardwarearchitekturen geprägt. Weitere frühe Meilensteine sind 1957 der erste FORTRAN-Compiler und 1960 der erste COBOL-Compiler. Viele Architekturmerkmale heutiger Compiler wurden aber erst in den 1960er Jahren entwickelt.

Programmoptimierung (ausführlich)

Zur Steuerung des Übersetzens kann der Quelltext neben den Anweisungen der Programmiersprache zusätzliche spezielle Compiler-Anweisungen enthalten.

Üblicherweise bietet ein Compiler Optionen für verschiedene Optimierungen mit dem Ziel, die Laufzeit des Zielprogramms zu verbessern oder dessen Speicherplatzbedarf zu minimieren. Die Optimierungen erfolgen teilweise in Abhängigkeit von den Eigenschaften der Hardware, zum Beispiel wie viele und welche Register der Prozessor des Computers zur Verfügung stellt. Optimierungen optimieren oft nur bestimmte Aspekte eines Programms. Es ist möglich, dass ein Programm nach einer Optimierung langsamer ausgeführt wird, als das ohne sie der Fall gewesen wäre. Dies kann zum Beispiel eintreten, wenn eine Optimierung für ein Programmkonstrukt längeren Code erzeugt, der zwar an sich schneller ausgeführt werden würde, aber mehr Zeit benötigt, um erst einmal in den Cache geladen zu werden. Er ist damit erst bei häufigerer Benutzung vorteilhaft.

Einige Optimierungen führen dazu, dass der Compiler Zielsprachenkonstrukte erzeugt, für die es gar keine direkten Entsprechungen in der Quellsprache gibt. Ein Nachteil solcher Optimierungen ist, dass es dann kaum noch möglich ist, den Programmablauf mit einem interaktiven Debugger in der Quellsprache zu verfolgen.

Optimierungen können sehr aufwendig sein. Vielfach muss v. a. in modernen JIT-Compilern daher abgewogen werden, ob es sich lohnt, einen Programmteil zu optimieren. Bei Ahead-of-time-Compilern werden bei der abschließenden Übersetzung alle sinnvollen Optimierungen verwendet, häufig jedoch nicht während der Software-Entwicklung (reduziert den Kompilier-Zeitbedarf). Für nicht-automatische Optimierungen seitens des Programmierers können Tests und Anwendungsszenarien durchgespielt werden (s. Profiler), um herauszufinden, wo sich komplexe Optimierungen lohnen.

Im folgenden werden einige Optimierungsmöglichkeiten eines Compilers betrachtet. Das größte Optimierungspotenzial besteht allerdings oft in der Veränderung des Quellprogramms selbst, zum Beispiel darin, einen Algorithmus durch einen effizienteren zu ersetzen. Dieser Vorgang kann meistens nicht automatisiert werden, sondern muss durch den Programmierer erfolgen. Einfachere Optimierungen können dagegen an den Compiler delegiert werden, um den Quelltext lesbarer zu halten.

Einsparung von Maschinenbefehlen

In vielen höheren Programmiersprachen benötigt man beispielsweise eine Hilfsvariable, um den Inhalt zweier Variablen zu vertauschen:

Einsparung von Maschinenbefehlen (MB)

Höhere Programmiersprache	Maschinenbefehle
	ohne Optimierung	mit Optimierung
hilf = a	a → Register 1 Register 1 → hilf	a → Register 1
a = b	b → Register 1 Register 1 → a	b → Register 2 Register 2 → a
b = hilf	hilf → Register 1 Register 1 → b	Register 1 → b

Mit der Optimierung werden statt 6 nur noch 4 Assemblerbefehle benötigt, außerdem wird der Speicherplatz für die Hilfsvariable hilf nicht gebraucht. D. h. diese Vertauschung wird schneller ausgeführt und benötigt weniger Hauptspeicher. Dies gilt jedoch nur, wenn ausreichend Register im Prozessor zur Verfügung stehen. Die Speicherung von Daten in Registern statt im Hauptspeicher ist eine häufig angewendete Möglichkeit der Optimierung.

Die oben als optimiert gezeigte Befehlsfolge hat noch eine weitere Eigenschaft, die bei modernen CPUs mit mehreren Verarbeitungs-Pipelines einen Vorteil bedeuten kann: Die beiden Lesebefehle und die beiden Schreibbefehle können problemlos parallel verarbeitet werden, sie sind nicht vom Resultat der jeweils anderen abhängig. Lediglich der erste Schreibbefehl muss auf jeden Fall abwarten, bis der letzte Lesebefehl ausgeführt wurde. Tiefer gehende Optimierungsverfahren fügen deshalb unter Umständen zwischen b → Register 2 und Register 2 → a noch Maschinenbefehle ein, die zu einer ganz anderen hochsprachlichen Befehlszeile gehören.

Statische Formelauswertung zur Übersetzungszeit

Die Berechnung des Kreisumfangs mittels

         pi = 3.14159
         u  = 2 * pi * r

kann ein Compiler bereits zum Übersetzungszeitpunkt zu u = 6.28318 * r auswerten. Dies spart die Multiplikation 2 * pi zur Laufzeit des erzeugten Programms. Diese Vorgehensweise wird als Konstantenfaltung (engl. „constant folding“) bezeichnet. (Compiler für die Sprache Ada müssen diese Compile-Zeit-Berechnungen sogar in beliebiger Genauigkeit durchführen.)

Elimination toten Programmcodes

Wenn der Compiler erkennen kann, dass ein Teil des Programmes niemals durchlaufen wird, dann kann er diesen Teil bei der Übersetzung weglassen.

Beispiel:

           100   GOTO 900
           200   k=3
           900   i=7
           ...   ...

Wenn in diesem Programm niemals ein GOTO auf das Label 200 erfolgt, dann kann auf die Anweisung 200 k=3 verzichtet werden. Zusammen mit dem Label 200 ist der Sprung 100 goto 900 ebenfalls überflüssig.

Erkennung unbenutzter Variablen

Wird eine Variable nicht benötigt, so braucht dafür kein Speicherplatz reserviert zu werden und kein Programmcode erzeugt zu werden.

Beispiel:

       subroutine test (a,b)
           b = 2 * a
           c = 3.14 * b
           return b

Hier wird die Variable c nicht benötigt: Sie steht nicht in der Parameterliste, wird in späteren Berechnungen nicht verwendet und wird auch nicht ausgegeben. Deshalb kann die Anweisung c = 3.14 * b entfallen.

Optimierung von Schleifen

Insbesondere Schleifen versucht man zu optimieren, indem man zum Beispiel

• möglichst viele Variablen in Registern hält (normalerweise mindestens die Schleifenvariable);
• statt eines Index, mit dem auf Elemente eines Feldes (englisch array) zugegriffen wird, Zeiger auf die Elemente verwendet, dadurch wird der Aufwand beim Zugriff auf Feldelemente geringer;
• Berechnungen innerhalb der Schleife, die in jedem Durchlauf dasselbe Ergebnis liefern, nur einmal vor der Schleife ausführt;
• zwei Schleifen, die über denselben Wertebereich gehen, zu einer Schleife zusammenfasst, damit fällt der Verwaltungsaufwand für die Schleife nur einmal an;
• die Schleife teilweise oder (bei Schleifen mit konstanter, niedriger Durchlaufzahl) komplett auflöst (englisch loop unrolling), sodass die Anweisungen innerhalb der Schleife mehrfach direkt hintereinander ausgeführt werden, ohne dass jedes Mal nach den Anweisungen eine Prüfung der Schleifenbedingung und ein Sprung zum Schleifenbeginn erfolgen;
• die Schleife (vor allem bei Zählschleifen mit for) umdreht, da beim Herunterzählen auf 0 effiziente Sprungbefehle (Jump-Not-Zero) benutzt werden können;
• die Schleife umformt, damit die Überprüfung der Abbruchbedingung am Ende der Schleife durchgeführt wird (Schleifen mit Anfangsüberprüfung haben stets eine bedingte und eine unbedingte Sprunganweisung, während Schleifen mit Endüberprüfung nur eine bedingte Sprunganweisung haben);
• die ganze Schleife entfernt, wenn sie (nach einigen Optimierungen) einen leeren Rumpf besitzt. Dies kann allerdings dazu führen, dass Warteschleifen, die ein Programm absichtlich verlangsamen sollen, entfernt werden. Allerdings sollten für diesen Zweck, soweit möglich, sowieso Funktionen des Betriebssystems benutzt werden.
• verschachtelte Schleifen (Schleifen in Schleifen) – wenn es die verwendete Programmierlogik erlaubt – aufsteigend anordnet, von der äußersten Schleife mit den wenigsten Schleifendurchläufen bis zur innersten Schleife mit den meisten Schleifendurchläufen. Damit verhindert man vielfache Mehrinitialisierungen der inneren Schleifenkörper.

Einfügen von Unterprogrammen

Bei kleinen Unterprogrammen fällt der Aufwand zum Aufruf des Unterprogrammes verglichen mit der vom Unterprogramm geleisteten Arbeit stärker ins Gewicht. Daher versuchen Compiler, den Maschinencode kleinerer Unterprogramme direkt einzufügen. Diese Technik wird auch als Inlining bezeichnet. In manchen Programmiersprachen ist es möglich, durch inline-Schlüsselwörter den Compiler darauf hinzuweisen, dass das Einfügen von bestimmten Unterprogrammen gewünscht ist. Das Einfügen von Unterprogrammen eröffnet oft, abhängig von den Parametern, weitere Möglichkeiten für Optimierungen.

Halten von Werten in Registern

Anstatt mehrfach auf dieselbe Variable im Speicher, beispielsweise in einer Datenstruktur, zuzugreifen, kann der Wert nur einmal gelesen und für weitere Verarbeitungen in Registern oder im Stack zwischengespeichert werden. In C, C++ und Java muss dieses Verhalten ggf. mit dem Schlüsselwort volatile abgeschaltet werden: Eine als volatile bezeichnete Variable wird bei jeder Benutzung wiederholt vom originalem Speicherplatz gelesen, da ihr Wert sich unterdessen geändert haben könnte. Das kann beispielsweise der Fall sein, wenn es sich um einen Hardware-Port handelt oder ein parallel laufender Thread den Wert geändert haben könnte.

Beispiel:

    int a = array[25]->element.x;
    int b = 3 * array[25]->element.x;

Im Maschinenprogramm wird nur einmal auf array[25]->element.x zugegriffen, der Wert wird zwischengespeichert und zweimal verwendet. Ist x volatile, dann wird zweimal zugegriffen.

Es gibt außer volatile noch einen anderen Grund, der eine Zwischenspeicherung in Registern unmöglich macht: Wenn der Wert der Variablen v durch Verwendung des Zeigers z im Speicher verändert werden könnte, kann eine Zwischenspeicherung von v in einem Register zu fehlerhaftem Programmverhalten führen. Da die in der Programmiersprache C oft verwendeten Zeiger nicht auf ein Array beschränkt sind (sie könnten irgendwohin im Hauptspeicher zeigen), hat der Optimizer oft nicht genügend Informationen, um eine Veränderung einer Variablen durch einen Zeiger auszuschließen.

Verwendung schnellerer äquivalenter Anweisungen

Statt einer Multiplikation oder Division von Ganzzahlen mit einer Zweierpotenz kann ein Schiebebefehl verwendet werden. Es gibt Fälle, in denen nicht nur Zweierpotenzen, sondern auch andere Zahlen (einfache Summen von Zweierpotenzen) für diese Optimierung herangezogen werden. So kann zum Beispiel (n << 1) + (n << 2) schneller sein als n * 6. Statt einer Division durch eine Konstante kann eine Multiplikation mit dem Reziprokwert der Konstante erfolgen. Selbstverständlich sollte man solch spezielle Optimierungen auf jeden Fall dem Compiler überlassen.

Weglassen von Laufzeitüberprüfungen

Programmiersprachen wie Pascal und Java fordern Laufzeitüberprüfungen beim Zugriff auf Felder oder Variablen. Wenn der Compiler ermittelt, dass ein bestimmter Zugriff immer im erlaubten Bereich sein wird (zum Beispiel ein Zeiger, von dem bekannt ist, dass er an dieser Stelle nicht NULL ist), kann der Code für diese Laufzeitüberprüfungen weggelassen werden.

Reduktion von Paging zur Laufzeit

Zusammenhängender Code, zum Beispiel eine Schleife, sollte zur Laufzeit möglichst auf der gleichen „Seite“ (zusammenhängend vom Betriebssystem verwalteter Speicherblock) im Hauptspeicher liegen. Dies kann man zum Beispiel dadurch erreichen, dass man dem Programmcode geeignete Leeranweisungen („NOPs“ – No OPeration) hinzufügt. Dadurch wird der Programmcode zwar größer, aber wegen des reduzierten Pagings wird das Programm schneller ausgeführt.

Vorziehen bzw. Verzögern von Speicherzugriffen

Durch das Vorziehen von Speicherlesezugriffen und das Verzögern von Schreibzugriffen lässt sich die Fähigkeit moderner Prozessoren zur Parallelarbeit verschiedener Funktionseinheiten ausnutzen. So kann beispielsweise bei den Befehlen: a = b * c; d = e * f; der Operand e bereits geladen werden, während ein anderer Teil des Prozessors noch mit der ersten Multiplikation beschäftigt ist.

Ein Beispielcompiler

Folgendes in der Programmiersprache C definiertes Programm stellt einen einfachen Einpass-Compiler dar. Dieser Compiler übersetzt einfache Ausdrücke in Infix-Notation in Ausdrücke der Postfix-Notation sowie in eine maschinennahe Assemblersprache. Er arbeitet mit der Technik des rekursiven Abstiegs.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
#define MODE_POSTFIX 0
#define MODE_ASSEMBLY 1
 
#define MAX_EXPRESSION_LENGTH 20
 
char lookahead;
int pos;
int compile_mode;
char expression[MAX_EXPRESSION_LENGTH+1];
 
void error() {
  printf("Syntaxfehler!\n");
}
 
void match( char t ) {
  if( lookahead == t ) {
    lookahead = expression[++pos];
  }
  else
    error();
}
 
void digit() {
  switch( lookahead ) {
    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '8': case '9':
        printf( compile_mode == MODE_POSTFIX ? "%c " : "\tPUSH %c\n", lookahead );
        match( lookahead );
        break;
    default:
        error();
        break;
  }
}
 
void term() {
  digit();
  while( 1 ) {
    switch( lookahead ) {
      case '*':
        match('*');
        digit();
        printf( "%s", compile_mode == MODE_POSTFIX
                      ? "* " : "\tPOP B\n\tPOP A\n\tMUL A, B\n\tPUSH A\n" );
        break;
      case '/':
        match('/');
        digit();
        printf( "%s", compile_mode == MODE_POSTFIX
                      ? "/ " : "\tPOP B\n\tPOP A\n\tDIV A, B\n\tPUSH A\n" );
        break;
      default:
        return;
    }
  }
}
 
void expr() {
  term();
  while( 1 ) {
    switch( lookahead ) {
      case '+':
        match('+');
        term();
        printf( "%s", compile_mode == MODE_POSTFIX
                      ? "+ " : "\tPOP B\n\tPOP A\n\tADD A, B\n\tPUSH A\n" );
        break;
      case '-':
        match('-');
        term();
        printf( "%s", compile_mode == MODE_POSTFIX
                      ? "- " : "\tPOP B\n\tPOP A\n\tSUB A, B\n\tPUSH A\n");
        break;
      default:
        return;
    }
  }
}
 
int main ( int argc, char** argv ) {
  printf("Bitte geben Sie einen Ausdruck in Infix-Notation ein:\n\n\t");
  fgets( expression, MAX_EXPRESSION_LENGTH, stdin );
 
  printf("\nKompilierter Ausdruck in Postfix-Notation:\n\n\t");
  compile_mode = MODE_POSTFIX;
  pos = 0;
  lookahead = *expression;
  expr();
 
  printf("\n\nKompilierter Ausdruck in Assemblersprache:\n\n");
  compile_mode = MODE_ASSEMBLY;
  pos = 0;
  lookahead = *expression;
  expr();
 
  return 0;
}

Ein Lauf dieses Compilers führt beispielsweise zu folgender Ausgabe:

  Bitte geben Sie einen Ausdruck in Infix-Notation ein:

       5+3*2-9

  Kompilierter Ausdruck in Postfix-Notation:

       5 3 2 * + 9 -

  Kompilierter Ausdruck in Assemblersprache:

        PUSH 5
        PUSH 3
        PUSH 2
        POP B
        POP A
        MUL A, B
        PUSH A
        POP B
        POP A
        ADD A, B
        PUSH A
        PUSH 9
        POP B
        POP A
        SUB A, B
        PUSH A

Einzelnachweise

1. ↑ F.L. Bauer, J. Eickel: Compiler Construction: An Advanced Course. Springer, 1975
2. ↑ Transcompiler. In: Neogrid IT Lexikon. abgerufen am 18. November 2011 (deutsch): „Wenn ein Compiler aus dem Quellcode einer Programmiersprache den Quellcode einer anderen erzeugt (z. B. C in C++) so spricht man von einem Transcompiler.“ 
3. ↑ Inventor of the Week Archive. Massachusetts Institute of Technology (Juni 2006). Abgerufen am 25. September 2011.
4. ↑ Kurt W. Beyer: Grace Hopper and the invention of the information age. Massachusetts Institute of Technology, 2009, ISBN 978-0-262-01310-9 (Google Books, abgerufen am 25. September 2011).
5. ↑ Kathleen Broome Williams: Grace Hopper. Naval Institute Press, 2004, ISBN 978-1-55750-952-9 (Google Books, abgerufen am 25. September 2011).

Literatur

• Alfred V. Aho, Lam, Ravi Sethi, Jeffrey D. Ullman: Compilers: principles, techniques, & tools. Pearson Addison-Wesley, Boston 2007, ISBN 0-321-48681-1.
• Alfred V. Aho, Lam, Ravi Sethi, Jeffrey D. Ullman: Compiler. Pearson, 2008, ISBN 978-3-8273-7097-6 (Deutsche Übersetzung).
• Reinhard Wilhelm, Dieter Maurer: Übersetzerbau – Theorie, Konstruktion, Generierung. Springer, 1997, ISBN 3-540-61692-6.
• Niklaus Wirth: Grundlagen und Techniken des Compilerbaus. 3., bearbeitete Auflage.. Oldenbourg Wissenschaftsverlag, München 2011, ISBN 978-3-486-70951-3.

Normdaten: SWD in der DNB: 4148248-7