Analysieren von beliebigen kontextfreien Grammatiken, meist kurze Ausschnitte

Ich möchte benutzerdefinierte domänenspezifische Sprachen analysieren. Diese Sprachen ähneln normalerweise mathematischen Notationen (ich analysiere keine natürliche Sprache). Benutzer definieren ihr DSL in einer BNF-Notation wie folgt:

expr ::= LiteralInteger
       | ( expr )
       | expr + expr
       | expr * expr

Eingaben wie 1 + ( 2 * 3 )müssen akzeptiert werden, Eingaben wie 1 +müssen als falsch zurückgewiesen werden und Eingaben wie 1 + 2 * 3müssen als mehrdeutig zurückgewiesen werden.

Eine zentrale Schwierigkeit dabei ist der benutzerfreundliche Umgang mit mehrdeutigen Grammatiken. Die Grammatik so einzuschränken, dass sie eindeutig ist, ist keine Option: So ist die Sprache - die Idee ist, dass Autoren lieber Klammern weglassen, wenn sie nicht notwendig sind, um Mehrdeutigkeiten zu vermeiden. Solange ein Ausdruck nicht mehrdeutig ist, muss ich ihn analysieren, und wenn nicht, muss ich ihn ablehnen.

Mein Parser muss an jeder kontextfreien Grammatik arbeiten, auch an mehrdeutigen, und muss alle eindeutigen Eingaben akzeptieren. Ich benötige den Analysebaum für alle akzeptierten Eingaben. Bei ungültigen oder mehrdeutigen Eingaben möchte ich im Idealfall gute Fehlermeldungen, aber zunächst nehme ich, was ich bekommen kann.

Normalerweise rufe ich den Parser bei relativ kurzen Eingaben mit gelegentlich längeren Eingaben auf. Daher ist der asymptotisch schnellere Algorithmus möglicherweise nicht die beste Wahl. Ich möchte für eine Verteilung von rund 80% Eingaben mit weniger als 20 Symbolen, 19% zwischen 20 und 50 Symbolen und 1% seltenen längeren Eingaben optimieren. Die Geschwindigkeit für ungültige Eingaben ist kein großes Problem. Desweiteren erwarte ich eine Änderung des DSL etwa alle 1000 bis 100000 Eingänge; Ich kann ein paar Sekunden damit verbringen, meine Grammatik vorzubereiten, nicht ein paar Minuten.

Welche Analysealgorithmen sollte ich bei meinen typischen Eingabegrößen untersuchen? Sollte die Fehlerberichterstattung ein Faktor in meiner Auswahl sein, oder sollte ich mich auf das Parsen eindeutiger Eingaben konzentrieren und möglicherweise einen vollständig separaten, langsameren Parser ausführen, um Fehlerrückmeldung zu geben?

(In dem Projekt, in dem ich das benötigte (vor einiger Zeit), habe ich CYK verwendet , das nicht zu schwer zu implementieren war und für meine Eingabegrößen angemessen funktionierte, aber keine sehr schönen Fehler produzierte.)

Der ideale Algorithmus für Ihre Anforderungen ist wahrscheinlich das Generalized LL Parsing (GLL). Dies ist ein sehr neuer Algorithmus (der Artikel wurde 2010 veröffentlicht). In gewisser Weise handelt es sich um den Earley-Algorithmus, der um einen Graph Structured Stack (GSS) erweitert wurde und den LL (1) -Vorgriff verwendet.

Der Algorithmus ist dem einfachen alten LL (1) ziemlich ähnlich, außer dass er Grammatiken nicht ablehnt, wenn sie nicht LL (1) sind: Er probiert nur alle möglichen LL (1) -Parses aus. Für jeden Punkt in der Analyse wird ein gerichteter Graph verwendet. Wenn also ein zuvor behandelter Analysezustand festgestellt wird, werden diese beiden Eckpunkte einfach zusammengeführt. Dies macht es auch für linksrekursive Grammatiken geeignet, im Gegensatz zu LL. Lesen Sie das Papier, um genaue Informationen über das Innenleben zu erhalten (es ist ein gut lesbares Papier, obwohl die Etikettensuppe etwas Ausdauer erfordert).

Der Algorithmus hat eine Reihe klarer Vorteile, die für Ihre Anforderungen relevant sind, gegenüber den anderen allgemeinen Analysealgorithmen (die ich kenne). Erstens ist die Implementierung sehr einfach: Ich denke, nur Earley ist einfacher zu implementieren. Zweitens ist die Leistung ziemlich gut: Tatsächlich wird sie auf Grammatiken, die LL (1) sind, genauso schnell wie LL (1). Drittens ist das Wiederherstellen der Analyse recht einfach, und es kann auch überprüft werden, ob es mehr als eine mögliche Analyse gibt.

Der Hauptvorteil von GLL besteht darin, dass es auf LL (1) basiert und daher bei der Implementierung, beim Entwerfen von Grammatiken und beim Parsen von Eingaben sehr einfach zu verstehen und zu debuggen ist. Darüber hinaus wird die Fehlerbehandlung vereinfacht: Sie wissen genau, wo mögliche Parser gestrandet sind und wie sie möglicherweise fortgesetzt wurden. Sie können die möglichen Parses zum Zeitpunkt des Fehlers und beispielsweise die letzten drei Punkte, an denen die Parses gestrandet sind, problemlos angeben. Sie können stattdessen versuchen, den Fehler zu beheben, und die Produktion, an der der am weitesten entfernte Parser gearbeitet hat, als "abgeschlossen" markieren. Anschließend können Sie prüfen, ob das Parsen fortgesetzt werden kann (z. B. wenn jemand eine Klammer vergessen hat). Sie könnten das sogar für die 5 am weitesten entfernten Parses machen.

Der einzige Nachteil des Algorithmus ist, dass er neu ist, was bedeutet, dass keine gut etablierten Implementierungen verfügbar sind. Dies ist möglicherweise kein Problem für Sie - ich habe den Algorithmus selbst implementiert und es war recht einfach zu tun.

Mein Unternehmen (Semantic Designs) hat GLR-Parser sehr erfolgreich eingesetzt, um mit unserem DMS Software Reengineering Toolkit genau das zu tun, was OP beim Parsen sowohl von domänenspezifischen Sprachen als auch von "klassischen" Programmiersprachen vorschlägt. Dies unterstützt Source-to-Source-Programmtransformationen, die für umfangreiche Programmumstrukturierungen / Reverse Engineering / Forward-Code-Generierung verwendet werden. Dies beinhaltet die automatische Behebung von Syntaxfehlern auf praktische Weise. Auf der Grundlage von GLR und einigen anderen Änderungen (semantische Prädikate, Token-Set-Eingabe statt nur Token-Eingabe ...) haben wir es geschafft, Parser für etwa 40 Sprachen zu erstellen.

Ebenso wichtig wie die Fähigkeit, Instanzen in vollständigen Sprachen zu analysieren, hat sich GLR auch beim Parsen von Regeln für das Umschreiben von Quellen zu Quellen als äußerst nützlich erwiesen . Dies sind Programmfragmente mit viel weniger Kontext als ein vollständiges Programm und sind daher im Allgemeinen mehrdeutig. Wir verwenden spezielle Anmerkungen (z. B. darauf bestehen, dass eine Phrase einer bestimmten Grammatik entspricht), um diese Unklarheiten während / nach dem Parsen der Regeln aufzulösen. Durch die Organisation der GLR-Parsing-Maschinerie und der damit verbundenen Tools erhalten wir Parser zum "freien" Umschreiben von Regeln, sobald wir einen Parser für seine Sprache haben. Die DMS-Engine verfügt über einen integrierten Umschreiberegelanwender, mit dem diese Regeln angewendet werden können, um die gewünschten Codeänderungen vorzunehmen.

Das wahrscheinlich spektakulärste Ergebnis ist die Fähigkeit, C ++ 14 trotz aller Unklarheiten auf der Grundlage einer kontextfreien Grammatik vollständig zu analysieren . Ich stelle fest, dass alle klassischen C ++ - Compiler (GCC, Clang) diese Möglichkeit aufgegeben haben und handgeschriebene Parser verwenden (was es meiner Meinung nach schwieriger macht, sie zu warten, aber sie sind nicht mein Problem). Wir haben diese Maschinerie verwendet, um massive Änderungen an der Architektur großer C ++ - Systeme vorzunehmen.

In Bezug auf die Leistung sind unsere GLR-Parser relativ schnell: Zehntausende Zeilen pro Sekunde. Dies liegt weit unter dem Stand der Technik, aber wir haben keinen ernsthaften Versuch unternommen, dies zu optimieren, und einige der Engpässe liegen in der Zeichenstromverarbeitung (vollständiger Unicode). Um solche Parser zu erstellen, verarbeiten wir die kontextfreien Grammatiken vorab mit etwas, das einem LR (1) -Parsergenerator sehr nahe kommt. Dies läuft normalerweise auf einer modernen Workstation in zehn Sekunden auf großen Grammatiken von der Größe von C ++. Überraschenderweise dauert die Generierung von Lexern für sehr komplexe Sprachen wie COBOL und C ++ ungefähr eine Minute. Einige der über Unicode definierten DFAs werden ziemlich haarig. Ich habe Ruby (mit einer vollständigen Subgrammatik für seine unglaublichen regulären Ausdrücke) nur als Fingerübung gemacht. DMS kann Lexer und Grammatik in ca. 8 Sekunden gemeinsam verarbeiten.

Es gibt viele allgemeine kontextfreie Parser, die mehrdeutige Sätze analysieren können (entsprechend einer mehrdeutigen Grammatik). Sie werden unter verschiedenen Namen geführt, insbesondere Dynamic Programming oder Chart Parser. Der bekannteste und neben dem einfachsten ist wahrscheinlich der von Ihnen verwendete CYK-Parser. Diese Allgemeingültigkeit ist erforderlich, da Sie mehrere Parses verarbeiten müssen und möglicherweise bis zum Ende nicht wissen, ob Sie mit einer Mehrdeutigkeit zu tun haben oder nicht.

Nach allem, was Sie sagen, würde ich denken, dass CYK keine so schlechte Wahl ist. Sie haben wahrscheinlich nicht viel zu gewinnen, wenn Sie Vorhersagbarkeit (LL oder LR) hinzufügen, und es kann tatsächlich Kosten verursachen, wenn Sie Berechnungen unterscheiden, die zusammengeführt und nicht unterschieden werden sollten (insbesondere im LR-Fall). Sie können auch entsprechende Kosten in Bezug auf die Größe des erzeugten Analysewalds verursachen (die möglicherweise eine Rolle bei Mehrdeutigkeitsfehlern spielen). Obwohl ich nicht sicher bin, wie ich die Angemessenheit der ausgefeilteren Algorithmen formal vergleichen soll, weiß ich, dass CYK eine gute gemeinsame Nutzung von Berechnungen ermöglicht.

Nun, ich glaube nicht, dass es viel Literatur über allgemeine CF-Parser für mehrdeutige Grammatiken gibt, die nur eindeutige Eingaben akzeptieren sollten. Ich kann mich nicht erinnern, welche gesehen zu haben, wahrscheinlich, weil selbst für technische Dokumente oder sogar Programmiersprachen syntaktische Mehrdeutigkeiten akzeptabel sind, solange sie auf andere Weise gelöst werden können (z. B. Mehrdeutigkeiten in ADA-Ausdrücken).

Ich frage mich eigentlich, warum Sie Ihren Algorithmus ändern möchten, anstatt sich an das zu halten, was Sie haben. Das könnte mir helfen zu verstehen, welche Art von Veränderung Ihnen am besten helfen könnte. Handelt es sich um ein Geschwindigkeitsproblem, um die Darstellung von Parses oder um die Fehlererkennung und -behebung?

Die beste Möglichkeit, mehrere Parses darzustellen, besteht in einer gemeinsam genutzten Gesamtstruktur, bei der es sich lediglich um eine kontextfreie Grammatik handelt, die nur Ihre Eingaben generiert, jedoch genau dieselben Analysebäume aufweist wie die DSL-Grammatik. Das macht es sehr einfach zu verstehen und zu verarbeiten. Für weitere Details schlage ich vor, dass Sie sich diese Antwort ansehen , die ich auf der Sprachseite gegeben habe. Ich verstehe, dass Sie nicht daran interessiert sind, einen Analysewald zu erhalten, aber eine korrekte Darstellung des Analysewalds kann Ihnen dabei helfen, bessere Aussagen darüber zu machen, wie vieldeutig das Problem ist. Sie können auch entscheiden, ob die Mehrdeutigkeit in bestimmten Fällen keine Rolle spielt (Assoziativität), wenn Sie dies möchten.

Sie erwähnen die Verarbeitungszeitbeschränkungen Ihrer DSL-Grammatik, geben aber keinen Hinweis auf deren Größe (was nicht bedeutet, dass ich mit Zahlen antworten könnte, die Sie gemacht haben).

Einige Fehler können auf einfache Weise in diese allgemeinen CF-Algorithmen integriert werden. Aber ich müsste verstehen, welche Art von Fehlerverarbeitung Sie als positiv empfinden. Möchten Sie einige Beispiele haben?

Es ist mir ein bisschen unangenehm, mehr zu sagen, weil ich nicht verstehe, was wirklich Ihre Motivationen und Einschränkungen sind. Auf der Grundlage dessen, was Sie sagen, würde ich mich an CYK halten (und ich kenne die anderen Algorithmen und einige ihrer Eigenschaften).