Las expresiones regulares no son

Pregúntele incluso a alguien con experiencia en informática qué es una expresión regular, y es probable que la respuesta vaya más allá de la restricción de estar al alcance de un autómata de estado finito.

Por ejemplo, la "expresión regular"

/^1?$|^(11+?)\1+$/

creado por la destacada personalidad de Perl, Abigail (y parte del conjunto de pruebas de Perl desde 2002) describe una máquina que acepta solo números unarios compuestos, pero el ejercicio 4.5 (b) en la tercera edición de Peter Linz An Introduction to Formal Languages ​​and Automata hace que el lector use el lema de bombeo para demostrar que

$\mathcal{L} = \left\{ a^n : n\ \mathrm{is\ not\ a\ prime\ number} \right\}$

No es un lenguaje normal.

En contextos donde la distinción es importante, ¿cómo deberíamos llamar a las expresiones estrictamente más poderosas?

Larry Wall propuso que usemos "expresión regular" para el formalismo que Kleene propuso, y "expresión regular" para expresiones para las extensiones ampliamente utilizadas. Es una convención bastante ampliamente seguida. Si desea dejar en claro que está hablando de expresiones regulares en el sentido de los idiomas formales, por lo general no es difícil traducirlo al lenguaje hablado.

El poder de las expresiones regulares proviene del retroceso, y se ha trabajado en autómatas para idiomas regulares con retroceso. Véase, en particular, Becchi & Crowley, 2008, Extendiendo autómatas finitos para que coincida de manera eficiente con las expresiones regulares compatibles con Perl .

Estas expresiones han sido examinadas por Aho (Handbook of Theoretical Computer Science, Vol. A, Cap. 5) y Campeanu, Salomaa, Yu ("Un estudio formal de expresiones prácticas prácticas", International Journal of Foundations of Computer Science, 14: 1007 –1018, 2003), así como algunos de los documentos de seguimiento.

Aho llama a las expresiones más poderosas "rewbr" (expresión regular con referencias posteriores), Campeanu et al. use "expresión regular extendida" así como "expresión regular práctica". Como parece, "expresión regular extendida" es el término más utilizado en la literatura reciente.

Partiendo del término "expresión racional" de la escuela francesa, y considerando el hecho de que esas expresiones se usan en el mundo real, a mí me gusta "expresión real".

Anexo: Un capítulo en mi tesis doctoral trata sobre esta clase de lenguajes formales (el documento correspondiente aparecerá en STACS 2011). Mientras escribía ese capítulo y el artículo, experimenté con varios términos. Finalmente, decidí usar expresiones regulares extendidas para el modelo con referencias posteriores y expresiones regulares adecuadas para las expresiones regulares agradables y normales. Como es bastante molesto cambiar la terminología en un documento que ya está completamente (o en su mayoría) escrito, creo que algunos podrían estar interesados ​​en las experiencias que llevaron a mi elección:

Primero, regex y rewbr realmente no ruedan la lengua, y usarlas una y otra vez en el transcurso de un trabajo completo se volvió realmente pesado para escribir y leer, en particular cuando se usa cualquiera de las posibles formas plurales. Las expresiones regulares similares a PERL también eran bastante difíciles de manejar. Por supuesto, no soy hablante nativo, así que YMMV.

Segundo, tan pronto como uno quiera hablar sobre ambos modelos, es conveniente usar términos que sean una variación de la expresión regular , ya que esto permite enfatizar la similitud o las diferencias según sea necesario (por ejemplo, "una expresión regular, sea apropiada o extendido"). Además, esto permite enfatizar fácilmente el caso especial de "expresiones regulares extendidas sin referencias posteriores", cuando se habla de casos especiales en toda la clase, en lugar de comparar diferentes modelos.

Tercero, preferí usar un término que ya se usa en la literatura sobre un término recién acuñado, lo que me permitió elegir entre expresiones regulares extendidas y expresiones regulares prácticas . La segunda opción implicaba (al menos implícitamente) que las expresiones regulares adecuadas son poco prácticas, lo que se siente bastante extraño (especialmente porque el RE2 de Google no usa backrefs y parece ser bastante práctico).

Por supuesto, esta opción es solo mi "máximo local personal", y dependiendo de las necesidades, otras opciones podrían ser más apropiadas.

Se sabe que el llamado regexp de Perl es lo suficientemente poderoso como para ser Turing completo; Incluso hay un compilador del programa habitual para perl regexp.

Por lo tanto, dudo que tenga sentido buscar un nombre para este tipo de "expresiones regulares".

Busque por ejemplo en http://search.cpan.org/~asavige/Acme-EyeDrops-1.62/lib/Acme/EyeDrops.pm

Creo que el mejor término para "expresión regular en el contexto de autómatas" es "expresión racional", como se usa, por ejemplo, en los Elementos de la teoría de autómatas de Sakarovitch, o en el Manual de autómatas ponderados.

Dadas las otras respuestas, sugeriría que los "idiomas regulares" son seguros, y después de comentar brevemente la diferencia, hablar sobre "expresiones regulares prácticas" para expresiones regulares (con retroceso).

También tenga en cuenta que la misma expresión regular, como expresiones regulares y como práctica, puede tener una semántica diferente, porque en este último caso la semántica se define en términos de retroceso, con diferentes resultados. Los detalles estarían fuera de tema, pero responderé si hace otra pregunta sobre eso (tal vez sobre SO en lugar de aquí, no sé) y me notificará a través de un comentario.

Podríamos llamarlos expresiones de patrones . Esto podría introducir confusiones con lenguajes de patrones, pero al menos estos son menos comunes.