Ismétlés gyanánt, ábécén egy véges, nemüres halmazt értettünk, amit Σ-val fogok jelölni. Egy szó, avagy string (az Σ ábécé fölött) egy véges jelsorozat, azaz egy w = a1a2...an alakú sorozat, ahol minden ai Σ-beli. Ha n=0, azaz 0-betűs a string, az az üres szó, aminek jele az ε lesz (van, ahol neki λ a jele).
Az összes Σ fölötti szó halmaza pedig Σ*. Egy nyelv (Σ fölött persze) pedig szavak egy tetszőleges halmaza.
A gyakorlatban persze nem feltétlen "betűk" vannak az ábécében. Ha például egy rendszer viselkedését akarod modellezni, akkor egy betű lehet pl. egy user akció vagy egy utasítás, egyéb event -- ekkor egy szó egy program végrehajtásának historyja lesz. Ezek közül a szavak közül lesznek, amik "helyes" programviselkedéshez tartoznak, és lesznek, amik nem. Ha azokat a szavakat rendezzük be egy halmazba, akik a programunk "elvárt" viselkedésének felelnek meg, akkor egy nyelvvel specifikáltuk a programunkat. Ha pedig egy programmal a forráskódunkból tudunk csinálni egy nyelvet, hogy hogyan viselkedhet valójában, akkor pedig ezt a nyelvvel össze tudjuk vetni a specifikáció nyelvével, hogy vajon tényleg a kívánt specifikációt implementáltuk-e vagy sem.
Most nem ezt fogjuk csinálni, de ilyesmi történik a "Hardware- és software-rendszerek verifikációja" c. kurzuson.
Most az ábécénkben tényleg karakterek lesznek, konkrétan nyilván vagy az ASCII, vagy az Unicode tábla lesz a Σ.
Egy nyelv megadása több módon történhet, az egyik ilyen a reguláris kifejezéssel történő megadás. Mik is voltak ezek?
- minden Σ-beli betű reguláris kifejezés. Az a betű az {a} nyelvet jelöli.
- az ε is reguláris kifejezés, ami pedig az {ε} nyelvet jelöli.
- az ∅ is reguláris kifejezés, ami pedig az üres nyelvet jelöli.
- Ha R reguláris kifejezés, akkor (R*) is reguláris kifejezés. Az R* nyelvben az összes olyan szó szerepel, mely előáll néhány R-beli szó konkatenációjaként, azaz egymás-után-írásaként. A "néhány"-ba belefér a nulla is (!). Formálisan, R* = { w1w2...wn: n ≥ 0, w1,...,wn ∈ R }.
- Ha R1 és R2 reguláris kifejezés, akkor (R1+R2) is és (R1R2) is reguláris kifejezés. Előbbi az R1 ∪ R2 nyelvet jelöli, utóbbi pedig az {uv: u ∈ R1, v ∈ R2} nyelvet.
- Más reguláris kifejezés nincs.
Így például az (a(b+aa))* kifejezés mit jelöl? Egyrészt aa az {aa} nyelvet, b+aa az {b,aa} nyelvet, a(b+aa) az {ab,aaa} nyelvet és végül a csillaggal együtt az {ε, ab, aaa, abaaa, abab, aaaab, aaaaaa, ababab, ...} nyelvet. Ezt úgy is mondjuk, hogy ezek a szavak illeszkednek a reguláris kifejezésre. A bb szó például nem illeszkedik rá.
A legtöbb normális programozási környezetben van valami standard(nak számító) könyvtár, ami reguláris kifejezés illesztést végezni. Így például
- Perlben ez egy alap nyelvi operátor, a =~;
- Javában a java.util.regex csomag Pattern és Matcher osztályai;
- PHP-ban a preg_match függvény;
- C++-ban (C++11 óta! végrevégre!) a <regex> header;
- .NETben a System.Text.RegularExpressions.Regex,
meg persze ott az egrep is.
bizonyára van Haskell, Prolog and such implementáció, de maradnék inkább most a mainstream nyelveknél. A Perlt csak érdekességképpen soroltam fel, hogy lássuk, ott bizony alap nyelvi komponens :-)
Hogy mikor használunk ilyet például? Ha mondjuk ellenőrizni akarjuk, hogy az input string
- valid e-mail cím-e?
- elég komplex password-e?
- (lebegőpontos) szám-e?
- IP-cím-e?
- valid URI-e?
- human-readable formátumra akarjuk cserélni a file összes legalább négy hosszú számát (hármasával tizedespontot szúrva bele, a kis helyiértékek felől);
- le akarjuk killelni az összes "kb ilyen-meg-ilyen" nevű processt;
- ki akarjuk listázni a szóismétlést tartalmazó sorokat
- esetleg automatikusan törölni az ismétlődő szavakat
- esetleg case-insensitive módon
- hand history file-ból le akarjuk filterezni azokat a leosztásokat, ahol kézbe osztott párunk van
Nyilván ezeket a taskokat meg lehet mindig oldani úgy is, hogy újra- és újra megírjuk a stringfeldolgozó függvényünket, de ez nem túl produktív. Ha kicsit is biztosabban kezeljük a regexeket, akkor egy egysoros regex, plusz a környezet által biztosított regex motor sokat segít a stringfeldolgozásban, ill. stringből infó kinyerésben.
Aki otthon van az elméletben Formális nyelvekből, az sejti ezen a ponton, hogy a "szóismétlést tartalmazó" feladat miért piros.. (egyébként a kézbepárokat se egy tizenhárom ifes regex oldja majd meg ;) ) erről majd később.
Legközelebb megnézzük, hogy hogyan kéne regexet illeszteniük a motoroknak, ehhez képest hogyan csinálják valójában, mennyire tér el az elméleti regex a gyakorlati regextől és melyik nyelv mennyire lassan illeszti őket.
