Expresividad de las expresiones regulares modernas.

9

Recientemente hablé con un amigo sobre un sitio web que propuso desafíos de expresiones regulares, principalmente haciendo coincidir un grupo de palabras con una propiedad especial. Estaba buscando una expresión regular que coincida con cadenas como ||||||||donde el número |es primo. Inmediatamente le dije que eso nunca funcionaría porque si ese lenguaje fuera regular, la traducción del lema de bombeo daría el hecho de que, por un momentopags lo suficientemente grande, existe kpags tal que pags+nortek es primo para todos norte-1y bueno, este no es el caso (reparto de primos, trivialidad de una propiedad tan desconocida y aplastante, ...)

Pero entonces alguien llegó con la solución: QUE NO (||+?)\1+ Esta expresión intenta hacer coincidir el grupo de captura (que puede ser ||, |||, ||||y así sucesivamente dek2ocurrencias de |)norte2veces. Si coincide, significa que el número representado por la cadena es divisible pork, y por lo tanto no es primo. De lo contrario, lo es.

Y me sentí estúpido, porque se hizo evidente que la agrupación y la referencia inversa permiten que la expresión regular sea en realidad mucho más expresiva que ... la expresión regular, en el sentido teórico. Ahora incluso agregaron búsquedas y otros operadores que no conocía cuando solía hacer expresiones regulares reales.

Según Wikipedia, es aún más expresivo que los lenguajes generados por una gramática libre de contexto. Ésta es mi pregunta :

  • ¿Podemos representar cualquier lenguaje algebraico (generado a partir de una gramática libre de contexto) con motores modernos de expresión regular
  • ¿Hay una descripción más general, o al menos un límite superior sobre la complejidad de qué tipo de lenguajes puede describir una expresión regular moderna?

Más pragmáticamente, ¿hay alguna teoría seria detrás de esto o simplemente estamos agregando nuevas características cada vez que parece implementable en el bloque inicial de expresiones regulares reales basadas en autómatas finitos?

Sé que "regex moderno" no es muy específico mientras que la pregunta es, pero quiero decir al menos con referencias inversas, y posiblemente más. Por supuesto, si tiene respuestas parciales asumiendo ciertas restricciones en este lenguaje "regex moderno", no dude en publicarlo.

yago
fuente
1
Pregunta relacionada . Me parece recordar que al menos algunos sabores RegExp están completos en Turing. Este artículo puede ser un punto de partida válido para la investigación bibliográfica.
Raphael
@Raphael muchas gracias, el artículo parece responder a una gran parte de mis interrogatorios
yago
Una razón más fuerte de por qué no todos los p + nk pueden ser primos es que cuando n = p, tienes p + nk = p (1 + k).
Nathan FD

Respuestas: