Hallo! Ich präsentiere Ihnen eine Amateurübersetzung eines Leitfadens zur Implementierung Ihrer JavaScript-Programmiersprache - PL Tutorial .

Vom Übersetzer

Wir werden unsere eigene Programmiersprache erstellen - λ-Sprache (im Original - λanguage). Während des Erstellungsprozesses werden wir viele interessante Techniken verwenden, wie z. B. rekursiven Abstieg, Kontrollübertragungsstil und grundlegende Optimierungstechniken. Es werden zwei Versionen des Interpreters erstellt - der reguläre und der CPS-Interpreter, der Transcompiler in JavaScript.

Der Autor des Originals ist Mihai Bazon , der Autor der berühmten UglifyJS-Bibliothek (ein Tool zum Minimieren und Formatieren von JS-Code).

Eintrag

Wenn Sie jemals Ihren Compiler oder Interpreter geschrieben haben, gibt es nichts Neues für Sie. Wenn Sie jedoch reguläre Ausdrücke verwenden, um etwas zu analysieren , das wie eine Programmiersprache aussieht, lesen Sie den Abschnitt zum Parsen . Schreiben wir Code mit weniger Fehlern!

Der Artikel ist in der Reihenfolge „von einfach bis komplex“ in Teile unterteilt. Ich empfehle nicht, Teile des Artikels zu überspringen, es sei denn, Sie verstehen das Thema gut. Sie können jederzeit zurückgehen, wenn Sie etwas nicht verstehen.

Was werden wir lernen:

• Was ist ein Parser und wie schreibt man ihn?
• Wie schreibe ich einen Dolmetscher?
• Die Fortsetzung der Übertragung und warum es wichtig ist.
• Schreiben eines (Trans-) Compilers.
• Fortführungsübertragungsstil.
• Einige grundlegende Techniken zur Codeoptimierung.
• Beispiele dafür, was in unserer λ-Sprache im Vergleich zu JavaScript neu ist.

Zusammen mit diesem werde ich zeigen, warum Lisp eine großartige Programmiersprache ist. Die Sprache, an der wir arbeiten, ist jedoch nicht Lisp. Es hat eine reichhaltigere Syntax (eine klassische Infix-Notation, die jeder kennt), so etwas wie Scheme (außer Makros). Gut oder nicht, aber Makros sind das Hauptmerkmal von Lisp - etwas, das andere Sprachen (außer Lisp-Dialekten) nicht so gut können wie sie. (Ja, ich weiß über SweetJS Bescheid ... nah dran, aber nicht das.)

Aber zuerst wollen wir unsere Programmiersprache vorstellen.

λ Sprache

Bevor wir etwas tun, müssen wir ein klares Bild davon haben, was wir tun wollen. Es wäre schön, eine Beschreibung der Grammatik der Sprache zu schreiben, aber ich werde es einfacher machen - schreibe ein Beispiel für ein einfaches Programm, also hier einige Beispiele für die λ-Sprache:

#   println("Hello World!"); println(2 + 3 * 4); #       `lambda`  `λ` fib = lambda (n) if n < 2 then n else fib(n - 1) + fib(n - 2); println(fib(15)); print-range = λ(a, b) # `λ`     ,   `lambda` if a <= b then { # `then`  ,      print(a); if a + 1 <= b { print(", "); print-range(a + 1, b); } else println(""); #   }; print-range(1, 5); 

Fazit:

 Hello World! 14 610 1, 2, 3, 4, 5 

Die Sprache ähnelt JavaScript, ist es aber insgesamt nicht. Erstens gibt es keine Aussagen, nur Ausdrücke. Ein Ausdruck muss einen Wert zurückgeben und kann an einer beliebigen Stelle in einem anderen Ausdruck verwendet werden. Semikolons werden benötigt, um Ausdrücke in einer "Folge" von Ausdrücken zu trennen. Geschweifte Klammern { und } erstellen eine Sequenz, die selbst ein Ausdruck ist, und ihr Wert ist der letzte Wert aus der Sequenz. Das folgende Programm ist korrekt:

 a = { fib(10); #    ,      fib(15) #        }; print(a); #  610 

Funktionen werden mit den Schlüsselwörtern lambda oder λ . Danach steht in Klammern eine (möglicherweise leere) Liste von Argumentnamen, die durch Kommas getrennt sind. Der Hauptteil einer Funktion ist ein Ausdruck, kann jedoch in eine Sequenz {...} . Es ist auch erwähnenswert, dass es kein Schlüsselwort für die return . Die Funktion gibt den Wert des letzten Ausdrucks zurück.

Auch keine var . Um eine Variable hinzuzufügen, können Sie das verwenden, was JavaScript-Programmierer IIFE nennen. Verwenden Sie lambda und deklarieren Sie Variablen als Argumente. Für Variablen ist der Gültigkeitsbereich eine Funktion, und Funktionen sind Verschlüsse, wie in JavaScript [ca. Übersetzung: bis ES6.].

Auch if es ein Ausdruck ist. JavaScript verwendet dazu den ternären Operator:

 a = foo() ? bar() : baz(); // JavaScript a = if foo() then bar() else baz(); # λ 

Das Schlüsselwort then ist optional, wenn der Zweig eine Sequenz ( {...} ) ist, wie Sie oben sehen können. In einem anderen Fall ist es notwendig. else verwendet, wenn ein alternativer Zweig vorhanden ist. Und dann wieder und then nimm den Ausdruck als Körper, aber du kannst mehrere Ausdrücke mit {...} zu einem kombinieren. Wenn else fehlt und die Bedingung false , ist das Ergebnis aller if false . Es ist erwähnenswert, dass false ein Schlüsselwort ist, das einen Wert darstellt, der der einzige falsche Wert in einer λ-Sprache ist:

 if foo() then print("OK"); 

wird nur dann OK ausgegeben, wenn das Ergebnis von foo() nicht false . Es gibt auch das Schlüsselwort true , aber absolut alles, was nicht false (in JavaScript der Operator === ), wird in den Zweigen als true betrachtet (einschließlich der Nummer 0 und der leeren Zeichenfolge "" ).

Beachten Sie, dass in if keine Klammern um den Ausdruck erforderlich if . Wenn Sie sie hinzufügen, ist dies kein Fehler, denn ( der Ausdruck beginnt, aber sie sind einfach überflüssig.

Das gesamte Programm kann analysiert werden, auch wenn es von Klammern umgeben ist. Fügen Sie daher Folgendes hinzu ; nach jedem Ausdruck. Der letzte Ausdruck ist eine Ausnahme.

Großartig, das ist unsere kleine λ-Sprache. Er ist nicht perfekt. Die Syntax sieht gut aus, hat aber Mängel. Es fehlen viele Funktionen wie Objekte und Arrays. Wir achten nicht auf sie, da sie für unsere Programmiersprache nicht grundlegend sind.

Als nächstes werden wir einen Parser für unsere Sprache schreiben.

Codekonvertierung in AST

Das Erstellen eines Parsers ist eine schwierige Aufgabe. Im Wesentlichen sollte ein Teil des Codes in einen AST (Abstract Syntax Tree) umgewandelt werden. AST ist eine strukturierte Darstellung eines Programms im Speicher, abstrakt, da es keine vollständigen Informationen über den Code enthält, sondern nur die Semantik. Beschreibung AST befindet sich in einem separaten Teil.

Zum Beispiel haben wir den folgenden Code:

 sum = lambda(a, b) { a + b; }; print(sum(1, 2)); 

Unser Parser generiert einen Baum als JavaScript-Objekt:

 { type: "prog", prog: [ //  : { type: "assign", operator: "=", left: { type: "var", value: "sum" }, right: { type: "lambda", vars: [ "a", "b" ], body: { //     "prog",  ,  //     ,  //     . type: "binary", operator: "+", left: { type: "var", value: "a" }, right: { type: "var", value: "b" } } } }, //  : { type: "call", func: { type: "var", value: "print" }, args: [{ type: "call", func: { type: "var", value: "sum" }, args: [ { type: "num", value: 1 }, { type: "num", value: 2 } ] }] } ] } 

Die Hauptschwierigkeit beim Erstellen eines Parsers ist die Schwierigkeit, den Code richtig zu organisieren. Der Parser sollte auf einer höheren Ebene arbeiten als das Lesen von Zeichen aus einer Zeichenfolge. Einige Richtlinien zur Reduzierung der Codekomplexität:

• Schreiben Sie viele kleine Funktionen. Machen Sie in jeder Funktion eine Sache und machen Sie es gut.
• Versuchen Sie nicht, reguläre Ausdrücke zum Parsen zu verwenden. Sie funktionieren einfach nicht. Sie können im lexikalischen Analysegerät nützlich sein, werden jedoch der Einfachheit halber nicht verwendet.
• Versuchen Sie nicht zu raten. Wenn Sie nicht sicher sind, wie Sie etwas analysieren sollen, lösen Sie eine Ausnahme aus, die den Ort des Fehlers enthält (Zeile und Spalte).

Um den Code einfacher zu halten, werden wir ihn in drei Teile unterteilen, die wiederum in viele kleine Funktionen unterteilt sind:

• Zeichenstrom
• Token Flow (Token)
• Parser

Zeichenstrom

Dies ist der einfachste Teil. Wir werden ein Stream-Objekt erstellen, das die Operationen zum sequentiellen Lesen von Zeichen aus einer Zeichenfolge darstellt. Es enthält vier Funktionen:

• peek() - gibt das nächste Zeichen zurück, ohne es aus dem Stream zu extrahieren.
• next() - gibt das nächste Zeichen zurück und extrahiert es aus dem Stream.
• eof() - gibt true zurück true wenn der Stream keine weiteren Zeichen enthält.
• croak(msg) - löst eine Ausnahme aus, die die Nachricht ( msg ) und die aktuelle Position im Stream enthält.

Die letzte Funktion wird benötigt, damit Sie einfach eine Ausnahme auslösen können, die den Ort des Fehlers enthält.

Hier ist der gesamte Code für dieses Objekt (nennen wir es InputStream ). Es ist klein genug, damit Sie keine Probleme damit haben sollten:

 function InputStream(input) { var pos = 0, line = 1, col = 0; return { next : next, peek : peek, eof : eof, croak : croak, }; function next() { var ch = input.charAt(pos++); if (ch == "\n") line++, col = 0; else col++; return ch; } function peek() { return input.charAt(pos); } function eof() { return peek() == ""; } function croak(msg) { throw new Error(msg + " (" + line + ":" + col + ")"); } } 

Bitte beachten Sie, dass dies kein gewöhnliches Objekt ist (das über new ). Um dieses Objekt zu erhalten, benötigen Sie: var stream = InputStream(string) .

Als nächstes schreiben wir die folgende Abstraktionsebene: Token Flow (Token) .

Token Flow (Token)

Der Tokenizer (Lexer) verwendet einen Strom von Zeichen und gibt ein Objekt mit derselben Schnittstelle zurück, aber die Rückgabewerte der Funktionen peek() / next() sind Token. Ein Token ist ein Typ mit zwei Eigenschaften: type , value . Hier sind einige Beispiele für Token:

 { type: "punc", value: "(" } // . : , ,     . . { type: "num", value: 5 } //  { type: "str", value: "Hello World!" } //  { type: "kw", value: "lambda" } //   { type: "var", value: "a" } //  { type: "op", value: "!=" } //  

Leerzeichen (Leerzeichen, Tabulatoren, Zeilenumbrüche) und Kommentare werden einfach übersprungen.

Um einen Tokenizer zu schreiben, müssen wir uns unsere Sprache genauer ansehen. Die Idee ist zu beachten, dass wir abhängig vom aktuellen Zeichen ( input.peek() ) entscheiden können, welches Token gelesen werden soll:

• Überspringen Sie zunächst Leerzeichen.
• Wenn input.eof() , geben Sie null .
• Wenn es sich um ein # -Zeichen handelt, überspringen Sie alle Zeichen bis zum Ende der Zeile (und geben Sie das nächste Token zurück).
• Wenn dies ein Anführungszeichen ist, lesen Sie die Zeichenfolge.
• Wenn dies eine Nummer ist, lesen Sie die Nummer.
• Wenn es sich um einen Buchstaben handelt, lesen wir das Wort und geben entweder den Bezeichner oder das Schlüsselwort zurück.
• Wenn dies eines der Sonderzeichen ist, geben Sie das entsprechende Token zurück.
• Wenn dies eines der Operatorsymbole ist, geben Sie das entsprechende Token zurück.
• Wenn keine der oben genannten input.croak() zutrifft, input.croak() mit input.croak() eine Ausnahme aus.

Wir werden die Funktion read_next , die Hauptfunktion des Tokenizers:

 function read_next() { read_while(is_whitespace); if (input.eof()) return null; var ch = input.peek(); if (ch == "#") { skip_comment(); return read_next(); } if (ch == '"') return read_string(); if (is_digit(ch)) return read_number(); if (is_id_start(ch)) return read_ident(); if (is_punc(ch)) return { type : "punc", value : input.next() }; if (is_op_char(ch)) return { type : "op", value : read_while(is_op_char) }; input.croak("Can't handle character: " + ch); } 

Hier sehen Sie viele zusätzliche Funktionen, die verschiedene Arten von Token zurückgeben, z. B. read_string() , read_number() usw. ... Sie sind in separaten Funktionen angeordnet, damit der Code einfacher und schöner aussieht.

Interessant ist auch, dass wir nicht alle Symbole auf einmal entfernen: Jedes Mal, wenn der Parser nach dem nächsten Token fragt, lesen wir einen Token. Wenn ein Fehler auftritt, lesen wir nicht einmal alle Zeichen.

read_ident() liest alle Zeichen in einer Zeile, die Teil des Bezeichners sein können ( is_id() ). Der Bezeichner muss mit dem Buchstaben λ oder _ und darf dieselben Zeichen, Zahlen oder eines der folgenden Elemente enthalten: ?!-<>= . Daraus folgt, dass foo-bar nicht als drei Token gelesen wird, sondern als einer ( var Token). Ist dies notwendig, um Funktionen mit Namen wie is-pair? definieren zu können is-pair? oder string>= (sorry, das ist Lisper in mir).

Außerdem read_ident() , ob die Liste der bekannten Schlüsselwörter einen Bezeichner enthält, und wenn dieser vorhanden ist, wird ein kw Token anstelle eines var Tokens zurückgegeben.

Ich denke, der Code spricht für sich selbst. Hier ist ein vorgefertigter Tokenizer für unsere Sprache:

 function TokenStream(input) { var current = null; var keywords = " if then else lambda λ true false "; return { next : next, peek : peek, eof : eof, croak : input.croak }; function is_keyword(x) { return keywords.indexOf(" " + x + " ") >= 0; } function is_digit(ch) { return /[0-9]/i.test(ch); } function is_id_start(ch) { return /[a-zλ_]/i.test(ch); } function is_id(ch) { return is_id_start(ch) || "?!-<>=0123456789".indexOf(ch) >= 0; } function is_op_char(ch) { return "+-*/%=&|<>!".indexOf(ch) >= 0; } function is_punc(ch) { return ",;(){}[]".indexOf(ch) >= 0; } function is_whitespace(ch) { return " \t\n".indexOf(ch) >= 0; } function read_while(predicate) { var str = ""; while (!input.eof() && predicate(input.peek())) str += input.next(); return str; } function read_number() { var has_dot = false; var number = read_while(function(ch){ if (ch == ".") { if (has_dot) return false; has_dot = true; return true; } return is_digit(ch); }); return { type: "num", value: parseFloat(number) }; } function read_ident() { var id = read_while(is_id); return { type : is_keyword(id) ? "kw" : "var", value : id }; } function read_escaped(end) { var escaped = false, str = ""; input.next(); while (!input.eof()) { var ch = input.next(); if (escaped) { str += ch; escaped = false; } else if (ch == "\\") { escaped = true; } else if (ch == end) { break; } else { str += ch; } } return str; } function read_string() { return { type: "str", value: read_escaped('"') }; } function skip_comment() { read_while(function(ch){ return ch != "\n" }); input.next(); } function read_next() { read_while(is_whitespace); if (input.eof()) return null; var ch = input.peek(); if (ch == "#") { skip_comment(); return read_next(); } if (ch == '"') return read_string(); if (is_digit(ch)) return read_number(); if (is_id_start(ch)) return read_ident(); if (is_punc(ch)) return { type : "punc", value : input.next() }; if (is_op_char(ch)) return { type : "op", value : read_while(is_op_char) }; input.croak("Can't handle character: " + ch); } function peek() { return current || (current = read_next()); } function next() { var tok = current; current = null; return tok || read_next(); } function eof() { return peek() == null; } } 

• Die next() -Funktion ruft nicht immer read_next() , da möglicherweise ein Token gelesen wurde, das zuvor gelesen wurde (mithilfe der peek() -Funktion). Dazu haben wir eine current Variable, die das aktuelle Token enthält.
• In regulärer Notation werden nur Dezimalzahlen unterstützt (1E5, 0x usw. werden nicht unterstützt). Aber wenn wir ihre Unterstützung hinzufügen wollten, würden wir nur read_number() ändern.
• Im Gegensatz zu JavaScript sind die einzigen Zeichen, die in einer Zeichenfolge nicht entfernt werden können, Anführungszeichen und Backslash. Zeilen können Zeilenumbrüche, Tabulatoren und alles andere enthalten. Wir interpretieren keine Standardkombinationen wie \n , \t usw. ... Es ist sehr einfach zu wiederholen ( read_string() ).

Jetzt haben wir leistungsstarke Tools zum einfachen Schreiben eines Parsers , aber zuerst würde ich empfehlen, die AST-Beschreibung zu lesen .

AST Beschreibung

Wie oben angegeben, erstellt der Parser eine Struktur, die die Semantik des Programms zeigt. AST besteht aus Knoten. Jeder Knoten ist ein reguläres JavaScript-Objekt mit einer type Eigenschaft, die den Typ des Knotens bestimmt, sowie zusätzlichen Informationen, die vom Typ abhängen.

 123.5 

 { type: "num", value: 123.5 } 

 "Hello World" 

 { type: "str", value: "Hello World!" } 

 true false 

 { type: "bool", value: true } { type: "bool", value: false } 

 foo 

 { type: "var", value: "foo" } 

 lambda (x) 10 #  λ (x) 10 

 { type: "lambda", vars: [ "x" ], body: { type: "num", value: 10 } } 

 foo(a, 1) 

 { "type": "call", "func": { "type": "var", "value": "foo" }, "args": [ { "type": "var", "value": "a" }, { "type": "num", "value": 1 } ] } 

 if foo then bar else baz 

 { "type": "if", "cond": { "type": "var", "value": "foo" }, "then": { "type": "var", "value": "bar" }, "else": { "type": "var", "value": "baz" } } 

 if foo then bar 

 { "type": "if", "cond": { "type": "var", "value": "foo" }, "then": { "type": "var", "value": "bar" } } 

 a = 10 

 { "type": "assign", "operator": "=", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 10 } } 

 x + y * z 

 { "type": "binary", "operator": "+", "left": { "type": "var", "value": "x" }, "right": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "y" }, "right": { "type": "var", "value": "z" } } } 

 { a = 5; b = a * 2; a + b; } 

 { "type": "prog", "prog": [ { "type": "assign", "operator": "=", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 5 } }, { "type": "assign", "operator": "=", "left": { "type": "var", "value": "b" }, "right": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 2 } } }, { "type": "binary", "operator": "+", "left": { "type": "var", "value": "a" }, "right": { "type": "var", "value": "b" } } ] } 

 let (a = 10, b = a * 10) { a + b; } 

 { "type": "let", "vars": [ { "name": "a", "def": { "type": "num", "value": 10 } }, { "name": "b", "def": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 10 } } } ], "body": { "type": "binary", "operator": "+", "left": { "type": "var", "value": "a" }, "right": { "type": "var", "value": "b" } } } 

Parser

Der Parser erstellt den oben beschriebenen Baum.

Dank der Arbeit, die wir im Tokenizer geleistet haben, arbeitet der Parser mit einem Strom von Token anstelle eines Stroms von Zeichen. Es gibt hier noch viele zusätzliche Funktionen, um die Struktur zu vereinfachen. Wir werden über die wichtigsten sprechen. Beginnen wir mit einer allgemeinen Parser-Funktion:

 function parse_lambda() { return { type: "lambda", vars: delimited("(", ")", ",", parse_varname), body: parse_expression() }; } 

Diese Funktion wird aufgerufen, wenn das lambda Schlüsselwort bereits aus dem Token-Stream übernommen wurde. Wir müssen also nur die Namen der Argumente übernehmen. Da sie jedoch in Klammern stehen und durch Kommas getrennt sind, verwenden wir dazu die delimited Funktion, die die folgenden Argumente verwendet: start , stop , separator , die parser Funktion, die jedes Element separat analysiert. In diesem Fall verwenden wir die Funktion parse_varname , die einen Fehler parse_varname , wenn etwas bemerkt wird, das nicht wie eine Variable aussieht. Der Hauptteil der Funktion ist ein Ausdruck, daher erhalten wir ihn mit parse_expression .

Die delimited Funktion ist niedriger:

 function delimited(start, stop, separator, parser) { var a = [], first = true; skip_punc(start); while (!input.eof()) { if (is_punc(stop)) break; if (first) first = false; else skip_punc(separator); if (is_punc(stop)) break; //      a.push(parser()); } skip_punc(stop); return a; } 

Wie Sie sehen können, werden noch mehr Funktionen verwendet: is_punc und skip_punc . Der erste gibt true zurück true wenn das aktuelle Token ein bestimmtes Interpunktionszeichen ist (ohne es zu extrahieren), während skip_punc prüft, ob das aktuelle Token ein bestimmtes Interpunktionszeichen ist, und es extrahiert (oder eine Ausnahme auslöst).

Die Funktion, die das gesamte Programm analysiert, scheint die einfachste zu sein:

 function parse_toplevel() { var prog = []; while (!input.eof()) { prog.push(parse_expression()); if (!input.eof()) skip_punc(";"); } return { type: "prog", prog: prog }; } 

Da wir nur Ausdrücke haben, rufen wir einfach parse_expression() und lesen die Ausdrücke, bis wir alles gelesen haben. Mit skip_punc(";") tun wir dies ; obligatorisch nach jedem Ausdruck.

Ein weiteres einfaches Beispiel ist parse_if() :

 function parse_if() { skip_kw("if"); var cond = parse_expression(); if (!is_punc("{")) skip_kw("then"); var then = parse_expression(); var ret = { type: "if", cond: cond, then: then }; if (is_kw("else")) { input.next(); ret.else = parse_expression(); } return ret; } 

Sie überspringt das Schlüsselwort if (löst eine Ausnahme aus, wenn das aktuelle Token nicht das Schlüsselwort if ) und liest die Bedingung mit parse_expression() . Wenn das Symbol { nicht weiter geht, ist das Schlüsselwort then erforderlich (die Syntax sieht ohne es nicht sehr gut aus). Zweige sind nur Ausdrücke, daher verwenden wir für sie einfach wieder parse_expression() . Der else Zweig ist optional, daher prüfen wir zunächst, ob das Schlüsselwort vorhanden ist, bevor wir es analysieren.

Mit vielen kleinen Funktionen können wir den Code einfach machen. Wir haben den Parser fast so geschrieben, als würden wir eine Hochsprache speziell für die Parsing-Syntax verwenden. Alle diese Funktionen sind "gegenseitig rekursiv", parse_atom() wir haben parse_atom() , das abhängig vom aktuellen Token andere Funktionen aufruft. Eines davon ist parse_if() (wird aufgerufen, wenn das aktuelle Token if ) und ruft wiederum parse_expression() . Aber parse_expression() ruft parse_atom() . Es gibt keine unendliche Rekursion, da eine der Funktionen immer mindestens ein Token extrahiert.

Diese Art der Analysemethode wird als rekursive Abstiegsmethode bezeichnet und ist in der Tat am einfachsten zu schreiben.

Untere Ebene: parse_atom() und parse_expression()

Die Funktion parse_atom() ruft abhängig vom aktuellen Token eine andere Funktion auf:

 function parse_atom() { return maybe_call(function(){ if (is_punc("(")) { input.next(); var exp = parse_expression(); skip_punc(")"); return exp; } if (is_punc("{")) return parse_prog(); if (is_kw("if")) return parse_if(); if (is_kw("true") || is_kw("false")) return parse_bool(); if (is_kw("lambda") || is_kw("λ")) { input.next(); return parse_lambda(); } var tok = input.next(); if (tok.type == "var" || tok.type == "num" || tok.type == "str") return tok; unexpected(); }); } 

Wenn sie die öffnende Klammer sieht, sollte der Klammerausdruck gehen. Daher überspringt die Funktion parse_expression() und erwartet, dass die schließende Klammer danach übersprungen wird. Wenn sie ein Schlüsselwort sieht, ruft sie die entsprechende Funktion auf. Wenn sie eine Konstante oder einen Bezeichner sieht, gibt sie diese unverändert zurück. Und wenn nichts auftaucht, ruft es unexpected() , was eine Ausnahme auslöst.

Wenn sie { sieht, ruft sie parse_prog auf, um die Reihenfolge der Ausdrücke zu analysieren. Außerdem führt parse_prog eine einfache Optimierung durch: Wenn zwischen { und } keine Ausdrücke vorhanden sind, wird false . Wenn nur ein Ausdruck vorhanden ist, wird nur dieser zurückgegeben. Andernfalls wird der prog Knoten mit einem Array von Ausdrücken zurückgegeben.

 //     FALSE   , //     . var FALSE = { type: "bool", value: false }; function parse_prog() { var prog = delimited("{", "}", ";", parse_expression); if (prog.length == 0) return FALSE; if (prog.length == 1) return prog[0]; return { type: "prog", prog: prog }; } 

Und hier ist die Funktion parse_expression() . Im Gegensatz zu parse_atom() werden mit maybe_binary() so viele Ausdrücke wie möglich maybe_binary() :

 function parse_expression() { return maybe_call(function(){ return maybe_binary(parse_atom(), 0); }); } 

Funktionen maybe_*

Diese Funktionen prüfen, was nach dem Ausdruck kommt, und entscheiden, ob der Ausdruck in seinen Knoten eingeschlossen oder unverändert zurückgegeben werden soll.

Die Funktion maybe_call() ist sehr einfach: Sie erhält eine Funktion, die den aktuellen Ausdruck analysiert, und wenn sie auf etwas trifft ( nach dem Ausdruck, umschließt sie sich selbst in einen call . Beachten Sie, wie delimited() zum Parsen einer Liste von Argumenten geeignet ist:

 function maybe_call(expr) { expr = expr(); return is_punc("(") ? parse_call(expr) : expr; } function parse_call(func) { return { type: "call", func: func, args: delimited("(", ")", ",", parse_expression) }; } 

Bedienerpriorität

Die Funktion maybe_binary(left, my_prec) wird verwendet, um Ausdrücke wie 1 + 2 * 3 zu kombinieren. , , , :

 var PRECEDENCE = { "=": 1, "||": 2, "&&": 3, "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7, "+": 10, "-": 10, "*": 20, "/": 20, "%": 20, }; 

, * "", + , , 1 + 2 * 3 (1 + (2 * 3)) ((1 + 2) * 3) .

, ( read_atom ) maybe_binary() ( ), ( my_prec ). maybe_binary , . , , .

, , , binary , , , (*):

 function maybe_binary(left, my_prec) { var tok = is_op(); if (tok) { var his_prec = PRECEDENCE[tok.value]; if (his_prec > my_prec) { input.next(); var right = maybe_binary(parse_atom(), his_prec) // (*); var binary = { type : tok.value == "=" ? "assign" : "binary", operator : tok.value, left : left, right : right }; return maybe_binary(binary, my_prec); } } return left; } 

, , , maybe_binary , ( my_prec ), , , . - , (, ), .

, , my_prec 0, binary ( assign = ).

, .

 var FALSE = { type: "bool", value: false }; function parse(input) { var PRECEDENCE = { "=": 1, "||": 2, "&&": 3, "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7, "+": 10, "-": 10, "*": 20, "/": 20, "%": 20, }; return parse_toplevel(); function is_punc(ch) { var tok = input.peek(); return tok && tok.type == "punc" && (!ch || tok.value == ch) && tok; } function is_kw(kw) { var tok = input.peek(); return tok && tok.type == "kw" && (!kw || tok.value == kw) && tok; } function is_op(op) { var tok = input.peek(); return tok && tok.type == "op" && (!op || tok.value == op) && tok; } function skip_punc(ch) { if (is_punc(ch)) input.next(); else input.croak("Expecting punctuation: \"" + ch + "\""); } function skip_kw(kw) { if (is_kw(kw)) input.next(); else input.croak("Expecting keyword: \"" + kw + "\""); } function skip_op(op) { if (is_op(op)) input.next(); else input.croak("Expecting operator: \"" + op + "\""); } function unexpected() { input.croak("Unexpected token: " + JSON.stringify(input.peek())); } function maybe_binary(left, my_prec) { var tok = is_op(); if (tok) { var his_prec = PRECEDENCE[tok.value]; if (his_prec > my_prec) { input.next(); return maybe_binary({ type : tok.value == "=" ? "assign" : "binary", operator : tok.value, left : left, right : maybe_binary(parse_atom(), his_prec) }, my_prec); } } return left; } function delimited(start, stop, separator, parser) { var a = [], first = true; skip_punc(start); while (!input.eof()) { if (is_punc(stop)) break; if (first) first = false; else skip_punc(separator); if (is_punc(stop)) break; a.push(parser()); } skip_punc(stop); return a; } function parse_call(func) { return { type: "call", func: func, args: delimited("(", ")", ",", parse_expression), }; } function parse_varname() { var name = input.next(); if (name.type != "var") input.croak("Expecting variable name"); return name.value; } function parse_if() { skip_kw("if"); var cond = parse_expression(); if (!is_punc("{")) skip_kw("then"); var then = parse_expression(); var ret = { type: "if", cond: cond, then: then, }; if (is_kw("else")) { input.next(); ret.else = parse_expression(); } return ret; } function parse_lambda() { return { type: "lambda", vars: delimited("(", ")", ",", parse_varname), body: parse_expression() }; } function parse_bool() { return { type : "bool", value : input.next().value == "true" }; } function maybe_call(expr) { expr = expr(); return is_punc("(") ? parse_call(expr) : expr; } function parse_atom() { return maybe_call(function(){ if (is_punc("(")) { input.next(); var exp = parse_expression(); skip_punc(")"); return exp; } if (is_punc("{")) return parse_prog(); if (is_kw("if")) return parse_if(); if (is_kw("true") || is_kw("false")) return parse_bool(); if (is_kw("lambda") || is_kw("λ")) { input.next(); return parse_lambda(); } var tok = input.next(); if (tok.type == "var" || tok.type == "num" || tok.type == "str") return tok; unexpected(); }); } function parse_toplevel() { var prog = []; while (!input.eof()) { prog.push(parse_expression()); if (!input.eof()) skip_punc(";"); } return { type: "prog", prog: prog }; } function parse_prog() { var prog = delimited("{", "}", ";", parse_expression); if (prog.length == 0) return FALSE; if (prog.length == 1) return prog[0]; return { type: "prog", prog: prog }; } function parse_expression() { return maybe_call(function(){ return maybe_binary(parse_atom(), 0); }); } } 

Marijn Haverbeke, parse-js (Common Lisp), , . , , JS, .

: JavaScript. Teil 2: Dolmetscher