1. gyakorlat

Grep, egrep

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. Az egrep viselkedésével pontosan megegyezik a grep -E parancs hívása is, az E opcióról később még fogunk beszélni. A grep doksi szerint "egrep is the same as grep -E. fgrep is the same as grep -F. Direct invocation as either egrep or fgrep is deprecated", ezért mi a grep -E-t fogjuk használni.

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:

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

$ grep -E alma 01-alma.txt

ezt kapjuk:

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: a grep -E parancsnak ha első argumentumként (mintaként) egy stringet adunk, másodikként egy file nevét, akkor listázza a 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:

$ grep -E alma 01-alma.txt | wc -l
3
$ grep -E 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 a grep egy szövegben matchelni próbálja az R regexet, akkor azokat a sorokat engedi át a szűrőn, melyek (matematikailag) a Σ^*RΣ^* (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.

Case insensitive illesztés

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

$ grep -E -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.

Note:

Ugyanezt persze elérhetjük karakterosztállyal is, ha csak a regexnek csak egy részén szeretnénk ilyen illeszkedést.

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:

$ grep -E [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:

$ grep -E [ 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:

$ grep -E '\[' 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. Note: ha ékezetes betűket is akarunk kezelni, ellenőrizzük le, hogy az épp használt regex motorunk és az épp használt karakter encoding szerint az ékezetes betűk beletartoznak-e az intervallumba, vagy külön kell őket hozzáadnunk!
• 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:

$ grep -E '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:

$ grep -E '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

$ grep -E '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, a grep 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: a grep 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 grep 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:

$ grep -E '(alma|al)(l|malom)'

almalom

almalom

Itt két dolgot láthatunk:

• Egyrészt a grepnek ha nem adunk meg bemeneti filet, akkor ő is ugyanúgy, mint a sed (lásd később), 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 kipró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, a grep 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, amíg lehet), 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 a grep 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 grep 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 a greppel. 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: 2021-10-23 18:39:09