Spresson Regular
An ciéncia de la cumputaçon, ua spresson regular (ó l strangeirismo regex, abrebiaçon de l anglés regular spression) probé ua forma cuncisa i flexible d'eidantificar cadeias de carateres d'antresse, cumo carateres particulares, palabras ó padrones de carateres. Spressones regulares son scritas nua lenguaige formal que puode ser anterpretada por un processador de spresson regular, un porgrama que ó sirbe un gerador d'analisador sintático ó eisamina l testo i eidantifica partes que casan cula specificaçon dada.

L termo deriba de l trabalho de l matemático norte-amaricano Stephen Cole Klene, que zambolbiu las spressones regulares cumo ua notaçon al qu'el chamaba de álgebra de cunjuntos regulares. Sou trabalho serbiu de base pa ls purmeiros algoritmos cumputacionales de busca, i depuis para alguas de las mais antigas ferramientas de tratamiento de testo de la plataforma Unix.

L'uso atual de spressones regulares anclui percura i sustituiçon de testo an eiditores de testo i lenguaiges de porgramaçon, balidaçon de formatos de testo (balidaçon de protocolos ó formatos digitales), rialce de sintaxe i filtraige d'anformaçon.

Cunceitos básicos 
Ua spresson regular (ó, un padron) çcribe un cunjunto de cadeias de carateres, de forma cuncisa, sin percisar listar todos ls eilemientos de l cunjunto. Por eisemplo, un cunjunto cuntendo las cadeias "Handel", "Händel" i "Haendel" puode ser çcrito pul padron H(ä|ae?)ndel. La maiorie de ls formalismos probé pul menos trés ouparaçones para custruir spressones regulares.

La purmeira deilhas ye l'altarnáncia, an qu'ua barra bertical (|) separa altarnatibas. Por eisemplo, psicadélico|psicodélico puode casar "psicadélico" ó "psicodélico". La segunda ouparaçon ye l'agrupamiento, an que parénteses ((, )) son ousados para defenir l scopo i la precedéncia d'ouperadores, antre outros usos. Por eisemplo, psicadélico|psicodélico i psic(la|l)délico son eiquibalentes i ambas çcriben "psicadélico" i "psicodélico". Por fin, la terceira ouparaçon ye la quantificaçon (ó repetiçon). Un quantificador passado un token (cumo un caratere) ó un agrupamiento specifica la cantidade de bezes que l'eilemiento precedente puode ocorrer. Ls quantificadores mais quemuns son ?, * i +. L punto d'anterrogaçon andica qu'hai zero ó ua ocorréncia de l'eilemiento precedente. Por eisemplo, ac?çon casa tanto "açon" quanto "açon". Yá l asterisco andica qu'hai zero ó mais ocorréncias de l'eilemiento precedente. Por eisemplo, ab*c casa "ac", "abc", "abbc", "abbbc", i assi por delantre. Por fin, l senhal d'adiçon andica qu'hai ua ó mais ocorréncias de l'eilemiento precedente. Por eisemplo, ab+c casa "abc", "abbc", "abbbc", i assi por delantre, mas nun "ac".

Essas custruçones puoden ser cumbinadas arbitrariamente para formar spressones cumplexas, assi cumo spressones aritméticas cun númaros i ouparaçones d'adiçon, subtraçon, multiplicaçon i debison. De forma giral, hai dibersas spressones regulares para çcrebir un mesmo cunjunto de cadeias de carateres. La sintaxe sata de la spresson regular i ls ouperadores çponibles barian antre las amplementaçones.

Stória 
L'ourige de las spressones regulares stan na teorie de ls outómatos i na teorie de las lenguaiges formales, i ambas fázen parte de la teorie de la cumputaçon. Esses campos studan modelos de cumputaçon (outómatas) i formas de çcriçon i classeficaçon de lenguaiges formales. Na década de 1950, l matemático Stephen Cole Klene çcrebiu tales modelos usando sue notaçon matemática chamada de "cunjuntos regulares", formando la álgebra de Klene. La lenguaige SNOBOL fui ua amplementaçon pioneira de casamiento de padrones, mas nun era idéntica a las spressones regulares. Ken Thompson custruiu la notaçon de Klene ne l eiditor de testo QED cumo ua forma de casamiento de padrones an arquibos de testo. Mais tarde, el adicionou essa funcionalidade ne l'eiditor de testo Unix ed, que resultou ne l'uso de spressones regulares na popular ferramienta de busca grep. Zde anton, dibersas bariaçones de l'adataçon ouriginal de Thompson fúrun ousadas an Unix i deribados, ancluindo spr, AWK, Emacs, bi i lex.

Las spressones regulares de Perl i Tcl fúrun deribadas de la biblioteca scrita por Heinry Spencer, i ne l Perl la funcionalidade fui spandida mais tarde. Phelip Hazel zambolbiu la PCRE (Perl Cumpatible Regular Spressiones), ua biblioteca ousada por dibersas ferramientas modernas cumo PHP i l serbidor Apache. Parte de l zambolbimiento de l Perl 6 fui melhorar l'antegraçon de las spressones regulares de Perl, i oumentar sou scopo i funcionalidade para permitir la defeniçon de gramáticas de spresson d'analisadores sintáticos. L resultado fui ua meni-lenguaige, las regras de l Perl 6, ousada para defenir la gramática de l Perl 6 assi cumo fornecer ua ferramienta para porgramadores de la lenguaige. Tales regras mantibírun las funcionalidades de spressones regulares de l Perl 5.x, mas tamien permitiran ua defeniçon BNF dun analisador sintático çcendente recursibo.

L'uso de spressones regulares an normas d'anformaçon struturada pa la modelaige de decumientos i bancos de dados ampeçou na década de 1960, i spandiu na década de 1980 quando normas cumo la ISO SGML fúrun cunsulidadas.

Teorie de lenguaiges formales 
Spressones regulares puoden ser spressas atrabeç de la teorie de lenguaiges formales. Eilhas cunsisten de custantes i ouperadores que denotan cunjuntos de cadeias de carateres i ouparaçones subre esses cunjuntos, respetibamente. Dado un alfabeto fenito Σ, las seguintes custantes son defenidas:
 (cunjunto bazio)  denotando l cunjunto 
 (cadeia de carateres bazie) ε denotando l cunjunto {ε}
 (literal) la an Σ denotando l cunjunto {la}

Las seguintes ouparaçones son defenidas:
 (cuncatenaçon) RS denotando l cunjunto { αβ | α an R i β an S }. Por eisemplo, {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}.
 (altarnáncia) R|S denotando l cunjunto ounion de R i S. Usa-se ls simblos ,  ó  para altarnáncia al ambés de la barra bertical. Por eisemplo, {"ab", "c"}{"db", "ef"} = {"ab", "c", "db", "ef"}
 (Fecho de Klene) R* denotando l menor superconjunto de R que cuntén ε i ye cerrado sob cuncatenaçon. Esse ye l cunjunto de todas las cadeias de carateres que puoden ser custruídas al cuncatenar zero ó mais cadeias an R. Por eisemplo, {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "c", "ababab", "abcab", ... }.

Las custantes i ls ouperadores arriba forman la álgebra de Klene.

Para eibitar parénteses, ye assumido que l fecho de Klene ten la maior prioridade, depuis la cuncatenaçon i por fin l'altarnáncia. Se nun houbir ambiguidades, ls parénteses puoden ser omitidos. Por eisemplo, (ab)c puode ser scrito cumo abc, i la|(b(c*)) puode ser scrito cumo la|bc*.

Eisemplos
 la|b* denota {ε, la, b, bb, bbb, ...}
 (la|b)* denota l cunjunto de todas las cadeias de carateres que cuntén ls símbols la i b, ancluindo la cadeia bazie: {ε, la, b, aa, ab, ba, bb, aaa, ...}
 ab*(c|ε) denota l cunjunto de cadeias de carateres ampeçando cun la, anton cun zero ó mais bs i oupcionalmente cun un c: {la, ac, ab, abc, abb, ...}

La defeniçon formal de spressones regulares ye cuncisa i eibita l'outelizaçon de ls quantificadores redundantes ? i +, que puoden ser spressados respetibamente por (la|ε) i aa*. Por bezes l'ouperador de cumplemiento ~ ye adicionado;  ~R denota l cunjunto de las cadeias de carateres de Σ* que nun stan an R. Esse ouperador ye redundante, i puode ser spressado usando outros ouperadores, anque de la cumputaçon para tal repersentaçon ser cumplexa.

Spressones regulares puoden spressar lenguaiges regulares, la classe de lenguaiges aceita por un outómato fenito. Antretanto, hai ua defrença seneficatiba na cumpataçon. Alguas classes de lenguaiges regulares puoden ser çcritas solamente por outómatos que crecen sponencialmente an tamanho, anquanto l tamanho de las spressones regulares requeridas solo puode crecer linearmente. Spressones regulares corresponden al Tipo-3 de las gramáticas de la Hierarquia de Chomsky. Por outro lado, eisiste un mapeamiento simples de spressones regulares para máquinas de stado fenito nó-determinísticas que nun lieba al crecimiento çgobernado de l tamanho. Por essa rezon, essas máquinas nun determinísticas son giralmente ousadas cumo repersentaçon altarnatiba de las spressones regulares.

Ye possible screbir un algoritmo que, para dues spressones regulares dadas, decide se las lenguaiges çcritas son eissencialmente eiguales. Reduç-se cada spresson na máquina de stado fenito mínima, i detremina-se se ambas las máquinas mínimas son eisomórficas (eiquibalentes).

Bal notar que dibersas amplementaçones de spressones regulares amplementan funcionalidades que nun puoden ser spressadas na álgebra de Klene; ber ambaixo mais subre l'assunto.

Sintaxe

POSIX 
De 1986, la norma IEEE POSIX 1003.2 (POSIX.2) padroniza spressones regulares, i fornece dues specificaçones, a saber: l cunjunto básico (BRE) i l cunjunto stendido (ERE).

BRE: spressones regulares básicas 
La sintaxe tradecional de spressones regulares an Unix seguiu cumbençones quemuns, mas diferiu antre las amplementaçones. La norma IEEE POSIX BRE (Basic Regular Spressiones, de l anglés, spressones regulares básicas) fui zambolbida primordialmente por cumpatibelidade cula sintaxe tradecional, mas fornecie ua norma quemun que zde anton fui adotada por dibersas ferramientas.

Na sintaxe de BRE, la maiorie de ls carateres son tratados cumo literales — eilhes casan solamente culs própios (por eisemplo, la casa "la"). Las sceçones son chamadas metacarateres ó metasequéncias, defenidos ambaixo:

Ua caratelística de la BRE ye que ls metacarateres giralmente eisigen barras ambertidas para séren tratador cumo tal. Por eisemplo, an BRE, la{1,2} ye cumpuosto solamente por literales, i casará solamente "la{1,2}". Para casar antre ua la dues ocorréncias de "la", debe-se ousar la spresson regular la\{1,2\}. La motibaçon desse sistema ye la cumpatelidade cun sistemas antigos, yá que na época de la padronizaçon yá habie código Unix legado qu'usaba chabes cumo literales.

ERE: spressones regulares stendidas 
L seneficado de ls metacarateres séren escapados cula barra ambertida ye rebertido na sintaxe POSIX ERE (Stended Regular Spression, de l anglés, spressones regulares stendidas). Esso senefica que nun son ousadas barras ambertidas para eidantificar metacarateres. Pul cuntrairo, eilhas serben justamente para trasformar metacarateres an literales. Retomando l'eisemplo de la seçon anterior, an ERE, la{1,2} casa ua la dues ocorréncias de "la", anquanto la\{1,2\} casa l literal "la{1,2}".

Ls seguintes metacarateres fúrun adicionados:

Ferramientas qu'adotórun la sintaxe ancluen MySQL i PHP, esta, que suporta tamien las deribaçones de Perl ne l modelo de l PCRE.

Classes de carateres 
Yá que dibersos grupos de carateres dependen dua cunfiguraçon de locale specífica, la POSIX define alguas classes (ó catadories) de carateres para fornecer un método padron d'acesso l'alguns grupos specíficos de carateres bastante outelizados, cumo mostrado na seguinte tabela:

Notar que las duoze classes defenidas arriba tamien stan defenidas na biblioteca padron de l C, na seçon de funçones de testes de carateres de l cabeçalho type.h.

Tales classes solo puoden ser ousadas drento de spressones de listas de carateres. Defrentes locales puoden fornecer classes adicionales. Ua stenson nun POSIX difundida ye [:word:] (atalho de l Perl \w), giralmente defenida cumo [:alnun:] ó traço baixo (_) i [:ascii:], cuntendo solamente carateres ASCII ([\x01-\x7F]).

Puode-se negar ua classe de carateres precedendo un aciento circunflexo al nome de la classe. Por eisemplo, para negar [:digit:] usa-se [:^digit:].

Lemites de palabras 
La norma POSIX define inda dous metacarateres speciales que serben para casar ls lemites de palabras nas cadeias de carateres. Nesse cuntesto de la POSIX, ua palabra ye formada por carateres [:alnun:] ó traço baixo (_). Assi cumo las áncoras,  esses metacarateres nun casan pedaços de l testo, eilhas serben solo cumo ua refréncia. Eilhes son:

Perl i deribaçones 
Perl ten ua sintaxe mais cunsistente i rica que las normas POSIX BRE i ERE. Un eisemplo ye que \ siempre scapa un caratere nun alfanumérico. Debido al poder de spresson, outras ferramientas adotórun la sintaxe de l Perl, cumo por eisemplo Jaba, JabaScrit, PCRE, Python, Ruby i .NET. Alguas lenguaiges i ferramientas cumo PHP suportan dibersos tipos de spressones regulares.

Un eisemplo de funcionalidade possible an Perl mas nun an POSIX ye la quantificaçon preguiçosa. Ls quantificadores padrones de las spressones regulares son "gananciosos", esto ye, casan l quanto podíren, buoltando atrás solamente se necessairo para casar l resto de la spresson regular. Por eisemplo, un nobato ne l'assunto tentando ancontrar la purmeira anstáncia dun iten antre ls simblos < i > ne l testo "Outra spluson acunteciu an <26 de janeiro> de <2004>" probabelmente ousarie l padron <.*>, ó similar. Antretanto, esse padron retornará "<26 de janeiro> de <2004>" al ambés de "<26 de janeiro>", cumo sperado, pus l quantificador * ye ganancioso — el cunsumirá la cantidade mássima de carateres, i "26 de janeiro> de <2004" ten mais carateres que "26 de janeiro".

Anque desse porblema ser eibitable de defrentes formas (por eisemplo, specificando l que nun casar: <[^>]*>), la maiorie de las ferramientas permiten qu'un quantificador seia preguiçoso, ó nun ganancioso, al suceder l quantificador cun un punto d'anterrogaçon. Ne l'eisemplo anterior, l'altarnatiba serie <.*?>. Seguen ls quantificadores nó-gulosos:

L PERL define alguas sequéncias de scape que serben cumo atalhos para ciertos metacarateres:

Para alhá de ls quantificadores preguiçosos i de las nuobas sequéncias de scape, l Perl tamien adicionou ua forma nuoba de casamiento de padrones que stenden la POSIX. San un cunjunto de metacarateres que seguen l padron (?…), listados ambaixo:

Padrones para lenguaiges nun regulares 
Dibersas funcionalidades ancontradas an bibliotecas atuales de spressones regulares proben un poder de spresson que scede las lenguaiges regulares. Por eisemplo, l'halbelidade d'agrupar subexpressones cun parénteses i chamar outra beç l balor casado na mesma spresson senefica que l padron puode casar cadeias de palabras repetidas cumo "papa" ó "WikiWiki", ls chamados quadrados na teorie de lenguaiges formales. L padron para essas cadeias ye (.*)\1. Antretanto, la lenguaige de quadrados nun ye regular, nin libre de cuntesto. Casamiento de padrones cun un númaro andeterminado de refréncias anteriores, cumo suportado an ferramientas atuales, ye NP-defícel.

Antretanto, las ferramientas que fornecen tales custruçones inda úsan l termo spressones regulares pa ls padrones, l que lieba a ua nomenclatura que difire de la teorie de las lenguaiges formales. Por essa rezon, alguas pessonas úsan l termo regex ó simplesmente padron para çcrebir esse cunceito mais abrangente.

Amplementaçones 
Eesisten pul menos dous algoritmos fundamentalmente defrentes antre si que deciden se i cumo ua spresson regular casa ua cadeia de carateres.

L mais antigo i mais rápido faç uso dun percípio de la teorie de lenguaiges formales que permite a todas las máquinas de stado fenito nun determinísticas séren trasformadas an máquinas de stado fenito determinísticas. Giralmente chamado de DFA, l'algoritmo rializa ó simula tal trasformaçon i anton eisecuta la máquina determinística resultante na cadeia de carateres, un simblo de cada beç. Esse radadeiro porcesso ten cumplexidade linear relatiba al tamanho de la cadeia de carateres. Mais percisamente, ua cadeia de carateres de tamanho m puode ser testada nua spresson regular de tamanho m ne l tiempo L() ó L(), dependendo de ls detalhes d'amplementaçon. Esse algoritmo ye rápido, mas puode ser ousado solamente para casamientos i nun pa la rechamada de grupos de catura, quantificaçon preguiçosa i dibersas outras funcionalidades ancontradas nas bibliotecas modernas de spressones regulares. Tamien ye possible eisecutar la máquina nun determinística diretamente, custruindo cada stado de la máquina determinística quando necessairo i anton çcartando-lo ne l próssimo passo. Esso eibita la cantidade sponencial de mimória neçaira pa la custruçon cumpleta de la máquina determinística, inda que garantindo la busca an tiempo linear.

L'outro algoritmo ye casar l padron cula cadeia de carateres atrabeç de backtracking. Giralmente chamado de NFA, Sou tiempo d'eisecuçon puode ser sponencial, l que puode acuntecer an amplementaçones simples ne l casamiento de spressones cumo (la|aa)*b, que fuorçan l'algoritmo a cunsidrar un númaro sponencial de subcasos. Amplementaçones modernas giralmente eidantifican tales causos, i acelírun i amóbitan l'eisecuçon. Anque dessas amplementaçones cun backtracking garantiren tiempo sponencial ne l pior causo, eilhas fornecen mais flexibelidade i poder de spresson.

Relacionamiento cun Unicode 
Ouriginalmente, las spressones regulares éran ousadas cun carateres ASCII, mas bárias amplementaçones atuales suportan Unicode. Na maiorie de ls causos nun hai defrença antre cunjuntos de carateres, mas alguas questones son relebantes al suportar Unicode.

Ua deilhas ye la codificaçon suportada, yá qu'alguas amplementaçones spírun UTF-8, anquanto outras puoden asperar UTF-16 ó UTF-32. Outra queston ye stender las funcionalidades çponibles para ASCII ne l Unicode. Por eisemplo, an amplementaçones ASCII, cunjuntos de carateres na forma [x-y] son bálidos para qualesquiera x i y ne l'anterbalo [0x00,0x7F] zde que l código de x seia menor que l código de y. La scolha natural serie permitir l mesmo an Unicode ne l'anterbalo de códigos [0,0x10FFFF], l que nun ye possible pus alguas amplementaçones nó permiten que cunjuntos de carateres ultrapassen ls blocos de código çponibles.

De l punto de bista de ls detalhes técnicos de l Unicode, tamien surge questones. Cumo la normalizaçon, pus, an Unicode, mais dun código puode repersentar l mesmo caratere. Por eisemplo, l caratere "ye" puode ser repersentado por U+0065 (letra latina "i" minúsclo) cumbinado cun U+0301 (diacrítico "aciento agudo"), mas tamien puode ser repersentado cumo U+00E9 (letra latina "i" cun diacrítico "aciento agudo"). Tamien hai ls códigos de cuntrole Unicode, las marcas d'orde de byte i las marcas de direçon de testo, que dében ser tratados separadamente.

Uso 
Spressones regulares son ousadas por dibersos eiditores de testo, outelitairos i lenguaiges de porgramaçon para percurar i manipular testo baseado an padrones. Por eisemplo, Perl i Tcl possuen suporte la spressones regulares natibamente. Dibersos outelitairos de çtribuiçones Unix ancluen l'eiditor de testo ed, que popularizou l cunceito de spresson regular, i l filtro grep.

Outro uso ye la balidaçon de formatos de testo (balidaçon de protocolos ó formatos digitales). Por eisemplo, al recebir l'antrada dun campo de formulairo dua aplicaçon que supone recebir un andereço de email, puode-se ousar ua spresson regular para garantir que l que fui recebido de fato ye un andereço de email.

Mais un uso ye l'amplementaçon anterna dun sistema de rialce de sintaxe, cumo ancontrado an ambientes de zambolbimiento antegrado. Spressones regulares puoden ser ousadas para ancontrar palabras reserbadas, literales i outros tokenes specíficos, i para altarar la formataçon de l testo d'acuordo cul casamiento feito.

Un uso difundido de spressones regulares ye la filtraige d'anformaçon an bancos de dados de testo. Por eisemplo, nun arquibo de testo cuntendo cadastros de pessonas i sues datas d'anibersairo cumo a seguir:

 1954-10-01 João Alberto
 1976-07-25 Marie Eduarda
 1966-10-22 Carlos Silba

Puode-se filtrar pessonas que nacírun nun detreminado anho, més ó die. Por eisemplo, l'uso de l padron ^[0-9]{4}-10-[0-9]{2} (.*)$ eidantifica l nome de las pessonas que nacírun an outubre. Pa l cadastro arriba serien retornados dous grupos de catura, \1 cuntendo "João Alberto" i \2 cuntendo "Carlos Silba". Splorando l'eisemplo anterior i l'uso de balidaçon de formatos digitales, ye possible ousar spressones regulares para balidar las datas persentes ne l'arquibo de testo d'anibersairos arriba. L padron (19|20)\d\d([- /.])(0[1-9]|1[012])\2([012][0-9]|3[01]) ye ousado para balidar ua data antre 1900-01-01 i 2099-12-31. Atentar que la separaçon antre anho, més i die puode se dar atrabeç d'hífen, spácio an branco, barra ó punto. Mas debe-se ousar l mesmo simblo de separaçon antre anho i més i antre més i die, l que ye possible atrabeç de la rechamada de l grupo de catura anterior (l trecho \2 de l padron). Atentar tamien que l padron ye ancumpleto na medida an que nun defrencia la cantidade de dies an cada més, l que resulta ne l casamiento dua cadeia de carateres "2000-02-31", ancorreta d'acuordo cul calendairo griegoriano.

Eiditor de testo
 Teorie de la cumputaçon
 Outómato
 Lenguaige regular
 Casamiento de padrones

Manual de Regex
 Portal subre spressones regulares
 Wiki subre spressones regulares

Lenguaiges formales
Tópicos an lenguaiges de porgramaçon