Permutationsphrasen mit LR-Analyse

16

Eine Permutationsphrase ist eine Erweiterung der kontextfreien Grammatikdefinitionen von Standard (E) BNF: Eine Permutationsphrase enthält n Produktionen (oder entsprechend Nichtterminale) A 1 bis A n . An der Stelle der Permutationsphrase möchten wir jede dieser Produktionen genau einmal sehen, aber die Reihenfolge dieser Nichtterminale interessiert uns nicht.{A1,,An}nA1An

Beispielsweise:

S <- X { A, B, C } Y

ist äquivalent zu:

S <- X  A B C  Y
S <- X  A C B  Y
S <- X  B A C  Y
S <- X  B C A  Y
S <- X  C A B  Y
S <- X  C B A  Y

Das Konzept scheint in "Erweitern von kontextfreien Grammatiken mit Permutationsphrasen" eingeführt worden zu sein . Darin wird auch beschrieben, wie diese Phrasen in linearer Zeit unter Verwendung eines LL (1) -Parsers analysiert werden.

Der Artikel " Analysieren von Permutationsphrasen " beschreibt eine Methode zum Analysieren von Permutationsphrasen mit Parser-Kombinatoren. Dies sind die einzigen zwei Artikel, die ich gefunden habe und die sich mit Permutationsphrasen und deren Analyse befassen.

Angesichts der Tatsache, dass wir diese Art von Permutationsphrasen mit LL (1) -basierten Parsern leicht analysieren können, würde ich davon ausgehen, dass wir dasselbe mit Parsern im LR (1) -Stil tun können. Meine Frage lautet daher:

Kann eine Grammatik, die Permutationsphrasen enthält, in der Größe der Eingabezeichenfolge unter Verwendung der LR (1) -Maschinerie zeitlinear analysiert werden, während eine Tabelle mit angemessener Größe beibehalten wird?

O(|G|!)

O(2|G|)

Obwohl dies besser ist, ist es natürlich nicht gut genug - eine Permutationsphrase von 30 Elementen würde die Grammatik unbrauchbar machen. Es gibt noch einen Teil des LR-Parsings, den wir noch nicht behandelt haben, und das ist das eigentliche stapelbasierte Verfahren, das für das Parsing verwendet wird. Ich kann mir vorstellen, dass das Speichern von Zählern auf dem Stapel das Problem lösen kann, aber ich bin mir nicht sicher, wie ich das tun soll.

Ich implementiere derzeit einen Parser-Generator und im Problembereich wären Permutationsphrasen ein Geschenk des Himmels. Da ich LR (1) -Maschinen benutze, folgte die obige Frage.

Alex ten Brink
quelle
Die Komplexität des LR (1) -Parsings ist in Bezug auf die Größe der Grammatik ohne Permutationsphrasen bereits exponentiell. Dies gilt jedoch nicht, wenn Sie eine "on the fly" -Rechnung des Parsers implementieren echtes LR (1) eins.
Sylvain
2
Zum Rest Ihrer Frage: cstheory.stackexchange.com/questions/4962/… zeigt eine exponentielle Untergrenze für die Größe eines CFG für Permutationen, und durch die übliche polynomielle Konstruktion von CFGs aus PDAs bedeutet dies eine exponentielle Untergrenze für auch die Größe des PDAs.
Sylvain
1
Ich hatte mir die Zeitung über LL (1) nicht angesehen. In der Tat ist der implementierte Parser kein PDA mehr. Ich glaube immer noch nicht an die Existenz einer "angemessen großen Tabelle", da die Mitgliedschaft für kommutative kontextfreie Grammatiken NP-vollständig ist (siehe z. B. dx.doi.org/10.3233/FI-1997-3112 ), aber es ist wahr dass die harten Instanzen möglicherweise nicht LR (1) sind.
Sylvain
2
@ Sylvain: Können Sie näher erläutern, inwiefern Frage 4962 sich auf diese Frage bezieht? In Frage 4962 ist die Permutation für jede Eingabelänge festgelegt, und die zu permutierenden Zeichenfolgen ändern sich. In der aktuellen Frage korrigieren wir die Permutation nicht. Ich sehe also keinen wirklichen Zusammenhang zwischen ihnen.
Tsuyoshi Ito
2
@Tsuyoshito Ito: Beim LR (1) -Parsing wird zuerst ein DPDA-Äquivalent zur Eingabe-Grammatik erstellt und dann mit der zu erkennenden Zeichenfolge verglichen. Da es für jede Permutationssprache ein lineares CFG mit Permutationsphrasen gibt, zeigt Yuval Filmus 'Artikel (der umfassender ist als seine Antwort zu cstheory: siehe cs.toronto.edu/~yuvalf/CFG-LB.pdf ), dass nein Ein solches DPDA kann eine Polynomgröße in der Größe der Eingabegrammatik haben.
Sylvain

Antworten:

1

Haben Sie darüber nachgedacht, dies in ein semantisches Problem umzuwandeln? Anstelle von Grammatikregeln für alle Permutationen von Nichtterminalen {A, B, C} muss nur eine Regel (A | B | C) ^ 3 zusammen mit einem speziellen internen Code erkannt werden, der sicherstellt, dass jeweils nur eine davon erkannt wird, andernfalls wird deklariert ein Fehler. Ich würde eine leere Produktion vor der obigen Klausel einfügen, deren Reduktion die Initialisierung dessen auslöst, was Sie zum Zählen von A, B und C verwenden, und eine nachfolgende, deren Reduktion die Zählerüberprüfung auslöst und (falls erforderlich) den Fehler bestätigt. (Natürlich kann dies etwas schwierig werden, wenn die Grammatik durch A, B und / oder C rekursiv ist.)

PMar
quelle
0

Ich glaube nicht, dass man einen Zähler braucht. Im Wesentlichen überprüfen Sie nur alle Permutationen, brechen aber ab

Pseudocode:

perm-match(input, pattern)
     if pattern = nil return true

     foreach(rule in pattern)
         if (match(input, rule))
             perm-match(input - matchedpart, pattern - rule)
             break
         end
     end
     return false
end

Hier ist ein konkreteres Beispiel

Angenommen, wir versuchen, eine Permutation von abcd abzugleichen, und unsere Zeichenfolge lautet bcda

  • Schritt 1: Finden Sie das erste übereinstimmende Symbol. In diesem Fall ist es b
  • Schritt 2: Entfernen Sie dieses Symbol aus unserem Muster und reduzieren Sie die Zeichenfolge: z. B. bleiben acd und cda übrig
  • Schritt 3: Wiederholen Sie Schritt 1 für die neuen Saiten
    • c stimmt mit cda überein, was uns mit ad und da zurücklässt
    • Ein Streichholz in da, das uns mit d und d zurücklässt
    • d stimmt mit d überein, was uns in beiden Zeichenfolgen mit null zurücklässt

Sie sehen also, dass dieser einfache Algorithmus ganz einfach nach einer Permutation suchen kann, indem er "Strings" in der falschen Reihenfolge vergleicht. Beachten Sie, dass die Komplexität der Funktion O (n!) Worst Case und O (1) Best Case ist. In gewisser Weise zählen wir, indem wir die übereinstimmenden Symbole in einem Array speichern. Ich würde denken, dass dies im Allgemeinen "schnell" sein würde, da man in den meisten Fällen nicht mit sehr großen n umgehen würde.

Uiy
quelle
2
nn=50