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 :)