Implementieren einer Sprache in JavaScript – Teil 1: Grundlagen

Möchte man Sprachen wie bspw. YAML, SQL oder XML in JavaScript interpretieren, existiert eine Vielzahl an Bibliotheken, die hierfür herangezogen werden können. Doch was, wenn dies für eine Sprache noch nicht der Fall ist? Wie wird eine Sprache definiert und wie kann man diese von einer Maschine ausführen lassen?

Im Rahmen dieses zweiteiligen Blog-Beitrages werden diese Fragen anhand der Object Constraint Language (OCL) beispielhaft geklärt. Da die OCL ein sehr breites Funktionsspektrum aufweist, wird nur ein kleiner Teil aufgegriffen. Anhand dieses Ausschnittes werden die grundlegenden Werkzeuge und Begriffe zur Definition einer Sprache vorgestellt und erklärt. Im zweiten Teil des Blog-Beitrages wird dann eine konkrete Implementierung eines Parsers mit Hilfe des Parser-Generators Jison beschrieben.

Die Object Constraint Language (OCL)

Die OCL ist eine Sprache, die maßgeblich im Rahmen der UML Anwendung findet. Sie erlaubt es, textuell definierte Regeln (Constraints) festzulegen, welche die Semantik eines UML-Modells präzisiert. So ist es bspw. mit Hilfe eines UML-Klassendiagramms recht einfach möglich, eine Eltern-Kind-Beziehung zu definieren: eine Klasse Person hat eine zyklische Assoziation auf sich selbst mit dem Namen childOf. Soll nun der Umstand berücksichtigt werden, dass eine Person nicht sein/ihr eigenes Elternteil sein kann, ist es nahezu unmöglich dies nur über Konzepte der UML allein darzustellen. Mit Hilfe der OCL hingegen ist dies ein Kinderspiel und kann über folgende Invariante erreicht werden:

context Person inv:
    self.children->forAll(c | c <> self)

Diese Invariante zeigt an, dass für jedes Element (forAll) der Liste children gelten muss, dass dies nicht auf das Objekt zeigen darf, welches die Liste selbst hält, da sonst eine zyklische Referenz entsteht.

Festlegen der Sprachfeatures

Die OCL erlaubt es also Abfragen auf Objekten auszuführen. Hierzu ist es notwendig, dass über die Felder eines Objekts navigiert werden kann, was durch eine Punktnotation realisiert wird. Es kann also via a.b auf den Wert des Feldes b des Objekts a (in beliebiger Tiefe) zugegriffen werden. Stellt a eine Liste von Objekten dar, wird durch den Aufruf von a.b eine neue Liste mit allen Werten des Feldes b (sofern vorhanden) der Objekte der Liste aus a zurückgegeben. Auch existieren Funktionen, die auf dem Ergebnis einer Abfrage ausgeführt werden können. Hierfür wird der Pfeil-Operator -> eingesetzt, gefolgt vom Namen der Funktion (bspw. forAll, min, max, select, u.v.m).

Folgendes Objekt dient als Beispiel zur Veranschaulichung der oben beschriebenen Abfrageregeln:

{
  field: “value”,
  listField: [
    { value: “a” },
    { value: “b” },
    { value: “c” }
  ],
  objectField: {
    value: “d”
  }
}

Werden die nun folgenden Abfragen (linke Spalte) auf dem obigen Objekt ausgeführt, ergeben sich die in der rechten Spalte angegebenen Ergebnisse:

self.field

self.listField





self.objectField.value

self.listField.value

"value"

[
  { value: "a" },
  { value: "b" },
  { value: "c" }
]

"d"

["a","b","c"]

Formale Definition der Sprache

Kern dieses Blogartikels ist es, die oben skizzierten Features zur Abfrage von Objekten als Sprache zu implementieren. Hierfür ist eine formale Definition der Sprache unerlässlich. Die Definition untergliedert sich in die Bereiche Lexer und Parser, welche folgend näher beschrieben werden.

Lexer

Aufgabe eines Lexers (auch Tokenizer) ist es, den textuell vorliegenden Programmcode in einzelne Teile (sog. Token) zu zerlegen. Hierfür müssen dem Lexer Regeln mitgegeben werden, welche die jeweiligen Token definieren und als solche für den Lexer greifbar gemacht werden. Für die beiden Operatoren . und -> ist dies simpel, da diese statische Konstrukte darstellen und analog unter den Token “.” bzw. “->” abgelegt werden. Auch die runden Klammern des Operationsaufrufs sind feste Konstrukte, die als solche jeweils ein Token darstellen.

Interessanter sind die Zugriffe auf Feld- oder Operationsnamen, da diese variabel sind. Die Namen unterliegen jedoch einem festen Muster und können daher mit Hilfe eines Regulären Ausdrucks erkannt und behandelt werden: [a-zA-Z_][a-zA-Z0-9_]*. Stößt der Lexer auf eine Zeichenkette die diesem Regulären Ausdruck entspricht, wird sie als Token “VARIABLE_NAME” erfasst.
Zudem wird der Lexer so konfiguriert, dass mehrfach auftretende Leer- oder ähnliche Zeichen (Tab, Zeilenumbruch) ignoriert werden. Ein besonderes Token ist das EOF-Token (End-of-File). Dieses wird später dazu verwendet, dem Parser anzuzeigen, dass mit keinem weiteren Ausdruck zu rechnen ist. Für die in diesem Blog-Beitrag vorgestellte Abfragesprache sehen die Lexer-Regeln daher wie folgt aus:

\s+                             { /* skip blanks, new line, etc. */ }
'.'                             { return '.'; }
'->'                            { return '->'; }
'('                             { return '('; }
')'                             { return ')'; }
[a-zA-Z_][a-zA-Z0-9_]*          { return 'VARIABLE_NAME'; }
<<EOF>>                         { return 'EOF'; }

Parser

Konnte der Lexer eine Abfrage in Token zerteilen, wird das Ergebnis an den Parser übergeben, der anhand einer gegebenen Grammatik die Token transformiert. Eine Grammatik lässt sich mathematisch definieren als G = (N,T,P,S), wobei N die Menge nichtterminaler Symbole (hier: e), T die Menge terminaler Symbole (die Token aus den Lexer-Regeln), P die Regeln der Grammatik und S das Startsymbol definiert (hier: e).

Gemäß dieser Vorgabe ergibt sich für die OCL folgende Grammatik:

N = {e}
T = {'.', '->', '(', ')', 'VARIABLE_NAME', 'EOF'}
P = e -> e 'EOF',
    e -> 'VARIABLE_NAME',
    e -> e '.' 'VARIABLE_NAME',
    e -> 'VARIABLE_NAME' '(' ')'
S = e

An dieser Stelle sind sowohl die Lexerregeln als auch die Grammatik definiert, sodass die Sprachdefinition vollständig ist. Der letzte, fehlende Schritt die Sprache ausführbar zu gestalten, ist das Erstellen eines Parsers. Natürlich kann ein Parser grundsätzlich manuell implementiert werden, jedoch zeigt die Erfahrung, dass mit wachsender Komplexität der Sprache auch die Komplexität des Parsers steigt und es sich daher anbietet, einen Parsergenerator zu verwenden. Hierfür wird im zweiten Teil des Blog-Beitrages die konkrete Umsetzung eines Parsers in JavaScript mit Hilfe der Bibliothek Jison vorgenommen.