Kurs:Programmieren in Aleph/ein Compiler

• Einleitung
• Installation
• Sprachschatz
• Objekte
• Befehle
• Java-Basis
• Java-Kooperation
• Anwendungen
•  Compiler  
• Rekursion
• Infix
• Listen

Der Colon-Compiler

Aleph hat keinen Compiler, die virtuelle Maschine V2M auch nicht. Es existieren compilierende Anweisungen, die es gestatten jederzeit kleine Elemente eine Compilat hinzuzufügen. Damit ist zwar ein Maximum an Flexibilität gegeben, aber es ist umständlich eine komplette neue Anweisung (Methode, Unterprogramm) "mal eben so" zu erstellen. Der hier beschriebene "Colon-Compiler" füllt diese Lücke.

Namensgebung

Funktionen, Prozeduren, Unterprogramme oder Methoden sind eigenständige Sequenzen von compiliertem Code, versehen mit einem Namen. In Aleph heißen diese Gebilde einfach Commands oder Anweisungen. Weil Aleph sehr auf Klarheit der verwendeten Bezeichner Wert legt (legen muss), wird eine Sequenz als Aufzählung angesehen und der Name als Bezeichnung der Aufzählung. In diesem Sinne sind

• Zahlen : 3 4 9 4
• Zeichen : & % a Z
• Aufzählung : Zahlen Zeichen usw.

derartige Sequenzen. Die letzte Aufzählung kann auch als

• Aufzählung : 3 4 9 4 & % a Z usw.

formuliert werden. Der Aufbau folgt stets dem dem gleichen Schema.

• Bezeichnung : Element-1 Element-2 ... Element-n

Ein Doppelpunkt oder Colon trennt die Bezeichnung von der Liste mit Elementen, die unter einer Bezeichnung zusammengefasst werden. Bei Programmen sind die Elemente eben zu compilierende Zeichenketten und die Bezeichnung der Name des (Unter)Programms. Der Doppelpunkt ist bei vielen Sprachen oft durch Klammern ersetzt. Aleph hat keine Klammern. Der Doppelpunkt ist also das Zeichen mit der stärksten Aussagekraft im Sinne dieser Trennung. Deshalb der Name Colon-Compiler.

Arbeitsweise des Compilers

Compiler sind normalerweise sehr komplexe Systeme. So muss der Quellcode einer Syntaxprüfung unterzogen und aus den einzelnen Sprachelementen der Code für die Maschine erzeugt werden. Oft sind noch Optimierer und Linker beteiligt, bis ein ausführbares Programm fertig ist. Wie aber sieht die Sache aus wenn weder Syntax noch Grammatik vorhanden sind? Die spontane Antwort ist oft: "Sinnlos!". Wird dem Anwender zugestanden zu wissen was er tut, stellt sich dem System diese Frage überhaupt nicht. Der Colon-Compiler geht davon aus, dass der Anwender über dieses Wissen verfügt. Im Gegensatz zu herkömmlichen Programmiersprachen und deren Compilern hat der Anwender bei Aleph immer im Recht. Es gibt eine Ausnahme. Es kann sein, dass der Anwender die Kompilierung von etwas Unbekanntem verlangt. Weil das unmöglich ist, wird eine entsprechende Meldung ausgegeben. Keinesfalls wird deshalb der gesamte Vorgang abgebrochen. Die Arbeitsweise kann nun in die folgenden Abschnitte unterteilt werden:

1. Bezeichnung der Anweisung speichern.
2. Wort lesen. Wenn Ende der Kompilierung , dann weiter bei 4.
3. Kompilierten Code des Worts der Aufzählung hinzufügen, weiter bei 2.
4. Aufzählung mit Bezeichnung verbinden.

Die eigentliche Arbeit findet in den Punkten 2 und 3 statt. Hier werden Eigenschaften der Worte geklärt. Dazu gehört u.a. ob eine Zahl, ein String oder ein Command zu compilieren ist. Aber auch, ob ein imediate Command auszuführen ist, um erst danach eine spezielle Kompilierung durchzuführen ist.

Ganz so einfach ist auch dieser Compiler nicht. Ein Flussdiagramm ist hier das beste Mittel zur Veranschaulichung. Die einzelnen Elemente des Diagramms werden hier kurz erläutert.

• Wort gelesen

Die Anweisung "word" liest ein Wort (Zeichenkette ohne Leerzeichen) von der Eingabe. Wurde etwas gelesen, so liegt die Zeichenkette und ein true auf dem Stack, sonst nur false.

• Kommentar

Wenn die Zeichenkette mit "//" beginnt, liegt ein Kommentar vor und wird ignoriert.

• Ende

Besteht die Zeichenkette nur aus dem Semikolon (';'), so ist das Ende der Kompilierung erreicht.

• Command

Die Anweisung "find" such im Wortschatz nach einem Command mit dem Namen der Zeichenkette. Wurde ein Command gefunden, so liegt das Command und ein true auf dem Stack, sonst nur false.

• Symbol

Wenn die Zeichenkette etwas symbolisiert, also eine Zahl, einen Character, usw. darstellt, so liegt das Symbol und ein true auf dem Stack, sonst nur false.

• immediate

Ist ein "immediate" Command vorhanden, so wird es ausgeführt.

Es zeigt sich, dass bereits dieses kleine Programm syntaktische Elemente verlangt. So miss eine Neudefinition stets mit einem Doppelpunkt beginnen. Die Kompilierung endet erst, wenn ein Semikolon gelesen wurde. Wenn aber kein Semikolon mehr in der Datei vorhanden ist, wird der Compiler mit einer entsprechenden Meldung verlassen. Weil Dateien stets ein Ende haben, könnten sie auch unmittelbar nach dem Doppelpunkt enden. Dann wird die Schleife gar nicht betreten und stattdessen eine entsprechende Meldung ausgegeben.

Eintrag ins Dictionary

Der Code, den das Diagramm verlangt, muss nach seiner Erzeugung einem Eintrag im Dictionary zugeordnet werden. Deshalb muss dieser Eintrag erst einmal vorhanden sein.

":" entry

Schon fertig. Ein neuer leerer Eintrag im Dictionary. Wird jetzt da Command ":" aufgerufen, macht das nichts - wortwörtlich.

Compilieren ohne Compiler

Bis jetzt steht prinzipiell fest, wie der Compiler arbeiten soll. Nun ergibt sich das Problem wie der Compiler selbst compiliert werden soll. Für Sprachen wie C, C++, Java usw. gibt es Compiler Compiler (yacc oder javaCC). Für Aleph kann es derartige Werkzeuge nicht geben, denn ohne Syntax keine BNF und somit auch kein linearer Automat.

Es gibt einen Ausweg. Aleph verfügt über einen kleinen Befehlssatz. Dazu gehören auch Commands "compile", "entry", "symbol", "bind" und "find". Ihre Funktionsweisen sind sehr einfach, und werden hier noch einmal kurz dargestellt.

• symbol

bildet aus einer Zeichenkette eine Identitätsfunktion. Funktion sind in Aeph stets Commands. Dieses Command liegt dann auf dem Stack.

• find

findet das Command mit dem Namen der Zeichenkette. Das gefundene Command liegt dann auf dem Stack.

• compile

Das oberste Objekt auf dem Stack (Command oder nicht) wird an einen Speicherbereich namens "HERE" angehängt. In Kurzform: "Ausführbaren Code hier anhängen."

• entry

Eine Zeichenkette wird in den Wortschatz aufgenommen.

• bind

Der Bereich mit dem Compilat (HERE) wird dem zuletzt gemachten Eintrag im Wörterbuch als ausführbarer Code zugewiesen.

Mit diesen wenigen Anweisungen könn bereits neues Commands erzeugt werden, was ja einer Kompilation entspricht. Die Vorgehensweise wird anhand des Colon-Compilers selbst besprochen.

Zeichenkette in Command wandeln

Die neue Anweisung soll über den Namen (auf dem Stack) identifiziert und der ausführbare Code, das Command selbst, auf dem Stack abgelegt werden. Dabei ist vorausgesetzt, dass eine Anweisung mit diesem Namen auch existiert. Der Name der neuen Anweisung ist "cmd". Wäre der Compiler bereits vorhanden, so könnte einfach

: cmd
   find // name      --> true cmnd
   drop // true cmnd --> cmnd
;

eingegeben werden. Das Verhalten muss jedoch in "Handarbeit" nachgebildet werden.

Über find werden das Command (cmnd) und true auf dem Stack abgelegt. Weil der Erfolg der Suche bereits feststeht, kann mit drop das Ergebnis der Suche (true) einfach entfernt werden. Jetzt liegt nur noch das ausführbare Command als Objekt auf dem Stack und kann mit compile "hier angehängt" werden. Genau das wird hier gemacht.

"cmd" entry              // : cmd        Der String "cmd" wird ins Wörterbuch eingetragen.
"find" find drop compile //    find      Den String "find" finden, true entfernen, mit compile "hier anhängen".
"drop" find drop compile //    drop      Den String "drop" finden, true entfernen, mit compile "hier anhängen".
bind                     // ;            Mit bind Eintrag im Wörterbuch mit Aufzählung (HERE) verbinden.

Es wurde eine neue Anweisung "in Handarbeit" compiliert. Viel Arbeit, für so eine simple Sache, aber sonst wäre noch viel mehr Arbeit zu verrichten, wie sich im Weiteren zeigen wird.

Aufgabe:

Warum ist hier sowohl der String "drop" als auch das Command drop in einer Zeile vorhanden?

Zeichenkette in Symbol wandeln und compilieren

Eine Zeichenkette (auf dem Stack) soll als Symbol identifiziert und mit compile gleich "hier angehängt" werden. Eigentlich ein Verhalten wie im letzten Abschnitt, nur um einen Test erweitert.

"sym" entry           // : sym
"symbol"  cmd compile //    symbol
"drop"    cmd compile //    drop
"compile" cmd compile //    compile
bind                  // ;

Statt hinter jedem String "find drop" zu schreiben, genügt jetzt die neue Anweisung cmd. Ein kleine Einsparung, aber es wird noch besser.

Zeichenkette in Command wandeln und compilieren

Hier genügt es, die Anweisung "cmd" auszuführen und das Ergebnis mit "compile" zu behandeln.

"cmp" entry           // : cmp
"cmd"     cmd compile //    cmd
"compile" cmd compile //    compile
bind                  // ;

Zeichenkette in Command wandeln und ausführen

Einfach compile durch execute ersetzen.

"exc" entry           // : exc
"cmd"     cmd compile //    cmd
"execute" cmd compile //    execute
bind                  // ;

Die letzte "hilfreiche" Anweisung wurde erstellt. Mit diesen Commands kann jetzt das Flussdiagramm in ein Programm umgesetzt werden.

Aufgabe:

Welche Aufgabe haben die letzten drei Sequenzen?

Eine kurze, klare Beschreibung mit Hinweisen auf mögliches Fehlverhalten ist gefragt.

Umsetzung des Diagramms

Mit den eben erstellten Commands ist es nun möglich jede Befehlszeile eines Programms aus nur zwei Elementen aufzubauen. Das erste Element ist ein String. Er ist entweder der Name einer Anweisung oder er symbolisiert einen Wert (Zahl, Text). Das Zweite Element ist eine der neu definierten Anweisungen.

Jede Zeile eines Programms besteht also aus einem Wort (String) und der Anweisung was dieses Wort aussagt (Command, Symbol). Es ist also immer ein Objekt auf dem Stack welches compiliert oder ausgeführt wird. Die einzelnen Elemente des Flussdiagramms werden nun in dieser Form der Programmierung erstellt und besprochen. Es wird umfangreicher als bisher, aber es lohnt sich. Die hier gezeigten Techniken können in anderen Programmen eingesetzt werden und erweitern die Möglichkeiten der Programmentwicklung erheblich.

Wort lesen und eintragen

Das erste Element "Wort gelesen" aus dem Diagramm ist hier realisiert.

"word"                cmp // Wort
"not"                 cmp // nicht gelesen?
"if"                  exc // "if" ist immediate, also ausführen.
 "\" no identifier. " sym // String-Symbol {" no itentifier }
 "."                  cmp // ausgeben
 "exit"               cmp // compiler verlassen
"endif"               exc // "endif" ist immediate, also ausführen.
"entry"               cmp // gelesenes Wort eintragen

Ungewöhnlich erscheint das String-Symbol "no identifier". Offensichtlich soll mit der Anweisung "sym" ein String compiliert werden. Allerdings muss das compilierte String-Objekt nach der Kompilierung noch als String-Objekt erkannt werden. Es darf also nicht einfach nur eine Zeichenkette (ohne doppelte Hochkommas) vorhanden sein, sondern auch die Eigenschaft, dass dieses Objekt einen String symbolisiert.

Hie erscheint ein syntaktisches Element in unangenehmer Weise. Die virtuelle Maschine V2M erkennt ein String-Symbol an dem doppelten Hochkomma am Anfang. Das Command "word" liefert stets die Zeichen eines Strings ohne doppelte Hochkommas auf dem Stack. Damit nun die Anweisung "symbol" ein Objekt als "stringsymbolisierend" erkennt, muss das erste Zeichen aber ein doppeltes Hochkomma sein. Deshalb wird dieses Zeichen mit '\"' im String erzwungen. Das abschließende doppelte Hochkomma braucht hier nicht beachtet zu werden. Nur so viel: Maßnahmen zur Steigerung der Geschwindigkeit in der virtuellen Maschine. Eine Besprechung der V2M ist hier nicht vorgesehen.

Jedenfalls wird eine Meldung mit genau diesem Inhalt erzeugt, wenn "word" keine Zeichenkette an dieser Stelle findet. Im Flussdiagramm ist diese Meldung als "Nichts da" vorhanden. Im anderen Fall wird mit "entry" die gelesene Zeichenkette (die liegt auf dem Stack) in das Wörterbuch eingetragen.

Kompilierung aller weiteren Eingaben

Der eigentliche Vorgang der Kompilierung beginnt jetzt. Alle Worte, die jetzt gelesen werden sind zu compilieren oder auszuführen. Bis auf zwei Ausnahmen.

1. "//" ist die Einleitung eines Kommentars, der bis zum Ende der Zeile oder Ende der Eingabe reicht.
2. ";" ist der Abschluss der Kompilierung.

Das letzte Wort ist durch eine Regel festgelegt. Es ist das Semikolon ";"; deshalb auch die doppelten Hochkommas, denn ein Wort ist stets ein String. Wieder findet der eben beschrieben Vorgang des Lesens statt. Der Unterschied besteht nur darin, dass eine andere Meldung erscheint, wenn kein Wort vorhanden ist.

"loop"                     exc // Schleifenanfang ausführen
 "word"                    cmp
 "not"                     cmp
 "if"                      exc
 "\" No end of sequence. " sym // im Flussdiagramm: "kein Ende"
 "."                       cmp
  "exit"                   cmp
 "endif"                   exc
 "dup"                     cmp // das Wort wird öfter gebraucht

Jetzt liegt das gelesene Wort doppelt auf dem Stack. Weil alle Tests konsumierend sind, muss das Wort auch dann noch vorhanden sein, wenn der Test fehlschlägt.

Test, ob Kommentar

Ein Kommentar ist ebenfalls eine rein syntaktische Angelegenheit. Aleph hat (leider) "//" als syntaktisches Element eingebaut. Das Command "word" liefert dann die gesamte Zeichenkette bis zum Zeilenende auf dem Stack. Hier kann der Text für die weitere Auswertung (Dokumentation, conditional compiling usw.) herangezogen werden.

"\"//"                    sym // "//"
"swap"                    cmp 
"\"startsWith {String}"   sym // am Wortanfang
"call"                    cmp
"if"                      exc // wenn ja,
 "drop"                   cmp // dann ignorieren
"else"                    exc // sonst ...

Kommentare werden in diesem Compiler nicht berücksichtigt, es geht also bei "else" weiter. Das Flussdiagramm verlangt jetzt eine Prüfung auf das Ende der Kompilierung.

Test, ob Ende der Kompilierung

Ein Semikolon ';' bedeutet das Ende der Kompilierung. Damit muss die Bindung der compilierten Commands an den Eintrag erfolgen und die Schleife verlassen werden.

"dup"                    cmp // Wort könnte auch nicht das Ende bedeuten
"\";"                    sym // ";" wäre das Ende
"="                      cmp // es da wäre
"if"                     exc // wenn Ende?
 "drop"                  cmp // dann entferne das Wort
 "bind"                  cmp //      binde das compilierte
 "exit"                  cmp //      verlass die Schleife
"endif"                  exc

Es könnte aber noch nicht das Ende sein. Dann müssten Anweisungen kompiliert oder ausgeführt werden. Das ist der nächste Punkt im Flussdiagramm.

Aufgabe:

Die Beachtung syntaktischer Elemente ist in den beiden vorangegangenen Sequenzen gegeben. Wie wirken sie sich auf die Kompilierung des Codes aus?

Eine kurze, klare Beschreibung mit Hinweisen auf mögliches Fehlverhalten ist gefragt.

Kompilieren oder ausführen

Ist das Wort im Wortschatz vorhanden, so ergibt sich die Frage nach dem weiteren Vorgehen. Wenn die entsprechende Anweisung "immediate" ist, muss sie ausgeführt werden. Ist das Wort ncht im Dictionary, könnte es etwas völlig anderes sein (eine Zahl?!); um das später noch klären zu können, beginnt diese Sequenz mit "dup".

"dup"                    cmp // könnte unbekannt sein
"find"                   cmp // bekannt
"if"                     exc // wenn ja
 "1"                     sym // dann
 "ndrop"                 cmp // entferne das "Gemerkte"
 "dup"                   cmp // dafür das Command behalten
 "\"immediate"           sym // kann immediate sein
 "swap"                  cmp
 "fetch"                 cmp
 "if"                    exc // wenn ja
  "execute"              cmp // dann ausführen
 "else"                  exc // sonst
  "compile"              cmp //      compilieren
 "endif"                 exc
"else"                   exc // unbekannt, also ...

Es findet praktisch nur eine Unterscheidung zwischen einer auszuführenden und einer zu compilierenden Anweisung statt. Dabei ist "find" der Schlüssel. Nur wenn das Wort nicht gefunden wird, geht es bei "else" weiter; in jedem anderen Fall beginnt Alles ab Schleifenanfang von vorn.

Symbol oder unbekannt

Das gelesene Wort kann jetzt nur noch das Symbol eines Wertes sein. Wenn auch diese Überprüfung fehlschlägt, dann ist es völlig unbekannt.

"dup"                   cmp // könnte unbekannt sein
"symbol"                cmp // symbol?
"if"                    exc // wenn ja
 "1"                    sym // dann 
 "ndrop"                cmp //      entferne das Gemerkte
 "compile"              cmp //      compile symbol
"else"                  exc // sonst
 "\" Command '"         sym //      Mitteilung
 "."                    cmp //      das Wort
 "."                    cmp
 "\"' is unknowm. "     sym //      ist unbekannt.
 "."                    cmp
"endif"                 exc

Das war's. Mehr ist nicht, der Compiler ist fertig. Alles Weitere ist Beiwerk. Außer dem Vergessen der "hilfreichen Anweisungen".

Vergessen, aber gezielt

Die "bind"-Anweisungen beziehen sich stets auf die zuletzt gemachten Einträge. Der Colon-Eintrag hat bis jetzt nicht Ausführbares. Alles was kompiliert wurde ist zwar HERE, aber eben (noch) nicht mit dem ":" verbunden. Vorher müssen aber erst die Anweisungen vergessen, die nur als Hilfe für das Colon-Command erstellt wurden. Erstens sind sie berflüssig, viel wichtiger aber - sie "blockieren" den "bind>-Zugang zum ":". Das Colon muss der letzte Eintag im Dictionary sein, sonst kann keine Bindung erfolgen. Die letzten beiden Zeilen sind

"cmd" cmd forget // vergiss alle Einträge ab cmd
bind             // verbine HERE mit dem Colon

Jetzt steht die ":"-Anweisung zur Erstellung weiterer Commands bereit. Diese Anweisung ist die Grundlage für viele der gezeigten Beispiele. Keinesfalls ist sie als Bedingung oder Vorschrift gedacht. Jeder Anwender kann seine eigenen Sequenzen zur Bereitstellung neuer Commands erstellen.

Aufgabe:

Entwerfen eines "Colon-Compilers" mit geänderter "Namensgebung". Statt des einfachen Colons (:) sollen nun mit

define Name :

die Commands definiert werden.