Phrases de permutation avec analyse LR

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.$\{ A_1, \dots, A_n \}$$n$$A_1$$A_n$

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.

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)

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.