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!
quelle
Antworten:
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.
quelle
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.
quelle
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
quelle
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.
quelle
Ich möchte die obigen Antworten wiederholen, indem ich Ihnen vorschlage, dieses Papier zu lesen:
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:
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.
quelle