You are hereEin ELAN Compiler

Ein ELAN Compiler


By thomas - Posted on 14 November 2011

In den folgenden Seiten werde ich versuchen, einen Compiler für die Programmiersprache ELAN zu erzeugen. In wieweit das gelingen wird ist mir zum jetzigen Zeitpunkt selbst noch nicht klar. Hier entsteht das Programmsystem parallel zum Text und umgekehrt. Die Wahrscheinlichkeit ist hoch, dass wir einen sinnvoll arbeitenden Scanner und Parser erhalten. In wieweit wir die tatsächliche Code-Generierung für einen konkreten Prozessor schaffen, weiß ich nicht (und, um ehrlich zu sein, ich glaubs auch nicht).

Gleich vorweg ein Hinweis: Die Quellen sind unter https://io.ax.lt/viewcvs/cvsroot/elan/ zu finden. Über diesen Link kann man im Code ein bisschen rumstöbern. Natürlich ist jeder dazu eingeladen, an den Quellen bzw. dem Compiler mitzubasteln. Dazu ists hilfreich, das Repository auszuchecken:

export CVSROOT=:pserver:anonymous@io.ax.lt/srv/cvs/cvsroot
cvs checkout elan

Gerne nehme ich Patches entgegen wenn sie in einem halbwegs lesbaren Format vorliegen. Sendet sie mit einfach per Mail an elan(at)io.ax.lt zu.

Die Sprache ELAN stammt aus den 70er Jahren, 1976 um genau zu sein an der TU Berlin und der GMD entwickelt (Wikipedia:ELAN). ELAN heißt (E)ducational (LAN)guage, und wurde als solche bis weit in die 80er an diversen Lehranstalten eingesetzt.
Meiner Meinung nach könnte ELAN aber auch (E)xtendable (LAN)guage heißen, weil sie dafür ein paar wesentliche Eigenschaften mitbringt:

Modul-Konzept
Ein Modul-Konzept womit auch größere Programmsysteme realisierbar sind (sog. PACKETs); das wäre vergleichbar mit UNITs aus Turbo-Pascal. Damit lassen sich also große Programme in Teile aufgliedern die nur über ihre jeweiligen Schnittstellen miteinander kommunizieren. Nicht nur dass somit auch mehrere Programmierer an einem Projekt arbeiten können, lässt sich so hat auch vermeiden, dass unerwünschte Seiteneffekte auftreten.

Operatoren
Operatoren können frei auf neue Datentypen definiert werden können. So läßt sich beispielsweise ein Multiplikations-Operator (*) auch für einen Integer- und einen Zeichen-Wert definieren: 5 * "a" ergäbe "aaaaa". ELAN ansich kennt eigentlich nur ein paar Typen (INT, REAL, TEXT, BOOL), aber von sich aus kaum Operatoren, die darauf agieren. Erst im Standard-Modul wird ein Operator definiert, der beispielsweise einen INT zu einem anderen INT dazuzählen kann. Das ist, warum ich behaupte, es könnte auch (E)xtendable (LAN)guage heißen.

Wertliefernde Statements
Jedes Statement kann einen Wert liefern. Denkt man, dass C durch das ?:-Konstrukt recht flexibel in Zuweisungen sein kann, so ist das in einer sogar noch erweiterten Form bereits in ELAN zu finden gewesen:
C:

x = (a > 0) ? y : z;

ELAN:

x := IF a > 0 THEN y ELSE z FI;

Die Notation in C ist zugegebenermaßen kürzer, aber ELAN ist hier leistungsfähiger. So geht eben auch

x := SELECT a OF
       CASE 1 : p
       CASE 2 : q
       CASE 3 : r
       CASE 4 : s
       OTHERWISE z
     ENDSELECT;

*) allerdings erst in späteren Erweiterungen des ELAN-Standards
Cool, nicht wahr?

Refinements
Eine wirkliche Spezialität von ELAN sind aber die sogenannten Refinements. In klassischen Pascal-Programmen wird eine Aufgabenstellung üblicherweise von unten nach oben (bottom_up) gelöst. Das heißt, im Quelltext erscheinen nacheinander Prozeduren (und Funktionen) die von einen recht tiefen Detaillierungsgrad zu immer abstrakteren Formulierungen reifen.

PASCAL:

PROCEDURE eingabe(VAR i : Integer);
BEGIN
  Write('Bitte Zahl eingeben: ');
  ReadLn(i);
END;

PROCEDURE verarbeite(i, j : Integer; VAR k : Integer);
BEGIN
  k := i + j;
END;

PROCEDURE ausgabe(i, j, k : Integer);
BEGIN
  WriteLn('Die Summe von ',i,' und ',j,' ist ',k);
END;

VAR a, b, c : Integer;
BEGIN
  eingabe(a);
  eingabe(b);
  verarbeite(a,b,c);
  ausgabe(a,b,c);
END.

Erst am Ende des Quelltextes ist eine recht abstrakte Formulierung der Lösung zu finden. Durch den klassischen Lesestil von oben nach unten muss sich der Programmierer erst durch Details hindurcharbeiten um erst gegen Ende zu sehen, für was das alles gut ist. In ELAN wiederum könnte man diese Aufgabe mit Hilfe von Refinements sozusagen von oben herab verfeinern. Dieses Vorgehen nennt man auch stepwise refinement (C2:Zähneputzen), schrittweise Verfeinerung. Die Aufgabenstellung ist ja, zwei Zahlen einzulesen, sie zu verarbeiten und ein Ergebnis auszugeben. Und genau so läßt sich das in ELAN formulieren:

main:
  gebe zwei zahlen ein;
  verarbeite die zahlen;
  gib ergebnis aus.

Damit ist in den ersten vier Zeilen schon klar worum es in dem Programm geht. Es wird zunächst das WAS beschrieben, im weiteren Verlauf dann mehr und das WIE. Das genannte Beispiel läßt sich wie folgt, im top_down-Stile, ausformulieren:

ELAN:

main:
  gebe zwei zahlen ein;
  verarbeite die zahlen;
  gib ergebnis aus.

gebe zwei zahlen ein:
  gib eine zahl ein;
  gib noch eine zahl ein.

gib eine zahl ein:
  INT VAR i;
  put("Gib eine Zahl ein: ");
  get(i).

gib noch eine zahl ein:
  INT VAR j;
  put("Gib eine Zahl ein: ");
  get(j).

verarbeite die zahlen:
  INT VAR k;
  k := i + j.

gib ergebnis aus:
  put("Summe aus "+text(i)+" und "+text(j)+" ist "+text(k)).

Bemerkenswert ist dabei zu beobachten, wie die Anzahl der Elemente, die nicht natürlich-sprachlichen Ursprungs sind (z.B. Typbezeichner, Kalkulationsanweisungen etc.), gegen Ende des Programmes zunimmt, in gleichem Maße wie die natürlichsprachlichen Elemente abnehmen. Der technische Detailierungsgrad nimmt zu.

Natürlich läßt sich das o.g. ELAN-Programm auch im bottom_up-Stil schreiben. Dann sieht es sehr ähnlich zum Pascal-Programm aus:

PROC eingabe(INT VAR i) :
  put("Gib eine Zahl ein: ");
  get(i)
ENDPROC;

PROC verarbeite(INT CONST i, j, INT VAR k) :
  k := i + j
ENDPROC;

PROC ausgabe(INT CONST i, j, k) :
  put("Die Summe von "+text(i)+" und "+text(j)+" ist "+text(k))
ENDPROC;

main:
  INT VAR a, b, c;
  eingabe(a);
  eingabe(b);
  verarbeite(a,b,c);
  ausgabe(a,b,c) .

Offensichtlich lassen sich also die bottom_up- und top_down-Strukturen gleichzeitig verwenden. Ein Hauptprogramm wie in Pascal eingebettet zwischen BEGIN und END besteht in ELAN aus einem Refinement.

Bei der Gelegenheit will ich gleich darauf hinweisen, dass der Compiler (so es denn jemals einer werden wird) in C realisiert wird. Warum nicht in ELAN selbst? Ja, könnten wir auch tun, Pascal, Fortran, Assembler, PL/I wäre natürlich ebenso möglich. Im Prinzip ist es eher zweitrangig in welcher Sprache der Compiler realisiert wird, die Aufgabe desselben ist aus der Ausgangssprache S in eine Zielsprache T umzuformen. Dass dazu die Sprache L verwendet wird, ist in diesem unserem speziellen Fall recht egal.
Apropos S, T und L - das Umsetzen von S nach T unter Zuhilfenahme von L sieht man häufig auch in den sog. T-Diagrammen. N.Wirths Buch "Compilerbau" [1] wird auf dem Buchdeckel damit schön geschmückt.

    +---------------+---------------+
    |                               |
    |     S     -------->     T     |
    |                               |
    +---------+ - - - - - +---------+
              |           |
              |     L     |
              |           |
              +-----------+

Ein einfaches Beispielprogramm reicht aber natürlich nicht aus um die Struktur einer Programmiersprache vollständig zu beschreiben. Im Allgemeinen sind die einen oder anderen Begriffe vorher zu definieren und die einen oder anderen Fragestellungen zu beantworten.