Regularni izraz

U računarstvu i informatici, regularni izraz (još i pravilni izraz, ispravni izraz – često i engleske skraćenice regexp ili regex, u množini regexps, regexes ili regexen) je niz znakova koji opisuje druge nizove znakova (engl. string), u skladu s određenim sintaksnim pravilima. Prvenstvena svrha regularnog izraza je opisivanje uzorka za pretraživanje nizova znakova.

Regularne izraze koriste mnogi uređivači teksta i pomoćni programi za pretragu i manipulaciju teksta ovisno o nekim uzorcima. Mnogi programski jezici podržavaju regularne izraze za manipulaciju stringovima. Na primjer, Perl i Tcl u svojoj sintaksi sadrže potrebne elemente za korištenje regularnih izraza. Skup pomoćnih programa (uključujući uređivač ed i filter grep) koji se standardno distribuira sa Unix distribucijama je znatno učinio na promociji i popularizaciji koncepta regularnih izraza.

Osnovni koncepti

Regularni izraz, često zvan uzorak ili pattern, je izraz koji opisuje skup stringova. Uobičajeno se koriste za davanje konciznog opisa skupa, bez potrebe za nabrajanjem svih elemenata skupa. Na primjer, skup koji sadrži sva tri stringa Handel, Händel, i Haendel se može opisati uzorkom "H(ä|ae?)ndel" (ili alternativno, kaže se da uzorak sparuje (engl. match) svaki od tri stringa. U većini formalizama, ako postoji regex koji sparuje određeni skup, tada postoji i beskonačan skup takvih izraza. Većina formalizama pružaju sljedeće operacije prilikom konstrukcije regularnih izraza:

alternacija

Okomita crta razdvaja alternative. Na primjer "gray|grey" se može skratiti u istovjetan izraz "gr(a|e)y", i pri tome spariti "gray" ili "grey".

grupiranje

Zagrade se koriste za definiranje područja djelovanja (engl. scope) i prednosti operatora. Na primjer, "gray|grey" i "gr(a|e)y" su različiti uzorci, ali oboje opisuju skup koji sadrži gray ili grey.

Kvantifikacija

Kvantifikator nakon znaka ili skupine njih određuje učestalost pojavljivanja izraza koji prethodi. Najčešće korišteni kvantifikatori su ?, *, i +:

?

Upitnik označava da se prethodni izraz pojavljuje 0 ili 1 puta. Na primjer, "colou?r" sparuje i color i colour.

*

Zvjezdica (engl. asterisk) označava pojavljivanje prethodnog izraza 0, 1 ili bilo koji veći broj puta. Na primjer, "go*gle" sparuje ggle, gogle, google, gooogle, itd.

+

Znak plusa označava pojavljivanje prethodnog izraza barem jednom. Na primjer, "go+gle" sparuje gogle, google, gooogle, itd. (ali ne i ggle).

Ovi se elementarni konstrukti mogu kombinirati u proizvoljno složene izraze, slično načinu na koji se mogu konstruirati aritmetički izrazi iz brojeva i operacija +, -, * i /.

Stoga "H(ae?|ä)ndel" i "H(a|ae|ä)ndel" jesu valjani uzorci, i štoviše, oba sparuju iste stringove baš poput primjer sa početka članka. Uzorak "((great )*grand )?((fa|mo)ther)" sparuje bilo kojeg od stringova koji u engleskom jeziku označavaju pretke father, mother, grand father, grand mother, great grand father, great grand mother, great great grand father, great great grand mother, great great great grand father, great great great grand mother i tako dalje.

Precizna sintaksa regularnih izraza varira ovisno o alatima i područjima primjene – više detalja je dano u sekciji Sintaksa.

Povijest

Porijeklo regularnih izraza leži u teoriji automata i teoriji formalnih jezika, pri čemu su oboje discipline teoretskog računarstva. Ove discipline proučavaju modele računanja (automate) te načine opisa i klasifikacije formalnih jezika. Matematičar Stephen Kleene je 1950-ih opisao ove modele koristeći matematičku notaciju zvanu regularni skupovi. Ken Thompson je ugradio ovu notaciju u uređivač QED, a potom i u Unix editor ed, što je s vremenom dovelo do uporabe regularnih izraza u grep-u. Otad se regularni izrazi naširoko koriste u Unixu i Unixoidnim pomoćnim programima kao što su expr, awk, Emacs, vi, lex i Perl.

Perl i Tcl regularni izrazi su izvedeni iz regex biblioteke koju je napisao Henry Spencer, iako je Perl kasnije proširio Spencerovu regex biblioteku i dodao mnogo novih svojstava. Philip Hazel je razvio PCRE (Perl Compatible Regular Expressions) koji jako dobro oponaša funkcionalnost regularnih izraza u Perlu, i kojeg koriste mnogi moderni programski alati kao što su PHP, ColdFusion, i Apache. Dio napora uloženog u dizajn Perla 6 je baš u smjeru poboljšanja integracije Perlovih regularnih izraza, te povećanju njihovog područja djelovanja u svrhu dozvole definicije tzv. 'parsing expression grammar Rezultat je mini-jezik zvan Perl 6 pravila, koja se koriste kako za definiciju gramatike Perla 6 tako i kao alat Perl programerima. Ova pravila čuvaju sva svojstva regularnih izraza, ali i dozvoljavaju definicije u BNF stilu parsera tehnikom rekurzivnog spusta preko potpravila.

Korištenje regularnih izraza u strukturiranim informacijskim standardima (za modeliranje dokumenata i baza podataka) se pokazalo vrlo važnim, počevši od 1960-ih te se proširujući 1980-ih konsolidacijom industrijskih standarda kao što je ISO SGML. Jezgra standarda jezika specifikacije strukture su regularni izrazi. Jednostavnija i evidentnija uporaba jest u groupnoj sintaksi DTD-a.

Formalna teorija jezika

Regularni izrazi mogu biti izraženi preko formalizma teorije formalnih jezika. Regularni se izrazi sastoje od konstanti i operatora koji označavaju skupove stringova i operacija nad tim skupovima. Za danu abecedu [math]\displaystyle{ \Sigma }[/math], sljedeće konstante su definirane:

• (prazni skup) [math]\displaystyle{ \emptyset }[/math] koji označava [math]\displaystyle{ \emptyset }[/math]
• (prazni string) [math]\displaystyle{ \varepsilon }[/math] koji označava skup [math]\displaystyle{ \left\{ \varepsilon \right\} }[/math]
• (literalni karakter) a u [math]\displaystyle{ \Sigma }[/math] koji označava skup {a}

te sljedeće operacije:

• (nadovezivanje ili konkatenacija) RS označava skup { αβ | α u R i β u S }. Na primjer {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}.
• (alternacija) R|S označava uniju skupova R i S.
• (Kleeneov operator) R* označava najmanji nadskup od R koji sadrži [math]\displaystyle{ \varepsilon }[/math] i zatvoren je na nadovezivanje stringova. Ovo je skup svih stringova koji mogu biti načinjeni nadovezivanjem nijednog ili više stringova u R. Na primjer, {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", … }.

Gornje konstante i operatori oblikuju Kleeneovu algebru.

Mnogi udžbenici koriste simbole [math]\displaystyle{ \cup }[/math], + ili [math]\displaystyle{ \vee }[/math] za alternaciju mjesto vertikalne crte.

Da bi se izbjeglo korištenje zagrada, pretpostavlja se da Kleeneov operator ima najveću prednost, a potom slijede nadovezivanje i naposljetku unija skupova. Ukoliko ne postoji nejednoznačnost, zagrade se mogu odbaciti. Na primjer, (ab)c se piše kao abc i a|(b(c*)) može biti zapisano kao a|bc*.

Primjeri:

• a|b* označava {ε, a, b, bb, bbb, …}
• (a|b)* označava skup svih stringova koji se sastoje od bilo kojeg broja simbola a i b, uključujući prazni string
• b*(a|b*)* isto kao prethodni primjer
• ab*(c|ε) označava skup svih stringova koji počinju simbolom a, nakon kojeg slijedi nula ili više simbola b te konačno opcionalno c.
• (aa|ab(bb)*ba)*(b|ab(bb)*a)(a(bb)*a|(b|a(bb)*ba)(aa|ab(bb)*ba)*(b|ab(bb)*a))* označava skup svih stringova koji sadrže paran broj simbola a i neparan broj simbola b

Formalna definicija regularnih izraza je s namjerom štura i izbjegava definiranje zalihosnih kvantifikatora ? i +, koji pak mogu biti izraženi na sljedeći način: a+ = aa*, i a? = (ε|a). Ponekad se dodaje operator komplementa ~, tako da ~R označava skup svih stringova nad Σ* koji nisu u R. Operator komplementa je zalihosan – uvijek ga se može izraziti korištenjem drugih operatora (proces računanja takvog predstavljanja je složen, a rezultat može biti eksponencijalno veći, no svejedno je moguć).

Regularni izrazi u ovom smislu mogu izraziti točno klasu jezika koju prihvaćaju konačni automati – regularne jezike. Međutim, postoji značajna razlika u kompaktnosti – neke klase regularnih jezika mogu biti opisane automatima koji rastu eksponencijalno u veličini, dok duljina zahtijevanih regularnih izraza raste linearno. Regularni izrazi odgovaraju trećem tipu gramatika Chomskyjeve hijerarhije i mogu biti korišteni za opis regularnog jezika. S druge strane, postoji jednostavno preslikavanje između regularnih izraza i nedeterminističkih konačnih automata (NKA) koje ne vodi ka tolikom rastu veličine. To je glavni razlog korištenja NKA kao alternativnog načina predstavljanja regularnih izraza.

Također se može proučavati ekspresivna moć unutar formalizma. Kao što primjer pokazuje, različiti regularni izrazi izražavaju isti jezik – formalizam je zalihosan.

Moguće je napisati algoritam koji za dva dana regularna izraza ispituje jednakost opisanih jezika, na način što reducira svaki izraz na minimalni deterministički konačni automat i potom ispituje izomorfnost njihova grafa dijagrama stanja.

Do koje razine se ova zalihost može eliminirati? Može li se naći zanimljiv podskup regularnih izraza koji je još uvijek potpuno ekspresivan? Kleeneov operator i unija skupova su očito među zahtijevanim operacijama, ali možda njihova uporaba može biti ograničena. Ovo se pokazao kao začuđujuće težak problem. Koliko god jednostavni regularni izrazi bili, pokazalo se da ne postoji metoda njihovog sistematskog prepisivanja u neki normalni oblik. Oni nisu konačno aksiomatizibilni, te stoga moramo pribjeći drugim metodama. Ovo vodi do problema visine zvijezde; pogledati dolje za više o ovome.

Sintaksa

Tradicionalni regularni izrazi na Unixu

"Osnovna" sintaksa regularnih izraza na Unixu je danas zastarjela po POSIX definicijama, iako se naširoko koristi poradi unazadne kompatibilnosti. Većina pomoćnih programa na Unixu svjesnih regularnih izraza, kao što su grep i sed, koriste ih podrazumijevano, dok pružaju podršku za proširene regularne izraze preko komandnolinijskih argumenata (vidjeti dolje).

U osnovnoj sintaksi, sa većinom se karaktera postupa doslovno (kao završnim znakovima) – sparuju se samo sa sobom samima (tj. "a" sparuje "a", (bc" sparuje "(bc", itd).

.	Sparuje bilo koji karakter samo jednom. Unutar [] ima svoje uobičajeno značenje. Na primjer, "a.cd" sparuje "abcd", "a..d" sparuje "abcd".
[ ]	Sparuje jedan karakter sadržan unutar uglatih zagrada. Na primjer, [abc] sparuje "a", "b", or "c". [a-z] sparuje sva mala slova. Ova se dva stila mogu i miješati: [abcq-z] sparuje a, b, c, q, r, s, t, u, v, w, x, y, z, baš kao i [a-cq-z]. Karakter '-' bi trebao biti shvaćen doslovno (kao literal) samo ako je prvi ili posljednji karakter unutar zagrada: [abc-] ili [-abc]. Da bi se sparili karakteri '[' ili ']', najlakše je zatvarajuću uglatu zagradu postaviti prvu u obuhvaćajućim uglatim zagradama: [][ab] sparuje ']', '[', 'a' ili 'b'.
[^ ]	Sparuje jedan karakter koji nije sadržan unutar uglatih zagrada. Na primjer, [^abc] sparuje bilo koji karakter osim "a", "b", i "c". [^a-z] sparuje bilo koji karakter koji nije malo slovo. Baš kao u prethodnim primjerima, ovi se stilovi mogu miješati.
^	Sparuje početak linije (bilo koje linije, kad je primijenjen u višelinijskom načinu rada)
$	Sparuje kraj linije (bilo koje linije, kad je primijenjen u višelinijskom načinu rada)
( )	Definira "označeni podizraz". Što zagradama obuhvaćeni izraz sparuje može kasnije biti dohvaćeno – vidjeti sljedeći unos za \n. "Označeni podizraz" je također "blok". Ova osobina nije prisutna u nekim instancama regexa. U većini pomoćnih programa na Unixu (kao što su sed i vi), karakter "\" (engl. backslash) mora prethoditi otvorenim i zatvorenim zagradama.
\n	Pri čemu je n znamenka od 1 do 9 – sparuje n-ti spareni označeni podizraz. Ovaj konstrukt je teoretski neregularan i nije prihvaćen u proširenoj sintaksi regularnih izraza.
*	Izraz od jednog karaktera nakon kojeg slijedi "*" sparuje nula ili više kopija sebe. Na primjer, "ab*c" sparuje "ac", "abc", "abbbc" itd. "[xyz]*" sparuje "", "x", "y", "zx", "zyx", i tako dalje. \n*, pri čemu je n znamenka od 1 do 9, sparuje nula ili više iteracija n-tog sparenog označenog podizraza. Na primjer, "(a.)c\1*" sparuje "abcab" i "abcabab", ali ne i "abcac". Izraz zatvoren u "\(" i "\)" nakon čega slijedi "*" je nevaljan. U nekim slučajevima (npr. /usr/bin/xpg4/grep na SunOS 5.8), sparuje jednu ili više iteracija stringa kojeg zagradama obuhvaćeni izraz sparuje. U drugim slučajevima, (npr. /usr/bin/grep na SunOS 5.8), sparuje ono što zagradama obuhvaćeni izraz sparuje, nakon čega slijedi literalni karakter "*".
+	Izraz od jednog karaktera nakon kojeg slijedi "+" sparuje jednu ili više kopija izraza. Na primjer, "ab+c" sparuje "abc", "abbbc" itd. "[xyz]+" sparuje "x", "y", "zx", "zyx", i tako dalje. \n+, pri čemu je n znamenka od 1 do 9, sparuje jednu ili više iteracija onoga što sparuje n-ti označeni podizraz. Izraz obuhvaćen sa "\(" i "\)" nakon kojeg slijedi "+" je navaljan.
{x,y}	Sparuje posljednji blok barem "x" i ne više od "y" puta. Na primjer, "a\{3,5}" sparuje "aaa", "aaaa" ili "aaaaa". Uočite da ovaj konstrukt nije prisutan u nekim instancama regexa.

Uočite da neka pojedina ostvarenja regularnih izraza interpretiraju backslash karakter različito ispred nekih metakaraktera. Na primjer, egrep i Perl interpretiraju zagrade i vertikalne crte kojima ne prethodi backslash kao metakaraktere, rezervirajući verziju u kojima prethodi u svrhu značenja literalnih karaktera. Starije verzije programa grep nisu podržavale operator alternacije "|".

Primjeri:

".at" sparuje bilo koji string od tri karaktera poput hat, cat ili bat

"[hc]at" sparuje hat i cat

"[^b]at" sparuje sve sparene stringove iz regexa ".at" izuzev bat

"^[hc]at" sparuje hat i cat ali samo na početku linije

"[hc]at$" sparuje hat i cat ali samo na kraju linije

Budući da mnogi opsezi karaktera ovise o specifično odabranim jezičnim postavkama (npr., u nekim postavkama su slova uređena kao abc..yzABC..YZ dok u nekim drugim kao aAbBcC..yYzZ), POSIX standard definira neke razrede ili kategorije karaktera kao što je prikazano sljedećom tablicom:

POSIX razred	slično izrazu	značenje
[:upper:]	[A-Z]	velika slova
[:lower:]	[a-z]	mala slova
[:alpha:]	[A-Za-z]	velika i mala slova
[:alnum:]	[A-Za-z0-9]	znamenke, velika i mala slova
[:digit:]	[0-9]	znamenke
[:xdigit:]	[0-9A-Fa-f]	heksadecimalne znamenke
[:punct:]	[.,!?:...]	punktuacija (pravopisni znakovi)
[:blank:]	[ \t]	karakter praznine (engl. space) i TAB
[:space:]	[ \t\n\r\f\v]	prazninski karakteri (engl. whitespace)
[:cntrl:]		kontrolni karakteri
[:graph:]	[^ \t\n\r\f\v]	karakteri koji se mogu grafički ispisati
[:print:]	[^\t\n\r\f\v]	karakteri koji se mogu grafički ispisati i karakter praznine

Na primjer: [[:upper:]ab] bi trebao spariti samo velika slova i mala slova 'a' i 'b'.

Dogovorno je prihvaćeno da se razred [:print:] sastoji od razreda [:graph:] uz pridodan karakter praznine (space). Međutim, u Perlovim regularnim izrazima [:print:] sparuje uniju razreda [:graph:] i [:space:].

Dodatni razred kojeg POSIX ne definira a kojeg neki alati razumiju jest [:word:], koji se obično definira kao razred [:alnum:] sa pridodanim karakterom "_" (engl. underscore). Ovo odražava činjenicu da je ovako proširen razred korišten u mnogim programskim jezicima kao skup karaktera dozvoljen u nazivima identifikatora. Uređivač vim još razlikuje i razrede word i word-head (koristeći notaciju \w i \h) pošto u mnogim programskim jezicima karakteri kojima nazivi identifikatora mogu započinjati nisu isti kao i karakteri koji mogu biti sadržani na ostalim pozicijama naziva identifikatora.

(Za obojani ASCII dijagram koji prikazuje POSIX razrede pogledati ASCII.)

Pohlepni izrazi

Kvantifikatori u regularnim izrazima sparuju koliko god mogu – pohlepni su (što znači da pokušavaju spariti najveći mogući ishod). Ovo može biti značajan problem. Na primjer, netko tko želi naći prvu instancu sadržaja u dvostrukim uglatim zagradama u tekstu

Another whale explosion occurred on [[January 26]], [[2004.]], in [[Tainan City]], [[Taiwan]].

bi najizglednije koristio sljedeći uzorak (\[\[.*\]\]), koji izgleda ispravan (uočimo da je uglatoj zagradi prethodi backslash te će na taj način biti interpretirana kao karakter literal). Međutim, ovaj će uzorak ustvari vratiti [[January 26]], [[2004.]], in [[Tainan City]], [[Taiwan]] mjesto očekivanog [[January 26]]. Ovo se događa zato što će uzorak vratiti sve između prve dvije uglate zagrade od [[January 26]] i posljednje dvije uglate zagrade od [[Taiwan]].

Postoje dva načina izbjegavanja ovog problema. Prvi, mjesto da se specificra što se sparuje, specificira se što se ne sparuje – u ovom se slučaju ] ne sparuje, pa će uzorak biti (\[\[[^\]]*\]\]). Međutim, ovaj uzorak neće uopće spariti na ovom stringu:

A B C [[D E] F G]]

Drugo, moderni alati za regularne izraze dozvoljavaju kvantifikatoru da bude specificiran kao nepohlepan, stavljanjem znaka upitnika ispred kvantifikatora: (\[\[.*?\]\]).

Moderni (prošireni) POSIX regularni izrazi

Moderniji "prošireni" regularni izrazi mogu često biti korišteni u modernim pomoćnim programima na Unixu koristeći komandnolinijsku zastavicu "-E".

Prošireni POSIX regularni izrazi su slični u sintaksi tradicionalnim regularnim izrazima na Unixu, izuzev nekih iznimki. Sljedeći metakarakteri su dodani:

+	Spari posljednji "blok" jedan ili više puta – "ba+" sparuje "ba", "baa", "baaa" i tako dalje
?	Spari posljednji "blok" nula ili više puta – "ba?" sparuje "b" ili "ba"
|	Operator izbora (ili unije skupova): spari ili izraz prije ili izraz poslije operatora – "abc|def" sparuje "abc" ili "def".

Također, backslash karakteri su odbačeni: \{...\} postaje {...} i \(...\) postaje (…). Primjeri:

"[hc]+at" sparuje "hat", "cat", "hhat", "chat", "hcat", "ccchat" itd.

"[hc]?at" sparuje "hat", "cat" i "at"

"([cC]at)|([dD]og)" sparuje "cat", "Cat", "dog" i "Dog"

Budući da su karakteri '(', ')', '[', ']', '.', '*', '?', '+', '^' i '$' korišteni kao istaknuti karakteri posebne namjene, moraju biti "eskejpani" ukoliko ih se misli koristiti kao karakter literale. To se obavlja tako što se ispred njih postavlja karakter '\' koji također mora biti "eskejpan" ukoliko se želi shvatiti kao literal. Primjeri:

"a\.(\(|\))" sparuje string "a.)" ili "a.("

Perl-kompatibilni regularni izrazi (PCRE)

Perl-kompatibilni regularni izrazi (engl. Perl-compatible regular expressions) je ostvarenje regularnih izraza u programskom jeziku Perl. Imaju bogatiju i predvidljiviju sintaksu čak i od proširenih POSIX regexa. Primjer njihove predvidljivosti jest činjenica da \ uvijek citira (engl. quote) nealfanumerički karakter. Primjer nečega što je moguće specificirati u Perlu ali ne i u POSIXu jest odabir dijela sparivanja za koji se želi da bude pohlepan ili ne. Na primjer, u uzorku /a.*b/, poduzorak .* će spariti koliko god može, dok će uzorak /a.*?b/, .*? spariti što je moguće manje. Tako će u slučaju stringa "a bad dab" prvi uzorak spariti cijeli string, dok će drugi spariti samo "a b".

Zbog ovih razloga, mnogi drugi pomoćni programi i aplikacije su prigrlili sintaksu koja jako sliči Perlovoj – na primjer Java, Ruby, Python, PHP, exim, BBEdit pa čak i Microsoftov .NET Framework svi koriste sintaksu regularnih izraza sličnu Perlovoj. Nisu sve "Perl-kompatibilne" implementacije regularnih izraza identične, i mnoge implementiraju samo podskup Perlovih osobina.

Uzorci za neregularne jezike

Mnogi uzorci pružaju ekspresivnu moć koja nadaleko nadilazi onu regularnih jezika. Na primjer, sposobnost grupiranja podizraza zagradama i njihovo dohvaćanje u istom izrazu znači da uzorak može spariti string ponavljajućih riječi poput "papa" ili "WikiWiki" koji se zovu "kvadrati" (engl. squares) u teoriji formalnih jezika. Uzorak za ovakve stringove je samo "(.*)\1". Međutim, jezik kvadrata nije regularan, pa čak ni kontekstno-neovisan. Sparivanje uzoraka sa neograničenim brojem unazadnih referenci, kao što pružaju brojni moderni alati, je NP-teško.

S druge strane, mnogi alati, biblioteke i motori koji pružaju takve konstrukte svejedno koriste naziv regularni izraz za svoje uzorke. Ovo je dovelo do nomenklature u kojoj naziv "regularni izraz" ima različita značenja u teoriji formalnih jezika i u sparivanju uzoraka. Predloženo je korištenje naziva regex ili jednostavno uzorak u potonjem kontekstu. Larry Wall (autor Perla) piše u Apokalipsi 5:

"'[R]egularni izrazi' […] se samo marginalno odnosi na prave regularne izraze. Svejedno, naziv je rastao sa sposobnostima naših strojeva za sparivanje uzoraka, te se stoga neću ovdje pokušati boriti oko lingvističke nužnosti. Međutim, općenito ću koristiti naziv "regexes" (ili "regexen" kad sam u anglosaksonskom raspoloženju)."

Ostvarenja i vremena izvršavanja

Postoje barem dva različita algoritma odlučivanja sparuje li (i kako) regularni izraz dani string.

Najstariji i najbrži se pouzdaje na rezultat proizašao iz teorije formalnih jezika koji dozvoljava konverziju bilo kojeg nedeterminističkog konačnog automata (NKA) u istovjetni deterministički konačni automat (DKA). Algoritam obavlja ili simulira konverziju i potom pokreće proces prihvaćanja ulaznog stringa nad DKA, jedan po jedan znak. Ovaj posljednji korak zahtijeva linearno vrijeme u ovisnosti o duljini ulaznog stringa. Preciznije, ulazni string veličine n se može testirati regularnim izrazom veličine m u vremenu O(n+2^m) ili O(nm), ovisno o detaljima programskog ostvarenja (implementacije). Ovaj algoritam se često naziva DKA algoritam. Brz je, ali se može koristiti samo za sparivanje, ne i za dohvaćanje grupiranih podizraza. Postoji varijanta koja može dohvatiti grupirane podizraze, ali njeno vrijeme izvođenja usporava sve do O(n²m).

Drugi algoritam jest sparivanje uzorka i ulaznog stringa korištenjem unazadnog pretraživanja. (Ovaj se algoritam ponekad zove NKA, ali ova terminologija često zbunjuje). Vrijeme izvođenja ovog algoritma može biti eksponencijalno, što jednostavna ostvarenja demonstriraju kada sparuju izraze poput "(a|aa)*b" koji sadrže i alternaciju i neograničenu kvantifikaciju, te tako prisiljavaju algoritam da uzme u obzir eksponencijalan broj podizraza. Složenija ostvarenja identificiraju i ubrzavaju razne uobičajene slučajeve.

Iako ostvarenja metodom unazadnog pretraživanja mogu dati samo eksponencijalnu garanciju u najgorem slučaju, dozvoljavaju mnogo veću fleksibilnost i pružaju ekspresivniju moć. Na primjer, svako ostvarenje koje dozvoljava uporabu unazadnih referenci, ili pak ostvaruje razna poboljšanja koja je Perl uveo, mora biti ostvarena preko unazadnog pretraživanja.

Neka ostvarenja pokušavaju pružiti najbolje od oba algoritma tako što prvo pokreću DKA sparivanje da vide sparuje li uopće string regularni izraz, i samo u tom slučaju obavljaju potencijalno sporije sparivanje unazadnim pretraživanjem.

Regularni izrazi i Unicode

Regularni su izrazi izvorno korišteni sa ASCII karakterima. Mnogi strojevi regularnih izraza danas mogu barati i sa Unicode simbolima. U većini slučajeva je svejedno o kojem se skupu karaktera radi, ali određeni problemi se pojavljuju proširenjem regularnih izraza u Unicode.

Jedan od problema jest koji je Unicode format podržan. Svi komandnolinijski motori regularnih izraza očekivaju UTF-8, ali to varira kod biblioteka regularnih izraza. Neke očekivaju UTF-8, dok druge očekivaju druga Unicode enkodiranja (UTF-16, zastarjeli UCS-2 ili UTF-32).

Drugi problem jest je li puni Unicode opseg podržan. Mnogi strojevi regularnih izraza podržavaju samo osnovnu višejezičnu ravninu, tj. karaktere koji se mogu enkodirati samo u 16 bitova. Samo nekoliko trenutno prisutnih motora mogu baratati punim 21-bitnim Unicode opsegom.

Treći problem je varijacija u načinu kako ASCII orijentirani konstrukti mogu biti prošireni u Unicode. Na primjer, u ASCII baziranim ostvarenjima, karakterni opsezi oblika [x-y] su valjani kadgod su x i y kodne točke (engl. codepoint) u opsegu [0x00,0x7F] pri čemu je codepoint(x) <= codepoint(y). Prirodno proširenje takvih opsega karaktera bi jednostavno promijenilo zahtjev da krajnje točke leže u opsegu [0x00,0x7F] u zahtjev da leže u opsegu [0,0x10FFFF]. Međutim, u praksi to nije toliko čest slučaj. Neka ostvarenja, poput onoga pomoćnog alata gawk, ne dozvoljavaju da opsezi karaktera pređu granice Unicode blokova. Opseg poput [0x61,0x7F] je valjan pošto obje krajnje točke leže u osnovnom latinskom bloku, kao što je valjan i [0x0530,0x0560] pošto obje krajnje točke leže u armenskom bloku, ali opseg poput [0x0061,0x0532] je nevaljan jer uključuje višestruke Unicode blokove. Drugi strojevi, poput onoga u uređivaču Vim (uređivač teksta)Vim, dozvoljavaju prijelaz između blokova ali ograničavaju broj karaktera u opsegu na 128.

Također je područje u kojem postoje varijacije u interpretaciji ono koje se tiče zastavica kontrole razlikovanja velikih i malih slova. Neke takve zastavice djeluju samo na ASCII karaktere. Druge zastavice djeluju na sve karaktere. Neki strojevi imaju različite zastavice, jednu za ASCII drugu za Unicode. Također varira određivanje koji karakteri pripadaju POSIX razredima.

Drugi odgovor na Unicode je bilo uvođenje razreda karaktera za Unicode blokove i općenita svojstva Unicode karaktera. U Perlu i u Java biblioteci java.util.regex, razredi oblika \p{InX} sparuju karaktere u bloku X i \P{InX} sparuje komplement. Na primjer, \p{Armenian} sparuje bilo koji karakter u armenskom bloku. Slično, \p{X} sparuje bilo koji karakter sa općim svojstvom karaktera X i \P{X} komplement. Na primjer, \p{Lu} sparuje sva velika slova.

Uporaba regularnih izraza

Regularni su izrazi osobito korisni u sustavima kompletiranja koda i bojanja sintakse u integriranim razvojnim okolišima. Na primjer

(public|private|protected|)\s*(\w+)\s+(\w+)\s*\("

bi spario funkcije u mnogim programskim jezicima.

Bilješke

]]}},

Izvori

• Forta, Ben. Sams Teach Yourself Regular Expressions in 10 Minutes. Sams. ISBN 0-672-32566-7 

• Friedl, Jeffrey. Mastering Regular Expressions. O'Reilly. ISBN 0-596-00289-0 

• Habibi, Mehran. Real World Regular Expressions with Java 1.4. Springer. ISBN 1-59059-107-0 

• Liger, Francois; Craig McQueen, Paul Wilton. Visual Basic .NET Text Manipulation Handbook. Wrox Press. ISBN 1-86100-730-2 

• Sipser, Michael. "Chapter 1: Regular Languages". Introduction to the Theory of Computation. PWS Publishing. str. 31–90. ISBN 0-534-94728-X 

• Stubblebine, Tony. Regular Expression Pocket Reference. O'Reilly. ISBN 0-596-00415-X 

Vanjske poveznice

• Regular-Expressions.info Alati za regularne izraze, primjeri i reference. (en.)
• DMOZ popis povezinca za regularne izraze (en.)
• Regular Expression Library Biblioteka regularnih izraza suradnika iz cijelog svijeta. (en.)
• Boost Regular Expression Library C++ biblioteka regularnih izraza na web stranici boost.org (en.)
• Javascript RegExp Object Reference od Mozilla Developer Center (en.)
• Regular Expression Cheat Sheet Referenca regularnih izraza na jednoj stranici (en.)
• Regexp Syntax Summary Referentna tablica za UNIX grep, Emacs, Perl, Python i Tcl regularnih izraza. (en.)
• SWC – Regular Expressions Početnica regularnih izraza sa poveznicama na teoriju računanja i popularne aspekte korištenja. (en.)
• Regular Expression Quick Reference (PDF) (en.)
• The Regex Coach Besplatni pomoćni program za testiranje regularnih izraza. (en.)
• The RegexTester Besplatni online pomoćni program za testiranje regularnih izraza. (en.)
• Primjer s regularnim izrazima s web stranice www.osvemu.com (hrv.)^{[neaktivna poveznica]}
• Primjer s regularnim izrazima s web stranice JAVA NET (hrv.)