1. gyakorlat

A gyakorlat anyaga

Reguláris kifejezés "klasszikus" elemei, ismétlés

Grep és sed

Oprendszerekből már elvileg láttunk reguláris kifejezést (továbbiakban: regex) mintaillesztésre használni: egy hosszabb szövegfileból tudtuk leszűrni (filterezni) a regex által megadott mintára illeszkedő (azaz: a regexre matchelő) sorokat. Ez egy unix terminálban az egrep parancs használatával történhet.

Sima szöveg keresése

Mondjuk, hogy az aktuális munkakönyvtárunkban szerepel a 01-alma.txt file, kényelmi okokból ide is bemásolom a tartalmát:

1
2
3
4
5
6
7
8
szöveges file
nem tartalmaz semmi érdekes információt
nincs hatalma semmi fölött
Alma nagybetűvel is szerepelhet benne
vagy akár kiálthatjuk is, hogy ALMA
hosszan is: ALMAAA
persze a körte az egész mást jelent
többször is alma előfordulhat az almalma a sorban almalmalma

Ekkor kiadva a következő egrep parancsot (a dollár csak a unix terminál szokásos jele, a példákban azt fogja jelölni, hogy ezt a sort mi gépeltük be):

1
$ egrep alma 01-alma.txt

ezt kapjuk:

1
2
3
nem tartalmaz semmi érdekes információt
nincs hatalma semmi fölött
többször is alma előfordulhat az almalma a sorban almalmalma

A legegyszerűbb alkalmazás ez: az egrep parancsnak ha első argumentumként (mintaként) egy stringet adunk, másodikként egy file nevét, akkor listázza stringet részszóként tartalmazó sorokat, melyeket aztán a szokásos módon pipe-al továbbirányíthatunk másik processznek vagy az output csatorna felülvágásával kirakhatunk egy fileba:

1
2
3
4
5
6
7
$ egrep alma 01-alma.txt | wc -l
3
$ egrep alma 01-alma.txt > eredmeny.txt
$ cat eredmeny.txt
nem tartalmaz semmi érdekes információt
nincs hatalma semmi fölött
többször is alma előfordulhat az almalma a sorban almalmalma

Az előadásról ismert fogalmakat használva ha az egrep egy szövegben matchelni próbálja az R regexet, akkor azokat a sorokat engedi át a szűrőn, melyek (matematikailag) a Σ** (matematikai) reguláris kifejezésre illeszkednek, azaz substring illeszkedést vizsgál.

Persze nem csak erre alkalmazható, az alapelemekből különböző konstruktorokkal egyre bonyolultabb regexeket építhetünk fel. Amit eddig láttunk:

  • (általában) egy c karakter a c (egybetűs) stringre illeszkedik,
  • ha R és U két regex, akkor az RU regex illeszkedik egy u szóra, ha u=xy úgy, hogy R illeszkedik x-re, U pedig y-ra,
  • ha a grep parancs egy R regexet kap, akkor visszaadja az összes olyan sorát az input file-nak, melynek van olyan részszava, amire illeszkedik R.

Így illesztettük az alma szót: külön-külön az a, l, m és ismét az a regexek voltak, az al is egy regex, ami konkrétan az al stringre illeszkedik, stb.

A grep parancs terminálba printelve ki is színezi (ha defaultból nem, akkor a --color kapcsolóval már igen) azt a részszót, melyre az illeszkedést találta, vagy ha a minta többször is szerepel, akkor közülük néhányat kiemel:

többször is alma előfordulhat az almalma a sorban almalmalma

Alapvetően a szabvány azt mondja, hogy az illeszkedés a leghamarabb kell kezdődjön, ha ezen belül pedig van több lehetőség (amikor csak egy konkrét szót keresünk, ilyen nem lesz), arra is vannak szabályok, melyeket később látunk; majd az illesztés végétől kezdve (átlapolás nélkül!) folytatja a regexre match keresését. Így jött ki a fentebbi sorban a négy bejelölt előfordulás.

Search and replace: sed

Nagyon gyakran nem csak arra van szükség, hogy filterezzünk, hanem hogy kezdjünk is valamit a matchelő sorokban az illeszkedésekkel. A legegyszerűbb ilyen igény, amikor egy search-and-replace-t szeretnénk végrehajtani, amire egy unix terminálban a sed parancs biztosít egy simple interface-t:

1
2
3
4
5
6
7
8
9
$cat 01-alma.txt | sed 's/alma/szilva/g'
szöveges file
nem tartszilvaz semmi érdekes információt
nincs hatszilva semmi fölött
Alma nagybetűvel is szerepelhet benne
vagy akár kiálthatjuk is, hogy ALMA
hosszan is: ALMAAA
persze a körte az egész mást jelent
többször is szilva előfordulhat az szilvalma a sorban szilvalmszilva

A sed (stream editor) parancsól a következőket érdemes tudni:

  • az input streamről várja az inputot, ezért pipeoltuk bele az előző parancsnál a 01-alma.txt file tartalmát cattel. Persze egy sed 's/alma/szilva/g' <01-alma.txt hívás is pontosan ugyanezt tette volna, shell paraméterben átirányítva a standard inputot. Ha viszont közvetlen file feldolgozást szeretnénk tenni, átirányítás nélkül, sed 's/alma/szilva/g' 01-alma.txt is ugyanez történik.
  • a syntax alapvetően: s/regex/mire/, ami a regex regex-re talált illeszkedéseket kicseréli mire, erről, hogy mire is lehet cserélni, egyelőre maradjunk annyiban, hogy nem lehet akármilyen regexet odaírni (hiszen egyértelmű kéne legyen, hogy mire cseréli ki), de ahogy látjuk, egyszerű szóra ki lehet cserélni az illeszkedő substringeket.
  • ezzel a syntaxszal csak az első találatot cserélné le minden sorban:
1
2
3
4
5
6
7
8
9
$ sed 's/alma/szilva/' 01-alma.txt
szöveges file
nem tartszilvaz semmi érdekes információt
nincs hatszilva semmi fölött
Alma nagybetűvel is szerepelhet benne
vagy akár kiálthatjuk is, hogy ALMA
hosszan is: ALMAAA
persze a körte az egész mást jelent
többször is szilva előfordulhat az almalma a sorban almalmalma

a g mint "global" kapcsoló a végén jelenti, hogy ne replaceFirst, hanem replaceAll módban kérjük a cseréket. Azonban érdemes megfigyelnünk, hogy csak átlapolás nélkül fogja illeszteni és cserélni, ugyanúgy, mint az egrep is! így pl. az almalmalma szóból nem a szilvalmalma, majd szilvszilvalma, végül szilvszilvszilva lesz, hanem az eredeti szövegben átlapolás nélkül megtalált almákat cseréli szilvára, így kapjuk a fenti kimenetben is szereplő szilvalmszilva szót.

Case insensitive illesztés

Gyakorlati szempontból sokszor előfordul, hogy case insensitive akarunk illeszteni, ezt ez egrep-ben a -i kapcsolóval érjük el:

1
2
3
4
5
6
7
$ egrep -i alma 01-alma.txt 
nem tartalmaz semmi érdekes információt
nincs hatalma semmi fölött
Alma nagybetűvel is szerepelhet benne
vagy akár kiálthatjuk is, hogy ALMA
hosszan is: ALMAAA
többször is alma előfordulhat az almalma a sorban almalmalma

Látható, hogy most megtaláltuk az Alma és ALMA szavakat is. Ez praktikusan annyit tesz, hogy a regex-beli a illeszkedik az a és az A stringre is, stb. Ugyanezt persze elérhetjük karakterosztállyal is, ha csak a regexnek csak egy részén szeretnénk ilyen illeszkedést.

A sed is támogatja, szintén az i opció megadásával a case insensitive illesztést:

1
2
3
4
5
6
7
8
9
$ sed 's/alma/szilva/gi' 01-alma.txt
szöveges file
nem tartszilvaz semmi érdekes információt
nincs hatszilva semmi fölött
szilva nagybetűvel is szerepelhet benne
vagy akár kiálthatjuk is, hogy szilva
hosszan is: szilvaAA
persze a körte az egész mást jelent
többször is szilva előfordulhat az szilvalma a sorban szilvalmszilva

Itt tehát két opciót adtunk meg a search funkcióhoz: g, hogy minden találatot cseréljen le, i pedig, hogy az illesztés case insensitive történjen.

Karakterosztályok: []

A [] operátort használhatjuk olyan regex készítésére, mely egybetűs stringekre illeszkedik. Alapesetben csak fel kell soroljuk a szegletes zárójelek közt azokat a karaktereket, melyekre illeszkedni akarunk, így pl. [ae] illeszkedik az a és az e betűre is, tehát pl. a gr[ae]y regex matchel a gray és a grey szavakra (másra pedig nem), egy case insensitive alma illesztés pedig történhet akár egy [aA][lL][mM][aA] regex illesztésével is:

1
2
3
4
5
6
7
$ egrep [aA][lL][mM][aA] 01-alma.txt 
nem tartalmaz semmi érdekes információt
nincs hatalma semmi fölött
Alma nagybetűvel is szerepelhet benne
vagy akár kiálthatjuk is, hogy ALMA
hosszan is: ALMAAA
többször is alma előfordulhat az almalma a sorban almalmalma

Persze ebből látszik, hogy a [ egy speciális jel a regexekben, így ha pl. konkrétan a [ stringre keresnénk rá, az így nem fog menni:

1
2
$ egrep [ 02-speci.txt 
grep: Invalid regular expression

A pl. C-ből is ismert szokásos módon, backslash \ jelzi a speciális karakterek literálként való kezelését:

1
2
$ egrep '\[' 02-speci.txt 
tartalmaz [ jelet is és ] jelet is

Figyeljük meg, hogy ehhez már aposztrófok közé kell tegyük a regexet, hogy működjön; erre egyébként is jó, ha rászokunk.

A karakterosztályok megadására szintaxis:

  • Karakter intervallumot is megadhatunk kötőjellel: [a-z] illeszkedik az angol ábécé kisbetűire.
  • A karakter intervallumok elé és után is felsorolhatunk továbbiakat, akár más intervallumot is: [0-9a-fA-F] illeszkedik az összes hexa "számjegy"re.
  • Emiatt karakterosztályon belül a kötőjel speciális karakter. Ha a kötőjelre akarunk illeszkedni, akkor adjuk meg a karakterosztály elején vagy végén: [-a-z] illeszkedik az angol ábécé kisbetűire is és a kötőjel karakterre is.
  • Karakterosztályon belül így a ] jel is speciális karakter. Karakterosztályon belül a \ escapelés nem működik, ha a csukó szögletes jelet is be akarjuk venni a karakterosztályba, akkor ezzel kezdjük a karakterosztályt: []{}()[] illeszkedik az összes féle zárójelre. (És a két széle alkot egy párt, azon belül vannak a különféle zárójelek, kezdve a ]-vel.) Karakterosztályon belül megadott [ egyszerűen egy [ karakternek számít, a nem-első pozíción megadott ] viszont bezárja a karakterosztályt. Tehát pl. ha a [[]] regexet vesszük, akkor az a [[] és a ] regexek konkatenáltja, szorzata: az első egy karakterosztály, csak a [ jelre illeszkedik, a második pedig egy karakter, mert a ] karakterosztályon kívül nem speciális karakter, tehát az egész regex [[]] pontosan a [] stringre illeszkedik (és nem pedig egy, a kétféle szögletes zárójelre illeszkedő karakterosztály!)
  • Ha a karakterosztály első karaktere a ^ (caret, kalap) karakter, akkor ez egy negált karakterosztály: a karakterosztály maradék részében megadott karakterekre nem illeszkedik. Tehát pl. [^0-9] illeszkedik minden nem-számjegy karakterre, [^^] pedig minden karakterre, ami nem a caret.

Egy bármilyen karakter: .

Regexen belül a . (dot, pont) ugyanaz, mint a matematikai Σ: egy tetszőleges karakterre illeszkedik. Ezzel kapcsolatban:

  • Ha a pontra mint karakterre akarunk illeszteni, azt megtehetjük úgy is, hogy kiescapeljük: \. vagy karakterosztályba tesszük: [.], mert karakterosztályon belül a pont nem speciális karakter.

Alternatívák: |

Az előadásról + jelként megismert operátor, "vagyolás" szemantikailag a halmazelméleti uniót generálja. A legtöbb regex nyelvben a + jelentése nem ez, hanem az unáris iteráció (melynek jele az előadásban R+), de persze terminálban nem ütünk felső indexet). Unióra a |, pipe jelet használjuk. Így pl. a [0-9] karakterosztályt leírhatjuk akár 0|1|2|3|4|5|6|7|8|9-ként is, ugyanezt jelenti, azonban egykarakteres alternatívák helyett a javasolt megoldás mindenképpen a karakterosztály (ennek okaira később még rátérünk, mikor a regex illesztő motorok működéséről lesz szó).

Ha egy R|U alakú regexet próbálunk illeszteni egy pozíción, akkor matchelni fog, ha akár R matchel, akár U matchel. Amennyiben egyik sem matchel, akkor azon a pozíción nincs illeszkedés (és a grep motorja továbblép a következő pozícióra, hogy ott van-e illeszkedés).

Néhány példa:

$ egrep 'alma|semmi' 01-alma.txt

nem tartalmaz semmi érdekes információt

nincs hatalma semmi fölött

többször is alma előfordulhat az almalma a sorban almalmalma

Ebből azt láthatjuk, hogy a szorzás, konkatenáció, erősebb művelet, mint az alternatíva: az alma|semmi esetében van az alma regex és a semmi regex, ezek közül az almára próbálunk előbb illeszteni, és ha nem sikerült, akkor a semmire.

Nézzük most a következő két hívást:

$ egrep 'alma|al' 01-alma.txt

nem tartalmaz semmi érdekes információt

nincs hatalma semmi fölött

többször is alma előfordulhat az almalma a sorban almalmalma

$ egrep 'al|alma' 01-alma.txt

nem tartalmaz semmi érdekes információt

nincs hatalma semmi fölött

többször is alma előfordulhat az almalma a sorban almalmalma

Azt láthatjuk, hogy hiába cseréljük fel az al és alma regexek sorrendjét az alternatíván belül, az egrep motorja továbbra is az alma szavakat fogja matchelni. Ennek okát szintén később, a regex motorok under-the-hood megismerésekor fogjuk pontosabban megtudni, most a lényeg: az egrep a leghosszabb illeszkedést próbálja visszaadni. Effektíve tehát az al|alma így magában az al-ra csak akkor fog illeszkedni, ha ez nem egy alma szónak az eleje (de pl. ha az "alsó" szóra illesztjük ezt a regexet, akkor ennek az első két karakterére fog illeszkedni.

Ha kedvenc programozási nyelvünkben kipróbáljuk, akkor viszont nagyon jó eséllyel azt fogjuk tapasztalni, hogy az (al|alma) regexre a visszaadott matchek rendre az al stringekre fognak illeszkedni! (Ha még nem használtunk ilyet, akkor egy online lehetőség a RegExLib weblapon begépelni a szöveget és a regexet a két boxba, érdemes akár itt is mindent kipróbálni, ami az első gyakorlaton egrep példaként előjön.)

Egyelőre ebből azt érdemes megjegyezni, hogy ugyan az igaz, hogy egy stringben vagy van match, vagy nincs, de a konkrét visszaadott match olyankor, ha többféleképp is illeszkedhet a regex, különböző nyelvek motorjai esetében különbözhet is (és persze maguk a regexek is szintaktikailag kicsit másképp nézhetnek ki egyik nyelvben, mint másikban) - ez is számos hibának lehet a forrása, amikor nyelvek közt portolunk reguláris kifejezéseket, vagy copyzunk le stackoverflowról regexeket, amik egy nyelven megoldanak egy problémát, de a mienken pont nem biztos.

Csoportosítás, grouping

Az alternatívák és a szorzás alap sorrendje persze zárójelezéssel megváltoztatható: az (alma|al)fa regex az almafa és az alfa stringekre illeszkedik.

  • Látni fogjuk, hogy a () kerek zárójelek ún. capturing zárójelek, extra funkciót is ellátnak a legtöbb nyelvben. A grep és a sed esetében a non-capturing groupok nem támogatottak, de pl. javában ha csak a precedencia megváltoztatása a célunk a zárójelekkel, arra inkább a (?: nyitó- és ) zárójelet illik és érdemes használni, több okból, amit látni fogunk később, ebben (és a többi, PCRE motor esetében) a fenti regexet inkább (?:alma|al)fa jelölné.

A "leghosszabb match" nem mindig a leghosszabb

A félév során erre is vissza fogunk még térni, de összetett regex esetében nem mindig egyszerű meghatározni, hogy többféle match esetében pontosan mire is fog ezek közül illeszkedni a regexünk az inputból, ez nagyon sok hibának tud a forrása lenni. Például:

$ egrep '(alma|al)(l|malom)'

almalom

almalom

Itt két dolgot láthatunk:

  • Egyrészt az egrepnek ha nem adunk meg bemeneti filet, akkor ő is ugyanúgy, mint a sed, a streamről olvassa be az inputot, tehát pl lehet bele pipeolni is, vagy így interaktív módon tesztelgetni az illeszkedéseket.
  • Az almalom szó teljesen pirosan jött vissza, ami azt jelenti, hogy itt a matcher az első blokkból az al, a másodikból pedig a malom szót illesztette. Hiába igaz, hogy lokálisan az első csoportban az alma szó lett volna a leghosszabban illeszkedő, majd ha ezt megtartottuk volna, akkor a második blokkból az l is illeszkedett volna és ezzel az almal substring lenne, amit a matcher visszaad! A matcher ezek helyett az első blokkból a rövidebbet adja fel végeredményben illeszkedésre, mert azzal tudja elérni, hogy globálisan a leghosszabb substringre illeszkedő matchet adjon vissza.
  • Javascriptben viszont ha mindezt kiróbáljuk, akkor az almal jön vissza matchként...

Később látni fogjuk, hogy ennek mi az oka, mindenesetre ez adhat egy gyanút arra, hogy ehhez lehet, hogy ki kéne próbálni az összes lehetőséget, hogy a leghosszabbat adhassa vissza a motor - és lényegében ez is történik a legtöbb regex illesztő motor esetében, ami miatt egyes regexeknek egyes inputokra nagyon sokáig futhat az illesztése... majd azt is látni fogjuk, hogy a regex matcher motorok alapvetően kétféle, nagyon különböző implementációban léteznek, az egrep az egyik, "szélvész gyors, de nem mindent támogat, a szabványt meg végképp nem" kategória (mert véges automatát használ az illesztéshez), a javascript, java, php, c++, scala stb. regex könyvtárai viszont a "támogatja a szabványt, de van amin extrém módon belassul" kategória (mert backtracket használ az illesztéshez). A (PCRE-nek nevezett, Perl Compatible Regular Expression) szabvány pedig elég komplikáltan fogalmazza meg, hogy ha többféle illesztés is lehetséges, akkor melyiket kell visszaadni.

Opció, iteráció: ?, *, + és

Ha R egy regex, akkor R?, R* és R+ is azok, mégpedig:

  • R? mindenre illeszkedik, amire R, és még az üres stringre is (de a hossz preferálása miatt ez rendszerint azt jelenti, hogy az üres stringre csak akkor fog, ha R-re nem tud illeszteni).
  • R* illeszkedik minden olyan x szóra, amit fel lehet darabolni x=x1 x2 x3 ... xn alakba úgy, hogy R illeszkedjen mindegyik xi darabra. Itt n=0 is megengedett, azaz R* illeszkedni fog az üres szóra is.
  • Ezzel szemben, R+ a "pozitív sok ismétlés", annyiban különbözik az R*-tól, hogy a fentebbi képletben n>0 kell teljesüljön. (Ettől még lehetséges, de nem biztos, hogy illeszkedik az üres szóra! Hogyan lehetséges?)
  • Ha kicsit precízebben akarjuk az ismétlések lehetséges számát vezérelni, akkor R{n}jelöli, hogy pontosan n, R{,n} azt, hogy legfeljebb n (tehát akár 0 is), R{n,} azt, hogy legalább n, R{n,m} pedig, hogy legalább n és legfeljebb m darabra vághatjuk a szót úgy, hogy a darabok külön-külön illeszkednek R-re. Tehát pl. R* ugyanaz, mint R{0,}, R+ ugyanaz, mint R{1,} és R? ugyanaz, mint R{0,1}.

A precedenciáról: az iterációs műveletek erősebbek, mint a szorzás (aminél meg az alternálás gyengébb), de persze ezt zárójelezéssel ugyanúgy felülbírálhatjuk.

Feladatok

  • Használva az egrep színezett outputját, és - szükség esetén módosítva - a mai gyakorlat két input txt file-ját, gyakoroljuk a karakterosztályokkal való megadását egyes speciális karaktereknek és őket tartalmazó ill. nem tartalmazó karakterhalmazoknak.
  • Hozzunk létre egy nagyméretű szövegfile-t. Próbáljuk meg kimérni valamilyen módon, hogy okoz-e különbséget futásidőben, ha karakterosztályt alternatívaként adunk meg, vagy sem.
  • A parancssori egrep és sed hívásokon felül nézzük meg kedvenc mainstream programozási nyelvünk regex könyvtárát, hogy hogyan kell használni.
  • Gondoljuk át, hogy mire illeszkedik a (.+)+b reguláris kifejezés. Matcheljük az aaa, aaaa, stb. stringek ellen az egreppel. Gond nélkül le kell fusson, még az aaaaaaaaaaaaaaaaaaaaaaaaaa input string esetében is mérhetetlen kevés idő alatt. Teszteljük ugyanezt a regexet ugyanilyen inputokra pl. javascriptben vagy (szinte) bármi más mainstream nyelven (java, c, c++, perl, de valószínűleg a c# is ilyen lesz), akár a RegExLib weblap teszterjébe beírjuk, ennyi a-ra ez a regex illesztése el fog tartani egy jó darabig. Ha növeljük az a-k számát, előbb-utóbb a kedvenc nyelvünk alap regex könyvtára is valószínűleg timeoutolni fog.

Utolsó frissítés: 2020-09-18 21:00:32