Phrases de permutation avec analyse LR

16

Une phrase de permutation est une extension des définitions de grammaire sans contexte standard (E) BNF: une phrase de permutation contient n productions (ou de manière équivalente, non terminales) A 1 à A n . À la position de la phrase de permutation, nous aimerions voir chacune de ces productions exactement une fois, mais nous ne sommes pas intéressés par l'ordre de ces non-terminaux.{UNE1,,UNEn}nUNE1UNEn

Par exemple:

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

est équivalent à:

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

Le concept semble être introduit dans "Étendre les grammaires sans contexte avec des phrases de permutation" . Il y est également décrit comment analyser ces phrases en temps linéaire en utilisant un analyseur LL (1).

L'article "Analyse des phrases de permutation" décrit une méthode d'analyse des expressions de permutation à l'aide de combinateurs d'analyseurs. Ce sont les deux seuls articles que j'ai trouvés qui parlent de phrases de permutation et comment les analyser.

Voyant que nous pouvons facilement analyser ces types de phrases de permutation avec des analyseurs basés sur LL (1), je suppose que nous pouvons faire de même avec les analyseurs de style LR (1). Ma question est donc:

Une grammaire contenant des phrases de permutation peut-elle être analysée en temps linéaire dans la taille de la chaîne d'entrée à l'aide de la machinerie LR (1) tout en conservant une table de taille raisonnable?

O(|g|!)

O(2|g|)

Bien que ce soit mieux, ce n'est bien sûr pas assez bon - avoir une phrase de permutation de 30 éléments rendrait la grammaire inutilisable. Il y a encore une partie de l'analyse LR que nous n'avons pas encore abordée, et c'est la procédure basée sur la pile réelle utilisée pour l'analyse. J'imagine que le stockage de compteurs sur la pile peut résoudre le problème, mais je ne sais pas comment faire.

J'implémente actuellement un générateur d'analyseur et, dans le problème, les phrases de permutation seraient un cadeau du ciel. Comme j'utilise des machines LR (1), la question ci-dessus a suivi.

Alex ten Brink
la source
La complexité de l'analyse LR (1) est déjà exponentielle dans la taille de la grammaire sans phrases de permutation --- sauf si vous implémentez un calcul "à la volée" de l'analyseur, mais cela ressemble plus à un analyseur Earley qu'à un authentique LR (1) un.
Sylvain
2
À propos du reste de votre question: cstheory.stackexchange.com/questions/4962/… montre une limite inférieure exponentielle sur la taille d'un CFG pour les permutations, et par la construction polynomiale habituelle des CFG à partir de PDA, cela implique une limite inférieure exponentielle sur la taille du PDA également.
Sylvain
1
Je n'avais pas regardé le papier sur LL (1). En effet, l'analyseur implémenté n'est plus un PDA. Je ne crois toujours pas à l'existence d'une "table de taille raisonnable", car l'appartenance à des grammaires commutatives sans contexte est NP-complète (voir par exemple dx.doi.org/10.3233/FI-1997-3112 ), mais c'est vrai que les instances dures pourraient ne pas être LR (1).
Sylvain
2
@Sylvain: Pouvez-vous expliquer comment la question 4962 se rapporte à celle-ci? Dans la question 4962, la permutation est fixe pour chaque longueur d'entrée et les chaînes à permuter changent. Dans la question actuelle, nous ne fixons pas la permutation. Je ne vois donc aucun lien réel entre eux.
Tsuyoshi Ito du
2
@Tsuyoshito Ito: Dans LR (1), une analyse DPDA équivalente à la grammaire d'entrée est d'abord construite puis exécutée sur la chaîne à reconnaître. Comme il existe un CFG de taille linéaire avec des phrases de permutation pour chaque langue de permutation, l'article de Yuval Filmus (qui est plus complet que sa réponse sur cstheory: voir cs.toronto.edu/~yuvalf/CFG-LB.pdf ) montre qu'aucun un tel DPDA peut avoir une taille polynomiale dans la taille de la grammaire d'entrée.
Sylvain

Réponses:

1

Avez-vous envisagé de convertir cela en un problème sémantique? Au lieu de règles de grammaire pour toutes les permutations de non terminaux {A, B, C}, il suffit d'avoir une règle à reconnaître (A | B | C) ^ 3 ainsi qu'un code interne spécial qui garantit qu'un seul de chacun est reconnu, sinon il déclare une erreur. J'insérerais une production vide avant la clause ci-dessus, dont la réduction déclenche l'initialisation de tout ce que vous utilisez pour compter les A, B et C, et une après, dont la réduction déclenche la vérification du compteur et (si nécessaire) affirme l'erreur. (bien sûr, cela pourrait devenir un peu délicat si la grammaire est récursive via A, B et / ou C)

PMar
la source
0

Je ne pense pas que l'on ait besoin d'un compteur. Essentiellement, vous vérifiez simplement toutes les permutations, mais vous cassez

pseudo-code:

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

Voici un exemple plus concret

Supposons que nous essayons de faire correspondre toute permutation d'abcd et que notre chaîne soit bcda

  • Étape 1: Trouvez le premier symbole correspondant. Dans ce cas, c'est b
  • Étape 2: supprimez ce symbole de notre modèle et réduisez la chaîne: par exemple, acd et cda sont laissés
  • Étape 3: répétez l'étape 1 sur les nouvelles chaînes
    • c correspond à cda qui nous laisse avec ad et da
    • un match en da qui nous laisse avec d et d
    • d correspond à d, ce qui nous laisse zéro dans les deux cordes

Donc, vous voyez que cet algorithme simple peut vérifier une permutation assez facilement en comparant simplement les "chaînes" en désordre. Notez que la complexité de la fonction est O (n!) Pire cas et O (1) meilleur cas. Dans un sens, nous comptons en stockant les symboles à faire correspondre dans un tableau. Je pense que ce serait "rapide" en général, car on ne traiterait pas de très grand n dans la plupart des cas.

Uiy
la source
2
nn=50