Ugrás a tartalomhoz

Reguláris kifejezés

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából
(Reguláris kifejezések szócikkből átirányítva)

A reguláris kifejezés (rövidítve: regexp vagy regex az angol regular expression után) egy olyan, bizonyos szintaktikai szabályok szerint leírt string, amivel meghatározható stringek egy halmaza.

Az ilyen kifejezés valamilyen minta szerinti szöveg keresésére, cseréjére, illetve a szöveges adatok ellenőrzésére használható.

Például egy érvényes (nem feltétlenül még élő személyt jelölő) személyi szám biztosan a következő elemekből áll:

  • egy 1 és 8 közötti számjegy;
  • egy szóköz;
  • 19 vagy 20 vagy 21 és még két számjegy (év);
  • utána
    • egy 0 és egy 1-9 közötti számjegy vagy
    • egy 1 és egy 0-2 közötti számjegy (hónap);
  • utána
    • egy 0-2 közötti számjegy és egy 0-9 közötti számjegy vagy
    • egy 3, amit 0 vagy 1 követ (nap)
  • egy szóköz
  • és még négy számjegy.

(Esetleg a szóközök helyén kötőjel is állhat.)

A programnak megmondhatjuk, hogy keresse meg az összes ilyen minta szerinti karaktersorozatot, majd pedig a kötőjeleket cserélje szóközre, hogy egységes legyen (vagy a kötőjeleket és a szóközöket is nem törhető szóközre, hogy egy weblapon egyben maradjanak). Egy másik példa: egy érvényes, dr. és más előtagok nélküli magyar személynév a magyar ábécé betűiből, szóközökből és kötőjelekből állhat a következő megszorításokkal: kötőjel és szóköz nem állhat az elején és a végén, sem másik kötőjel vagy szóköz után, csak két betű között; az első betű, valamint a szóközök és kötőjelek utáni betűk nagyok, a többi pedig kicsi; végül legalább egy szóköznek mindenképpen lennie kell. Ez a két példa nem garantálja, hogy amit találtunk, az biztosan érvényes személyi szám vagy magyar név, csak azt, hogy ily módon az összeset megtaláltuk. De ha olyan karaktersorozatot keresünk, amelyik 1 vagy 2 vagy 3 I (nagy i betű) után egy pontot, egy szóközt és az András vagy az Endre szavakat tartalmazza, akkor biztosak lehetünk benne, hogy egy valódi magyar király nevét találtuk meg (a római I a keresés szempontjából betűnek számít, és még arra is figyelnünk kell, hogy a sorozatot megelőző karakter bármi más lehet, csak még egy I nem, különben a reguláris kifejezésünk a „IIII. András” stringet is megtalálná, ami hiba lenne). Ha ugyanezt elfogadjuk nulla vagy egynél több szóközzel is, de ezeket egyre cseréljük, akkor hibás alakokat is találhatunk, és egy gyakori gépelési hibát javíthatunk ki. Ha ragozott alakokat is keresni akarunk, akkor figyelnünk kell rá, hogy az Endréből é betűs alak lehet, míg az András szótő változatlan marad.

A reguláris kifejezéseket sok szövegszerkesztő, illetve segédprogram használja, főleg szövegek keresésekor vagy szövegek bizonyos minták szerinti kezelésekor.

A reguláris kifejezéseket a jelsorozatokkal, stringekkel való műveleteknél több programozási nyelv is használja, illetve támogatja. Például a Perl, a Python és a Tcl is rendelkezik direkt reguláris kifejezések elemzésére szolgáló szintaktikai elemzővel. A különböző Unix-disztribúciókban lévő segédprogramok jelentős része (beleértve a sed szövegszerkesztőt és a grep szűrőt) támogatta először a reguláris kifejezések használatát.

Alapkoncepció

[szerkesztés]

A gyakran mintának nevezett reguláris kifejezés a jelsorozatok, stringek egy halmazát határozza meg. A minták használatával tömören megadhatók halmazok leírásai anélkül, hogy az összes elemüket fel kellene sorolni. Tegyük fel például, hogy egy halmaz a következő jelsorozatokat tartalmazza: Handel, Händel, és Haendel. Leírhatók-e a halmaz elemei a H(ä|ae?)ndel mintával (más szavakkal: mondhatjuk-e, hogy a mintához mindhárom string illeszkedik)? Amint az a későbbiekből kiderül, általában azonos halmazok különböző mintákkal is leírhatóak.

A legtöbb formalizálásnál a következő operátorok használatával konstruálhatók meg a megfelelő reguláris kifejezések.

választás
A függőleges vonal (|) a lehetséges alternatívákat választja el. Például a „kap|kép” minta alternatívákhoz illeszkedik a kap vagy a kép jelsorozat is.
csoportosítás
A zárójelek az operátorok hatásköre elsőbbségének a meghatározására szolgálnak. Például, a kap|kép és k(a|é)p minták különbözőek, de ugyanazok a jelsorozatok illeszkednek hozzájuk (kap és kép).
mennyiségjelzés
A mennyiségjelző egy karakter vagy csoport után azt határozza meg, hogy hányszor fordulhat elő a megelőző kifejezés. A leggyakoribb mennyiségjelzők a ?, a * és a +:
?
A kérdőjel jelzi, hogy a megelőző kifejezés csak 0 vagy 1 esetben fordulhat elő. Például, a colou?r minta illeszkedik a color és a colour jelsorozatok közül bármelyikre.
*
A csillag jelzi, hogy a megelőző kifejezés akárhány esetben fordulhat elő (beleértve a nullát is). Például, go*gle minta illeszkedik a ggle-e, a gogle-re, a google-re stb. Nagyon fontos, hogy a * értelmezése alapvetően eltér a Windows-beli megszokott értelmezéstől!
+
A plusz karakter jelzi, hogy a megelőző kifejezés legalább 1 esetben fordulhat elő. Például a go+gle mintához illeszkedik a gogle, google stb. (de a ggle nem!).
{n}
A kapcsoszárójel jelzi, hogy a megelőző kifejezés pontosan n esetben fordulhat elő.

A fenti konstrukciók egymással kombinálva a különféle formák komplex ellenőrzését teszik lehetővé.

Tehát a H(ae?|ä)ndel és a H(a|ae|ä)ndel érvényes, szabályos minták, és ezen túlmenően, mindkettő illeszkedik a előző példaként megadott jelsorozatokra.

Másik példa a előzőekben leírt operátorok kínálta lehetőségek kihasználásra:

Legyen a minta a következő:
(nagy ?)*(apa|anya)

A minta illeszkedik a következő stringek közül bármelyikre: apa, anya, nagy apa, nagy anya, nagy nagy apa, nagy nagy anya, nagyapa, nagyanya, nagy nagyapa, nagy nagyanya, nagy nagy nagyapa, nagy nagy nagyanya és így tovább.

A reguláris kifejezések pontos szintaxisa a változó eszközök és alkalmazások miatt egységesen nem adható meg; a további részleteket lásd a Szintaxis résznél.

Története

[szerkesztés]

A reguláris kifejezések először az automata elmélet és formális nyelvek elmélete (mindkettő része a elméleti számítógép-tudománynak) kapcsán merültek fel. Ezek az elméletek a számítógép működésének modellezésénél (automaták), illetve ezek osztályozásánál és leírásánál formális nyelvek voltak fontosak. Az 1940-es években Warren McCulloch és Walter Pitts az idegrendszer neuronokkal történő modellezésének leírásához használt egy kicsiny, egyszerű automatát. A matematikus Stephen Kleene ugyanezt a modellt matematikai jelölésekkel, az úgynevezett reguláris halmazok alkalmazásával írta le. Ken Thompson ezt a jelölési módot építette be az általa készített QED szövegszerkesztő programba. Ez került a Unix szerkesztőjébe (ed) is, ami a reguláris kifejezéseket használó grep elkészüléséhez vezetett. Azóta a reguláris kifejezések széles körben elterjedtek a Unix és a Unix-szerű rendszerek segédprogramjainál, amilyenek például az expr, az awk, az Emacs, a vi, a lex és a Perl.

A Perl és a Tcl reguláris kifejezései a Henry Spencer által írt regexből származnak. Philip Hazel kifejleszti a pcre (Perl Compatible Regular Expressions) alkalmazást, amely képes szimulálni a Perl reguláris kifejezési funkcionalitásait, és több modern eszközben is megjelenik, többek között a PHP-ben, és az Apache-ban.

A későbbiekben felsorolt nagyszámú eszköz, könyvtár stb. bizonyítja, hogy a reguláris kifejezések ma egyre nagyobb teret nyernek, és egyre több olyan eszköz jelenik meg, amelyeket direkt ezek kezelésére fejlesztettek.

A reguláris kifejezések számítógépes nyelvekbe integrálása még nagyon kevéssé elterjedt, bár a Perl reguláriskifejezés-integrációja a legjobbak között van, de a jövőben a fejlesztésnél még erőfeszítések szükségesek (angol nyelven Perl6) az integráció növeléséhez. Ide tartozik a Apocalypse 5 projekt is.

Kapcsolat a formális nyelvek elméletével

[szerkesztés]

A reguláris kifejezések konstansokból és operátorokból épülnek fel, stringek egy bizonyos halmazát jelölik, illetve műveleteket definiálnak a halmaz elemeire, vagy az elemei között.

Adott véges Σ ábécé a következő konstansokat

  • (üres halmaz) Ø halmaz jelölése Ø
  • (üres string) ε halmaz jelölése {ε}
  • (literál karakter) a Σ része, halmaz jelölése {a}

és a következő operátorokat definiálja:

  • (konkatenáció) RS halmaz jelölése { αβ | α R-ben és β S-ben }. Például {„ab”, „c”}{„d”, „ef”} = {„abd”, „abef”, „cd”, „cef”}.
  • (választás) R|S jelöli a halmazok R és S unióját.
  • (Kleene csillag) R* jelöli azt az R legkisebb részhalmazát, amely tartalmazza ε-t és a stringjeinek konkatenációit. Ez a konkatenált stringek halmaza úgy áll elő, hogy többször vagy egyszer sem konkatenáljuk az R halmazban lévő stringeket. Például {„ab”, „c”}* = {ε, „ab”, „c”, „abab”, „abc”, „cab”, „cc”, „ababab”, … }.

Több leírásban a , , vagy szimbólumokat használják a választás jelölésére a függőleges vonal helyett.

A felesleges zárójelezések elkerülésére a műveletek eltérő prioritásúak: megegyezés szerint a Kleene csillag nagyobb prioritású, mint a konkatenáció és a konkatenáció nagyobb prioritású, mint az unió, így elhagyhatók a zárójelek, amennyiben az nem okoz kétértelműséget. Például, az (ab)c abc-nek is írható és az a|(b(c*))-t írhatjuk mint a|bc*.

Példák:

  • a|b* jelöli a {ε, a, b, bb, bbb, …} halmazt
  • (a|b)* által jelölt halmaz tartalmaz minden olyan stringet, amely tetszés szerinti számú a és b szimbólumból áll, valamint az üres stringet is
  • b*(ab*)* mint az előző
  • ab*(c|ε) jelöli a stringek olyan halmazát, amelyben a stringek a-val kezdődnek, utána nulla vagy több b következik, a záró c opcionális.
  • ((a|ba(aa)*b)(b(aa)*b)*(a|ba(aa)*b)|b(aa)*b)*(a|ba(aa)*b)(b(aa)*b)* jelöli minden olyan string halmazát, amelyek páros számú b-ből és páratlan számú a-ból állnak. Megjegyezzük, hogy a fenti kifejezés leírható a következő formában is: (X Y*X U Y)*X Y* ahol X = a|ba(aa)*b és Y = b(aa)*b.

A reguláris kifejezések formális definíciói szándékosan a lehető legegyszerűbbek és igyekszenek elkerülni a redundáns mennyiségi jelölőket, (? és +) amelyek kifejezhetőek a következőképpen: a+= aa*, és a? = (ε|a). Néha a komplementer képző operátort ~ is használják (~R jelöli az összes string halmazát a Σ ábécé felett, amelyek nem részei R-nek. A komplementerképző operátor redundáns: minden esetben kifejezhető egyéb operátorok használatával.

A reguláris kifejezések ebben az értelemben pontosan kifejezhetők a nyelvek azon csoportjával, amelyeket véges automata el tud fogadni: a reguláris nyelvekkel. Némi ellentmondást jelent, hogy a reguláris nyelvek néhány osztálya leírható egy automatával, azonban a reguláris kifejezések hossza exponenciálisan növekvő, míg más esetben a hossz növekedése csak lineáris. A reguláris kifejezések által definiált nyelvek osztálya megfelel a Chomsky-féle hierarchia harmadik típusú nyelvtanainak, és leírásukhoz a reguláris nyelvek használhatók.

Amint azt a példák is mutatják, különböző reguláris kifejezések azonos nyelven kifejezhetők: a használt formalizmus redundáns.

Lehetséges olyan algoritmus írása, amelyik két adott reguláris kifejezésről eldönti, hogy az adott nyelven egymásnak megfelelnek-e, ekkor a kifejezéseket egy minimális determinisztikus automatává redukálják, így eldönthető, hogy azok izomorfak-e (ekvivalensek).

Hogyan lehet megszüntetni a redundanciát? Található-e reguláris kifejezések olyan megfelelő részhalmaza, amely még teljesen kifejező? A Kleene csillag és halmazok uniója nyilvánvalóan szükségesek, de korlátozottan használhatóak. Kiderül, hogy ez a probléma meglepően bonyolult. Egy egyszerű reguláris kifejezésről kiderül, hogy nincs szisztematikus helyettesítési eljárás valamilyen normál formává alakítására. A reguláris kifejezések végesen nem axiomatizálhatók. Más módszert kell igénybe venni. A fentiek miatt merült fel a csillag súly probléma .

A gyakorlatban megvalósított „reguláris kifejezés elemző gépek” működését nem lehet egy reguláris kifejezés algebrával leírni; a részleteket lásd a alul pontban.

Szintaxis

[szerkesztés]

„Tradicionális” Unix reguláris kifejezések

[szerkesztés]

Az „alap” Unix reguláris kifejezéseinek definíciói a POSIX megjelenésével ugyan elavultak, ennek ellenére széles körben használatosak a visszafelé kompatibilitás miatt. A legtöbb reguláris kifejezést felismerő Unix (segéd)program, például a grep és a sed alapértelmezésként használja még ezeket.

Ebben a szintaxisban a legtöbb karaktert literalként kezelik – saját magukra illeszkednek csak („a” illeszkedik „a”-ra, „(bc” illeszkedik „(bc”-re stb.). A kivételek az illesztő-karaktereknek nevezett metakarakterek:

. Illeszkedik bármilyen egyedülálló karakterre
[ ] Illeszkedik arra az egyedülálló karakterre, ami a zárójelek között fel van sorolva. Például, [abc]-re illeszkedik „a”, „b”, vagy „c”. [a-z]-re illeszkedik bármelyik kisbetű. A jelölések keverhetők: [abcq-z]-re illeszkedik a, b, c, q, r, s, t, u, v, w, x, y, z, de így is írható: [a-cq-z].

A '-' karakter literálként viselkedik, ha a zárójelen belül első vagy utolsó helyen szerepel: [abc-] vagy [-abc]. A'[' vagy ']' karakterek illesztése nagyon egyszerű, csak a záró szögletes zárójelet előbb kell írni a nyitó szögletes zárójelnél: [][ab]-re illeszkedik ']', '[', 'a' vagy 'b'.

[^ ] Illeszkedik egy egyedülálló karakterre, amely nem szerepel a zárójelben felsoroltak között. Például, [^abc] illeszkedik bármilyen karakterre, amelyik nem „a”, „b”, vagy „c”. [^a-z] illeszkedik bármilyen egyedülálló karakterre, ami nem kisbetű. Amint azt már említettük, ezek a jelölések is keverhetők.
^ Illeszkedik a sor kezdetére (vagy bármelyik sorra, többsoros mód alkalmazása esetén)
$ Illeszkedik a sor végére (vagy bármelyik sorra, többsoros mód alkalmazása esetén)
\( \) Egy „megjelölt alkifejezést” definiál. Az alkifejezés illeszkedés később is ellenőrizhető. Lásd a következő, \n pontot. Megjegyezzük, hogy a „megjelölt alkifejezés” helyett gyakran a „blokk” kifejezés használatos.
\n Ahol n egy 1 és 9 közötti számjegy; az n-edik megjelölt alkifejezést illeszti. Ez a konstrukció elméletileg szabálytalan és nem engedi meg minden reguláris kifejezés kiértékelő szintaxisa.
*
  • Egy egyszerű karakter kifejezést követő „*” a kifejezés nulla vagy több másolatát illeszti. Például, „[xyz]*” illeszkedik a következőkre „”, „x”, „y”, „zx”, „zyx”, és így tovább.
  • \n*, ahol n egy 1 és 9 közötti számjegy, nulla vagy több iterációval illeszti az n-edik megjelölt alkifejezést. Például, „\(a.\)c\1*” illeszkedik „abcab”-re és „abcaba”-re, de nem illeszkedik „abcac”-re.
  • A „\(” és „\)” közé zárt kifejezést követő „*” érvénytelennek tekintendő. Néhány esetben (például /usr/bin/xpg4/grep a SunOS 5.8 esetén), nulla vagy több iterációval illeszti a zárójelek közötti kifejezést. Másik esetben(például /usr/bin/grep a SunOS 5.8 esetén), illeszti a „*” előtti zárójelben lévő kifejezést.
{x,y} Az utolsó „blokkot” legalább x-szer, de legfeljebb y-szor illeszti. Például, „a{3,5}”-re illeszkedik „aaa”, „aaaa” vagy „aaaaa”. megjegyezzük, hogy ez sem található meg minden regex megvalósításban.

Meg kell jegyezni, hogy bizonyos reguláris kifejezés elemző megvalósítások a \ metakaraktert másként értelmezik, mint azt az előzőekben mutattuk.

A grep régi változatai nem támogatják a választási operátort jelölő „|” karakter használatát. Példák:

„.ép” illszkedik bármilyen háromkarakteres stringre, mint például kép, lép vagy tép és nép
„[kl]ép” illeszkedik kép-re és lép-re
„[^t]ép” illeszkedik minden, az előzőekben leírt „.ép” kifejezésnek megfelelő stringre, kivéve a tép-et
„^[kl]ép” illeszkedik kép-re és lép-re, de csak akkor, ha ezek a stringek a sor elején állnak
„[kl]ép$” illeszkedik kép-re és lép-re, de csak ha a sor végén állnak

A különféle beállításoktól, értelmezésektől függően változhat a karakterek sorrend szerinti csoportosítása (például bizonyos beállítások szerint a karakterek sorrendje az abc..yzABC..YZ szerinti, míg más elv szerint az aAbBcC..yYzZ a sorrend) a – nem mindenki által elfogadott – POSIX szabvány meghatározza a karakterek osztályokba vagy csoportokba sorolást a következő tábla alapján:

POSIX osztály Megfelel Jelentése
[:upper:] [A-Z] Nagybetűk
[:lower:] [a-z] Kisbetűk
[:alpha:] [A-Za-z] Nagy- és kisbetűk
[:alnum:] [A-Za-z0-9] Számjegyek, nagy- és kisbetűk
[:digit:] [0-9] számjegyek
[:xdigit:] [0-9A-Fa-f] hexadecimális számjegyek
[:punct:] [.,!?:…] elválasztó karakterek
[:blank:] [ \t] szóköz és TAB
[:space:] [ \t\n\r\f\v] üres karakterek
[:cntrl:] vezérlő karakterek
[:graph:] [^ \t\n\r\f\v] nyomtatásvezérlő karakterek
[:print:] [^\t\n\r\f\v] nyomtatásvezérlő karakterek és szóköz

Például: [[:upper:]ab] meghatározza az összes nagybetűt és a kisbetűs 'a'-t és 'b'-t.

(Egy ASCII kódtáblán színesben mutatja a különböző POSIX osztályokat a következő link https://web.archive.org/web/20060418224525/http://www.billposer.org/Software/RedetManual/builtincharclass.html.)

Megjegyezzük, hogy a magyar ábécé ékezetes betűinek kezelése esetenként eltérő módon történik, ugyanis a különféle szabványok nem minden esetben térnek ki a különböző országokban használatos, az angol ábécé betűitől eltérő betűk kódolására, kezelésére. Gyakori probléma például, hogy az ábécé szerinti rendezésnél az ékezetes betűk rossz helyre kerülnek, mivel a karakterek kódjai – többnyire – a nem ékezetes karakterek kódjai után következnek, tehát rendezés szempontjából azok valóban „nincsenek sorban”.

POSIX modern (bővített) reguláris kifejezések

[szerkesztés]

Több modern, „bővített” reguláris kifejezést használhatnak a modern Unix segédprogramok a parancssorban az „-E” jelző hatására.

A POSIX bővített reguláris kifejezéseinek szintaxisa néhány kivételtől eltekintve megegyezik a „tradicionális” Unix reguláris kifejezéseivel. A következő metakaraktereket értelmezi még a program:

+ Az utolsó „blokk” egyszeri vagy többszöri illesztése – „ba+” illeszkedik a következőkre: „ba”, „baa”, „baaa” és így tovább.
? Az utolsó „blokk” illesztése (csak egyszer) vagy nem illesztése – „ba?” illeszkedik a következőkre: „b” vagy „ba”
| A választás (vagy unióképző) operátor: az operátort megelőző vagy követő kifejezést illeszti – „abc|def”-re illeszkedik „abc” vagy „def”.

A „visszatörtjel” eltávolítása: \{…\} átalakul {…}-re és \(…\) átalakul (…)-re. Példák:

„[hc]+at” illeszkedik a következőkre: „hat”, „cat”, „hhat”, „chat”, „hcat”, „ccchat” stb.
„[hc]?at” illeszkedik „hat”-ra, „cat”-ra és „at”-ra
„([cC]at)|([dD]og)” illeszkedik a következőkre: „cat”, „Cat”, „dog” és „Dog”

A speciális jelentéssel bíró '(', ')', '[', ']', '.', '*', '?', '+', '^' és '$' karakterek az escape-zés használatával literálként lesznek értelmezve. Ez azt jelenti, hogy a karaktert megelőzi a '\' karakter, amely így „escape-ezve” már saját literálját jelenti csak. Példa:

„a\.(\(|\))” illeszkedik az „a.)” vagy az „a.(” stringekre

Perl-kompatibilis reguláris kifejezések (PCRE)

[szerkesztés]

A Perl egy gazdag és következetes szintaktikai elemzővel rendelkezik, amely még a POSIX kiterjesztett reguláris kifejezéseinek elemzésére is alkalmas. A következetességre jó példa, hogy a \ karakter minden esetben egy nem alfanumerikus karaktert jelöl. Szabályozható, hogy a specifikáció kiválasztásával milyen illesztési algoritmust használjon az elemző: a Perl szintaxis, szemben a POSIX szintaxissal a „mohó” algoritmust követi, míg a másik nem. Ez azt jelenti a gyakorlatban, hogy a /a.*b/ minta .* jelölése azt jelenti, hogy annyit illesszen az elemző, amennyit lehet, míg a /a.*?b/ mintában a .*? jelöli, hogy csak olyan kicsit illesszen az elemző, amennyit csak lehet. Ha adott a „a bad dab” string, akkor az első minta illeszkedik az egész stringre, míg a második csak az „a b” részt „ismeri fel”.

A fentiek miatt több alkalmazás és segédprogram is megvalósítja a Perl „szerű” szintaxist, többek között – a Python, Ruby, exim, és a BBEdit. Készültek olyan alkalmazások, például a Tcl, amely a POSIX előírásokat és a Perl kiterjesztéseket is megvalósítja. Ennek viszont az a következménye, hogy a Tcl illesztési modellje nem mohó, azaz a „lehető legkisebb” illesztési elvet valósítja meg.

Minták a nem reguláris nyelvekben

[szerkesztés]

A minták használatának lehetőségeiből származó előnyök túlmutatnak a reguláris nyelveken. Például megjelölt alkifejezések zárójelek segítségével történő csoportosítása és azok későbbi kiértékelése, minták használatával, különösen az ismétlődő szavak esetében („papa”, „WikiWiki” stb.) a formális nyelvek elméletében bevett gyakorlat, és a „(.*)\1” mintával igen egyszerűen kivitelezhető. Ugyanakkor a fenti megoldás nem megengedett még a környezetfüggetlen nyelvek esetében sem. A mintaillesztést korlátlan számú előzetes referencia használatával számos modern NP-teljes komplexitású eszköz biztosítja.

Mégis, egyre több eszköz, könyvtár, elemző támogatja a reguláris kifejezések és a mintaillesztési mechanizmus használatát. Ennek az a következménye, hogy a „reguláris kifejezés” és a hozzá tartozó mintaillesztés jelentését eltérően értelmezi a formális nyelvek elmélete.

Megvalósítások és futási idők

[szerkesztés]

Legalább két, alapjában eltérő algoritmus típus ismert, amely eldönti, hogy (és hogyan) illeszkedik-e egy reguláris kifejezés egy adott karakterláncra.

A régebbi és gyorsabb megoldás alapja, hogy a formális nyelvek elmélete szerint megengedett, hogy minden nemdeterminisztikus véges állapotú gép (Nondeterministic Finite automaton, NFA) átalakítható egy determinisztikus véges állapotú géppé (Deterministic Finite automaton, DFA). Az algoritmus ezt az átalakítást hajtja végre vagy szimulálja, és ezután az eredményül kapott DFA elemzi a bejövő jelsorozatot. Egészen pontosan, egy n hosszúságú bejövő karakterlánc ellenőrzése egy M hosszúságú kifejezés esetén O(n+2m) vagy O(nm) időt igényel, a megvalósítástól függően. Erre az algoritmusra gyakran mint DFA-ra hivatkoznak. Ez valóban gyors, azonban csak és kizárólag illeszkedést lehet vele vizsgálni, és nem képes emlékezni csoportosított alkifejezésekre. Létezik olyan változata az algoritmusnak, amely képes a emlékezni csoportosított alkifejezésekre, azonban ekkor a futási idő O(n2m)-re lassul.

A másik algoritmus csoport a mintaillesztés elvét használja ki, mintát illeszt a bejövő jelsorozathoz visszaléptetési módszerrel. (Ezt az algoritmust gyakran nevezik NFA-nak, azonban ez nagyon zavaró.) A futási ideje exponenciálisan növekvő, ha azt az egyszerű megvalósítást vizsgáljuk, amikor az „(a|aa)*b” mintát kell illeszteni egy kifejezésre, ami választást és kötetlen számú illeszkedés is magába foglal, a lehetséges alapesetek száma igen nagyra nőhet – a kifejezés hosszától és összetettségétől függően, és ezek számától függően exponenciálisan nő a futási idő. Nagyon komplex megvalósítás esetén is csak a legegyszerűbb és leggyakoribb eseteknél nőhet a sebesség valamennyit, de egyébként csökken.

Még a visszaléptetés megvalósítása is csak egy exponenciális korlátot jelent, a legrosszabb esetre, viszont nagyobb flexibilitást biztosít.

Néhány esetben úgy növelik a teljesítményt, hogy a két algoritmust egyszerre alkalmazzák: első lépéseben a gyors DFA illesztő algoritmussal végigmennek a bejövő karakterláncon, majd a nem illeszthető részekre a sokkal lassabb visszaléptető eljárást használják.

Kapcsolódó szócikkek

[szerkesztés]

Angol nyelvű irodalom

[szerkesztés]

Külső kapcsolatok

[szerkesztés]

Angol nyelvű cikkek

[szerkesztés]

Eszközök

[szerkesztés]

Programkönyvtárak

[szerkesztés]
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Reguláris_kifejezés&oldid=26839993”