Regulární výrazy v příkladech

Regulární výrazy nám umožňují jednoduše vyhledávat a nahrazovat text. Pronikly snad do všech programů pro zpracování textů. V dnešní době nenajdete v Linuxu textový editor, který by regulární výrazy nepodporoval. Pro ty, kteří si nedokážou regulární výraz vůbec představit, bych zde uvedl jednoduché přirovnání k „zástupným žolíkům“ u vyhledávání souborů. Pokud o regulárních výrazech vůbec nic nevíte, doporučuji si přečíst skvělý seriál, který vyšel na rootu.

Začneme netradičně. Povíme si něco o tom, jak počítač regulární výrazy vyhodnocuje. Ze všeho nejdříve si pro něj sestaví konečný(nejlépe deterministický, aby se dobral výsledku) automat. Automat je věc, do které pošlete řetězec a ona rozhodne, zda daný vstup výrazu vyhovuje, či ne. Je to taková černá skříňka. Automaty obvykle znázorňujeme jako orientované grafy, kde uzly jsou stavy automatu a (orientované) hrany představují přechody mezi nimi. Některé uzly zvolíme jako koncové (např. barevně je odlišíme). Po vytvoření se automat inicializuje, to znamená, že přejde do počátečního stavu (obykle je označen q0). Automat pracuje po krocích. V každém kroku načte jeden znak ze vstupu, což je dáno právě regulárností výrazu. Pokud ze stavu existuje přechod odpovídající načtenému znaku, automat přejde do nového stavu a pokračuje dalším znakem. V opačném případě se znova inicializuje a načte další znak. Opakuje to tak dlouho, dokud daný vstup celý nenačte (záleží na regulárním výrazu, můžete také definovat, aby při prvním selhání ukončil činnost) nebo neskončí v koncovém stavu. Pokud ano, vstup je rozpoznán.

Celou věc si nyní ukážeme na příkladu. Uvažujme následující jednoduchý regulární výraz: www\.[a-z]*\.(cz|sk). Pro tento výraz by počítač sestavil podobný automat, jaký vidíte na obrázku.

Samozřejmě, že si počítač nesestaví orientovaný graf. Nejjednodušší je pro něj stavy očíslovat, do aktuálního stavu uložit nulu a sestavit si matici přechodů (např. pomocí dvojrozměrného pole). Uvažujme nyní vstup www.root.cz. Automat se nachází ve stavu q0. Načte znak „w“, pro něj existuje přechod do stavu q1. Automat tedy načte znovu (2×) znak „w“, až se dostane do stavu q3, kde načte tečku, čímž se podobným způsobem dostane až do stavu q4. Zde se odehraje tzv. uzávěr. Automat načte znak „r“. Pro něj ale existuje přechod ([a-z] je zkráceně zapsáno {a, b, c, …, y, z}). Je to dokonce přechod q4 na q4 (v odborné hantýrce tzv. kvedlání :-). Tento proces se opakuje (automat vykvedlá) až po znak „t“. Nyní je na programu druhá tečka, která zapříčiní přesunutí do stavu q5. Ve stavu q5 akceptuje znak c nebo s, to díky speciálním znakům )|( – proč jsem závorky v tomto textu zaměnil, je asi každému ;-] jasné. Pokud vše dobře dopadne (jako že ano), tak se dostane až do stavu q8. Tento stav jsme zvolili jako koncový, tutíž automat akceptuje vstup. Zkuste akceptovat tuto větu: „www.microsof­t.com“. Podle mého názoru automat takto zkonstruovaný takové zadání neakceptuje (a nejen on ;-).

Jistě chápete, proč jsou regulární výrazy tak mocné. Jednak lze s nimi pokrýt širokou paletu gramatik a jednak jsou poměrně rychlé. Přehazovat někde ukazatel nebo přesouvat číslo z paměti do registru, no tak to by totiž počítači šlo (jak říká jeden můj kamarád – počítačův sen). Na druhou stranu na jiné gramatiky (např. bezkontextové) již regulární výraz nestačí. Snadno lze dokázat, že nelze sestavit regulární gramatiku, která by akceptovala například vstup ve tvaru 011010…1100 (se stejným počtem jedniček a nul, tedy vstup 100 už ne) nebo která by ověřovala paritu závorek.

Když už víme, jak regulární výraz funguje a na co je, můžeme začít experimentovat. Implementací regulárních výrazů je mnoho. Nejznámější z nich jsou asi implementace Perl5+, AWK, vim nebo GNU grep. My se v našem povídání zaměříme na implementaci Perl5+, což je de facto standard, který používá nejen programovací jazyk Perl verze 5 nebo vyšší. Většinu řídících výrazů však mají všechny implementace společné a liší se jen drobnostmi.

Pokud nějaký řetězec vyhovuje naší podmínce, můžeme ho prostě jen zobrazit (různe vyhledávací programy typu grep, egrep), získat na něj odkaz, či ho modifikovat (v programovacích jazycích, jako je Perl a podobně). Pokud váš oblíbený jazyk nepodporuje regulární výrazy (v dokumentaci hledejte slovo „regexp“), tak si můžete z internetu stáhnout knihovnu, pomocí které s nimi můžete snadno pracovat i v těchto jazycích (např. C/C++). Jazyků, které regulární výrazy přímo podporují, je ale mnoho, jmenujme alespoň Perl, Python, Ruby, Java či C#. Podívejme se nyní na význam nejdůležitějších řídících výrazů:

Nyní si všechno vyzkoušíme. Všechny zde uvedené příklady můžete ihned zkoušet v apletu. Pro běh apletu budete potřebovat plug-in Java 1.3 nebo vyšší.

Příklad: pro
Vyhledali jsme všechny výskyty řetězce pro. Žádná věda. Jdeme dál.

Příklad: .e
Vyhledáme všechny řetězce, které začínají libovolným znakem (řídící znak tečka) a pokračují znakem e. Jejich délka musí být přesně 2.

Příklad: .*1
V podobném příkladě však použijeme kvantifikátor hvězdička, který říká, že před číslem 1 musí být žádný nebo více libovolných znaků. Všimněte si, že regulární výraz se chová „hladově“ a snaží se maximalizovat výsledek. V tomto případě pohltil celé zadání až po poslední jedničku v textu. „Hladovost“ se dá v regulárních výrazech omezovat, ale to se v různých implementacích li­ší.

Příklad: \bpro\b
V tomto případě jsme využili hranici slova a vyhledali pouze slova „pro“ stojící samostatně.

Příklad: \b(a|i|o|u)\b
Pomocí tohoto zadání vyhledáme konkrétní předložky a spojky. Pomocí logického NEBO a díky závorkám jsme efektivně definovali, které to mají být.

Příklad: \d+\.\d+\.\d+\­.\d+
Regulární výraz vyhledá všechny IP adresy v textu. Pomocí \d+ jsme určili jednu nebo více cifer. Tečka je speciální znak, proto jí musí předcházet zpětné lomítko (\.).

Příklad: (\d{1,3}\.){3}\d{1,3}
Příklad se stejným výsledkem, ale napsaný jinak. V tomto případě se na IP adresu díváme jako na tři po sobě jdoucí cifry délky 1 až 3, vždy následované tečkou. Za poslední číslicí však již tečka není, a tak jsme ji zahrnuli do výrazu zvlášť.

Příklad: http://[a-zA-Z_.]+
Tímto výrazem můžeme snadno nalézt webové odkazy. Jistě byste už dovedli zkonstruovat odkaz, který by například našel jen ty odkazy, které by nekončily řetězcem „asp“.

Příklad: (http://)?w{3}[a-zA-Z_.]+\.cz
Složitější příklad, ve kterém říkáme, že adresa může začínat řetězcem „http://“ (ale nemusí: otazník znamená „žádný nebo jeden“), následuje „www“, pak znaky a-Z, podtržítko a tečka a vše to končí řetězcem „.cz“. Jedná se o vyhledání URL v české doméně začínající „www“.

Příklad: [a-zA-Z_.]+@[a-zA-Z_.]+
Poslední příklad je jednoduchý regulární výraz pro vyhledání e-mailové adresy. Jak jistě víte, e-mailová adresa může mít mnoho podob, díky speciálním znakům můžeme nadefinovat, přes jaké servery má být dopis doručen, dokonce se dá posílat i na číselné adresy a podobně. Takový regulární výraz by však byl značně složitý (viz příklad v knize Mastering regular expresions, O`Reilly, který má i s komentářem několik stran). My se spokojíme s tím, že adresa je tvaru „něco před znakem at (@) a něco za ním“.