Zaphod / Narcissus
JavaScript VM in JavaScript

von Philipp Hirch


Seminar Zaphod / Narcissus | Inhaltsverzeichnis | Einleitung | Interpreter | Narcissus | Beispiel | Fazit | Quellenverzeichnis

Narcissus


der Name

Der Name Narcissius bezieht sich auf eine Sage aus der Griechischen Mythologie, in der sich der Sohn des Flussgottes in sein eigenes Spiegelbild verliebte.

Passend dazu, ist Narcissus in JavaScript geschrieben und soll zugleich JavaScript interpretieren.


Aufbau


Zusammenfassung

Narcissus ist ein Meta-circularer Interpreter der speziell an SpiderMonkey 1.8.5 angepasst ist. Ist ECMAScript 5 Kompatibel und versteht auch schon Teile von neuen ECMA Harmony Standard.


SpiderMonkey (benutze Funktionen)

Zur Laufzeit Optimierung benutzt Narcissus einige Erweiterungen von SpiderMonkey. Wobei es sich hauptsächlich um Erweiterungen handelt die inzwischen in den ECMAScript-Standard eingeflossen sind, wie zum Beispiel die Catch-Guards, Konstanten Deklaration oder RegEx-Objekte.

Diese Erweiterungen machten es Anfangs unmöglich, die VM auf andere Engines wie die V8 von Google zu portieren. Da diese Erweiterungen inzwischen Einzug in die anderen Engines gemacht haben, sollte es nun möglich sein. Jedoch sind auch andere Modifikationen vorhanden, die die Portierung erschweren.

So verwendet Narcissus zum überprüfen, ob es sich um eine Native Funktion handelt, die Methode „toSource“ welche den Text „...[native code]...“ zurückgibt. Oder nutzt zum einlesen von Dateien die snarf-Funktion.

SpiderMonkey extensions used:


Module

Der Kern von Narcissus ist in 4 Modulen aufgeteilt.

JsDefs:
beinhaltet defininitionen die von allen Modulen benötigt werden, wie z.B. die Keywords und die dazugehörigen Tokens.

JsLex:
Beinhaltet den Tokenizer( Lexikalischen Scanner), welcher den Input in Tokens aufteilt.

JsParse:
Beinhaltet den Parser der aus den Tokens vom Scanner einen Programmbaum/Syntaxbaum aufbaut.

JsExec:
Beinhaltet die Apply(Anwenden) Funktion, welche den Programmbaum ausführt.


Lex Scanner (Tokenizer)

Der Scanner liest den Input Zeichenweise ein und verfolgt dabei die Strategie des „longest match“. Das bedeutet es wird immer die längste mögliche Zeichenfolge verwendet.

Es kann können keine Regulären Ausdrücke (RegEx) zum Parsen der Tokens verwendet werden, da JavaScript auch RegEx als Datentyp kennt, und es nicht möglich ist, valide RegExe mit einen RegEx zu erkennen.

Durch die strikten Regeln und Konventionen für Bezeichner, ist es jedoch trotzdem möglich, anhand des ersten Zeichens, den Typ zu identifizieren. Eine Ausnahme macht hier jedoch der Punkt-Operator. Hier benötigt man zusätzlich das 2te Zeichen.

Insgesamt unterscheidet der Tokenizer nur zwischen 6 verschiedenen Arten von Token
  1. [a-Z_&][a-Z0-9_&]* → Identifier
  2. [0-9][1-9]*(\.[0-9]+)?([Ee][+-]?[0-9]*)? → Number
  3. “.*“|'.*' → String
  4. /.../ → Regex
  5. +, -, =, ! ,< .. → Operatoren
  6. Die 6te Art sind die Schlüsselwörter, die vom Aufbau her den Identifiern entsprechen, aber als eigene Tokens gespeichert werden. Dafür prüft der Scanner jeden Identifier ob er ein Reserviertes Wort wie FOR, DO … entspricht.


Parser

Beim Parser handelt es sich um eine TopDown-Parser mit einer LL(1)-Grammatik, ein sogenannter Recursive descent parser (RD-Parser).

Der RD-Parser baut den Programmbaum von Oben nach Unten und von Links nach Rechts auf.

Da es sich um eine LL(1)-Grammatik handelt schaut er sich der Parser stets nur ein Token voraus an (lookahead von 1). Dies hat den Vorteil das keine Spezielle Lookup-Tabelle benötigt wird, jedoch hat man dadurch auch keine Informationen über die Rechte-Seite, was die Fehlerbehandlung deutlich erschwert. Deshalb benötigt der Parser, in diesem Fall, 13 Schritte zum erkennen einer Zuweisung.

Die Idee hinter dem RD-Parser ist, das für jedes Nichtterminalsymbol in der Grammatik, eine Prozedur erstellt wird, welche eine Regel abarbeitet.


Apply

In der jsExec.js ist die apply-Funktion definiert. Sie traversiert den Programmbaum und ruft für jeden Knoten die passende Funktion auf.


Funktionalität

Narcissus bedient sich aller Vorteile eines Meta-circular Interpreters. Funktionen und das Global-Objekt werden als eigene primitive Datenstruktur erzeugt. Strings und Arrays werden aus dem Hostsystem ins lokale System gewrappt.

Alle anderen Objekte werden aus dem Hostsystem aufgerufen.


Global-Objekt

Narcissus besitzt zusätzlich zu dem Global-Objekt von SpiderMonkey, noch ein zweites eigenes Global-Objekt.

Wie das JavaScript Global-Objekt besitzt das von Narcissus, alle Funktionen der Umgebung. Zusätzlich besitzt es aber noch eine Verknüpfung zum Global-Objekt vom Host-System, was es möglich macht die Standardfunktionen vom Host-System zu nutzen.

Der Zugriff auf die Funktionen des Host-System, wird mit JavaScript-Proxys realisiert. In den ersten versionen noch mit Statischen Proxys, in den aktuelleren mit den neuen Dynamischen Proxys aus ECMA Harmony.

Bei statischen gibt es stets der Problematik, dass man alle Features die man aus dem Host-System nutzen wollte, vorher einmal definieren musste. Das ist mit den neuen Proxys nicht mehr nötig. Bei einem Aufruf einer Funktion, prüft Narcissus zuerst, ob es eine lokale Funktion ist. Ist dies nicht der Fall, prüft es, ob es im Host-System, die Funktion gibt, und gibt diese dann zurück.


Funktionen

Funktionen werden in Narcissus meta-circular definiert. Dies bedeutet sie werden als eigene primitive Datenstruktur gespeichert.

Die Datenstruktur beinhaltet einen eigenen Programmbaum welcher die Funktion widerspiegelt. Zudem behält er eine Liste mit allen in der Funktion definierten Variablen und Funktionen.

Damit es mit den vorherigen Strukturen zu keinen Konflikte kommt, wird der Aufruf nicht über die internen Funktionsaufrufe, wie call, construct, has … realisiert, sondern über leicht an der Syntax angepasste Funktionen.

Call → __call__
construct → ___construct__
has → __hasInstance__


Wrapping

Beim Wrapping, wird ein natives Objekt, mit einem neuen, lokalen, Objekt verknüpft. Dies wird dadurch geschafft, dass die Objekte gegenseitig als Prototype beziehungsweise als Konstruktor des anderen gesetzt werden.

Durch das Wrapping ist es nicht notwendig, die Funktionalität des nativen Objekts nachzubilden, sondern es kann auf die vorhandene Funktionalität zurückgegriffen werden. Und selbst Anpassungen an den vorhandenen Strukturen können gemacht werden.

Ablauf: Holen des vorhanden Objekts vom Hostsystem
Setzen des User-Objekts als Prototype des Host-Objekts
Ersetzen des Konstruktors des User-Objekts mit dem des Host-Objekts

Beispiel:
function reflectClass(name, proto) {
var gctor = global[name];
Object.defineProperty(gctor, "prototype", { value: proto});
Object.defineProperty(proto, "constructor", { value: gctor});
return proto;
}
reflectClass('Array', new Array);


Native Funktionen

Native Funktionen werden in Narcissus zu Funktionsobjekten gewrappt, so dass sie in der lokalen Umgebung verfügbar sind.

Damit sie sich, in ihrem verhalten, nicht von lokalen Funktionen unterscheiden, bekommen sie eine extra Schicht Prototyping. Die Standard Funktionen wie CALL und APPLY werden von ihren Ersatzfunktionen __CALL__ und __APPLY__ gekapselt.

So unterscheidet sich der Aufruf, von Native Funktionen, nicht mehr von den der „neuen“ lokalen Funktionen.

Aufruf:
funktion.__call__(Parameter);


Seminar Zaphod / Narcissus | Inhaltsverzeichnis | Einleitung | Interpreter | Narcissus | Beispiel | Fazit | Quellenverzeichnis