Hlavní navigace

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

Lukáš Zapletal

Nevíte, co je regulární výraz? Rádi byste si regulární výrazy vyzkoušeli? Zajímá vás, jak takový regulární výraz vypadá uvnitř? Děsí vás slovo automat? Pak je tento článek určen právě vám.

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.

Automat

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ů:

Tabulka č. 366

Výraz

Vysvětlení

Znaky
x znak x
\\ zpětné lomítko
\0n znak v osmičkovém kódu 0n (0 <= n <= 7)
\xhh znak v hexadecimálním kódu 0×hh
\uhhhh znak UNICODE v hexadecimálním kódu 0×hhhh
\t znak tabulátor (‚\u0009‘)
\n znak nového řádku (‚\u000A‘)
\r znak posunu vozíku (‚\u000D‘)
Skupiny znaků
[abc] výčet znaků: a, b, nebo c
[^abc] jakýkoli znak kromě: a, b, nebo c(negace)
[a-zA-Z] a až z nebo A až Z, včetně (rozsah)
[a-d[m-p]] a až d, nebo m až p: [a-dm-p](sjednocení)
[a-z&&[def]] d, e, nebo f (průnik)
[a-z&&[^bc]] a až z, kromě b ac: [ad-z](rozdíl)
Předdefinované skupiny znaků
\d číslice: [0–9]
\D opak číslice (negace): [^0–9]
\s bílý znak: [ \t\n\x0B\f\r]
\S opak bílého znaku: [^\s]
\w slovo: [a-zA-Z0-9]
\W opak slova: [^\w]
Hranice
^ začátek řádku
$ konec řádku
\b hranice slova
\B opak hranice slova (negace)
Kvantifikátory
X? X, žádný nebo jeden
X* X, žádný nebo více
X+ X, jeden nebo více
X{n} X, přesně nkrát
X{n,} X, minimálně nkrát
X{n,m} X, minimálně nkrát, ale ne více než mkrát
Logické spojky
XY X ihned zaY
X|Y X neboY
(X)

párování logických spojek
slouží také k zapamatování při nahrazování pomocí \1 až \\n/p>

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“.

Našli jste v článku chybu?

31. 5. 2011 13:36

Georgo (neregistrovaný)

Potřeboval bych vyhledat pomocí regulárního výrazu na začátku souboru speciální znaky v hexdecimálním formátu, můžete mi prosím poradit jak na to?

Zkoušel jsem níže uvedený výraz, ale bezvýsledně (pravděpodobně budou na vině mezery mezi dvoucifernými hodnotami).
^00 00 01 00


20. 3. 2011 12:32

padan (neregistrovaný)

Dobry den,
prosim mohli byste mi nekdo vysvetlit, co znamena (()|a|b|c|d)*?
hledal jsem to v tech vysvetlivkach, ale nedava mi to smysl. Je to libovolna permutace ze znaku a,b,c,d a ()?



DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Vitalia.cz: Když přijdete o oko, přijdete na rok o řidičák

Když přijdete o oko, přijdete na rok o řidičák

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Vitalia.cz: I církev dnes vyrábí potraviny

I církev dnes vyrábí potraviny

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Podnikatel.cz: Snížení DPH na 15 % se netýká všech

Snížení DPH na 15 % se netýká všech

Vitalia.cz: Taky věříte na pravidlo 5 sekund?

Taky věříte na pravidlo 5 sekund?

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy