xscDevBlog – LastSharp & Co.

Die Aufgabe, die ich mir hier gestellt habe, eine eigene Script- oder Programmiersprache zu entwickeln, bringt so ihre Probleme mit sich. Wie und wo fange ich an? Ist das nicht zu viel für mich? Und sollte ich nicht auf bereits vorhandene Bibliotheken zurückgreifen, anstatt alles von Grund auf neu zu entwickeln?

Vor allem die letzte Frage kann einem zu schaffen machen. Warum etwas möglicherweise nicht gut funktionierendes entwickeln, wenn es doch überall schon tausendfach durchdachte Lösungen gibt? Immerhin lautet doch eine der obersten Regeln in der Softwareentwicklung:

Don’t reinvent the wheel!

Nun, ich bin Informatikstudent. Ich will wissen, wie die Dinge “unter der Haube” aussehen, ich will lernen. Und wenn alle nur noch auf vorgefertige Bibliotheken zurückgreifen, weiß doch bald keiner mehr, was dem Zauber eigentlich zugrunde liegt… Dementsprechend:

Don’t reinvent the wheel, unless you plan on learning more about wheels!

Diese Anleitung soll jedem helfen, der interessiert daran ist, was im Inneren eines Interpreters oder Compilers eigentlich (ungefähr so) abläuft. Ich selbst habe gerade erst das zweite Semester hinter mir, d.h. allzu theoretisch wird es hier nicht und jeder mit ein wenig logischem Denken und genug Engagement sollte es hinbekommen, meinen Ausführungen zu folgen.

Lasset uns beginnen.

Der Lexer

Ein lexikalischer Scanner (kurz: Lexer) ist eine “Maschine”, die eine Zeichenfolge als Eingabe erhält und diese in kleinere Teile spaltet, denen eine bestimmte Bedeutung/ein bestimmter Typ zugrunde liegt.

Ein Taschenrechner, beispielsweise, kennt Zahlen, Operatoren und Klammern. Gibt man dem Lexer dieses Taschenrechners nun die Folge “1+2*(4-3)” zur Verarbeitung, wird daraus die folgende (oder eine ähnliche) Liste:

zahl        :    1
operator    :    +
zahl        :    2
operator    :    *
open        :    (
zahl        :    4
operator    :    -
zahl        :    3
close       :    )

Die einzelnen Zeilen nennt man Tokens. Sie bestehen aus einem Typ (“zahl”, “operator”, …) und einem Wert (“1″, “+”, …) und kapseln somit alle Informationen, die man benötigt, um damit weiterzuarbeiten.

Wichtig ist folgendes: der Lexer überprüft nicht den “Sinn” der Eingabe, d.h. auch ein nicht wohlgeformter Ausdruck wie “1+)(*2″ würde von ihm brav und folgsam in eine Liste von Tokens umgewandelt werden. Die semantische Überprüfung erfolgt an anderer Stelle: dem Parser.

Prinzip

Wie schreibe ich einen Lexer? Das ist keine allzu schwere Sache, die Frage ist nur, wie effizient er letztlich ist. Ich werde hier verschiedene Ansätze darstellen, die jeweils Vor- und Nachteile haben.

Ansatz 1: Reguläre Ausdrücke auf den Anfang der Eingabesequenz anwenden
(~ nicht naiv, aber auch nicht so der Hammer)

• Der Lexer verwaltet eine Reihe von Datentypen, die durch reguläre Ausdrücke (Testen kann man z.B. hier) eindeutig definiert sind. Also z.B.:

  zahl   =>    [0-9]+
  id     =>    [a-zA-Z]+
  open   =>    \(
  close  =>    \)
  comma  =>    ,
  op     =>    [+\-]
  ...

• Auf Basis dieser Typen erfolgt nun die Umwandlung einer Eingabezeichenfolge in Tokens:
  • Erstelle eine leere Ausgabeliste.
  • Während die Zeichenfolge nicht leer ist:
    1. Vergleiche den Anfang der Zeichenfolge mit den regulären Ausdrücken aller verfügbaren Datentypen, bis du einen Treffer landest.
    2. Kein Treffer: Die Zeichenfolge enthält einen unbekannten Datentyp!
    3. Ansonsten:
       • Schneide den gefundenen Ausdruck von der Eingabezeichenfolge ab.
       • Erstelle ein Token des gefundenen Typs und hänge es an die Ausgabeliste an.
    4. Gib die Ausgabeliste aus.
• Ein Token enthält (wie bereits erwähnt) den Typ und Wert eines Ausdrucks. Des weiteren könnte es sich anbieten, auch jeweils Verweise zum vorhergehenden und nachfolgenden Token bereitzustellen, die ja Einfluss auf den realen Typ eines Tokens haben können.
  (Ein Plus benötigt z.B. normalerweise zwei Parameter, wenn aber vor dem Plus ein anderer Operator und danach eine Zahl steht, ist diese Zahl der einzige Parameter und das Plus ist ein Vorzeichen. Die Methode, die solche Sachen überprüft, sollte in der Implementierung der Datentypen auftauchen!)

Der Vorteil dieser Methode ist die Erweiterbarkeit. Wenn man einen neuen Typen hinzufügen will, erstellt man einfach den dazugehörigen Ausdruck. Den Rest übernimmt der Lexer.

Ein gewaltiger Nachteil ist die Zuverlässigkeit: oft gibt es Mehrdeutigkeiten bei regulären Ausdrücken und der Lexer weiß nicht, welcher gerade der richtige ist. Außerdem lässt die Geschwindigkeit zu wünschen übrig: Im schlimmsten Fall (die gesamte Eingabe besteht aus n Tokens des gleichen Typs und dieser Typ ist der letzte, der überpürft wird) beträgt  bei einer Gesamtzahl von m Datentypen die Laufzeit: O(n*m*O(regulärer Ausdruck)) also vermutlich irgendetwas im Bereich O(m*n²)

Ansatz 2: Spezialisierung auf bekannte Eingabetypen
(~ naiver Ansatz)

Wenn man den Lexer nicht für beliebige Datentypen und -formate ausrichtet, sondern von vornherein weiß, wie viele es davon gibt und wie sie aussehen, kann man die Realisierung einfacher/verständlicher machen:

1. Initialisiere einen Zähler i mit 0 und eine leere Liste für die Ausgabe.
2. Während i kleiner ist als die Länge der Eingabe:
   • Überprüfe das i-te Zeichen.
   • Wenn es eine Zahl ist, erhöhe i so lange um eins, bis das i-te Zeichen keine Zahl mehr ist und erstelle aus den dabei “überstrichenen” Zeichen ein Token des Typs “integer”. (Erstellt Token für Zahlen.)
   • Wenn es ein Buchstabe ist, erhöhe i so lange um eins, bis das i-te Zeichen weder Zahl noch Buchstabe ist und erstelle aus den dabei überstrichenen Zeichen ein Token des Typs “identifier”. (Erstellt Token für Variablen)
   • Wenn es ein Anführungszeichen ist, erhöhe i so lange um eins, bis das i-te Zeichen ebenfalls ein Anführungszeichen und das (i-1)-te Zeichen kein Backslash ist [...] (Erstellt Token für Strings)
   • usw…
   • Hänge das erstellte Token an die Ausgabeliste an.
3. Gib die Ausgabeliste aus.

Der Vorteil ist ganz klar die Geschwindigkeit: Jedes Zeichen der Eingabesequenz wird höchstens zweimal überprüft, d.h. die Laufzeit liegt in O(n).

Nachteile sind hier die umständliche Erweiterbarkeit, sowie der meist aufgeblähte Code.

Ansatz 3: Endlicher Automat
(~ professionell und kompliziert (?))

Ansatz 2 war schon nichts anderes als die prinzipielle Funktionsweise eines endlichen Automaten: Ausgehend von einem aktuellen Zustand (z.B. “Kein Zeichen überprüft”, “Stringbeginn entdeckt”) und einer Eingabe (z.B. das nächste Zeichen) geht der Automat in einen neuen Zustand (z.B. “Unerlaubtes Zeichen”, “Stringinhalt”) über. Wenn irgendwann ein Ausgabezustand erreicht wird, erhält man das gerade gelesene Token.

Wenn wir beispielsweise nur die Schlüsselwörter “echo” und “echtheit” hätten, ergäbe sich folgender Automat. (Startsymbol: S, Endsymbol E):

                                         "echo" -----> E("echo")
    e          c           h          o /
S -----> "e" -----> "ec" -----> "ech"
                                      t \         h              e
                                         "echt" -----> "echth" -----> ... -----> E("echtheit")

Wenn ein Zustandsübergang nicht möglich ist, hat man es mit einer unerlaubten Sequenz zu tun. Ein detaillierteres Beispiel zur Modellierung eines endlichen Automaten findet man hier.

Das besondere an endlichen Automaten ist, dass jeder reguläre Ausdruck in so einen Automaten verwandelt werden kann. Eine detaillierte Beschreibung für Interessierte gibt es hier (Uni Bremen).

Vor- und Nachteile entsprechen Ansatz 2, die Laufzeit beträgt ebenfalls O(n). Endliche Automaten werden von fast allen Lexer-/Parser-Generatoren (auf Basis einer Grammatik) erstellt, sind also der meistverbreitete Ansatz zum Erstellen eines Lexers.

Ansatz 4: “Akzeptanztest” auf Basis vieler kleiner Typ-Automaten
( ~ Symbiose von Ansatz 1 und 3)

Ich stand also nun vor dem Problem, zwischen Effizienz und Erweiterbarkeit abzuwägen – genauer gesagt: mich für eines von beiden entscheiden zu müssen – und das passte mir nicht wirklich. Also, zur Ablenkung mal weg vom Schreibblock und Computer, zum Lidl einkaufen und Flaschen zurückbringen. Was man halt so tut.

Und da war er: ein Pfandflaschen-Rückgabe-Automat, der nichts anderes tat, als tagein, tagaus Flaschen anzunehmen und zu überprüfen. Passte die Flasche, gab es einen Zettel, der bares Geld wert war, passte sie nicht, eine Fehlermeldung.

Warum erzähle ich das? Nun, dieser Automat war die Lösung für mein Problem!
Man braucht viele kleine, auf einen bestimmten Typ (von Token, von Flaschen, …) spezialisierte Automaten, die anhand der bereits zuvor eingegebenen Daten (gelesene Zeichen, akzeptierte Flaschen, …) sagen, ob sie eine Eingabe (das nächste Zeichen, die nächste Flasche, …) akzeptieren. Oder eben nicht.

Das Beispiel aus Ansatz 3  würde hierbei so realisiert: Sowohl der “echo”-Automat, als auch der “echtheit”-Automat würden die Eingaben “e”, “c” und “h” (in dieser Reihenfolge) akzeptieren, aber wenn nun ein “o” kommt, wird sich der “echtheit”-Automat aufregen. Für die weitere Überprüfung kann er also ignoriert werden. Und erst wenn auch der “echo”-Automat nicht mehr weitermachen will (also nach besagtem “o”), hat man sein Token gefunden und kann es über die Ausgabefunktion des Automaten auslesen.

Allgemein: Man habe eine Menge A von Typ-Automaten und eine Eingabesequenz <s₀, s₁, s₂, s₃, …, s_n>

1. Versetze alle Automaten in A in ihren Ausgangszustand. (Reset)
2. Finde alle Automaten in A, die s₀ akzeptieren und bilde aus ihnen die Menge A₀
3. Initialisiere i mit 0. Während 0 <= i < n:
   • Wenn |A_i| = 0: brich Schleife ab.
   • Ansonsten: Finde alle Automaten in A_i, die s_i+1 akzeptieren und bilde aus ihnen die Menge A_i+1
   • Erhöhe i um 1.
4. Wenn i=0: Ungültiger Ausdruck.
5. Ansonsten: Finde einen  passenden Typ aus A_i-1 bis A₀, der sich in einem Ausgabezustand befindet (der Index der entsprechenden Automatenmenge sei j), und erstelle ein Token mit dem Wert <s₀, s₁,…, s_j> und dem gefundenen Typen.
6. Fahre mit der restlichen Eingabesequenz fort.

Betrachten wir die Laufzeit: Schritt 1 liegt in O(|A|), Schritt 2 ebenfalls. Schritt 3 benötigt im schlimmsten Fall (die Zeichenfolge wird von allen Automaten komplett akzeptiert) eine Laufzeit von O(n*|A|). Schritt 5 kann ebenfalls eine Laufzeit in O(n*|A|) erreichen, wenn kein einziger Automat in einem Ausgabezustand ist, die restlichen Schritte haben einen konstanten Zeitbedarf O(1).

Diese Methode ermittelt also den nächsten Token mit einer Laufzeit von O((2n+2)*|A|+1), also O(n*|A|). Gleichzeitig ist Erweiterbarkeit gewährleistet, da die Typ-Automaten sehr leicht zu implementieren sind und der Lexer sie nicht von vornherein kennen muss.

Zuverlässigkeit ist nur in Schritt 5 fraglich: Was ist der “passende Typ” zu einem Token? Hier könnte man ein hierarchisches System einführen, das z.B. festlegt: “Wenn die Wahl zwischen dem Typ Funktion und dem Typ Bezeichner getroffen werden muss, nimm die Funktion!”

Die Funktion eines Integer-Automats, die überprüft, ob ein Zeichen akzeptiert wird, könnte z.B. so aussehen:

public bool Accept(char c)
{
    switch (char)
    {
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
            return true;
        default:
            return false;
    }
}

Damit kann man leben, oder? Schwieriger wird es erst bei solchen Sachen wie Strings, wo z.B. beachtet werden muss, dass ein gültiges Zeichen, das nach dem Schließen des Strings kommt, natürlich nicht mehr akzeptiert werden darf. (Man müsste also im Automaten selbst weitere Zustandsdaten, z.B. einen boolschen Wert stringClosed oder so, speichern.)

Fazit

Um eine größtmögliche Erweiterbarkeit zu gewährleisten und weil ich stolz auf die Idee bin und überprüfen will, wie sie sich umsetzen lässt, werden wir Ansatz 4 implementieren. Ich frage mich allerdings, was “Pfandflaschenalgorithmus” auf Englisch heißt…

Update (30.08.2009):
Eine bessere Analogie für den Algorithmus wäre statt dem Pfandflaschenautomaten wohl ein Rennen oder ein Wettbewerb: derjenige, der am weitesten kommt (“die meisten Eingaben akzeptiert), ist der Sieger – außer er bricht dann zusammen, fängt an zu heulen, etc… (“außer er befindet sich nicht in einem Ausgabezustand”) In dem Fall gewinnt der zweite Platz (der aber identisch mit dem ersten sein kann), außer auch dieser kommt mit dem Druck nicht klar. Und so weiter.

Implementierung

Bei der Implementierung des Lexers sollten gleich alle verfügbaren Datentypen (Operator, Trennzeichen, Terminalausdruck, …) in eigenen Klassen gekapselt werden. Das macht die spätere Verwendung einfacher.

Zwei Sachen sollten hier näher erläutert werden. Zuerst die Methode signification der Klasse SyntaxType: sie ermittelt anhand eines konkreten Tokens den “wirklichen Typ” dieses Tokens. Man könnte z.B. einen Grundtyp Identifier definieren (als Unterklasse von Terminal), der alle Buchstabenfolgen (keine Zahlen, keine Sonderzeichen) repräsentiert. Die signification-Methode könnte dann ermitteln ob der Identifier eine Variable, ein Listenname, eine Konstante, etc… ist und dies zurückliefern. Oder eben oben genanntes Beispiel mit dem Pluszeichen, das abhängig vom Kontext ein Operator oder ein Vorzeichen sein kann.

Zweitens das Interface IStateMachine: Es kapselt die für Ansatz 4 (s.o.) benötigten Operationen. (Die Methode IsOutputState fehlt, sollte aber nicht vergessen werden!)

Update (12.08.2009):
Datentypen, die spezielle, angepasste Methoden signification benötigen, müssen als Unterklassen der jeweiligen Typen (hauptsächlich Terminal vermutlich) definiert werden und die Methoden überschreiben. Nur, falls das noch nicht klar war.

Gesamtfazit

Nun kommen wir leicht an die einzelnen Bestandteile eines Ausdrucks, aber uns fehlen noch die Mittel, damit richtig umzugehen. Der nächste Schritt ist es also, Regeln für unsere verschiedenen Ausdrücke zu erstellen (Welche Art von Parametern benötigt eine Funktion/ein Operator/ein Pattern? Darf eine Funktion verschachtelt ausgeführt werden? Etc…) und anhand dieser Regeln einen gegebenen Ausdruck zu überprüfen und in eine einfach weiterzuverarbeitende Form zu bringen.

Hier kommt der sog. Syntaxbaum ins Spiel. Und der Parser, der ihn erstellt.

Inhalt

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