/h[aeiou]+/gUna expresión regular (abreviada como regex o regexp ), [1] a veces denominada expresión racional , [2] [3] es una secuencia de caracteres que especifica un patrón de coincidencia en el texto . Por lo general, estos patrones son utilizados por algoritmos de búsqueda de cadenas para operaciones de "buscar" o "buscar y reemplazar" en cadenas , o para validación de entradas . Las técnicas de expresión regular se desarrollan en informática teórica y teoría del lenguaje formal .
El concepto de expresiones regulares comenzó en la década de 1950, cuando el matemático estadounidense Stephen Cole Kleene formalizó el concepto de lenguaje regular . Se volvieron de uso común con las utilidades de procesamiento de textos de Unix . Desde la década de 1980 han existido diferentes sintaxis para escribir expresiones regulares, una es el estándar POSIX y otra, ampliamente utilizada, la sintaxis Perl .
Las expresiones regulares se utilizan en motores de búsqueda , en cuadros de diálogo de búsqueda y reemplazo de procesadores de texto y editores de texto , en utilidades de procesamiento de texto como sed y AWK , y en análisis léxico . Las expresiones regulares son compatibles con muchos lenguajes de programación.
Las expresiones regulares se originaron en 1951, cuando el matemático Stephen Cole Kleene describió los lenguajes regulares utilizando su notación matemática llamada eventos regulares . [4] [5] Estos surgieron en la informática teórica , en los subcampos de la teoría de autómatas (modelos de computación) y la descripción y clasificación de lenguajes formales . Otras implementaciones tempranas de coincidencia de patrones incluyen el lenguaje SNOBOL , que no usaba expresiones regulares, sino sus propias construcciones de coincidencia de patrones.
Las expresiones regulares entraron en uso popular a partir de 1968 en dos usos: coincidencia de patrones en un editor de texto [6] y análisis léxico en un compilador. [7] Una de las primeras apariciones de expresiones regulares en forma de programa fue cuando Ken Thompson incorporó la notación de Kleene en el editor QED como un medio para hacer coincidir patrones en archivos de texto . [6] [8] [9] [10] Para mayor velocidad, Thompson implementó la coincidencia de expresiones regulares mediante compilación justo a tiempo (JIT) con el código IBM 7094 en el Compatible Time-Sharing System , un importante ejemplo temprano de compilación JIT. [11] Más tarde agregó esta capacidad al editor de Unix ed , lo que finalmente llevó al uso de expresiones regulares por parte de la popular herramienta de búsqueda grep ("grep" es una palabra derivada del comando para la búsqueda de expresiones regulares en el editor de ed: significado "Búsqueda global de líneas coincidentes de impresión y expresión regular"). [12] Casi al mismo tiempo que Thompson desarrolló QED, un grupo de investigadores, incluido Douglas T. Ross, implementó una herramienta basada en expresiones regulares que se utiliza para el análisis léxico en el diseño de compiladores . [7]g/re/p
Muchas variaciones de estas formas originales de expresiones regulares se utilizaron en programas Unix [10] en los Laboratorios Bell en la década de 1970, incluidos vi , lex , sed , AWK y expr , y en otros programas como Emacs (que tiene su propio e incompatible sintaxis y comportamiento). Posteriormente, las expresiones regulares fueron adoptadas por una amplia gama de programas, y estas primeras formas se estandarizaron en el estándar POSIX.2 en 1992.
En la década de 1980, surgieron expresiones regulares más complicadas en Perl , que originalmente derivaban de una biblioteca de expresiones regulares escrita por Henry Spencer (1986), quien más tarde escribió una implementación para Tcl llamada Expresiones regulares avanzadas . [13] La biblioteca Tcl es una implementación híbrida NFA / DFA con características de rendimiento mejoradas. Los proyectos de software que han adoptado la implementación de expresiones regulares Tcl de Spencer incluyen PostgreSQL . [14] Más tarde, Perl amplió la biblioteca original de Spencer para agregar muchas características nuevas. [15] Parte del esfuerzo en el diseño de Raku (anteriormente llamado Perl 6) es mejorar la integración de expresiones regulares de Perl y aumentar su alcance y capacidades para permitir la definición de gramáticas de expresión de análisis . [16] El resultado es un minilenguaje llamado reglas de Raku , que se utilizan para definir la gramática de Raku y para proporcionar una herramienta a los programadores en el lenguaje. Estas reglas mantienen las características existentes de las expresiones regulares de Perl 5.x, pero también permiten la definición estilo BNF de un analizador de descenso recursivo a través de subreglas.
El uso de expresiones regulares en estándares de información estructurada para el modelado de documentos y bases de datos comenzó en la década de 1960 y se expandió en la década de 1980 cuando se consolidaron estándares de la industria como ISO SGML (precursor de ANSI "GCA 101-1983"). El núcleo de los estándares del lenguaje de especificación de estructuras consta de expresiones regulares. Su uso es evidente en la sintaxis del grupo de elementos DTD . Antes del uso de expresiones regulares, muchos lenguajes de búsqueda permitían comodines simples, por ejemplo "*" para hacer coincidir cualquier secuencia de caracteres y "?" para que coincida con un solo carácter. Hoy en día se pueden encontrar reliquias de esto en la sintaxis global para nombres de archivos y en el operador SQL LIKE .
A partir de 1997, Philip Hazel desarrolló PCRE (Perl Compatible Regular Expressions), que intenta imitar fielmente la funcionalidad de expresiones regulares de Perl y es utilizado por muchas herramientas modernas, incluidas PHP y Apache HTTP Server . [ cita necesaria ]
Hoy en día, las expresiones regulares son ampliamente compatibles con lenguajes de programación, programas de procesamiento de texto (particularmente lexers ), editores de texto avanzados y algunos otros programas. La compatibilidad con Regex es parte de la biblioteca estándar de muchos lenguajes de programación, incluidos Java y Python , y está integrada en la sintaxis de otros, incluidos Perl y ECMAScript . Las implementaciones de la funcionalidad de expresiones regulares a menudo se denominan motor de expresiones regulares y hay varias bibliotecas disponibles para su reutilización. A finales de la década de 2010, varias empresas comenzaron a ofrecer implementaciones de hardware, FPGA , [17] GPU [18] de motores de expresiones regulares compatibles con PCRE que son más rápidos en comparación con las implementaciones de CPU .
La frase expresiones regulares , o expresiones regulares , se utiliza a menudo para referirse a la sintaxis textual estándar específica para representar patrones para hacer coincidir texto, a diferencia de la notación matemática que se describe a continuación. Cada carácter de una expresión regular (es decir, cada carácter de la cadena que describe su patrón) es un metacarácter que tiene un significado especial o un carácter regular que tiene un significado literal. Por ejemplo, en la expresión regular b., 'b' es un carácter literal que coincide solo con 'b', mientras que '.' es un metacarácter que coincide con todos los caracteres excepto una nueva línea. Por lo tanto, esta expresión regular coincide, por ejemplo, con 'b%', 'bx' o 'b5'. Juntos, los metacaracteres y los caracteres literales se pueden utilizar para identificar texto de un patrón determinado o procesar varias instancias del mismo. Las coincidencias de patrones pueden variar desde una igualdad precisa hasta una similitud muy general, controlada por los metacaracteres. Por ejemplo, .es un patrón muy general [a-z](coincide con todas las letras minúsculas de 'a' a 'z') es menos general y bes un patrón preciso (coincide solo con 'b'). La sintaxis de metacaracteres está diseñada específicamente para representar objetivos prescritos de una manera concisa y flexible para dirigir la automatización del procesamiento de texto de una variedad de datos de entrada, en una forma fácil de escribir usando un teclado ASCII estándar .
Un caso muy simple de expresión regular en esta sintaxis es ubicar una palabra escrita de dos maneras diferentes en un editor de texto ; la expresión regular seriali[sz]ecoincide con "serializar" y "serializar". Los caracteres comodín también logran esto, pero están más limitados en lo que pueden modelar, ya que tienen menos metacaracteres y una base de lenguaje simple.
El contexto habitual de los caracteres comodín es incluir nombres similares en una lista de archivos, mientras que las expresiones regulares se emplean generalmente en aplicaciones que coinciden con patrones de cadenas de texto en general. Por ejemplo, la expresión regular coincide con el exceso de espacios en blanco al principio o al final de una línea. Una expresión regular avanzada que coincide con cualquier número es .^[ \t]+|[ \t]+$[+-]?(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)?
Un procesador de expresiones regulares traduce una expresión regular en la sintaxis anterior en una representación interna que puede ejecutarse y compararse con una cadena que representa el texto que se busca. Un enfoque posible es el algoritmo de construcción de Thompson para construir un autómata finito no determinista (NFA), que Luego se vuelve determinista y el autómata finito determinista (DFA) resultante se ejecuta en la cadena de texto de destino para reconocer subcadenas que coinciden con la expresión regular. La imagen muestra el esquema NFA obtenido a partir de la expresión regular , donde s denota a su vez una expresión regular más simple, que ya ha sido traducida recursivamente a NFA N ( s ).N(s*)s*
Una expresión regular, a menudo denominada patrón , especifica un conjunto de cadenas necesarias para un propósito particular. Una forma sencilla de especificar un conjunto finito de cadenas es enumerar sus elementos o miembros. Sin embargo, a menudo hay formas más concisas: por ejemplo, el conjunto que contiene las tres cadenas "Handel", "Händel" y "Haendel" se puede especificar mediante el patrón H(ä|ae?)ndel; decimos que este patrón coincide con cada una de las tres cuerdas. Sin embargo, puede haber muchas formas de escribir una expresión regular para el mismo conjunto de cadenas: por ejemplo, (Hän|Han|Haen)delen este ejemplo también se especifica el mismo conjunto de tres cadenas.
La mayoría de los formalismos proporcionan las siguientes operaciones para construir expresiones regulares.
gray|greygray|greyy son patrones equivalentes que describen el conjunto de "gris" o "gris".gr(a|e)y? , el asterisco * (derivado de la estrella Kleene ) y el signo más + ( Kleene plus )..coincide con cualquier carácter. Por ejemplo,a.bcoincide con cualquier cadena que contenga una "a", y luego cualquier carácter y luego "b".a.*bcoincide con cualquier cadena que contenga una "a" y luego el carácter "b" en algún momento posterior.Estas construcciones se pueden combinar para formar expresiones arbitrariamente complejas, de forma muy parecida a como se pueden construir expresiones aritméticas a partir de números y las operaciones +, −, × y ÷.
La sintaxis precisa de las expresiones regulares varía según las herramientas y el contexto; Se dan más detalles en § Sintaxis.
Las expresiones regulares describen lenguajes regulares en la teoría del lenguaje formal . Tienen el mismo poder expresivo que las gramáticas regulares .
Las expresiones regulares constan de constantes, que denotan conjuntos de cadenas, y símbolos de operador, que denotan operaciones sobre estos conjuntos. La siguiente definición es estándar y se encuentra como tal en la mayoría de los libros de texto sobre teoría del lenguaje formal. [20] [21] Dado un alfabeto finito Σ, las siguientes constantes se definen como expresiones regulares:
aen Σ que denota el conjunto que contiene sólo el carácter a .Dadas las expresiones regulares R y S, se definen las siguientes operaciones sobre ellas para producir expresiones regulares:
(RS)denota el conjunto de cadenas que se pueden obtener concatenando una cadena aceptada por R y una cadena aceptada por S (en ese orden). Por ejemplo, sea R {"ab", "c"} y S {"d", "ef"}. Entonces, (RS)denota {"abd", "abef", "cd", "cef"}.(R|S)denota la unión de conjuntos descritos por R y S. Por ejemplo, si R describe {"ab", "c"} y S describe {"ab", "d", "ef"}, la expresión (R|S)describe { "a B C D e F"}.(R*)denota el superconjunto más pequeño del conjunto descrito por R que contiene ε y está cerrado bajo concatenación de cadenas. Este es el conjunto de todas las cadenas que se pueden formar concatenando cualquier número finito (incluido cero) de cadenas del conjunto descrito por R. Por ejemplo, si R denota {"0", "1"}, (R*)denota el conjunto de todas cadenas binarias finitas (incluida la cadena vacía). Si R denota {"ab", "c"}, (R*)denota {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", . ..}.Para evitar paréntesis, se supone que la estrella Kleene tiene la máxima prioridad, seguida de la concatenación y luego la alternancia. Si no hay ambigüedad, se pueden omitir los paréntesis. Por ejemplo, (ab)cse puede escribir como abcy a|(b(c*))se puede escribir como a|bc*. Muchos libros de texto utilizan los símbolos ∪, + o ∨ para alternancia en lugar de la barra vertical.
Ejemplos:
a|b*denota {ε, "a", "b", "bb", "bbb", ...}(a|b)*denota el conjunto de todas las cadenas sin símbolos distintos de "a" y "b", incluida la cadena vacía: {ε, "a", "b", "aa", "ab", "ba", "bb" , "aaa", ...}ab*(c|ε)denota el conjunto de cadenas que comienzan con "a", luego cero o más "b" y finalmente, opcionalmente, una "c": {"a", "ac", "ab", "abc", "abb", "abbc ", ...}(0|(1(01*0)*1))*denota el conjunto de números binarios que son múltiplos de 3: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110" , "1001", "1100", "1111", "00000", ... }La definición formal de expresiones regulares es mínima a propósito y evita definir ?y +; estas se pueden expresar de la siguiente manera: a+= aa*y a?= (a|ε). A veces se agrega el operador complemento para dar una expresión regular generalizada ; aquí R c coincide con todas las cadenas sobre Σ* que no coinciden con R . En principio, el operador complemento es redundante, porque no otorga ningún poder más expresivo. Sin embargo, puede hacer que una expresión regular sea mucho más concisa: eliminar un operador de complemento único puede provocar una doble ampliación exponencial de su longitud. [22] [23] [24]
Las expresiones regulares en este sentido pueden expresar los lenguajes regulares, exactamente la clase de lenguajes aceptados por los autómatas finitos deterministas . Sin embargo, existe una diferencia significativa en la compacidad. Algunas clases de lenguajes regulares sólo pueden describirse mediante autómatas finitos deterministas cuyo tamaño crece exponencialmente en el tamaño de las expresiones regulares equivalentes más cortas. El ejemplo estándar aquí son los idiomas L k que consisten en todas las cadenas sobre el alfabeto { a , b } cuya k ésima desde la última letra es igual a . Por un lado, una expresión regular que describe L 4 viene dada por .
Generalizando este patrón a L k se obtiene la expresión:
Por otro lado, se sabe que todo autómata finito determinista que acepte el lenguaje L k debe tener al menos 2 k estados. Afortunadamente, existe un mapeo simple de expresiones regulares a los autómatas finitos no deterministas (NFA) más generales que no conduce a tal aumento de tamaño; por esta razón, los NFA se utilizan a menudo como representaciones alternativas de lenguajes regulares. Las NFA son una variación simple de las gramáticas de tipo 3 de la jerarquía de Chomsky . [20]
En la dirección opuesta, hay muchos lenguajes que un DFA describe fácilmente y que no se describen fácilmente mediante una expresión regular. Por ejemplo, determinar la validez de un ISBN determinado requiere calcular el módulo del número entero en base 11, y se puede implementar fácilmente con un DFA de 11 estados. Sin embargo, una expresión regular para responder al mismo problema de divisibilidad entre 11 tiene al menos varios megabytes de longitud. [ cita necesaria ]
Dada una expresión regular, el algoritmo de construcción de Thompson calcula un autómata finito no determinista equivalente. El algoritmo de Kleene logra una conversión en la dirección opuesta .
Finalmente, vale la pena señalar que muchos motores de "expresiones regulares" del mundo real implementan características que las expresiones regulares no pueden describir en el sentido de la teoría del lenguaje formal; más bien, implementan expresiones regulares . Consulte a continuación para obtener más información sobre esto.
Como se ve en muchos de los ejemplos anteriores, hay más de una forma de construir una expresión regular para lograr los mismos resultados.
Es posible escribir un algoritmo que, para dos expresiones regulares dadas, decida si los lenguajes descritos son iguales; el algoritmo reduce cada expresión a una máquina de estados finitos determinista mínima y determina si son isomorfas (equivalentes).
Las leyes algebraicas para expresiones regulares se pueden obtener utilizando un método de Gischer que se explica mejor con un ejemplo: Para comprobar si ( X + Y ) * y ( X * Y * ) * denotan el mismo lenguaje regular, para todas las expresiones regulares X , Y , es necesario y suficiente comprobar si las expresiones regulares particulares ( a + b ) * y ( a * b * ) * denotan el mismo idioma sobre el alfabeto Σ={ a , b }. De manera más general, una ecuación E = F entre términos de expresiones regulares con variables se cumple si, y sólo si, se cumple su instanciación con diferentes variables reemplazadas por diferentes símbolos constantes. [25] [26]
Cada expresión regular puede escribirse únicamente en términos de la estrella de Kleene y establecer uniones sobre palabras finitas. Éste es un problema sorprendentemente difícil. Por más simples que sean las expresiones regulares, no existe ningún método para reescribirlas sistemáticamente en alguna forma normal. La falta de un axioma en el pasado llevó al problema de la altura de las estrellas . En 1991, Dexter Kozen axiomatizó las expresiones regulares como un álgebra de Kleene , utilizando axiomas ecuacionales y de la cláusula de Horn . [27] Ya en 1964, Redko había demostrado que ningún conjunto finito de axiomas puramente ecuacionales puede caracterizar el álgebra de los lenguajes regulares. [28]
Un patrón de expresiones regulares coincide con una cadena de destino . El patrón está compuesto por una secuencia de átomos . Un átomo es un punto único dentro del patrón de expresiones regulares que intenta hacer coincidir con la cadena objetivo. El átomo más simple es un literal, pero agrupar partes del patrón para que coincidan con un átomo requerirá su uso ( )como metacaracteres. Los metacaracteres ayudan a formar: átomos ; cuantificadores que dicen cuántos átomos (y si es un cuantificador codicioso o no); un carácter lógico OR, que ofrece un conjunto de alternativas, y un carácter lógico NOT, que niega la existencia de un átomo; y referencias retrospectivas para referirse a átomos anteriores de un patrón de átomos completo. Se realiza una coincidencia, no cuando todos los átomos de la cadena coinciden, sino cuando todos los átomos del patrón en la expresión regular coinciden. La idea es hacer que un pequeño patrón de caracteres represente una gran cantidad de cadenas posibles, en lugar de compilar una lista grande de todas las posibilidades literales.
Dependiendo del procesador de expresiones regulares, hay alrededor de catorce metacaracteres, caracteres que pueden tener o no su significado literal , según el contexto, o si están "escapados", es decir, precedidos por una secuencia de escape , en este caso, la barra invertida \. Las expresiones regulares modernas y extendidas POSIX usan metacaracteres con más frecuencia que su significado literal, por lo que para evitar la "barra invertida" o el síndrome del palillo inclinado , tienen un escape de metacaracteres a un modo literal; Sin embargo, al principio tienen los cuatro metacaracteres entre corchetes ( )y { }son principalmente literales, y "escapan" de este significado habitual para convertirse en metacaracteres. Los estándares comunes implementan ambos. Los metacaracteres habituales son {}[]()^$.|*+?y \. Los personajes habituales que se convierten en metacaracteres cuando se escapan son dswDSWy N.
Al ingresar una expresión regular en un lenguaje de programación, se puede representar como una cadena literal habitual, por lo que generalmente se cita entre comillas; esto es común en C, Java y Python, por ejemplo, donde la expresión regular rese ingresa como "re". Sin embargo, a menudo se escriben con barras diagonales como delimitadores , como en el /re/caso de la expresión regular re. Esto se origina en ed , donde /está el comando del editor para realizar búsquedas, y /re/se puede usar una expresión para especificar un rango de líneas (que coincidan con el patrón), que se puede combinar con otros comandos en cualquier lado, el más famoso g/re/pcomo en grep ("global regex print"), que se incluye en la mayoría de los sistemas operativos basados en Unix , como las distribuciones de Linux . Se utiliza una convención similar en sed , donde la búsqueda y el reemplazo vienen dados por s/re/replacement/y los patrones se pueden unir con una coma para especificar un rango de líneas como en /re1/,/re2/. Esta notación es particularmente conocida debido a su uso en Perl , donde forma parte de la sintaxis distinta de los literales de cadena normales. En algunos casos, como sed y Perl, se pueden utilizar delimitadores alternativos para evitar colisiones con los contenidos y para evitar tener que escapar de las apariciones del carácter delimitador en los contenidos. Por ejemplo, en sed el comando s,/,X,reemplazará a /por an X, usando comas como delimitadores.
El estándar IEEE POSIX tiene tres conjuntos de cumplimiento: BRE (Expresiones regulares básicas), [29] ERE (Expresiones regulares extendidas) y SRE (Expresiones regulares simples). SRE está en desuso , [30] a favor de BRE, ya que ambos proporcionan compatibilidad con versiones anteriores . La siguiente subsección que cubre las clases de caracteres se aplica tanto a BRE como a ERE.
BRE y ERE trabajan juntos. ERE agrega ?, +y |, y elimina la necesidad de escapar de los metacaracteres ( )y { }, que son necesarios en BRE. Además, siempre que se respete la sintaxis estándar POSIX para expresiones regulares, puede haber, y a menudo hay, sintaxis adicional para servir aplicaciones específicas (aunque compatibles con POSIX). Aunque POSIX.2 deja algunos detalles de implementación sin definir, BRE y ERE proporcionan un "estándar" que desde entonces se ha adoptado como la sintaxis predeterminada de muchas herramientas, donde la elección de los modos BRE o ERE suele ser una opción compatible. Por ejemplo, GNU grep tiene las siguientes opciones: " grep -E" para ERE, " grep -G" para BRE (el valor predeterminado) y " grep -P" para expresiones regulares de Perl .
Las expresiones regulares de Perl se han convertido en un estándar de facto, ya que tienen un conjunto rico y poderoso de expresiones atómicas. Perl no tiene niveles "básicos" ni "extendidos". Como en los ERE POSIX, ( )y { }se tratan como metacaracteres a menos que se les escape; Se sabe que otros metacaracteres son literales o simbólicos basándose únicamente en el contexto. La funcionalidad adicional incluye coincidencia diferida, referencias inversas, grupos de captura con nombre y patrones recursivos .
En el estándar POSIX , la sintaxis regular básica ( BRE ) requiere que los metacaracteres ( ) y { }estén designados \(\)y \{\}, mientras que la sintaxis regular extendida ( ERE ) no.
Ejemplos:
.atcoincide con cualquier cadena de tres caracteres que termine en "at", incluidos "hat", "cat", "bat", "4at", "#at" y "at" (comenzando con un espacio).[hc]atcoincide con "sombrero" y "gato".[^b]atcoincide con todas las cadenas coincidentes .atexcepto "bat".[^hc]atcoincide con todas las cadenas que coinciden con .atotras que no sean "sombrero" y "gato".^[hc]atcoincide con "sombrero" y "gato", pero sólo al principio de la cadena o línea.[hc]at$coincide con "sombrero" y "gato", pero sólo al final de la cadena o línea.\[.\]coincide con cualquier carácter rodeado por "[" y "]" ya que los corchetes están en formato de escape, por ejemplo: "[a]", "[b]", "[7]", "[@]", "[]] " y "[ ]" (espacio entre corchetes).s.*coincide con s seguida de cero o más caracteres, por ejemplo: "s", "saw", "seed", "s3w96.7" y "s6#h%(>>>mn mQ".Según Ross Cox, la especificación POSIX requiere que las subexpresiones ambiguas se manejen de una manera diferente a la de Perl. El comité reemplazó las reglas de Perl por una que es fácil de explicar, pero las nuevas reglas "simples" son en realidad más complejas de implementar: eran incompatibles con las herramientas preexistentes y hacían esencialmente imposible definir una "coincidencia diferida" (ver más abajo). ) extensión. Como resultado, muy pocos programas implementan realmente las reglas de subexpresión POSIX (incluso cuando implementan otras partes de la sintaxis POSIX). [32]
El significado de los metacaracteres con una barra invertida se invierte para algunos caracteres en la sintaxis de expresión regular extendida ( ERE ) de POSIX. Con esta sintaxis, una barra invertida hace que el metacarácter se trate como un carácter literal. Así, por ejemplo, \( \)es ahora ( )y \{ \}es ahora { }. Además, se elimina la compatibilidad con referencias anteriores y se agregan los siguientes metacaracteres:\n
Ejemplos:
[hc]?atcoincide con "en", "sombrero" y "gato".[hc]*atcoincide con "at", "hat", "cat", "hhat", "chat", "hcat", "cchchat", etc.[hc]+atcoincide con "hat", "cat", "hhat", "chat", "hcat", "cchchat", etc., pero no con "at".cat|dogcoincide con "gato" o "perro".Las expresiones regulares extendidas POSIX a menudo se pueden usar con utilidades modernas de Unix al incluir el indicador de línea de comando -E .
La clase de personaje es el concepto de expresión regular más básico después de una coincidencia literal. Hace que una pequeña secuencia de caracteres coincida con un conjunto más grande de caracteres. Por ejemplo, [A-Z]podría representar cualquier letra mayúscula del alfabeto inglés y podría significar cualquier dígito. Las clases de caracteres se aplican a ambos niveles POSIX.\d
Al especificar un rango de caracteres, como [a-Z](es decir, de minúsculas aa mayúsculas Z), la configuración regional de la computadora determina el contenido mediante el orden numérico de la codificación de caracteres. Podrían almacenar dígitos en esa secuencia, o el orden podría ser abc...zABC...Z o aAbBcC...zZ . Entonces, el estándar POSIX define una clase de carácter, que será conocida por el procesador de expresiones regulares instalado. Esas definiciones se encuentran en la siguiente tabla:
Las clases de caracteres POSIX solo se pueden utilizar dentro de expresiones entre corchetes. Por ejemplo, coincide con las letras mayúsculas y minúsculas "a" y "b".[[:upper:]ab]
Una clase adicional que no es POSIX y que algunas herramientas entienden es [:word:], que generalmente se define como [:alnum:]guión bajo más. Esto refleja el hecho de que en muchos lenguajes de programación estos son los caracteres que pueden usarse en los identificadores. El editor Vim distingue además las clases de palabras y cabezas de palabras (usando la notación y ), ya que en muchos lenguajes de programación los caracteres que pueden comenzar un identificador no son los mismos que los que pueden aparecer en otras posiciones: los números generalmente se excluyen, por lo que un identificador se vería como o en notación POSIX.\w\h\h\w*[[:alpha:]_][[:alnum:]_]*
Tenga en cuenta que lo que los estándares de expresiones regulares POSIX llaman clases de caracteres se denominan comúnmente clases de caracteres POSIX en otros tipos de expresiones regulares que las admiten. Con la mayoría de los otros tipos de expresiones regulares, el término clase de carácter se usa para describir lo que POSIX llama expresiones entre corchetes .
Debido a su poder expresivo y (relativa) facilidad de lectura, muchas otras utilidades y lenguajes de programación han adoptado una sintaxis similar a la de Perl , por ejemplo, Java , JavaScript , Julia , Python , Ruby , Qt , .NET Framework de Microsoft y XML . Esquema . Algunos lenguajes y herramientas como Boost y PHP admiten múltiples tipos de expresiones regulares. Las implementaciones de expresiones regulares derivadas de Perl no son idénticas y generalmente implementan un subconjunto de características que se encuentran en Perl 5.0, lanzado en 1994. Perl a veces incorpora características que se encuentran inicialmente en otros lenguajes. Por ejemplo, Perl 5.10 implementa extensiones sintácticas desarrolladas originalmente en PCRE y Python. [33]
En Python y algunas otras implementaciones (por ejemplo, Java), los tres cuantificadores comunes ( *, +y ?) son codiciosos de forma predeterminada porque coinciden con tantos caracteres como sea posible. [34] La expresión regular ".+"(incluidas las comillas dobles) aplicada a la cadena
"Ganimedes", continuó, "es la luna más grande del Sistema Solar".
coincide con toda la línea (porque toda la línea comienza y termina con comillas dobles) en lugar de coincidir solo con la primera parte, "Ganymede,". Sin embargo, los cuantificadores antes mencionados pueden volverse vagos , mínimos o reacios , haciendo coincidir la menor cantidad de caracteres posible, agregando un signo de interrogación: ".+?"solo coincidencias "Ganymede,". [34]
En Java y Python 3.11+, [35] los cuantificadores pueden volverse posesivos agregando un signo más, que inhabilita el retroceso (en un motor de retroceso), incluso si hacerlo permitiría que la coincidencia general fuera exitosa: [36] Mientras que la expresión regular ".*"aplicado a la cuerda
"Ganimedes", continuó, "es la luna más grande del Sistema Solar".
coincide con toda la línea, la expresión regular ".*+"no coincide en absoluto , porque .*+consume toda la entrada, incluido el final ". Por tanto, los cuantificadores posesivos son más útiles con clases de caracteres negados, por ejemplo "[^"]*+", que coinciden "Ganymede,"cuando se aplican a la misma cadena.
Otra extensión común que cumple la misma función es la agrupación atómica, que deshabilita el retroceso para un grupo entre paréntesis. La sintaxis típica es (?>group) . Por ejemplo, mientras ^(wi|w)i$ coincide con wi y wii , ^(?>wi|w)i$ solo coincide con wii porque el motor tiene prohibido retroceder y, por lo tanto, no puede intentar configurar el grupo en "w" después "wi" coincidente. [37]
Los cuantificadores posesivos son más fáciles de implementar que los cuantificadores codiciosos y perezosos y, por lo general, son más eficientes en tiempo de ejecución. [36]
Muchas características que se encuentran en prácticamente todas las bibliotecas de expresiones regulares modernas brindan un poder expresivo que excede los lenguajes regulares . Por ejemplo, muchas implementaciones permiten agrupar subexpresiones con paréntesis y recuperar el valor que coinciden en la misma expresión (referencias anteriores ). Esto significa que, entre otras cosas, un patrón puede coincidir con cadenas de palabras repetidas como "papá" o "WikiWiki", llamadascuadradosen la teoría del lenguaje formal. El patrón de estas cuerdas es(.+)\1.
El lenguaje de los cuadrados no es regular ni está libre de contexto , debido al lema de bombeo . Sin embargo, la coincidencia de patrones con un número ilimitado de referencias anteriores, respaldada por numerosas herramientas modernas, sigue siendo sensible al contexto . [38] El problema general de hacer coincidir cualquier número de referencias inversas es NP-completo , y el tiempo de ejecución de algoritmos conocidos crece exponencialmente según la cantidad de grupos de referencias inversas utilizados. [39]
Sin embargo, muchas herramientas, bibliotecas y motores que proporcionan este tipo de construcciones todavía utilizan el término expresión regular para sus patrones. Esto ha llevado a una nomenclatura en la que el término expresión regular tiene diferentes significados en la teoría del lenguaje formal y la coincidencia de patrones. Por esta razón, algunas personas han empezado a utilizar el término expresión regular , expresión regular o simplemente patrón para describir este último. Larry Wall , autor del lenguaje de programación Perl, escribe en un ensayo sobre el diseño de Raku:
Las "expresiones regulares" […] están sólo marginalmente relacionadas con las expresiones regulares reales. Sin embargo, el término ha crecido con las capacidades de nuestros motores de coincidencia de patrones, por lo que no voy a intentar luchar aquí contra la necesidad lingüística. Sin embargo, generalmente los llamaré "regexen" (o "regexen", cuando estoy en un estado de ánimo anglosajón). [dieciséis]
Otras características que no se encuentran en la descripción de lenguajes regulares incluyen las afirmaciones. Estos incluyen el omnipresente ^y $, utilizado al menos desde 1970, [40] así como algunas extensiones más sofisticadas como lookaround que apareció en 1994. [41] Los lookarounds definen el entorno de una partida y no se extienden a la partida en sí, una característica Sólo es relevante para el caso de uso de búsqueda de cadenas [ cita requerida ] . Algunos de ellos pueden simularse en un lenguaje normal tratando el entorno también como parte del lenguaje. [42]
Elaserciones de anticipación (?=...) y(?!...)han sido atestiguadas desde al menos 1994, comenzando con Perl 5. [41] Las afirmaciones de anticipación(?<=...)y(?<!...)están atestiguadas desde 1997 en un compromiso de Ilya Zakharevich con Perl 5.005. [43]
Hay al menos tres algoritmos diferentes que deciden si una expresión regular determinada coincide con una cadena y cómo.
El más antiguo y rápido se basa en un resultado de la teoría del lenguaje formal que permite que cada autómata finito no determinista (NFA) se transforme en un autómata finito determinista (DFA). El DFA se puede construir explícitamente y luego ejecutarse en la cadena de entrada resultante, un símbolo a la vez. La construcción del DFA para una expresión regular de tamaño m tiene un costo de tiempo y memoria de O (2 m ), pero se puede ejecutar en una cadena de tamaño n en un tiempo O ( n ). Tenga en cuenta que el tamaño de la expresión es el tamaño después de que se hayan ampliado las abreviaturas, como los cuantificadores numéricos.
Un enfoque alternativo es simular la NFA directamente, esencialmente construyendo cada estado de DFA según la demanda y luego descartándolo en el siguiente paso. Esto mantiene el DFA implícito y evita el costo de construcción exponencial, pero el costo de funcionamiento aumenta a O ( mn ). El enfoque explícito se denomina algoritmo DFA y el enfoque implícito, algoritmo NFA. Agregar almacenamiento en caché al algoritmo NFA a menudo se denomina algoritmo "DFA diferido", o simplemente algoritmo DFA sin hacer distinción. Estos algoritmos son rápidos, pero usarlos para recordar subexpresiones agrupadas, cuantificación diferida y características similares es complicado. [44] [45] Las implementaciones modernas incluyen la familia re1- re2 -sregex basada en el código de Cox.
El tercer algoritmo consiste en hacer coincidir el patrón con la cadena de entrada retrocediendo . Este algoritmo se denomina comúnmente NFA, pero esta terminología puede resultar confusa. Su tiempo de ejecución puede ser exponencial, lo que exhiben implementaciones simples cuando se comparan con expresiones como las que contienen alternancia y cuantificación ilimitada y obligan al algoritmo a considerar un número exponencialmente creciente de subcasos. Este comportamiento puede causar un problema de seguridad llamado Denegación de servicio de expresión regular (ReDoS).(a|aa)*b
Aunque las implementaciones de retroceso solo ofrecen una garantía exponencial en el peor de los casos, proporcionan mucha mayor flexibilidad y poder expresivo. Por ejemplo, cualquier implementación que permita el uso de referencias retrospectivas, o que implemente las diversas extensiones introducidas por Perl, debe incluir algún tipo de retroceso. Algunas implementaciones intentan ofrecer lo mejor de ambos algoritmos ejecutando primero un algoritmo DFA rápido y volviendo a un algoritmo de retroceso potencialmente más lento solo cuando se encuentra una referencia inversa durante la coincidencia. GNU grep (y el gnulib DFA subyacente) utiliza dicha estrategia. [46]
Se han logrado algoritmos de tiempo de ejecución sublineal utilizando algoritmos basados en Boyer-Moore (BM) y técnicas de optimización DFA relacionadas, como el escaneo inverso. [47] GNU grep, que admite una amplia variedad de sintaxis y extensiones POSIX, utiliza BM para un prefiltrado de primer paso y luego utiliza un DFA implícito. Wu agrep , que implementa una coincidencia aproximada, combina el filtrado previo en DFA en BDM (coincidencia DAWG hacia atrás). BNDM de NR-grep amplía la técnica BDM con paralelismo a nivel de bits Shift-Or. [48]
Existen algunas alternativas teóricas al retroceso de las referencias retrospectivas, y sus "exponentes" son más suaves porque solo están relacionados con el número de referencias retrospectivas, una propiedad fija de algunos lenguajes de expresiones regulares como POSIX. Un método ingenuo que duplica un NFA sin seguimiento para cada nota de referencia tiene una complejidad de tiempo y espacio para un pajar de longitud n y k referencias en RegExp. [49] Un trabajo teórico muy reciente basado en autómatas de memoria proporciona un límite más estricto basado en los nodos variables "activos" utilizados y una posibilidad polinómica para algunas expresiones regulares con referencias inversas. [50]
En términos teóricos, cualquier conjunto de tokens puede coincidir con expresiones regulares siempre que esté predefinido. En términos de implementaciones históricas, las expresiones regulares se escribieron originalmente para usar caracteres ASCII como conjunto de tokens, aunque las bibliotecas de expresiones regulares han admitido muchos otros conjuntos de caracteres . Muchos motores de expresiones regulares modernos ofrecen al menos algo de soporte para Unicode . En la mayoría de los aspectos, no importa cuál sea el conjunto de caracteres, pero surgen algunos problemas al extender las expresiones regulares para admitir Unicode.
[x-y]son válidos siempre que x e y tengan puntos de código en el rango [0x00,0x7F] y punto de código ( x ) ≤ punto de código ( y ). La extensión natural de dichos rangos de caracteres a Unicode simplemente cambiaría el requisito de que los puntos finales se encuentren en [0x00,0x7F] al requisito de que se encuentren en [0x0000,0x10FFFF]. Sin embargo, en la práctica esto no suele ser así. Algunas implementaciones, como la de gawk , no permiten que rangos de caracteres crucen bloques Unicode. Un rango como [0x61,0x7F] es válido ya que ambos puntos finales caen dentro del bloque latino básico, al igual que [0x0530,0x0560] ya que ambos puntos finales caen dentro del bloque armenio, pero un rango como [0x0061,0x0532] no es válido ya que incluye múltiples bloques Unicode. Otros motores, como el del editor Vim , permiten el cruce de bloques, pero los valores de los caracteres no deben estar separados por más de 256. [51]java.util.regexbiblioteca, las propiedades de la forma coinciden \p{InX}con \p{Block=X}caracteres en el bloque X o coinciden con puntos de código \P{InX}que \P{Block=X}no están en ese bloque. De manera similar, \p{Armenian}, \p{IsArmenian}o \p{Script=Armenian}coincide con cualquier carácter de la escritura armenia. En general, \p{X}coincide con cualquier carácter con la propiedad binaria X o la categoría general X. Por ejemplo, \p{Lu}, \p{Uppercase_Letter}o \p{GC=Lu}coincide con cualquier letra mayúscula. Las propiedades binarias que no son categorías generales incluyen \p{White_Space}, \p{Alphabetic}, \p{Math}y \p{Dash}. Ejemplos de propiedades no binarias son \p{Bidi_Class=Right_to_Left}, \p{Word_Break=A_Letter}y \p{Numeric_Value=10}.La mayoría de los lenguajes de programación de propósito general admiten capacidades de expresiones regulares, ya sea de forma nativa o mediante bibliotecas . El soporte integral está incluido en:
Las expresiones regulares son útiles en una amplia variedad de tareas de procesamiento de texto y, en general , en el procesamiento de cadenas , donde los datos no necesitan ser textuales. Las aplicaciones comunes incluyen validación de datos , raspado de datos (especialmente raspado web ), manipulación de datos , análisis simple , producción de sistemas de resaltado de sintaxis y muchas otras tareas.
Si bien las expresiones regulares serían útiles en los motores de búsqueda de Internet , procesarlas en toda la base de datos podría consumir recursos informáticos excesivos dependiendo de la complejidad y el diseño de la expresión regular. Aunque en muchos casos los administradores de sistemas pueden ejecutar consultas basadas en expresiones regulares internamente, la mayoría de los motores de búsqueda no ofrecen soporte para expresiones regulares al público. Las excepciones notables incluyen Google Code Search y Exalead . Sin embargo, Google Code Search se cerró en enero de 2012. [62]
Las reglas de sintaxis específicas varían según la implementación específica, el lenguaje de programación o la biblioteca en uso. Además, la funcionalidad de las implementaciones de expresiones regulares puede variar entre versiones .
Debido a que las expresiones regulares pueden ser difíciles de explicar y comprender sin ejemplos, los sitios web interactivos para probar expresiones regulares son un recurso útil para aprenderlas mediante experimentación. Esta sección proporciona una descripción básica de algunas de las propiedades de las expresiones regulares a modo de ilustración.
En los ejemplos se utilizan las siguientes convenciones. [63]
metacaracteres ;; la columna de metacaracteres especifica la sintaxis de expresiones regulares que se demuestra=~ m// ;; indica una operación de coincidencia de expresiones regulares en Perl=~ s/// ;; indica una operación de sustitución de expresiones regulares en Perl
También vale la pena señalar que estas expresiones regulares tienen una sintaxis similar a Perl. Las expresiones regulares POSIX estándar son diferentes.
A menos que se indique lo contrario, los siguientes ejemplos se ajustan al lenguaje de programación Perl , versión 5.8.8, 31 de enero de 2006. Esto significa que otras implementaciones pueden carecer de soporte para algunas partes de la sintaxis que se muestra aquí (por ejemplo, expresiones regulares básicas versus extendidas, \( \)versus expresiones regulares. (), o falta de \den lugar de POSIX [:digit:] ).
La sintaxis y las convenciones utilizadas en estos ejemplos también coinciden con las de otros entornos de programación. [64]
Las expresiones regulares a menudo se pueden crear ("inducir" o "aprender") basándose en un conjunto de cadenas de ejemplo. Esto se conoce como inducción de lenguajes regulares y es parte del problema general de la inducción gramatical en la teoría del aprendizaje computacional . Formalmente, dados ejemplos de cadenas en un lenguaje regular, y quizás también ejemplos de cadenas que no están en ese lenguaje regular, es posible inducir una gramática para el lenguaje, es decir, una expresión regular que genera ese lenguaje. No todos los lenguajes regulares pueden inducirse de esta manera (ver identificación de lenguaje en el límite ), pero muchos sí. Por ejemplo, el conjunto de ejemplos {1, 10, 100} y el conjunto negativo (de contraejemplos) {11, 1001, 101, 0} se pueden utilizar para inducir la expresión regular 1⋅0* (1 seguido de cero o más 0).
Kleene introdujo el concepto de eventos regulares mediante la definición de expresiones regulares.
Esta propiedad no tiene por qué ser válida para expresiones regulares extendidas, incluso si no describen una clase más grande que los lenguajes regulares; cf. pág.121.
Digresión: subcoincidencia POSIX
Si el escáner detecta una transición en la referencia inversa, devuelve una especie de "semiéxito" que indica que la coincidencia deberá verificarse con un comparador de retroceso.
m/[^abc]/también podría representarse como /[^abc]/. La 'm' solo es necesaria si el usuario desea especificar una operación de coincidencia sin utilizar una barra diagonal como delimitador de expresiones regulares . A veces es útil especificar un delimitador de expresiones regulares alternativo para evitar una " colisión de delimitadores ". Consulte 'perldoc perlre Archivado el 31 de diciembre de 2009 en Wayback Machine ' para obtener más detalles.
Medios relacionados con Regex en Wikimedia Commons