regex - reemplazar - ¿Terminan las expresiones regulares de Perl?
perl expresiones regulares reemplazar (3)
Excluyendo cualquier tipo de código incrustado, como ?{ } , Es probable que no cubran todas las máquinas de Turing sin contexto, y mucho menos. Podrían, pero que yo sepa, nadie lo ha probado de una manera u otra. Dado que las personas han estado tratando de resolver ciertos problemas de contexto con expresiones regulares de Perl por un tiempo y aún no han llegado a una solución, es probable que no estén libres de contexto.
Hay una discusión interesante sobre qué características son simplemente convenientes y cuáles realmente agregan poder. Por ejemplo, hacer coincidir 0 n * 1 * 0 n (que es una notación para "cualquier número de ceros, seguido de uno, seguido del mismo número de ceros que antes") no es algo que pueda hacerse con expresiones regulares puras. Puede probar que esto no se puede hacer con expresiones regulares usando el lema de bombeo, pero la prueba simple e informal es que la expresión regular debería contar un número arbitrario de ceros, y las expresiones regulares no pueden hacer el recuento.
Sin embargo, las referencias posteriores pueden coincidir con las siguientes:
/(0*) 1 /1/x;
Entonces, eso significa que las referencias posteriores te dan más poder y no son una mera conveniencia. ¿Qué otra cosa podría darnos más poder, me pregunto?
Además, los "patrones" de Perl6 (ni siquiera simulan que ya son expresiones regulares) están diseñados para parecerse a las expresiones regulares de Perl5 (por lo que no es necesario volver a aprender mucho), pero tienen suficientes funciones añadidas para estar completamente contextualizadas. gratis. En realidad, están diseñados para que pueda usarlos para modificar la forma en que se analiza el lenguaje dentro de un alcance léxico.
He visto a los programadores de Ruby y Perl hacer algunos complicados desafíos de código completamente con expresiones regulares. Las capacidades de mirar hacia adelante y hacia atrás en las expresiones regulares de Perl las hacen más potentes que las implementaciones de expresiones regulares en la mayoría de los otros lenguajes. Me preguntaba qué tan poderosos son en realidad.
¿Hay alguna manera fácil de probar o refutar que las expresiones regulares de Perl están completas ?
Hay al menos dos discusiones: Turing integridad y expresiones regulares y ¿Son universales los patrones de Perl? con más referencias.
El consenso (para mi ojo no entrenado) parece ser que la respuesta es "no", pero no estoy seguro si entiendo todo correctamente.
Para las expresiones regulares en Perl hay dos casos:
- Con código incrustado: Son por supuesto Turing-completos.
- Sin código incrustado: Siempre se detienen para que no sean máquinas de Turing generales.
Todos los lenguajes regulares pueden ser aceptados por un autómata finito . Su entrada debe ser una cadena finita.
[...] un autómata finito determinista (DFA) -también conocido como máquina determinista de estados finitos- es una máquina de estados finitos que acepta / rechaza cadenas finitas de símbolos [...].
Lo mismo ocurre con las máquinas de Turing : la definición formal ni siquiera tiene entrada. Debe estar codificado en el número finito de estados.
Las definiciones alternativas (equivalentes) incluyen entrada, pero debe ser finita.