Säännöllinen lauseke

Säännöllinen lauseke (engl. regular expression, lyhyesti regexp tai regex) on tietojenkäsittelyteoriassa lauseke, joka määrittelee säännöllisen kielennn. Kieli tarkoittaa tässä yhteydessä joukkoa merkkijonoja. Säännöllinen kieli on yksinkertaisin Noam Chomsky neliportaisessa kielioppien hierarkiassa. Säännölliset kielet voidaan tunnistaa äärellisillä automaateilla. Äärellinen automaatti on malli tietokoneelle, joka saa syötteen merkki kerrallaan, eikä voi kelata syötettä edestakaisin. Äärelliset automaatit ovat silti hyödyllisiä monissa asioissa, kuten tekstialkioiden tunnistuksessa tai tietoliikenteessä tila-automaateissa. Säännöllisten lausekkeiden tärkein käyttökohde on tarkastella, kuuluuko jokin merkkijono lausekkeen määrittämään kieleen. Useat ohjelmointikielet ja ohjelmat sisältävät mahdollisuuden tähän.

Määrittely

Kieleen kuuluu aina aakkosto, jota merkitään Σ:lla (Sigma). Aakkosto on joukko-opin alkioiden joukko. Yleisessä tapauksessä se voi olla ASCII tai Unicode-merkistö. Kaikkia Σ:sta muodostettavia merkkijonoja merkitään Σ*:llä. Tyhjää merkkijonoa merkitään ε:lla (epsilon).

Esimerkkejä:

{a}* = { ε, 'a', 'aa', 'aaa', 'aaaa', ... }
{0, 1}* = { ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, ... }

Kieli on mikä tahansa Σ*:n osajoukko. Kieli on äärellinen, jos siihen kuuluu vain äärellinen määrä merkkijonoja. Äärellisen kielen voi määritellä luettelemalla kaikki siihen kuuluvat merkkijonot, äärettömälle kielelle tämä ei onnistu. Säännöllinen lauseke on eräs yksinkertainen tapa määritellä mahdollisesti ääretön määrä merkkijonoja.

Määritellään operaattorit:

*   toisto, edeltävä symboli 0-n kertaa
|   tai, jompikumpi symboli

Esimerkkejä, kirjaimet ovat metakielen symboleita, jotka vastaavat yksittäisiä kirjaimia. a = 'a', jne.

a  = { a }
ab = { ab }
a* = { ε, a, aa, aaa, ... } eli a* vastaa tyhjää
     merkkijonoa ja merkkijonoja 'a', 'aa', 'aaa', jne.
a|b = { a, b } merkkijono 'a' tai 'b'
ab|cd* = { ab, c, cd, cdd, cddd, ... }

Lisäksi määritellään lyhennysmerkinnät:

an   symboli toistettuna n kertaa.
a+   symboli 1-n kertaa.

Nämä eivät ole säännöllisiä lausekkeita, vain lyhenteitä.

Esimerkiksi:

a4 = aaaa
(ab)2 = abab
anbn laiton, n ei voi olla parametri.

Näillä merkinnöillä voidaan ilmaista säännöllinen kieli, johon kuuluu ääretön määrä merkkijonoja. Deterministinen äärellinen automaatti pystyy tunnistamaan säännöllisten lausekkeiden määrittelemät kielet. Eri ohjelmien ja ohjelmointikielten tuntemat lausekkeet eroavat toisistaan, klassinen Unix grep on toteutettu deterministisellä äärellisellä automaatilla ja sen tuntema kieli on lähes tämä laajennettuna muutamilla operaattoreilla. Useiden ohjelmien tuntema kieli ei ole enää säännöllinen, mutta samankaltaisuuden vuoksi näistä lausekkeistä käytetään nimeä laajennetut säännölliset lausekkeet.

Sovelluksia

Unix-työkaluohjelmaa grep käytetään merkkijonojen etsimiseen tiedostoista hyödyntäen säännöllisiä lausekkeita.

Katso myös

• Perl
• Shell-skriptit
• sed
• Johdanto täsmäysmerkintöihin