From Wikipedia, the free encyclopedia
U računarstvu i informatici, regularni izraz (još i pravilan izraz, ispravan izraz - engl. skr. ili , u množini , ili ) 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, i imaju moćan motor za regularne izraze ugrađen direktno u sintaksu. Skup pomoćnih programa (uključujući uređivač i filter koji se standardno distribuira sa juniks distribucijama je mnogo učinio na promociji i popularizaciji koncepta regularnih izraza.
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 , , i se može opisati uzorkom "(|?)" (ili alternativno, kaže se da uzorak sparuje (engl. ) 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:
Uspravna crta razdvaja alternative. Na primer "|" se može skratiti u istovetan izraz "(|)", i pri tome spariti ili .
Zagrade se koriste za definisanje područja delovanja (engl. ) i prednosti operatora. Na primer, "|" i "(|)" su različiti uzorci, ali oboje opisuju skup koji sadrži ili .
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, sparuje i "" i "".
Zvezdica (engl. ) označava pojavljivanje prethodnog izraza nula puta, jedanput ili bilo koji veći broj puta. Na primer, sparuje , , , , itd.
Znak plus označava pojavljivanje prethodnog izraza barem jednom. Na primer, sparuje , , , itd. (ali ne i ).
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 "(?|)" i "(||)" ispravni uzorci, i štaviše, oba sparuju iste niske baš poput primera sa početka članka. Uzorak "(( )* )?((|))" sparuje bilo koji od niski koje u engleskom jeziku označavaju pretke , , , , , , , , , i tako dalje.
Precizna sintaksa regularnih izraza varira od alata do alata i područja primene - više detalja je dato u sekciji Sintaksa.
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 je 1950-ih opisao ove modele koristeći matematičku notaciju nazvanu regularni skupovi. je ugradio ovu notaciju u uređivač , a potom i u juniks editor , što je s vremenom dovelo do upotrebe regularnih izraza u -u. Otad se regularni izrazi naširoko koriste u juniksu i juniksoidnim pomoćnim programima kao što su , , , , i .
i regularni izrazi su izvedeni iz regex biblioteke koju je napisao , iako je kasnije proširio -ovu regex biblioteku i dodao mnogo novih svojstava.[1] je razvio () koji jako dobro oponaša funkcionalnost regularnih izraza u -u, i kojeg koriste mnogi moderni programski alati kao što su , , i . Deo napora uloženog u dizajn je baš u smeru poboljšanja integracije -ovih regularnih izraza, te povećanju njihovog područja delovanja u svrhu dozvole definicije tzv. [2]'. Rezultat je mini-jezik nazvan 6 pravila, koja se koriste kako za definiciju gramatike -a 6 tako i kao alat 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 . Jezgra standarda jezika specifikacije strukture su regularni izrazi. Jednostavnija i evidentnija upotreba je u grupnoj sintaksi -a.
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:
te sledeće operacije:
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, "()" se piše kao "" i "|((*))" može biti zapisano kao "|*".
Primeri:
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: + = *, i ? = (ε|). Ponekad se dodaje operator komplementiranja ~, tako da ~ označava skup svih niski nad Σ* koji nisu u . 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.
"Osnovna" sintaksa regularnih izraza na juniksu je danas zastarela po definicijama, iako se naširoko koristi zbog kompatibilnosti unazad. Većina pomoćnih programa na juniksu svesnih regularnih izraza, kao što su 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. "" sparuje , "(" sparuje (, itd).
. | Sparuje bilo koji karakter samo jednom. Unutar [] ima svoje uobičajeno značenje. Na primer, "." sparuje , ".." sparuje . |
[] | Sparuje jedan karakter sadržan unutar uglastih zagrada. Na primer, "[]" sparuje , ili . "[-]" sparuje sva mala slova. Ova se dva stila mogu i mešati: "[-]" sparuje , , , , , , , , , , , , , baš kao i "[--]".
Karakter '-' bi trebalo da bude shvaćen doslovno (kao literal) samo ako je prvi ili posljednji karakter unutar zagrada: "[-]" ili "[-]". Da bi se sparili karakteri '[' ili ']', najlakše je zatvarajuću uglastu zagradu postaviti prvu u obuhvatajućim uglastim zagradama: "[][-{ab}]" sparuje ], [, ili . |
[^] | Sparuje jedan karakter koji nije sadržan unutar uglastih zagrada. Na primer, "[^]" sparuje bilo koji karakter osim , , i . "[^-]" 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 [[]] i [[]]), karakter "\" (engl. ) mora prethoditi otvorenim i zatvorenim zagradama. |
\ | Pri čemu zamenjuje broj od 1 do 9 - sparuje -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, "*" sparuje , , itd. "[]*" sparuje praznu reč, , , , , i tako dalje.
|
+ | Izraz od jednog karaktera nakon kojeg sledi "+" sparuje jednu ili više kopija izraza. Na primer, "" sparuje , itd. "[]+" sparuje , , , , i tako dalje.
|
{,} | Sparuje posljednji blok barem i ne više od puta. Na primer, "\{3,5}" sparuje aaa, aaaa ili aaaaa. Ova konstrukcija nije prisutna u nekim instancama regexa. |
Neke interpretacije regularnih izraza interpretiraju karakter različito ispred nekih metakaraktera. Na primer, i interpretiraju zagrade i vertikalne crte kojima ne prethodi kao metakaraktere, rezervišući verziju u kojima prethodi u svrhu značenja literalnih karaktera. Starije verzije programa nisu podržavale operator alternacije "|".
Primeri:
Budući da mnogi opsezi karaktera zavise o specifično odabranim jezičkim postavkama (npr., u nekim postavkama su slova uređena kao .... dok u nekim drugim kao ..), standard definiše neke razrede ili kategorije karaktera kao što je prikazano sledećom tablicom:
razred | slično izrazu | značenje |
---|---|---|
[::] | [-] | velika slova |
[::] | [-] | mala slova |
[::] | [--] | velika i mala slova |
[::] | [--0-9] | brojevi, velika i mala slova |
[::] | [0-9] | brojevi |
[::] | [0-9--] | heksadecimalni brojevi |
[::] | [.,!?:...] | interpunkcija (pravopisni znakovi) |
[::] | [ \t] | praznina (engl. ) i TAB |
[::] | [ \t\n\r\f\v] | prazninski karakteri (engl. ) |
[::] | kontrolni karakteri | |
[::] | [^ \t\n\r\f\v] | karakteri koji se mogu grafički ispisati |
[::] | [^\t\n\r\f\v] | karakteri koji se mogu grafički ispisati i karakter praznine |
Na primer: [[::]]] bi trebalo spariti samo velika slova i mala slova '' i ''.
Dogovorom je prihvaćeno da se razred [::] sastoji od razreda [::] uz pridodat karakter praznine (). Međutim, u -ovim regularnim izrazima [::] sparuje uniju razreda [::] i [::].
Dodatni razred koga ne definiše, a koga neki alati razumeju je [::], koji se obično definiše kao razred [::] sa pridodanim karakterom "_" (engl. ). 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č još razlikuje i razrede i - (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 dijagram koji prikazuje razrede pogledati
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
bi najizglednije koristio sledeći uzorak (\[\[.*\]\])
, koji izgleda ispravan (uočimo da je uglastoj zagradi prethodi 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:
Drugo, moderni alati za regularne izraze dozvoljavaju kvantifikatoru da bude specificiran kao nepohlepan, stavljanjem znaka upitnika ispred kvantifikatora:
(\[\[.*?\]\])
.
Moderniji "prošireni" regularni izrazi mogu često biti korišteni u modernim pomoćnim programima na juniksu koristeći komandnolinijsku zastavicu "-E".
Prošireni 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 - "+" sparuje , , i tako dalje |
? | Spari poslednji "blok" nula ili jednom - "?" sparuje ili |
| | Operator izbora (ili unije skupova): spari ili izraz pre ili izraz posle operatora - "abc|def" sparuje ili . |
Takođe, karakteri su odbačeni: \{...\} postaje {...} i \(...\) postaje (...). Primeri:
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:
-kompatibilni regularni izrazi (engl. ) je implementacija regularnih izraza u programskom jeziku [[]]. Imaju bogatiju i predvidljiviju sintaksu čak i od proširenih regexa. Primer njihove predvidljivosti je činjenica da \ uvijek citira (engl. ) nealfanumerički karakter. Primer nečega što je moguće specificirati u -u ali ne i u -u je odabir dela sparivanja za koji se želi da bude pohlepan ili ne. Na primer, u uzorku /.*/, poduzorak .* će spariti koliko god može, dok će uzorak /.*?/, .*? spariti što je moguće manje. Tako će u slučaju niske "" prvi uzorak spariti celu nisku, dok će drugi spariti samo "".
Zbog ovih razloga, mnogi drugi pomoćni programi i aplikacije su prigrlili sintaksu koja jako slična -ovoj - na primer , , , , , pa čak i -ov svi koriste sintaksu regularnih izraza sličnu -ovoj. Nisu sve "-kompatibilne" implementacije regularnih izraza identične, i mnoge implementiraju samo podskup -ovih osobina.
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 ili koji se zovu "kvadrati" (engl. ) 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. (autor -a) piše u Apokalipsi 5:
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 se može testirati regularnim izrazom veličine u vremenu (+2) ili (), 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 (2).
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 "(|)*" 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 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 su izrazi izvorno korišteni sa karakterima. Mnogi motori regularnih izraza danas mogu baratati i sa 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 .
Jedan od problema je koji je format podržan. Svi komandnolinijski motori regularnih izraza podržavaju , ali to varira kod biblioteka regularnih izraza. Neke očekuju , dok druge očekuju druga enkodiranja (, zastareli ili ).
Drugi problem je da li je puni 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 opsegom.
Treći problem je varijacija u načinu kako orijentisane konstrukcije mogu biti prošireni u . Na primer, u baziranim implementacijama, karakterni opsezi oblika [-] su valjani kad god su i kodne tačke (engl. ) u opsegu [0x00,0x7F] pri čemu je (x) <= (y). Prirodno proširenje takvih opsega karaktera bi jednostavno promenilo zahtev da krajnje tačke leže u opsegu [0x00,0x7] u zahtev da leže u opsegu [0,0x10]. Međutim, u praksi to nije toliko čest slučaj. Neke implementacije, poput onoga pomoćnog alata [[]], ne dozvoljavaju da opsezi karaktera pređu granice 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 blokove. Drugi motori, poput onoga u uređivaču , 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 karaktere. Druge zastavice deluju na sve karaktere. Neki motori imaju različite zastavice, jednu za drugu za . Takođe varira određivanje koji karakteri pripadaju razredima.
Drugi odgovor na je bilo uvođenje razreda karaktera za blokove i uopštena svojstva karaktera. U -u i u biblioteci , razredi oblika \{} sparuju karaktere u bloku i \{} sparuje komplement. Na primer, \{} sparuje bilo koji karakter u armenskom bloku. Slično, \{} sparuje bilo koji karakter sa opštim svojstvom karaktera i \{} komplement. Na primer, \{} sparuje sva velika slova.
Regularni izrazi su izrazito korisni u programima kompletiranja koda i bojenja sintakse u integrisanim razvojnim okruženjima. Na primer
"(||)\s*(\w+)\s+(\w+)\s*\("
bi spario funkcije u mnogim programskim jezicima.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.