Reguláris kifejezés

A Wikipédiából, a szabad lexikonból.

Ezen szócikk összedolgozandó a(z) Szabályos kifejezések szócikkel,
azután az egyik lap törlendő.

A reguláris kifejezés (az angol regular expression kifejezésből származó rövidítéssel regexp vagy regex) az informatikában szövegek csoportjainak tömör leírására szolgáló módszer. Legegyszerűbb formájában a reguláris kifejezés olyan szöveg, amelyben egyes betűk helyett speciális jelek állnak; a reguláris kifejezés által jellemzett szövegek ezeken a helyeken többfélék is lehetnek. Például a .bc regexp azokat a szavakat írja le, amelyek három betűből állnak, a második betűjük b és a harmadik c (az első bármi lehet). Az ab[xyz] regexp azokat, amelyek három betűből állnak, az első a, a második b, a harmadik pedig vagy x, vagy y, vagy z. A bonyolultabb reguláris kifejezések ennél lényegesen többre is képesek.

A reguláris kifejezéseket elsősorban programnyelvekben és szövegszerkesztőkben használják különféle szövegfeldolgozási feladatok elvégzésére.

[szerkesztés] Alapok

Egy reguláris kifejezés, vagy ahogy gyakran hívják, egy minta, egy olyan speciális karakterlánc, ami karakterláncok egy halmazát írja le. Azt mondjuk, hogy egy minta illeszkedik egy karakterláncra, ha az az általa leírt halmazba tartozik.

A reguláris kifejezések szintaxisára számos különböző szabvány van, amelyek azonban főbb vonásaikban többnyire megegyeznek. Néhány azok közül az építőkövek közül, amelyek szinte minden szabványban megtalálhatóak (a példákban a POSIX szabvány szerinti jelöléssel, de a legtöbb szabvány ugyanezeket a jelöléseket használja):

karakterosztály
A karakterosztály több karaktert tartalmaz, amelyek közül bármelyik állhat a szöveg megfelelő pozícióján. Például a la[jp]os minta illeszkedik a lajos és a lapos szavakra is, de a lakos-ra nem. A karakterosztályokat általában az összes elemük felsorolásánál rövidebben is meg lehet adni, például az [a-f] karakterosztály az a, b, c, d, e, f karaktereket tartalmazza.
„wildcard” elem
Azt jelzi, hogy a szövegben a megfelelő pozíción bármi állhat. Például a ke.et minta illeszkedik a kelet, kenet és kenet szavakra is.
előfordulások számát jelző elemek
Azt jelzik, hogy az előttük álló karakter hányszor fordulhat elő. A leggyakoribb ilyen elemek a + (egy vagy több előfordulás), a * (nulla vagy több előfordulás) és a ? (nulla vagy egy előfordulás). Például az 12+3 minta illeszkedik az összes olyan számra, aminek az első számjegye 1, az utolsó 3, és közöttük csak kettesek vannak. Az 12*3 hasonló hozzá, de a 13-ra is illeszkedik. Az 12?3 minta illeszkedik a 13-ra és a 123-ra, de az 1223-ra már nem.
Ezek az elemek kombinálhatóak a wildcarddal, így például a .? egy tetszőleges karaktert, a .* pedig bármit (egy tetszőleges karakterláncot, vagy az üres karakterláncot) jelölhet.
A fejlettebb szabványokban ennél pontosabban is kontrollálható az előfordulások száma, például az a{5} öt darab a karaktert, a b{6,8} 6, 7 vagy 8 b betűt jelent.
alternatívák
Az alternatívák több mintából állnak; minden olyan szövegre illeszkednek, amikre ezen minták legalább egyike. Például az egy|kettő minta illeszkedik az egy-re és a kettő-re is.
csoportosítás
A csoportosítás segítségével változtatni lehet azon, hogy egy-egy speciális elem mire vonatkozzon. Például a kormo?s minta a kormos és a korms karakterláncokra illeszkedik, ezzel szemben a ko(rmo)?s a korms-ra nem, de a kormos-ra és a kos-ra igen. Hasonlóan, a száz(tizen|huszon)egy illeszkedik a száztizenegy-re és a százhuszonegy-re, de a százegy-re vagy a huszonegy-re nem.

Az építőelemekből a matematikai műveletekhez hasonlóan bonyolult kifejezések állíthatóak össze; például az [A-Z]{3}-[0-9]{3} minta a magyar autók rendszámát írja le. Ugyanazt a karakterlánc-halmazt általában többféle mintával is le lehet írni; például a fal|fel és a f[ae]l egyaránt a {fal, fel} halmazt írja le.

[szerkesztés] A reguláris kifejezések története

A reguláris kifejezésekhez hasonló konstrukciók a számítógéptudományban, azon belül is az automaták és a formális nyelvek elméletében már régóta léteznek. Az 1940-es években Warren McCulloch és Walter Pitts úgy próbálták modellezni az idegrendszert, hogy a neuronokat egyszerű automatákként kezelték. Stephen Kleene egy reguláris halmazoknak nevezett matematikai jelölésrendszert alkotott a modellük leírására. Ken Thompson beépítette ezt a jelölést a QED szövegszerkesztőbe, majd a Unix-os ed-be, ahonnan gyorsan elterjedt a Unix olyan különféle, szövegekkel dolgozó segédprogramjaiban, mint például az expr, az awk, az Emacs, a vi vagy a lex.

A 80-as évek végén Henry Spencer megírta a korábbiaknál lényegesen többre képes regex reguláris kifejezés könyvtárat, amit átvett a Perl és a Tcl, majd a Philip Hazel készítette PCRE könyvtáron keresztül számos más szoftver és programozási nyelv, például az Apache és a PHP.

[szerkesztés] Matematikai háttér

Egy reguláris kifejezés karakterláncok halmazait jelölő konstansokból és ezeken a halmazokon értelmezett műveletekből áll. Legyen σ egy véges ábécé, és definiáljuk a következő konstansokat:

  • üres halmaz: \empty jelölje az üres halmazt;
  • üres sztring: ε jelölje az {ε} halmazt;
  • karakterkonstans: minden a \in \sigma-ra a jelölje a {a} halmazt;

és a következő műveleteket:

  • konkatenáció: RS := \{\alpha\beta|\alpha \in R \and \beta \in S\};
  • elágazás: R|S := R \cup S (a függőleges vonal helyett néha a +, \vee vagy \cup jelölést alkalmazzák);
  • Kleene-csillag: R^* = \bigcup_{i \in \mathbb{N}} R^i, azaz R * azoknak a sztringeknek a halmaza, amelyek előállnak nulla vagy több R-beli sztring konkatenációjaként. (Más szóval az a legszűkebb R-t tartalmazó halmaz, ami tartalmazza ε-t, és zárt a konkatenációra.

Ezek a konstansok és műveletek egy Kleene-algebrát formálnak. A műveletek között a Kleene-csillagnak a legnagyobb a precedenciája, és az elágazásnak a legkisebb, így például ab * c | de = (a(b * )c) | (de).

A matematikai leírásban a könnyebb kezelhetőség kedvéért a műveletek száma minimális, de a többi szokásos műveletet ki lehet fejezni a fentiekkel, például a + = aa * és a? = (a | ε).

Más nyelveken