Algol-60-Bericht

Der Algol-60-Bericht wurde zwischen 1959 und 1960 von einem Team von Programmiersprachenexperten, bestehend aus dem Herausgeber Peter Naur und mehreren Lehrern und Praktikern aus Europa und den Vereinigten Staaten, verfasst. Ziel des Berichts war es, eine vollständige Beschreibung einer internationalen algorithmischen Sprache zur Darstellung numerischer Prozesse in einer Form zu entwickeln, die sich für die Übersetzung in Computerprogrammiersprachen eignet. Sie war nicht als Programmiersprache gedacht, obwohl sie später als Sprache implementiert wurde und in Europa populär wurde.

Viele Versionen der Programmiersprache Algol wurden in den 1960er und frühen 1970er Jahren implementiert. Sie führte auch zur Entwicklung mehrerer anderer Programmiersprachen, wie Pascal, das von Niklaus Wirth in den frühen 1970er Jahren implementiert wurde, und C.

Der Bericht führte die Begriffe einer Referenzsprache, einer Publikationssprache und einer Hardwaredarstellung ein. Die Referenzsprache war der Standard für den Bericht, die Compiler-Autoren und die Hardware-Implementierung. Sie gab die Form der Sprache und ihre Syntax vor. Die Publikationssprache verwendete die Referenzsprache mit geringfügigen Anpassungen an länderspezifische Unterschiede in der Publikation und in der Druck- und Schreibweise, z. B. bei der Behandlung von tiefgestellten und hochgestellten Buchstaben und anderen Notationen. Bei der Hardware-Darstellung wurden die Eigenschaften der Maschine berücksichtigt. Die Referenzsprache war die definierende Sprache, und die Publikationssprache und die Hardware-Darstellung mussten in diese Sprache übersetzbar sein.

Der Zweck des Berichts und der Sprache war es, verschiedenen Computerkonzepten eine eindeutige Darstellung zu geben – insbesondere dem Entwurf von Algorithmen, oder ALGOrithmic Language 1960. Eine spätere Version, Algol68, war nicht so populär oder weit verbreitet wie Algol-60, obwohl sie leistungsfähiger war.

Algol ist eine strukturierte Sprache, die while-Anweisungen, if-then-else-Anweisungen und andere Konstrukte enthält, die Auswahl, Iteration, grundlegende Anweisungen, Blockstruktur und Rekursion implementieren. Obwohl sie nur wenige Jahre nach FORTRAN (FORmula TRANslator) entwickelt wurde, das 1957 von IBM herausgegeben wurde, enthielt sie Funktionen, die in FORTRAN fehlten – nämlich die Rekursion und die strukturierte Sprache – und war ein großer Fortschritt in der Programmierung.

Einer der Nachfahren von Algol und FORTRAN war die Sprache BASIC (Beginner’s All-purpose Symbolic Instruction Code), die von John Kemeny und Thomas Kurtz von der Dartmouth University entwickelt wurde. BASIC war eine Art formatanweisungsfreie Version von FORTRAN für interaktives Rechnen und Anfänger. BASIC erfreute sich von den 1970er bis zu den 1980er Jahren einer langen Beliebtheit und wurde kürzlich in einer ganz anderen Form, Visual Basic, implementiert.

Ein Nachkomme von Algol war Pascal, das sich ebenfalls einer langen Beliebtheit als Sprache zur Implementierung von Datenstrukturen und zum Studium von Compilern erfreute. Es war keine Produktionssprache, sondern ein Lehrmittel. C war eine Systemsprache und führte zur Entwicklung von C, einer objektorientierten Sprache, die immer noch beliebt ist.

Die Algol-Sprache wurde in einer Notation beschrieben, die Backus-Normal- oder Backus-Naur-Form (BNF) genannt wird. Die Notation wurde von John Backus vorgeschlagen, der sie auf eine Notation von E. L. Post, einem berühmten Logiker in den 1930er Jahren, zurückführte. Sie ähnelt der von Noam Chomsky 1957 für die Linguistik entwickelten Notation, die zur Implementierung von Grammatiken verwendet wurde. Eine Grammatik ist eine knappe, eindeutige Methode zur Beschreibung von Sprachen. Die Verwendung einer formalen Notation in der Sprachtheorie war ein großer Fortschritt.

Die Entwicklung der Programmiersprachen war beeindruckend, aber nicht so atemberaubend wie die Entwicklung der Compiler-Theorie. Kurz nach dem Algol-60-Bericht verwendeten mehrere Compiler-Theoretiker die Grammatiknotation, um Compiler auf „automatische“ Weise zu implementieren. Diese Compiler wurden als Compiler-Compiler bezeichnet. Ähnliche Bemühungen waren die Entwicklung von Lex, einem lexikalischen Analysator, und Yacc („Yet another compiler-compiler“) in den Bell Laboratories Mitte der 1970er Jahre.

Understanding Programming Language

Die englische Grammatik hat bestimmte Konstrukte, wie z.B. eine Substantivphrase, die aus anderen Konstrukten, wie einem Substantiv und einem Modifikator, besteht. In Programmiersprachen gibt es Konstrukte wie while-Anweisungen und arithmetische Ausdrücke. Diese Konstrukte werden durch spezielle Symbole angezeigt, die als Nichtterminal- oder Metasymbole der Sprache bezeichnet werden.

Die Symbole, die tatsächlich in der Sprache erscheinen, werden Terminalsymbole genannt. Die Terminologie stammt von den Datenstrukturen oder Parse-Bäumen, die zur Implementierung der Sprache verwendet werden.

Ein Beispiel ist:

Diese Grammatik zeigt an, dass ein arithmetischer Ausdruck, E, aus anderen arithmetischen Ausdrücken und Termen, T, besteht, die zusammengefügt werden (E–>E T). Ein Term T setzt sich zusammen aus einem Term mal einem Faktor F, so dass T–>T*F. Ein Faktor F schließlich ist der einfachste Ausdruck, der aus eingeklammerten Ausdrücken (dem eingeklammerten E), Bezeichnern (benutzerdefinierten Bezeichnern oder Variablen), id und numerischen Konstanten (num) besteht. Die Grammatik gibt die Form der arithmetischen Ausdrücke vor.

Das Beispiel gibt einen Eindruck von der Notation. Die Elemente auf der linken Seite des Pfeils sind aus den Elementen auf der rechten Seite zusammengesetzt. In diesem Fall sind E, T und F die Metasymbole. Die anderen Symbole, *, (, ), und in diesem Fall id und num, kommen in der Sprache vor. Sie sind die Wörter der Sprache. In diesem Fall ist E das Startsymbol oder das erste nicht-terminale Symbol. Es ist der allgemeinste Ausdruck, der definiert wird. Obwohl die Notation auf den ersten Blick umständlich erscheinen mag, ist sie für den Entwurf von Sprachen, die Compiler-Theorie und die Implementierung nützlich.

Die Entwicklung von Grammatiken in der Informatik gab dem Entwurf und der Implementierung von Programmiersprachen einen großen Auftrieb.

Siehe auch Algorithmen; Prozedurale Sprachen; Programmierung.

Roger R. Flynn

Bibliographie

Naur, Peter, ed. „Revised Report on the Algorithmic Language Algol-60.“ Communications ACM 6, no. 1 (1963): 1-17.

Wexelblat, Richard L., ed. History of Programming Languages. New York: Academic Press, 1981.