Andreas Rozek
[ Impressum ]   [ Datenschutzerklärung ]   [ Kontakt ]   [ ]

PEG.js

PEG.js

Von David Majda stammt der bekannte Parser-Generator PEG.js, der inzwischen von Futago-za Ryuu weitergeführt wird. Der Generator kann auch ohne eine vorherige Installation rein online betrieben werden.

In der Vorlesung "Grundlagen der Informatik" an der Hochschule für Technik in Stuttgart können sich Studenten mithilfe von PEG.js aktiv mit der Syntax (nicht nur) von Programmiersprachen sowie den notwendigen Schritten bei der Analyse und Verarbeitung von Texten vertraut machen.

XML-Konverter nach JSON

In einem ersten Schritt wird eine ggb. XML-Datei analysiert und in eine äquivalente JSON-Datei umgewandelt.

vereinfachte XML-Grammatik für PEG.js

Um in der wenigen zur Verfügung stehenden Zeit als Lehrbeispiel dienen zu können, deckt die verwendete Grammatik nur die wichtigsten Aspekte von XML ab.

EBNF-Version für Syntax-Diagramme

Syntax-Diagramme sind (vor allem für Einsteiger) bisweilen einfacher verständlich als eine abstrakte (E)BNF- oder PEG-Notation.

Der bekannte Railroad Diagram Generator erzeugt für eine (in einer BNF-artigen Notation) gegebene Grammatik die zugehörigen Syntax-Diagramme.

Konverter-Definition für PEG.js

Mit entsprechenden JavaScript-Anweisungen dekoriert, wird aus der reinen XML-Grammatik für PEG.js ein Konverter, der aus einer gegebenen XML-Datei das zugehörige JSON-Äquivalent erzeugt.

Als Beispiel-Datei dient ein Beitrag für einen fingierten Blog

PEG.js als Script-Interpreter

Ein Datei-Konverter ist ja schon ganz praktisch, aber eigentlich dürstet es einen Informatik-Studenten nach einer eigenen Programmiersprache.

Dank PEG.js ist der Aufwand dafür selbst für einen Anfänger sehr überschaubar:

  1. sobald man eine Vorstellung davon hat, wie die Sprache aussehen und was sie können soll,
  2. erstellt man zweckmäßigerweise erst einmal ein paar theoretische Beispiele (die möglichst alle syntaktischen Aspekte der Sprache abdecken).
  3. Als nächstes definiert man die Syntax der Programmiersprache und
  4. testet sie anhand der zuvor entwickelten Beispiele. Diese Tests sollten durchaus sorgfältig durchgeführt werden, weil spätere Änderungen schnell sehr aufwändig werden können)
  5. Sobald die reine Grammatik funktioniert, kann man sie mit JavaScript-Anweisungen dekorieren, die einen "abstract syntax tree" (AST) erzeugen - möglichst in einer Form, die in der PEG.js-Ausgabe gut kontrolliert werden kann.
  6. Auch diese Grammatik sollte wieder getestet werden - diesmal allerdings anhand von Beispielen, die später auch ausgeführt werden können (also einen semantischen Sinn beinhalten)
  7. Zu guter Letzt wird die Ausgabe der primären Regel (d.h. der Regel für das gesamte Skript) dahingehend geändert, dass der AST nicht ausgegeben, sondern interpretiert wird.

Et voilà, Sie haben eine eigene Skriptsprache spezifiziert und implementiert!

slang - die "simple language"

Als Beispiel diene "slang", eine sehr einfache Skript-Sprache, die vor allem zur Demonstration der grundlegenden Mechanismen eines Interpreters (und weniger für einen praktischen Einsatz) gedacht ist.

Datentypen

slang kennt nur die folgenden Datentypen

  • nil - repräsentiert "nichts", also einen nicht definierten Wert (JavaScript undefined)
  • logische Werte ('true' und 'false')
  • numerische Werte (Gleitkommazahlen im doppelt-genauen IEEE 754 Format)
  • Zeichenketten
  • Funktionen und Blöcke
  • "native" Funktionen (JavaScript)

Insbesondere kennt slang keinerlei Datenstrukturen (dadurch wird die Grammatik etwas einfacher)

Funktionen und Blöcke sind "first-class values", können also an Variablen zugewiesen und als Argumente für Funktionsaufrufe verwendet werden

Literale

Werte der o.g. Datentypen werden wie folgt im Programmtext definiert

  • nil
  • true oder false
  • Zahlen
    • im Binär-Format (nur für vorzeichenlose ganze Zahlen) mit vorangestelltem 0b (also z.B. 0b01101100) mit bis zu 32 Ziffern/Bits
    • im Hexadezimal-Format (nur für vorzeichenlose ganze Zahlen) mit vorangestelltem 0x (also z.B. 0x0123AFFE) mit bis zu 8 Ziffern (32 Bits)
    • als Dezimalzahl mit opt. Vorzeichen, Vor- und Nachkommastellen und Exponenten
  • Zeichenketten
    • einzeilig in einfachen oder doppelten Hochkommata ('...' oder "...")
    • mehrzeilig in einfachen oder doppelten Hochkommata ('''...''' oder """...""")
    • mit Unterstützung der (unter JavaScript) üblichen Escape-Sequenzen (\b, \f, \n, \r, \t, \v, \0, \', \", \\ sowie \x## und \u####)
  • Blöcke {...}
  • Lambdas (Skript-Funktionen) (...) => {...}
  • native Funktionen native (...) => string

Bezeichner

"Bezeichner" sind die Namen von Kontext-Einträgen, also globalen, lokalen oder lexikalischen Variablen und Funktionen.

Sie beginnen mit einem der Buchstaben a-z bzw. A-Z oder einem der beiden Zeichen $ bzw. _, optional gefolgt von einem oder mehreren weiteren Buchstaben, $ oder _ bzw. dezimalen Ziffern (0-9).

Variablen und Funktionen dürfen aber nicht wie ein reserviertes Wort heißen. Reservierte Worte sind global, local, it, native, nil, true, false, nan, e, pi, div, mod, and, or, not, if, then, else, select, when, otherwise, for, from, down, to, by, repeat, while, until, continue, break und return

Die Groß-/Kleinschreibung der Bezeichner ist signifikant.

Kontexte

Kontexte fassen Werte und Funktionen zusammen, so dass diese aus Funktionen und Blöcken heraus anhand ihres Namens angesprochen werden können.

Es gibt "äußere", "innere" und "lexikalische" Kontexte.

Der äußerste Kontext ist der "globale Kontext" mit allen globalen Werten und Funktionen.

Wenn eine Funktion gestartet wird, erzeugt sie einen "inneren" Kontext für Aufrufparameter und lokale Variablen. Beim Lesen werden Kontext-Einträge zuerst lokal und anschließend global gesucht. Beim Schreiben werden Einträge stets nur im lokalen Kontext gesucht (und dort ggfs. neu angelegt)

Wenn ein Block gestartet wird, erzeugt dieser ebenfalls einen lokalen Kontext, diesmal allerdings im "lexikalischen" Kontext der Stelle, an der er definiert wurde. Beim Lesen werden Kontext-Einträge deshalb zunächst im lokalen, anschließend (ggfs. rekursiv) in den zugehörigen lexikalischen Kontexten und am Ende auch im globalen Kontext gesucht. Beim Schreiben werden Einträge ebenfalls im lokalen und in den lexikalischen Kontexten gesucht - niemals aber im globalen Kontext. Gefundene Einträge werden dort geändert, wo sie gefunden wurden, nicht gefundene Einträge werden lokal angelegt.

Blöcke

Blöcke beinhalten Abfolgen von Anweisungen, die im Programmtext auf Wunsch durch ein oder mehrere Semikola voneinander getrennt werden können (aber nicht müssen)

Allein stehende Ausdrücke gelten ebenfalls als Anweisung.

Jede ausgeführte Anweisung liefert ein Ergebnis, dieses wird in der lokalen Variable it gespeichert.

Das Ergebnis eines Blockes ist das Ergebnis der letzten ausgeführten Anweisung.

Lambdas (Skript-Funktionen)

Lambdas sind (anonyme) Funktionen mit 0, 1 oder mehr "Parametern". Definiert werden sie durch Ausdrücke der Form

  • () => {...} für parameterlose Lambdas,
  • (parameter) => {...} für Lambdas mit einem Parameter,
  • (parameter, parameter, ...) => {...} für Lambdas mit mehreren Parametern

Die Parameter stehen innerhalb der Funktion als lokale Variablen zur Verfügung und werden zu Beginn mit den Werten der beim Aufruf übergebenen Argumente vorbelegt.

Lambdas können sofort aufgerufen, als Argumente an andere Funktionen übergeben oder einer Variablen zugewiesen werden.

Das Ergebnis einer Funktion ist

  • das Ergebnis der letzten Anweisung im Funktionsblock oder
  • das Ergebnis einer return-Anweisung
Nota bene: derzeit wird noch nicht abgesichert, dass alle Parameter unterschiedliche Namen tragen

Native Funktionen

"Native Funktionen" sind in JavaScript programmierte und von slang aus aufrufbare Funktionen und dienen der Erweiterung der Skript-Sprache. Definiert werden sie durch Ausdrücke der Form

  • native () => string für parameterlose Funktionen,
  • native (parameter) => string für Funktionen mit einem Parameter,
  • native (parameter, parameter, ...) => string für Funktionen mit mehreren Parametern

Der Quelltext der nativen Funktion wird (innerhalb von slang) als ein- oder mehrzeiliger slang-String vorgegeben.

Die Parameter der JavaScript-Funktion tragen die bei der Definition festgelegten Namen; der lexikalische Kontext, in dem die native Funkton aufgerufen wurde, steht als "this"-Objekt zur Verfügung.

Ausdrücke und Operatoren

Ausdrücke bestehen aus

  • Zuweisungen,
  • Operator-Verknüpfungen,
  • Aufrufen,
  • Literalen, Variablen, Klammerungen oder
  • Lambdas bzw. nativen Funktionen

slang unterstützt die folgenden Operatoren (mit abnehmendem Vorrang)

  • (...) (Klammerung)
  • ^ (Potenzierung)
  • *, /, div (Ganzzahl-Division), mod (Modulo-Division)
  • +, -
  • <, <=, =, >=, > und <> (ungleich)
  • not (logische Negation)
  • or (logische Disjunkton)
  • and (logische Konjunktion)
  • := (Zuweisung)

Die "Punkt-vor-Strich"-Konvention (PEMDAS) wird berücksichtigt.

Die meisten Operatoren sind "links-assoziativ", nur Zuweisungen, Potenzierungen und die logische Negation werden "rechts-assoziativ" ausgewertet.

Zuweisungen

Zuweisungen ändern den Wert eines bestehenden Kontext-Eintrages (meist einer Variablen) oder legen diesen an.

Eine "generische Zuweisung" hat die Form

identifier := expression

und ändert einen bestehenden Eintrag im lokalen oder lexikalischen Kontext bzw. legt einen neuen Eintrag im lokalen Kontext an.

Eine "lokale Zuweisung" hat die Form

local identifier := expression

und schreibt stets einen Eintrag im lokalen Kontext.

Eine "globale Zuweisung" hat die Form

global identifier := expression

und schreibt einen Eintrag im globalen Kontext. Globale Zuweisungen sind die einzige Möglichkeit, Einträge im globalen Kontext anzulegen oder zu ändern.

Auch Zuweisungen liefern ein Ergebnis (und können somit in Ausdrücken verwendet werden), und zwar den Wert, der zugewiesen wurde.

Steueranweisungen

Zur Steuerung des Programmflusses stehen folgende Anweisungen zur Verfügung:

  • if (...) then {...}
    if (...) then {...} else {...}
    ist der hinter if angegebene Ausdruck true, so wird der hinter then notierte Block ausgeführt. Ist der Ausdruck false wird stattdessen der hinter else notierte Block ausgeführt - sofern ein solcher existiert, anderenfalls wird die Anweisung einfach ignoriert. Das Ergebnis der Anweisung ist das Ergebnis des ausgeführten Blockes bzw. nil, falls kein Block ausgeführt wurde
  • select {
      when (...) then {...}
      ...
      otherwise {...}
    }
    wertet der Reihe nach alle hinter when notierten Ausdrücke aus, hält an sobald der erste Ausdruck mit dem Wert true gefunden wurde und führt daraufhin den Block hinter dem zugehörigen then aus. Liefert kein when-Ausdruck den Wert true, so wird stattdessen der Block hinter otherwise ausgeführt - sofern ein solcher existiert, anderenfalls wird die Anweisung ignoriert. Das Ergebnis der Anweisung ist das Ergebnis des ausgeführten Blockes bzw. nil, falls kein Block ausgeführt wurde
  • for identifier from ... to ... by ... repeat {...}
    for identifier from ... down to ... by ... repeat {...}
    führt den hinter repeat notierten Schleifenblock wiederholt und mit unterschiedlichen Werten für den gegebenen identifier aus, wobei diese Werte mit dem Wert des Ausdruckes hinter from beginnen und bei jedem Durchlauf um den Wert des Ausdruckes hinter by verändert werden. In der Version mit dem Schlüsselwort down endet die Schleife mit dem Unterschreiten des Wertes des Ausdruckes hinter to, ansonsten mit dessen Überschreiten. Hat der Ausdruck hinter by den Wert nil, so wird stattdessen +1 (in der Version ohne down) bzw. -1 (in der Version mit down) angenommen. Der identifier darf eine bereits vorhandene Variable aus dem lexikalischen Kontext bezeichnen, ansonsten wird die entsprechende Variable im Kontext der Schleife angelegt. Im Schleifenblock angelegte lokale Variablen behalten von einem Durchlauf zum nächsten ihren Wert. Das Ergebnis der Schleife ist das Ergebnis der letzten Ausführung des Schleifenblockes
  • while (...) repeat {...}
    führt den hinter repeat notierten Schleifenblock wiederholt durch, solange der hinter while notierte Ausdruck den Wert true liefert. Im Schleifenblock angelegte lokale Variablen behalten von einem Durchlauf zum nächsten ihren Wert, und die Abbruchbedingung wird ebenfalls im Kontext des Schleifenblockes ausgeführt. Das Ergebnis der Schleife ist das Ergebnis der letzten Ausführung des Schleifenblockes
  • repeat {...} until (...)
    führt den hinter repeat notierten Schleifenblock wiederholt durch, bis der hinter until notierte Ausdruck den Wert true liefert. Im Schleifenblock angelegte lokale Variablen behalten von einem Durchlauf zum nächsten ihren Wert, und die Abbruchbedingung wird ebenfalls im Kontext des Schleifenblockes ausgeführt. Das Ergebnis der Schleife ist das Ergebnis der letzten Ausführung des Schleifenblockes
  • break
    bricht die innerste in der gerade ausgeführten (Script-)Funktion laufende Schleife ab
  • continue
    fordert eine neue Iteration der innersten in der gerade ausgeführten (Script-)Funktion laufenden Schleife an - oder bricht diese ab, falls die Abbruchbedingung der Schleife erfüllt ist
  • return expr
    bricht die gerade laufende Funktion ab und liefert den Wert des (optionalen) Ausdrucks zurück - fehlt dieser Ausdruck, so wird nil zurückgegeben

Kommentare

slang unterstützt einzeilige und mehrzeilige (nicht schachtelbare) Kommentare:

  • einzeilig // ... bis Zeilenende
  • mehrzeilig /* ...ein- oder mehrzeilig, nicht schachtelbar */

slang-Laufzeitumgebung

Genauso wie "richtige" Programmiersprachen bietet auch slang mit einer Grundausstattung an "intrinsischen" (d.h. eingebauten) Werten und Funktionen an. Diese liegen im globalen Kontext und sind somit von überall erreichbar - sofern sie nicht von gleichnamigen Funktionen im lokalen Kontext "überdeckt" werden.

intrinsische Werte

  • nil - repräsentiert "nichts", also einen nicht definierten Wert (JavaScript undefined)
  • true - repräsentiert den logischen Wert für "wahr"
  • false - repräsentiert den logischen Wert für "falsch"
  • pi - enthält den Wert für die Kreiszahl pi
  • e - enthält den Wert für die Euler-Konstante

Operatoren als Funktionen

Die logischen, mathematischen und vergleichenden Operatoren können auch als Funktionen aufgerufen werden - durch Überschreiben dieser Funktionen kann demnach das Verhalten der zugehörigen Operatoren verändert werden. Der Parser ruft Operatoren in Ausdrücken übrigens direkt aus dem globalen Kontext heraus auf, so dass lokale Funktionen des gleichen Namens keine Operatoren überdecken können.

  • neg(a) - liefert die Zahl a mit umgekehrtem Vorzeichen (also -a)
  • plus(a,b) - addiert die beiden Zahlen a und b bzw. hängt Zeichenketten aneinander an
  • minus(a,b) - subtrahiert die Zahl b von der Zahl a
  • times(a,b) - berechnet das Produkt der beiden Zahlen a und b
  • through(a,b) - dividiert die Zahl a durch die Zahl b
  • div(a,b) - dividiert die Zahl a durch die Zahl b und liefert den ganzzahligen Anteil des Ergebnisses
  • mod(a,b) - liefert den Rest der Division der Zahl a durch die Zahl b
  • raised(a,b) - liefert die b-te Potenz der Zahl a
     
  • lt(a,b) - liefert true dann und nur dann, wenn a < b gilt
  • le(a,b) - liefert true dann und nur dann, wenn a <= b gilt
  • eq(a,b) - liefert true dann und nur dann, wenn a = b gilt
  • ge(a,b) - liefert true dann und nur dann, wenn a >= b gilt
  • gt(a,b) - liefert true dann und nur dann, wenn a > b gilt
  • ne(a,b) - liefert true dann und nur dann, wenn a <> b gilt
     
  • not(a) - liefert die logische Negation des boole'schen Wertes a
  • and(a,b) - liefert die logische Konjunktion der boole'schen Werte a und b
  • or(a,b) - liefert die logische Disjunktion der boole'schen Werte a und b

intrinsische mathematische Funktionen

Folgende mathematische Funktionen sind in slang eingebaut:

  • is_nan(a) - liefert true dann und nur dann, wenn a den Wert NaN besitzt
     
  • sqrt(a) - liefert die Quadratwurzel von a
  • sin(a) - liefert den Sinus von a
  • cos(a) - liefert den Cosinus von a
  • tan(a) - liefert den Tangens von a
     
  • rnd(a) - liefert eine Pseudo-Zufallszahl im Bereich 0...a, wobei a selbst ausgeschlossen ist

Kontrollanweisungen als Funktionen

Auch die Anweisungen zur Steuerung des Programmflusses liegen als globale Funktionen vor und können demzufolge geändert werden. Der Parser ruft Anweisungen übrigens direkt aus dem globalen Kontext heraus auf, so dass lokale Funktionen des gleichen Namens keine Anweisungen überdecken können.

  • if_then_else (condition, then_clause, else_clause)
    ist der boole'sche Wert condition true, wird der Block then_clause ausgeführt; ist er false, wird der Block else_clause ausgeführt - sofern ein solcher Block existiert, ansonsten wird die Anweisung einfach ignoriert. Das Ergebnis der Funktion ist das Ergebnis des ausgeführten Blockes bzw. nil, falls kein Block ausgeführt wurde
  • select_when (otherwise_clause, condition,block,...)
    wertet der Reihe nach alle condition-Blöcke bzw. (logischen) Werte der gegebenen condition-block-Paare aus, hält an sobald die erste condition mit dem Ergebnis true gefunden wird und führt daraufhin den zugehörigen block aus. Liefert keine condition den Wert true, so wird stattdessen der otherwise_clause ausgeführt. Das Ergebnis der Funktion ist das Ergebnis des ausgeführten Blockes
  • for_repeat (identifier, downwards, start_value, stop_value, step_value, loop_body)
    führt den Block loop_body wiederholt mit unterschiedlichen Werten für den gegebenen identifier aus, wobei diese Werte mit start_value beginnen und bei jedem Durchlauf um step_value verändert werden. Hat das boole'sche Argument downwards den Wert true, so endet die Schleife mit dem Unterschreiten des stop_value, ansonsten mit dessen Überschreiten. Hat step_value den Wert nil, so wird stattdessen der Wert +1 (falls downwards = false) bzw. -1 (falls downwards = true) angenommen. Der identifier darf eine bereits vorhandene Variable aus dem lexikalischen Kontext bezeichnen, ansonsten wird die Variable im Kontext der Schleife angelegt. In loop_body angelegte lokale Variablen behalten von einem Durchlauf zum nächsten ihren Wert. Das Ergebnis der Schleife ist das Ergebnis der letzten Ausführung des loop_body
  • while_repeat (condition, loop_body)
    führt den Block loop_body wiederholt durch, solange eine Ausführung des Blockes condition den Wert true liefert. In loop_body angelegte lokale Variablen behalten von einem Durchlauf zum nächsten ihren Wert. Das Ergebnis der Schleife ist das Ergebnis der letzten Ausführung des loop_body
  • repeat_until (loop_body, condition)
    führt den Block loop_body wiederholt durch, bis eine Ausführung des Blockes condition den Wert true liefert. In loop_body angelegte lokale Variablen behalten von einem Durchlauf zum nächsten ihren Wert. Das Ergebnis der Schleife ist das Ergebnis der letzten Ausführung des loop_body
  • break (value)
    bricht die innerste in der gerade ausgeführten (Script-)Funktion laufende Schleife ab und liefert den gegebenen value zurück
  • continue
    fordert eine neue Iteration der innersten in der gerade ausgeführten (Script-)Funktion laufenden Schleife an - oder bricht diese ab, falls die Abbruchbedingung der Schleife erfüllt ist
  • return (value)
    bricht die gerade laufende Funktion ab und liefert den gegebenen value zurück
  • assert (value)
    prüft, ob value den Wert true hat - falls ja, wird die Programmausführung fortgesetzt, anderenfalls wird sie mit einer Fehlermeldung abgebrochen
  • assert_failure (block)
    prüft, ob bei der Ausführung des Blockes block ein Fehler auftritt - falls ja, wird der Fehler ignoriert und die Programmausführung fortgesetzt, anderenfalls wird sie mit einer Fehlermeldung abgebrochen
  • log (value)
    gibt value auf die Browser-Konsole aus

slang-Grammatik

Die Grammatik zu slang in PEG.js-Notation kommt (wie üblich) ohne separaten "Lexer" aus und ist dennoch erstaunlich kompakt.

slang-Grammatik mit AST-Generierung

Mit ein paar zusätzlichen JavaScript-Dekorierungen ist diese Grammatik in der Lage, einen "abstract syntax tree" (AST) auszugeben.

Vollständiger slang-Interpreter

Von der AST-Ausgabe zu einem vollwertigen Interpreter ist es nicht mehr weit - allerdings muss dazu JavaScript programmiert werden, die Domäne der reinen Syntax-Spezifikation wird folglich verlassen.

Beispiele

Die folgenden Beispiele zeigen die Verwendung der unterschiedlichen Werte, Operatoren und Anweisungen - und dienen zugleich als eine Art "Smoke Test" für den Interpreter

Test der "tail call elimination" in slang

Zu den Besonderheiten von "slang" gehört das Auflösen von "Endaufrufen" und insbesondere auch "Endrekursionen" - auf diese Weise können (ähnlich wie in manchen streng funktionalen Sprachen) Schleifen gefahrlos durch Rekursionen ersetzt werden.

Zu den klassischen Beispielen für Funktionen, die für eine "tail recursion elimination" umgeschrieben werden können, gehören die mathematische Fakultät und die Berechnung der Fibonacci-Reihe - auch wenn moderne Sprachen (wie z.B. JavaScript) auf leistungsfähigen Rechnern heutzutage eher die Grenze des numerischen Wertebereiches erreichen als auf Probleme mit der Rekursion stoßen.

Will man einen modernen Rechner in die Knie zwingen, muss man schon zu "heftigeren" Methoden greifen - z.B. die Verwendung von Rekursionen anstelle von Schleifen.