Algorithmus für eine kontextfreie Grammatik

Question

Ich versuche, einen Algorithmus zu entwerfen, der eine CFG G und ein Terminal-Symbol a als Eingabe nimmt und yes ausgibt, wenn S (die Startregel von G) eine zu startende Sentential-Form generieren kann mit einem. h., wenn es eine Zeichenkette α in (T U N) * gibt, so dass S => * aα ist, sonst gibt sie nein aus. Zum Beispiel, wenn die Grammatik S -> [S] | ist SS | ε, und wenn a =], ist die Antwort nein. Ich bin nicht auf der Suche nach Code, ich versuche nur zu verstehen, wie ich dieses Thema in Pseudocode angehen sollte.

Answer 1

Es gibt drei Möglichkeiten, X kann eine Zeichenfolge beginnend mit a ableiten.

1. Es gibt eine Regel der Form X -> a...
2. Es gibt eine Regel der Form X -> A... und A leitet eine Zeichenfolge mit a beginnen.
3. Es gibt eine Regel der Form X -> B A... und B leitet ε und A... leitet eine Zeichenfolge mit a beginnen.

Sie können diese verwenden, um einen Algorithmus zu entwickeln, die mit denen der Form S -> ... und gelten entweder 1 überprüfen, ob die mit einem Terminal oder beiden Kontrollen rhs beginnt 2 und 3, wenn es ab allen Regeln der Grammatik sieht beginnt mit einem Nicht-Terminal. Jede Überprüfung entspricht einer (möglicherweise rekursiven) Funktion, die einen booleschen Wert zurückgibt.

Ein interessantes Detail ist die Notwendigkeit, mit Zyklen in der Grammatik umzugehen, z.B. einzelne Regeln wie A -> A a, aber auch A -> B..., B -> C..., C -> A.... Wenn Sie nicht vorsichtig sind, werden die gegenseitig rekursiven Prüfungen unendlich oft wiederholt. Das werde ich dir überlassen. Denken Sie darüber nach, wie eine Tiefensuche die folgenden Zyklen in einem Diagramm für immer vermeidet.

Ein anderes Detail ist, wie man bestimmt, ob ein gegebenes Nichtterminal B ε ableitet. Sie sollten in der Lage sein, das selbst auszuarbeiten, aber wenn alles andere fehlschlägt, suchen Sie nach "Nullable non-terminal". Sie werden einen bekannten kleinen Algorithmus finden.

Wenn eine der Überprüfungen positiv ist, geben Sie yes zurück. Eine andere erschöpfende Anwendung der Regeln hat keinen Weg gefunden. Rückkehr Nr.

Answer 2

Sie können nur den Prädiktor von Earley parser ausführen, bis die Vorhersage beendet wird, und prüfen, ob Regeln generiert werden, die mit dem betreffenden Terminal beginnen. Geben Sie alle Nichtterminale ein, die das fragliche Terminal als erste Eingabe akzeptieren, und markieren Sie dann alle Nichtterminals, die bereits markierte Nichtterminals als ihre erste Eingabe akzeptieren, und wiederholen Sie bis zum Ende, und prüfen Sie, ob S ist in der Menge der markierten Nichtterminals.