Reguláris kifejezések - az elmélet I.

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.

A zárójeleket elhagyjuk azzal, hogy legerősebb a csillag, aztán a szorzás és végül az összeadás.

Í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?

stb; vagy, és ez a gyakoribb, egy rakás stringből akarjuk lefilterezni a nekünk tetszőket (van bennük email cím, szám, IP-cím stb), vagy még inkább csinálni akarunk valamit azokkal a sorokkal, amik teljesítenek valamit:

• 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

stb.

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.