Die Implementierung „*?“ (Lazy „*“) regexp Muster in der kombinatorischen GLR Parsern

Question

Ich habe kombi GLR-Parser implementiert. Unter ihnen gibt es:

• char(·) Parser, verbraucht Zeichen oder Zeichenbereich angegeben.
• many(·) combinator der Parser von null bis unendlich angegebenen Zeiten wiederholt wird.

. Beispiel: "char('a').many()" wird mit einer beliebigen Anzahl von "a"-s einen String passen

Aber many(·) combinator gierig ist, so zum Beispiel char('{') >> char('{') >> char('a'..'z').many() >> char('}') >> char('}') (wo ">>" sequentielle Verkettung von Parsern ist) werden den ganzen "{{foo}}some{{bar}}" Zeichenfolge erfolgreich verbrauchen.

Ich will die faulen Version von many(·) implementieren, die im vorherigen Beispiel verwendet wird, wird nur "{{foo}}" verbrauchen. Wie kann ich das tun?

Edit:

Kann sein, ich verwirrt ya alle. In meinem Programm ist ein Parser eine Funktion (oder „Funktor“ in Bezug auf die C ++), die einen „Schritt“ und kehrt Wald von „Stufen“ akzeptiert. A „Schritt“ kann von OK-Typ sein (das bedeutet, dass ein Teil des Parser Eingabe erfolgreich verbraucht hat) und FAIL-Typ (dh hat der Parser Fehler aufgetreten ist). Es gibt mehrere Arten von Schritten, aber sie sind Hilfs.

Parser = f(Step) -> Collection of TreeNodes of Steps.

Wenn ich also Parse-Eingang, I:

• Compose einfache Parser Funktionen vordefinierte komplexe Parser Funktion darstellt erforderlich Grammatik zu erhalten.

• Form erster Schritt von der Eingabe.

• Geben Sie den ersten Schritt zur komplexen Parser-Funktion.

• Filter TreeNodes mit den Schritten, so dass nur OK Einsen (oder mit minimalem FAIL-s, wenn Fehler in der Eingabe waren).

• Sammeln von Informationen aus den Schritten, die gelassen wurden.

Answer 1

Betrachten wir den regulären Ausdruck <.*?> und den Eingang <a>bc<d>ef. Dies sollte finden <a> und keine andere Spiele, nicht wahr?

Betrachten wir nun den regulären Ausdruck <.*?>e mit den gleichen Eingang. Dies sollte <a>bc<d>e, Recht finden?

Dies stellt ein Dilemma. Im Interesse des Benutzers, wollen wir das Verhalten des combinator >> in Bezug auf seinen zwei Operanden zu verstehen. Dennoch gibt es keine Möglichkeit den zweiten Parsers des Verhalten in Bezug darauf, was die ersten Funde zu erzeugen.

Eine Antwort ist für jeden Parser eines sequence aller Parsen zu produzieren, vorzugsweise bestellt, anstatt der ungeordneten Menge aller Parser. Greedy passende Matches würden wieder sortiert längste kürzeste; Nicht-gierig, kürzeste längst.

Answer 2

Ich habe implementiert und habe GLR-Parser seit 15 Jahren unter Verwendung als Sprache Frontends für ein Programm Transformationssystem.

Ich weiß nicht, was ein „kombinatorischer GLR-Parser“ ist, und ich bin nicht vertraut mit Ihrer Notation also ist mir nicht ganz sicher, wie es zu interpretieren. Ich gehe davon aus dem eine Art curried Funktion Notation ist? Ich stelle mir deine combinator Regeln gleichwertig sind eine grammer in Bezug auf Terminal Zeichen definining, wo entspricht Grammatikregeln „char (‚a‘) viele.“

 char = "a" ;
 char = char "a" ;

GLR-Parser, in der Tat, produziert alle möglichen Parsen. Der Schlüssel zum Verständnis GLR-Parsing ist seine psuedo-parallele Verarbeitung aller möglichen parst. Wenn Ihr „Kombinatoren“ multiple Parsen vorschlagen kann (das heißt, sie produzieren Grammatikregeln Art der obigen Äquivalent), und Sie in der Tat haben sie zu einem GLR-Parser verbunden sind, werden sie alle ausprobiert werden, und nur die Sequenzen von Produktionen, die Fliese der Text wird überleben (alle gültigen parsess Sinn, zum Beispiel zweideutig Parsen) werden überleben.

Wenn Sie in der Tat einen GLR-Parser, diese Sammlung aller möglichen Parsen umgesetzt haben sollten Sie waren sehr klar. Die Tatsache, dass es nicht Hinweise, was Sie implementiert haben, ist kein GLR-Parser.

Fehlerbehandlung mit einem GLR-Parser ist möglich, wie bei jeder anderen Parsing-Technologie. Was wir tun, ist die Menge der Live-Parsen vor dem Punkt des Fehlers halten; wenn ein Fehler gefunden wird, versuchen wir (in psuedo-parallel, die GLR-Parsing Maschinen so einfach macht, wenn er es richtig gebogen) alle die folgenden: a) die säumige Token, b) das Löschen aller Token eingefügt, die im Wesentlichen FOLLOW (x) sind wobei x Live-Parsing. Im Wesentlichen löschen Sie das Token oder einen von einer Live-Parse erwartet ein. Wir wenden uns dann den GLR-Parser wieder los. Nur die gültigen Parsen (zum Beispiel Reparaturen) werden überleben. Wenn die aktuellen Token nicht verarbeitet werden können, die Verarbeitung die Parser den Stream mit dem Token gelöschten überlebt. Im schlimmsten Fall, Fehler das GLR-Parser Recovery-Enden nach oben wirft alle Token EOF entfernt. Ein gravierender Nachteil ist die Laufzeit des GLR-Parser ziemlich radikal wächst Fehler beim Parsen; wenn es an einem Ort viele sind, kann die Fehlerbehebungszeit durch die Decke gehen.

Answer 3

Wird kein GLR-Parser erzeugen alle möglichen Parsen des Eingangs? Dann die Mehrdeutigkeit der Lösung ist eine Frage der Kommissionierung der Parse Sie bevorzugen. Um das zu tun, nehme ich an die Elemente des Parsewald müssen gekennzeichnet werden nach, welche Art von combinator produziert sie, eifrig oder faul. (Sie können nicht die Mehrdeutigkeit beheben inkrementell, bevor Sie haben alle den Eingang zu sehen ist, im Allgemeinen.)

(Diese Antwort basiert auf meiner schwache Erinnerung und vage mögliches Mißverständnis von GLR-Parsing. Hoffentlich jemand Experten wird kommen durch.)

Answer 4

Nicht-gierige Funktionalität ist nichts anderes als ein Begriffsklärung Mechanismus. Wenn Sie wirklich eine verallgemeinerte Parser haben (was nicht Begriffsklärung benötigt seine Ergebnisse zu produzieren), dann „genügsam“ ist bedeutungslos; die gleichen Ergebnisse zurückgegeben werden, ob ein Operator „genügsam“ ist.

Nicht-gierige Begriffsklärung Verhalten zum vollständigen Satz von Ergebnissen durch einen generali Parser bereitgestellt angewandt werden könnte. Arbeiten von links nach rechts, Filter der mehrdeutigen Untergruppen zu einem nicht-gierigen Betreibern entsprechend das kürzeste Spiel zu verwenden, die zu einem erfolgreichen Parse der restlichen Eingabe noch führten.