Me pregunto cómo encontrar un conjunto de todas las coincidencias para una expresión regular dada con un número finito de coincidencias.Crear un conjunto de todas las coincidencias posibles para una expresión regular dada
Por ejemplo:
Todos estos ejemplo, usted puede asumir que comienzan con ^
y terminan con $
`hello?` -> (hell, hello)
`[1-9][0-9]{0,3}` -> (1,2,3 ..., 9998, 9999)
`My (cat|dog) is awesome!` -> (My cat is awesome!, My dog is awesome!)
`1{1,10}` -> (1,11, ..., 111111111, 1111111111)
`1*` -> //error
`1+` -> //error
`(1|11){2}` -> (1,11,111,1111) //notice how it doesn't repeat any of the possibilities
Yo también estaría interesado si había una manera de recuperar el recuento soluciones únicas para la expresión regular o si hay una forma de determinar si la expresión regular tiene soluciones finitas.
Sería bueno si el algoritmo pudiera analizar cualquier expresión regular, pero un subconjunto lo suficientemente potente de la expresión regular estaría bien.
Estoy interesado en una solución PHP para este problema, pero otros lenguajes también estarían bien.
EDIT:
que he aprendido en mi clase de teoría formal sobre DFA que puede ser utilizado para implementar expresiones regulares (y otros lenguajes regulares). Si pudiera transformar la expresión regular en un DFA, la solución parece bastante directa para mí, pero esa transformación me parece bastante difícil.
EDIT 2:
Gracias por todas las sugerencias, see my post about the public github project que estoy trabajando a "respuesta" a esta pregunta.
Gran pregunta. Imagino que algo que podría hacer esto sería muy útil para las pruebas unitarias. – FtDRbwLXw6
@drrcknlsn Ese fue uno de mis pensamientos, estaba pensando en usarlo para generar un caché completo para un sistema de enrutamiento basado en expresiones regulares para un MVC. –
Está asumiendo anclajes implícitos. Es fácil mostrar todas las formas posibles de emparejar una cadena dada. Por ejemplo, dado "Hello world", el patrón '/ hel + o?/I' coincide con Hello, Hell y Hel. Sin embargo, eso no es lo mismo que la generación. – tchrist