A backreference ereje

Kb az első dolog, amit a reguláris kifejezésekkel kapcsolatban megtanul az ember, az az, hogy

az a^nb^n nyelv nem reguláris, nincs őt jelölő reguláris kifejezés

mert pumpáló lemma.

Ma első körben tehát írunk egy regexet, ami márpedig az a^nb^n-t matcheli, szépen lépésenként.

DISCLAIMER. A regex NEM erre való! Soha, soha, soha ne illesszetek olyasmi reguláris kifejezést, amit most fogok leírni! Ezeket a problémákat célnyelven sokkal hatékonyabban meg lehet oldani! A post célja csak figyelemfelkeltés, hogy valójában mekkora is a mai regexek kifejezőereje, amit kihasználni viszont tilos, veszélyes és nem hatékony!

1. ^(a+)b+$

ez ugye az a+b+-ra illeszkedik, néhány a (legalább egy), majd néhány b (legalább egy), nem feltétlenül ugyanannyi. Első csoportba bekerülnek az a-k, feldolgozza az egész stringet.

2. ^(a+)(?=b+$)

Lookahead csoportba kerültek a b-k. Ugyanúgy az a+b+ alakú inputra illeszkedik, de ezúttal csak az a-kat dolgozza fel, azok ki is kerülnek az első elfogott csoportba. Ezt nem matchelni, hanem findolni kell már, mert csak az a-kra illesztünk.

3. ^(a(?=a*b+$))+

Lássuk, itt mi történik? Valami iterálva van, mégpedig az a(?=a*b+$) csoport. Ez egyszerre egy darab a-ra illeszkedik akkor, ha utána a*b+$ alakú string jön. Mivel kalappal kezdünk, az első pozíción is erre kell illeszkedni, az pedig akkor lehet, ha a+b+ alakú a string. Ezután a mohó plusz feldolgozza az összes a-t, mert ekkor mindegyik a utáni rész a*b+$ alakú lesz. (noch dazu vegyük észre, hogy lookaheadat simán lehet iterálni!)

4. ^(?:a(?=a*(\1b)))+

A lookahead belsejében a b+-t kicseréltük \1-re, a külső csoport non-capturing lett, a (\1b) rész pedig lett az első capturing group. HA a \1 alapból "" tartalommal lenne inicializálva, akkor az első a betűre ez akkor illeszkedne, ha utána a*b következne (azaz legalább egy b lenne a stringben az a-k után). Ekkor a \1 tartalma "b" lenne (az elkapott \1b miatt), a következő iterációban, vagyis a második a betűre a lookahead egy a*bb-t kérne (legalább két b-t), és utána \1 tartalma bb lenne. A harmadik a betűre akkor illeszkedne, ha utána a*bbb állna stb, az n. a betűre akkor, ha n darab b követné.

Ez akár működhetne is, DE a \1 alapból nem "", hanem nem illeszkedik semmire, ezért már az első menetben se illeszkedik semmire a lookahead. (vegyük észre, hogy az n. csoportba simán belehelyettesítettük az n. csoport tartalmát!)

5. ^(?:a(?=a*(\1?+b)))+

A kérdőjellel opcionálissá tettük a csoport \1 részét, ezzel elértük, hogy az első iterációban (mikor nem illeszkedik semmire) a motor ki fogja hagyni és úgy halad tovább, ahogy szeretnénk: az első a-ra akkor fog illeszkedni, ha van első b. Utána mert possessive ?+-ot használunk, nem engedi el a találatot: a következő menetben \1 tartalma b, ez tudjuk, hogy ott is van (mert az előbb a b illeszkedett), ezt megfogja, nem engedi, és kéri a második b-t is hozzá (ha sima mohó kérdőjelet használnánk, az elfogadná az a+b alakú inputokat is, mert a másodiktól kezdve minden iterációban azzal haladna tovább, hogy nincs ott a \1. A possessive kérdőjel ezt nem engedi, mivel az eggyel kevesebb b tudjuk, hogy ott van, arra fog illeszkedni a \1?+, nincs backtrack, és kér még egy b-t.

Ez a kifejezés tehát úgy működik, mint az előző és akkor illeszkedik az a+b+ alakú stringnek az a-kból álló részére, ha legalább annyi b van, mint ahány a.

6. ^(?:a(?=a*(\1?+b)))+\1$

Ezzel pedig befejezzük az előzőt: az utolsó a után még egy \1 zárja a stringet, akkor pont annyi a-val kezdünk, mint ahány b-re végződünk, tehát a^nb^n-t matcheljük ezzel a kifejezéssel. (Ez innen van.)

Ha valakit ez nem akasztott ki, jöjjön egy SAT solver regex.

Emlékeztetőül, a SAT az input konjunktív normálforma kielégíthetőségét kérdezi, kulturáltabb esetben ha kielégíthető, kér egy kielégítő kiértékelést is. Egy ilyet fogunk megoldani a példa $(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2)\wedge(\neg x_2\vee\neg x_3)$ formulánkon.

Azt fogjuk csinálni, hogy az \1 csoportba tesszük az $x_1$ változó értékét, a \2 csoportba az $x_2$ értékét stb. Mégpedig úgy, hogy ha a változó értéke igaz, akkor a csoport tartalma mondjuk 'x', ha hamis, akkor pedig ''. Ez eddig könnyű: a regex (x?)(x?)(x?), a szöveg pedig xxx. Ha hat változónk van, akkor hat csoport és hat x. Hogy ezt a részt biztos feldolgozzuk, inkább (x?)(x?)(x?)x*, regexet illesztjük az xxx, stringre, akkor a vesszőig mindent lenyelünk.

Akkor egy x-re az \1 regex akkor illeszkedik, ha az $x_1$ értéke igaz. A \1x regex pedig akkor, ha $x_1$ értéke hamis (mert akkor \1 az üres string ugye). Ha így csinálunk literálból regexet és vagyoljuk egy klózon belül a literálokból készített regexet, tehát pl. az $(x_1\vee\neg x_2\vee x_3)$ klózhoz az (?:\1|\2x|\3) regexet rendeljük, ez pont akkor fog illeszkedni egy x-re, ha a klózban van egy igaz literál (tehát ha a klóz igaz).

Ezután már csak annyi dolgunk van, hogy klózonként bővítsük így a regexünket, vesszőkkel elválasztva, a textet meg egy-egy x-szel klózonként, szintén vesszőkkel elválasztva, hogy ne legyen kavarodás.

Tehát pl. az (x?)(x?)(x?)x*,(?:\1|\2x|\3),(?:\1x|\2),(?:\2x|\3x) regex pont akkor illeszkedik az xxx,x,x,x textre, ha a fenti formulánk kielégíthető. Illeszkedik is, ez most épp az $x_1=x_2=1$, $x_3=0$ értékadást fogja nekünk visszaadni. (Ez innen van.)

...szóval mezei regex matchinggel meg lehet oldani NP-teljes problémákat is, amiket amúgy jelen tudásunk szerint csak exponenciális (determinisztikus) időben tudunk. Ez arra utal, hogy azért ezeket a regexeket már nem lehet csak simán automatává konvertálni polinomidőben, hiszen akkor polinomidejű lenne az egész történet.

A backreference okozza a problémát. Backreference-en kívül minden mai modern regex elemet meg lehet csinálni automatával is, lineáris, gyors illesztéssel, a fentiek pedig mutatják, hogy a backreference jelenléte viszont kb a backtrackinget teszi az egyetlen értelmes alternatívává.

Az RE2 motor pontosan így működik: ha van backreference, backtrackel, ha pedig nincs, automatát épít. Nem tudok olyan másik elérhető motorról, ami ezt a viselkedést produkálja, szerintem ez a legjobb a világon per pillanat.

just a thought :)

A klasszikus reguláris operátorokon túl 2.

Többször utaltam már rá, hogy (pl.) a ? operátor mohó avagy greedy: ez annyit tesz, hogy egy R? alakú subregexet először is illeszteni próbálja az R-t, ha illeszkedik, úgy halad tovább, no ezután két eset lehetséges: vagy sikerül az illesztés a regex végéig, ez jó, vagy nem, ekkor pedig (ha az R-t semmiképp nem tudja illeszteni úgy, hogy azt befejezze) elengedi az R-t, és üres stringet illeszt. Ha így sikerül illeszteni a regex végéig, akkor OK, ez lesz az illesztés végeredménye, ha így sem, akkor persze backtrack.

Így például a y(hello|dolly|hell|doll)?d regexnek a dollydollydolly stringen hívott find() metódus eredménye sikeres illeszkedés, mégpedig a félkövérrel kiemelt részen, az opcionális találat a "dolly" szót adja vissza. (Maga a regex egy árnyalattal gyorsabban illeszthető lenne, ha y(hello?|dolly?)y alakba kerülne, de így se rossz.)

Ez a viselkedés megváltoztatható: egyrészt a ? lehet lazy is, ennek jele ??: ekkor pedig a subregex először próbálja illeszteni az üres stringet, és csak ha így nem vezet eredményre az illesztés, akkor próbál ténylegesen betenni valami nemüres stringet, ami illeszkedik R-re. Vagyis pl. az y(hello|dolly|hell|doll)??d regex szintén illeszkedik a dollydollydolly stringre, a jelölt részen.

Azt azért vegyük észre, hogy a greedy vs lazy illesztés időben nem okoz majd különbséget, ha végül a text nem illeszkedik a regexre, mert mindkét esetben kipróbálja az összes lehetőséget, csak a sorrend a különbség (és persze ha többféle illesztési találat lehetséges, akkor mást fog visszaadni az egyik és mást a másik).

A harmadik, a possessive módja a ? operátornak, aminek jele a ?+, a következőt jelenti: először is megpróbál keresni egy illesztést. Ha sikerül, akkor ehhez ragaszkodik és ha a regex további része nem illeszkedik a string maradék részére, és visszajön backtrackkel, akkor se nem próbálja másképp illeszteni a kérdéses subregexet, se nem próbálja kihagyni, hanem dobja tovább a backtracket. Ha viszont a subregex nem illeszkedik ezen a ponton, akkor az üres stringet illeszti és azzal megy tovább. Egy példán: a ^(hello|dolly|hell|doll)?+y regex nem illeszkedik a dolly stringre: a motor balról jobbra próbálgatva az alternatívákat először észreveszi, hogy a "dolly" alternatíva illeszkedik, ezt illeszti a subregexre, majd haladna tovább, ám a string elfogyott, a regex záró "y" karakterére nem fog passzolni semmi. Ha simán egy ? operátorunk lenne, most backtrackkel próbálná tovább a lehetőségeket és a doll illesztése már sikerre vezetne, de mivel most ez egy possessive kérdőjel, így nem próbálkozik tovább, ragaszkodik a dollyhoz mint találathoz és kidobja az egész illesztést az ablakon. Egyébként a ^ metachar nélkül a (hello|dolly|hell|doll)?+y regexet a find metódus megtalálja a dolly stringben: az utolsó y karakteren, ott mivel a csoport belseje nem illeszkedik egyáltalán, üres stringet illeszt rá, és melléteszi az y-t. A possessive tehát könnyen lehet, hogy kevesebb stringre illeszkedik, mint a greedy és lazy párjai, nem-találatnál viszont gyorsabb lehet, mint a másik kettő (hiszen nem fog mindent végigiterálni belül). Technikailag egyébként az R?+ ugyanaz, mint az (?>R?), tehát egy greedy belerakva egy atomic groupba. Egyes nyelvek lehet, hogy nem támogatnak possessive-et, de atomicot igen, ott így csinálunk possessive-et, ha nagyon akarunk.

A greedy / lazy / possessive variánsai persze nem csak a ? operátornak, de a *, + és {m,n} operátornak is megvannak, a lazyt mindig egy plusz kérdőjellel, a possessive-et pedig mindig egy plusz plusszal kapjuk, pl. a *? a lazy csillag (ami a lehető legkevesebb iterációból próbálja megúszni az illesztést). Csak példaképp, egy xml tag belsejét (a <..> közti részt, amiben nincs másik >) a <(.*?)> regex első csoportjában megkapjuk, pl. a hello<b>world</b> stringben a lazy star a kiemelt b-re illeszkedik. A greedy star pedig a b>world</b részre illeszkedne, hiszen benyelne a lehető legtöbb mindent, ami még nem rontja el az illesztést. A possessive star pedig

egyáltalán nem illeszkedik

erre az inputra. Miért? A <.*+> regexet ha a hello<b>world</b> stringre illesztjük (find()), akkor az első < jelen tudja illeszteni az első karaktert. Most jön a .*+, tetszőleges karakter possessive iterálása, ami lényegében egy greedy iteráció, amit nem lehet backtrackelni. Vagyis első próbálkozásképp ez a subregex feldolgozza a b>world</b> (tehát az egész hátralevő) substringet, és rájön, hogy nincs utána >. csak ezután nem backtrackel és engedi el az utolsó karaktert, mint a greedy, hanem visszalép, hogy nincs illesztés. Ekkor a regex első < karakterét próbálja máshova, később illeszteni a motort, illik is a </b>-re, de a possessive star azt is elrontja és nem lesz egyáltalán illeszkedés. (A .*+ egy elég értelmetlen konstrukció, hiszen mindig ezt csinálja: elmegy az input végéig és ha a regex maradék része illik az ottani üres stringre, akkor OK, egyébként fail)

Azt azért ne gondoljuk, hogy pl. a possessive star értelmetlen lenne: a tagbelső bányászást konkrétan én a <([^>]*+)> regex használatával csinálnám: iterálom a nem-> jelet, majd ha > jön, akkor visszaadom a belsőt. Ha viszont itt > helyett vége a stringnek, a greedy star még egyesével visszaadogatná a karaktereket, amiket megszerzett, és mindnél rájönne, hogy nem > jön utána, teljesen fölöslegesen; a possessive star nem backtrackel, hanem szól, hogy itt nem lesz illesztés.

Ennyi kitérő után nézzünk egy eggyel összetettebb taskot: van egy input stringünk, amiben pöttyöket kell betegyünk az előforduló számokba hármasával tizedesjegyenként. Tehát például a

sanyi1234 12345678910 másiksanyi12 142857142

stringből a

sanyi1234 12.345.678.910 másiksanyi12 142.857.142

stringet kéne kapjuk: a két szabadonálló számba kerüljön bele két-három pötty.

Persze ezt is meg lehet csinálni célnyelven, de ha az ember magabiztosan kezeli a regexeket, ezt még talán azzal célszerű is megcsinálni. (Ellentétben pl. a következő post regexeivel, amiket soha, de soha nem ajánlok senkinek :D )

Van pl Javában a Matcher osztálynak egy replaceAll metódusa, ez jó is lesz a célra: ahol illeszkedik a regex, azokat a substringeket kicseréli a paraméterére. Továbbmenve, a captured group-ok eredményét is vissza lehet helyettesíteni, $n jelöli az n. csoport értékét.

Első próbálkozás lehet pl. egy ilyen, amikor is a (\d)(\d{3}) regex ha matchel, cseréljük $1. \$2-re. (Ez legalább pontot tesz be valahova :D ) amint látszik, ideone.com-on futtattam, eredmény:

sanyi1.234 1.2345.678910 másiksanyi12 1.4285.7142

oké, mi is történt, először is megtalálta az egyest, ami után van három számjegy, betett egy pöttyöt, mant tovább. Megtalálta a második egyest, ami után van három számjegy, tett egy pöttyöt. De mivel ekkor már feldolgozta a 4-est, az 5-ösnél folytatta a következő próbálkozást (ami egy számjegy, utána 678, kiírta az 5.678-at), majd mivel a 9-es volt a következő feldolgozatlan karakter, azt nézte (azután nincs három másik, így legközelebb a másik hossú számba tett be pöttyöket.

Ha véggiggondoljuk, ez a legalább négy hosszú számokba tesz be pöttyöket, négy jegyenként, de balra igazítva (az első jegy után jön az első pötty), nekünk meg hármasával kéne jobbra igazítva.

A jobbra igazítás az keményebb diónak látszik. Illeszteni még csak-csak lehet egy számra így: \b(\d+)((?:\d{3})+)\b, vagyis szóhatár, számjegyek, utána hárommal osztható darab számjegy, de ha ezek közé teszünk be pontot, mint az előbb, kód, akkor az eredmény

sanyi1234 12345678.910 másiksanyi12 142857.142

lesz, ami ugyan csak a számokban cserélt dolgokat, és be is tett jobbra igazított pöttyöt, de csak számonként egyet. Miért? Azért, mert a regex az egész számra illeszkedik, a \d+ rész első próbálkozásban lenyeli az egész számot, azután nincs hárommal osztható darab számjegy, szépen elenged egyesével három jegyet, ekkor van egy jó vágása, első csoportba bekerül az 12345678, másodikba a 910, a replaceAll közéjük teszi a pöttyöt, minden szép, csak a következő menetben már az 12345678-ra nem próbál tovább illeszteni, mert azt már feldolgozta és a másiksanyi12-nél folytatja az illesztést.

Valahogy el kellene érni, hogy csak lássuk a szöveget, hogy illeszkedik-e egy mintára, de ne dolgozza fel a motor.

Erre jó a lookahead és lookbehind, közös néven lookaround.

A lookahead csoport szintaxisa (?=...), belül egy teljesen normális regexet írhatunk, ekkor az történik, hogy megnézi a motor, hogy az aktuális pozíción kezdve illeszkedik-e a lookaheadban levő regex; ha nem illeszkedik, akkor backtrackel, de ha illeszkedik, akkor továbbmegy, viszont nem dolgozza fel a megnézett részt! Pl az a(?=aaaa)a regexet ha find()oljuk az aaabaaaaa texten, a vastagított részt kapjuk találatként: először illeszt egy a-t, majd megnézi, hogy még négy a következik-e, ha igen, akkor illeszt még egy a-t. Másik példának az (?=a)b regex nem illeszkedik semmire, mert egyrészt az adott pozíción előrenézve a következő karakter a kell legyen, és ha az, akkor megpróbál ráilleszteni egy b-t, ami nyilván nem fog menni.

Visszatérve a feladathoz, így már könnyű dolgunk van: ha van egy számjegy-sorozatunk, ami után hárommal osztható darab számjegy jön előretekintve, tegyünk mögé pöttyöt: \b(\d+)(?=(?:\d{3})+\b)-t cseréljük $1.-ra. Vegyük észre, hogy a háromdigit ismétlését azért teszem bele egy non-capturing groupba, mert különben valami possessive pontosanháromjegyet kapnék, ami nekem nem túl világos, hogy mit kéne jelentsen :D szóval a "pontosan n darab ismétlés" is lehet szintaktikailag lazy meg possessive, de nem kéne mást jelentsen, a pont n az pont n. na mindegy. Eredmény:

sanyi1234 12345678.910 másiksanyi12 142857.142

hát ez nem sokkal jobb, mint volt. Mi történt? Az, hogy a + greedy, most azért ette meg a szám túlnyomó részét. Ha a lazy plust használjuk:

sanyi1234 12.345678910 másiksanyi12 142.857142

Persze, ez meg a szóhatár miatt nem illeszkedik a következő iterációban: bár csak a 12. kerül kiírásra és a 345...-nél folytatja a motor a feldolgozást, mégse fog illeszteni, mert a 345 az eredeti szövegben nem a szó eleje volt. (Anélkül a feltétel nélkül meg a sanyi1234 is kapna pontot, amit nem akarunk. Ha mégis akarnánk, akkor a (\d)(?=(?:\d{3})+\b) regexet cseréljük $1.-ra és kész.)

Ami most segíthet: a lookbehind, aminek szintaktikája (?<=...), ez akkor illeszkedik egy pozícióra, ha a string közvetlenül megelőző része illeszkedik a regexre (de nem dolgozza fel azt, csak megnézi). Szerencsére a Java támogatja a változó hosszú lookbehindot is, a különböző nyelvek elég változatos képet mutatnak afelől, hogy támogatják-e egyáltalán a lookbehindot, és hogy annak lehet-e a hossza nem konstans.

Mit cseréljünk most mire? Ha találunk egy számjegyet, ami előtt egy szóhatár, majd számjegyek voltak (lookbehind), utána pedig hárommal osztható darab számjegy és egy szóhatár (lookahead), akkor cseréljük ezt a számjegyet önmagára és egy pontra. Azaz (<=\b\d*)(\d)(?=(?:\d{3})+\b)-t cserélünk $1.-ra. Kód itt. Működik!

sanyi1234 12.345.678.910 másiksanyi12 142.857.142

Körbenézésből (ahol támogatva van) van negatív is: a negatív lookahead jele (?!...), a negatív lookbehindé pedig (?<!...), és akkor illeszkednek pozíción, ha az előtte/utána közvetlen lévő részre nem illeszkedik a csoport tartalma.

A pöttyös példát egyébként a Friedl könyvéből szedtem.

Legközelebb megnézünk pár extrém regex overabuse-t. Ilyeneket fogunk csinálni, hogy a{n}b{n}-re matchelünk regexet, meg konjunktív normálformának keresünk kielégítő kiértékelést. De csak azért, hogy lássuk, milyen érdekesen lehet egyszerre alkalmazni a körbenézést a capturing groupokkal és a backreference-ekkel együttesen. Nem azért, hogy bárkit arra biztassak, csináljon ilyet.

sőt.

folytköv

A klasszikus reguláris operátorokon túl 1.

Szóval volt az a kínos ügy, mikor is az $a?^na^n$ regexet illesztve az $a^n$ szövegre kaptunk egy exponenciális illesztési időt, meg a másik kínos ügy, amikor is az $(a^*)^*b$ regexet illesztettük az $a^n$-re és szintén exponenciális futásidőt kaptunk.

A korrektség kedvéért hozzátenném, hogy az $a?a?a?a?a?$ regex nem pont az, amit középkategóriás regex crafter leír, hiszen van ismétlés operátor: $R\{min,max\}$ azt jelenti, hogy az $R$ regexet legalább $min$, legfeljebb $max$ számúszor ismételjük. Alapból greedy operátor, tehát minél több iterációt szeretne csinálni a lehetőségein belül. Így az $a?^na^n$ regexet normális körülmények közt $a\{n,2n\}$ jegyzi. Még az ennél sokkal butább $(a?)\{n\}a\{n\}$  regexről is azt hinnénk, hogy szintén produkálja az exponenciális lassulást az $a^n$ stringen

de nem

az $(a?)\{n\}a\{n\}$ regex nagy $n$-ekre is pár ms alatt illeszkedik $a^n$-re. Még az én szubnotinom is $n=400$-nál megy fel 0ms-ről 1ms-re egyáltalán az illesztés. De miért?

A kérdés érdekesebbé válik akkor, ha illesztjük az $(aa?)\{n\}$ regexet az $a^n$ stringre, mert ekkor

megint exponenciális ideig vergődik vele

amit viszont már értek, szemben az előzővel, hogy mitől gyorsult az $(a?)\{n\}a\{n\}$ ennyire fel.
Beletúrva a java.regex.Pattern.Loop osztályba azt találtam, hogy valószínűleg arról van szó, hogy iterált csoportot nem illesztenek nulla hosszon, elkerülendő a végtelen ciklust, de nem mentem utána valami mélyen.

Mindenesetre a $(a^*)^*$ és az $a^*$ regexek nem teljesen ugyanazt mondják. Ugyanis, a sima zárójel egy mai regexben (ne felejtsük el, ha "reguláris kifejezést" mondok, az jelenti a matematikai konstrukciót, a "regex" pedig a jelenkori implementációkat) egy capturing groupot jelöl: illeszkedés tekintetében valóban ekvivalens, de sikeres illesztés után le lehet kérdezni az illesztő motortól, hogy ez a subregex az input string melyik substringjére illeszkedett. Nézzük ezt meg egy olyan példán, amire jó a regex: input egy XML file, nyerjük ki belőle a tageket (attribútumok, whitespace és szöveges cdata törlésével)! Tehát pl. az 'Ez egy < i spock="vulcan" >html <b>teszt</b>része</i>' inputra szeretnénk egy "<i><b></b></i>" szöveget kapni. Most feltételezzük, hogy attribútum belsejében nincs < vagy > jel, meg úgy alapból egy XML-helyes string az input. Akkor pl. eljárhatunk úgy, hogy

• megkeressük az első < jelet a szövegben
• skippeljük utána a whitespace-t
• ami karaktersorozat utána jön az a tag maga, mondjuk whitespace-ig vagy > jelig; ezt egy capturing groupba tesszük
• utána mindent skippelünk az első > jelig
• kiírjuk az elkapott csoport tartalmát mondjuk <> jelek közé rakva, és ismételjük az egészet, amíg csak találunk illeszkedést.

Erre a regex: <\s*([^\s>]+)[^>]*>, például.  Ha ezt a regexet ciklusban illesztgetni akarjuk a stringükre, amíg el nem fogy és az elkapott tagnevet kiírni, akkor ezt Javában pl így tesszük. (Az elkapott csoport belsejébe tehetnénk egy atomi csoportot is, mert nem akarunk belebacktrackelni, ha mégis XML-invalid az input, de erről később.) Világos: a find() metódus a következő illeszkedő substringet találja meg, ha van ilyen, és true az eredmény, ha nincs több, akkor false. Még lényeges, hogy az egész illeszkedő substringet lenyeli és a következő hívásnál az előző illeszkedés végénél kezdi próbálni illeszteni a regexet, ezt fontos tudnunk, ha átfedő illeszkedésekkel is akarunk foglalkozni (ahogy egy későbbi példában fogunk is). Az a substring egyébként, amire az egész regex illeszkedik, az a 0. csoportként kapható meg. Ha nem a substring kell, hanem a kezdő/végpozíció, akkor a group( groupIndex ) metódus helyett a start( groupIndex ) és end( groupIndex ) metódusokat szeretjük.

Ha nem szeretnénk kinyerni egy (mondjuk precedencia miatt) zárójeles subregex tartalmát, akkor mindenképp érdemes non-capturing groupingot használjunk (kivéve esetleg az olvashatósági szempontokat :P ), aminek jele a $(?:\ldots)$. Ha pl. az $(?:a^*)^*$ regexet nézzük, na az már ekvivalens az $a^*$ regexszel: simán zárójelbe rakva még illesztés után visszakaphatjuk, hogy a belső $a^*$ rész mire illeszkedik tulajdonképpen (az első összefüggő $a$-sorozatra fog), de ebben a non-capturing formában nem tudjuk ezt meg.
A non-capturing groupokat azért is érdemes használni, mert sok motorban korlátozva van a használható backreference-ek száma, javában a javadoc alapján kilencre saccolom. A backreference, avagy visszahivatkozás, de felőlem Berke Ferenc is lehet, egy regexen belülre írt $\backslash n$ kifejezés, ahol $n$ egy szám (javában tán egy pozitív számjegy lehet), ha ilyet lát a motor, oda behelyettesíti az $n$. capturing group legutoljára elfogott tartalmát. Pl. ha két egyforma számjegy ismétlődését akarjuk szűrni, akkor arra egy kifejezés a $(\backslash d)\backslash 1$. Ha egy szövegben szóismétlődést keresünk, akkor arra pl. egy regex a $\backslash b (\backslash w^*)\backslash b\backslash s^*\backslash 1$, ami az első capturing groupba bele is teszi nekünk a szó első előfordulását. (Ha valakinek nem rémlik, a $\backslash b$ a szóhatár metakarakter, nulla hosszon illeszkedik szavak határára.)

Nézzünk egy példát, amit legegyszerűbb backreferencekkel megoldani: ha jön be két karakter, akkor mondjuk "pár"-nak őket, ha egyformák, vagy van köztük $0$ (a nulla a "joker"). Ha csak annyi a feladat, hogy mondjuk meg, hogy az input string pár-e, akkor erre ezek szerint egy jó regex: $(.)\backslash 1|0.|.0$, az első opció lekezeli a "valódi" párokat, a második ha az első karakter a "joker", a harmadik ha a második karakter a joker. Mi van, ha a kérdést úgy módosítjuk, hogy az input string párok sorozata-e? "csillagozzuk meg", mondja az egyszeri jóember: $(?:(.)\backslash 1|0.|.0)^*$, aki még arra is figyelt, hogy a külső, csillagozott csoport non-capturing legyen, mert különben az lenne az egyes csoport és ekkor az első alternatvában $\backslash 1$ helyett $\backslash 2$ kéne szerepeljen. (Egyébként a nyitójelek sorrendje határozza meg, hogy hanyas számú a capturing group.)

bad move

ha ugyanis ezt a csillagos regexet mondjuk a $0^{2n+1}$ (páratlan hosszú, tehát kizárt, hogy illeszkedő) textre illesztjük, akkor mi történik? A csillag szépen mindig próbálja illeszteni az első alternatívát (ami most a $(.)\backslash 1$), illeszkedik, örül, továbbmegy, elér a string végéig, hopp, backtrackel és mivel a második és harmadik alternatívák is illeszkednek a $00$ stringre, ezért

végigpróbálja mind a $3^n$ lehetőséget

mielőtt rájönne, hogy nem illeszkedik.
Ez a fajta catastrophic behaviour egyébként mindig megtörténhet, ha olyan alternatívás regexet csillagozunk meg, ahol az alternatívák nem diszjunkt szóhalmazokra illeszkednek (!), ha a $w$ szó illeszkedik két alternatívára legalább, akkor a $w^n$ kezdetű, de végül nem illeszkedő inputokra exp ideig fut a motor. Azt már korábban láttuk, hogy ha egy csillagozott csoporthoz van olyan $w$ szó, hogy egy $w^k$ és egy másik, $w^m$ szó is illeszkedik a csoportra (pl illeszkedik rá az ababab és az abababab is, akkor $w=ab$, $k=3$, $m=4$, értjük), akkor egy $w^N$ alakú, végül nem illeszkedő inputtal exponenciális illesztést lehet belőle kicsalni. Itt arról van most szó, hogy ugyanaz a $w$ szó illeszkedik többféleképp a csoportra.

A backtracket többféleképp elkerülhetjük. Egyrészt átírhatjuk a regexet diszjunkt alternatívákra is: (?:(.)\1|0[^0]|[^0]0)*. Ez megoldja most a problémát, de nem mindig tudunk így tenni (pl. van, hogy nehéz meghatározni a két nyelv metszetét egyáltalán, és persze van, hogy nem lehet ilyen egyszerűen kitiltani a metszetet, mint most az egyetlen $00$ szót).
Egy másik lehetőség, hogy ún. atomi csoportot használunk. Az atomi csoport annyit tesz, hogy nem backtrackel semmiképp: ha talál egy illeszkedést, és később a motor visszatér rá backtrack üzemben, akkor (ellentétben az eddig látott csoportokkal, amik ekkor elkezdenek keresni egy másik illesztést, legközelebb egy harmadikat, stb..) nem is próbálkozik többet, hanem dobja tovább a backtracket. (Persze ha legközelebb megint illeszteni próbálják egy másik pozícióra, akkor ott ismét keres egy első találatot.) Ha tehát az eredeti regexünket (?>(.)\1|0.|.0)* formába írjuk át (az atomi csoport jele a $(?>\ldots)$, ahogy láthatjuk), az is megoldja a problémát és backtrack nélkül, mint a szél, illeszti a kifejezést. A három regex itt.
Azért persze ne rohanjunk minden csoportot atomira átírni, néha kell a backtrack. Pl. ha egy stringről azt akarjuk megtudni, hogy $ww$ alakú-e, arra egy példa regex a $(.^*)\backslash 1$, ahogy már láttunk pár ilyet. Ha az első csoportot atomira rakjuk, akkor hát az első probléma az lesz, hogy atomi csoport nem capture csoport (semelyik, $?$-lel kezdődő csoport sem az btw). Ezt még megoldhatjuk azzal, hogy az atomi csoportot berakjuk egy elfogóba: $((?>.^*))\backslash 1$, de ez így

csak az üres stringre fog illeszkedni

mert először a $.^*$ csoport a csillag mohósága miatt bescanneli az egész inputot, aztán rájön, hogy ezután nincs ott az egész input még egyszer, aztán visszalép egyet, úgy is megnézné, hogy ami utána következik, az az első csoport (most már eggyel rövidebb) tartalma-e, stb. Amikor eljut a string feléhez, ha $ww$ alakú, észre fogja venni, de ehhez $|w|$-szer kell backtrackelni és egy-egy karaktert elengedni. Atomi csoportnál nem indul el a backtrack, a csillag lenyel mindent, azt mondja, hogy az input hátralevő részére a backreference nem illeszkedik, és visszadobja az egészet találat nélkül.
Amikor viszont kockázat nélkül atomivá tehetünk egy csoportot, az pl. az az eset, mikor a csoport egy prefixmentes nyelvre illeszkedik: azaz, ha egy szóra illeszkedik, akkor annak semelyik valódi prefixére nem. Ekkor ugyanis ha bejön egy adott pozíciótól kezdve egy találat, akkor másik találatokat úgyse találnánk a backtrack során (hiszen a "másik" az vagy prefixe lenne a már meglevőnek, vagy a meglevő lenne prefixe neki, egyik se fordul elő prefixmentes nyelvnél). A példánkban levő "párok" nyelve az prefixmentes (mert minden szó konkrétan kettő hosszú benne, nyilván nem prefixei egymásnak), ezért ezt teljes nyugalomban atomivá tehetjük.

Technikailag javában az atomi csoportot betudták egyfajta kérdőjeles csoportnak, ami nekem furcsa egy kicsit, de ízlések és pofonok, erre hamarosan visszatérünk.