Können abstrakte Syntaxbäume in subexponentieller Zeit nicht analysiert werden?

Abstrakte Problembeschreibung

So wie ich es sehe, bedeutet Unparsing, einen Token-Stream aus einem AST zu erstellen, der beim erneuten Parsen einen gleichen AST erzeugt, dh parse(unparse(AST)) = ASThalten sollte.

Dies entspricht dem Auffinden eines gültigen Analysebaums, der denselben AST erzeugen würde.

Die Sprache wird durch eine kontextfreie S-zugeschriebene Grammatik unter Verwendung einer eBNF-Variante beschrieben.

Der Unparser muss also einen gültigen 'Pfad' durch die durchquerten Knoten finden, in dem alle Grammatikbeschränkungen gelten. Dies bedeutet im Grunde, eine gültige Zuordnung von AST-Knoten zu Grammatikproduktionsregeln zu finden. Dies ist im Allgemeinen ein Constraint-Zufriedenheitsproblem (CSP) und könnte wie das Parsen durch Zurückverfolgen in gelöst werden .$O(e^n)$

Zum Glück für das Parsen kann dies in mit GLR (oder besser mit Einschränkung der Grammatik) erfolgen. Da die AST-Struktur der Struktur der Grammatikproduktionsregeln so nahe kommt, war ich wirklich überrascht, eine Implementierung zu sehen, bei der die Laufzeit schlechter als das Parsen ist: XText verwendet ANTLR zum Parsen und Backtracking zum Entparsen.$O(n^3)$

Fragen

1. Ist eine kontextfreie S-Attribut-Grammatik alles, was ein Parser und ein Unparser gemeinsam nutzen müssen, oder gibt es weitere Einschränkungen, z. B. für die Parsing-Technik / Parser-Implementierung?
2. Ich habe das Gefühl, dass dieses Problem im Allgemeinen nicht - könnte mir ein Genie dabei helfen?$O(e^n)$

Ich habe auf StackOverflow keine Antwort auf diese Frage erhalten . Es wurde vorgeschlagen, hier zu fragen, aber ich hasse Redundanz, also hoffe ich, dass Sie mir verzeihen, dass ich Sie gebeten habe, hier zu antworten .

Es gibt eine Version Ihrer Frage, für die das Parsen einfach ist und in linearer Zeit durchgeführt werden kann. Ich bin mir jedoch nicht ganz sicher, ob sich Ihre Frage auf diese spezielle Version von Unparsing bezieht, daher werde ich mir das zuerst ansehen.

Sie sagen in Ihrer Frage bei StackOverflow, dass Ihr AST wie "AnyObject -> AnyObject -> Vehicle [name =" Car "]" aussieht. Ihre Frage wäre viel einfacher, wenn Ihr AST wie "Bereich -> Autobahn -> Auto" aussieht, dh wir wissen, welche Produktionen aufgenommen wurden, als Ihr AST erstellt / analysiert wurde. Bei normalen kontextfreien Parsern erhalten Sie (fast) immer diese Informationen: Sie können sie möglicherweise wegwerfen, aber (fast) alle Parsing-Algorithmen können Ihnen diese Informationen auch geben.

Wenn Sie diese Informationen nicht haben, bin ich mir ziemlich sicher, dass die exponentielle Zeit das Beste ist, was Sie tun können, es sei denn, Sie wissen etwas über Ihre S-Ausdrücke. Das Problem ist dann einfach die Wiederherstellung des AST "Area -> Highway -> Car", das anschließende Aufheben der Analyse ist der einfache Teil.

Wenn Sie diese Informationen haben, können wir uns nur kontextfreie Grammatiken ansehen und versuchen, sie zu analysieren. Betrachten Sie diese Grammatik:

1: $S \to a$
2: $S \to a S a$

Ein AST für diese Grammatik könnte so aussehen $S \to a (S \to a) a$, bei Eingabe "aaa". Das Aufheben der Analyse dieses AST ist einfach: Führen Sie eine Nachbestellungswanderung des Baums durch und geben Sie alle in dieser Wanderung gefundenen Terminals aus. Das Ergebnis ist wieder "aaa".

Die Dinge werden etwas komplizierter, wenn Sie sich mehrdeutige kontextfreie Grammatiken ansehen. Einerseits sind die Dinge immer noch einfach: Sie wählen einfach einen Analysebaum Ihrer Eingabe aus und führen die oben genannten Schritte aus: Sie können alle anderen Analysebäume aus dem Ergebnis rekonstruieren.

Bei Vorhandensein von Disambiguierungsregeln müssen Sie jedoch etwas Kluges tun. Insbesondere kann die Eingabe "(1 + 2) * 3" als "1 + 2 * 3" nicht analysiert werden, was sich vom Original unterscheidet. Dies ist in linearer Zeit möglich$LR(1)$ Grammatiken (bei denen Vorrang und Assoziativität wie in Yacc erzwungen werden) durch Umkehren $LR$parse zur unparsen Zeit. Ich werde die Details überspringen, da dies nicht Teil Ihrer Frage war, aber es kann getan werden.