Gibt es einen nicht-allgemeinen CFG-Parsing-Algorithmus, der EPAL erkennt?

EPAL, die Sprache der geraden Palindrome, wird als die Sprache definiert, die durch die folgende eindeutige kontextfreie Grammatik erzeugt wird:

$S \rightarrow a a$

$S \rightarrow b b$

$S \rightarrow a S a$

$S \rightarrow b S b$

EPAL ist der Fluch vieler Parsing-Algorithmen: Ich habe noch keinen Parsing-Algorithmus für eindeutige CFGs gefunden, der jede Grammatik analysieren kann, die die Sprache beschreibt. Es wird oft verwendet, um zu zeigen, dass es eindeutige CFGs gibt, die von einem bestimmten Parser nicht analysiert werden können. Dies hat meine Frage inspiriert:

Gibt es einen Parsing-Algorithmus, der nur eindeutige CFGs akzeptiert, die auf EPAL funktionieren?

Natürlich kann man einen Ad-hoc-Parser mit zwei Durchgängen für die Grammatik entwerfen, der die Sprache in linearer Zeit analysiert. Ich interessiere mich für Analysemethoden, die nicht speziell für EPAL entwickelt wurden.

formal-languages formal-grammars parsers Alex ten Brink
quelle

Ich habe fast Angst zu fragen: Was ist falsch an LL (1) bei rekursiver Abstammung?

Raphael

Rekursiver Abstieg ohne Backtracking kann EPAL nicht verarbeiten, da die Sprache nicht LL (k) für k ist. Rekursiver Abstieg mit Backtracking kann die Grammatik in -Zeit verarbeiten, aber das ist ein allgemeiner Algorithmus mit exponentiellem Worst-Case-Verhalten, nach dem ich nicht suche.

O (n^{2})

$O(n^2)$

Alex ten Brink

O (N^{2})

$O(N^2)$ ist nicht exponentiell, sondern quadratisch. ist exponentiell.

O (2^{N})

$O(2^N)$

Victor Stafusa

@ Victor: Backtracking hat bei einigen Grammatiken ein exponentielles Verhalten, nur bei dieser bestimmten Grammatik nicht. Da es sich jedoch um einen Algorithmus handelt, der mit mehrdeutigen Grammatiken arbeitet, wird er als Antwort auf meine Frage herabgesetzt.

Alex ten Brink

@jmad: Meine Absicht ist es nicht, die Sprache zu analysieren (Sie können dies trivial in linearer Zeit tun), sondern meine Neugier zu befriedigen: Ich habe gesehen, dass sie als Beispiel für eine Sprache verwendet wird, die mit einer Analysemethode nicht analysiert werden kann Ich bin so oft gespannt, ob es eine Parsing-Methode gibt, die das erkennt.

Alex ten Brink

Antworten:

Betrachten Sie die folgende Skizze einer Analysestrategie auf eigenes Risiko.

Anstatt die Eingabe nur von einem Ende aus zu lesen, lesen wir von beiden Seiten und suchen nach übereinstimmenden Regeln. Wir können dies im rekursiven Abstiegsstil tun; Suchen Sie bei einem Aufruf von das Präfix und das Suffix für die Eingabe, sodass es eine Regel , und steigen Sie für das verbleibende Wort auf ab. Wenn es keine übereinstimmende Regel gibt, lehnen Sie das Wort ab. $A()$ $w$ $v$ $A \to wBv$ $B()$

Dieser Algorithmus analysiert alle linearen, eindeutigen Grammatiken. Es dauert lineare Zeit , wenn alle Regelpaar und haben oder ¹. Dies schließt EPAL ein. Andernfalls müssen wir nach vorne schauen, damit wir uns Zeit für können. $A \to wBv$ $A \to w'B'v'$ $w \not\equiv_p w'$ $v \not\equiv_s v'$ $\Theta(n^2)$

Die Idee funktioniert überhaupt nicht für nichtlineare Grammatiken. Lineare, aber mehrdeutige Grammatiken können im Allgemeinen nicht ohne Rückverfolgung analysiert werden (zumindest für negative Eingaben).

$w \not\equiv_p v$ bedeutet hier, dass und , dh kein Wort ist ein Präfix des anderen. ist für Suffixe ähnlich. $w \not\sqsubseteq v$ $v \not\sqsubseteq w$ $\not\equiv_s$

Raphael
quelle

Ausgezeichnet! Genau das, wonach ich gesucht habe. Es ist großartig, dass eine Sprache, die nicht für ist, mit einem so einfachen Algorithmus syntaktisch analysiert werden kann.

N L R (k)

$NLR(k)$

k

$k$

Alex ten Brink

Nachdem ich darüber nachgedacht hatte, entdeckte ich einen kleinen Fehler in Ihrer Beschreibung: die lineare Grammatik ist eindeutig, aber es gibt kein so eindeutiges Präfix, wie Sie es beschreiben. Es gibt immer noch ein eindeutiges Präfix, aber Sie müssen möglicherweise in das Nichtterminal schauen, um es zu erhalten, und Ihre Laufzeit wird zu . Ihr Algorithmus arbeitet jedoch mit .

S \to a A b | a B b, A \to a, B \to b

$S \rightarrow a A b | a B b, A \rightarrow a, B \rightarrow b$

O (n^{2})

$O(n^2)$

E P A L

$EPAL$

Alex ten Brink

@AlextenBrink Guter Fang. Ich habe bearbeitet, um dies zu berücksichtigen.

Raphael