xscDevBlog – LastSharp & Co.

In diesem Artikel, dem ersten von vielen, geht es um die Entwicklung einer eigenen Script- oder Programmiersprache. Das sei nur für die erwähnt, die sich Angesichts des Vorgeplänkels der nächsten zwei Absätze fragen: “Was wird das denn jetzt?” und dann wieder verschwinden wollen…

Vorspiel

Neben LastSharp und LeSharp, den beiden Tools, die für eine breite Masse gedacht und deshalb auch zumindest ein bisschen nützlich sind, arbeite ich noch an zwei eher theoretischen Projekten: UVD (das im Moment ruht) und Lapicon (Loose API Connection Language).

Letzteres ist eine Scriptsprache zum Senden und Verarbeiten von REST-Requests, also zum Verwenden verschiedenster APIs, z.b. dem von Last.FM. Kein großer Leckerbissen für den Otto-Normal-Benutzer also und auch für Entwickler, die sich mit dem Thema beschäftigen, ist die Sprache nicht der Inbegriff von Eleganz. Deshalb mein Entschluss: Lapicon muss von Grund auf neu entwickelt werden. Das bedeutet: neue Funktionen, mehr Komfort, bessere Performance, usw… Alles in allem keine triviale Aufgabe.

Und dann kam mir die Idee, meinen Versuch zu protokollieren und somit allen, die daran interessiert sind, eine eigene Programmier- oder Scriptsprache zu entwickeln, ein Stückchen weiterzuhelfen. Eine kleine Reise, ein kleines Abenteuer also.

Ein Hinweis

Das Konzept, das hier entwickelt wird, eignet sich für Sprachen, die – so will ich es jetzt aus Ermangelung eines Fachbegriffs mal nennen – “blockbasiert” sind, also so etwa wie Pascal oder VHDL. D.h. man hat (z.B. bei Funktionen) immer einen Start- und einen Endblock, wobei der Endblock überflüssig werden kann, wenn man Sachen wie Zeileneinrückung einbezieht. (Ein Konzept, dass ich, während ich mich in Ruby eingearbeitet habe, bei HAML und SASS kennen- und schätzen gelernt habe.)

Des weiteren werden wir zur Erkennung verschiedener Anweisungen mit Regular Expressions arbeiten, weshalb man sich dort auskennen sollte. Ein Tutorial gibt es z.B. hier (englisch).

Reisevorbereitung

Bevor wir uns überhaupt mit der Sprache selbst beschäftigen, sollten wir folgendes tun:

1. Wir müssen uns überlegen, welche Komponenten wir entwickeln müssen, um Ausdrücke zu erkennen und zu verarbeiten.
   Die Schlagworte hier sind Lexer und Parser. (Ich hatte anfangs ein anderes Konzept vorgesehen, das aber einen Haufen Schwächen hatte, weshalb ich jetzt doch wieder auf das klassische Prinzip zurückkomme. Ich werde mich bemühen, das so gut wie möglich darzustellen…)

   Der Lexer nimmt einen Ausdruck und zerlegt ihn in sog. Token, d.h. in kleine Teile, die einen Typ und einen Wert besitzen. Man nehme beispielsweise den Ausdruck “1+2*sqrt(e)”. Ein Lexer (auch Tokenizer genannt) könnte daraus eine Liste der folgenden Gestalt fabrizieren:

   integer  : 1
   operator : +
   integer  : 2
   operator : *
   id       : sqrt
   open     : (
   id       : e
   close    : )

   Der Parser nimmt nun diese Liste und erstellt daraus einen Syntaxbaum, d.h. eine Repräsentation des Ausdrucks als Baumstruktur. Hier wird vor allem darauf geachtet, dass verschiedene Operatoren verschiedene Prioritäten haben können, dass es Verschachtelungen durch Klammern gibt, etc… Ein Syntaxbaum für unser Beispiel könnte nach dem Parsen z.B. so aussehen:

                  operator : +
                 /            \
           integer : 1     operator : *
                          /            \
                     integer : 2   function : sqrt
                                        |
                                   constant : e

2. Wir müssen festlegen, was die Sprache können soll.
   Welche Datenstrukturen sollen zugänglich sein? Kann man Funktionen definieren? Gibt es arithmetische Operationen? Schleifen? Man sollte sich eine Liste machen. Für unsere Beispielsprache könnte das so aussehen:
   • Es gibt zwei Datentypen: Zahlen und Strings.
   • Es gibt Variablen, die aber nur Zahlen enthalten können.
   • Es gibt eine Ausgabefunktion, die Strings und Zahlen ausgibt.
   • Es gibt eine Ausgabefunktion, die Zeilenumbrüche erzeugt.
   • Es gibt eine Eingabefunktion, die Zahlen einliest und in einer Variablen speichert.
   • Es gibt die arithmetischen Operationen Addition (+), Subtraktion (-), Multiplikation (*), Division (/), die auf ganzen Zahlen arbeiten.
   • Es gibt Klammern, mit denen man die Ausführungsreihenfolge beeinflussen kann.
   • Es gibt eine Schleife, die einen Befehl genau n-mal (n ist gegeben) ausführt.
   • Es gibt drei Funktionen, die jeweils überprüfen, ob eine Zahl größer, kleiner oder gleich 0 ist und bei zutreffendem Ergebnis, einen Fehler ausgeben.

   Was wir also entwickeln werden, ist ein Taschenrechner.

3. Wir müssen uns Gedanken dazu machen, wie der Interpreter aufgebaut ist und arbeitet.
   Wie genau wird unser Programmcode verarbeitet? Wie arbeitet der Interpreter intern?An dieser Stelle wird klar, warum ich mich dafür entschieden habe, eine “blockbasierte” (also mit expliziten Blockanfängen und -enden) Sprache zu entwickeln: es ermöglicht die Ausführung eines Programms Zeile für Zeile. (Zwar wäre es kein unerträglicher Aufwand, auch so etwas wie Klammerstrukturen, ähnlich zu C#, unterstützen zu lassen, aber es geht auch so – und macht außerdem den Quelltext strukturierter, wie man z.B. an Ruby sieht.)

   Das andere Konzept, das den Interpreter zu einem nützlichen Interpreter macht, habe ich bei der Mikroprogrammierung näher kennengelernt. Man hat einen Instruktionszeiger (Instruction Pointer, IP), der auf die aktuelle Instruktion zeigt und einen Stack, der den Wert des Zeigers zwischenspeichern kann. Jede Anweisung sagt dem Interpreter nach ihrer Ausführung, was er nun weiter machen soll. Zyklus:

   1. Hole die Anweisung (Statement), auf die der IP gerade zeigt. Ist keine Anweisung vorhanden, brich ab.
   2. Übergib die Anweisung an den Verarbeiter (Processor) und speichere das Ergebnis.
   3. Lies aus dem Ergebnis die folgenden Teile aus: Zeiger-Offset, Zeiger-Aktion und Stack-Aktion.
   4. Wenn die Stack-Aktion “PUSH” ist, lege den IP auf den Stack.
   5. Wenn die Zeiger-Aktion “NULL” ist, setze den IP auf 0, ist sie “STACK”, setze den IP auf die Position, die zuoberst auf dem Stack liegt. Bei “CONTINUE” erhöhe den IP um 1.
   6. Wenn die Stack-Aktion “POP” ist, nimm das oberste Element vom Stack.
   7. Addiere den Zeiger-Offset auf den Instruktionszeiger.
   8. Gehe zu 1.

   Beispiel: Schleife, die mindestens einmal ausgeführt wird
   (Notation: Zeiger-Offset, Zeiger-Aktion, Stack-Aktion)

   Schleifenbeginn: 0 / CONTINUE / PUSH
   Schleifenrumpf: beliebig
   Schleifenbedingung erfüllt: 1 / STACK / NONE
   Schleifenbedingung nicht erfüllt: 0 / CONTINUE / POP

   Beispiel 2: Funktionsaufruf

   Aufruf: <Adresse+1> / NULL / PUSH
   Rumpf: beliebig
   Rücksprung: 1 / STACK / POP

   Der Processor ist das, wo die eigentliche Ausführung  eines Befehls stattfindet. Er tut folgendes:

   1. Erstelle mithilfe von Lexer und Parser (siehe oben) den Syntaxbaum des Befehls.
   2. Wenn der Baum Kindknoten hat, werte zuerst die jeweiligen Teilbäume aus. (Top-Down-Methode)
   3. Schaue, ob für den Typ des Wurzelknotens eine Verarbeitungsroutine (Evaluator) existiert. Wenn ja, rufe sie mit den in 2. ermittelten Daten auf und gib ihr Ergebnis zurück, wenn nicht, gib eine Fehlermeldung aus und brich die Gesamtausführung ab.
4. Und wie werden die programminternen Daten gespeichert?
   Wir benötigen eine Umgebung, in der ein Programm läuft. Diese Umgebung hat vor allem die Aufgabe, Variablen, Objekte, Funktionen, Listen, Arrays, etc… zu verwalten, also eine große Menge an Daten zu speichern und zugreifbar zu machen. Wenn man von vornherein weiß, was auf einen zukommt (wenn man also einen Interpreter für eine ganz bestimmte und ganz genau definierte Sprache schreibt), kann man es sich einfach machen:
   • einen Speicher für Variablen,
   • einen Speicher für Funktionen,
   • einen Speicher für Listen,
   • …

   Die Realisierung als Hashtabelle (Wörterbuch, Dictionary) würde sich für jeden einzelnen dieser Speicher anbieten. Eine Hashtabelle ist eine Liste von Schlüssel-Wert-Paaren, wo jeder Wert schnell über seinen Schlüssel adressiert werden kann – in obigem Fall wären folgende Zuordnungen sinnvoll:

   • [Variablenname => Variablenwert]
   • [Funktionsname => (Funktionsbeginn (Zeiger), Funktionsende (Zeiger))]
   • [Listenname => Liste]
   • …

   In meinem Studium wird mir beigebracht, alles so abstrakt wie möglich zu halten, weswegen ich die nun folgende Lösung vorschlage. Hierbei benötigen wir nur zwei Hashtabellen (plus eine geschachtelte) und haben zum einen den Vorteil, dass wir beliebige Daten speichern können, zum anderen, dass die Überprüfung auf doppelte Bezeichner (Variablen-, Funktions- und Listennamen sollten ja nur einmal vorkommen!) sehr einfach wird:

   • Wir verwenden eine Tabelle, um jedem Bezeichner einen Typ zuzuweisen. ([Bezeichner => Typ])
   • Wir verwenden eine weitere Tabelle, um jedem Typ eine weitere Hashtabelle zuzuweisen, die wiederum jeden Bezeichner mit seinem Wert verknüpft. ([Typ => [Bezeichner => Wert]])

   Mit entsprechenden Operationen auf diesen beiden Tabellen haben wir nun unsere Umgebung (Environment).

Nachdem wir das alles beantwortet haben, können wir loslegen. Aber Halt! Einen wichtigen Punkt haben wir noch nicht angesprochen: Wie verwende ich Regular Expressions so, dass ich zum einen leicht feststellen kann, welchen Anweisungstyp ich vor mir habe, und zum anderen einfach an die gewünschten Daten komme?

Das ist der Punkt, an dem wir unsere praktische Arbeit beginnen werden.

Inhalt

1. Einführung: Ein Abenteuer in Teilen
2. Der Lexer
3. Grundlagen des Parsens
4. Syntax