© Enkel/Shutterstock.com
Wie man seine eigene Programmiersprache baut – Teil 1

Ein Interpreter für einen Lisp-Dialekt


Wenn man tagein, tagaus an Businesssoftware schreibt und mit Fachbereichen diskutiert, hat man zwischendurch vielleicht auch mal Spaß an einer technischen Spielerei. Was könnte man machen? Betriebssysteme habe ich früher geschrieben, warum also nicht etwas anderes, mal eine Sprache bauen? Wer daran wie ich Interesse hat, ist hier richtig: Im Rahmen dieser Artikelserie werde ich zeigen, wie eine neue Programmiersprache entsteht.

So ganz neu ist die Sprache nicht: Sie reiht sich in die lange Reihe von Lisp-Dialekten ein (laut Wikipedia [1] die zweitälteste Programmiersprache). Warum habe ich für meine Experimente Lisp als Basis gewählt? Es ist eine einfache Sprache, mit banal einfacher Syntax. Außerdem ist sie nicht typisiert, so musste ich kein komplexes Typsystem implementieren. Dafür fallen eine Menge Typprüfungen zur Laufzeit an. Ein guter Name ist mir bisher nicht eingefallen, die Sprache heißt daher FPL, für „Functional Programming Language“. Den kompletten Quelltext gibt es übrigens auf GitHub [2] unter der Apache 2.0 License.

Sprachvorstellung

Fangen wir mit der Syntax an: Die „Atome“ von FPL bestehen aus Zahlen (ganze Zahlen und Fließkommazahlen, Syntax wie in Java), Strings (ebenso wie in Java, auch die \-Escapes), Symbolen und runden Klammern. Symbole sind ähnlich zu den Bezeichnern in Java, aber sie dürfen mehr Zeichen enthalten, auch Dinge wie + oder -. Verboten sind nur '"()[]{}:; und das Leerzeichen. Die eckigen/geschweiften Klammern und den Doppelpunkt habe ich nur deswegen auf die schwarze Liste gesetzt, um sie für eventuelle Erweiterungen zu reservieren. Das Semikolon leitet einen Kommentar ein, der bis zum Zeilenende reicht. Doppelte Anführungszeichen werden für Strings benötigt, zu der Bedeutung von ' (Quote) komme ich später.

Aus den Atomen können nun Ausdrücke gebildet werden. Die Regeln dafür sind auch recht einfach: Eine Zahl, ein String oder ein Symbol bilden einen Ausdruck. Die zweite Form eines Ausdrucks ist eine Liste, bestehend aus öffnender Klammer, einer Folge von 0 bis n Ausdrücken, gefolgt von einer schließenden Klammer. Keine Regel ohne Ausnahme: Vor einem Ausdruck kann noch ein einfaches Anführungszeichen stehen (Quote), was seine Auswertung unterdrückt.

Ein Programm besteht schließlich aus einer Folge von Ausdrücken, die der Reihe nach ausgewertet werden. Das war auch schon die komplette Syntax, wechseln wir zur Semantik, die festlegt, wie Ausdrücke ausgewertet werden. Zahlen und Strings verändern sich durch die Auswertung nicht, sie geben sich selbst zurück. Bei der Auswertung eines Symbols wird der Wert des Symbols in der aktuellen Umgebung nachgeschlagen, ähnlich wie Variablenzugriffe in Java.

Die Mächtigkeit der Sprache entsteht durch die Listen: Hier erfolgt die Auswertung in zwei Schritten: Zuerst wird das erste Element der Liste ausgewertet. Das Ergebnis muss eine Funktion sein, alles andere führt zu einer Fehlermeldung. Anschließend wird diese Funktion mit den restlichen Werten als Parametern aufgerufen. Diese Präfixschreibweise fühlt sich erstmal ungewohnt an. Statt 3 + 4 schreibt man in FPL (+ 3 4). Bleibt nur noch der Sonderfall Quote zu erklären: Ein ' vor einem Ausdruck hat zur Folge, dass er ohne Auswertung zurückgeben wird. ' (+ 3 4) wird daher nicht zu 7 ausgewertet, sondern zu einer Liste mit einem Symbol (dem Pluszeichen) und zwei Zahlen. Die Quote-Syntax ist auch von Lisp übernommen, alternativ könnte man auch (quote (+ 3 4)) schreiben.

Mit diesen wenigen Absätzen sind alle wesentlichen Konzepte von FPL beschrieben: Basisdatentypen (Zahl, String), Listen und Funktionen. Die Syntax von Java hätte ein paar Absätze mehr erfordert. Gegenüber einem Java-Parser ist der FPL-Parser daher auch viel einfacher.

Quelltext lesen

Die Beschreibung der Sprache eignet sich hervorragend als Schablone für den Parser und Interpreter. Im ersten Schritt wird der Quelltext mit der Klasse Scanner in Instanzen von Token zerlegt. Instanziiert wird der Scanner mit einem java.io.Reader und einem Namen des Quelltexts (den Namen benötigt man für Fehlermeldungen). Über die Methode next() liefert er das nächste Token, wobei auch das Ende des Quelltextes ein gültiges Token ist. In Listing 1 sieht man den Kern der Klasse Scanner, die Methode next().

Listing 1

public Token next() throws IOException, ParseException { skipComment(); Position position = new Position(name, line, column); if (eof) { return new Token(position, Id.EOF); } else if (ch == '(') { readChar(); return new Token(position, Id.LEFT_PAREN); } else if (ch == ')') { readChar(); return new Token(position, Id.RIGHT_PAREN); } else if (ch == '\'') { readChar(); return new Token(position, Id.QUOTE); } else if (ch == '-' && nextIsNumberCharacter() || ch >= '0' && ch <= '9') { return number(position); } else if (ch == '"') { return string(position); } else if (NON_SYMBOL_CHARS.indexOf(ch) != -1) { throw new ParseException(position, "Illegal character for symbol: " + (char) ch); } else { return symbol(position); } }

Was zeichnet diesen Teil der Implementierung aus? Mittels der Methode skipComment() liest sie zuerst über alle Kommentare (und Whitespace) hinweg. Dann schaut sie sich jeweils ein Zeichen an, durch den sich das Token zu erkennen gibt. Eine Ausnahme bildet das Minuszeichen: Es kann ein Symbol oder eine Zahl einleiten, die Entscheidung fällt erst beim nächsten Zeichen: Ziffer für Zahl, Rest für Symbol. Der Scanner benötigt für seine Arbeit somit zwei Zeichen: das aktuelle und das nächste Zeichen, abgelegt in ch und nextCh. Nach der Verarbeitung eines Zeichens wird mittels readChar() auf das nächste Zeichen der Eingabe weiter geschaltet. readChar() kümmert sich auch darum, dass line und column korrekte Werte enthalten. Daraus – zusammen mit dem Namen der Quelle...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Gewinner-Teams

Wir bieten Lizenz-Lösungen für Teams jeder Größe: Finden Sie heraus, welche Lösung am besten zu Ihnen passt.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang