Axel Rogat
Aufbau und Arbeitsweise von Compilern
 
  1.10: Compilationsphasen Kapitel 1 2: Theoretische Grundlagen 
 
  1.11 Geschichte  
 

Der Compilerbau ist eines der ältesten Forschungsgebiete der Informatik (d.h. ab etwa 1950 formalisiert betrachtet).

Eine Grundlage wurde in den späten 20er Jahren gelegt, als die sogenannte "umgekehrte polnische Notation" ( UPN, Postfix-Notation, klammerfreie Notation) für arithmetische Ausdrücke untersucht wurde (J. Lukasiewicz),
z.B.   (a+b)c+d/e  -->  ab+cde/+

Diese Notation ist sehr wichtig für die Mechanisierung und Formulierung des Übersetzungsvorgangs -- insbesondere natürlich bei der Übersetzung von arithmetischen Ausdrücken, aber auch bei verschachtelten Kontrollstrukturen.

In den 1930ern und 40ern wurden zuerst formalisierte Regeln zur Bildung von Ausdrücken entwickelt.

Anfang der 50er wurde ein Algorithmus entwickelt, der arithmetische Ausdrücke auf ihre syntaktische Korrektheit prüfte. Außerdem wurde zum ersten Mal der mechanische Übersetzungsvorgang (nur für Ausdrücke) im Detail beschrieben ("automatische Rechenplanfertigung").

Als Compiler hatte man bis dahin ein Hilfsprogramm bezeichnet, das das Gesamtprogramm aus einzelnen Formelauswertungen und Unterprogrammen zusammensetzte, die noch per Hand in Maschinensprache geschrieben werden mußten (englisch "to compile" = sammeln, zusammentragen).

1954 kam der Begriff "algebraic compiler" für ein Programm auf, das die Umsetzung von Formeln in Maschinencode selbst übernahm. Das "algebraic" fiel im Lauf der Zeit weg.

Beispiel: Eine besondere Schwierigkeit bestand damals darin, die Operator-Prioritäten ("Punktrechnung vor Strichrechnung") korrekt umzusetzen. In den ersten FORTRAN-Compilern behalf man sich z.B. damit, daß man die Operatoren im Quelltext mit Hilfe eines Makroprozessors durch Klammerkonstrukte ersetzte.

Zum Beispiel wurde + ersetzt durch )))+(((, entsprechend -, es wurde * ersetzt durch ))*((, entsprechend /, und ** (Potenzierung) durch )**(. Klammern in Formeln wurden durch vier Klammern ersetzt, und der ganzen Formel wurde ((( vorangestellt und ))) angefügt. Dadurch werden die richtigen Prioritäten erzwungen.

Aus

A+B*C+D/(E-F)
wird mit (per Hand) erzwungenen Prioriäten:
(A+(B*C)) + (D/(E-F))
dagegen mit Hilfe der obigen Konstruktion:
(((A)))+(((B))*((C)))+(((D))/((((((E))-((F)))))))
(am besten auf Papier nachvollziehen...)
Um 1957 beschäftigte man sich in der Sowjetunion (Lyapunov, Yanov) mit der Darstellung von arithmetischen Ausdrücken in Form von Binärbäumen und mit der Manipulation in diesem Format.

Die vorher bereits zur Darstellung von Nervenaktivitäten benutzten endlichen Automaten (1943 McCulloch) wurden Anfang der 50er in die Informatik importiert und erlangten schnell überragende Bedeutung.

Im Lauf der 50er Jahre wurden die ersten lauffähigen Compiler für Großrechner entwickelt, z.B. für FORTRAN (1954 IBM, Sheridan) und ALGOL.

Bei der Entwicklung eines neuen ALGOL-Standards (ALGOL60) wurden erstmals Formalismen zur Beschreibung von höheren Programmiersprachen entwickelt (Backus und Naur).

Die schon vorher (1956) von Chomsky entwickelten Methoden zur Definition der Syntax von natürlichen Sprachen wurde um diese Zeit erstmals auf Computersprachen angewandt.

Weitere wichtige Entwicklungen stichwortartig:

1954 Minimierungsalgorithmen für endliche Automaten (Huffman, Moore)
1956 Einführung der regulären Ausdrücke (Kleene)
1959 Beweis der Äquivalenz von deterministischen und nicht-deterministischen endlichen Automaten (Robin, Scott)
1960 Algorithmus zur Konstruktion eines endlichen Automaten zu einem regulären Ausdruck
1961 Ansätze zur Entwicklung von attributierten Grammatiken (synthetisierte Attribute)
1961 Entwicklung erster recursive-descent-Parser (Lucas, Conway)
1963 Betrachtung von Syntaxbäumen (McCarthy)
1963 Entwicklung von Fehlerbehandlungsmethoden aufgrund formaler Grammatikregeln (Irons)
1964 Compiler-Generatoren mit recursive descent (META: Schorre, TMG: McClure 1965)
1965 Erste Implementation komplexer Typ-Überprüfung (ALGOL)
1965 Parser-Algorithmus für beliebige kontextfreie Sprachen (Younger, Cocke, Kasami)
1965 LR(k)-Analyse erweitert die Klasse der compilierbaren Sprachen bedeutend (Knuth)
1966 Algorithmus zur optimalen Verwendung von Registern (Horwitz, für FORTRAN)
1968 Untersuchung von LL(k)-Grammatiken (Lewis, Stearns, Forster)
1968 Einführung von attributierten Grammatiken zur Beschreibung der Semantik von Programmiersprachen (Knuth)
1969 Verwendung von endlichen Automaten und Maschinen für lexikalische und syntaktische Analyse
1969 Die Entwicklung von LALR(k)- und SLR(k)-Methoden ermöglicht das erste Mal effiziente Bottom-Up-Parser
1971 Definition der Wohldefiniertheit von attributierten Grammatiken (Knuth)
1973 Exakte formale Definition von PASCAL
1975 Entwicklung des Scanner-Generators LEX (Lesk) und des Parser-Generators Yacc (Johnson)

 
  1.10: Compilationsphasen Kapitel 1 2: Theoretische Grundlagen