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. Ohjelmoinnissa tämä voi esimerkiksi tarkoittaa sitä, että käyttäjän antama syöte voidaan tarkastaa tai muotoilla toisenlaiseksi. Esimerkiksi turvallisten salasanojen luominen tarkastetaan näin. Säännöllinen lauseke voi esimerkiksi tarkastaa onko salasanassa: tarpeeksi merkkejä, ainakin 2 isoa kirjainta ja 1 erikoismerkki. Säännölliset lausekkeet ovat myös yleisiä verkko-osoitteiden muotoilussa. Kirjoitettu teksi saatetaan muotoilla automaattisesti linkiksi, ilman että käyttäjän tarvitsee tehdä sitä.

Esimerkki linkin muotoilusta PHP:ssa:

 $teksti = "Vain tekstiä, http://www.wikipedia.org, muunna minut linkiksi. Älä muotoile minua: www.esimerkki";
 $teksti = preg_replace('#http://[a-z0-9._/-]+#i', '<a href="$0">$0</a>', $teksti);

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ä]