Hispanopedia Wiki
Articulo de referencia

Expresión regular

/r[aeiou]+/g (lowercase ''r'' followed by one or more lowercase vowels)."},"text":{"wt":"Blue"}},"i":0}}]}"> Las zonas resaltadas en azul muestran los resultados de la coincid...

Hispanopedia WikiContenido en espanolLectura gratuita
Las zonas resaltadas en azul  muestran los resultados de la coincidencia con el patrón de expresión regular: ( r minúsculaseguida de una o más vocales minúsculas)./r[aeiou]+/g

Una 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 un texto . Por lo general, estos patrones son utilizados por algoritmos de búsqueda de cadenas para operaciones de "búsqueda" o "búsqueda y reemplazo" en cadenas , o para la validación de entrada . Las técnicas de expresiones regulares se desarrollan en la informática teórica y la teoría del lenguaje formal .

El concepto de expresiones regulares surgió en la década de 1950, cuando el matemático estadounidense Stephen Cole Kleene formalizó el concepto de lenguaje regular . Su uso se popularizó con las utilidades de procesamiento de texto de Unix . Desde la década de 1980, existen diferentes sintaxis para escribir expresiones regulares, entre ellas el estándar POSIX y la sintaxis de Perl , ampliamente utilizada .

Las expresiones regulares se utilizan en motores de búsqueda , en los 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 el análisis léxico . Muchos lenguajes de programación admiten expresiones regulares. Las implementaciones de bibliotecas suelen denominarse « motores » [ 4 ] [ 5 ] , y muchas de ellas están disponibles para su reutilización.

Historia

Stephen Cole Kleene , quien introdujo el concepto.

Las expresiones regulares se originaron en 1951, cuando el matemático Stephen Cole Kleene describió lenguajes regulares usando su notación matemática llamada eventos regulares . [ 6 ] [ 7 ] Estas surgieron en la ciencia de la computación 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 , motivadas por el intento de Kleene de describir las primeras redes neuronales artificiales . (Kleene lo introdujo como una alternativa a "comprensible" de McCulloch y Pitts , pero admitió "Agradeceríamos cualquier sugerencia sobre un término más descriptivo." [ 8 ] ) 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 se popularizaron a partir de 1968 en dos aplicaciones: coincidencia de patrones en un editor de texto [ 9 ] y análisis léxico en un compilador. [ 10 ] Entre las primeras apariciones de expresiones regulares en forma de programa se encuentra cuando Ken Thompson incorporó la notación de Kleene al editor QED como un medio para hacer coincidir patrones en archivos de texto . [ 9 ] [ 11 ] [ 12 ] [ 13 ] Para mayor velocidad, Thompson implementó la coincidencia de expresiones regulares mediante compilación justo a tiempo (JIT) en el código IBM 7094 en el Compatible Time-Sharing System , un importante ejemplo temprano de compilación JIT. [ 14 ] Posteriormente, añadió esta capacidad al editor Unix ed , lo que finalmente condujo 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 ed: significa "Búsqueda global de expresiones regulares e impresión de líneas coincidentes"). [ 15 ] Casi al mismo tiempo que Thompson desarrolló QED, un grupo de investigadores, entre ellos 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 . [ 10 ]g/re/p

En la década de 1970, en los programas de Unix [ 13 ] de Bell Labs , se utilizaron numerosas variantes de estas formas originales de expresiones regulares , como lex , sed , AWK y expr , así como en otros programas como vi y Emacs (que posee una sintaxis y un comportamiento propios e incompatibles). 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, las expresiones regulares más complejas surgieron en Perl , que originalmente derivaba de una biblioteca de expresiones regulares escrita por Henry Spencer (1986), quien más tarde escribió una implementación para Tcl llamada Advanced Regular Expressions . [ 16 ] 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 de Tcl de Spencer incluyen PostgreSQL . [ 17 ] Perl luego amplió la biblioteca original de Spencer para agregar muchas características nuevas. [ 18 ] 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 expresiones de análisis . [ 19 ] El resultado es un mini-lenguaje llamado reglas Raku , que se utilizan para definir la gramática Raku, así como para proporcionar una herramienta a los programadores en el lenguaje. Estas reglas conservan las características existentes de las expresiones regulares de Perl 5.x, pero también permiten la definición, al estilo BNF , de un analizador sintáctico descendente recursivo mediante subreglas.

El uso de expresiones regulares en los 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 con la consolidación de estándares industriales como ISO SGML (precursor de ANSI "GCA 101-1983"). El núcleo de los estándares del lenguaje de especificación de estructura se basa en expresiones regulares. Su uso es evidente en la sintaxis de grupos de elementos DTD . Antes del uso de expresiones regulares, muchos lenguajes de búsqueda permitían el uso de comodines simples, por ejemplo, "*" para coincidir con cualquier secuencia de caracteres y "?" para coincidir con un solo carácter. Aún hoy se pueden encontrar vestigios de esto en la sintaxis glob para nombres de archivo y en el operador SQLLIKE .

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 utilizada por muchas herramientas modernas, incluyendo PHP y Apache HTTP Server . [ 20 ]

Hoy en día, las expresiones regulares son ampliamente compatibles con lenguajes de programación, programas de procesamiento de texto (en particular, analizadores léxicos ), editores de texto avanzados y otros programas. La compatibilidad con expresiones regulares forma parte de la biblioteca estándar de muchos lenguajes de programación, incluidos Java y Python , y está integrada en la sintaxis de otros, como Perl y ECMAScript . A finales de la década de 2010, varias empresas comenzaron a ofrecer implementaciones de hardware, FPGA , [ 21 ] GPU [ 22 ] de motores de expresiones regulares compatibles con PCRE que son más rápidos en comparación con las implementaciones de CPU .

Patrones

La frase expresiones regulares , o regex , se usa a menudo para referirse a la sintaxis textual estándar específica para representar patrones de coincidencia de texto, a diferencia de la notación matemática que se describe a continuación. Cada carácter en una expresión regular (es decir, cada carácter en la cadena que describe su patrón) es un metacaracter , que tiene un significado especial, o un carácter regular que tiene un significado literal. Por ejemplo, en la regex b., 'b' es un carácter literal que coincide solo con 'b', mientras que '.' es un metacaracter que coincide con cualquier carácter excepto un salto de línea. Por lo tanto, esta regex coincide, por ejemplo, con 'b%', o 'bx', o 'b5'. Juntos, los metacaracteres y los caracteres literales se pueden usar para identificar texto de un patrón dado o procesar varias instancias del mismo. Las coincidencias de patrones pueden variar desde una igualdad precisa hasta una similitud muy general, según lo controlen 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 predefinidos de forma concisa y flexible, con el fin de dirigir la automatización del procesamiento de texto de diversos datos de entrada, en un formato fácil de escribir utilizando un teclado ASCII estándar .

Un ejemplo muy sencillo de expresión regular en esta sintaxis consiste en localizar una palabra escrita de dos maneras diferentes en un editor de texto ; por ejemplo, la expresión regular seriali[sz]ecoincide tanto con "serialise" como con "serialize". Los caracteres comodín también logran esto, pero son más limitados en cuanto a los patrones que pueden generar, ya que tienen menos metacaracteres y una base lingüística más simple.

El contexto habitual de los caracteres comodín es la búsqueda de nombres similares en una lista de archivos, mientras que las expresiones regulares se suelen emplear en aplicaciones que realizan coincidencias de patrones en 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+)?

Traducción de la estrella de Kleene ( s * significa "cero o más de s ")

Un procesador de expresiones regulares traduce una expresión regular con la sintaxis anterior a una representación interna que puede ejecutarse y compararse con una cadena que representa el texto que se busca. Un posible enfoque es el algoritmo de construcción de Thompson para construir un autómata finito no determinista (AFN), que luego se convierte en determinista y el autómata finito determinista (AFD) resultante se ejecuta en la cadena de texto objetivo para reconocer subcadenas que coinciden con la expresión regular. La imagen muestra el esquema del AFN obtenido a partir de la expresión regular , donde s denota una expresión regular más simple a su vez, que ya ha sido traducida recursivamente al AFN N ( s ).N(s*)s*

Conceptos básicos

Una expresión regular, a menudo llamada 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 cadenas. Sin embargo, puede haber muchas formas de escribir una expresión regular para el mismo conjunto de cadenas: por ejemplo, (Hän|Han|Haen)deltambién especifica el mismo conjunto de tres cadenas en este ejemplo.

La mayoría de los formalismos proporcionan las siguientes operaciones para construir expresiones regulares.

operador booleano "o"
Una barra vertical separa las alternativas. Por ejemplo, puede coincidir con "gris" o "gris".gray|grey
Agrupamiento
Los paréntesis se utilizan para definir el alcance y la precedencia de los operadores (entre otros usos). Por ejemplo, gray|greyy son patrones equivalentes que describen el conjunto de "gris" o "gris".gr(a|e)y
Cuantificación
Un cuantificador después de un elemento (como un token , un carácter o un grupo) especifica cuántas veces se permite que se repita el elemento precedente. Los cuantificadores más comunes son el signo de interrogación? , el asterisco* (derivado de la estrella de Kleene ) y el signo más+ ( Kleene plus ).
Comodín
El comodín .coincide con cualquier carácter. Por ejemplo,
a.bcoincide con cualquier cadena que contenga una "a", luego cualquier carácter y luego una "b".
a.*bcoincide con cualquier cadena que contenga una "a" y, a continuación, el carácter "b" en algún punto posterior.

Estas construcciones se pueden combinar para formar expresiones arbitrariamente complejas, de forma muy similar a como se pueden construir expresiones aritméticas a partir de números y las operaciones +, −, × y ÷.

La sintaxis precisa para las expresiones regulares varía según las herramientas y el contexto; se ofrece más información en la sección  Sintaxis .

teoría del lenguaje formal

Las expresiones regulares describen lenguajes regulares en la teoría del lenguaje formal . Tienen el mismo poder expresivo que las gramáticas regulares . Pero el lenguaje de las expresiones regulares en sí mismo es un lenguaje libre de contexto .

Definición formal

Las expresiones regulares constan de constantes, que denotan conjuntos de cadenas, y símbolos de operadores, 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 de lenguajes formales. [ 24 ] [ 25 ] Dado un alfabeto finito Σ, las siguientes constantes se definen como expresiones regulares:

  • ( conjunto vacío ) ∅ que denota el conjunto ∅.
  • ( cadena vacía ) ε que denota el conjunto que contiene solo la cadena "vacía", que no tiene ningún carácter.
  • ( carácter literal ) aen Σ que denota el conjunto que contiene solo el carácter a .

Dadas las expresiones regulares R y S, se definen las siguientes operaciones sobre ellas para producir expresiones regulares:

  • ( concatenación ) (RS)denota el conjunto de cadenas que se pueden obtener al concatenar una cadena aceptada por R y una cadena aceptada por S (en ese orden). Por ejemplo, sea R la cadena {"ab", "c"} y S la cadena {"d", "ef"}. Entonces, (RS)denota {"abd", "abef", "cd", "cef"}.
  • ( alternancia ) (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 {"ab", "c", "d", "ef"}.
  • ( La estrella de Kleene ) (R*)denota el superconjunto más pequeño del conjunto descrito por R que contiene ε y es cerrado bajo la 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 las 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 asume que la estrella de Kleene tiene la máxima prioridad, seguida de la concatenación y, por último, la alternancia. Si no hay ambigüedad, se pueden omitir los paréntesis. Por ejemplo, (ab)cse puede escribir como abc, y a|(b(c*))se puede escribir como a|bc*. Muchos libros de texto utilizan los símbolos ∪, + o ∨ para la 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 otros símbolos que no sean "a" y "b", incluyendo 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 derivada de una expresión regular se puede definir utilizando la derivada de Brzozowski .

Poder expresivo y compacidad

La definición formal de expresiones regulares es mínima a propósito y evita definir ?y +—estos 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 mayor poder expresivo. Sin embargo, puede hacer que una expresión regular sea mucho más concisa; eliminar un solo operador complemento puede causar un aumento exponencial doble de su longitud. [ 26 ] [ 27 ] [ 28 ]

Las expresiones regulares en este sentido pueden expresar los lenguajes regulares, precisamente la clase de lenguajes aceptados por autómatas finitos deterministas . Sin embargo, existe una diferencia significativa en compacidad. Algunas clases de lenguajes regulares solo 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 lenguajes L k que consisten en todas las cadenas sobre el alfabeto { a , b } cuya k -ésima letra desde el final es igual a a . Por un lado, una expresión regular que describe L 4 viene dada por  (a∣b)∗a(a∣b)(a∣b)(a∣b){\displaystyle (a\mid b)^{*}a(a\mid b)(a\mid b)(a\mid b)}.

Generalizando este patrón a L k se obtiene la expresión:

(a∣b)∗a(a∣b)(a∣b)⋯(a∣b)⏟k−1 veces.{\displaystyle (a\mid b)^{*}a\underbrace {(a\mid b)(a\mid b)\cdots (a\mid b)} _{k-1{\text{ veces}}}.\,}

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 una correspondencia simple entre expresiones regulares y autómatas finitos no deterministas (AFN) más generales que no produce tal aumento de tamaño; por esta razón, los AFN se utilizan a menudo como representaciones alternativas de lenguajes regulares. Los AFN son una variación simple de las gramáticas de tipo 3 de la jerarquía de Chomsky . [ 24 ]

En sentido contrario, existen muchos lenguajes que se describen fácilmente mediante un autómata finito determinista (AFD) pero que no se describen fácilmente mediante una expresión regular. Por ejemplo, determinar la validez de un ISBN requiere calcular el resto de un número entero módulo 11, y se puede implementar fácilmente con un AFD de 11 estados. Sin embargo, convertirlo a una expresión regular da como resultado un archivo de 2,14 megabytes. [ 29 ]

Dado 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, muchos motores de "expresiones regulares" del mundo real implementan características que no pueden describirse mediante expresiones regulares en el sentido de la teoría del lenguaje formal; en cambio, implementan regex . Véase más abajo para más información al respecto.

Determinación de la equivalencia de expresiones regulares

Como se puede observar en muchos de los ejemplos anteriores, existe 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 isomorfos (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 lenguaje sobre el alfabeto Σ={ a , b }. De forma más general, una ecuación E = F entre términos de expresiones regulares con variables se cumple si, y solo si, su instanciación con diferentes variables sustituidas por diferentes constantes de símbolo se cumple. [ 30 ] [ 31 ]

Toda expresión regular puede escribirse únicamente en términos de la estrella de Kleene y uniones de conjuntos sobre palabras finitas. Este es un problema sorprendentemente difícil. Por simples que sean las expresiones regulares, no existe un método para reescribirlas sistemáticamente a alguna forma normal. La falta de axiomas en el pasado condujo al problema de la altura de la estrella . En 1991, Dexter Kozen axiomatizó las expresiones regulares como un álgebra de Kleene , utilizando axiomas de cláusulas ecuacionales y de Horn . [ 32 ] Ya en 1964, Redko había demostrado que ningún conjunto finito de axiomas puramente ecuacionales puede caracterizar el álgebra de los lenguajes regulares. [ 33 ]

Sintaxis

Un patrón de expresiones regulares coincide con una cadena objetivo . El patrón se compone de una secuencia de átomos . Un átomo es un punto individual dentro del patrón de expresiones regulares que intenta 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á el uso de metacaracteres. Los metacaracteres ayudan a formar: átomos ; cuantificadores que indican cuántos átomos hay (y si se trata de 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 inversas para referirse a átomos anteriores de un patrón de átomos que se completa. Se produce una coincidencia, no cuando coinciden todos los átomos de la cadena, sino cuando coinciden todos los átomos del patrón en la expresión regular. La idea es que un pequeño patrón de caracteres represente un gran número de cadenas posibles, en lugar de compilar una larga lista de todas las posibilidades literales.( )

Dependiendo del procesador de expresiones regulares, hay alrededor de catorce metacaracteres, caracteres que pueden o no tener su significado literal , dependiendo del 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-osis" o el síndrome del palillo inclinado , tienen un escape de metacaracter a un modo literal; sin embargo, al principio, en su lugar tienen los cuatro metacaracteres de 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 caracteres habituales que se convierten en metacaracteres cuando se escapan son y .( ){ } {}[]()^$.|*+?\dswDSWN

delimitadores

Al introducir una expresión regular en un lenguaje de programación, puede representarse como una cadena literal habitual, por lo que normalmente se entrecomilla; esto es común en C, Java y Python, por ejemplo, donde la expresión regular rese introduce como "re". Sin embargo, a menudo se escriben con barras diagonales como delimitadores , como en /re/para la expresión regular re. Esto tiene su origen en ed , donde es el comando del editor para buscar, y 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 a ambos lados, el más famoso como en grep ("impresión de expresiones regulares globales"), que se incluye en la mayoría de los sistemas operativos basados ​​en Unix , como las distribuciones de Linux . Una convención similar se usa en sed , donde la búsqueda y el reemplazo se dan por y los patrones se pueden unir con una coma para especificar un rango de líneas como en . Esta notación es particularmente conocida debido a su uso en Perl , donde forma parte de la sintaxis distinta de las cadenas literales normales. En algunos casos, como en sed y Perl, se pueden usar delimitadores alternativos para evitar colisiones con el contenido y para evitar tener que escapar las ocurrencias del carácter delimitador en el contenido. Por ejemplo, en sed el comando reemplazará una con una , usando comas como delimitadores./re/g/re/ps/re/replacement//re1/,/re2/s,/,X,/X

Estándar IEEE POSIX

El estándar IEEE POSIX tiene tres conjuntos de cumplimiento: BRE (Expresiones Regulares Básicas), [ 34 ] ERE (Expresiones Regulares Extendidas) y SRE (Expresiones Regulares Simples). SRE está obsoleto , [ 35 ] en favor de BRE, ya que ambos proporcionan compatibilidad con versiones anteriores . La subsección siguiente 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 los metacaracteres y , que son necesarios en BRE. Además, siempre que se cumpla la sintaxis estándar POSIX para regexs, puede haber, y a menudo hay, sintaxis adicional para servir aplicaciones específicas (pero compatibles con POSIX). Aunque POSIX.2 deja algunos detalles de implementación sin definir, BRE y ERE proporcionan un "estándar" que desde entonces ha sido 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 tiene las siguientes opciones: " " para ERE, y " " para BRE (el predeterminado), y " " para regexs de Perl .( ){ }grepgrep -Egrep -Ggrep -P

Las expresiones regulares de Perl se han convertido en un estándar de facto, con un conjunto rico y potente de expresiones atómicas. Perl no tiene niveles "básicos" ni "extendidos". Al igual que en las expresiones regulares extendidas de POSIX, se tratan como metacaracteres a menos que se escapen; otros metacaracteres se consideran literales o simbólicos según el contexto. La funcionalidad adicional incluye coincidencia diferida , retroreferencias , grupos de captura con nombre y patrones recursivos .( ){ }

POSIX básico y extendido

En el estándar POSIX , la Sintaxis Regular Básica ( BRE ) requiere que los metacaracteres y se designen como y , mientras que la Sintaxis Regular Extendida ( ERE ) no lo requiere.( ){ }\(\)\{\}

Ejemplos:

  • .atcoincide con cualquier cadena de tres caracteres que termine en "at", incluyendo "hat", "cat", "bat", "4at", "#at" y "at" (que comienza con un espacio).
  • [hc]atcoincide "sombrero" y "gato".
  • [^b]atcoincide con todas las cadenas coincidentes por .atexcepto "bat".
  • [^hc]atcoincide con todas las cadenas que coinciden con .atexcepto "hat" y "cat".
  • ^[hc]atcoincide con "sombrero" y "gato", pero solo al principio de la cadena o línea.
  • [hc]at$coincide con "sombrero" y "gato", pero solo al final de la cadena o línea.
  • \[.\]coincide con cualquier carácter individual rodeado de "[" y "]" ya que los corchetes se escapan, por ejemplo: "[a]", "[b]", "[7]", "[@]", "[]]" y "[ ]" (corchete espacio corchete).
  • s.*coincide con s seguido de cero o más caracteres, por ejemplo: "s", "saw", "seed", "s3w96.7" y "s6#h%(>>>mn mQ".

Según Russ Cox, la especificación POSIX exige que las subexpresiones ambiguas se manejen de una manera diferente a la de Perl. El comité reemplazó las reglas de Perl por unas sencillas de explicar, pero estas nuevas reglas "sencillas" son en realidad más complejas de implementar: eran incompatibles con las herramientas preexistentes e imposibilitaban prácticamente la definición de una extensión de "coincidencia diferida" (véase más adelante). Como resultado, muy pocos programas implementan las reglas de subexpresiones POSIX (incluso cuando implementan otras partes de la sintaxis POSIX). [ 37 ]

Metacaracteres en POSIX extendido

El significado de los metacaracteres escapados con una barra invertida se invierte para algunos caracteres en la sintaxis de expresiones regulares extendidas ( ERE ) de POSIX. Con esta sintaxis, una barra invertida hace que el metacaracter se trate como un carácter literal. Así, por ejemplo, ahora es y ahora es . Además, se elimina la compatibilidad con las retroreferencias y se agregan los siguientes metacaracteres:\( \)( )\{ \}{ }\n

Ejemplos:

  • [hc]?atcoincide con "at", "hat" y "cat".
  • [hc]*atcoincide con "at", "hat", "cat", "hhat", "chat", "hcat", "cchchat", y así sucesivamente.
  • [hc]+atcoincide con "hat", "cat", "hhat", "chat", "hcat", "cchchat", etc., pero no con "at".
  • cat|dogcoincide con "gato" o "perro".

Las expresiones regulares extendidas de POSIX a menudo se pueden usar con utilidades modernas de Unix incluyendo el indicador de línea de comandos -E .

Clases de personajes

La clase de caracteres es el concepto más básico de las expresiones regulares después de una coincidencia literal. Permite 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 por ejemplo [a-Z](de minúsculas aa mayúsculas Z), la configuración regional del ordenador determina el contenido según 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 . Por lo tanto, el estándar POSIX define una clase de caracteres, que será reconocida por el procesador de expresiones regulares instalado. Dichas definiciones se encuentran en la siguiente tabla:

Las clases de caracteres POSIX solo se pueden usar dentro de expresiones entre corchetes. Por ejemplo, coincide con las letras mayúsculas y minúsculas "a" y "b".[[:upper:]ab]

Una clase adicional no POSIX que entienden algunas herramientas es [:word:], que normalmente se define como [:alnum:]más un guion bajo. 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 palabra (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 conoce comúnmente como clases de caracteres POSIX en otras variantes de expresiones regulares que las admiten. En la mayoría de las demás variantes de expresiones regulares, el término clase de caracteres se utiliza para describir lo que POSIX llama expresiones entre corchetes .

Perl y PCRE

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 , el .NET Framework de Microsoft y XML Schema . Algunos lenguajes y herramientas como Boost y PHP admiten múltiples variantes de expresiones regulares. Las implementaciones de expresiones regulares derivadas de Perl no son idénticas y generalmente implementan un subconjunto de características presentes en Perl 5.0, lanzado en 1994. En ocasiones, Perl incorpora características que inicialmente se encontraban en otros lenguajes. Por ejemplo, Perl 5.10 implementa extensiones sintácticas desarrolladas originalmente en PCRE y Python. [ 38 ]

Emparejamiento perezoso

En Python y algunas otras implementaciones (por ejemplo, Java), los tres cuantificadores comunes ( *, +, y ?) son codiciosos por defecto porque coinciden con tantos caracteres como sea posible. [ 39 ] La expresión regular ".+"(incluidas las comillas dobles) aplicada a la cadena

"Ganímedes", continuó, "es la luna más grande del Sistema Solar".

coincide con la línea completa (porque la línea completa comienza y termina con una comilla doble) en lugar de coincidir solo con la primera parte, "Ganymede,". Sin embargo, los cuantificadores mencionados anteriormente pueden hacerse perezosos , mínimos o reacios , coincidiendo con la menor cantidad de caracteres posible, agregando un signo de interrogación: ".+?"coincide solo "Ganymede,". [ 39 ]

Coincidencia posesiva

En Java y Python 3.11+, [ 40 ] los cuantificadores pueden hacerse posesivos agregando un signo más, lo que desactiva el retroceso (en un motor de retroceso), incluso si hacerlo permitiera que la coincidencia general tuviera éxito: [ 41 ] Mientras que la expresión regular ".*"aplicada a la cadena

"Ganímedes", 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 lo tanto, los cuantificadores posesivos son más útiles con clases de caracteres negadas, por ejemplo "[^"]*+", que coincide "Ganymede,"cuando se aplica a la misma cadena.

Otra extensión común que cumple la misma función es el agrupamiento atómico, que desactiva el retroceso para un grupo entre paréntesis. La sintaxis típica es (? > grupo) . Por ejemplo, mientras que ^(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 establecer el grupo en "w" después de coincidir con "wi". [ 42 ]

Los cuantificadores posesivos son más fáciles de implementar que los cuantificadores codiciosos y perezosos, y suelen ser más eficientes en tiempo de ejecución. [ 41 ]

IETF I-Regexp

El RFC 9485 de la IETF describe "I-Regexp: un formato de expresiones regulares interoperable". Especifica un subconjunto limitado de expresiones regulares diseñadas para ser interoperables, es decir, para producir el mismo efecto, en un gran número de bibliotecas de expresiones regulares. I-Regexp también se limita a la coincidencia, es decir, proporciona una coincidencia verdadera o falsa entre una expresión regular y un texto dado. Por lo tanto, carece de características avanzadas como grupos de captura, búsqueda anticipada y referencias inversas. [ 43 ]

Patrones para lenguajes no regulares

Muchas características presentes en prácticamente todas las bibliotecas modernas de expresiones regulares proporcionan un poder expresivo que supera al de los lenguajes regulares . Por ejemplo, muchas implementaciones permiten agrupar subexpresiones con paréntesis y recuperar el valor con el que coinciden en la misma expresión (backreferences ). Esto significa que, entre otras cosas, un patrón puede coincidir con cadenas de palabras repetidas como "papa" o "WikiWiki", llamadascuadradosen la teoría del lenguaje formal. El patrón para estas cadenas es(.+)\1.

El lenguaje de los cuadrados no es regular ni libre de contexto , debido al lema de bombeo . Sin embargo, la coincidencia de patrones con un número ilimitado de retroreferencias, como lo permiten numerosas herramientas modernas, sigue siendo sensible al contexto . [ 44 ] El problema general de hacer coincidir cualquier número de retroreferencias es NP-completo , y el tiempo de ejecución de los algoritmos conocidos crece exponencialmente con el número de grupos de retroreferencias utilizados. [ 45 ]

Sin embargo, muchas herramientas, bibliotecas y motores que proporcionan dichas construcciones siguen utilizando el término expresión regular para sus patrones. Esto ha dado lugar a una nomenclatura en la que el término expresión regular tiene diferentes significados en la teoría del lenguaje formal y en la coincidencia de patrones. Por esta razón, algunas personas han optado por utilizar los términos regex , regexp 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" […] solo guardan una relación marginal con las expresiones regulares reales. Sin embargo, el término ha evolucionado junto con las capacidades de nuestros motores de búsqueda de patrones, así que no voy a intentar luchar contra la necesidad lingüística en este caso. No obstante, generalmente las llamaré "regexes" (o "regexen", cuando esté en un estado de ánimo anglosajón). [ 19 ]

Afirmaciones

Otras características que no se encuentran al describir lenguajes regulares incluyen las aserciones. Estas incluyen las omnipresentes ^y $, utilizadas desde al menos 1970, [ 46 ] así como algunas extensiones más sofisticadas como lookaround que apareció en 1994. [ 47 ] Lookarounds define el entorno de una coincidencia y no se extiende a la coincidencia misma, una característica relevante solo para el caso de uso de búsqueda de cadenas. Algunas de ellas pueden simularse en un lenguaje regular tratando el entorno como parte del lenguaje también. [ 48 ]

ElLas aserciones de anticipación(?=...) y(?!...)han sido atestiguadas desde al menos 1994, comenzando con Perl 5. [ 47 ] Las aserciones de retroceso(?<=...)y(?<!...)están atestiguadas desde 1997 en una confirmación de Ilya Zakharevich a Perl 5.005. [ 49 ]

Implementaciones y tiempos de ejecución

Existen al menos tres algoritmos diferentes que deciden si una expresión regular coincide con una cadena de texto y cómo lo hace.

El método más antiguo y rápido se basa en un resultado de la teoría del lenguaje formal que permite transformar cualquier autómata finito no determinista (AFN) en un autómata finito determinista (AFD). El AFD se puede construir explícitamente y luego procesar la cadena de entrada resultante símbolo por símbolo. Construir el AFD para una expresión regular de tamaño m tiene un coste de tiempo y memoria de O (2m ) , pero se puede procesar una cadena de tamaño n en tiempo O ( n ). Cabe destacar que el tamaño de la expresión es el tamaño después de expandir las abreviaturas, como los cuantificadores numéricos.

Un enfoque alternativo es simular el NFA directamente, construyendo esencialmente cada estado del DFA bajo demanda y luego descartándolo en el siguiente paso. Esto mantiene el DFA implícito y evita el costo exponencial de construcción, pero el costo de ejecución aumenta a O ( mn ). El enfoque explícito se llama algoritmo DFA y el enfoque implícito algoritmo NFA. Agregar almacenamiento en caché al algoritmo NFA a menudo se llama algoritmo "DFA perezoso", o simplemente algoritmo DFA sin hacer distinción. Estos algoritmos son rápidos, pero usarlos para recuperar subexpresiones agrupadas, cuantificación perezosa y características similares es complicado. [ 50 ] [ 51 ] Las implementaciones modernas incluyen la familia re1- re2 -sregex basada en el código de Cox.

El tercer algoritmo consiste en comparar el patrón con la cadena de entrada mediante retroceso . Este algoritmo se conoce comúnmente como autómata finito no determinista (AFND), pero esta terminología puede resultar confusa. Su tiempo de ejecución puede ser exponencial, como demuestran las implementaciones sencillas al comparar con expresiones que contienen tanto alternancia como cuantificación ilimitada, lo que obliga al algoritmo a considerar un número exponencialmente creciente de subcasos. Este comportamiento puede provocar un problema de seguridad denominado denegación de servicio por expresiones regulares (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 retroreferencias, 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 recurriendo a un algoritmo de retroceso potencialmente más lento solo cuando se encuentra una retroreferencia durante la coincidencia. GNU grep (y el DFA subyacente gnulib) utiliza dicha estrategia. [ 52 ]

Se han logrado algoritmos de tiempo de ejecución sublineales utilizando algoritmos basados ​​en Boyer-Moore (BM) y técnicas de optimización DFA relacionadas, como el escaneo inverso. [ 53 ] GNU grep, que admite una amplia variedad de sintaxis y extensiones POSIX, utiliza BM para un prefiltrado de primera pasada y luego utiliza un DFA implícito. Wu agrep , que implementa la coincidencia aproximada, combina el prefiltrado en el DFA en BDM (coincidencia DAWG hacia atrás). BNDM de NR-grep extiende la técnica BDM con paralelismo a nivel de bits Shift-Or. [ 54 ]

Existen algunas alternativas teóricas al retroceso para las retroreferencias, y sus "exponentes" son más moderados, ya que solo están relacionados con el número de retroreferencias, una propiedad fija de algunos lenguajes de expresiones regulares como POSIX. Un método ingenuo que duplica un autómata finito no determinista (AFND) sin retroceso para cada nota de retroreferencia tiene una complejidad de ⁠O(norte2k+2){\displaystyle {\mathrm {O} }(n^{2k+2})}tiempo y​O(norte2k+1){\displaystyle {\mathrm {O} }(n^{2k+1})}espacio para un montón de referencias inversas de longitud n y k en la RegExp. [ 55 ] El trabajo teórico basado en autómatas de memoria proporciona una cota más ajustada basada en los nodos de variables "activas" utilizadas y una posibilidad polinómica para algunas regexps con referencias inversas. [ 56 ]

Unicode

En teoría, cualquier conjunto de tokens puede coincidir con expresiones regulares siempre que esté predefinido. Históricamente, las expresiones regulares se diseñaron 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 cierto soporte para Unicode . En la mayoría de los casos, el conjunto de caracteres no importa, pero surgen algunos problemas al extender las expresiones regulares para que admitan Unicode.

  • Codificación compatible . Algunas bibliotecas de expresiones regulares esperan trabajar con una codificación específica en lugar de con caracteres Unicode abstractos. Muchas de ellas requieren la codificación UTF-8 , mientras que otras pueden esperar UTF-16 o UTF-32 . Por el contrario, Perl y Java son independientes de la codificación y operan internamente con caracteres decodificados.
  • Rango Unicode compatible . Muchos motores de expresiones regulares solo admiten el Plano Multilingüe Básico , es decir, los caracteres que se pueden codificar con solo 16 bits. Actualmente (a partir de 2016)) solo unos pocos motores de expresiones regulares (por ejemplo, los de Perl y Java) pueden manejar el rango completo de Unicode de 21 bits.
  • Extender las construcciones orientadas a ASCII a Unicode . Por ejemplo, en las implementaciones basadas en ASCII, los rangos de caracteres de la forma [x-y]son válidos donde x e y tienen puntos de código en el rango [0x00,0x7F] y codepoint( x ) ≤ codepoint( y ). La extensión natural de dichos rangos de caracteres a Unicode simplemente cambiaría el requisito de que los puntos finales estén en [0x00,0x7F] al requisito de que estén en [0x0000,0x10FFFF]. Sin embargo, en la práctica esto a menudo no es así. Algunas implementaciones, como la de gawk , no permiten que los rangos de caracteres crucen bloques Unicode. Un rango como [0x61,0x7F] es válido ya que ambos extremos se encuentran dentro del bloque Latín Básico, al igual que [0x0530,0x0560] ya que ambos extremos se encuentran dentro del bloque Armenio, pero un rango como [0x0061,0x0532] no es válido ya que incluye varios 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. [ 57 ]
  • Insensibilidad a mayúsculas y minúsculas . Algunas banderas de insensibilidad a mayúsculas y minúsculas afectan solo a los caracteres ASCII. Otras banderas afectan a todos los caracteres. Algunos motores tienen dos banderas diferentes: una para ASCII y otra para Unicode. También varía qué caracteres pertenecen exactamente a las clases POSIX.
  • Primos de la insensibilidad a mayúsculas y minúsculas . Dado que ASCII distingue entre mayúsculas y minúsculas, la insensibilidad a mayúsculas y minúsculas se convirtió en una característica lógica en la búsqueda de texto. Unicode introdujo escrituras alfabéticas sin distinción de mayúsculas y minúsculas, como el devanagari . Para estas, la distinción entre mayúsculas y minúsculas no es aplicable. Para escrituras como la china, otra distinción parece lógica: entre tradicional y simplificada. En escrituras árabes, puede ser deseable la insensibilidad a la posición inicial, media, final y aislada . En japonés, la insensibilidad entre hiragana y katakana a veces resulta útil.
  • Normalización . Unicode tiene caracteres combinables . Al igual que las antiguas máquinas de escribir, los caracteres base simples (espacios en blanco, signos de puntuación, símbolos, dígitos o letras) pueden ir seguidos de uno o más símbolos que no sean espacios (generalmente diacríticos, como acentos que modifican letras) para formar un único carácter imprimible; pero Unicode también proporciona un conjunto limitado de caracteres precompuestos, es decir, caracteres que ya incluyen uno o más caracteres combinables. Una secuencia de un carácter base + caracteres combinables debe coincidir con el mismo carácter precompuesto (solo algunas de estas secuencias combinables pueden precomponerse en un único carácter Unicode, pero son posibles infinitas otras secuencias combinables en Unicode, y necesarias para varios idiomas, utilizando uno o más caracteres combinables después de un carácter base inicial; estas secuencias combinables pueden incluir un carácter base o caracteres combinables parcialmente precompuestos, pero no necesariamente en orden canónico y no necesariamente utilizando las precomposiciones canónicas). El proceso de estandarizar secuencias de un carácter base + caracteres combinatorios mediante la descomposición de estas secuencias canónicamente equivalentes , antes de reordenarlas en orden canónico (y opcionalmente recomponer algunos caracteres combinatorios en el carácter base principal) se denomina normalización.
  • Nuevos códigos de control . Unicode introdujo, entre otros códigos, marcas de orden de bytes y marcadores de dirección de texto. Es posible que estos códigos deban tratarse de forma especial.
  • Introducción de clases de caracteres para bloques Unicode, scripts y numerosas otras propiedades de caracteres . Las propiedades de bloque son mucho menos útiles que las propiedades de script, porque un bloque puede tener puntos de código de varios scripts diferentes, y un script puede tener puntos de código de varios bloques diferentes. [ 58 ] En Perl y la java.util.regexbiblioteca, las propiedades de la forma \p{InX}o \p{Block=X}coinciden con caracteres en el bloque X y \P{InX}o \P{Block=X}coinciden con puntos de código que no están en ese bloque. De manera similar, \p{Armenian}, \p{IsArmenian}, o \p{Script=Armenian}coincide con cualquier carácter en el alfabeto armenio. 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}.

Soporte de idiomas

La mayoría de los lenguajes de programación de propósito general admiten capacidades de expresiones regulares, ya sea de forma nativa o a través de bibliotecas .

Usos

Las expresiones regulares son útiles en una amplia variedad de tareas de procesamiento de texto y, en general, en el procesamiento de cadenas de caracteres , donde los datos no tienen por qué ser textuales. Entre las aplicaciones comunes se incluyen la validación de datos , la extracción de datos (especialmente de la web ), la manipulación de datos , el análisis sintáctico simple , la creación de sistemas de resaltado de sintaxis y muchas otras tareas.

Algunos programas de autoedición de alta gama permiten usar expresiones regulares para aplicar automáticamente estilos de texto, lo que evita que el diseñador tenga que hacerlo manualmente para todo aquello que pueda coincidir con una expresión regular. Por ejemplo, al definir un estilo de carácter que convierta el texto en versalitas y luego usar la expresión regular [A-Z]{4,}para aplicar ese estilo, cualquier palabra de cuatro o más letras mayúsculas consecutivas se mostrará automáticamente en versalitas.

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. 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. Entre las excepciones notables se encuentran Google Code Search y Exalead . Sin embargo, Google Code Search cerró en enero de 2012. [ 59 ]

Ejemplos

Las reglas de sintaxis específicas varían según la implementación, el lenguaje de programación o la biblioteca que se utilice. Además, la funcionalidad de las implementaciones de expresiones regulares puede variar entre versiones .

Dado que las expresiones regulares pueden ser difíciles de explicar y comprender sin ejemplos, los sitios web interactivos para probarlas son un recurso útil para aprenderlas mediante la experimentación. Esta sección ofrece 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. [ 60 ]

metacaracteres ;; la columna de metacaracteres especifica la sintaxis de expresiones regulares que se está demostrando. =~ 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

Estas expresiones regulares tienen una sintaxis similar a la de Perl. Las expresiones regulares POSIX estándar son diferentes.

Salvo que se indique lo contrario, los siguientes ejemplos se ajustan al lenguaje de programación Perl , versión 5.8.8, del 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 frente a extendidas, \( \)frente a (), o la falta de \den lugar de POSIX[:digit:] ).

La sintaxis y las convenciones utilizadas en estos ejemplos coinciden también con las de otros entornos de programación. [ 61 ]

Inducción

Las expresiones regulares a menudo se pueden crear ("inducir" o "aprender") a partir de un conjunto de cadenas de ejemplo. Esto se conoce como la inducción de lenguajes regulares y forma 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 pertenecen a 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 se pueden inducir de esta manera (véase identificación de lenguajes 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 usar para inducir la expresión regular 1⋅0* (1 seguido de cero o más 0).

Véase también

Notas

  1. ↑ Goyvaerts, Jan. "Tutorial de expresiones regulares: aprenda a usar expresiones regulares" . Regular-Expressions.info . Archivado del original el 1 de noviembre de 2016. Consultado el 31 de octubre de 2016 .
  2. ↑ Mitkov, Ruslan (2003). The Oxford Handbook of Computational Linguistics . Oxford University Press. p. 754. ISBN  978-0-19-927634-9Archivado del original el 28 de febrero de 2017. Consultado el 25 de julio de 2016 .
  3. ↑ Lawson, Mark V. (17 de septiembre de 2003). Autómatas finitos . CRC Press. págs. 98–100 . ISBN  978-1-58488-255-8Archivado del original el 27 de febrero de 2017. Consultado el 25 de julio de 2016 .
  4. ↑ "Cómo funciona internamente un motor de expresiones regulares" . regular-expressions.info . Consultado el 24 de febrero de 2024 .
  5. ↑ Heddings, Anthony (11 de marzo de 2020). "¿Cómo se usan realmente las expresiones regulares?" . howtogeek.com . Consultado el 24 de febrero de 2024 .
  6. ↑ Kleene 1951 .
  7. ↑ Leung, Hing (16 de septiembre de 2010). "Lenguajes regulares y autómatas finitos" (PDF) . Universidad Estatal de Nuevo México . Archivado del original (PDF) el 5 de diciembre de 2013. Recuperado el 13 de agosto de 2019. El concepto de eventos regulares fue introducido por Kleene a través de la definición de expresiones regulares.
  8. ↑ Kleene 1951, pág. 46
  9. 1 2 Thompson 1968 .
  10. 1 2 Johnson et al. 1968 .
  11. ↑ Kernighan, Brian (8 de agosto de 2007). "Un comparador de expresiones regulares" . Beautiful Code . O'Reilly Media . págs. 1-2 . ISBN  978-0-596-51004-6Archivado del original el 7 de octubre de 2020. Consultado el 15 de mayo de 2013 .
  12. ↑ Ritchie, Dennis M. "Una historia incompleta del editor de texto QED" . Archivado del original el 21 de febrero de 1999. Consultado el 9 de octubre de 2013 .
  13. 1 2 Aho y Ullman 1992 , 10.11 Notas bibliográficas para el capítulo 10, pág. 589.
  14. ↑ Aycock 2003 , pág. 98.
  15. ↑ Raymond, Eric S. citando a Dennis Ritchie (2003). "Archivo de jerga 4.4.7: grep" . Archivado del original el 5 de junio de 2011. Recuperado el 17 de febrero de 2009 .
  16. ↑ "Nuevas características de expresiones regulares en Tcl 8.1" . Archivado del original el 7 de octubre de 2020. Consultado el 11 de octubre de 2013 .
  17. ↑ "Documentación: 9.3: Coincidencia de patrones" . PostgreSQL . Archivado del original el 7 de octubre de 2020. Consultado el 12 de octubre de 2013 .
  18. ↑ Wall, Larry (2006). "Expresiones regulares de Perl" . perlre . Archivado del original el 31-12-2009 . Recuperado el 10-10-2006 .
  19. 1 2 Muro (2002)
  20. ↑ "PCRE - Expresiones regulares compatibles con Perl" . www.pcre.org . Consultado el 7 de abril de 2024 .
  21. ↑ "GRegex – Análisis más rápido para datos de texto no estructurados" . grovf.com . Archivado del original el 7 de octubre de 2020. Consultado el 20 de abril de 2026 .
  22. ↑ "CUDA grep" . bkase.github.io . Archivado del original el 7 de octubre de 2020. Consultado el 22 de octubre de 2019 .
  23. 1 2 3 4 Kerrisk, Michael. "grep(1) - Página del manual de Linux" . man7.org . Consultado el 31 de enero de 2023 .
  24. ^ Hopcroft , Motwani y Ullman (2000)
  25. ↑ Sipser (1998)
  26. ↑ Gelade & Neven (2008 , p. 332, Thm.4.1) 
  27. ↑ Gruber y Holzer (2008)
  28. ↑ Basado en Gelade y Neven (2008) , una expresión regular de longitud de aproximadamente 850 tal que su complemento tiene una longitud de aproximadamente 2 32 se puede encontrar en File:RegexComplementBlowup.png .
  29. ↑ "Expresiones regulares para decidir la divisibilidad" . s3.boskent.com . Consultado el 21 de febrero de 2024 .
  30. ↑ Gischer, Jay L. (1984). (Título desconocido) (Informe técnico). Universidad de Stanford, Departamento de Ciencias de la Computación.
  31. ↑ Hopcroft, John E.; Motwani, Rajeev y Ullman, Jeffrey D. (2003). Introducción a la teoría de autómatas, lenguajes y computación . Upper Saddle River, Nueva Jersey: Addison Wesley. págs. 117–120 . ISBN  978-0-201-44124-6Esta propiedad no tiene por qué cumplirse para expresiones regulares extendidas, incluso si no describen una clase mayor que la de los lenguajes regulares; cf. pág. 121 .
  32. ↑ Kozen (1991)
  33. ↑ Redko, VN (1964). "Sobre la definición de relaciones para el álgebra de eventos regulares" . Ukrainskii Matematicheskii Zhurnal (en ruso). 16 (1): 120– 126. Archivado del original el 29 de marzo de 2018. Consultado el 28 de marzo de 2018 .
  34. ↑ ISO/IEC 9945-2:1993 Tecnología de la información – Interfaz de sistema operativo portátil (POSIX) – Parte 2: Shell y utilidades , revisada sucesivamente como ISO/IEC 9945-2:2002 Tecnología de la información – Interfaz de sistema operativo portátil (POSIX) – Parte 2: Interfaces del sistema , ISO/IEC 9945-2:2003, y actualmente ISO/IEC/IEEE 9945:2009 Tecnología de la información – Especificaciones básicas de la interfaz de sistema operativo portátil (POSIX), Edición 7
  35. ↑ La Especificación Única de Unix (Versión 2)
  36. ↑ "9.3.6 BRE que coinciden con múltiples caracteres" . The Open Group Base Specifications Issue 7, edición de 2018. The Open Group. 2017. Recuperado el 10 de diciembre de 2023 .
  37. ↑ Russ Cox (2009). "Coincidencia de expresiones regulares: el enfoque de la máquina virtual" . swtch.com . Digresión: Subcoincidencia POSIX
  38. ↑ "Documentación de expresiones regulares de Perl" . perldoc.perl.org. Archivado del original el 31 de diciembre de 2009. Consultado el 5 de noviembre de 2024 .
  39. 1 2 "Sintaxis de expresiones regulares" . Documentación de Python 3.5.0 . Python Software Foundation . Archivado del original el 18 de julio de 2018. Recuperado el 10 de octubre de 2015 .
  40. ↑ SRE: El agrupamiento atómico (?>...) no es compatible #34627
  41. 1 2 "Clases esenciales: Expresiones regulares: Cuantificadores: Diferencias entre cuantificadores voraces, reticentes y posesivos" . Los tutoriales de Java . Oracle . Archivado del original el 7 de octubre de 2020. Recuperado el 23 de diciembre de 2016 .
  42. ↑ "Agrupación atómica" . Tutorial de expresiones regulares . Archivado del original el 7 de octubre de 2020. Consultado el 24 de noviembre de 2019 .
  43. ↑ Bormann, Carsten; Bray, Tim. I-Regexp: Un formato de expresión regular interoperable . Grupo de trabajo de ingeniería de Internet. doi : 10.17487/RFC9485 . RFC 9485. Consultado el 11 de marzo de 2024 .
  44. ↑ Cezar Câmpeanu; Kai Salomaa y Sheng Yu (dic. 2003). "Un estudio formal de expresiones regulares prácticas" . Revista Internacional de Fundamentos de Ciencias de la Computación . 14 (6): 1007– 1018. doi : 10.1142/S012905410300214X . Archivado del original el 4 de julio de 2015. Recuperado el 3 de julio de 2015 .Teorema 3 (pág. 9)
  45. ↑ "La coincidencia de expresiones regulares en Perl es NP-difícil" . perl.plover.com . Archivado del original el 7 de octubre de 2020. Consultado el 21 de noviembre de 2019 .
  46. ↑ Ritchie, DM; Thompson, KL (junio de 1970). Editor de texto QED (PDF) . MM-70-1373-3. Archivado del original (PDF) el 3 de febrero de 2015. Consultado el 5 de septiembre de 2022 .Reimpreso como "Manual de referencia del editor de texto QED", MHCC-004, Murray Hill Computing, Bell Laboratories (octubre de 1972).
  47. 1 2 Wall, Larry (1994-10-18). "Perl 5: perlre.pod" . GitHub .
  48. ↑ Wandering Logic. "¿Cómo simular anticipaciones y retrospectivas en autómatas de estados finitos?" . Computer Science Stack Exchange . Archivado del original el 7 de octubre de 2020 . Recuperado el 24 de noviembre de 2019 .
  49. ↑ Zakharevich, Ilya (1997-11-19). "Parche Jumbo Regexp aplicado (con ajustes menores de corrección): Perl/perl5@c277df4" . GitHub .
  50. ↑ Cox (2007)
  51. ↑ Laurikari (2009)
  52. ↑ "gnulib/lib/dfa.c" . Archivado del original el 18 de agosto de 2021. Recuperado el 12 de febrero de 2022. 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.
  53. ↑ Kearns, Steven (agosto de 2013). "Coincidencia sublineal con autómatas finitos mediante escaneo de sufijos inversos". arXiv : 1308.3822 [ cs.DS ].
  54. ↑ Navarro, Gonzalo (10 de noviembre de 2001). "NR-grep: una herramienta de coincidencia de patrones rápida y flexible" ( PDF) . Software: Practice and Experience . 31 (13): 1265– 1312. doi : 10.1002/spe.411 . S2CID 3175806. Archivado (PDF) del original el 7 de octubre de 2020. Recuperado el 21 de noviembre de 2019 . 
  55. ↑ "travisdowns/polyregex" . GitHub . 5 de julio de 2019. Archivado del original el 14 de septiembre de 2020. Consultado el 21 de noviembre de 2019 .
  56. ↑ Schmid, Markus L. (marzo de 2019). "Expresiones regulares con retroreferencias: técnicas de coincidencia en tiempo polinomial". arXiv : 1903.05896 [ cs.FL ].
  57. ↑ "Documentación de Vim: patrón" . Vimdoc.sourceforge.net. Archivado del original el 7 de octubre de 2020. Consultado el 25 de septiembre de 2013 .
  58. 1 2 "UTS#18 sobre expresiones regulares Unicode, Anexo A: bloques de caracteres" . Archivado del original el 7 de octubre de 2020. Consultado el 5 de febrero de 2010 .
  59. ↑ Horowitz, Bradley (24 de octubre de 2011). "Una barrida de otoño" . Blog de Google . Archivado del original el 21 de octubre de 2018. Recuperado el 4 de mayo de 2019 .
  60. ↑ El carácter 'm' no siempre es necesario para especificar unaoperación de coincidencia en Perlm/[^abc]/ . Por ejemplo, también podría representarse como/[^abc]/. La 'm' solo es necesaria si el usuario desea especificar una operación de coincidencia sin usar una barra inclinada como delimitador de expresiones regulares . A veces es útil especificar un delimitador de expresiones regulares alternativo para evitar " colisión de delimitadores ". Consulte ' perldoc perlre Archivado el 31/12/2009 en Wayback Machine ' para obtener más detalles.
  61. ↑ Por ejemplo, véase Java in a Nutshell , pág. 213; Python Scripting for Computational Science , pág. 320; Programming PHP , pág. 106.
  62. ↑ Todas las sentencias if devuelven un valor VERDADERO.
  63. ↑ Conway, Damian (2005). "Expresiones regulares, fin de cadena" . Mejores prácticas de Perl . O'Reilly . pág. 240. ISBN  978-0-596-00173-5Archivado del original el 07/10/2020 . Consultado el 10/09/2017 .

Referencias

  • Aho, Alfred V. (1990). "Algoritmos para encontrar patrones en cadenas". En van Leeuwen, Jan (ed.). Manual de Informática Teórica, volumen A: Algoritmos y Complejidad . The MIT Press. pp. 255–300 . 
  • Aho, Alfred V.; Ullman, Jeffrey D. (1992). "Capítulo 10. Patrones, autómatas y expresiones regulares" (PDF) . Fundamentos de la informática . Archivado del original el 7 de octubre de 2020. Consultado el 14 de diciembre de 2013 .
  • Aycock, John (junio de 2003). "Una breve historia del sistema justo a tiempo" (PDF) . ACM Computing Surveys . 35 (2): 97–113 . CiteSeerX 10.1.1.97.3985 . doi : 10.1145/857076.857077 . S2CID 15345671 .  
  • "Expresiones regulares". Especificación única de UNIX, versión 2. The Open Group. 1997. Archivado del original el 7 de octubre de 2020. Consultado el 13 de diciembre de 2011 .
  • Capítulo 9: Expresiones regulares . Especificaciones básicas de The Open Group (6). The Open Group. 2004. IEEE Std 1003.1, edición de 2004. Archivado del original el 2 de diciembre de 2011. Consultado el 13 de diciembre de 2011 .
  • Cox, Russ (2007). "La coincidencia de expresiones regulares puede ser simple y rápida" . Archivado del original el 1 de enero de 2010. Recuperado el 27 de abril de 2008 .
  • Forta, Ben (2004). Sams: Aprende expresiones regulares en 10 minutos . Sams. ISBN 978-0-672-32566-3.
  • Friedl, Jeffrey EF (2002). Dominando las expresiones regulares . O'Reilly . ISBN 978-0-596-00289-3Archivado del original el 30 de agosto de 2005. Consultado el 26 de abril de 2005 .
  • Gelade, Wouter; Neven, Frank (2008). Succinctness of the Complement and Intersection of Regular Expressions . Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008) . pp. 325–336 . arXiv : 0802.2869 . Archivado del original el 18 de julio de 2011. Recuperado el 15 de junio de 2009 . 
  • Goyvaerts, Jan; Levithan, Steven (2009). Regular Expressions Cookbook . [O'reilly]. ISBN 978-0-596-52068-7.
  • Gruber, Hermann; Holzer, Markus (2008). Autómatas finitos, conectividad de digrafos y tamaño de expresiones regulares (PDF) . Actas del 35.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 2008) . Lecture Notes in Computer Science. Vol.  5126. pp. 39–50 . doi : 10.1007/978-3-540-70583-3_4 . ISBN  978-3-540-70582-6. Archivado (PDF) del original el 11-07-2011 . Recuperado el 03-02-2011 .
  • Habibi, Mehran (2004). Expresiones regulares del mundo real con Java 1.4 . Springer. ISBN 978-1-59059-107-9.
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2000). Introducción a la teoría de autómatas, lenguajes y computación (2.ª  ed.). Addison-Wesley.
  • Johnson, Walter L.; Porter, James H.; Ackley, Stephanie I.; Ross, Douglas T. (1968). "Generación automática de procesadores léxicos eficientes mediante técnicas de estados finitos" . Communications of the ACM . 11 (12): 805– 813. doi : 10.1145/364175.364185 . S2CID 17253809 . 
  • Kleene, Stephen C. (1951). «Representación de eventos en redes nerviosas y autómatas finitos». En Shannon, Claude E.; McCarthy, John (eds.). Automata Studies (PDF) . Princeton University Press. pp. 3–42 . Archivado (PDF) del original el 7 de octubre de 2020. Recuperado el 10 de diciembre de 2017 . 
  • Kozen, Dexter (1991). «Un teorema de completitud para álgebras de Kleene y el álgebra de eventos regulares». [ 1991 ] Actas del Sexto Simposio Anual del IEEE sobre Lógica en Ciencias de la Computación . págs. 214–225 . doi : 10.1109/LICS.1991.151646 . hdl : 1813/6963 . ISBN  978-0-8186-2230-4. S2CID 19875225 . 
  • Laurikari, Ville (2009). "Biblioteca TRE 0.7.6" . Archivado del original el 14 de julio de 2010. Recuperado el 1 de abril de 2009 .
  • Liger, François; McQueen, Craig; Wilton, Paul (2002). Visual Basic .NET Text Manipulation Handbook . Wrox Press . ISBN 978-1-86100-730-8.
  • Sipser, Michael (1998). «Capítulo 1: Lenguajes regulares» . Introducción a la teoría de la computación . PWS Publishing. págs. 31-90 . ISBN  978-0-534-94728-6.
  • Stubblebine, Tony (2003). Regular Expression Pocket Reference . O'Reilly. ISBN 978-0-596-00415-6.
  • Thompson, Ken (1968). "Técnicas de programación: algoritmo de búsqueda de expresiones regulares" . Communications of the ACM . 11 (6): 419– 422. doi : 10.1145/363347.363387 . S2CID 21260384 . 
  • Wall, Larry (2002). "Apocalipsis 5: Coincidencia de patrones" . Archivado del original el 12 de enero de 2010. Recuperado el 11 de octubre de 2006 .
  • Logotipo de Wikimedia CommonsContenido multimedia relacionado con expresiones regulares en Wikimedia Commons.
  • ISO/IEC/IEEE 9945:2009 Tecnología de la información – Especificaciones básicas de la interfaz de sistema operativo portátil (POSIX), Edición 7
  • Expresiones regulares, IEEE Std 1003.1-2024, Open Group
  • Lista de recursos de expresiones regulares de código abierto