** "Sieht aus wie JavaScript, Gehirn (Inhalt) ist Ruby, (Stabilität ist AC / DC)" ** Skriptsprache Kinx ). Diesmal ist ein Parser-Kombinator.
Letztes Mal habe ich JIT Library eingeführt, aber ich habe es mit den folgenden Worten beendet.
Wenn Sie es mit einem Parser-Kombinator implementieren und kombinieren, können Sie mit JIT ein kleines Sprachverarbeitungssystem erstellen.
Ja, ich habe es dort eilig gemacht. Parser-Kombinator-Bibliothek. Sein Name ist ** Parsek **. Parsek, nicht Parsec.
Die Schnittstelle basiert auf Parsimmon, aber die Implementierung ist völlig einzigartig. Die API ist nicht so umfangreich, kann aber so verwendet werden, wie sie ist. Es ist einfach, eine Schnittstelle hinzuzufügen. Fügen Sie sie also nach Bedarf hinzu.
Es wird lange dauern, also werde ich den Artikel in zwei Teile teilen.
Lassen Sie uns diesmal die arithmetische Grammatik mit vier Regeln analysieren und einen AST (Abstract Syntax Tree) erstellen. Das nächste Mal werde ich endlich JIT kompilieren und ausführen.
Eine Bibliothek zum Kombinieren kleiner (einfacher) Parser, um einen großen Parser zu erstellen. Ich werde die Details anderen Artikeln überlassen, aber lassen Sie uns dies verstehen, während wir uns das folgende Beispiel ansehen.
Dieses Mal werde ich den Geschmack ändern und anhand einer Probe erklären. Die Stichprobe ist eine Operation mit vier Regeln und einer positiven Ganzzahl (natürliche Zahl). Negative Zahlen werden der Einfachheit halber nicht behandelt (Ergebnisse können negativ sein).
Normalerweise werden wir hier über BNF und PEG sprechen, aber sie ignorieren. Bewegen Sie sich zunächst durch die Probe.
using Parsek
Die Parser-Kombinator-Bibliothek ist nicht standardmäßig integriert. Verwenden wir sie also. Außerdem wird die Bibliothek als Klasse bereitgestellt. Lassen Sie uns sie also instanziieren.
using Parsek;
var $ = new Parsek();
Sie können $ als Variablennamen verwenden.
Lassen Sie mich nacheinander ein Beispiel geben.
Definieren wir zunächst eine positive Ganzzahl. Dies ist der erste kleine (einfache) Parser. Erstens ist es ein regulärer Ausdruck. Nun, es ist nicht so schwierig, also ist es leicht zu verstehen.
Die einzige Gefahr besteht darin, dass der Motor (= Dämonenauto), den Sie verwenden, nicht POSIX NFA ** ist. Sie müssen also den Motor schreiben, der länger passt. Einfach ausgedrückt, im folgenden Beispiel stimmt "123" richtig mit "123" überein, aber das Gegenteil ("/ [0-9] | [1-9] [0-9] * /" ) Stimmt mit dem ersten geschriebenen "[0-9]" überein und stoppt die Suche, so dass es "1" ist und nicht mit "23" übereinstimmt. Lass uns aufpassen.
var number = $.regex(/[1-9][0-9]*|[0-9]/);
Dieser Parser "number" kann jetzt Zahlen analysieren (die Zeichenfolge, in die sie geschrieben sind). Machen wir das.
Die eigentliche Analyse erfolgt mit der Methode parseAll (). Es gibt auch parse (), aber dies ist eine Methode, die auch dann erfolgreich ist, wenn sie in der Mitte endet und normalerweise intern verwendet wird. Im Fall von "parseAll ()" ist die gesamte Analyse abgeschlossen, die Nachbearbeitung wird durchgeführt und das Ergebnis wird zurückgegeben.
using Parsek;
var $ = new Parsek();
var number = $.regex(/[1-9][0-9]*|[0-9]/);
System.println(number.parseAll("0")); // => {"position":1,"status":1,"value":"0"}
System.println(number.parseAll("10")); // => {"position":2,"status":1,"value":"10"}
System.println(number.parseAll("129")); // => {"position":3,"status":1,"value":"129"}
System.println(number.parseAll("abc")); // => {"position":0,"status":0,"value":null}
System.println(number.parseAll("0129")); // => {"position":1,"status":0,"value":null}
Der Rückgabewert "position" ist die Abschlussposition der analysierten Zeichenfolge, "status" ist der Erfolg / Misserfolg (1 ist der Erfolg) und "value" ist die Zeichenfolge, die tatsächlich analysiert wurde. Wie Sie sehen können, ist "value" "null", wenn dies fehlschlägt.
Aber wenn Sie genau hinschauen, ist "Wert" eine Zeichenfolge. Es ist natürlich, weil es nur eine Zeichenkette interpretiert. Hier ist die Methode, die in "Wert" konvertiert wird, ".map ()". Geben Sie die Konvertierungsfunktion wie folgt an.
using Parsek;
var $ = new Parsek();
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(&(value) => Integer.parseInt(value));
System.println(number.parseAll("129")); // => {"position":3,"status":1,"value":129}
Es wurde ein numerischer Wert. Im obigen Fall übergeben Sie nur den Wert, sodass die direkte Übergabe von "Integer.parseInt" identisch ist.
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
Dies ist prägnanter.
Da die Priorität je nach Bediener unterschiedlich ist, teilen Sie sie in zwei Teile.
+ Oder -* Oder / oder %Eine bequeme Möglichkeit, das einzelne Zeichen oder zu interpretieren, ist "$ .oneOf ()". Verwenden Sie es wie folgt.
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
Es ist einfach. Lass es uns gleich versuchen.
using Parsek;
var $ = new Parsek();
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
System.println(addsub.parseAll("+")); // => {"position":1,"status":1,"value":"+"}
System.println(addsub.parseAll("-")); // => {"position":1,"status":1,"value":"-"}
System.println(addsub.parseAll("*")); // => {"position":0,"status":0,"value":null}
System.println(muldiv.parseAll("*")); // => {"position":1,"status":1,"value":"*"}
System.println(muldiv.parseAll("/")); // => {"position":1,"status":1,"value":"/"}
System.println(muldiv.parseAll("%")); // => {"position":1,"status":1,"value":"%"}
System.println(muldiv.parseAll("a")); // => {"position":0,"status":0,"value":null}
Wie erwartet.
Eine andere Sache, lassen Sie uns die Klammern interpretieren, die für die numerische Berechnung notwendig sind. Der Parser, der einer bestimmten Zeichenfolge entspricht, verwendet $ .string () `. Hier ist es ein Zeichen, aber jede Zeichenfolge ist in Ordnung.
var lbr = $.string("(");
var rbr = $.string(")");
Dies funktioniert auch gut, wenn Sie es versuchen. Versuchen wir es mit einem anderen String, um den Effekt von $ .string () zu sehen.
using Parsek;
var $ = new Parsek();
var lbr = $.string("(");
var rbr = $.string(")");
var hoge = $.string("hoge");
System.println(lbr.parseAll("(")); // => {"position":1,"status":1,"value":"("}
System.println(lbr.parseAll(")")); // => {"position":0,"status":0,"value":null}
System.println(rbr.parseAll("(")); // => {"position":0,"status":0,"value":null}
System.println(rbr.parseAll(")")); // => {"position":1,"status":1,"value":")"}
System.println(hoge.parseAll("hoge")); // => {"position":4,"status":1,"value":"hoge"}
System.println(hoge.parseAll("fuga")); // => {"position":0,"status":0,"value":null}
Sie können sehen, dass es richtig übereinstimmt.
Jetzt haben Sie ein kleines (einfaches) Parser-Tool.
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
var lbr = $.string("(");
var rbr = $.string(")");
Kombinieren wir diese. Hier ist die PEG. BNF ist in Ordnung, aber PEG ist besser für Kombinatoren geeignet. Wenn Sie nicht zeigen, dass die Grammatik so ist, wissen Sie nicht, was Sie tun. Ich werde die Bedeutung einzeln ansprechen.
number <- regex(/[1-9][0-9]*|[0-9]/)
addsub <- '+' / '-'
muldiv <- '*' / '/' / '%'
lbr <- '('
rbr <- ')'
expression <- term (addsub term)*
term <- factor (muldiv factor)*
factor <- number / (lbr expression rbr)
Das PEG-priorisierte Auswahlsymbol "/" und die Teilungsspezifikation "/" sind verwirrend, aber Sie können sie sehen, indem Sie genau hinschauen.
Es gibt sowohl Top-Down als auch Bottom-Up, aber hier werden wir den Parser von unten nach oben erstellen.
factor
Erstens ist "Faktor".
factor <- number / (lbr expression rbr)
"Faktor" kann "Zahl" oder "lbr Ausdruck rbr" sein. Sie können es so wie es ist im Programm ablegen. Die folgenden Methoden werden hier verwendet.
expression noch nicht definiert wurde, verwenden Sie $ .lazy (), um es zu verzögern. Wenn Sie $ .lazy () verwenden, wird ein Parser erstellt, wenn er tatsächlich ausgewertet wird.$ .Seq () gibt an, dass mehrere Dinge aufeinander folgen, z. B. lbr expression rbr.Jetzt lass uns schreiben. Deklarieren Sie "Ausdruck" nur im Voraus.
var expression;
var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr)));
term
Als nächstes kommt "Begriff".
term <- factor (muldiv factor)*
Dies bedeutet, dass auf "Faktor" 0 (oder öfter) "(Muldiv-Faktor)" folgt. Da es 0 Mal erlaubt ist, ist es in Ordnung, dass nichts weitergeht. Das Anordnen wie "Muldiv-Faktor" bedeutet, dass es das gleiche wie der vorherige "lbr-Ausdruck rbr" ist und stetig ist. Die hier verwendete Methode ist wie folgt.
Definieren wir es.
var term = $.seq(factor, $.seq(muldiv, factor).many());
Sie haben jetzt "Begriff" definiert.
expression
Schließlich "Ausdruck". Die Form ist die gleiche wie "Begriff".
expression <- term (addsub term)*
Schreiben wir es so wie es ist.
expression = $.seq(term, $.seq(addsub, term).many());
Jetzt haben Sie einen Parser. Lass uns versuchen zu analysieren!
Ich werde den gesamten Quellcode einmal setzen. Das ist nicht so sehr.
using Parsek;
var $ = new Parsek();
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
var lbr = $.string("(");
var rbr = $.string(")");
var expression;
var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr)));
var term = $.seq(factor, $.seq(muldiv, factor).many());
expression = $.seq(term, $.seq(addsub, term).many());
// parse expression!
System.println(expression.parseAll("1+2*3+2*(14-2)"));
// => {"position":14,"status":1,"value":[[1,{}],[["+",[2,[["*",3]]]],["+",[2,[["*",["(",[[14,{}],[["-",[2,{}]]]],")"]]]]]]]}
System.println(expression.parseAll("1+2*3+2*(14-2-)"));
// => {"position":7,"status":0,"value":null}
Der erste erweist sich als erfolgreich (wenn auch lange). Es ist schwer, die Ergebnisse zu lesen, aber lassen Sie uns dies später gestalten. Und Sie können sehen, dass der zweite fehlschlägt. Das liegt daran, dass das letzte (14-2-) keiner der Regeln entspricht.
Formatieren wir dieses Ergebnis. Das, was funktioniert, ist ".map ()", das in "number" verwendet wird.
Zuerst der Teil $ .seq (lbr, expression, rbr). $ .seq () gibt das resultierende Array als Wert zurück. Der Klammerausdruck benötigt keine Klammern als Wert, und nur das Ergebnis des Ausdrucks im Inneren ist ausreichend. Ändern Sie es also wie folgt.
var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr).map(&(value) => value[1])));
Nach der Änderung ist das Ergebnis wie folgt.
System.println(expression.parseAll("1+2*3+2*(14-2)"));
// => {"position":14,"status":1,"value":[[1,{}],[["+",[2,[["*",3]]]],["+",[2,[["*",[[14,{}],[["-",[2,{}]]]]]]]]]]}
Es ist etwas kürzer.
term、expression
Als nächstes kommen "Begriff" und "Ausdruck". Hier formatieren wir es in Form von AST (Abstract Syntax Tree) für eine spätere Analyse. Da es sich im Grunde genommen um einen binären Operator handelt, erstellen Sie ein Objekt, das aus LHS (linke Seite = linke Seite), RHS (rechte Seite = rechte Seite) und Operator (Operator) besteht.
Ändern Sie nun "$ .seqMap ()" anstelle von "$ .seq ()". Es ist wie eine Kombination aus $ .seq () und .map (), einer praktischen Methode, die die Ergebnisliste als Argument verwendet und die als letztes Argument angegebene Funktion aufruft. Ich benutze es so.
var term = $.seqMap(factor, $.seq(muldiv, factor).many(), &(first, rest) => {
var expr = first;
for (var i = 0, l = rest.length(); i < l; ++i) {
expr = { lhs: expr, op: rest[i][0], rhs: rest[i][1] };
}
return expr;
});
first ist das Ergebnis von factor und rest ist das Ergebnis von$ .seq (muldiv, factor) .many (). "Rest" ist also ein Array der Form "[Operator, rechte Seite]" für jedes Element (es kann ein leeres Array sein). Es ist zu einem AST geformt. Infolgedessen wird so etwas wie "2 * 3 * 4" wie folgt formatiert.
rest ist [['*', 3], ['*', 4]]2 wird in expr eingegebenDer AST hat eine Form, in der der linke Zweig wächst (dies wird als linke Verbindung bezeichnet). Alle Operatoren sind diesmal linksassoziativ.
Da expression auch gleich ist, schreiben wir es auf die gleiche Weise. Der Inhalt ist genau der gleiche, also machen wir es zu einer Funktion und verwenden sie.
function makeAST(first, rest) {
var expr = first;
for (var i = 0, l = rest.length(); i < l; ++i) {
expr = { lhs: expr, op: rest[i][0], rhs: rest[i][1] };
}
return expr;
}
var term = $.seqMap(factor, $.seq(muldiv, factor).many(), makeAST);
expression = $.seqMap(term, $.seq(addsub, term).many(), makeAST);
Ich fühle mich erfrischt.
Dann ist es eine Reihe von Programmen. Mit nur dieser Definition können Sie vier Regeloperationen analysieren (wobei die Operatorpriorität berücksichtigt wird). Es ist wunderbar!
using Parsek;
function makeAST(first, rest) {
var expr = first;
for (var i = 0, l = rest.length(); i < l; ++i) {
expr = { lhs: expr, op: rest[i][0], rhs: rest[i][1] };
}
return expr;
}
var $ = new Parsek();
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
var lbr = $.string("(");
var rbr = $.string(")");
var expression;
var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr).map(&(value) => value[1])));
var term = $.seqMap(factor, $.seq(muldiv, factor).many(), makeAST);
expression = $.seqMap(term, $.seq(addsub, term).many(), makeAST);
// test
System.println(expression.parseAll("1+2*3+2*(14-2)").value.toJsonString(true));
Das Ergebnis ist so. Es funktioniert!
"lhs": {
"lhs": 1,
"op": "+",
"rhs": {
"lhs": 2,
"op": "*",
"rhs": 3
}
},
"op": "+",
"rhs": {
"lhs": 2,
"op": "*",
"rhs": {
"lhs": 14,
"op": "-",
"rhs": 2
}
}
Jetzt haben Sie den gewünschten AST. Nächstes Mal werde ich das interpretieren und laufen lassen. Ich werde auch die JIT-Bibliothek verwenden, die ich erstellt habe!
Bis zum nächsten Mal!