Säännöllinen lauseke

Wikipedia
Loikkaa: valikkoon, hakuun

Säännöllinen lauseke (engl. regular expression, lyhyesti regexp tai regex) on tietojenkäsittelyteoriassa lauseke, joka määrittelee säännöllisen kielen. Kieli tarkoittaa tässä yhteydessä joukkoa merkkijonoja. Säännöllinen kieli on yksinkertaisin Noam Chomskyn 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[muokkaa | muokkaa wikitekstiä]

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

On huomattava, että yleensä käytännöllisissä ohjelmointikielissä ei käytetä merkkejä Σ tai ε. Näitä erikoismerkkejä käytetään tässä säännöllisten lausekkeiden teoreettisessa tarkastelussa (alla), mutta ohjelmien lähdekoodissa on tavallisesti erilainen, tavallisiin ASCII-merkkeihin perustuva syntaksi säännöllisten lausekkeiden esittämiseen.

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ä lausekkeista käytetään nimeä laajennetut säännölliset lausekkeet.

Sovelluksia[muokkaa | muokkaa wikitekstiä]

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

PHP-kielessä on funktioita säännöllisten lausekkeiden käyttöä varten (mm. preg_match ja preg_replace).

Katso myös[muokkaa | muokkaa wikitekstiä]