Regulaaravaldis

sümbolitest koosnev otsingumuster

Regulaaravaldis (ingl. regular expression, regex või regexp[1]) on teoreetilises informaatikas märkidest koosnev otsingumuster. Tavaliselt kasutatakse sellist mustrit sõnedes otsingu- ja/või asendusoperatsioonideks.

Tulemused tekstis järgneva mustri otsimisel
(?<=\.) {2,}(?=[A-Z])
Sobitatakse vähemalt kaks tühikut, kuid ainult siis kui need paiknevad punkti järel ja suure tähe ees

Regulaaravaldisi kasutatakse otsingumootorites, tekstiredaktorite otsimis- ja asendamisdialoogides, tekstitöötlustööriistades nagu sed ja AWK ning leksilises analüüsis. Regulaaravaldiste tugi on enamikus programmeerimiskeeltes sisseehitatud või saadaval teekidega. Regulaaravaldiste kirjutamiseks on erinevaid süntakse, näiteks POSIX standard ja laialdaselt levinud Perli süntaks.

Mustrid

muuda

Regulaaravaldistega kirjeldatakse otsingumustreid. Selleks kasutatavad sümbolid on kas metamärgid (erilise tähendusega) või tavalised sümbolid (otsese tähendusega). Näiteks regulaaravaldises a. tähistab a tähelist vastavust 'a' ning . metamärki, mis sobitub kõikide sümbolitega välja arvatud reavahetus. Seega sobituks see regulaaravaldis näiteks sõnedega a või ax või a0. Mustrisobituse vastete võimalikku täpsust saabki reguleerida metamärkide kasutusega. Näieks on . väga üldine muster, [a-z] (sobivad kõik tähed a kuni z) on vähem üldisem ning a on väga täpne muster (sobib vaid a). Metamärkide süntaks on loodud lihtsaks ja paindlikuks tekstitöötluse automatiseerimiseks kujul, mida on lihtne tavalisel ASCII klaviatuuril kirjutada.

Väga lihtne näide sellisest regulaaravaldisest oleks leida tekstiredaktoris sama sõna mitme erineva kirjapildiga. Näiteks Helsin[gk]i sobitub nii sõnaga "Helsingi" kui ka sõnaga "Helsinki".

Sümbol võimalike hulgast

muuda

Kasutades kandilisi sulge ([ ja ]) saab defineerida sümbolivaliku. Nende vahel olev avaldis sobitab täpselt ühte sümbolit võimalikest. Lisaks saab selle avaldise alguses kasutada tsirkumfleksi (^) tähtedevaliku välistamiseks ning kahe tähe vahel kasutada sidekriipsu (-) tähtede vahemiku määramiseks ASCII järgi. Näiteks [a-g] on samaväärne kui [abcdefg].

Näiteid sümbolivaliku kasutamisest
Avaldis Selgitus
[egh] üks tähtedest e, g või h
[0-6] üks number 0 kuni 6 (0, 1, 2, 3, 4, 5 või 6)
[A-Za-z0-9] üks ladina täht või number
[^a] üks sümbol, mis ei ole a (^ avaldise alguses käitub eitusena)

Defineeritud sümbolivalikud

muuda

Samuti toetab osa regulaaravaldise mootoritest järgnevaid märgivaliku lühivorme, mida saab kirjeldada ka kandiliste sulgude ([ ja ]) vahel olevate avaldistega.

Avaldis Ingliskeelne vaste Selgitus
. (peaaegu) ükskõik milline sümbol (tavaliselt reavahetusi ei arvestata)
\d digit üks number ([0-9] ning vahel ka ülejäänud numbrilised sümbolid Unicode'is)
\D no digit sümbol, mis ei ole number ([^\d])
\w word character üks täht, number või alakriips ([a-zA-Z_0-9] ning vahel ka ülejäänud tähed, nt täpitähed)
\W no word character üks sümbol, mis ei ole täht, number ega alakriips ([^\w])
\s whitespace üks tavaline tühik ning ka talitusmärgid \f, \n, \r, \t ja \v
\S no whitespace sümbol, mis ei ole tühik ([^\s])

Kvantifikaatorid

muuda

Kvantifikaatorid lubavad eelneval avaldisel korduda.

Avaldis Selgitus
? Eelnev avaldise osa kas 0 või 1 korda. (Samaväärne kui {0,1})
+ Eelnev avaldise osa vähemalt 1 kord, kuid lubatud ka mitu. (Samaväärne kui {1,})
* Eelnev avaldise osa ükskõik kui mitu korda, võib ka puududa. (Samaväärne kui {0,})
{n} Eelnev avaldise osa täpselt n korda. (Samaväärne kui {n,n})
{min,} Eelnev avaldise osa vähemalt min korda.
{min,max} Eelnev avaldise osa min kuni max korda, mõlemad kaasaarvatud.
{0,max} Eelnev avaldise osa kuni max korda, kaasaarvatud.

Need kvantifikaatorid viitavad eelnevale regulaaravaldise osale, kuid mitte tingimata nende leitud vastele. Näiteks a+ sobitub nii sõnega a kui sõnega aaaa, aga [0-9]+ korral ei pea korduma sama number, vaid need võivad olla ka erinevad, näiteks sobib 0741852. Veel näiteid:

  • [ab]+ korral sobivad a, b, aa, bbbaab jne
  • [0-9]{2,5} korral sobivad kõik kahe, kolme, nelja või viienumbrilised sõned, näiteks 42 või 12345, kuid mitte sõned 0, 1.1 ega a1b2.

Ajalugu

muuda

Regulaaravaldised pärinevad aastast 1951, mil matemaatik Stephen Cole Kleene kirjeldas regulaarkeeli ning kasutas selleks matemaatilist kirjapilti, mida ta kutsus regulaarhulkadeks.[2] Üks varasemaid mustrisobituse implementatsioone realiseeriti SNOBOL keeles, mis kasutas regulaaravaldiste asemel oma mustrisobituskonstrukte.

Regulaaravaldised muutusid eriti populaarseks 1968. aastast kahes kasutusvaldkonnas: mustrisobitus tekstiredaktorites[3] ja leksiline analüüs kompilaatorites[4]. Üks esimesi regulaaravaldiste realisatsioone oli Ken Thompsoni QED redaktorisse lisatud tekstifailide mustriotsing, mis kasutas parema jõudluse eesmärgil sünkroonkompilaatorit.[3][5][6][7] Hiljem lisas ta selle tööriista ka Unixi redaktorisse ed, millest inspireerituna loodi ka tänapäeval populaarne otsingutööriist grep. Samal ajal kui Thompson arendas QEDi, implementeerisid teadlased, sh Douglas T. Ross regulaaravaldistel põhinevat leksilise analüüsi tööriista, mida kasutatakse kompilaatoriidisainis.[4]

1970. aastatel kasutasid mitmed Unix programmid (nt vi, lex, sed, AWK ja expr) regulaaravaldiste variatsioone.[7] Ajapikku võeti kasutusele järjest rohkem erinevaid avaldisi. Need algsed mustrite kujud standardiseeriti POSIX.2 standardiga 1992. aastal.

1980. aastatel tõusid Perlis esile keerulisemad regulaaravaldised, mis tulenesid algselt Henry Spenceri loodud regulaaravaldiste teegist. Spenceri hilisemat parema jõudluse ja Unicode toega teeki Tcl-ile kasutatakse muuhulgas ka PostgreSQLis.[8][9]

1997. aastast on Philip Hazel arendanud PCRE teeki C-keelele, mis üritab matkida Perli regulaaravaldiste funktsionaalsust. Seda kasutatakse paljudes tänapäevastes tööriistades, muuhulgas ka PHPs ja Apache HTTP Serveris.

Tänapäeval on regulaaravaldised laialdaselt toetatud programmeerimiskeeltes, tekstitöötlusprogrammides ja -redaktorites ning mujal. Regulaaravaldised on paljude programmeerimiskeelte standardteegis, näiteks Javas ja Pythonis, ning osal keeltest süntaksis, näiteks Perlis ja ECMAScriptis. Regulaaravaldiste funktsionaalsuse implementatsioone kutsutakse tihti regulaaravaldise mootoriks ning mitmeid teeke saab mitmeotstarbeliselt kasutada.

Viited

muuda
  1. What Regular Expressions Are Exactly - Terminology
  2. Kleene 1951.
  3. 3,0 3,1 Thompson 1968.
  4. 4,0 4,1 Johnson jt 1968.
  5. Kernighan, Brian. "A Regular Expressions Matcher". Beautiful Code. O'Reilly Media. Lk 1–2. ISBN 978-0-596-51004-6. Vaadatud 15.05.2013.
  6. Ritchie, Dennis M. "An incomplete history of the QED Text Editor". Originaali arhiivikoopia seisuga 21.02.1999. Vaadatud 9.10.2013.
  7. 7,0 7,1 Aho ja Ullman 1992, 10.11 Bibliographic Notes for Chapter 10, p. 589.
  8. "New Regular Expression Features in Tcl 8.1". Vaadatud 11.10.2013.
  9. "PostgreSQL 9.3.1 Documentation: 9.7. Pattern Matching". Vaadatud 12.10.2013.