GLL Parser Combinator oder Generator in/für C oder C++ [closed]

Gibt es eine bestehende Implementierung der GLL Algorithmus, entweder in Form von Parser-Kombinatoren (bevorzugt) oder als Parser-Generator für C oder C++?

Meine Anforderungen sind, dass die Ausgabe ein Shared Packed Parse Forest (SPPF) ist, den ich später mit semantischen und/oder kontextuellen Regeln disambiguieren kann. Es gibt andere Parsing-Algorithmen wie GLR, die mit allgemeinen kontextfreien Grammatiken umgehen können, aber alle GLR-Parser-Generatoren, die ich finden konnte, geben entweder den ersten erfolgreichen Parsing-Baum zurück oder schlagen fehl, wenn am Ende eine Mehrdeutigkeit verbleibt.

Was wäre, wenn du es ausprobierst GLL Kombinatoren? Obwohl es Scala verwendet, können Sie mithilfe von “dünne” Wrapper dafür schreiben JNI.

GLL Kombinatoren ist ein Framework zur Implementierung von GLL-Parsing-Algorithmus
(Scott und Johnstone, LDTA 2009) in funktionaler Weise. Genauer gesagt verwendet das Framework atomare Parser-Kombinatoren, um Grammatiken zusammenzustellen, die dann unter Verwendung des GLL-Algorithmus ausgewertet werden. Das Framework bietet eine Syntax für diese Aufgabe, die fast identisch mit der des in Scala integrierten Parser-Combinator-Frameworks ist. Zum Beispiel können wir die klassische “Klammern-Grammatik” mit GLL-Kombinatoren rendern:

lazy val expr: Parser[Any] = (
    "(" ~ expr ~ ")"
  | ""
)

Wie die Typenanmerkung impliziert, expr verweist auf eine Instanz des Typs
Parser[Any]. Das heißt, ein atomarer Parser, der einige Eingaben verbraucht und einen Wert vom Typ zurückgibt Any. Wir können diesen Parser gegen a aufrufen String wie folgt eingeben:

expr("((()))")

Dies gibt einen Wert vom Typ zurück Stream[Result[Any]]. Das Result[A] ADT ist wie folgt definiert (für einige Typen A):

• Success[A] — Stellt eine erfolgreiche Analyse dar und enthält den resultierenden Wert.
• Failure — Stellt eine fehlgeschlagene Analyse dar und enthält die relevante Fehlermeldung sowie den Rest des Analysestroms (die Zeichen, die nicht verbraucht wurden).

Wenn ein Ergebnis erfolgreich ist (d. h. eine Instanz von Success[A]), dann werden keine Fehler zurückgegeben. Und so kam es dass der Stream zurückgegeben wird vollständig homogen, enthält entweder Success oder Failure, aber nicht beide. EIN Stream wird anstelle eines einzelnen Werts zurückgegeben, um Mehrdeutigkeiten in der Grammatik zu berücksichtigen (siehe unten).

Es ist erwähnenswert, dass GLL eine Form von ist rekursive Abstiegsanalyse. Es hat alle Vorteile des herkömmlichen rekursiven Abstiegs, einschließlich eines intuitiven Kontrollflusses, willkürlicher Positionierung semantischer Aktionen und überlegener Fehlermeldungen. Tatsächlich ist es die Tatsache, dass GLL rekursiv absteigt, was es ermöglicht, es unter Verwendung von atomaren Kombinatoren zu implementieren. Andere Algorithmen, die die gleichen Fähigkeiten wie GLL haben (wie GLR, Earley Parsing usw.), sind aufgrund ihres höchst unintuitiven Steuerflusses grundsätzlich nicht mit dem Kombinatormodell kompatibel. Beim GLL-Parsing folgt der Kontrollfluss dem der Grammatik, wie es bei herkömmlichen Parser-Kombinatoren oder jeder anderen Form von rekursivem Abstieg der Fall ist.