Einen Analysewald von einem Earley-Parser wiederherstellen?

25

Ich habe kürzlich den Earley-Parser gelesen und denke, er ist einer der elegantesten Algorithmen, die ich bisher gesehen habe. Der Algorithmus im herkömmlichen Sinne ist jedoch ein Erkenner und kein Parser. Dies bedeutet, dass er erkennen kann, ob eine Zeichenfolge mit einer bestimmten CFG übereinstimmt, aber keinen Analysebaum für diese erstellt. Meine Frage ist, wie man nicht einen Parsing- Baum , sondern den Parsing- Wald aller möglichen Parsings der angegebenen Eingabezeichenfolge wiederherstellt.

In Grune und Jacobs "Parsing Techniques: A Practical Guide" veranschaulichen sie einen Algorithmus, mit dem eine Analyse-Gesamtstruktur aus dem Ergebnis des Earley-Erkenners wiederhergestellt werden kann, der jedoch auf Ungers Parsing-Methode basiert, deren Laufzeit O (n k + ist 1 ), wobei k die Länge der längsten Produktion in der Grammatik ist. Dies bedeutet, dass die Laufzeit kein Polynom in der Größe der Grammatik ist. Darüber hinaus ist Earleys Originalarbeit über den Algorithmus, der einen Algorithmus zum Wiederherstellen von Analyse-Gesamtstrukturen vorschlägt, falsch (siehe z. B. Seite 762 dieses Artikels von Tomita), obwohl viele Quellen ihn immer noch als geeignete Methode zum Wiederherstellen der Analyse-Gesamtstruktur anführen .

Meine Frage ist, ob es in der Polynomzeit möglich ist, eine Analysegesamtstruktur für eine bestimmte Eingabezeichenfolge wiederherzustellen. Ich habe hier eine Arbeit gefunden , die einen Algorithmus zum Erzeugen von kubisch großen Syntaxanalysewald-Darstellungen für jede Syntaxanalyse unter Verwendung einer PDA-Simulation bereitstellt. Dies scheint also möglich zu sein, aber ich habe noch keinen Weg gefunden, dies zu tun. Idealerweise würde ich dies tun, ohne die Eingabe-Grammatik in CNF umzuwandeln (was das Problem tatsächlich lösen würde), da der resultierende Analyse-Wald ziemlich chaotisch wäre.

Vielen Dank für jede Hilfe, die Sie anbieten können!

templatetypedef
quelle
Muss es ein Algorithmus sein, der auf Earley-Parsing basiert, oder würde es Ihnen nichts ausmachen, einen anderen allgemeinen CFG-Parser zu verwenden?
Alex ten Brink
1
Ich würde einen Algorithmus vorziehen, der auf dem Earley-Parser basiert. Ich habe einen Compilerkurs unterrichtet und ein paar Tage lang versucht, eine Antwort auf diese Frage zu finden, und es nervt mich wirklich.
Templatetypedef
Exponentielle Laufzeiten sind nicht überraschend, da Wörter exponentiell viele Analysebäume haben können. Sie können sogar unendlich viele haben, wenn Sie beliebige CFGs zulassen.
Raphael
3
@Raphael Die Rolle des Parsen von Wäldern besteht genau darin, einen Mechanismus zur gemeinsamen Nutzung zu haben, der es ermöglicht, alle Bäume, auch unendlich viele, mit einer endlichen Struktur und einer geringen räumlichen Komplexität darzustellen. Dies kann natürlich Arbeit für Holzfäller hinterlassen.
Babou
Vielleicht möchten Sie sich Marpa ansehen . Es handelt sich um ein Perl-Modul und eine C-Bibliothek, die einen Earley-Parser implementiert und die vollständige Unterstützung für das Parsen von Gesamtstrukturen bietet.
Hippietrail

Antworten:

14

Dies würde natürlich von der richtigen Darstellung für einen "gepackten Wald" abhängen, der alle Analysebäume für einen bestimmten Satz darstellt.

Ich denke, der Ort, an dem Sie anfangen möchten, ist Joshua Goodmans These (von innen nach außen analysieren, Harvard, 1999). Grundsätzlich besteht die Idee darin, dass Sie einen Parsing-Algorithmus unter einem bestimmten Semiring definieren können. Je nach Semiring können Sie anstelle des nackten Analysebaums alle Arten von Größen und Strukturen berechnen (als Erkenner oder als Parser). Ein Semiring, den Sie definieren können (was Goodman in seiner Dissertation tut), ist ein Semiring, bei dem die Werte Mengen von Parses sind. Wenn Sie das Parsen eines Satzes abschließen, werden alle Analysebäume im Hauptanalyseknoten angezeigt.

Auch hier muss man vorsichtig sein, um dies durch die richtige Darstellung zu ermöglichen.

gmmodeler
quelle
Danke für den Hinweis! Dies sieht nach einer großartigen Ressource aus und ich werde einige Zeit damit verbringen, darüber nachzudenken.
Templatetypedef
8

Es gibt ein Papier, das beschreibt, wie es geht:

Parsing nach SPPF-Art von Earley Recognisers von Elisabeth Scott

Es wird beschrieben, wie in kubischer Zeit ein binarisierter Analysewald erstellt wird.

Angelo Borsotti
quelle
2
Diese Verbindung scheint jetzt unterbrochen zu sein. Haben Sie einen Verweis (Titel der Veröffentlichung, Autorenliste) und / oder einen aktualisierten Link?
DW
1
Siehe web.archive.org/web/20130508170633/http://thor.info.uaic.ro/… : "SPPF-Style Parsing From Earley Recognisers", Elizabeth Scott. Ein weiterer Link: dinhe.net/~aredridel/.notmine/PDFs/… .
Uhr
Dies ist die richtige Antwort auf die Frage "Wie bekommt man einen Analysewald von einem Earley-Erkenner?".
22.
Es gibt eine nette Implementierung davon in JS hier: joshuagrams.github.io/pep
tjvr
Was ist in diesem Zusammenhang unter binärisiert zu verstehen?
Bruce Adams
6

Sie brauchen nie CNF. Es hat den Nachteil, die Grammatikstruktur zu ändern. Sie müssen jedoch Zwischenterminals einführen, damit keine rechte Seite länger als 2 (2-Form) ist, da die RHS-Länge die Komplexität bestimmt. Der beste Versuch, dies intuitiv zu erklären, ist ein Artikel von Beau Shiel, "Observations on Context Free Parsing" (Beobachtungen zum kontextfreien Parsen), der 1976 in einer Konferenz zur Computerlingistik veröffentlicht wurde. Earleys Algorithmus verwendet implizit die 2-Form. Es ist nur im Algorithmus versteckt. In Bezug auf die Wiederherstellung und Behandlung von Parsing-Gesamtstrukturen sollten Sie im Web nach "Parsing-Gesamtstrukturen" suchen. Es ist eigentlich sehr einfach. Viele Artikel befinden sich im Web, wenn Sie (aus Zitaten oder Inhaltsverzeichnissen) die Titel oder Autoren erhalten, um sie direkt zu durchsuchen.

Tatsächlich können Sie viel mehr als nur CF-Operationen ausführen und trotzdem in polynomieller Zeit Analysewälder abrufen. Die Frage ist manchmal: Was können Sie damit machen, wenn Sie es haben?

Der letzte Artikel, den Sie erwähnen, soll zeigen, dass komplexe Algorithmen (z. B. GLR) weder zeitlich noch räumlich etwas kosten und möglicherweise Ihren Analysewald ändern.

Eine Bemerkung zum Unterrichten. Ich denke, Earley, so zukunftsweisend es war, ist viel zu kompliziert für den Unterricht und könnte durch einfachere Algorithmen mit im Wesentlichen demselben Bildungsinhalt ersetzt werden. In der Lehre geht es um Konzepte oder Technologie. In Earleys Algorithmus sind die wesentlichen Konzepte in der Komplexität der Details verborgen und aus technologischer Sicht veraltet. Es war eine großartige Arbeit, aber es bedeutet nicht, dass es der beste pädagogische Ansatz ist.

Die Literatur zur Computerlinguistik enthält möglicherweise mehr Informationen als die üblichen Kanäle der Informatik. Ich habe das Ceriel-Grune-Jacobs-Buch nicht, aber ich wäre überrascht, wenn sie nicht alle richtigen Referenzen hätten (obwohl ich nicht sicher bin, welche Auswahlkriterien sie haben).


Ergänzung zu einer Anfrage in einem Kommentar (7. Juli 2013)

Diese Ergänzung steht für die Existenz einfacherer Algorithmen als Earleys.

Wie ich bereits sagte, sollte das Durchsuchen des Webs unter "Parsing Intersection Forest" schnell Hinweise geben, anhand derer Sie weiter graben können.

Die Grundidee ist, dass alle Pfade, die mit der Konstruktion eines gemeinsamen Waldes analysiert werden, nichts anderes als die alte Kreuzungskonstruktion von Bar Hillel, Perles und Shamir für eine reguläre Sprache und eine kontextfreie Sprache unter Verwendung eines endlichen Automaten und einer kontextfreien Grammatik sind. In Anbetracht der CF-Grammatik wenden Sie die Konstruktion auf einen einfachen Automaten an, der nur Ihre Eingabezeichenfolge erkennt. Das ist alles. Der gemeinsame Wald ist nur die Grammatik für die Kreuzung. Es bezieht sich auf die ursprüngliche Grammatik durch einen Homomorphismus, erkennt nur die angegebene Zeichenfolge, aber mit allen Analysebäumen der ursprünglichen Grammatik bis zu diesem Homomorphismus (dh einfaches Umbenennen von Nicht-Terminals).

Die resultierende Grammatik enthält eine Menge nutzloser Dinge, Nicht-Terminals und Regeln, die entweder vom Axiom nicht erreichbar sind (nicht in einer Zeichenfolge zu finden, die vom Anfangssymbol abgeleitet ist) oder die nicht produktiv sind (nicht in ein Terminal abgeleitet werden können) Zeichenfolge).

Dann müssen Sie es entweder am Ende mit einem guten Pinsel reinigen (möglicherweise lang, aber algorithmisch einfach), oder Sie können versuchen, die Konstruktion so zu verbessern, dass am Ende weniger unnütze Flusen gebürstet werden.

Beispielsweise ist die CYK-Konstruktion genau so aufgebaut, jedoch so organisiert, dass alle erstellten Regeln und Nicht-Terminals produktiv sind, obwohl viele davon nicht erreichbar sein können. Dies ist bei einer Bottom-up-Technik zu erwarten.

Top-down-Techniken (wie LR (k) -basierte) vermeiden nicht erreichbare Regeln und Nicht-Terminals, erzeugen jedoch unproduktive Regeln.

Ein Großteil des Putzens kann tatsächlich durch eine angemessene Verwendung von Zeigern erreicht werden, denke ich, aber ich habe mich lange nicht damit befasst.

Alle existierenden Algorithmen folgen im Wesentlichen diesem Modell. Das ist also wirklich der Kern der Sache, und es ist sehr einfach. Warum sollte man es dann in Komplexität begraben?

In der Literatur werden viele "Optimierungen" vorgeschlagen, die häufig auf der LR (k), LL (k) -Familie der Parserkonstruktionen basieren, möglicherweise mit statischem Faktorisieren dieser Konstruktionen (Earley hat kein statisches Faktorisieren). Es könnte tatsächlich auf alle bekannten Techniken angewendet werden, einschließlich der alten Präzedenz-Parser. Ich setze "Optimierung" zwischen Anführungszeichen, weil es normalerweise nicht klar ist, was Sie optimieren oder sogar, ob Sie es tatsächlich optimieren oder ob der Nutzen der Verbesserung die zusätzliche Komplexität Ihres Parsers wert ist. Sie werden wenig objektive, formale oder experimentelle Daten darüber finden (es gibt einige), aber viel mehr Behauptungen. Ich sage nicht, dass es nichts Interessantes gibt. Es gibt einige kluge Ideen.

Sobald Sie die Grundidee kennen, können die "Optimierungen" oder Verbesserungen häufig statisch (möglicherweise inkrementell) eingeführt werden, indem ein Push-Down-Automat aus der Grammatik erstellt wird, der der Art der Parser-Konstruktionstechnik folgt, an der Sie interessiert sind, und dann angewendet wird die produktübergreifende Konstruktion für die Schnittmenge zu diesem Automaten (fast dasselbe wie für die Grammatik) oder zu einer von diesem Automaten abgeleiteten Grammatik.

Dann kann man Schnickschnack einführen, aber das sind meistens technologische Details.

Die Philosophiæ Naturalis Principia Mathematica von Isaac Newton ist angeblich ein großartiges Stück Physik und Mathematik. Ich glaube nicht, dass es auf der Leseliste vieler Studenten steht. Wenn alle anderen Dinge gleich sind, halte ich es nicht für sehr nützlich, Earleys Algorithmus zu lehren, obwohl es sich um ein wichtiges historisches Stück handelt. Die Schüler haben genug zu lernen, wie es ist. Ich bin der Meinung, dass das Knuth LR (k) -Papier ähnlich ist, da das Risiko besteht, von vielen Menschen abgeschossen zu werden. Es ist eine hervorragende theoretische Analyse und wahrscheinlich eine wichtige Lektüre für einen Theoretiker. Ich bezweifle stark, dass es für die Erstellung von Parsern nach dem aktuellen Stand der Technik, sowohl der Hardware als auch der Software, so wichtig ist. Die Zeiten sind vorbei, in denen das Parsen einen wesentlichen Teil der Kompilierungszeit ausmachte. oder als die Geschwindigkeit der Compiler ein kritisches Thema war (ich kannte ein Unternehmen, das vor 30 Jahren an den Kosten für das Compilieren gestorben ist). Der Parsing-Spezialist möchte dieses Fachwissen vielleicht irgendwann erlernen, aber der durchschnittliche Student in Informatik, Programmierung oder Ingenieurwesen benötigt es nicht.

Wenn die Schüler mehr Zeit mit dem Parsen verbringen müssen, gibt es andere Erweiterungen, die möglicherweise nützlicher und formativer sind, z. B. solche, die in der Computerlinguistik verwendet werden. Die erste Aufgabe des Unterrichts besteht darin, die einfachen Ideen zu extrahieren, die das wissenschaftliche Wissen strukturieren, und die Studenten nicht dazu zu zwingen, das zu leiden, was die Wissenschaftler zu leiden hatten (Doktoranden ausgenommen: es ist ein Übergangsritus :-).

Lizenz CC BY-SA 3.0 vom Autor

babou
quelle
2
"Earley ... ist viel zu kompliziert für den Unterricht und könnte durch einfachere Algorithmen ersetzt werden ...". Könnten Sie ein Beispiel für einen solchen einfacheren Algorithmus geben?
WJL
@wjl Ich antworte Ihnen in einem Nachtrag zu der obigen Antwort. Ich weise nicht auf einen bestimmten Algorithmus hin, obwohl Sie einige in der Literatur finden können, wenn Sie eine Suche durchführen, wie ich empfehle. Ich habe eher versucht zu erklären, warum es sehr einfach ist, einfachere und dennoch effiziente Algorithmen zu erstellen. Earley's ist wahrscheinlich das komplexeste von allen. Die Erklärung von Bar Hillel et al. Aufbau ist ungefähr eine halbe Seite des Lehrbuchs, sagen Sie eine Seite mit dem Beweis.
Babou
Die Beantwortung Ihrer Anfrage hat einige Zeit in Anspruch genommen. Hat es dir geholfen? . . . . . Wenn Sie einen tatsächlichen Algorithmus wollten, gibt es einen im letzten Link der Anfangsfrage.
Babou
Ja Dankeschön; Ich schätze das zusätzliche Detail. Ich arbeite an einer verallgemeinerten Parserbibliothek für einige meiner Arbeiten und habe eine Menge Forschung zu verschiedenen Algorithmen betrieben. Ich neige derzeit zu einer frühen Implementierung, da es für mich ein sehr einfach zu verstehender Algorithmus zu sein schien und sich leicht auf konjunktive Grammatiken und "Black-Box" -Terminals (möglicherweise kontextsensitiv) erweitern lässt. Ich überflog einige der Papiere, auf die Sie hingewiesen haben, und druckte sie aus. aber ich habe sie noch nicht ernsthaft gelesen.
WJL
@wjl Wenn Sie dies tun, sollten Sie sich die folgenden Themen ansehen: leicht kontextsensitive Sprachen, lineare kontextfreie Umschreibungssysteme (LCFRS) und Grammatiken zur Bereichsverkettung. Ich verstehe nicht, was ein "Black-Box" -Terminal ist. - - E-Mail: babou bei inbox.com. - -
babou
5

Der Artikel, der beschreibt, wie ein binarisierter Analysewald in kubischer Zeit erstellt wird (erwähnt in dem Beitrag von Angelo Borsotti), lautet: "SPPF-Style Parsing From Earley Recognizers" von Elizabeth Scott. Sie finden es hier: http://dx.doi.org/10.1016/j.entcs.2008.03.044

In diesem Artikel wird der Aufbau eines gemeinsam genutzten gepackten Parsewalds (SPPF) beschrieben, der alle möglichen Parsebäume darstellt. Unterbäume werden nach Möglichkeit gemeinsam genutzt, und Knoten, die unterschiedlichen Ableitungen desselben Teilstrings von demselben Nichtterminal entsprechen, werden kombiniert.

Eiderente
quelle
Danke für den Hinweis. Das Bauen binarisierter Parse-Wälder in kubischer Zeit ist Standard. Die Binarisierung ist der einzige Weg, um kubische Zeit zu erhalten, so dass die Bemerkung des OP zur Komplexität bezüglich der Grammatikgröße irrelevant ist. Ein weiteres Problem besteht darin, zu verstehen, auf welche Weise der Analysewald binärisiert wird. Das kann vom Algorithmus abhängig sein. Andere Probleme sind die gemeinsame Nutzung der Gesamtstruktur und die praktische Effizienz der Parsing-Strategie (Earley ist möglicherweise eine schlechte Idee). All dies wurde in der letzten Referenz des OP entwickelt. Eine allgemeine formale Sicht auf das Thema ist in meiner Antwort skizziert.
Babou
1

Ich möchte die obigen Antworten wiederholen, indem ich Ihnen vorschlage, dieses Papier zu lesen:

http://dx.doi.org/10.1016/j.entcs.2008.03.044

Ich möchte mich jedoch qualifizieren, indem ich sage, dass ich den Algorithmus in diesem Artikel implementiert habe und ich glaube, dass ein Fehler vorliegt. Insbesondere der erste Satz des zweiten Absatzes von Abschnitt 4. Die Vorgängerbezeichnungen, die Sie für das machen, was Earley die "Scan" -Phase nennen würde, sollten von p nach q zeigen und nicht umgekehrt.

Insbesondere die folgende Zeile:

Setze E0 als die Items (S :: = · α, 0). Für i> 0 initialisieren Sie Ei, indem Sie für jedes q = (A :: = α · aiβ, j) ∈ Ei − 1 den Punkt p = (A :: = αai · β, j) addieren und, falls α =, a erzeugen Vorgängerzeiger mit der Bezeichnung i - 1 von q bis p

Sollte lauten "von p nach q" und nicht "von q nach p"

Ich habe den Algorithmus so implementiert, wie er ursprünglich angegeben wurde. Dies führte zu Fehlern bei einigen handgefertigten Testfällen, die behoben wurden, nachdem ich hier die Richtung des Zeigers geändert hatte.

Jeremy Dohmann
quelle