Producir todas las coincidencias posibles de una expresión regular

Dada una expresión regular, quiero producir el conjunto de cadenas que esa expresión regular concuerde. Es importante tener en cuenta que este conjunto no sería infinito porque habría una longitud máxima para cada cadena. ¿Existen algoritmos bien conocidos para hacer esto? ¿Hay algún documento de investigación que pueda leer para obtener información sobre este problema?Producir todas las coincidencias posibles de una expresión regular

Gracias.

p.s. ¿Esta clase de pregunta sería más apropiada en el intercambio de pila cs teórico?

Fuente

2011-07-10 Sam

Bueno, no podemos votar a moverse a Teórica CS, para que pueda bandera de su pregunta y pedir un mod. – BoltClock

Todas las cadenas posibles corresponden a todas las rutas posibles a través de la máquina de estado que termina en una coincidencia. Pero esto es como preguntar, darme todos los posibles programas de duración limitada que coincidan con la salida de mi programa. – gtrak

Cuando dice una "longitud máxima" para cada cadena, ¿quiere decir que su expresión regular no contiene ningún operador + o *? –

En el mundo de Perl que tienen un módulo de CPAN que hace precisamente eso ->Regexp::Genex

Fuente

2011-07-10 21:38:47 average

Gracias. Puedo seguir adelante y usar ese módulo. ¿Conoce algún recurso que debata cómo implementar dicho módulo? Tenía curiosidad de cómo podría implementarse elegantemente/eficientemente. – Sam

simplemente verifique su código fuente. intuitivamente, una expresión regular es un autómata, entonces un gráfico. generar todas las cadenas que coincidan con una cadena significaría encontrar todas las rutas comenzando con el nodo "inicio" y terminando en el nodo "aceptar" del autómata, por lo que solo significaría una enumeración de rutas dentro de un gráfico. – average

Producir todas las coincidencias posibles de una expresión regular

Respuesta

Cuestiones relacionadas