** "Sieht aus wie JavaScript, Gehirn (Inhalt) ist Ruby, (Stabilität ist AC / DC)" ** Skriptsprache Kinx ). Diese Zeit ist auch ein Parser-Kombinator.
Vor kurzem habe ich es mit Kinx Library-Parser Combinator (Teil 2) ausgeführt. Was ist diesmal?
Ja, ich möchte die Schnittstelle vorstellen. Es tut mir leid, ich habe das letzte Mal vergessen.
Parsek
Instanzen der Klasse "Parsek" haben die folgenden Methoden: Das $ in der Anweisung gibt die tatsächliche Parsek-Instanz an, die instanziiert wurde.
Die folgenden vordefinierten Parser sind bereits in der Instanz der Parsek-Klasse vorhanden.
| Vordefinierter Parser | Inhalt |
|---|---|
| $.eof | Ein Parser, der erfolgreich ist, wenn es sich um einen EOF handelt. |
| $.any | Ein Parser, der mit einem einzelnen Zeichen erfolgreich ist. |
| $.all | Ein Parser, der alles bis zum Ende verarbeitet und erfolgreich ist. |
| $.index | Gibt die aktuelle Position zurück ({ offset, line, column}). Versatz ist 0 Startpunkt, Linie/Spalte ist ein Ausgangspunkt. |
| $.letter | $.regex(/[a-zA-Z]/)Gleich wie. |
| $.letters | $.regex(/[a-zA-Z]*/)Gleich wie. |
| $.digit | $.regex(/[0-9]/)Gleich wie. |
| $.digits | $.regex(/[0-9]*/)Gleich wie. |
| $.whitespace | $.regex(/\s+/)Gleich wie. |
| $.optWhitespace | $.regex(/\s*/)Gleich wie. |
| $.cr | $.string("\r")Gleich wie. |
| $.lf | $.string("\n")Gleich wie. |
| $.crlf | $.string("\r\n")Gleich wie. |
| $.newline | $.alt($.crlf, $.lf, $.cr)Gleich wie. |
| $.end | $.alt($.newline, $.eof)Gleich wie. |
Instanzen der Klasse "Parsek" können Parser mit den folgenden Methoden generieren:
| Parser-Generierungsfunktion | Inhalt |
|---|---|
| $.string(str) | strErstellt einen Parser, der erfolgreich ist, wenn er mit der in angegebenen Zeichenfolge übereinstimmt. |
| $.regex(re, groupIndex) | reErstellt einen Parser, der erfolgreich ist, wenn er mit dem in angegebenen regulären Ausdruck übereinstimmt. Wert istgroupIndexDas Erfassungsergebnis der in angegebenen Gruppe wird eingegeben. |
| $.succeed(result) | resultSo erstellen Sie einen Parser, der immer erfolgreich ist. |
| $.fail(message) | messageErstellen Sie einen Parser, der fehlschlägt, indem Sie eine Nachricht hinterlassen. |
| $.oneOf(chars) | charsErstellen Sie einen Parser, der erfolgreich ist, wenn er mit einem darin enthaltenen Zeichen übereinstimmt. |
| $.noneOf(chars) | charsErstellen Sie einen Parser, der erfolgreich ist, wenn er nicht mit einem darin enthaltenen Zeichen übereinstimmt. |
| $.sepBy(content, separator) | contentEine Zeichenfolge, mit der analysiert werden kannseparatorErstellen Sie einen Parser, der das Ergebnis geteilt durch das übereinstimmende Ergebnis zurückgibt. |
| $.sepBy1(content, separator) | sepByIst erlaubt 0,sepBy1Schlägt fehl, wenn mindestens eine nicht übereinstimmt. |
| $.lazy(description, f) | fGeben Sie eine Funktion an, an die ein Parser zurückgegeben wird, und generieren Sie einen Parser, wenn er zum ersten Mal verwendet wird. |
| $.alt(...parsers) | Erstellt einen Parser, der erfolgreich ist, wenn er mit einem der angegebenen Parser übereinstimmt. Die Bewerbung erfolgt in der angegebenen Reihenfolge. |
| $.takeWhile(predicate) | Das nächste Zeichen istpredicateErstellen Sie einen Parser, der weiterhin erfolgreich ist, solange er wahr ist. |
| $.seq(...parsers) | Erstellt einen Parser, der erfolgreich ist, wenn mehrere angegebene Parser der Reihe nach übereinstimmen. Die Ergebnisse werden als Array aller Ergebnisse zurückgegeben. |
| $.seqMap(...parsers, mapf) | Erstellt einen Parser, der erfolgreich ist, wenn mehrere angegebene Parser der Reihe nach übereinstimmen. Das Ergebnis ist ein Array aller Ergebnisse, gibt jedoch den Wert zurück, der von der von mapf angegebenen Funktion zurückgegeben wird. |
ParsekParser
Der von der Methode der Klasse "Parsek" generierte Parser ist eine Instanz der Klasse "ParsekParser". Diese Klasse definiert Methoden zum Verketten von Parsern.
Wenn alle Parser bereit sind, führen Sie die Analyse mit der folgenden Methode aus.
| Methode | Inhalt |
|---|---|
| parser.parseAll(target) | targetGegenparserZum Parsen mit. |
| Parser-Generierungsfunktion | Inhalt |
|---|---|
| parser.desc(description) | parserStellen Sie die Nachricht ein, die angezeigt werden soll, wenn das Parsen nach nicht erfolgreich ist. |
| parser.or(nextParser) | parserBeim Parsen vonnextParserErstellen Sie einen Parser, der dies versucht. |
| parser.and(nextParser) | parserWenn es Ihnen gelingt, zu analysierennextParserErstellen Sie einen Parser, der ausgeführt werden soll. Das Ergebnis wird als Array zurückgegeben. |
| parser.then(nextParser) | parserWenn es Ihnen gelingt, zu analysierennextParserErstellen Sie einen Parser, der ausgeführt werden soll. Ergebnis istnextParserGib den zurückparserDas Ergebnis von wird ignoriert. |
| parser.skip(nextParser) | parserWenn es Ihnen gelingt, zu analysierennextParserErstellen Sie einen Parser, der ausgeführt werden soll. Ergebnis istparserGib den zurücknextParserDas Ergebnis von wird ignoriert. |
| parser.many() | parserErstellen Sie einen Parser, der das Auftreten von 0 oder mehr Mal analysiert. |
| parser.many1() | parserErstellen Sie einen Parser, der mehr als einmal analysiert. |
| parser.times(min, max) | parserAberminMehr als einmalmaxErstellen Sie einen Parser, der das Erscheinungsbild nicht mehr als einmal wiederholt analysiert. ..maxWenn weggelassen wird, einfachminErfolg bei mehrmaliger Häufigkeit. |
| parser.sepBy(separator) | parserEine Zeichenfolge, mit der analysiert werden kannseparatorErstellen Sie einen Parser, der das Ergebnis geteilt durch das übereinstimmende Ergebnis zurückgibt. |
| parser.sepBy1(separator) | sepByIst erlaubt 0,sepBy1Schlägt fehl, wenn mindestens eine nicht übereinstimmt. |
| parser.map(f) | parserVerwenden Sie das Ergebnis der oben von der Funktion f konvertierten. |
| parser.chain(f) | parserÜbergeben Sie das Ergebnis von an die Funktion f und verbinden Sie die Parser, um den von f zurückgegebenen neuen Parser als nächsten Parser zu verwenden. |
| parser./(nextParser) | parser.or(nextParser)Ein anderer Name für. |
| parser.+(nextParser) | nextParserOhne Angabeparser.+()Bei Verwendung alsparser.many1()Ein anderer Name für.nextParserWenn Sie angebenparser.and(nextParser)Ein anderer Name für. |
| parser.*() | parser.many()Ein anderer Name für. |
Packrat Parsing
Unterstützt Packrat Parsing.
Parser-Kombinatoren fahren normalerweise mit der Analyse auf dem Backtrack fort. Mit anderen Worten, zum Beispiel im Fall von "$ .alt (a, b, c)", wenn der Parser von "a" ausfällt, fährt er als "b" fort, aber der gleiche Parser kann in der Mitte viele Male wiederholt werden.
Daher kann beim Zurückverfolgen eine Leistungsverbesserung erwartet werden, indem einige Ergebnisse zwischengespeichert und wiederverwendet werden, indem die Eigenschaft verwendet wird, dass ** bei Analyse an derselben Stelle und unter denselben Bedingungen dasselbe Ergebnis erzielt wird **. .. Es ist ein Memo.
Parsek unterstützt diese Funktion. Übrigens kann es deaktiviert werden, indem beim Erstellen einer Parsek-Instanz im Konstruktor "{disablePackratParsing: true}" angegeben wird.
Lassen Sie uns seine Leistung mit einem Benchmark sehen. Informationen zur Grammatik, die eine enorme Anzahl von Rückverfolgungen verursacht, finden Sie unter hier. Die Grammatik ist unten.
S <- A
A <- P "+" A / P "-" A / P
P <- "(" A ")" / "1"
Dadurch wird die folgende Zeichenfolge analysiert:
(((((((((((((1)))))))))))))
Die Erklärung ist leicht zu verstehen, daher werde ich sie so zitieren, wie sie ist.
Das Wesentliche an dieser Kombination aus Regel und Zeichenfolge ist, dass alle A- und P-Kombinationen durchlaufen werden müssen, bevor sie endgültig analysiert werden. Mit anderen Worten, der schlimmste Fall eines Backtracks kann fast reproduziert werden. Wenn Sie also offen zurückverfolgen, sollte sich die Verarbeitungszeit exponentiell mit der Anzahl der Klammerkorrespondenzen erhöhen.
Nein, es ist unglaublich.
Hier ist also der Quellcode für den Benchmark. Der Parser selbst ist derselbe, daher wird der gleiche Test mit dem Parser "$ D" mit "{disablePackratParsing: true}" und dem Parser "$ E" mit aktiviertem Parser durchgeführt.
using Parsek;
var $E = new Parsek();
var $D = new Parsek({ disablePackratParsing: true });
var tmr = new SystemTimer();
// rule:
// S <- A
// A <- P "+" A / P "-" A / P
// P <- "(" A ")" / "1"
// input:
// (((((((((((((1)))))))))))))
function generateParser($) {
var S, A, P;
S = $.lazy(&() => A);
A = $.lazy(&() => $.alt($.seq(P, $.string('+'), A), $.seq(P, $.string('-'), A), P));
P = $.alt($.seq($.string('('), A, $.string(')')), $.string('1'));
return S;
}
function test($) {
for (var i = 0; i <= 10; ++i) {
tmr.restart();
var r = generateParser($).parseAll(('(' * i) + '1' + (')' * i));
var elapsed = tmr.elapsed();
System.println(["%8.5f" % elapsed, r]);
}
}
test($E);
test($D);
Machen wir das!
Wenn gültig
[" 0.00090", {"position":1,"status":1,"value":"1"}]
[" 0.00041", {"position":3,"status":1,"value":["(","1",")"]}]
[" 0.00044", {"position":5,"status":1,"value":["(",["(","1",")"],")"]}]
[" 0.00061", {"position":7,"status":1,"value":["(",["(",["(","1",")"],")"],")"]}]
[" 0.00083", {"position":9,"status":1,"value":["(",["(",["(",["(","1",")"],")"],")"],")"]}]
[" 0.00055", {"position":11,"status":1,"value":["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"]}]
[" 0.00061", {"position":13,"status":1,"value":["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"]}]
[" 0.00071", {"position":15,"status":1,"value":["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"]}]
[" 0.00200", {"position":17,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 0.00101", {"position":19,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 0.00196", {"position":21,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
Wenn deaktiviert
[" 0.00022", {"position":1,"status":1,"value":"1"}]
[" 0.00034", {"position":3,"status":1,"value":["(","1",")"]}]
[" 0.00097", {"position":5,"status":1,"value":["(",["(","1",")"],")"]}]
[" 0.00353", {"position":7,"status":1,"value":["(",["(",["(","1",")"],")"],")"]}]
[" 0.01142", {"position":9,"status":1,"value":["(",["(",["(",["(","1",")"],")"],")"],")"]}]
[" 0.02686", {"position":11,"status":1,"value":["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"]}]
[" 0.09525", {"position":13,"status":1,"value":["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"]}]
[" 0.26821", {"position":15,"status":1,"value":["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"]}]
[" 0.72229", {"position":17,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 2.44629", {"position":19,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 7.48334", {"position":21,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
Wenn Packrat Parsing aktiviert ist, werden 10 Klammern innerhalb von 2 Millisekunden vervollständigt. Wenn es dagegen deaktiviert ist, dauert es 7,5 Sekunden, bis die letzten 10 Klammern erreicht sind.
Parser-Kombinator, es ist bequem, dies zu versuchen. Ich habe es nicht viel benutzt, aber ich denke, ich werde es in Zukunft ein bisschen mehr benutzen. Sie können leicht Zeichenfolgen analysieren, die nicht durch reguläre Ausdrücke ausgedrückt werden können.
Sie können damit ein Sprachverarbeitungssystem erstellen. Kinx verwendet yacc für die Syntaxanalyse und Handschrift für die Phrasenanalyse.
Ursprünglich mag ich die Syntaxanalyse selbst und den handgeschriebenen rekursiven absteigenden Parser, aber ich verwende yacc ausschließlich, weil es schwierig ist, die Grammatikdefinition zu ändern. Der Parser-Kombinator kann jedoch auch eine Phrasenanalyse durchführen, was praktisch ist.
wir sehen uns!