2. gyakorlat

A gyakorlat anyaga

Pozícióra illeszkedő regex elemek. Capturing groupok és backreference

Pozícióra illeszkedő regex elemek és karakterosztály shorthandek

Az alábbi gyakori karakterosztályok a legtöbb regex motor elérhetőek rövidítésekkel:

  • számjegyek: \d ("digit"), a [0-9] osztályt rövidíti
  • alfanumerikus karakterek: \w ("word"), a latin ábécé betűi, számjegyek és az underscore illeszkedik rá.
  • whitespace: \s ("space"), szóköz, \t tab, \n újsor és pl. a \r carriage return is illeszkedik rá.
  • \D, \W és \S: az előzőek komplementerei.

Vannak továbbá karakterek közötti "pozíciókra" illeszkedő horgony ("anchor") jelek is:

  • ^: az első karakter előtti pozícióra illeszkedik
  • $: az utolsó karakter utáni pozícióra illeszkedik
  • \b: szóhatárra illeszkedik. Ez többféleképp történhet:
    • két karakter között, ha az egyik alfanumerikus, a másik whitespace
    • az első karakter előtt, ha alfanumerikus
    • az utolsó karakter után, ha alfanumerikus

Note: egyes regex motorok nem kezelik teljesen szinkronban a \b és a \w, \s kapcsolatát, pl. Javában a \w nem támogatja az Unicode karaktereket, de a \b igen -- ezt mindenképp érdemes tesztelni az aktuális munkanyelvünkben, hogy éppen az ékezetes vagy extended unicode karakterek hogyan viselkednek a worddel és a bounddal szemben.

Capturing groupok

A zárójeleknek a legtöbb regex motor esetében nem csak csoportosító, hanem capturing szerepe is van: amennyiben az input string illeszkedik a regexre, úgy (rendszerint 0-tól indexelt) csoportokba menti ki az input string egyes substringjeit. Mégpedig:

  • a 0. csoport (rendszerint) a teljes illeszkedő string (tehát teljes illesztés esetén az egész input) lesz,
  • az i. csoport, ahol i>0, pedig a regexben i-edik nyitójellel kezdődő részkifejezésre illeszkedő substring lesz.

Így például a ^\s*(.*)$ regex esetében a nulladik csoport a teljes input stringet fogja visszaadni, az első csoport pedig az input string, kivéve az elejéről letrimmelt whitespaceket.

A legtöbb programozási környezetben egy matches függvény hívása után, amennyiben a match értéke true, elkérhetjük a csoportok tartalmát, ez egy nagyon jól használható módszer információ kinyerésére strukturált szöveges infóból, és annak a cseréjére másra.

Java regex alapok

Javában a String osztály boolean matches(String regex) függvényével végezhetünk illesztést egy regexre, pl. "alma".matches(".*m.*") igaz lesz, "alma".matches("a") pedig hamis (ellentétben az egreppel, az itteni match függvény a teljes inputra próbálja illeszteni a regexet).

Ha ennél összetettebb feladatot szeretnénk elvégezni (mint pl. capturing groupokkal dolgozni), akkor a java.util.regex.Pattern és a java.util.regex.Matcher osztályok lesznek a barátunk, erre példa:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
String text = "  sanyi";
String regex = "\\s*(.*)";  //note: dupla escape kell, hogy így a regex \s*(.*) legyen
Pattern pattern = Pattern.compile( regex );  //statikus factory metódussal készítünk egy Pattern-t a regex szöveges reprezentációjából
Matcher matcher = pattern.matcher( text );   //ezt a patternt használhatjuk az input szövegen egy illesztésre, eredménye egy Matcher
if (matcher.matches()) {  //ami egyrészt tárolja, hogy illeszkedett-e a pattern a textre
  System.out.println("A minta illeszkedik a textre. Csoportok: ");
  for (int groupID = 0; groupID <= matcher.groupCount(); groupID++) { // és ha igen, akkor pl. a captured groupokat is elkérhetjük.
    System.out.println("Group " + groupID + ": " + matcher.group(groupID));
  }
} else {
  System.out.println("A minta nem illeszkedik a textre");
}

Non-capturing groupok

Mivel a capture tárolása is memóriát igényel illesztés közben, egyfajta extra bookmarkingot, továbbá a gond, hogy ha zárójeles regexet kell másoljunk egy meglévőben refaktoráláskor, elronthatja a csoportok indexelését, végül azért, mert sok nyelv csak legfeljebb tíz csoport capture-ülését támogatja, felmerül az igény, hogy legyen olyan zárójelünk is, ami tényleg csak a műveleti precedenciáért felel, és nem capture-öl. Ezek a non-capturing groupok és a jelük rendszerint a (?: nyitójel és ) csukójel.

Így például a ^(?:blue|red)*(green(?:blue|red|green)*)*^ regex egy olyan stringre illeszkedik, melyet a red, blue, green szavak valamilyen sorrendben, bármelyik bárhányszor, alkotnak, pl. redredgreenredgreenblue, illeszkedés esetén ez az eredeti string kerül a nulladik, és az első green, valamint az azt követő rész kerül majd az egyes csoportba, mert az első green előtti rész non-capturing groupban van. Továbbá szintén non-capturing groupban van a green utáni rész - az iterálton belüli group egyébként is csak egyet kapna el az illeszkedő substringekből.

Backreference

Az eddigi konstrukciók mind "regulárisak" voltak abban az értelemben, hogy lehet hozzájuk készíteni véges automatát, mely hatékony és gyors elemzést tesz lehetővé. Azonban ahogy a regexek tudásával szemben nőtt az igény, megjelentek a - formális nyelvek elmélete nevezéktana szerint - nem reguláris műveletek is (ezért is próbálom ezen a kurzuson elválasztani az elméleti "reguláris kifejezés" fogalmát a "regex"-től), az egyik első ilyen a backreference támogatása volt: reguláris kifejezés illesztésekor már menet közben illeszteni az inputot az egyik korábbi, capturing grouppal elkapott substringre. Ennek jele pl. Javában az \1..\9 jelzetek (csak az első 9 capturing groupra támogatja a backreferencet, emiatt is fontos, hogy ahol nem kell kimentsük a substringet, szokjunk rá a non-capturing syntaxra). Egy példával segítve a megértést: a ^.*\b(\w+)\b\s*\b\1\b.*$ regex olyan stringekre illeszkedik, melyekben van szóismétlés:

  • a ^.* rész mindenre illeszkedik a string elején,
  • majd következik egy \b word boundary, egy capture-ölt szó a \w+ részen, egészen egy következő \b szóhatárig, tehát egy teljes szót elfogunk az első csoportba,
  • majd jöhet esetleg némi whitespace,
  • eztán szóhatár (ez itt most redundáns), és a \1 azt mondja, hogy itt megpróbálja illeszteni az eddig elkapott első csoportot
  • ha illeszkedik és vége is lesz a szónak (\b˙szóhatár), akkor utána már .*$ bármit elfogadunk.

Ez így segíthet kiszűrni a pontos szóismétléseket -- egyelőre nem alkalmas a "Nagyon nagyon", eltérő kapitalizációval leírt szavak ismétlésének detektálására, de alakul.

Ezen a ponton megjegyezném, hogy mivel a szóismétlés detektálása nem megoldható automatával, ez a konstrukció - szemben a korábbiakkal - már tényleg kivezet a véges automata generálással megoldható problémák köréből és lényegében csak a backtracking alapú (vagy legalább hibrid) regex illesztő motorok képesek támogatni - melyek viszont sokszor érzékenyek a catastrophic backtrackingre, lásd később.

Feladatok

  • Írjunk regexet, mely első capturing groupjába stripeli a whitespace-t (tehát pl kettő három négy- ből a kettő három négy-et stripeli). Miért nem lesz jó "megoldás" a pl. itt is olvasható ^\s*(.*)\s*$ regex?
  • Írjunk regexet, mely pontosan akkor illeszkedik egy input sorra, ha benne páros sok a betű szerepel. (Ehhez talán először rajzoljunk egy automatát, aztán ezt konvertáljuk algoritmussal regexbe.)
  • Írjunk regexet, mely pontosan akkor illeszkedik egy input sorra, ha benne páros sok a betű vagy páratlan sok b betű szerepel.
  • Írjunk regexet, mely pontosan akkor illeszkedik egy input sorra, ha benne páros sok a betű és páratlan sok b betű szerepel.
  • Az előzőekben megadott páros-páratlan regexek illesztési sebességét mérjük ki Javában és egreppel is oly módon, hogy
    • generáljunk egy nagy szöveges filet, sok hosszú sorral, melyekben random a, b és c betűk vannak
    • futtassuk le az illesztést a regexünkkel, melyet készítettünk
    • futtassunk le egy olyan programot, mely két egyszerűbb regex egymás utáni illesztésével végzi el a feladatot
    • vonjunk le tanulságot!
  • Javában mérjük ki egy komplikáltabb reguláris kifejezés sok rövid sorra való illesztésével, hogy ha csak matchesre vagyunk kíváncsiak, akkor gyorsabb lehet-e a Pattern egyszeri létrehozása, majd illesztése a String.matches(String regex) függvény sorozatos hívásánál!
  • Írjunk regexet, mely egy hand history file-ból a kézbe osztott párokra illeszkedik (egy ilyen file-ban a releváns részben XY ZW a string, ahol X és Z értékek a [2-9TJQKA] karakterosztályból, Y és W pedig színek a [shdc] karakterosztályból, és akkor kell elfogadjuk a stringet, ha a két érték megegyezik)! Milyen regexet kapunk backreference-el és anélkül?
  • Oldjuk meg kedvenc programozási nyelvünkön a következő dekódoló feladatot (from ggmarkk prog1 stepik):
    • egy, csak kis- és nagybetűket (szorítkozhatunk mondjuk az angol ábécé kis- és nagybetűire) tartalmazó string tömörített változatát kapjuk
    • a tömörítés lényege, hogy az ismétlődő stringeket ismétlésszám + string alakba konvertálja valamilyen módon rekurzívan
    • ha egy karakter ismétlődik valahányszor, az csak egy szám + egy karakter egymás után írva, így pl. 4a az aaaa string egy tömörítése, 21b pedig a bbbbbbbbbbbbbbbbbbbbb stringet kódolja el
    • hosszabb ismétlődő stringeket egy szám + nyitójel + string + csukójel kódol, így pl. 3(ab) az ababab stringet, 4(a) az aaaa stringet, 0(abc) és 65() pedig az üres stringet kódolják
    • lehetnek egymásba ágyazva is a tömörítő jelzetek, így pl. ab3(c10a3(b)) az abcaaaaaaaaaabbbcaaaaaaaaaabbbcaaaaaaaaaabbb stringet kódolja.
    • a feladat egy ilyen módszerrel elkódolt string dekódolása, regex és capturing group használatával.

Utolsó frissítés: 2020-09-27 13:47:57