Пређи на садржај

Regularni izraz

С Википедије, слободне енциклопедије
(преусмерено са Regular expression)

U računarstvu i informatici, regularni izraz (još i pravilan izraz, ispravan izraz - engl. skr. regexp ili regex, u množini regexps, regexes ili regexen) je niska koja opisuje ili sparuje skup niski, u skladu s određenim sintaksnim pravilima. Regularne izraze koriste mnogi tekst editori i pomoćni programi za pretragu i manipulaciju teksta. Mnogi programski jezici podržavaju regularne izraze za manipulisanje niskama. Na primer, Perl i Tcl imaju moćan motor za regularne izraze ugrađen direktno u sintaksu. Skup pomoćnih programa (uključujući uređivač sed i filter grep) koji se standardno distribuira sa juniks distribucijama je mnogo učinio na promociji i popularizaciji koncepta regularnih izraza.

Osnovni koncepti

[уреди | уреди извор]

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

alternacija

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

grupisanje

Zagrade se koriste za definisanje područja delovanja (engl. scope) i prednosti operatora. Na primer, "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 skupa njih određuje učestalost pojavljivanja izraza koji prethodi. Najčešće korišćeni kvantifikatori su ?, *, i +:

?

Upitnik označava da pojavljivanje prethodnog izraza nula puta ili jedanput. Na primer, colou?r sparuje i "color" i "colour".

*

Zvezdica (engl. asterisk) označava pojavljivanje prethodnog izraza nula puta, jedanput ili bilo koji veći broj puta. Na primer, "go*gle" sparuje ggle, gogle, google, gooogle, itd.

+

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

Ove elementarne konstrukcije se mogu kombinovati u proizvoljno složene izraze, slično načinu na koji se mogu konstruisati aritmetički izrazi iz brojeva i operacija +, -, * i /.

Stoga su "H(ae?|ä)ndel" i "H(a|ae|ä)ndel" ispravni uzorci, i štaviše, oba sparuju iste niske baš poput primera sa početka članka. Uzorak "((great )*grand )?((fa|mo)ther)" sparuje bilo koji od niski koje 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 od alata do alata i područja primene - više detalja je dato u sekciji Sintaksa.

Istorija

[уреди | уреди извор]

Poreklo regularnih izraza leži u teoriji automata i teoriji formalnih jezika, pri čemu su obe 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 nazvanu regularni skupovi. Ken Thompson je ugradio ovu notaciju u uređivač QED, a potom i u juniks editor ed, što je s vremenom dovelo do upotrebe regularnih izraza u grep-u. Otad se regularni izrazi naširoko koriste u juniksu i juniksoidnim 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 Spencer-ovu regex biblioteku i dodao mnogo novih svojstava.[1] Philip Hazel je razvio PCRE (Perl Compatible Regular Expressions) koji jako dobro oponaša funkcionalnost regularnih izraza u Perl-u, i kojeg koriste mnogi moderni programski alati kao što su PHP, ColdFusion, i Apache. Deo napora uloženog u dizajn Perla 6 je baš u smeru poboljšanja integracije Perl-ovih regularnih izraza, te povećanju njihovog područja delovanja u svrhu dozvole definicije tzv. 'parsing expression grammar[2]'. Rezultat je mini-jezik nazvan [[Perl 6 pravila]], koja se koriste kako za definiciju gramatike Perl-a 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 informacionim 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 upotreba je u grupnoj 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 niski i operacija nad tim skupovima. Za datu abecedu , sledeće konstante su definisane:

  • (prazan skup) koji označava
  • (prazna niska) koji označava skup
  • (literalni karakter) a u koji označava skup {a}

te sledeće operacije:

  • (nadovezivanje ili konkatenacija) RS označava skup { αβ | α u R i β u S }. Na primer {ab, c}{d, ef} = {abd, abef, cd, cef}.
  • (alternacija) R|S označava uniju skupova R i S.
  • (Klinijev operator) R* označava najmanji nadskup od R koji sadrži i zatvoren je za nadovezivanje niski. Ovo je skup svih niski koji mogu biti načinjeni nadovezivanjem nula ili više niski u R. Na primer, {ab, c}* = {ε, ab, c, abab, abc, cab, cc, ababab, ... }.

Gornje konstante i operatori oblikuju Kleeneovu algebru.

Mnogi udžbenici koriste simbole , + ili za alternaciju umesto vertikalne crte.

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

Primeri:

  • "a|b*" označava {ε, a, b, bb, bbb, ...}
  • "(a|b)*" označava skup svih niski koji se sastoje od bilo kog broja simbola a i b, uključujući praznu nisku
  • "b*(a|b*)*" isto kao prethodni primer
  • "ab*(c|ε)" označava skup svih niski koji počinju simbolom a, nakon kojeg sledi nula ili više simbola b te konačno opciono 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 niski koje sadrže paran broj simbola a i neparan broj simbola b

Formalna definicija regularnih izraza je s namerom štura i izbegava definisanje zamenljivih kvantifikatora ? i +, koji pak mogu biti izraženi na sledeći način: a+ = aa*, i a? = (ε|a). Ponekad se dodaje operator komplementiranja ~, tako da ~R označava skup svih niski nad Σ* koji nisu u R. Operator komplementiranja je zamenljiv - uvek se može izraziti korištenjem drugih operatora (proces računanja takvog predstavljanja je složen, a rezultat može biti eksponencijalno veći, ali je ipak moguć).

Regularni izrazi u ovom smislu mogu izraziti tačno klasu jezika koju prihvataju 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 dužina zahtevanih regularnih izraza raste linearno. Regularni izrazi odgovaraju trećem tipu gramatika hijerarhije Čomskog 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đe se može proučavati izražajnu moć unutar formalizma. Kao što primer pokazuje, različiti regularni izrazi izražavaju isti jezik - formalizam je zamenljiv.

Moguće je napisati algoritam koji za dva data regularna izraza ispituje jednakost opisanih jezika, tako što redukuje svaki izraz na minimalni deterministički konačni automat i potom ispituje izomorfnost njihovih grafova dijagrama stanja.

Do kog nivoa se ova zamenljivost može eliminisati? Može li se naći zanimljiv podskup regularnih izraza koji je još uvek potpuno izražajan? Kleeneov operator i unija skupova su očigledno među zahtevanim operacijama, ali možda njihova upotreba može biti ograničena. Ovo se pokazalo 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 aksiomatizabilni, te stoga moramo pribeći drugim metodama. Ovo vodi do problema visine zvezde.

Sintaksa

[уреди | уреди извор]

Tradicionalni regularni izrazi na juniksu

[уреди | уреди извор]

"Osnovna" sintaksa regularnih izraza na juniksu je danas zastarela po POSIX definicijama, iako se naširoko koristi zbog kompatibilnosti unazad. Većina pomoćnih programa na juniksu svesnih regularnih izraza, kao što su grep i sed, koriste ih podrazumevano, dok pružaju podršku za proširene regularne izraze preko komandnolinijskih argumenata (videti dole).

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 primer, "a.cd" sparuje abcd, "a..d" sparuje abcd.
[] Sparuje jedan karakter sadržan unutar uglastih zagrada. Na primer, "[abc]" sparuje a, b ili c. "[a-z]" sparuje sva mala slova. Ova se dva stila mogu i meš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 trebalo da bude 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 uglastu zagradu postaviti prvu u obuhvatajućim uglastim zagradama: "[][-{ab}]" sparuje ], [, a ili b.

[^] Sparuje jedan karakter koji nije sadržan unutar uglastih zagrada. Na primer, "[^abc]" sparuje bilo koji karakter osim a, b, i c. "[^a-z]" sparuje bilo koji karakter koji nije malo slovo. Baš kao u prethodnim primerima, ovi se stilovi mogu mešati.
^ Sparuje početak linije (bilo koje linije, kad je primenjen u višelinijskom načinu rada)
$ Sparuje kraj linije (bilo koje linije, kad je primenjen u višelinijskom načinu rada)
( ) Definiše "označeni podizraz". Što zagradama obuhvaćeni izraz sparuje može kasnije biti dohvaćeno - videti sledeći unos za \n. "Označeni podizraz" je takođe "blok". Ova osobina nije prisutna u nekim instancama regexa. U većini pomoćnih programa na juniksu (kao što su [[sed]] i [[vi]]), karakter "\" (engl. backslash) mora prethoditi otvorenim i zatvorenim zagradama.
\n Pri čemu n zamenjuje broj od 1 do 9 - sparuje n-ti spareni označeni podizraz. Ova konstrukcija je teoretski neregularna i nije prihvaćena u proširenoj sintaksi regularnih izraza.
* Izraz od jednog karaktera nakon kojeg sledi "*" sparuje nula ili više kopija sebe. Na primer, "ab*c" sparuje ac, abc, abbbc itd. "[xyz]*" sparuje praznu reč, x, y, zx, zyx, i tako dalje.
  • \n*, pri čemu n zamenjuje broj od 1 do 9, sparuje nula ili više iteracija n-tog sparenog označenog podizraza. Na primer, "(a.)c\1*" sparuje abcab i abcabab, ali ne i abcac.
  • Izraz zatvoren u "\(" i "\)" nakon čega sledi "*" je neispravan. U nekim slučajevima (npr. /usr/bin/xpg4/grep na SunOS 5.8), sparuje jednu ili više iteracija niske koje 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 sledi literalni karakter "*".
+ Izraz od jednog karaktera nakon kojeg sledi "+" sparuje jednu ili više kopija izraza. Na primer, "ab+c" sparuje abc, abbbc itd. "[xyz]+" sparuje x, y, zx, zyx, i tako dalje.
  • \n+, pri čemu n zamenjuje broj 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 sledi "+" je neispravan.
{x,y} Sparuje posljednji blok barem x i ne više od y puta. Na primer, "a\{3,5}" sparuje aaa, aaaa ili aaaaa. Ova konstrukcija nije prisutna u nekim instancama regexa.

Neke interpretacije regularnih izraza interpretiraju backslash karakter različito ispred nekih metakaraktera. Na primer, egrep i Perl interpretiraju zagrade i vertikalne crte kojima ne prethodi backslash kao metakaraktere, rezervišući verziju u kojima prethodi u svrhu značenja literalnih karaktera. Starije verzije programa grep nisu podržavale operator alternacije "|".

Primeri:

  • ".at" sparuje bilo koju nisku od tri karaktera poput hat, cat ili bat
  • "[hc]at" sparuje hat i cat
  • "[^b]at" sparuje sve sparene niske iz regularnog izraza ".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 zavise o specifično odabranim jezičkim postavkama (npr., u nekim postavkama su slova uređena kao abc..yzABC..YZ dok u nekim drugim kao aAbBcC..yYzZ), POSIX standard definiše neke razrede ili kategorije karaktera kao što je prikazano sledeć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] brojevi, velika i mala slova
[:digit:] [0-9] brojevi
[:xdigit:] [0-9A-Fa-f] heksadecimalni brojevi
[:punct:] [.,!?:...] interpunkcija (pravopisni znakovi)
[:blank:] [ \t] praznina (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 primer: [[:upper:]]ab] bi trebalo spariti samo velika slova i mala slova 'a' i 'b'.

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

Dodatni razred koga POSIX ne definiše, a koga neki alati razumeju je [:word:], koji se obično definiše 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 obojeni ASCII dijagram koji prikazuje POSIX razrede pogledati

Pohlepni izrazi

[уреди | уреди извор]

Kvantifikatori u regularnim izrazima sparuju koliko god mogu - pohlepni su (što znači da pokušavaju spariti najveći mogući broj karaktera). Ovo može biti značajan problem. Na primer, neko želi naći prvu instancu sadržaja u dvostrukim uglastim zagradama u tekstu

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

bi najizglednije koristio sledeći uzorak (\[\[.*\]\]), koji izgleda ispravan (uočimo da je uglastoj zagradi prethodi backslash te će na taj način biti interpretirana kao karakter literal). Međutim, ovaj će uzorak u stvari vratiti [[-{January}- 26]], [[2004]], in [[-{Tainan City}-]], [[-{Taiwan}-]] umesto 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 izbegavanja ovog problema. Prvi, umesto da se specificira šta 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šte spariti na ovoj niski:

  • 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 juniksu koristeći komandnolinijsku zastavicu "-E".

Prošireni POSIX regularni izrazi su slični u sintaksi tradicionalnim regularnim izrazima na juniksu, izuzev nekih izmena. Sledeći metakarakteri su dodati:

+ Spari poslednji "blok" jedanput ili više puta - "ba+" sparuje ba, baa, baaa i tako dalje
? Spari poslednji "blok" nula ili jednom - "ba?" sparuje b ili ba
| Operator izbora (ili unije skupova): spari ili izraz pre ili izraz posle operatora - "abc|def" sparuje abc ili def.

Takođe, backslash karakteri su odbačeni: \{...\} postaje {...} i \(...\) postaje (...). Primeri:

  • "[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 namene, moraju biti "obeleženi" ukoliko ih želimo koristiti kao karakter literale. To se obavlja tako što se ispred njih postavlja karakter '\' koji takođe mora biti "obeležen" ukoliko želimo da ga shvatimo kao literal. Primeri:

  • "a\.(\(|\))" sparuje nisku a.) ili a.(

Perl-kompatibilni regularni izrazi (PCRE)

[уреди | уреди извор]

Perl-kompatibilni regularni izrazi (engl. Perl-compatible regular expressions) je implementacija regularnih izraza u programskom jeziku [[Perl]]. Imaju bogatiju i predvidljiviju sintaksu čak i od proširenih POSIX regexa. Primer njihove predvidljivosti je činjenica da \ uvijek citira (engl. quote) nealfanumerički karakter. Primer nečega što je moguće specificirati u Perl-u ali ne i u POSIX-u je odabir dela sparivanja za koji se želi da bude pohlepan ili ne. Na primer, 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 niske "a bad dab" prvi uzorak spariti celu nisku, dok će drugi spariti samo "a b".

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

Uzorci za neregularne jezike

[уреди | уреди извор]

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

S druge strane, mnogi alati, biblioteke i motori koji pružaju takve konstrukcije 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 poslednjem kontekstu. Larry Wall (autor Perl-a) piše u Apokalipsi 5:

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

Implementacije i vremena izvršavanja

[уреди | уреди извор]

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

Najstariji i najbrži se pouzdaje na rezultat proizišao iz teorije formalnih jezika koji dozvoljava konverziju bilo kojeg nedeterminističkog konačnog automata (NKA) u isti deterministički konačni automat (DKA). Algoritam obavlja ili simulira konverziju i potom pokreće proces prihvatanja ulazne niske nad DKA, jedan po jedan znak. Ovaj poslednji korak zahteva linearno vreme u zavisno od dužine ulazne niske. Preciznije, ulazna niske veličine n se može testirati regularnim izrazom veličine m u vremenu O(n+2m) ili O(nm), zavisno od detalja programske implementacije. Ovaj algoritam se često naziva DKA algoritam. Brz je, ali se može koristiti samo za sparivanje, ne i za dohvatanje grupisanih podizraza. Postoji varijanta koja može dohvatiti i grupisane podizraze, ali njeno vreme izvođenja usporava sve do O(n2m).

Drugi algoritam je sparivanje uzorka i ulazne niske korištenjem pretraživanja unazad. (Ovaj se algoritam ponekad zove NKA, ali ova terminologija često zbunjuje). Vreme izvođenja ovog algoritma može biti eksponencijalno, što jednostavne implementacije 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ženije implementacije identifikuju i ubrzavaju razne uobičajene slučajeve.

Iako implementacije metodom pretraživanja unazad mogu dati samo eksponencijalnu garanciju u najgorem slučaju, dozvoljavaju mnogo veću fleksibilnost i pružaju izražajniju moć. Na primer, svaka implementacija koja dozvoljava upotrebu referenci unazad, ili pak ostvaruje razna poboljšanja koja je Perl uveo, mora biti implementirana preko pretraživanja unatrag.

Neke implementacije pokušavaju pružiti najbolje od oba algoritma tako što prvo pokreću DKA sparivanje da vide sparuje li uopšte niska regularni izraz, i samo u tom slučaju obavljaju potencijalno sporije sparivanje pretraživanjem unazad.

Regularni izrazi i Unicode

[уреди | уреди извор]

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

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

Drugi problem je da li je puni Unicode opseg podržan. Mnogi motori regularnih izraza podržavaju samo osnovni višejezični format, 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 orijentisane konstrukcije mogu biti prošireni u Unicode. Na primer, u ASCII baziranim implementacijama, karakterni opsezi oblika [x-y] su valjani kad god su x i y kodne tačke (engl. codepoint) u opsegu [0x00,0x7F] pri čemu je codepoint(x) <= codepoint(y). Prirodno proširenje takvih opsega karaktera bi jednostavno promenilo zahtev da krajnje tačke leže u opsegu [0x00,0x7F] u zahtev da leže u opsegu [0,0x10FFFF]. Međutim, u praksi to nije toliko čest slučaj. Neke implementacije, poput onoga pomoćnog alata [[gawk]], ne dozvoljavaju da opsezi karaktera pređu granice Unicode blokova. Opseg poput [0x61,0x7F] je ispravan pošto obe krajnje tačke leže u osnovnom latiničnom bloku, kao što je ispravan i [0x0530,0x0560] pošto obe krajnje tačke leže u armenskom bloku, ali opseg poput [0x0061,0x0532] je neispravan budući da uključuje višestruke Unicode blokove. Drugi motori, poput onoga u uređivaču Vim, dozvoljavaju prelaz između blokova ali ograničavaju broj karaktera u opsegu na 128.

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

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

Upotreba regularnih izraza

[уреди | уреди извор]

Regularni izrazi su izrazito korisni u programima kompletiranja koda i bojenja sintakse u integrisanim razvojnim okruženjima. Na primer 

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

bi spario funkcije u mnogim programskim jezicima.

Референце

[уреди | уреди извор]
  1. ^ Wall, Larry; Perl 5 razvojni tim (2006). „perlre: Perl regular expressions”. 
  2. ^ Wall, Larry (4. 6. 2002). „Apocalypse 5: Pattern Matching”. Архивирано из оригинала 12. 01. 2010. г. Приступљено 01. 04. 2008. 

Literatura

[уреди | уреди извор]

Spoljašnje veze

[уреди | уреди извор]

Članci

[уреди | уреди извор]
Преузето из „https://sr.wikipedia.org/w/index.php?title=Regularni_izraz&oldid=28524566”