Welche Zeichen können der Zeichenfolge (in den sententialen Formen des CFG) folgen?

Question

Sei $ sigma $ der Satz von Terminal und $ n $ Die nicht terminalen Symbole einer kontextfreien Grammatik $ g $.

Sagen Sie, ich habe eine Zeichenfolge $ a in ( sigma cup n)^+$, so dass $ xay in mathcal {s} (g) $ wobei $ x, y in ( sigma cup n)^* $ und $ mathcal {s} (g) $ sind die sententialen Formulare von $ g $.

Mit $ g $ möchte ich einen Satz $ c = {b mid wabz in mathcal {s} (g), b in sigma cup n } $ ermitteln.

Um in diesem Fall zu verdeutlichen, sind $ W, X, Y, Z, A, B $ Terminals und Nicht-Terminals, und $ B $ ist von einer Länge eins.

Ich kann sehen, wie das geht, wenn $ a $ auch von einer Länge eins ist. Jedes $ B $ ist Mitglied des Follow-Set von $ a $ (einschließlich Nicht-Terminals).

Ich bin jedoch neugierig, ob es für eine Abfolge von Zeichen möglich ist. Für meine Anwendung ist die Zeichenfolge $ a $ nicht viel länger als die rechte Seite der Produktionen in $ g $.

Die Unterscheidung zwischen Terminals und Nicht-Terminalen ist in meiner Anwendung etwas stumm, weil ich eine generative Grammatik verwende. Und ich glaube, dass dies nicht zu viel Schwierigkeiten führen wird, da $ B $ mit einer Länge eins ist.

Answer 1

Ich werde einen Algorithmus beschreiben, der funktioniert. Es sollte nicht schlecht sein. Sie können auch ziemlich viel davon vorkomputieren.

Ich gehe davon aus, dass $ a $ keine Nicht -Terminals enthält (obwohl es wahrscheinlich einfach ist, sich an diesen Fall anzupassen) und dass Sie nicht $ x $, $ y $ oder die Ableitung von $ A $ kennen. Ich gehe auch davon aus, dass Ihre Grammatik keine Produktionen enthält, die in keiner Ableitung verwendet werden ($ a rightarrow a $ zum Beispiel).

Das Hauptproblem besteht wirklich darin, A $ $ zu analysieren, da Sie wissen möchten, in welcher Art von Staaten Sie landen, damit Sie wissen, was $ A $ folgen kann. Dies ist nicht so einfach, da Sie nicht $ x $ kennen.

Wir verwenden eine Anpassung von Earleys Algorithmus. Sie möchten diesen Algorithmus zuerst verstehen. Unser Algorithmus funktioniert auf die gleiche Weise, außer dass unsere Initialisierungs- und Abschlussschritte unterschiedlich sind.

Für die Initialisierung säen wir unseren ersten Satz mit einem Earley -Artikel für jedes Ereignis von $ a_1 $ (dem ersten Charakter in $ a $) in jeder Produktion Ihrer Grammatik. Wir setzen den hinteren Zeiger dieses Elements auf -1, einen ungültigen Wert. Dies ist wichtig für unsere modifizierte Fertigstellung. Im Wesentlichen bedeutet der -1 "Ich habe keine Ahnung, wo diese Produktion begonnen wurde".

Jetzt führen wir den Earley -Algorithmus für jedes mögliche solche anfänglichen Earley -Gegenstand separat durch. Wir können sie nicht einfach alle gleichzeitig machen, da die Parse sich gegenseitig beeinträchtigen können. Ich kann eine schnellere Methode nicht leicht sehen, als hier zurückzukehren.

Für den Abschlussschritt müssen wir nur eine Änderung vornehmen, um -1 -Rückenzeiger zu verarbeiten. Da wir eine Produktion abgeschlossen haben, deren Herkunft wir nicht kennen, sind wir in Schwierigkeiten. Jedoch, Die Methode zur Berechnung von $ lalr (1) $ Lookahead Sets durch Pennello und Deremer Speichert uns: Was wir hier brauchen, ist genau die $ lalr (1) $ Lookahead Sets. Jeder Artikel in diesen Lookahead -Sets hat eine entsprechende Position in der Grammatik, was wiederum einer möglichen Fortsetzung der abgeschlossenen Produktion entspricht.

Leider sehe ich hier keine andere Wahl, als hier noch einmal zurückzukehren. Für jede Position im Lookahead -Set führen Sie den Abschlussschritt mit dieser Position durch und setzen den Analyse von dort aus. Sie tun dies für jeden Parse getrennt. Beachten Sie, dass Ihre Lookahead, wenn Ihre Grammatik $ lalr (1) $ ist, eindeutig bestimmt, zu welcher Position Sie gehen müssen, damit Sie nicht zurückverfolgen müssen.

Sie setzen den obigen Algorithmus ein Zeichen über $ a $ fort, bei dem Sie diesen zusätzlichen, virtuellen Charakter als das 'beliebige Charakter' betrachten, das Ihnen sofort das "Follow' -Set" gibt, nach dem Sie suchen - jederzeit findet die Scannerphase etwas dafür In diesem letzten Satz können Sie diesen Charakter Ihrem Antwortsatz hinzufügen.

Bearbeiten: Ich denke, ich habe die Methode gefunden, die den größten Teil des von der Rückverdauerung eingeführten Overheads beseitigt. Wir assoziieren mit jedem Earley -Element eine Reihe von Kennungen, die Strings sind, da wir Präfixe dieser Kennungen verwenden müssen. Bei der Initialisierung fügen wir alle ersten Elemente zum Earley -Set hinzu und assoziieren mit jedem Satz eine eindeutige Kennung.

Bei den Scanner- und Prädiktorschritten werden Kennungen auf neue Gegenstände übertragen. Earley -Gegenstände im selben Earley -Set, das sich nur in ihren Kennungen unterscheidet, werden zusammengeführt, indem ihre Kennungen zusammengeführt werden. Beachten Sie, dass wir Scanner- und Prädiktorschritte zu diesen neuen Elementen mit Kennungen ausführen können, ohne diesen Schritt für jede Kennung separat ausführen zu müssen.

Der Abschluss berücksichtigt die Kennung separat und vervollständigt nur ein Element, wenn das entsprechende Element in der früheren Elementset eine Kennung enthält, die ein Präfix der Kennung ist. Für jede mögliche Fertigstellung (also für jeden Artikel im $ lalr (1) $ Lookahead -Set enden wir einen einzigartigen Charakter an die Kennungen der ausgefüllten Artikel.

Im Wesentlichen führen wir die Backtracking mit diesen Kennungen durch, damit wir keine Doppelarbeit in den Scanner- und Prädiktorschritten durchführen.