Frases de permutación con análisis LR

16

Una frase de permutación es una extensión de las definiciones de gramática libre de contexto estándar (E) BNF: una frase de permutación contiene n producciones (o, de manera equivalente, no terminales) A 1 a A n{UN1,...,UNnorte}norteUN1UNnorte . En la posición de la frase de permutación, nos gustaría ver cada una de estas producciones exactamente una vez, pero no estamos interesados ​​en ordenar estos no terminales.

Por ejemplo:

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

es equivalente a:

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

El concepto parece ser introducido en "Extender gramáticas libres de contexto con frases de permutación" . Allí también se describe cómo analizar estas frases en tiempo lineal usando un analizador LL (1).

El artículo "Analizando frases de permutación" describe un método para analizar frases de permutación utilizando combinadores de analizador sintáctico. Estos son los únicos dos documentos que he encontrado que hablan sobre frases de permutación y cómo analizarlas.

Al ver que podemos analizar fácilmente este tipo de frases de permutación con analizadores basados ​​en LL (1), supongo que podemos hacer lo mismo con los analizadores de estilo LR (1). Mi pregunta es por lo tanto:

¿Se puede analizar una gramática que contenga frases de permutación en un tiempo lineal en el tamaño de la cadena de entrada utilizando maquinaria LR (1) mientras se mantiene una tabla de tamaño razonable?

O(El |solEl |!)

O(2El |solEl |)

Aunque esto es mejor, por supuesto, no es lo suficientemente bueno: tener una frase de permutación de 30 elementos hará que la gramática sea inutilizable. Todavía hay una parte del análisis LR que aún no hemos tocado, y ese es el procedimiento real basado en la pila utilizado para el análisis. Me imagino que almacenar contadores en la pila puede resolver el problema, pero no estoy seguro de cómo hacerlo.

Actualmente estoy implementando un generador de analizador, y en el dominio del problema, las frases de permutación serían un regalo del cielo. Como estoy usando maquinaria LR (1), siguió la pregunta anterior.

Alex ten Brink
fuente
La complejidad del análisis LR (1) ya es exponencial en el tamaño de la gramática sin frases de permutación, excepto si implementa un cálculo "sobre la marcha" del analizador, pero luego se siente más como un analizador Earley que como un genuino LR (1) uno.
Sylvain
2
Sobre el resto de su pregunta: cstheory.stackexchange.com/questions/4962/… muestra un límite inferior exponencial en el tamaño de un CFG para permutaciones, y por la construcción polinomial habitual de CFG de PDA, esto implica un límite inferior exponencial en el tamaño de la PDA también.
Sylvain
1
No había mirado el documento sobre LL (1). De hecho, el analizador implementado ya no es un PDA. Todavía no creo en la existencia de una "tabla de tamaño razonable", ya que la membresía para gramáticas libres de contexto conmutativas es NP-complete (véase, por ejemplo, dx.doi.org/10.3233/FI-1997-3112 ), pero es cierto que las instancias difíciles podrían no ser LR (1).
Sylvain
2
@Sylvain: ¿Puedes explicar cómo se relaciona la pregunta 4962 con esta? En la pregunta 4962, la permutación se fija para cada longitud de entrada, y las cadenas a permutar cambian. En la pregunta actual, no arreglamos la permutación. Así que no veo ninguna conexión real entre ellos.
Tsuyoshi Ito
2
@Tsuyoshito Ito: en LR (1) el análisis de un DPDA equivalente a la gramática de entrada se construye primero y luego se ejecuta contra la cadena para reconocerlo. Como existe un CFG de tamaño lineal con frases de permutación para cada lenguaje de permutación, el artículo de Yuval Filmus (que es más completo que su respuesta en teoría: ver cs.toronto.edu/~yuvalf/CFG-LB.pdf ) muestra que no dicho DPDA puede tener un tamaño polinómico en el tamaño de la gramática de entrada.
Sylvain

Respuestas:

1

¿Has considerado convertir esto en un problema semántico? En lugar de reglas gramaticales para todas las permutaciones de no terminales {A, B, C}, simplemente tenga una regla para reconocer (A | B | C) ^ 3 junto con un código interno especial que asegure que solo uno de cada uno sea reconocido, de lo contrario, declara un error. Insertaría una producción vacía antes de la cláusula anterior, cuya reducción desencadena la inicialización de lo que esté utilizando para contar A, B y C, y una después, cuya reducción desencadena la verificación del contador y (si es necesario) afirma el error. (por supuesto, esto podría ser un poco complicado si la gramática es recursiva a través de A, B y / o C)

PMar
fuente
0

No creo que uno necesite un contador. Esencialmente, solo verificas todas las permutaciones pero rompes

pseudocódigo:

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

Aquí hay un ejemplo más concreto

Supongamos que estamos tratando de hacer coincidir cualquier permutación de abcd y nuestra cadena es bcda

  • Paso 1: encuentra el primer símbolo coincidente. En este caso es b
  • Paso 2: elimine ese símbolo de nuestro patrón y reduzca la cadena: por ejemplo, se dejan acd y cda
  • Paso 3: repita el paso 1 en las nuevas cadenas
    • c coincide en cda que nos deja con anuncios y da
    • un partido en da que nos deja con dyd
    • d coincide en d lo que nos deja con nulo en ambas cadenas

Como puede ver, este algoritmo simple puede verificar una permutación con bastante facilidad simplemente comparando "cadenas" fuera de orden. Tenga en cuenta que la complejidad de la función es O (n!) Peor caso y O (1) mejor caso. En cierto sentido, estamos llevando la cuenta almacenando los símbolos para que coincidan en una matriz. Creo que esto sería "rápido" en general, ya que no se trataría con n muy grande en la mayoría de los casos.

Uiy
fuente
2
nortenorte=50