regex - studio - ¿No son regulares los dialectos de expresión regular modernos?

regex replace example

Question

He visto algunos comentarios aquí que mencionan que las expresiones regulares modernas van más allá de lo que se puede representar en un lenguaje regular. ¿Cómo es esto?

¿Qué características de las expresiones regulares modernas no son regulares? Los ejemplos serían útiles.

Answer 1

Lo primero que viene a la mente son las referencias inversas:

(/w*)/s/1

(coincide con un grupo de caracteres de palabras, seguido de un carácter de espacio y luego el mismo grupo que coincidía anteriormente), por ejemplo: hello hello coincidencias, hello world no.

Esta construcción no es regular (es decir, no puede ser generada por una gramática regular ).

Otra característica compatible con Perl Compatible RegExp (PCRE) que no es regular son los patrones recursivos:

/((a*|(?R))*/)

Esto se puede usar para emparejar cualquier combinación de paréntesis equilibrados y "a" s (de wikipedia )

Answer 2

Un autómata finito determinista o no determinista reconoce solo los lenguajes regulares, que se describen mediante expresiones regulares. La definición de una expresión regular es simple. Sea S un alfabeto. Luego, el conjunto vacío, la cadena vacía y cada elemento de S son expresiones regulares (sobre S ). Sean u y v expresiones regulares. Entonces la unión ( u | v ), la concatenación ( uv ) y el cierre ( u *) de u y v son expresiones regulares sobre S. Esta definición se extiende fácilmente a los idiomas regulares. Ninguna otra expresión es una expresión regular. Como se señaló, algunas referencias son un ejemplo. Las páginas de Wikipedia sobre lenguajes regulares y expresiones son buenas referencias.

En esencia, ciertas "expresiones regulares" no son regulares porque no se puede construir un autómata de un tipo particular para reconocerlas. Por ejemplo, el idioma

{a ^ i b ^ i : i <= 0}

no es regular Esto se debe a que el autómata de aceptación requeriría infinitos estados, pero un autómata que acepta idiomas regulares debe tener un número finito de estados.

Answer 3

Un par de ejemplos:

• Las expresiones regulares apoyan la agrupación. Por ejemplo, en Ruby: /my (group)/.match("my group")[1] mostrará "group". almacenar algo en un grupo requiere un almacenamiento externo, que no tiene un autómata finito.
• Muchos idiomas, por ejemplo, C #, admiten capturas, es decir, que cada coincidencia se capturará en una pila, por ejemplo, el patrón (?<MYGROUP>.)* Podría realizar múltiples capturas de "." en el mismo grupo.
• La agrupación se utiliza para la referencia inversa según lo señalado anteriormente por el usuario NullUserException. La referencia al retroceso requiere una o más pilas externas con la potencia de un autómata de empuje hacia abajo (tienes que poder empujar algo en una pila y echar un vistazo o abrirlo después).
• Algunos motores tienen la posibilidad de empujar y estallar por separado las pilas externas y verificar si la pila está vacía. En .NET, en realidad (?<MYGROUP>test) empuja una pila, mientras que (?<-MYGROUP>) saca una pila.
• Algunos motores, como el motor .NET, tienen un concepto de agrupación equilibrado, en el que una pila externa puede empujarse y abrirse al mismo tiempo. La sintaxis de agrupación equilibrada es (?<FIRSTGROUP-LASTGROUP>) que muestra el LASTGROUP y empuja la captura desde el índice LASTGROUP en la pila de FIRSTGROUP. En realidad, esto se puede usar para hacer coincidir construcciones infinitamente anidadas que definitivamente están más allá del poder de un autómata finito.

Probablemente existan otros buenos ejemplos :-) Si está más interesado en algunos de los detalles de implementación de pilas externas en combinación con Regex y la agrupación equilibrada y, por lo tanto, autómatas de mayor orden que los autómatas finitos, una vez escribí dos artículos breves sobre esto (http: / /www.codeproject.com/KB/recipes/Nested_RegEx_explained.aspx y http://www.codeproject.com/KB/recipes/RegEx_Balanced_Grouping.aspx ).

De todos modos, sea finito o no, lamento que el poder que este material adicional aporta a los lenguajes regulares sea excelente :-)

Br. Morten