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:

Metacaratere	Çcriçon
Padrones andebiduales
.	Casa qualquiera caratere. Alguas amplementaçones scluen quebra de linha i codificaçon de carateres. Nas spressones POSIX de listas de carateres (ber lougo ambaixo), l caratere punto ye tratado cumo l literal. Por eisemplo, la.c casa "abc", etc., mas [la.c] casa solamente "la", "." ó "c".
[ ]	Lista de carateres. Casa ua ocorréncia de qualquiera caratere cuntido na lista. Por eisemplo, [abc] casa "la", "b" ó "c". Ye possible defenir anterbalos de carateres: [la-ç] casa qualquiera caratere de "la" la "ç", i [0123456789] ye eigual la [0-9]. L caratere - ye tratado cumo literal se fur l purmeiro ó l radadeiro de la lista, ó se fur escapado: [abc-], [-abc] ó [la\-bc].
[^ ]	Lista negada de carateres. Casa ua ocorréncia de qualquiera caratere nun cuntido na lista. Por eisemplo, [^abc] casa qualquiera caratere que nun seia "la", "b" ó "c". [^la-ç] casa qualquiera caratere que nun steia an caixa baixa.
Áncoras
^	Casa l'ampeço de la cadeia de carateres. Nua situaçon de múltiplas linhas, casa l'ampeço de las linhas. Lougo percebe-se que las áncoras nun casan pedaços de l testo, eilhas serben solo cumo ua refréncia.
$	Casa la fin de la cadeia de carateres ó la posiçon lougo antes de la quebra de linha de l fin de la cadeia. Nua situaçon de múltiplas linhas, casa la fin de las linhas.
Catura de dados
BRE: \( \) ERE: ( )	Grupo de catura. Marca ua subexpresson. La cadeia de carateres que casa cul cuntenido drento de ls parénteses puode ser chamada mais tarde.
\m	Associado cul iten anterior. Casa la m-ésima subexpresson marcada, an que m ye un dígito de 1 a 9. Essa custruçon ye teoricamente eirregular i nun fui adotada pula sintaxe POSIX ERE. Alguas ferramientas permiten referenciar mais de nuobe grupos de catura.
Quantificadores (ó repetidores)
*	Casa l'eilemiento precedente zero ó mais bezes. Por eisemplo, ab*c casa "ac", "abc", "abbbc", etc.. [xyç]* casa "", "x", "y", "ç", "zx", "zyx", "xyzzy", i assi por delantre. \(ab\)* casa "", "ab", "abab", "ababab", i assi por delantre.
BRE: \{m,m\} ERE: {m,m}	Casa l'eilemiento precedente pul menos m bezes i nun mais que m bezes. Por eisemplo, la\{3,5\} casa solamente "aaa", "aaaa", i "aaaaa". Esta funcionalidade nun ye ancontrada an alguas amplementaçones mui antigas. Outras oupçones ancluen omitir un de ls campos. Por eisemplo, la\{3,\} casa pul menos trés "la"s. Yá la\{3\} casa solamente trés "la"s. b{0,} ye análogo la b*, b{0,1} ye análogo la b? (ber l quantificador ? ambaixo) i b{1,} ye idéntico la b+ (ber l quantificador + 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:

Quantificadores
?	Casa l'eilemiento precedente zero ó ua beç. Por eisemplo, ba? casa "b" ó "ba".
+	Casa l'eilemiento precedente ua ó mais bezes. Por eisemplo, ba+ casa "ba", "baa", "baaa", i assi por delantre. Cumo bisto na seçon de teorie, esse metacaratere puode ser simulado an BRE atrabeç de aa*.
Altarnadores
|	Casa ó la spresson que precede ó la spresson que sucede. Por eisemplo, abc|def casa "abc" ó "def".

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:

[:alnun:]	Carateres alfanuméricos, l que ne l causo de ASCII corresponde la [La-Za-z0-9].
[:alpha:]	Carateres alfabéticos, l que ne l causo de ASCII corresponde la [La-Za-ç].
[:blank:]	Spácio i tabulaçon, l que ne l causo de ASCII corresponde la [ \t].
[:cntrl:]	Carateres de cuntrole, l que ne l causo de ASCII corresponde la [\x00-\x1F\x7F].
[:digit:]	Dígitos, l que ne l causo de ASCII corresponde la [0-9]. L Perl ouferece l'atalho \d.
[:graph:]	Carateres besibles, l que ne l causo de ASCII corresponde la [\x21-\x7E].
[:lower:]	Carateres an caixa baixa, l que ne l causo de ASCII corresponde la [la-ç].
[:print:]	Carateres besibles i spácios, l que ne l causo de ASCII corresponde la [\x20-\x7E].
[:punt:]	Carateres de pontuaçon, l que ne l causo de ASCII corresponde la [-!"#$%&'()*+,./:;<=>?@[\\\]_`{|}~].
[:space:]	Carateres de spácios an branco, l que ne l causo de ASCII corresponde la [ \t\r\m\b\f]. L Perl ouferece l'atalho \s, que, antretanto, nun ye satamente eiquibalente; defrente de l \s, la classe inda anclui un tabulador bertical, \x11 de l ASCII.
[:upper:]	Carateres an caixa alta, l que ne l causo de ASCII corresponde la [La-Z].
[:xdigit:]	Dígitos heixadecimales, l que ne l causo de ASCII corresponde la [La-Fa-f0-9].

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:

[[:<:]]	Casa l'ampeço de palabras.
[[:>:]]	Casa la fin de palabras.

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:

Quantificadores nó-gulosos
??	Berson nó-gulosa de ?. Dado l testo "aaa", la? casa "la" anquanto la?? casa "".
*?	Berson nó-gulosa de *. Dado l testo "aaa", la* casa "aaa" anquanto la*? casa "".
+?	Berson nó-gulosa de +. Dado l testo "aaa", la+ casa "aaa" anquanto la+? casa "la".
{m,m}?	Berson nó-gulosa de {m,m}. Dado l testo "aaa", la{2,3} casa "aaa" anquanto la{2,3}? casa "aa".

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

Padrones andebiduales
\s	Casa spácios an branco, \m \r ó \t.
\S	Negaçon de \s: casa l que nun fur spácio an branco, \m \r ó \t.
\w	Casa letras, dígitos, ó '_'.
\W	Negaçon de \w
\d	Casa dígitos, de 0 a 9.
\D	Negaçon de \d
Áncoras
\b	Casa la separaçon de palabras, l qu'anclui tamien l'ampeço (^) i la fin ($) de la cadeia de carateres testada. La defeniçon de ls carateres que forman palabras barie d'acuordo cula amplementaçon, mas ye siguro assumir pul menos [la-zA-Z0-9_]. Habendo suporte, l'atalho \w ye ua altarnatiba bálida. L Jaba ye ua notable sceçon na medida an que suporta \b mas nun \w. Notar qu'anque parecida culs lemites de palabras defenidos pula POSIX, esta sequéncia de scape nun çtingue l'ampeço i l final de la palabra, solamente la separaçon an si.
\B	Negaçon de \b
\La	Casa l'ampeço de la cadeia de carateres. Nua situaçon de múltiplas linhas, nun casa l'ampeço de las linhas seguintes, l que la difire de ^.
\Z	Casa la fin de la cadeia de carateres ó la posiçon lougo antes de la quebra de linha de l fin de la cadeia. Nua situaçon de múltiplas linhas, nun casa la fin de las linhas seguintes, l que la difire de $.
\ç	Casa la fin de la cadeia de carateres.

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:

(?# )	Adiciona un comentairo, eignorado ne ls casamientos.
(?: )	Grupo de catura que nun ye salbo para rechamada posterior (\1, \2, \3, ...)
(?= )	Casa ocorréncias de l padron atual a partir de la posiçon atual até l final. Assi cumo las áncoras (^, $), l padron nun ye ancluído ne l casamiento, serbindo solo na berificaçon. Por eisemplo, l padron carro(?=azul) aplicado la "Un carro sportibo azul barato." casará "carro".
(?! )	Negaçon de (?=), casa l'auséncia de l padron atual a partir de la posiçon atual até l final, i tamien nun anclui l padron ne l casamiento. Por eisemplo, l padron carro(?!amarielho) casará an "Un carro sportibo azul barato.", antretanto carro(?!azul) nun casará.
(?<= )	Casa ocorréncias de l padron atual a partir de l'ampeço até la posiçon atual, mas nun anclui l padron ne l casamiento, serbindo solo na berificaçon. Por eisemplo, l padron (?<=carro)azul aplicado la "Un carro sportibo azul barato." casará "azul".
(?<! )	Negaçon de (?<=), casa l'auséncia de l padron atual a partir de l'ampeço até la posiçon atual, i tamien nun anclui l padron ne l casamiento. Por eisemplo, l padron (?<!carro)amarielho casará an "Un carro sportibo azul barato.", antretanto (?<!carro)azul nun casará.
(? )	Aplica modificadores a partes de la spresson regular. Ls balores aceitos son i (eignora defrenças antre maiúsculas i minúsculas), m (testo multelinha), s (testo monolinha) i x (ancluson de spácios i comentairos).
(?(La)B|C)	Un ouperador ternairo, ousado giralmente an cunjunto de ls grupos de catura. Por eisemplo, la scolha dua ó outra subexpresson regular depende dun casamiento ó nun anterior.
(?(La)B)	Bariaçon binária de la strutura anterior, an qu'ua spresson ye adicionada al padron se i solamente se la cundiçon ye berdadeira.

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($m+2^{m}$) ó L($nn$), 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.

Refréncias

• «Regular Spressiones» (an anglés). The Oupen Group. 1997. Cunsultado an 19 de júlio de 2008  !CS1 mantenéncia: Lhéngua nó recoincida (link)
• . [S.l.: s.n.]. ISBN 978-85-7522-212-6
• . [S.l.: s.n.]. ISBN 0-672-32566-7
• . [S.l.: s.n.]. ISBN 0-596-00289-0
• . [S.l.: s.n.]. ISBN 1-59059-107-0
• . [S.l.: s.n.]. ISBN 1-86100-730-2
• . [S.l.: s.n.]. ISBN 0-534-94728-X
• . [S.l.: s.n.]. ISBN 0-596-00415-X

Ber tamien

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

Lhigaçones sternas

• Manual de Regex
• Portal subre spressones regulares
• Wiki subre spressones regulares^{[lhigaçon einatiba]}