Jak na hromadné nahrazování textu? · 2004. 12. 10. · •a na začátku řádky znak a •...

Jak na hromadneacute nahrazovaacuteniacute textu

Verze člaacutenku pro čteniacute httprootczclanekphp4id=77

11051999

Určitě se vaacutem již stalo že jste potřebovali v několika souborech změnit text podle vaacutem znaacutemeacuteho pravidla Možnaacute jste spustili svůj obliacutebenyacute textovyacute editor a začali jste ručně nahrazovat vyacuteskyty textu XYZ textem ABC Možnaacute jste použili funkci Replace zadali oba texty a pak jenom potvrzovali vyacuteměnu Pokud těch souborů bylo několik (slovy meacuteně než pět) pak se to daacute zvlaacutednout v rozumneacute době a při přijatelneacute naacutemaze Ale co když těch souborů je sto Nebo padesaacutet tisiacutec Pro tento přiacutepad vaacutem nabiacuteziacutem malyacute prograacutemek

Tento prograacutemek se sklaacutedaacute ze dvou souborů - perlovskeacuteho skriptu odstran a souboru s přiacutekazy pro editor VI Ne nelekejte se nebudete se muset učit pracovat s tiacutemto klasickyacutem editorem Jen jej budeme využiacutevat V naacutesledujiacuteciacutem textu budu řešit probleacutem odstraněniacute absolutniacutech adres v odkazech pro html soubory

Skript Perlovskyacute skript je velice triviaacutelniacute Vytvořte si soubor odstran (nebo použijte jinyacute naacutezev) a vložte do něj naacutesledujiacuteciacute text (tip pro začaacutetečniacuteky taženiacutem myši při stisknuteacutem leveacutem tlačiacutetku text označte Pak ve vedlejšiacutem okně či konzoli stisknutiacutem prostředniacuteho tlačiacutetka myši text vložiacutete do nějakeacuteho editoru)usrbinperl$soubory = `find -name html`file = split(^$soubory)foreach(file)

$neco = $_chop $necoprint Zpracovaacutevaacutem soubor $necosystem vi -f -s homeliteraklVI $neco

Pak soubor uložte a nastavte u něj praacutevo na spouštěniacute (přiacutekazem chmod +x odstran) Perlovštiacute guru si možnaacute budou rvaacutet vlasy při pohledu na zdrojovyacute koacuted nad jeho neefektivnostiacute pro mně je ale důležiteacute že to funguje Teď si jej trochu rozeberme Prvniacute řaacutedek spouštiacute interpretr perl Pokud jej nemaacutete v adresaacuteři usrbin pak změňte cestu

Na druheacutem řaacutedku do proměnneacute $soubory vložiacuteme všechny soubory ktereacute našel program find Tento program maacute obrovskeacute možnosti proto doporučuji přečiacutest si jeho manuaacutelovou straacutenku (man find) Pro naše uacutečely bude postačujiacuteciacute naacutesledujiacuteciacute popis

Prvniacute parametr určuje adresaacuteř kde se maacute začiacutet vyhledaacutevat V tomto přiacutepadě tečka označuje aktuaacutelniacute adresaacuteř Samozřejmě byste ale mohli použiacutet absolutniacute cestu Napřiacuteklad homeliteraklpublic_html Dalšiacutem parametrem je dvojice -name html Tento parametr určuje že se vyberou všechny soubory jejichž jmeacuteno splňuje druhaacute čaacutest podle shellovskeacute konvence Tedy můžete použiacutet zaacutestupneacute znaky jako jsou napřiacuteklad hvězdička (zastupuje nulu a viacutece libovolnyacutech znaků) otazniacutek (zastupuje přesně jeden libovolnyacute znak) a hranateacute zaacutevorky ([aeiouy] zastupuje jeden z vypsanyacutech znaků v tomto přiacutepadě samohlaacutesky

[âeiouy] zastupuje jeden znak kteryacute neniacute v uvedemeacute množině) Takže v tomto přiacutepadě se vyberou všechny soubory končiacuteciacute na html v aktuaacutelniacutem adresaacuteři a všech jeho podadresaacuteřiacutech

Ve zbyleacute čaacutesti skriptu se jedna proměnnaacute rozděliacute do pole promměnyacutech a v cyklu se pro každyacute nalezenyacute soubor vypiacuteše jeho jmeacuteno a zpracuje programem vi Čaacutest za znakem lt samozřejmě nahraďte spraacutevnou cestou

Soubor s přiacutekazyDo tohoto souboru se vklaacutedajiacute přiacutekazy pro editor vi Nazvěte si jej a umiacutestěte jak a kam chcete Nezapomeňte pak ale upravit předposledniacute řaacutedek skriptu Text souboru VI maacute obecně naacutesledujiacuteciacute tvar

gXYZsABCgwq

Na prvniacutem řaacutedku je regulaacuterniacute vyacuteraz na druheacutem přiacutekaz pro zapsaacuteniacute změn a ukončeniacute činnosti editoru vi Pokud vaacutem regulaacuterniacute vyacuterazy nic neřiacutekajiacute zkuste spustit vi a v něm napsat help pattern a zmaacutečknout enter Jinou možnostiacute je manuaacutelovaacute straacutenka regulaacuterniacutech vyacuterazů pro perl - man perlre

Při běžneacute praacuteci nahradiacutete text XYZ hledanyacutem textem a ABC novyacutem textem Pokud se vaacutem nechce pročiacutetat manuaacutely k regulaacuterniacutem vyacuterazům (vřele doporučuji je přečiacutest) snad vaacutem pomůže naacutesledujiacuteciacute vyacutetah kteryacute maacute daleko k uacuteplnosti

XYZ může byacutet běžnyacute text kteryacute hledaacutete Potom algoritmus porovnaacutevaacute prošlyacute text s požadovanyacutem textem a nalezne-li shodu změniacute jej na ABC V XYZ ale mohou byacutet zaacutestupneacute znaky Hvězdička stejně jako v shellu nahrazuje libovolnyacute počet libovolnyacutech znaků Tečka nahrazuje jeden libovolnyacute znak tj maacute stejnyacute vyacuteznam jako otazniacutek v shellu Hranateacute zaacutevorky se chovajiacute takeacute stejně jako v shellu vybiacuterajiacute jeden platnyacute znak z uvedeneacute množiny Pokud chcete najiacutet znak [ nebo ] napište před niacutem zpětneacute lomiacutetko To rušiacute vyacuteznam speciaacutelniacuteho znaku

Přiacuteklady

bull ahoj najde všechny slova obsahujiacuteciacute ahoj bull maka najde napřiacuteklad maka matka maska mařenka ma7558kla atd bull maka najde matka mamka maska marka atd bull ma[mt]ka najde jen matka mamka bull ma[^mt]ka najde maska marka ma8ka a dalšiacute kromě matka a mamka bull ma[n-z]ka najde maska marka matka a dalšiacute kde prostředniacute piacutesmeno ležiacute v rozmeziacute n

až z bull najde všechna dopřednaacute lomiacutetka bull najde hvězdičky

Dalšiacutem speciaacutelniacute znakem je ^ pokud neniacute použit jako negace ve vyacutečtu znaků Pak maacute vyacuteznam začaacutetku řaacutedku Obdobně znak $ ukazuje na konec řaacutedku Dvojice lt je zase naacutehradou začaacutetku slova a gt pak konce slova

Přiacuteklady

bull â na začaacutetku řaacutedky znak a bull les$ na konci řaacutedku znaky les bull â$ na řaacutedku je pouze znak a

To by snad mohlo pro uacutevod stačit Teď se vrhněme zpaacutetky na naacuteš přiacuteklad V html souborech ktereacute jsme si staacutehli autor použiacutevaacute absolutniacute odkazy i s naacutezvem jeho serveru Jenže my nejsme připojeni na internet a tak naacutem prohliacutežeč piacuteše že nemůže najiacutet ten server A naviacutec přiacutestup na disk je rychlejšiacute než přes internet (pokud nesediacutete u TEN-6000 ) ) Takže potřebujete odstranit napřiacuteklad řetězec httpwwwdomenaorg~uzivateladresar v několika desiacutetkaacutech souborů Soubor VI pak bude miacutet naacutesledujiacuteciacute tvar

gHREF=httpwwwdomenaorg~uzivateladresarsHREF=gwq

Všimněte si zpětnyacutech lomiacutetek rušiacuteciacutech vyacuteznam speciaacutelniacutech znaků V čaacutesti XYZ hledaacuteme řetězec HREF=httpwwwdomenaorg~uzivateladresar a ten nahradiacuteme řetězcem HREF= Tiacutemto způsobem nahradiacuteme skutečně jen odkazy nikoliv text Po spuštěniacute skriptu odstran ve spraacutevneacutem adresaacuteři se nahradiacute všechny vyacuteskyty a za několik sekund je tato praacutece hotova

Varovaacuteniacute

Regulaacuterniacute vyacuterazy mohou dělat něco jineacuteho než jste zamyacutešleli Proto pokud nejste guru přes regulaacuterniacute vyacuterazy raději si pořiďte zaacuteložniacute kopii dat Varoval jsem vaacutes

Nevyacutehody

bull potřebujete rozumět regulaacuterniacutem vyacuterazům bull žaacutedneacute uživatelskeacute rozhraniacute bull vše musiacutete napsat do obou souborů ručně

Vyacutehody

bull vše musiacutete napsat do obou souborů ručně ) bull automatizace nudnyacutech činnostiacute bull efektivita praacutece prudce naroste (v určityacutech situaciacutech) bull regulaacuterniacute vyacuteraz nic nepřehleacutedne a nezapomene

Tento skript se hodiacute vždy když potřebujete udělat nahrazeniacute v mnoha souborech Obvzlaacuteště se hodiacute při spraacutevě webovskyacutech straacutenek Už se nebudete muset baacutet změny struktury adresaacuteřů na vašem rozlehleacutem webovskeacutem serveru Pravda něco podobneacuteho a přiacutejemnějšiacuteho jsem nedaacutevno viděl v Homesitu Ani neviacutem kdy to ode mne zkopiacuterovali ) Snad to někomu pomůže

Nahrazovaacuteniacute textu II


24051999

V minuleacutem diacutele jsem popsal skript na daacutevkovou změnu textu Použil jsem při tom perl find a vi V tomto člaacutenku ukaacutežu dva dalšiacute způsoby jak udělat toteacutež jinyacutemi způsoby přičemž algoritmus Ondry Sureacuteho je nejefektivnějšiacute Berte tyto tři možnosti jako důkaz flexibility unixu

Prvniacute reakci jsem obdržel od [mailtoakelaticz] Honzy Dušaacuteka (omlouvaacutem se jestli se mi nepovedl převod z cestiny do češtiny) Jeho skript použiacutevaacute pouze kombinace perlu a find

find -name html -exec perl -ibak -p -e sstarenove

Co to dělaacute Kdykoliv find najde soubor kteryacute splňuje zadanaacute pravidla spustiacute perl ve speciaacutelniacutem modu A ten pomociacute svyacutech interniacutech regulaacuterniacutech vyacuterazů provede zaacuteměnu K tomuto skriptu bych měl vyacutehradu že se při každeacutem nalezeniacute souboru spouštiacute perl což je intepret A ne zrovna malyacute Naviacutec kdysi jsem psal nějakou aplikaci v perlu a rychlost vnitřniacutech regulaacuterniacutech vyacuterazů mě zklamala Ale to se mohlo mezitiacutem změnit

Dalšiacute dopis mi napsal [shadeglobecz] Ondra Suryacute Ten měl vyacutehrady k volbě programů (eufemicky řečeno) Miacutesto nich navrhl použiacutet sed a shell

binshfor $file in `find -name html` doecho -n Zpracovaacutevaacutem soubor $filemv $file $filebakcat $filebak | sed -e sXYZABC gt $fileecho -n hotovodone

Tento skript je ve sveacute podobě velmi podobnyacute meacutemu původniacutemu řešeniacute Miacutesto perlu ale použiacutevaacute shell (rychlejšiacute start zabiacuteraacute meacuteně paměti) a miacutesto vi program sed (rychlejšiacute běh meacuteně použiteacute paměti)

Jednočlennaacute komise ve složeniacute Leoš Literaacutek se jednomyslně shodla že viacutetězem se stal Ondra Suryacute Jeho řešeniacute je nejefektivnějšiacute a nejpřehlednějšiacute (a jaacute se po večerech budu učit programovat v shellu)

Tak mě napadaacute co udělat menšiacute soutěž Pošlete mi sveacute skripty jaacute je porovnaacutem otestuji a vyacutesledky zveřejniacutem Skript maacute

1 provaacutedět automatickou vyacuteměnu textu ve všech souborech splňujiacuteciacutech danou podmiacutenku 2 byacutet přehlednyacute a snadno použitelnyacute 3 byacutet vhodnyacute i pro začaacutetečniacuteky bez znalostiacute jednotlivyacutech programů 4 byacutet rychlyacute

Regulaacuterniacute vyacuterazy - čaacutest 1


06042000

Unix bez regulaacuterniacutech vyacuterazů je jako sex bez partnerapartnerky Daacute se to použiacutevat ale člověk o cosi zaacutesadniacuteho přichaacuteziacute Znalost regulaacuterniacutech vyacuterazů vaacutem daacute do rukou mimořaacutedně silnyacute naacutestroj pro praacuteci s textem

Jejich prostřednictviacutem můžete

bull vytahovat z textovyacutech dat uacutedaje ktereacute vaacutes zajiacutemajiacute bull přetvaacuteřet je do podoby kterou potřebujete bull vyhledaacutevat a nahrazovat v textovyacutech editorech a dalšiacutech programech

Zkraacutetka regulaacuterniacute vyacuteraz je univerzaacutelniacute pomocniacutek při praacuteci s textem Použiacutevaacute jej celaacute řada programů v Unixu Umožňujiacute prohledaacutevat soubory (grep egrep) editovat je (sed vi) analyzovat a vypočiacutetaacutevaacutet zajiacutemaveacute uacutedaje (awk) či nabiacutezejiacute plnohodnotnyacute programovaciacute jazyk kde si můžete dělat co vaacutes napadne (Perl Tk) Ale nebudeme se dlouho zdržovat propagandou a vzhůru do diacutela

Jednoducheacute vyacuterazy

Nejjednoduššiacutem regulaacuterniacutem vyacuterazem je obyčejneacute piacutesmeno - třeba r Když se v textu hledaacute řetězec kteryacute by tomuto regulaacuterniacutemu vyacuterazu vyhověl hledaacute se jednoduše piacutesmeno r Implicitně se (jak byacutevaacute v Unixu zvykem) rozlišujiacute malaacute a velkaacute piacutesmena Ve většině naacutestrojů však můžete tuto vlastnost vypnout

Jelikož i v těch nejjednoduššiacutech přiacutepadech člověk zpravidla hledaacute slovo a ne jedineacute piacutesmeno lze regulaacuterniacute vyacuterazy řetězit Použijete-li regulaacuterniacute vyacuteraz root představuje vlastně zřetězeniacute čtyř elementaacuterniacutech jednopiacutesmennyacutech regulaacuterniacutech vyacuterazů Vyacutesledkem je chovaacuteniacute ktereacute byste očekaacutevali - v textu se bude hledat slovo root

Vyhledaacutevaacuteniacute jednoduchyacutech slov je tou nejprimitivnějšiacute ale zaacuteroveň nejčastějšiacute aplikaciacute regulaacuterniacutech vyacuterazů

Přiacuteklad Řekněme že hledaacutete nejčerstvějšiacute soubory v aktuaacutelniacutem adresaacuteři Neviacutem jak vy ale jaacute v hlavě nenosiacutem jak se jmenuje volba přiacutekazu ls kteraacute zajistiacute uspořaacutedaacuteniacute podle času Takže zadaacutem man ls a naacutesledně si pomociacute time nechaacutem vyhledat prvniacute vyacuteskyt slova time Nebudu-li spokojen stisknu klaacutevesu n a poskočiacutem tak na dalšiacute vyacuteskyt

Popsaneacute hledaacuteniacute založeneacute na regulaacuterniacutech vyacuterazech dovedou oba programy použiacutevaneacute obvykle pro zobrazovaacuteniacute manuaacutelovyacutech straacutenek (a řady dalšiacutech textů) more i less Tyto programy zaacuteroveň ilustrujiacute jeden obecnyacute princip regulaacuterniacute vyacuteraz se typicky vyhledaacutevaacute jako podřetězec v jednotlivyacutech řaacutedciacutech textu

Libovolnyacute znak

Poměrně často dochaacuteziacute k situaciacutem kdy vaacutem na určiteacute čaacutesti hledaneacuteho řetězce nezaacuteležiacuteNapřiacuteklad chcete ve zdrojoveacutem textu HTML straacutenky vyhledaacutevat začaacutetky buněk v tabulkaacutech

ltTDgt a ltTHgt Až na třetiacute znak jsou oba řetězce shodneacute takže je lze vyhledaacutevatjedinyacutem regulaacuterniacutem vyacuterazem Pouze je třeba řiacuteci že na jeho třetiacutem znaku nezaacuteležiacute

Tuto činnost obstaraacute znak tečka () Při hledaacuteniacute jiacute vyhoviacute libovolnyacute znak kromě konce řaacutedku Nelze ji však ignorovat - nějakyacute znak jiacute program vždy musiacute přiřadit

PřiacutekladVyacuteše zmiacuteněneacute hledaacuteniacute řetězců ltTDampgt či ltTHgt obstaraacute regulaacuterniacute vyacuteraz ltTgt Přesněji řečeno mu vyhoviacute libovolnyacute čtyřznakovyacute řetězec kteryacute začiacutenaacute ltT a končiacute znakem gt

Ne až tak libovolnyacute znak

Použitiacutem tečky zcela rezignujete na hodnotu přiacuteslušneacuteho znaku V některyacutech přiacutepadech se to hodiacute jindy byste však potřebovali vyacuteběr omezit přiacutesněji Pak můžete saacutehnout po hranatyacutech zaacutevorkaacutech

Zapiacutešete-li do hranatyacutech zaacutevorek skupinu znaků bude tomuto regulaacuterniacutemu vyacuterazu vyhovovat praacutevě jeden z těchto znaků Napřiacuteklad vyacuterazu [xyz] vyhoviacute buď znak x nebo y nebo z Jestliže povoleneacute znaky tvořiacute interval můžete si ušetřit praacuteci a v hranatyacutech zaacutevorkaacutech uveacutest pouze jeho meze ktereacute spojiacutete pomlčkou

PřiacutekladPro vyhledaacuteniacute libovolneacute čiacuteslice posloužiacute regulaacuterniacute vyacuteraz [0-9] Předchoziacute hledaacuteniacute ltTDgt a ltTHgt bylo přiacuteliš benevolentniacute protože za T povolovalo libovolnyacute znak Lepšiacute je regulaacuterniacute vyacuteraz ltT[DH]gt kteryacute se skutečně omeziacute jen na uvedeneacute dvě značky

Jednotlivyacutech znaků a jejich intervalů můžete do hranatyacutech zaacutevorek napsat co hrdlo raacutečiacute Napřiacuteklad vyacuterazu [a0-9zl-nt] vyhoviacute libovolneacute z piacutesmen a l m n t z nebo libovolnaacute čiacuteslice

Kromě pomlčky se v hranatyacutech zaacutevorkaacutech vyskytuje ještě jeden speciaacutelniacute znak Pokud hned za oteviacuteraciacute hranatou zaacutevorkou zapiacutešete střiacutešku (^) bude celaacute skupina negovaacutena To znamenaacute že regulaacuterniacutemu vyacuterazu vyhoviacute libovolnyacute znak odlišnyacute od těch ktereacute jsou uvedeny ve skupině Napřiacuteklad [^0-9] vyhoviacute cokoli kromě čiacuteslice

Intervaly znaků vychaacutezejiacute z koacutedovaacuteniacute ASCII To znamenaacute že napřiacuteklad vyacuterazu [a-z] vyhoviacute libovolneacute maleacute piacutesmeno anglickeacute abecedy Doplnit velkaacute piacutesmena neniacute žaacutednyacute velkyacute probleacutem([a-zA-Z]) ale s českyacutemi znaky je potiacutež V některyacutech programech najdete konstrukce kteryacutemvyhoviacute i znaky českeacute abecedy univerzaacutelně platneacute elegantniacute řešeniacute však neexistuje

Speciaacutelniacute znaky

Možnaacute už vaacutes napadlo ale co když potřebuji vyhledat tečku Tedy obecněji jak vyřadit speciaacutelniacute vyacuteznam některyacutech znaků Obecnaacute odpověď na tuto otaacutezku zniacute zpětnyacutem lomiacutetkem V Unixu byacutevaacute zvykem že pokud speciaacutelniacutemu znaku předřadiacutete zpětneacute lomiacutetko vypnete tak jeho speciaacutelniacute chovaacuteniacute (a v některyacutech přiacutepadech praacutevě naopak jak uvidiacutete později)

PřiacutekladCelkem pohlednyacute regulaacuterniacute vyacuteraz hledaacute tři tečky Chcete-li vyhledat piacutesmeno uzavřeneacute v hranatyacutech zaacutevorkaacutech (tedy cosi jako [x]) použijte [[a-z]]

Uvnitř hranatyacutech zaacutevorek panuje specifickeacute prostřediacute Tečka zde představuje obyčejnou tečku a vyacuteznam ostatniacutech dvou speciaacutelniacutech znaků lze potlačit prostyacutem pořadiacutem Střiacuteška představuje negaci jen pokud je uvedena na samotneacutem začaacutetku a pomlčka sloužiacute jako oddělovač intervalu jen pokud maacute z obou stran jeho meze Takže napřiacuteklad vyacuterazu [âz-] vyhoviacute pouze jeden ze znaků ^ - a nebo z

Pokud maacute byacutet jedniacutem z povolenyacutech znaků pravaacute hranataacute zaacutevorka uveďte ji hned za oteviacuteraciacute Takže napřiacuteklad regulaacuterniacutemu vyacuterazu [][] vyhoviacute levaacute nebo pravaacute hranataacute zaacutevorka Pokud byste znaky uvnitř vnějšiacutech hranatyacutech zaacutevorek zapsali v opačneacutem pořadiacute ([[]]) vyacuteznam by seradikaacutelně změnil byl by interpretovaacuten jako [[] bezprostředně naacutesledovaneacute ] Čili vyhověl by mu jedině řetězec []

Shrnutiacute vyacuteraz vyhovuje

znak odpoviacutedajiacuteciacute znak

libovolnyacute znak

[znaky] jeden z uvedenyacutech znaků

[^znaky] libovolnyacute znak kromě uvedenyacutech

x vyřadiacutezapne speciaacutelniacute vyacuteznam znaku x



11042000

V předchoziacute čaacutesti jsem popsal zaacutekladniacute prvky regulaacuterniacutech vyacuterazů Konstrukce ktereacute jsem z nich vytvaacuteřel měly jednu společnou nevyacutehodu pevně danyacute počet znaků hledaneacuteho řetězce V dnešniacute čaacutesti se budu věnovat mechanismu opakovaacuteniacute Diacuteky němu lze zajistit že řetězec odpoviacutedajiacuteciacute regulaacuterniacutemu vyacuterazu může miacutet proměnlivou deacutelku

Opakovaacuteniacute vyacuterazu

Zaacutekladniacute konstrukciacute pro opakovaacuteniacute regulaacuterniacutech vyacuterazů je hvězdička () Znamenaacute žeregulaacuterniacute vyacuteraz bezprostředně před niacute se může zopakovat kolikraacutet to jenom jde

PřiacutekladVyacuterazu A tedy vyhoviacute libovolnyacute počet piacutesmen A zatiacutemco [0-9] ztělesňuje libovolně dlouhou posloupnost čiacuteslic (opakovanyacutem regulaacuterniacutem vyacuterazem je zde [0-9] tedy libovolnaacute čiacuteslice)

V řadě programovaciacutech jazyků je identifikaacutetor definovaacuten jako libovolně dlouhaacute posloupnost piacutesmen a čiacuteslic začiacutenajiacuteciacute piacutesmenem Pomociacute regulaacuterniacuteho vyacuterazu bychom jej zapsali jako [a-zA-Z][a-zA-Z0-9] Zdůrazňuji že opakovaacuteniacute se tyacutekaacute jen regulaacuterniacuteho vyacuterazu kteryacute je uveden bezprostředně před hvězdičkou Uvedenyacute vyacuteraz tedy znamenaacute praacutevě jeden vyacuteskyt [a-zA-Z](piacutesmeno) za niacutemž naacutesleduje libovolnyacute počet vyacuteskytů [a-zA-Z0-9] (piacutesmeno nebo čiacuteslice) Snad nejběžnějšiacutem opakovanyacutem vyacuterazem je tečka kteraacute v kombinaci s hvězdičkou () znamenaacute libovolnyacute řetězec znaků V souvislosti s opakovaacuteniacutem si dobře zapamatujte tři důležiteacute skutečnosti

bull do libovolneacuteho počtu opakovaacuteniacute se počiacutetaacute i nula bull opakovaacuteniacute se tyacutekaacute regulaacuterniacuteho vyacuterazu nikoli řetězce kteryacute je s niacutem porovnaacutevaacuten bull opakovaacuteniacute je hladoveacute - snažiacute se pozřiacutet co nejviacutec znaků

Přiacutepustnost nuloveacuteho počtu opakovaacuteniacute znamenaacute že opakovaneacutemu regulaacuterniacutemu vyacuterazu vždy může vyhovět i praacutezdnyacute řetězec Praktickyacutem důsledkem je že jen vzaacutecně daacutevaacute smysl vyhledaacutevat samotnyacute opakovanyacute vyacuteraz Zpravidla je třeba jej alespoň z jedneacute strany ohraničit něčiacutem povinnyacutem

Přiacuteklad Chcete-li vyhledat v textu všechna čiacutesla nemaacute smysl hledat libovolně dlouhou posloupnost čiacuteslic ([0-9]) protože posloupnost čiacuteslic nuloveacute deacutelky obsahuje každyacute řaacutedek (vyzkoušejte grep [0-9] soubor na libovolnyacute soubor - uvidiacutete že najde všechny jeho řaacutedky) Spraacutevně je třeba hledat alespoň jednu čiacuteslici tedy použiacutet regulaacuterniacute vyacuteraz [0-9][0-9]

Skutečnost že opakovaacuteniacute se tyacutekaacute regulaacuterniacuteho vyacuterazu nikoli srovnaacutevaneacuteho řetězce je velmi důležitaacute Zapiacutešete-li spojujete dva prvky symbol pro libovolnyacute znak a symbol opakovaacuteniacute Vyacuteslednou konstrukci lze chaacutepat dvěma způsoby Buď jako libovolnyacute počet libovolnyacutech znaků (opakovaacuteniacute regulaacuterniacuteho vyacuterazu) nebo že v textu může byacutet libovolnyacute znak a ten se pak

může opakovat kolikraacutet chce (opakovaacuteniacute ve zkoumaneacutem řetězci) Spraacutevnyacute je prvniacute vyacuteklad jinak bychom se z toho nejspiacuteš zblaacuteznili

Hladovost opakovaacuteniacute se projevuje tiacutem že opakovanyacute regulaacuterniacute vyacuteraz se vždy snažiacute roztaacutehnout na co největšiacute deacutelku - zahrnout do sebe co největšiacute počet znaků zkoumaneacuteho řetězce Proto když napřiacuteklad řetězec brambora srovnaacutete s regulaacuterniacutem vyacuterazem ra (libovolnyacute řetězec znaků začiacutenajiacuteciacute r a končiacuteciacute a) bude vyhovujiacuteciacutem řetězcem rambora (od prvniacuteho r až po posledniacute a)

Regulaacuterniacute vyacuterazy versus žoliacutekoveacute znaky

Začaacutetečniacuteci někdy zaměňujiacute regulaacuterniacute vyacuterazy s žoliacutekovyacutemi znaky Jistaacute podobnost tu skutečně je - oba prostředky umožňujiacute vytvaacuteřet jakeacutesi vzory ktereacute jsou porovnaacutevaacuteny se skutečnyacutemi daty Existujiacute mezi nimi dva zaacutesadniacute rozdiacutely Žoliacutekoveacute znaky se tyacutekajiacute naacutezvů souborů a zpracovaacutevaacute je interpret přiacutekazů (shell) Naproti tomu regulaacuterniacute vyacuterazy se zaobiacuterajiacute obsahem (textovyacutech) souborů a jejich interpretaci majiacute na starosti jednotliveacute programy (editory grep a podobně)

Přiacutepadnyacutem omylům ještě nahraacutevaacute podobnost některyacutech speciaacutelniacutech znaků mezi oběma konstrukcemi V tomto směru je zaacutehodno předevšiacutem miacutet na paměti že zatiacutemco v žoliacutekovyacutech znaciacutech představuje libovolnyacute řetězec v regulaacuterniacutech vyacuterazech se libovolnyacute řetězec zapisuje pomociacute

Mechanika srovnaacutevaacuteniacute

Pojmem srovnaacutevaacuteniacute (matching) se označuje proces kdy program hledaacute zda předloženyacute řetězec znaků odpoviacutedaacute regulaacuterniacutemu vyacuterazu či nikoli Zaacuteroveň se program snažiacute stanovit ktereacute čaacutesti řetězce odpoviacutedajiacute jednotlivyacutem čaacutestem regulaacuterniacuteho vyacuterazu

Dokud se zabyacutevaacutete pouze hledaacuteniacutem je pro vaacutes v podstatě nezajiacutemaveacute kde přesně byl danyacute vzor nalezen Ovšem když použiacutevaacutete regulaacuterniacute vyacuterazy k nahrazovaacuteniacute (a praacutevě v tom je jejich největšiacute siacutela) je tato informace velmi důležitaacute

Zaacutekladniacute princip srovnaacutevaacuteniacute je naacutesledujiacuteciacute začne se od začaacutetku řetězce Každeacutemu prvku regulaacuterniacuteho vyacuterazu se snažiacute přiřadit vždy co nejdelšiacute posloupnost znaků ze zkoumaneacuteho textu a teprve pak pokračuje srovnaacutevaacuteniacutem dalšiacutech čaacutestiacute Pokud to později nevyjde vraacutetiacute se zpět a zkusiacute přidělenyacute řetězec o jeden znak zkraacutetit Jestliže již zkraacutetil na minimum vše co zkraacutetit šlo a přesto se nepodařilo najiacutet shodu posune se na dalšiacute znak zkoumaneacuteho textu a vše se rozjede znovu

Přiacuteklad Podiacutevejme se jak by vypadalo srovnaacutevaacuteniacute regulaacuterniacuteho vyacuterazu r[0-9]o s řetězcem Brambory jsou na poli Při hledaacuteniacute by postupoval takto

1

2

3

4

5

Z přiacutekladu je vidět že diacuteky sveacute hladovosti regulaacuterniacute vyacuteraz zabere co největšiacute čaacutest řetězce - od prvniacuteho r až po posledniacute o Vyacuterazu je nakonec přiřazen řetězec ambory jsou na p Vyacuterazu [0-9] srovnaacutevaacuteniacute přiděliacute praacutezdnyacute řetězec Zdaacutenlivě proto že zkoumanyacute text neobsahuje žaacutedneacute čiacuteslice Ve skutečnosti však řetězec odpoviacutedajiacuteciacute tomuto vyacuterazu zůstane praacutezdnyacute vždy protože je umiacutestěn nesmyslně Předchaacuteziacute mu totiž obecnějšiacute regulaacuterniacute vyacuteraz s opakovaacuteniacutem Jakyacutekoli znak kteryacute by mohl vyhovovat [0-9] vyhovuje takeacute předchoziacutemu ktereacute jej diacuteky sveacute hladovosti sežere a na [0-9] nezbyde nic

Ze stejneacuteho důvodu když libovolnyacute řetězec znaků srovnaacutete s regulaacuterniacutem vyacuterazem bude prvniacutemu přiřazen celyacute zkoumanyacute řetězec a druheacutemu praacutezdnyacute řetězec

Přiacuteliš hladoveacute opakovaacuteniacute

Na hladovost opakovaacuteniacute je třeba si daacutevat pozor Diacuteky niacute se snadno může staacutet že opakujiacuteciacute se vyacuteraz pohltiacute i ty znaky se kteryacutemi jste nepočiacutetali Klasickyacutem přiacutekladem tohoto chovaacuteniacute je regulaacuterniacute vyacuteraz pro řetězec znaků v uvozovkaacutech

Začaacutetečniacuteci majiacute často tendenci uvažovat naacutesledovně řetězec v uvozovkaacutech to jsou oteviacuteraciacute uvozovky pak cokoli a na konci druheacute uvozovky To vyjaacutedřiacuteme regulaacuterniacutem vyacuterazem Probleacutem je že diacuteky hladovosti hvězdičky se tento regulaacuterniacute vyacuteraz roztaacutehne od prvniacutech uvozovek ve zkoumaneacutem řetězci až po posledniacute Takže napřiacuteklad když jej vypustiacutete na řetězec Volali Ahoacutej a Nazdaacuter dopadne to takto

Řešeniacutem je nepřipouštět v uzavřeneacutem řetězci libovolneacute znaky ale pouze znaky jineacute než koncovyacute V našem přiacutepadě cokoli kromě uvozovek takže tiacutem spraacutevnyacutem regulaacuterniacutem vyacuterazem bude [^]

Mimochodem - kdybyste na řetězec aplikovali vyacuteraz roztaacutehne se prvniacute na Volali Ahoacutej a a druheacute na Nazdaacuter Jelikož jsou v regulaacuterniacutem vyacuterazu povinneacute uvozovky nemůže prvniacute schramstnout všechno Ukousne si však co nejviacutec čiacutemž druheacute omeziacute na minimum



18042000

Prvniacute dvě čaacutesti našeho kraacutetkeacuteho seriaacutelu se zabyacutevaly těmi nejzaacutekladnějšiacutemi prvky regulaacuterniacutech vyacuterazů Přestože jsem napřiacuteklad v oblasti opakovaacuteniacute ještě zůstal dost dlužen rozhodl jsem se udělat malou přestaacutevku a věnovat se programům ktereacute regulaacuterniacute vyacuterazy použiacutevajiacute Dnes se tedy pokusiacutem popsat co a jak se s nimi daacute provaacutedět

grep a spol

Rodina programů grep sloužiacute k vyhledaacutevaacuteniacute v souborech Typickeacute použitiacute hledaacutete určityacute identifikaacutetor v haldě zdrojovyacutech koacutedů nebo chcete zjistit odkud se spouštiacute určityacute program Spuštěniacute je prosteacute

grep vzor seznam_souborů

Vzorem je regulaacuterniacute vyacuteraz Vyacutestup programu tvořiacute řaacutedky ktereacute vyhovujiacute zadaneacutemu vzoru (což nejčastěji znamenaacute že obsahujiacute zadaneacute slovo) Pokud program zkoumaacute viacutece než jeden soubor vypiacuteše zaacuteroveň před každyacute řaacutedek naacutezev souboru ze ktereacuteho pochaacuteziacute Prostřednictviacutemvoleb lze ovlivnit jeho chovaacuteniacute Těmi nejběžnějšiacutemi jsou

-i nerozlišovat malaacute piacutesmena od velkyacutech -w vybiacuterat jen řaacutedky na nichž vzoru vyhovuje celeacute slovo -v negovat vyacutesledek (vypisovat řaacutedky ktereacute nevyhovujiacute vzoru)-l vypisovat jen jmeacutena souborů -r rekurzivně prochaacutezet adresaacuteře (umiacute jen některeacute verze grepu)

grep je představitelem celeacute rodinky programů Majiacute podobnaacute jmeacutena i funkci lišiacute se jen v detailech Jejiacutemi standardniacutemi členy jsou tyto tři programy

grep klasickyacute grep vzorem může byacutet obyčejnyacute regulaacuterniacute vyacuteraz egrep vzorem je rozšiacuteřenyacute regulaacuterniacute vyacuteraz (viz přiacuteště) použiacutevaacute rychlejšiacute vyhledaacutevaciacute

algoritmus fgrep vzorem je jen obyčejnyacute řetězec znaků teoreticky nejrychlejšiacute ale praktickaacute měřeniacute

ukazujiacute opak zapomeňte na něj

Kromě nich existujiacute ještě některeacute dalšiacute pozoruhodneacute alternativy Asi nejzajiacutemavějšiacute je agrep (approximate grep) vyhledaacutevajiacuteciacute řetězce ktereacute se zadaneacutemu vzoru pouze podobajiacute Najde napřiacuteklad nejpodobnějšiacute nebo všechny takoveacute ktereacute se od vzoru lišiacute jen v daneacutem počtu znaků

Vřele doporučuji použiacutevat grep a spol pochaacutezejiacuteciacute z GNU projektu Ve srovnaacuteniacute s klasickyacutemi implementacemi je rychlejšiacute (použiacutevaacute lepšiacute algoritmy) a naviacutec umiacute některeacute přiacutejemnosti (třeba rekurzivniacute hledaacuteniacute) Zejmeacutena komerčniacute verze Unixu však majiacute tendenci trvat na originaacutelniacutech verziacutech Proto vyzkoušejte

grep --version

Dostanete-li chyboveacute hlaacutešeniacute nebo se ohlaacutesiacute někdo jinyacute než GNU grep maacutete co instalovat

sed

Program sed je neinteraktivniacute editor Zadaacutete mu sadu přiacutekazů a on podle nich zpracuje vstupniacute text De facto se jednaacute o naacutestroj pro vytvaacuteřeniacute editačniacutech filtrů

Regulaacuterniacute vyacuterazy se v sedu vyskytujiacute hned ve dvojiacute roli Lze je použiacutet k vyhledaacuteniacute řaacutedků na ktereacute se maacute vztahovat určityacute přiacutekaz Druhyacutem miacutestem vyacuteskytu regulaacuterniacutech vyacuterazů je přiacutekaz pro nahrazovaacuteniacute kteryacute maacute tvar svzornaacutehrada Vyhledaacutevaacute regulaacuterniacutem vyacuterazem zadanyacute vzor a pokud jej najde vložiacute na jeho miacutesto naacutehradu Za zaacutevěrečneacute lomiacutetko můžete připojit ještě volby Tou nejpoužiacutevanějšiacute je g (global) kteraacute zajistiacute nahrazeniacute všech vyacuteskytů vzoru na řaacutedku Standardně se totiž nahrazuje jen prvniacute

Přiacutekazy sedu majiacute obecně tvar

řaacutedky přiacutekaz

Počaacutetečniacute definice řaacutedků určuje na ktereacute řaacutedky vstupniacuteho textu se přiacutekaz bude vztahovat (chybiacute-li znamenaacute to všechny řaacutedky)

PřiacutekladŘekněme že jste změnili domeacutenu z kdesicz na jindecz Naviacutec chcete ze svyacutech WWW straacutenek odstranit pracovniacute texty - tedy veškereacute uacuteseky začiacutenajiacuteciacute ltDIV CLASS=pracovnigt a končiacuteciacute ltDIVgt Zajistiacute to naacutesledujiacuteciacute dvojice přiacutekazů skdesiczjindeczg ltDIV CLASS=pracovnigtltDIVgtd Prvniacute je klasickeacute nahrazeniacute ktereacute se bez určeniacute řaacutedků vztahuje na celyacute vstupniacute text Druhyacutempřiacutekazem je d (delete) ktereacutemu podlehnou všechny skupiny řaacutedků od řaacutedku vyhovujiacuteciacuteho prvniacutemu regulaacuterniacutemu vyacuterazu až po nejbližšiacute naacutesledujiacuteciacute kteryacute vyhovuje druheacutemu Všimněte si že lomiacutetko v ltDIVgt je třeba chraacutenit zpětnyacutem lomiacutetkem protože v přiacutekazu s maacute speciaacutelniacutefunkci oddělovače Tuto dvojici uložiacutete řekněme do souboru zmena a každou straacutenku pak podrobiacutete přiacutekazu sed -f zmena

Přiacuteklad tiše předpoklaacutedaacute že sveacute HTML straacutenky piacutešete stejně jako jaacute - tedy že značky ltDIVgt a ltDIVgt jsou na samostatneacutem řaacutedku Pokud ne vezme při mazaacuteniacute ze sveacute celyacute řaacutedek kteryacute některou z nich obsahuje vi

Unixoveacute textoveacute editory jejichž je vi nejklasičtějšiacutem představitelem typicky použiacutevajiacute regulaacuterniacute vyacuterazy k vyhledaacutevaacuteniacute textu a takeacute k jeho nahrazovaacuteniacute

Konkreacutetně v přiacutepadě vi zahajujete hledaacuteniacute stisknutiacutem klaacutevesy přiacutepadně (pokud chcete hledat směrem k začaacutetku dokumentu) Naacutesledně napište regulaacuterniacute vyacuteraz a stiskněte [Enter] Kurzor poskočiacute na nejbližšiacute naacutesledujiacuteciacutepředchoziacute řetězec vyhovujiacuteciacute zadaneacutemu vyacuterazu Chcete-li se přesunout na dalšiacute stiskněte n (next) pokud chcete hledat stejnyacutem směrem či N pro hledaacuteniacute směrem opačnyacutem Čili uacuteplně stejně jako v programech more a less

V kombinaci s tečkou (opakovaacuteniacute posledniacute editačniacute operace) tvořiacute n pořaacutedně silnou dvojku Pomociacute n si poskakujete na dalšiacute a dalšiacute vyacuteskyty hledaneacuteho řetězce a tu a tam na některyacute zopakujete editačniacute operaci stisknutiacutem tečky

Přiacutekaz pro nahrazeniacute maacute stejnou podobu jako u editoru sed Jedinyacutem rozdiacutelem je že pokud neuvedete řaacutedky implicitně se tyacutekaacute pouze aktuaacutelniacuteho řaacutedku Chcete-li nahradit vzor v celeacutemtextu použijte jako definici řaacutedků znak Nahrazovaacuteniacute patřiacute do přiacutekazoveacuteho režimu takže celyacute přiacutekaz musiacutete zahaacutejit dvojtečkou

PřiacutekladVyacuteše zmiňovanou naacutehradu kdesicz na jindecz by ve vi zajistil přiacutekaz

skdesiczjindeczg Některeacute verze vi určeneacute pro grafickeacute prostřediacute (napřiacuteklad gvim) nabiacutezejiacute i uživatelsky přiacutetulnou verzi tohoto přiacutekazu - viz obraacutezek Ortodoxniacute uživatel o ni samozřejmě nezavadiacute ani pohledem protože

1 Musiacute-li pracovat v textoveacutem režimu nebo na jineacutem počiacutetači nebude tato lahůdka k dispozici

2 s je rychlejšiacute a u novějšiacutech implementaciacute vi maacutete naviacutec historii přiacutekazů 3 Jen při použiacutevaacuteniacute s vypadaacutete jako skutečnyacute borec

Pokud použiacutevaacutete vim můžete k vyznačeniacute řaacutedků s vyacutehodou využiacutet vizuaacutelniacute režim Stiskněte klaacutevesu v a zvyacuterazněte požadovaneacute rozmeziacute řaacutedků Když potom stisknete editor automaticky vložiacute podivneacute rozmeziacute řaacutedků ltgt což znamenaacute od prvniacuteho vyznačeneacuteho řaacutedku po posledniacute Pozor nahrazeniacute se tyacutekaacute celyacutech řaacutedků ne jen vyznačeneacuteho textu v nich

Ostatniacute editory nabiacutezejiacute zpravidla podobneacute služby lišiacute se jen přiacutekazy kteryacutemi je vyvolaacutevaacutete

awk

Program awk realizuje specializovanyacute programovaciacute jazyk kteryacute umožňuje zpracovaacutevat textoveacute soubory s pevnou strukturou (např etcpasswd vyacutestup přiacutekazu ls -l a podobně)

Regulaacuterniacute vyacuterazy opět vystupujiacute ve dvou znaacutemyacutech roliacutech určujiacute řaacutedky kteryacutech se operace tyacutekaacute a vyskytujiacute se v nahrazovaacuteniacute

Zaacutekladniacutem probleacutemem awku je jeho jednostrannost Syntaktickyacute tvar programů je velmi nezvyklyacute a držet jej v hlavě kvůli uacutezce vymezeneacute skupině uacuteloh ktereacute dokaacuteže řešit se podle meacuteho soudu nevyplatiacute

Perl

Perl je pozoruhodnyacute programovaciacute jazyk kteryacute z hlediska regulaacuterniacutech vyacuterazů nabiacuteziacute dvě vysoce zajiacutemaveacute vlastnosti

1 Maacute nejbohatšiacute a nejpřehlednějšiacute sortiment regulaacuterniacutech vyacuterazů ze všech mně znaacutemyacutech naacutestrojů

2 Spojuje regulaacuterniacute vyacuterazy s běžnyacutemi programaacutetorskyacutemi konstrukcemi a la C

Ve srovnaacuteniacute s Perlem vaacutem sed či awk nemajiacute mnoho co nabiacutednout V posledniacute době pro neinteraktivniacute uacutepravy textů nepoužiacutevaacutem nic jineacuteho

Zaacutekladniacute konstrukciacute pro uplatněniacute regulaacuterniacutech vyacuterazů v Perlu je operaacutetor srovnaacuteniacute (=~) Jeho levyacutem operandem je řetězec znaků (typicky proměnnaacute) Pravyacute operand zaacutevisiacute na tom co s dotyčnyacutem řetězcem hodlaacutete provaacutedět Pokud vaacutem jde o prosteacute srovnaacuteniacute zda řetězec vyhovuje regulaacuterniacutemu vyacuterazu zapiacutešete sem obvyklyacute vzor uzavřenyacute mezi dvě lomiacutetka

Přiacuteklad Perl je velmi košatyacute a lze jej použiacutevat mnoha různyacutemi způsoby Začnu s minimalistickou variantou kdy provaacuteděnyacute program piacutešete přiacutemo do přiacutekazoveacuteho řaacutedku V tomto přiacutepadě se Perl použiacutevaacute s volbou -e kteraacute způsobiacute že naacutesledujiacuteciacute text bude interpretovaacuten rovnou jako přiacutekazy jazyka Zpravidla byacutevaacute kombinovaacutena s volbou -n diacuteky niacutež budou přiacutekazy provaacuteděny pro každyacute řaacutedek vstupniacuteho textu Takže třeba perl -ne print if Pepavypiacuteše ty řaacutedky vstupniacuteho textu ktereacute obsahujiacute řetězec Pepa Zaacuteroveň zde perl demonstruje skutečnost že si dokaacuteže hodně věciacute domyslet (chybiacute zde proměnnaacute i operaacutetor srovnaacuteniacute) Jaacute osobně se však teacuteto domyacutešlivosti raději straniacutem

Naacutesleduje serioacuteznějšiacute uacuteryvek z programu Vypiacuteše hlaacutešeniacute zda proměnnaacute $radek obsahuje podřetězec Pepa

if ( $radek =~ Pepa ) print Je tam

else print Neniacute tam

Chcete-li použiacutet regulaacuterniacute vyacuteraz k nahrazeniacute řetězce jinyacutem uveďte na praveacute straně srovnaacuteniacute obvyklou substitučniacute konstrukci svzornaacutehrada

Přiacuteklad A ještě jeden kondenzaacutet Naacutesledujiacuteciacute volaacuteniacute nahradiacute ve vstupniacutem textu všechna čiacutesla (celaacute čiacutesla nikoli jednotliveacute čiacuteslice) znakem X perl -pe s[0-9][0-9]Xg Použitaacute volba -p se podobaacute -n ale po provedeniacute přiacutekazů naviacutec pošle aktuaacutelniacute řaacutedek na standardniacute vyacutestup Všimněte si apostrofů kteryacutemi jsou obklopeny regulaacuterniacute vyacuterazy a přiacutekazy na přiacutekazoveacutem řaacutedku Zajišťujiacute že je interpret přiacutekazů předaacute v nezměněneacute podobě volaneacutemu programu a nebude se snažit interpetovat je jako sveacute speciaacutelniacute znaky

V programech se substituce zpravidla použiacutevaacute takto

$radek =~ s[0-9][0-9]Xg

Zde se nahrazuje v obsahu proměnneacute $radek Jak vidiacutete použitiacute regulaacuterniacutech vyacuterazů na proměnneacute obsahujiacuteciacute řetězce znaků je v Perlu velmi snadneacute Zajiacutemaveacute služby nabiacuteziacute takeacute funkce split(vzorřetězec) kteraacute řetězec znaků rozděliacute na čaacutesti ohraničeneacute vyacuteskyty zadaneacuteho regulaacuterniacuteho vyacuterazu Ideaacutelniacute pro zpracovaacuteniacute souborů jako je etcpasswd



28042000

Po kraacutetkeacute odbočce se vraciacuteme k opakovaacuteniacute Onu přestaacutevku věnovanou programům podporujiacuteciacutem regulaacuterniacute vyacuterazy jsem zařadil jednak abych předvedl nějakeacute praktickeacute využitiacute jednak proto že již nebude možneacute skryacutevat existenci různyacutech dialektů Různeacute programy totiž podporujiacute lehce odlišneacute varianty regulaacuterniacutech vyacuterazů Ty o kteryacutech jsem mluvil až dosud byly společneacute pro všechny Dnes už naraziacuteme na některeacute odlišnosti

Omezenyacute počet opakovaacuteniacute

Zaacutekladniacutem probleacutemem klasickeacute opakovaciacute hvězdičky je že je nekontrolovatelnaacute Pro některeacute situace potřebujete přesnějšiacute vyjadřovaacuteniacute

Vaše touhy uspokojiacute konstrukce minmax Opět se vztahuje na bezprostředně předchaacutezejiacuteciacute regulaacuterniacute vyacuteraz a řiacutekaacute že se maacute opakovat alespoň min-kraacutet nanejvyacuteš však max-kraacutet Jako každeacute opakovaacuteniacute i tohle je hladoveacute takže se snažiacute uplatnit vždy co největšiacute z povoleneacuteho počtu opakovaacuteniacute

PřiacutekladRegulaacuterniacutemu vyacuterazu i13 vyhoviacute řetězce i ii nebo iii

Tvar tohoto opakovaacutetka je velmi variabilniacute Pokud chybiacute horniacute mez (min) znamenaacute to že maximaacutelniacute počet opakovaacuteniacute je neomezenyacute Jestliže v konstrukci použijete jen samotneacute čiacuteslo (počet) musiacute se regulaacuterniacute vyacuteraz opakovat přesně danyacute počet-kraacutet

Přiacuteklad Regulaacuterniacute vyacuteraz pro rodneacute čiacuteslo by vypadal takto [0-9]6[0-9]34

Šest čiacuteslic lomiacutetko a ještě tři nebo čtyři čiacuteslice A již tu maacuteme prvniacute odlišnost V některyacutech verziacutech regulaacuterniacutech vyacuterazů (napřiacuteklad v Perlu) se při omezovaacuteniacute počtu opakovaacuteniacute před složenyacutemi zaacutevorkami nepiacutešiacute zpětnaacute lomiacutetka Zapiacutešete-li zde znamenaacute to že zkoumanyacute text maacute obsahovat znak Perl maacute pro tuto specialitu dobrou omluvu zavedl pravidlo že kombinace zpětneacuteho lomiacutetka a znaku odlišneacuteho od piacutesmena či čiacuteslice nikdy nemaacute speciaacutelniacute vyacuteznam a vždy představuje dotyčnyacute znak

Nejpopulaacuternějšiacute opakovačky

Dva velmi populaacuterniacute přiacutepady opakovaacuteniacute si vysloužily svůj vlastniacute speciaacutelniacute znak Prvniacutem je alespoň jeden vyacuteskyt - tedy cosi velmi podobneacuteho klasickeacute opakovaciacute hvězdičce až na to že opakovanyacute regulaacuterniacute vyacuteraz nelze vynechat Stejneacuteho efektu dosaacutehnete konstrukciacute 1 ale to je přiacuteliš složiteacute psaniacute Proto se alespoň jeden vyacuteskyt předchoziacuteho regulaacuterniacuteho vyacuterazu zapisuje znakem plus (+)

Druhou populaacuterniacute situaciacute je nepovinnyacute (čili nanejvyacuteš jeden) vyacuteskyt Opět jej lze zapsat pomociacute 01 ale kratšiacute je otazniacutek ()

Dialekty regulaacuterniacutech vyacuterazů se u teacuteto dvojice znaků opět silně rozchaacutezejiacute Programy použiacutevajiacuteciacute klasickeacute regulaacuterniacute vyacuterazy (grep sed vi) jim předřazujiacute zpětneacute lomiacutetko (+ a ) Generace kteraacute implementuje rozšiacuteřeneacute regulaacuterniacute vyacuterazy (egrep awk Perl) je piacuteše bez něj (+a )

PřiacutekladAlespoň jedna čiacuteslice se tedy v grep sed a vi vyjaacutedřiacute pomociacute [0-9]+ zatiacutemco egrep awk či Perl nabiacuteziacute kratšiacute [0-9]+ Zaacutepis můžeme lehce rozšiacuteřit na regulaacuterniacute vyacuteraz pro celeacute čiacuteslo nepovinneacute znameacutenko naacutesledovaneacute alespoň jednou čiacuteslici V klasickyacutech regulaacuterniacutech vyacuterazech to bude [-+][0-9]+ zatiacutemco v rozšiacuteřenyacutech [-+][0-9]+

Pozice

Vyacuterok dejte mi pevnyacute bod a pohnu zeměkouliacute jistě znaacutete Nahliacuteženo jeho optikou byly všechny naše dosavadniacute regulaacuterniacute vyacuterazy poněkud neukotveneacute Řetězec kteryacute jim vyhovuje se mohl vyskytovat kdekoli ve zkoumaneacutem textu Občas však člověk musiacute byacutet přiacutesnějšiacute

Proto regulaacuterniacute vyacuterazy nabiacutezejiacute několik speciaacutelniacutech pozičniacutech znaků Těmi nejznaacutemějšiacutemi jsou střiacuteška (^) kteraacute ztělesňuje začaacutetek řaacutedku (resp zkoumaneacuteho řetězce znaků) a dolar ($) označujiacuteciacute jeho konec

Přiacuteklad grep ^ vaacutem tedy najde řaacutedky začiacutenajiacuteciacute znakem grep [0-9]$ řaacutedky končiacuteciacute čiacutesliciacute a konečně grep ^-+$ řaacutedky složeneacute pouze z pomlček (nikoli však praacutezdneacute)

Dalšiacutem vyacuteznamnyacutem miacutestem je hranice slova Ve většině regulaacuterniacutech dialektů maacutete k dispozici konstrukci lt kteraacute označuje začaacutetek slova a gt ktereacute vyhoviacute pouze jeho konec

Perl nerozlišuje začaacutetek slova od konce maacute pouze speciaacutelniacute znak b pro hranici slova (tedy začaacutetek nebo konec) Ovšem dlužno přiznat že z okolniacuteho kontextu byacutevaacute zřejmeacute zda b může vyhovět začaacutetek nebo konec slova Jako cenu uacutetěchy ziacuteskaacutevaacutete v Perlu ještě B ktereacutemu vyhoviacute libovolneacute miacutesto ve zkoumaneacutem řetězci kromě hranice slova Jednaacute se tedy o negaci b

Přiacuteklad Zajiacutemajiacute-li vaacutes všechny řaacutedky na nichž se piacutesmeno a vyskytuje v roli jednopiacutesmenneacute spojky nasaďte grep ltagtToteacutež v Perlu (až na to že se nevypisujiacute jmeacutena souborů) by zajistil přiacutekazperl -ne print if babPokud se naacutezvů souborů nehodlaacutete vzdaacutet použijte

perl -ne print $ARGV$_ if bab Shrnutiacute vyacuteraz znamenaacute

libovolnyacute počet opakovaacuteniacute předchůdce

+ nebo + alespoň jeden vyacuteskyt předchůdce

nebo nanejvyacuteš jeden vyacuteskyt předchůdce

minmax nebo minmax alespoň min a nanejvyacuteš max vyacuteskytů předchůdce

^ začaacutetek řaacutedku

$ konec řaacutedku

lt nebo b začaacutetek slova

gt nebo b konec slova



09052000

Na paacutetou čaacutest seriaacutelu jsem si pošetřil snad nejsilnějšiacute prvek regulaacuterniacutech vyacuterazů - jejich paměť Regulaacuterniacute vyacuteraz si totiž dokaacuteže zapamatovat řetězec kteryacute vyhověl jeho čaacutesti a později jej použiacutet Největšiacute služby tento mechanismus odvede při nahrazovaacuteniacute

Zapamatuj a vzpomeň si

Prostředky pro zapamatovaacuteniacute jsou směšně jednoducheacute Čaacutest kterou si maacute regulaacuterniacute vyacuteraz podržet v paměti prostě ohraničiacutete konstrukcemi ( a ) Jistě si vzpomiacutenaacutete že v Perlu nemaacutenealfanumerickyacute znak předchaacutezenyacute zaacutevorkou nikdy speciaacutelniacute vyacuteznam takže tam se ke stejneacutemu uacutečelu použiacutevajiacute obyčejneacute zaacutevorky Takovyacutech uacuteseků můžete v regulaacuterniacutem vyacuterazu miacutet hned několik Dokonce je lze i vzaacutejemně vnořovat

Když později chcete použiacutet zapamatovanyacute řetězec napište čiacuteslo kde čiacuteslo je pořadoveacute čiacuteslo zapamatovaneacuteho uacuteseku Pořadovaacute čiacutesla začiacutenajiacute jedničkou a rozhoduje o nich pořadiacute leveacute (oteviacuteraciacute) zaacutevorky zapamatovaacutevaneacute sekvence

PřiacutekladPodrobiacutete-li řaacutedek ze souboru etcpasswd regulaacuterniacutemu vyacuterazu ^([^])[^]([^]) bude 1 obsahovat přihlašovaciacute jmeacuteno a 2 jemu odpoviacutedajiacuteciacute identifikaacutetor (UID)

O dobrodiniacute paměti jste ochuzeni u programů egrep a awk Jejich algoritmus pro srovnaacutevaacuteniacute regulaacuterniacutech vyacuterazů nepodporuje zapamatovaacuteniacute (a z principiaacutelniacutech důvodů ani podporovat nemůže) V přiacuteštiacute čaacutesti se k teacuteto otaacutezce vraacutetiacutem podrobněji

Použitiacute při hledaacuteniacute

Použitiacute zapamatovanyacutech čaacutestiacute při vyhledaacutevaacuteniacute je poměrně vzaacutecneacute Řečeno mluvou politiků společenskaacute potřeba takoveacute služby je celkem malaacute Přiacuteklady sice existujiacute nicmeacuteně byacutevajiacute takoveacute školometskeacute Tak si nějakeacute zkusiacuteme

Přiacuteklad Hezkou a zcela neužitečnou ilustraciacute zapamatovaacuteniacute je hledaacuteniacute palindromů (slov kteraacute se nezměniacute když je čtete pozadu) Tak napřiacuteklad vyacuterazu lt()()21gt vyhoviacute praacutevě a pouze pětiznakovyacute palindrom (např radar či rotor) Prvniacute dva znaky slova si zapamatuje za nimi naacutesleduje třetiacute libovolnyacute znak čtvrtyacute musiacute byacutet stejnyacute jako zapamatovanyacute druhyacute a paacutetyacute znak se musiacute shodovat s prvniacutem

Přiacuteklad Zkusiacutem něco co by alespoň vzdaacuteleně připomiacutenalo reaacutelnyacute život Řekněme že maacutete vyacutestupy z jakeacutehosi algoritmu - na každeacutem řaacutedku sadu čiacutesel oddělenyacutech mezerami Každyacute řaacutedek zaacuteroveň končiacute spraacutevnyacutem vyacutesledkem Pokud algoritmus pracuje spraacutevně posledniacute dvě čiacutesla na řaacutedku jsou totožnaacute Hledaacuteme tedy řaacutedky ve kteryacutech se posledniacute čiacuteslo lišiacute od předposledniacuteho K řešeniacute posloužiacute grep s negovanou podmiacutenkou (volba -v) grep -v ([^ ]+) +1$ Vzor začiacutenaacute mezerou před předposledniacutem čiacuteslem Za niacute naacutesleduje nepraacutezdnaacute posloupnost nemezerovyacutech znaků ([^ ]+) kteraacute se zapamatuje Po niacute naacutesleduje alespoň jedna mezera ( +) a znovu stejnaacute posloupnost za kterou už je jen konec řaacutedku

Použitiacute při nahrazovaacuteniacute

Daleko častěji se zapamatovaneacute řetězce vyskytujiacute v přiacutekazech pro nahrazovaacuteniacute Diacuteky nim si můžete ze vstupniacutech dat vytaacutehnout informace ktereacute vaacutes zajiacutemajiacute a posklaacutedat si je do tvaru kteryacute potřebujete

Přiacuteklad Běžnyacute probleacutem všedniacuteho dne potřebujete u skupiny souborů změnit přiacuteponu z htm na html Pro podobneacute uacutečely sice existujiacute různaacute udělaacutetka ale je třeba si je doinstalovaacutevat a praacutece s nimi nebyacutevaacute uacuteplně snadnaacute takže se podiacutevejme jak posloužiacute standardniacute naacutestroje ktereacute najdete v každeacutem Unixu

Postup je jednoduchyacute obstaraacutete si seznam jmen souborů každeacute jmeacuteno pak změniacutete na přiacutekaz mv stareacute noveacute a tyto přiacutekazy provedete Popsanyacute postup lze realizovat třeba takto

ls htm gt seznam sed s()mv 1 1l seznam gt akce chmod a+x akce akce rm seznam akce Uznaacutevaacutem že prosteacute připojeniacute l na konec jmeacutena souboru je dosti snadnou modifikaciacute Složitějšiacute věci však znamenajiacute jen uacutepravu přiacutekazu s Napřiacuteklad

změnu přiacutepony z doc na txt by zajistilo s()docmv 1doc 1txt -zapamatuje si jen vlastniacute jmeacuteno souboru a přiacutepony jsou explicitně vyjmenovaacuteny

Přiacuteklad A teď něco drsnějšiacuteho Chtěl bych ze souboru etcpasswd vyrobit seznam domaacuteciacutech straacutenek uživatelů Takže potřebuji řaacutedky transformovat z původniacute podoby uživatelhesloUIDGIDvlastniacute jmeacuteno na ltA HREF=~uživatelgtvlastniacute jmeacutenoltAgt Kyacuteženyacutem substitučniacutem přiacutekazem kteryacute to zařiacutediacute je s([^])([^])3([^])ltA HREF=~1gt3ltAgt Jak vidiacutete prostřednictviacutem zaacutevorek lze předepsat počet opakovaacuteniacute i rozsaacutehlejšiacutemu uacuteseku regulaacuterniacuteho vyacuterazu - zde se třikraacutet opakuje skupina [^] V takovyacutechto situaciacutech zaacutevorky většinou nesloužiacute k zapamatovaacuteniacute (i když si pochopitelně něco zapamatujiacute) ale čistě k vymezeniacute opakovaneacute čaacutesti Ta maacute - bez ohledu na skutečnyacute počet opakovaacuteniacute - jen jedineacute pořadoveacute čiacuteslo Proto se zaacutevěrečneacute zapamatovaneacute jmeacuteno uložiacute jako 3

Probleacutemem regulaacuterniacutech vyacuterazů je že jsou velmi kompaktniacute Vyznat se ve vyacuteše citovaneacutem substitučniacutem přiacutekazu zabere chviacuteli času (zpravidla viacutece než jej vymyslet) V Perlu si můžete vytvořeniacute seznamu rozložit nejprve řaacutedek rozkraacutejiacutete v miacutestě vyacuteskytu dvojteček a z vyacutesledneacuteho pole pak použijete prvniacute a paacutetyacute prvek (indexy 0 a 4)

while ( $radek = ltgt ) uzivatel = split( $radek) print ltA HREF=~$uzivatel[0]gt print $uzivatel[4]ltAgtn

Program uložte třeba do souboru htmlseznam a spusťte perl htmlseznam etcpasswd

Shrnutiacute vyacuteraz vyacuteznam

(vyacuteraz) zapamatuje si text vyhovujiacuteciacute vyacuterazu

1 prvniacute zapamatovanyacute řetězec



22052000

Od minula si umiacutete nalezeneacute věci zapamatovat a později použiacutet To je v reaacutelneacutem životě šeredně nebezpečnaacute vlastnost Napřiacuteklad jste teď nepoužitelniacute jako voliči Abyste se opět stali politicky korektniacutemi naučiacutem vaacutes pozměnit co jste si zapamatovali

Modifikaacutetory

Kdybych chtěl byacutet protivně korektniacute vlastně bych o modifikaacutetorech neměl mluvit protože oficiaacutelně nepatřiacute mezi regulaacuterniacute vyacuterazy Použiacutevajiacute se však v těsneacute součinnosti s nimi takže zpravidla byacutevajiacute haacutezeny do jednoho pytle

Modifikaacutetory jsou konstrukce ktereacute změniacute naacutesledujiacuteciacute znaky Jejich typickeacute použitiacute nese naacutesledujiacuteciacute znaky

bull sloužiacute k vzaacutejemneacutemu převodu malyacutechvelkyacutech piacutesmen bull vyskytujiacute se ve druheacute (nahrazujiacuteciacute) čaacutesti přiacutekazu pro nahrazovaacuteniacute řetězců bull byacutevajiacute aplikovaacuteny na zapamatovaneacute řetězce

Těmi nejjednoduššiacutemi jsou u a l Prvniacute z nich převede naacutesledujiacuteciacute znak z maleacuteho piacutesmene na velkeacute (upper case) Naacutesleduje-li cokoli jineacuteho než maleacute piacutesmeno zůstane znak beze změny Konstrukce l funguje praacutevě opačně - převaacutediacute naacutesledujiacuteciacute velkeacute piacutesmeno na maleacute (lower case)

Uvedeneacute modifikaacutetory se tyacutekaly vždy jen jedineacuteho znaku kteryacute naacutesleduje bezprostředně za nimi Pokud použijete velkeacute piacutesmeno (U či L) zasaacutehne modifikaacutetor všechny naacutesledujiacuteciacute znaky až po konec řetězce nebo nejbližšiacute naacutesledujiacuteciacute vyacuteskyt E kteraacutežto konstrukce sloužiacute jako ukončujiacuteciacute

Bohužel jsou modifikaacutetory poměrně vzaacutecneacute grep a jeho bratři nedovedou nahrazovat takže u nich nemajiacute smysl nemaacute je sed ani awk Z mnou běžně použiacutevanyacutech naacutestrojů nabiacuteziacute modifikaacutetory jen vim (jak je na tom klasickeacute vi neviacutem) a Perl Pokud použiacutevaacutete něco jineacuteho je potřeba nahleacutednout do dokumentace

Přiacuteklad A zase něco ze života vytvořili jste WWW straacutenky v prostřediacute MS Windows a naacutesledně je vystavili na Unixoveacutem serveru A nestačiacutete se divit Čaacutest obraacutezků zaacutehadně zmizela nefungujiacute dřiacuteve funkčniacute odkazy a podobně Přiacutečina je v tom že Unix a protokoly pohaacutenějiacuteciacute WWW rozlišujiacute malaacute piacutesmena od velkyacutech zatiacutemco MS Windows nikoli Maacutete-li na straacutenku vložen obraacutezek se jmeacutenem Image1gif ale soubor se ve skutečnosti jmenuje image1gif ve Windows vypadaacute vše v pořaacutedku ačkoli ve skutečnosti neniacute

Řešeniacute je třeba sjednotit velikost znaků - nejleacutepe tak že se vše převede na malaacute piacutesmena Takže si vypiacutešete seznam souborů v adresaacuteři se straacutenkami

(raději pomociacute find aby vyacutepis obsahoval i cesty do podadresaacuteřů) vychytaacutete ta jmeacutena kteraacute obsahujiacute velkaacute piacutesmena a převedete je na malaacute

find | grep [A-Z] gt seznam perl -pe s()mv 1 L1 seznam gt akce source akce rm seznam akce Po provedeniacute těchto přiacutekazů maacutete soubory přejmenovaacuteny na malaacute piacutesmena (druhyacute řaacutedek neniacute zcela korektniacute vraacutetiacutem se k němu na konci přiacutekladu) Zbyacutevaacute vypořaacutedat se s odkazy na ně Za nejschůdnějšiacute považuji vytvořit si konverzniacute program maleodkazy binsh for soubor in $ do perl -peibak s(href=)([][^]+[])1L2ig

s(src=)([][^]+[])1L2ig $soubor done

V substituciacutech si všimněte že kromě volby g (nahradit všechny vyacuteskyty) obsahuje i volbu i (ignorovat rozdiacutely mezi malyacutemi a velkyacutemi piacutesmeny) Diacuteky němu nezaacuteležiacute na tom jakyacutemi piacutesmeny jsou psaacuteny naacutezvy atributů SRC a HREF Zaacuteroveň jsem si je zapamatoval zvlaacutešť a vystrčil před L aby velikost jejich piacutesmen zůstala zachovaacutena

Volba -ibak způsobiacute že Perl soubor zpracuje na miacutestě a zaacutelohu jeho původniacuteho obsahu uložiacute s přiacuteponou bak

Program pak vypustiacutete na odpoviacutedajiacuteciacute soubory

maleodkazy html Jsou-li straacutenky i v podadresaacuteřiacutech bude zřejmě lepšiacute vložit jmeacutena souborů pomociacute přiacutekazu find uzavřeneacuteho ve zpětnyacutech apostrofech maleodkazy `find -name html` Avizoval jsem že přejmenovaacuteniacute souborů neniacute zcela v pořaacutedku Bude zlobit pokud se velkaacute piacutesmena vyskytnou ve jmeacutenech podadresaacuteřů takže pokud napřiacuteklad aktuaacutelniacute adresaacuteř bude obsahovat soubor AbcDef vygenerujiacute se přiacutekazy mv Abc abc mv AbcDef abcdef přičemž v okamžiku provaacuteděniacute druheacuteho již adresaacuteř Abc neexistuje Řešit by se to dalo tak že odděliacutete čaacutest cesty před lomiacutetkem a čaacutest za niacutem U čaacutesti před lomiacutetkem pak můžete předpoklaacutedat že už je malyacutemi piacutesmeny Aby se naviacutec negenerovala hlaacutešeniacute o přesunu souborů na sebe sameacute je zaacutehodno oddělit zpracovaacuteniacute adresaacuteřů a souborů adresaacuteře find -type d | grep [A-Z] gt seznam perl -pe s()()mv L1E2 L12 seznam gt akce source akce

soubory - adresaacuteře už nezlobiacute find | grep [A-Z] gt seznam perl -pe s()mv 1 L1 seznam gt akce source akce rm seznam akce

Klasickeacute a rozšiacuteřeneacute regulaacuterniacute vyacuterazy

Programy grep a egrep rozštěpily regulaacuterniacute svět na dva proudy Každyacute z nich použiacuteval poněkud jinou variantu regulaacuterniacutech vyacuterazů a takeacute jinyacute algoritmus pro jejich hledaacuteniacute Regulaacuterniacute vyacuterazy grepu představujiacute klasickou variantu zatiacutemco odrůdě reprezentovaneacute egrepem se řiacutekaacute rozšiacuteřeneacute regulaacuterniacute vyacuterazy

Zaacutekladniacute rozdiacutely rozšiacuteřenyacutech regulaacuterniacutech vyacuterazů proti klasickyacutem byly naacutesledujiacuteciacute zavedly speciaacutelniacute znaky + a pro alespoň jeden a nanejvyacuteš jeden vyacuteskyt znak | pro nebo a nepodporovaly mechanismus zapamatovaacuteniacute

Postupem času se však původniacute rozdiacutely smazaacutevaly a obě odrůdy implementovaly konstrukce ktereacute byly původně k dispozici jen u konkurence Takže mezi současnyacutem GNU grepem a GNU egrepem je rozdiacutel pouze v tom kde se piacutešiacute zpětnaacute lomiacutetka

V předminuleacutem odstavci jste možnaacute zastřiacutehali ušima protože jsem se zmiacutenil o dosud utajeneacute konstrukci Jednaacute se o nebo ktereacute se zapisuje v podobě svisleacute čaacutery (|) U klasickyacutech regulaacuterniacutech vyacuterazů se před ni zapisuje zpětneacute lomiacutetko (pokud je vůbec k dispozici)

Nebo maacute nižšiacute prioritu než zřetězeniacute takže napřiacuteklad egrep raz|dva najde řaacutedky obsahujiacuteciacute řetězec raz nebo dva Pokud potřebujete uacutečinek omezit použijte zaacutevorky

Přiacuteklad Naacutesledujiacuteciacute přiacutekaz vyhledaacute řaacutedky ktereacute začiacutenajiacute řetězcem From nebo Subject (může se hodit napřiacuteklad pro prohledaacutevaacuteniacute vašiacute poštovniacute schraacutenky) egrep ^(From|Subject) V podaacuteniacute grepu by přiacutekaz vypadal takto grep ^(From|Subject)

Regulaacuterniacute stroje

Nastal čas podiacutevat se alespoň orientačně na zoubek algoritmům ktereacute se starajiacute o interpretaci regulaacuterniacutech vyacuterazů Lze je rozdělit do třiacute kategoriiacute

Klasickyacute nedeterministickyacute

Tento algoritmus jsem popsal ve druheacute čaacutesti seriaacutelu Je založen na rekurzi a sveacute usilovaacuteniacute skončiacute jakmile naraziacute na prvniacute řetězec vyhovujiacuteciacute srovnaacutevaneacutemu vzoru Použiacutevaacute jej valnaacute většina programů - grep vi Perl a dalšiacute

Nedeterministickyacute podle POSIXu

Jednaacute se o variantu klasickeacuteho algoritmu jejiacutež chovaacuteniacute se lišiacute pokud regulaacuterniacute vyacuteraz obsahuje nebo POSIX varianta se nezastaviacute při prvniacutem naacutelezu Miacutesto toho prozkoumaacute všechny možneacute vyhovujiacuteciacute řetězce a z těch ktereacute začiacutenajiacute nejdřiacuteve pak vybere ten nejdelšiacute Důsledkem je že vyacutesledek nezaacutevisiacute na pořadiacute alternativ

Přiacuteklad Vezměme řetězec 12345 a srovnejme jej s regulaacuterniacutemi vyacuterazy 1+|[0-9]+ a [0-9]+|1+ Pokud se použiacutevaacute klasickyacute nedeterministickyacute algoritmus budou vyacutesledky rozdiacutelneacute prvniacutemu vyacuterazu vyhoviacute podřetězec 1 zatiacutemco při použitiacute druheacuteho vyhoviacute celyacute řetězec 12345 Klasickyacute algoritmus začne zkoumat prvniacute alternativu a jakmile najde vyhovujiacuteciacute řetězec skončiacute Naproti tomu při POSIXoveacutem algoritmu v obou přiacutepadech vyhoviacute 12345 protože obě alternativy začiacutenajiacute na stejneacute pozici a tato je delšiacute

Za svou nezaacutevislost na pořadiacute platiacute POSIXovyacute algoritmus rychlostiacute Jelikož musiacute prozkoumat všechny varianty je nejpomalejšiacute Upřiacutemně řečeno představuje spiacuteše teoretickou možnost protože jsem se dočetl pouze o několika maacutelo programech ktereacute jej implementujiacute (jedineacute obecněji rozšiacuteřeneacute jsou lex a mawk)

Deterministickyacute

Deterministickyacute algoritmus stojiacute na zcela odlišneacutem principu Nepoužiacutevaacute rekurzi ale paralelně sleduje všechny možneacute způsoby jak vyhovět daneacutemu vzoru Stejně jako předchoziacute tedy najde všechny alternativy a vybere nejdelšiacute z nejlevějšiacutech takže je takeacute nezaacutevislyacute na pořadiacute Jelikož celyacute řetězec zpracuje jedniacutem průchodem bez naacutevratů je nejrychlejšiacute Platiacute za to nemožnostiacute zapamatovat si čaacutesti vyhovujiacuteciacute jednotlivyacutem podvyacuterazům

Deterministickyacute algoritmus použiacutevaacute egrep a awk

Z hlediska taxonomie regulaacuterniacutech strojů majiacute velmi zvlaacuteštniacute pozici GNU naacutestroje Jsou totiž dvoumotoroveacute obsahujiacute implementaci jak deterministickeacuteho tak klasickeacuteho nedeterministickeacuteho algoritmu Pokud to jde použiacutevajiacute rychlejšiacute deterministickyacute Jakmile však přikaacutežete něco si zapamatovat saacutehnou po nedeterministickeacutem Diacuteky tomu napřiacuteklad GNU egrep na rozdiacutel od klasickeacuteho egrepu nabiacuteziacute mechanismus zapamatovaacuteniacute



01062000

Na posledniacute diacutel našeho seriaacutelu jsem si pošetřil speciality jazyka Perl Pokud se vaacutem při zahleacutednutiacute jmeacutena Perl povaacutežlivě zvedaacute hladina adrenalinu podiacutevejte se alespoň na konec

člaacutenku Najdete tam odkazy na literaturu a srovnaacutevaciacute tabulku speciaacutelniacutech znaků ktereacutežto materiaacutely by se vaacutem mohly hodit

Perl je do značneacute miacutery srdečniacute zaacuteležitost Znaacutem řadu jeho vaacutešnivyacutech zastaacutenců a zrovna tak jeho zuřiveacute odpůrce Ten jazyk je pohledem teoretika mimořaacutedně odpornyacute ale zaacuteroveň neuvěřitelně mocnyacute a praktickyacute Docela vyacutestižně (a velmi vtipně) to mysliacutem vyjaacutedřil Jeffrey E F Friedl ve sveacute knize o regulaacuterniacutech vyacuterazech

Siacutela Perlu může byacutet ničivou zbraniacute v rukaacutech zkušeneacuteho uživatele zdaacute se však že v Perlu sbiacuteraacutete zkušenosti tak že se opakovaně střiacuteliacutete do nohy

Dnes se ale nehodlaacutem věnovat jazyku jako takoveacutemu Raději se soustřediacutem na jeho speciality v oboru regulaacuterniacutech vyacuterazů A v tomto směru je v současnosti jasnaacute jednička ať se to jeho odpůrcům liacutebiacute nebo ne

Uvolněnaacute syntax

Regulaacuterniacute vyacuterazy jsou velmi kondenzovaneacute což je bohužel činiacute obtiacutežně srozumitelnyacutemi Obecně si troufaacutem prohlaacutesit že regulaacuterniacute vyacuteraz je často snadnějšiacute vytvořit než jej saacutem po sobě pochopit

Do jazyka Perl (přesněji řečeno do verze 5 ale ta už je na světě pět let takže ji lze považovat za standard jazyka) proto přibyla možnost rozvolněniacute zaacutepisu regulaacuterniacutech vyacuterazů Nepřidaacutevaacute žaacutedneacute noveacute konstrukce jen je umožňuje srozumitelně zapsat

Uvolněnou syntax zapiacutenaacute volba x v operaacutetoru pro hledaacuteniacute či nahrazovaacuteniacute (operaacutetory m a s) Regulaacuterniacute vyacuteraz se pak zapisuje do složenyacutech zaacutevorek podobně jako blok programu ignorujiacute se v něm mezery a konce řaacutedků (pokud jim nepředchaacuteziacute zpětneacute lomiacutetko) a komentaacuteře zahaacutejeneacute znakem

Přiacuteklad V čaacutesti o zapamatovaacuteniacute jste se mohli setkat s nechutnou substituciacute s([^])([^])3([^])ltA HREF=~1gt3ltAgt kteraacute z řaacutedků v etcpasswd vyraacuteběla seznam domaacuteciacutech straacutenek uživatelů S využitiacutem uvolněneacute syntaxe bychom ji mohli přepsat naacutesledovně

Nepřipadaacute vaacutem to o dost srozumitelnějšiacute Upozorňuji že uvolněnaacute syntax se tyacutekaacute pouze regulaacuterniacuteho vyacuterazu nikoli nahrazujiacuteciacuteho řetězce V něm se projeviacute pouze tiacutem že je uzavřen do složenyacutech zaacutevorek

s ([^]) přihlašovaciacute jmeacuteno (1) ([^])3 přeskočiacuteme heslo UID a GID

([^]) vlastniacute jmeacuteno (3) přeskočiacuteme zbytek

ltA HREF=~1gt3ltAgtx

Drobnosti ktereacute potěšiacute

Perl nabiacuteziacute řadu konstrukciacute ktereacute sice nepřinaacutešejiacute nějakou zaacutesadniacute inovaci stran schopnostiacute regulaacuterniacutech vyacuterazů ale v běžneacutem životě silně potěšiacute Asi nejčastěji použiacutevaneacute jsou kategorie znaků Z těch nejběžnějšiacutech lze jmenovat

Zaacutepis Vyacuteznam Odpoviacutedaacute

d čiacuteslice [0-9] D nečiacuteslice [^d] w alfanumerickyacute znak [a-zA-Z_0-9] W nealfanumerickyacute znak [^w] s praacutezdnyacute znak [ tnr] S nepraacutezdnyacute znak [^s]

Tyto speciaacutelniacute znaky celkem vyacuterazně přispiacutevajiacute ke srozumitelnosti regulaacuterniacutech vyacuterazů Naviacutec pokud svůj program zahaacutejiacutete přiacutekazem use locale budou mezi alfanumerickeacute znaky zařazeny i akcentovaneacute znaky naacuterodniacute abecedy

Přiacuteklad Vyacuteměnu prvniacutech dvou slov na řaacutedku pak zajistiacute celkem miacuterumilovnyacute přiacutekaz s(w+)(W+)(w+)321

Kromě Perlu už převzaly podobneacute znakoveacute kategorie i současneacute verze dalšiacutech naacutestrojů (konzultujte s dokumentaciacute) Kromě nich je leckde podporovaacuten i zaacutepis kategoriiacute podle POSIXu kde se napřiacuteklad čiacuteslice zapisuje jako [digit] alfanumerickyacute znak jako [alnum] a praacutezdneacute miacutesto [space] Tyto kategorie se však zapisujiacute mezi [] takže napřiacuteklad řaacutedek začiacutenajiacuteciacute čiacutesliciacute se vyjaacutedřiacute pomociacute ^[[digit]] což už maacute k eleganci poměrně daleko (toteacutež v Perlu ^d) Perl POSIXoveacute kategorie nepodporuje

Syteacute (teacutež liacuteneacute) opakovaacuteniacute pomůže řešit probleacutemy s nadměrnou žravostiacute opakovaciacutech konstrukciacute Zapisuje se jednoduše za opakovaciacute znak ( + či minmax) připojiacutete otazniacutek Přiacutepustnyacute počet opakovaacuteniacute se tiacutem nijak nezměniacute ale na rozdiacutel od klasickeacute varianty se snažiacute aby opakovaacuteniacute bylo co nejmeacuteně Takže třeba obliacutebenyacute řetězec v uvozovkaacutech lze hledat pomociacute Je to přehlednějšiacute ale pomalejšiacute než obvykleacute řešeniacute [^]

Třetiacute užitečnou drobnostiacute jsou zaacutevorky bez zapamatovaacuteniacute Sloužiacute vyacutelučně k vymezeniacute čaacutesti regulaacuterniacuteho vyacuterazu (např pro opakovaacuteniacute nebo omezeniacute působnosti nebo) Vyhovujiacuteciacute řetězec se neuklaacutedaacute takže vaacutem ubyde špetka starostiacute při počiacutetaacuteniacute indexů těch zapamatovanyacutech Tyto speciaacutelniacute zaacutevorky se zapisujiacute ve tvaru ()

Přiacuteklad Ještě jednou přepracuji přiacuteklad pro transformaci řaacutedku z etcpasswd na položku v seznamu domaacuteciacutech straacutenek S využitiacutem popsanyacutech konstrukciacute by mohl vypadat takto s

() přihlašovaciacute jmeacuteno (1) ()3 přeskočiacuteme heslo UID a GID

() vlastniacute jmeacuteno (2) přeskočiacuteme zbytek


Tentokraacutet se v čaacutesti přeskakujiacuteciacute heslo UID a GID vyhnu zapamatovaacuteniacute takže pod čiacutesly 1 a 2 maacutem uloženy skutečně jen ty informace ktereacute mne zajiacutemajiacute Dvojtečka z konstrukce ( se v tomto přiacutepadě bohužel nepěkně plete s oddělovačem položek ale s tiacutem se nedaacute nic dělat Liacuteneacute opakovaacuteniacute mi umožnilo poněkud zjednodušit vyacuterazy pro jednotliveacute čaacutesti řaacutedku

Vyhliacuteženiacute

Dost silnyacute naacutestroj pro některeacute speciaacutelniacute přiacutepady nabiacuteziacute tak zvaneacute vyhliacuteženiacute (anglicky lookahead) Existuje ve dvou odrůdaacutech pozitivniacute vyhliacuteženiacute se zapisuje v podobě (=vyacuteraz) a je splněno pokud naacutesledujiacuteciacute čaacutest řetězce vyhovuje vyacuterazu Negativniacute vyhliacuteženiacute (vyacuteraz)naopak uspěje pokud vyacuterazu nevyhovuje Důležiteacute je že vyhliacuteženiacute se jen podiacutevaacute zda se vzor daacute či nedaacute najiacutet ale neposouvaacute zkoumanou pozici daacutel (jemu odpoviacutedajiacuteciacute řetězec je vždy praacutezdnyacute)

PřiacutekladVzoru d+(= Kč) vyhoviacute nepraacutezdnaacute posloupnost čiacuteslic ale jen pokud za niacute naacutesleduje řetězec Kč Ten však saacutem o sobě neniacute zahrnut do vyhovujiacuteciacuteho řetězce Takže pokud přiacutekaz s(d+)(= Kč)g vypustiacutete na řetězec Paacuteraacutetka 20 CX Turbo za 25 Kč kus obdržiacutete vyacutesledek Paacuteraacutetka 20 CX Turbo za Kč kus

Za přiacuteklad negativniacuteho vyhliacuteženiacute může posloužit (000)ddd ktereacutemu vyhoviacute libovolnaacute trojice čiacuteslic s vyacutejimkou 000Faktem je že vyhliacuteženiacute neniacute principiaacutelně nezbytneacute Zpravidla je lze nahradit jinyacutemi konstrukcemi jazyka Napřiacuteklad zachovaacuteniacute Kč za skupinou čiacuteslic by se dalo zařiacutedit pomociacute zapamatovaacuteniacute Test na trojici čiacuteslic ne však 000 by se dal rozložit do dvou nezaacutevislyacutech testů a podobně V některyacutech přiacutepadech však vyhliacuteženiacute daacutevaacute zajiacutemaveacute možnosti

Přiacuteklad Hezkou vychytaacutevkou využiacutevajiacuteciacute vyhliacuteženiacute je oddělovaacuteniacute řaacutedů ve velkyacutech čiacuteslech Mezi trojice čiacuteslic se majiacute vložit mezery takže z 12345678 vznikne 12 345 678 Vtip je v tom že se trojice počiacutetajiacute odzadu na což regulaacuterniacute vyacuterazy nejsou přiacuteliš zařiacutezeneacute Vyhliacuteženiacute umožňuje naacutesledujiacuteciacute řešeniacute s

(d13) za prvniacute skupinu patřiacute mezera

(= ale jen když naacutesleduje

(ddd)+ alespoň jedna trojice čiacuteslic (d) a tiacutem čiacuteslo končiacute

) 1 gx

Diacuteky vyhliacuteženiacute se můžete přesvědčit že počet čiacuteslic ktereacute naacutesledujiacute za aktuaacutelniacute poziciacute ve zpracovaacutevaneacutem řetězci je naacutesobkem třiacute Vyhliacuteženiacute zaacuteroveň zajistiacute že se tato pozice nezměniacute a že se při přiacuteštiacutem opakovaacuteniacute (diacuteky volbě g se provaacutediacute pro všechny vyacuteskyty) se bude pokračovat za naposledy vloženou mezerou

Literatura

Pokud je mi znaacutemo vyšla zatiacutem jedinaacute kniha věnovanaacute vyacutelučně regulaacuterniacutem vyacuterazům Napsal ji Jeffrey E F Friedl a jmenuje se Mastering Regular Expressions (vydalo nakladatelstviacute OReilly amp Associates v roce 1997 ISBN 1-56592-257-3) Neniacute to pochopitelně vyslovenaacute oddechovka ale v raacutemci možnostiacute vysvětluje vlastnosti regulaacuterniacutech vyacuterazů vhodneacute a nevhodneacute techniky pro jejich vytvaacuteřeniacute Vzhledem k rozsahu přes 300 stran si může dovolit jiacutet dost do hloubky

Cenneacute služby odvede kniha Unix Power Tools jejiacutemiž autory jsou Jerry Peek Tim OReilly a Mike Loukides Vyšla takeacute u OReilly amp Associates v roce 1997 (2 vydaacuteniacute ISBN 1-56592-260-3) Obsahuje velmi slušnou kapitolu o regulaacuterniacutech vyacuterazech a kromě niacute řadu tipů a triků na využiacutevaacuteniacute programů ktereacute s nimi pracujiacute Osobně ji považuji za jednu z nejpřiacutenosnějšiacutech kniacutežek ktereacute jsem kdy měl v ruce

Přehledovaacute tabulka

Jako zaacutevěrečnou přiacutelohu vaacutem nabiacuteziacutem stručnyacute přehled regulaacuterniacutech vyacuterazů v nejběžnějšiacutech naacutestrojiacutech Konkreacutetně se jednaacute o GNU grep a egrep verze 23 GNU awk verze 304 vim verze 55 a Perl verze 5005_03 Tabulka je k dispozici v těchto formaacutetech [datatabulkaps] PostScript [datatabulkapdf] PDF [datatabulkahtml] HTML

[âeiouy] zastupuje jeden znak kteryacute neniacute v uvedemeacute množině) Takže v tomto přiacutepadě se vyberou všechny soubory končiacuteciacute na html v aktuaacutelniacutem adresaacuteři a všech jeho podadresaacuteřiacutech

Ve zbyleacute čaacutesti skriptu se jedna proměnnaacute rozděliacute do pole promměnyacutech a v cyklu se pro každyacute nalezenyacute soubor vypiacuteše jeho jmeacuteno a zpracuje programem vi Čaacutest za znakem lt samozřejmě nahraďte spraacutevnou cestou

Soubor s přiacutekazyDo tohoto souboru se vklaacutedajiacute přiacutekazy pro editor vi Nazvěte si jej a umiacutestěte jak a kam chcete Nezapomeňte pak ale upravit předposledniacute řaacutedek skriptu Text souboru VI maacute obecně naacutesledujiacuteciacute tvar

gXYZsABCgwq

Na prvniacutem řaacutedku je regulaacuterniacute vyacuteraz na druheacutem přiacutekaz pro zapsaacuteniacute změn a ukončeniacute činnosti editoru vi Pokud vaacutem regulaacuterniacute vyacuterazy nic neřiacutekajiacute zkuste spustit vi a v něm napsat help pattern a zmaacutečknout enter Jinou možnostiacute je manuaacutelovaacute straacutenka regulaacuterniacutech vyacuterazů pro perl - man perlre

Při běžneacute praacuteci nahradiacutete text XYZ hledanyacutem textem a ABC novyacutem textem Pokud se vaacutem nechce pročiacutetat manuaacutely k regulaacuterniacutem vyacuterazům (vřele doporučuji je přečiacutest) snad vaacutem pomůže naacutesledujiacuteciacute vyacutetah kteryacute maacute daleko k uacuteplnosti

XYZ může byacutet běžnyacute text kteryacute hledaacutete Potom algoritmus porovnaacutevaacute prošlyacute text s požadovanyacutem textem a nalezne-li shodu změniacute jej na ABC V XYZ ale mohou byacutet zaacutestupneacute znaky Hvězdička stejně jako v shellu nahrazuje libovolnyacute počet libovolnyacutech znaků Tečka nahrazuje jeden libovolnyacute znak tj maacute stejnyacute vyacuteznam jako otazniacutek v shellu Hranateacute zaacutevorky se chovajiacute takeacute stejně jako v shellu vybiacuterajiacute jeden platnyacute znak z uvedeneacute množiny Pokud chcete najiacutet znak [ nebo ] napište před niacutem zpětneacute lomiacutetko To rušiacute vyacuteznam speciaacutelniacuteho znaku

Přiacuteklady

bull ahoj najde všechny slova obsahujiacuteciacute ahoj bull maka najde napřiacuteklad maka matka maska mařenka ma7558kla atd bull maka najde matka mamka maska marka atd bull ma[mt]ka najde jen matka mamka bull ma[^mt]ka najde maska marka ma8ka a dalšiacute kromě matka a mamka bull ma[n-z]ka najde maska marka matka a dalšiacute kde prostředniacute piacutesmeno ležiacute v rozmeziacute n

až z bull najde všechna dopřednaacute lomiacutetka bull najde hvězdičky

Dalšiacutem speciaacutelniacute znakem je ^ pokud neniacute použit jako negace ve vyacutečtu znaků Pak maacute vyacuteznam začaacutetku řaacutedku Obdobně znak $ ukazuje na konec řaacutedku Dvojice lt je zase naacutehradou začaacutetku slova a gt pak konce slova

Přiacuteklady





Varovaacuteniacute


Nevyacutehody


Vyacutehody





24051999













06042000











Libovolnyacute znak



















libovolnyacute znak






11042000




















1

2

3

4

5










18042000


grep a spol











grep --version


sed


















awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura









Varovaacuteniacute


Nevyacutehody


Vyacutehody





24051999













06042000











Libovolnyacute znak



















libovolnyacute znak






11042000




















1

2

3

4

5










18042000


grep a spol











grep --version


sed


















awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura







24051999













06042000











Libovolnyacute znak



















libovolnyacute znak






11042000




















1

2

3

4

5










18042000


grep a spol











grep --version


sed


















awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura







06042000











Libovolnyacute znak



















libovolnyacute znak






11042000




















1

2

3

4

5










18042000


grep a spol











grep --version


sed


















awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura





Libovolnyacute znak



















libovolnyacute znak






11042000




















1

2

3

4

5










18042000


grep a spol











grep --version


sed


















awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura










libovolnyacute znak






11042000




















1

2

3

4

5










18042000


grep a spol











grep --version


sed


















awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura







11042000




















1

2

3

4

5










18042000


grep a spol











grep --version


sed


















awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura















1

2

3

4

5










18042000


grep a spol











grep --version


sed


















awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura





3

4

5










18042000


grep a spol











grep --version


sed


















awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura







18042000


grep a spol











grep --version


sed


















awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura





grep --version


sed


















awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura













awk




Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura





Perl













$radek =~ s[0-9][0-9]Xg




28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura








28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura







28042000














Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura







Pozice













$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura






$ konec řaacutedku





09052000


























22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura






















22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura















22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura







22052000


Modifikaacutetory






































01062000





































) 1 gx


Literatura


































01062000





































) 1 gx


Literatura



























01062000





































) 1 gx


Literatura














01062000





































) 1 gx


Literatura








































) 1 gx


Literatura



























) 1 gx


Literatura

















) 1 gx


Literatura






) 1 gx


Literatura





Date post:	13-Dec-2020
Category:	Documents
Upload:	others
View:	1 times
Download:	0 times

Jak na hromadné nahrazování textu? · 2004. 12. 10. · •a na začátku řádky znak a •...

Documents