Regulární výrazy (6)

Pavel Satrapa 22. 5. 2000

Od minula si umíte nalezené věci zapamatovat a později použít. To je v reálném životě šeredně nebezpečná vlastnost. Například jste teď nepoužitelní jako voliči. Abyste se opět stali politicky korektními, naučím vás pozměnit, co jste si zapamatovali.

Modifikátory

Kdybych chtěl být protivně korektní, vlastně bych o modifikátorech neměl mluvit, protože oficiálně nepatří mezi regulární výrazy. Používají se však v těsné součinnosti s nimi, takže zpravidla bývají házeny do jednoho pytle.

Modifikátory jsou konstrukce, které změní následující znaky. Jejich typické použití nese následující znaky:

  • slouží k vzájemnému převodu malých/velkých písmen
  • vyskytují se ve druhé (nahrazující) části příkazu pro nahrazování řetězců
  • bývají aplikovány na zapamatované řetězce.

Těmi nejjednoduššími jsou \u a \l. První z nich převede následující znak z malého písmene na velké (upper case). Následuje-li cokoli jiného, než malé písmeno, zůstane znak beze změny. Konstrukce \l funguje právě opačně - převádí následující velké písmeno na malé (lower case).

Uvedené modifikátory se týkaly vždy jen jediného znaku, který následuje bezprostředně za nimi. Pokud použijete velké písmeno (\U či \L), zasáhne modifikátor všechny následující znaky až po konec řetězce nebo nejbližší následující výskyt \E, kterážto konstrukce slouží jako ukončující.

Bohužel jsou modifikátory poměrně vzácné. grep a jeho bratři nedovedou nahrazovat, takže u nich nemají smysl, nemá je sed ani awk. Z mnou běžně používaných nástrojů nabízí modifikátory jen vim (jak je na tom klasické vi nevím) a Perl. Pokud používáte něco jiného, je potřeba nahlédnout do dokumentace.

Příklad:

A zase něco ze života: vytvořili jste WWW stránky v prostředí MS Windows a následně je vystavili na Unixovém serveru. A nestačíte se divit. Část obrázků záhadně zmizela, nefungují dříve funkční odkazy a podobně. Příčina je v tom, že Unix a protokoly pohánějící WWW rozlišují malá písmena od velkých, zatímco MS Windows nikoli. Máte-li na stránku vložen obrázek se jménem Image1.gif, ale soubor se ve skutečnosti jmenuje image1.gif, ve Windows vypadá vše v pořádku, ačkoli ve skutečnosti není.

Řešení: je třeba sjednotit velikost znaků - nejlépe tak, že se vše převede na malá písmena. Takže si vypíšete seznam souborů v adresáři se stránkami (raději pomocí find, aby výpis obsahoval i cesty do podadresářů), vychytáte ta jména, která obsahují velká písmena, a převedete je na malá:

find . | grep '[A-Z]' > seznam
perl -pe 's/(.*)/mv \1 \L\1/' seznam > akce
source akce
rm seznam akce

Po provedení těchto příkazů máte soubory přejmenovány na malá písmena (druhý řádek není zcela korektní, vrátím se k němu na konci příkladu). Zbývá vypořádat se s odkazy na ně. Za nejschůdnější považuji vytvořit si konverzní program maleodkazy:

#!/bin/sh
for soubor in $*
do
perl -pei.bak 's/(href=)(['"][^'"]+['"])/\1\L\2/ig;
   s/(src=)(['"][^'"]+['"])/\1\L\2/ig' $soubor
done

V substitucích si všimněte, že kromě volby g (nahradit všechny výskyty) obsahuje i volbu i (ignorovat rozdíly mezi malými a velkými písmeny). Díky němu nezáleží na tom, jakými písmeny jsou psány názvy atributů SRC a HREF. Zároveň jsem si je zapamatoval zvlášť a vystrčil před \L, aby velikost jejich písmen zůstala zachována.

Volba -i.bak způsobí, že Perl soubor zpracuje „na místě“ a zálohu jeho původního obsahu uloží s příponou .bak.

Program pak vypustíte na odpovídající soubory

./maleodkazy *.html

Jsou-li stránky i v podadresářích, bude zřejmě lepší vložit jména souborů pomocí příkazu find uzavřeného ve zpětných apostrofech:

./maleodkazy `find . -name \*.html`

Avizoval jsem, že přejmenování souborů není zcela v pořádku. Bude zlobit, pokud se velká písmena vyskytnou ve jménech podadresářů, takže pokud například aktuální adresář bude obsahovat soubor Abc/Def, vygenerují se příkazy

mv Abc abc
mv Abc/Def abc/def

přičemž v okamžiku provádění druhého již adresář Abc neexistuje. Řešit by se to dalo tak, že oddělíte část cesty před lomítkem a část za ním. U části před lomítkem pak můžete předpokládat, že už je malými písmeny. Aby se navíc negenerovala hlášení o přesunu souborů na sebe samé, je záhodno oddělit zpracování adresářů a souborů:

#adresáře
find . -type d | grep '[A-Z]' > seznam
perl -pe 's/(.*\/)(.*)/mv \L\1\E\2 \L\1\2/' seznam > akce
source akce
 
#soubory - adresáře už nezlobí
find . | grep '[A-Z]' > seznam
perl -pe 's/(.*)/mv \1 \L\1/' seznam > akce
source akce
rm seznam akce

Klasické a rozšířené regulární výrazy

Programy grep a egrep rozštěpily regulární svět na dva proudy. Každý z nich používal poněkud jinou variantu regulárních výrazů a také jiný algoritmus pro jejich hledání. Regulární výrazy grepu představují klasickou variantu, zatímco odrůdě reprezentované egrepem se říká rozšířené regulární výrazy.

Základní rozdíly rozšířených regulárních výrazů proti klasickým byly následující: zavedly speciální znaky + a ? pro alespoň jeden a nanejvýš jeden výskyt, znak | pro „nebo“ a nepodporovaly mechanismus zapamatování.

Postupem času se však původní rozdíly smazávaly a obě odrůdy implementovaly konstrukce, které byly původně k dispozici jen u konkurence. Takže mezi současným GNU grepem a GNU egrepem je rozdíl pouze v tom, kde se píší zpětná lomítka.

V předminulém odstavci jste možná zastříhali ušima, protože jsem se zmínil o dosud utajené konstrukci. Jedná se o „nebo“, které se zapisuje v podobě svislé čáry (|). U klasických regulárních výrazů se před ni zapisuje zpětné lomítko (pokud je vůbec k dispozici).

„Nebo“ má nižší prioritu než zřetězení, takže například egrep ‚raz|dva‘ najde řádky obsahující řetězec „raz“ nebo „dva“. Pokud potřebujete účinek omezit, použijte závorky.

widgety

Příklad:

Následující příkaz vyhledá řádky, které začínají řetězcem „From:“ nebo „Subject:“ (může se hodit například pro prohledávání vaší poštovní schránky):

egrep '^(From|Subject):'

V podání grepu by příkaz vypadal takto:

grep '^\(From\|Subject\):'

Regulární stroje

Nastal čas podívat se alespoň orientačně na zoubek algoritmům, které se starají o interpretaci regulárních výrazů. Lze je rozdělit do tří kategorií:

Klasický nedeterministický

Tento algoritmus jsem popsal ve druhé části seriálu. Je založen na rekurzi a své usilování skončí, jakmile narazí na první řetězec vyhovující srovnávanému vzoru. Používá jej valná většina programů - grep, vi, Perl a další.

Nedeterministický podle POSIXu

Jedná se o variantu klasického algoritmu, jejíž chování se liší, pokud regulární výraz obsahuje „nebo“. POSIX varianta se nezastaví při prvním nálezu. Místo toho prozkoumá všechny možné vyhovující řetězce a z těch, které začínají nejdříve, pak vybere ten nejdelší. Důsledkem je, že výsledek nezávisí na pořadí alternativ.

Příklad:

Vezměme řetězec „12345“ a srovnejme jej s regulárními výrazy 1+|[0–9]+ a [0–9]+|1+. Pokud se používá klasický nedeterministický algoritmus, budou výsledky rozdílné: prvnímu výrazu vyhoví podřetězec „1“, zatímco při použití druhého vyhoví celý řetězec „12345“. Klasický algoritmus začne zkoumat první alternativu a jakmile najde vyhovující řetězec, skončí. Naproti tomu při POSIXovém algoritmu v obou případech vyhoví „12345“, protože obě alternativy začínají na stejné pozici a tato je delší.

Za svou nezávislost na pořadí platí POSIXový algoritmus rychlostí. Jelikož musí prozkoumat všechny varianty, je nejpomalejší. Upřímně řečeno představuje spíše teoretickou možnost protože jsem se dočetl pouze o několika málo programech, které jej implementují (jediné obecněji rozšířené jsou lex a mawk).

Deterministický

Deterministický algoritmus stojí na zcela odlišném principu. Nepoužívá rekurzi, ale paralelně sleduje všechny možné způsoby, jak vyhovět danému vzoru. Stejně jako předchozí tedy najde všechny alternativy a vybere nejdelší z nejlevějších, takže je také nezávislý na pořadí. Jelikož celý řetězec zpracuje jedním průchodem bez návratů, je nejrychlejší. Platí za to nemožností zapamatovat si části vyhovující jednotlivým podvýrazům.

Deterministický algoritmus používá egrep a awk.

Z hlediska taxonomie regulárních strojů mají velmi zvláštní pozici GNU nástroje. Jsou totiž dvoumotorové: obsahují implementaci jak deterministického, tak klasického nedeterministického algoritmu. Pokud to jde, používají rychlejší deterministický. Jakmile však přikážete něco si zapamatovat, sáhnou po nedeterministickém. Díky tomu například GNU egrep na rozdíl od klasického egrepu nabízí mechanismus zapamatování.

Našli jste v článku chybu?
Lupa.cz: Jak levné procesory změnily svět?

Jak levné procesory změnily svět?

Vitalia.cz: Opuncie je plod kaktusu. Pozor na trny

Opuncie je plod kaktusu. Pozor na trny

Podnikatel.cz: Takhle se prodávají mražené potraviny

Takhle se prodávají mražené potraviny

Vitalia.cz: Tahák, jak vyzrát nad zápachem z úst

Tahák, jak vyzrát nad zápachem z úst

Vitalia.cz: Muž, který miluje příliš. Ženám neimponuje

Muž, který miluje příliš. Ženám neimponuje

Vitalia.cz: Jsou vegani a vyrábějí nemléko

Jsou vegani a vyrábějí nemléko

Vitalia.cz: Když všichni seli řepku, on vsadil na dýně

Když všichni seli řepku, on vsadil na dýně

Vitalia.cz: 5 pravidel proti infekci močových cest

5 pravidel proti infekci močových cest

Vitalia.cz: Jak Ondra o astma přišel

Jak Ondra o astma přišel

Podnikatel.cz: Chystá se smršť legislativních novinek

Chystá se smršť legislativních novinek

DigiZone.cz: Numan Two: rozhlasový přijímač s CD

Numan Two: rozhlasový přijímač s CD

Vitalia.cz: Test dětských svačinek: Tyhle ne!

Test dětských svačinek: Tyhle ne!

Vitalia.cz: Inspekce našla nelegální sklad v SAPĚ. Zase

Inspekce našla nelegální sklad v SAPĚ. Zase

Lupa.cz: Hackeři mají data z půlmiliardy účtů Yahoo

Hackeři mají data z půlmiliardy účtů Yahoo

DigiZone.cz: Koncesionářské poplatky pro RTVS

Koncesionářské poplatky pro RTVS

Lupa.cz: Patička e-mailu závazná jako vlastnoruční podpis?

Patička e-mailu závazná jako vlastnoruční podpis?

Lupa.cz: Další Češi si nechali vložit do těla čip

Další Češi si nechali vložit do těla čip

DigiZone.cz: Funbox 4K v DVB-T2 má ostrý provoz

Funbox 4K v DVB-T2 má ostrý provoz

Vitalia.cz: Voda z Vltavy před a po úpravě na pitnou

Voda z Vltavy před a po úpravě na pitnou

DigiZone.cz: Rapl: seriál, který vás smíří s ČT

Rapl: seriál, který vás smíří s ČT