Regulární výrazy - část 2
Základy opakování

V předchozí části jsem popsal základní prvky regulárních výrazů. Konstrukce, které jsem z nich vytvářel, měly jednu společnou nevýhodu: pevně daný počet znaků hledaného řetězce. V dnešní části se budu věnovat mechanismu opakování. Díky němu lze zajistit, že řetězec odpovídající regulárnímu výrazu může mít proměnlivou délku.

Opakování výrazu

Základní konstrukcí pro opakování regulárních výrazů je hvězdička (*). Znamená, že regulární výraz bezprostředně před ní se může zopakovat, kolikrát to jenom jde.

Příklad:
Výrazu A* tedy vyhoví libovolný počet písmen "A", zatímco [0-9]* ztělesňuje libovolně dlouhou posloupnost číslic (opakovaným regulárním výrazem je zde [0-9], tedy libovolná číslice).

V řadě programovacích jazyků je identifikátor definován jako libovolně dlouhá posloupnost písmen a číslic začínající písmenem. Pomocí regulárního výrazu bychom jej zapsali jako [a-zA-Z][a-zA-Z0-9]*. Zdůrazňuji, že opakování se týká jen regulárního výrazu, který je uveden bezprostředně před hvězdičkou. Uvedený výraz tedy znamená "právě jeden výskyt [a-zA-Z] (písmeno), za nímž následuje libovolný počet výskytů [a-zA-Z0-9] (písmeno nebo číslice)".

Snad nejběžnějším opakovaným výrazem je tečka, která v kombinaci s hvězdičkou (.*) znamená "libovolný řetězec znaků". V souvislosti s opakováním si dobře zapamatujte tři důležité skutečnosti:

• do libovolného počtu opakování se počítá i nula
• opakování se týká regulárního výrazu, nikoli řetězce, který je s ním porovnáván
• opakování je hladové - snaží se "pozřít" co nejvíc znaků

Přípustnost nulového počtu opakování znamená, že opakovanému regulárnímu výrazu vždy může vyhovět i prázdný řetězec. Praktickým důsledkem je, že jen vzácně dává smysl vyhledávat samotný opakovaný výraz. Zpravidla je třeba jej alespoň z jedné strany ohraničit něčím povinným.

Příklad:
Chcete-li vyhledat v textu všechna čísla, nemá smysl hledat "libovolně dlouhou posloupnost číslic" ([0-9]*), protože posloupnost číslic nulové délky obsahuje každý řádek (vyzkoušejte grep '[0-9]*' soubor na libovolný soubor - uvidíte, že "najde" všechny jeho řádky). Správně je třeba hledat "alespoň jednu číslici", tedy použít regulární výraz [0-9][0-9]*.

Skutečnost, že opakování se týká regulárního výrazu, nikoli srovnávaného řetězce, je velmi důležitá. Zapíšete-li .*, spojujete dva prvky: symbol pro libovolný znak a symbol opakování. Výslednou konstrukci lze chápat dvěma způsoby. Buď jako libovolný počet libovolných znaků (opakování regulárního výrazu) nebo že v textu může být libovolný znak a ten se pak může opakovat, kolikrát chce (opakování ve zkoumaném řetězci). Správný je první výklad, jinak bychom se z toho nejspíš zbláznili.

Hladovost opakování se projevuje tím, že opakovaný regulární výraz se vždy snaží roztáhnout na co největší délku - zahrnout do sebe co největší počet znaků zkoumaného řetězce. Proto když například řetězec "brambora" srovnáte s regulárním výrazem r.*a (libovolný řetězec znaků začínající "r" a končící "a"), bude vyhovujícím řetězcem "rambora" (od prvního "r" až po poslední "a").

Regulární výrazy versus žolíkové znaky

Začátečníci někdy zaměňují regulární výrazy s žolíkovými znaky. Jistá podobnost tu skutečně je - oba prostředky umožňují vytvářet jakési vzory, které jsou porovnávány se skutečnými daty. Existují mezi nimi dva zásadní rozdíly. Žolíkové znaky se týkají názvů souborů a zpracovává je interpret příkazů (shell). Naproti tomu regulární výrazy se zaobírají obsahem (textových) souborů a jejich interpretaci mají na starosti jednotlivé programy (editory, grep a podobně).

Případným omylům ještě nahrává podobnost některých speciálních znaků mezi oběma konstrukcemi. V tomto směru je záhodno především mít na paměti, že zatímco v žolíkových znacích * představuje libovolný řetězec, v regulárních výrazech se libovolný řetězec zapisuje pomocí .*.

Mechanika srovnávání

Pojmem srovnávání (matching) se označuje proces, kdy program hledá, zda předložený řetězec znaků odpovídá regulárnímu výrazu či nikoli. Zároveň se program snaží stanovit, které části řetězce odpovídají jednotlivým částem regulárního výrazu.

Dokud se zabýváte pouze hledáním, je pro vás v podstatě nezajímavé, kde přesně byl daný vzor nalezen. Ovšem když používáte regulární výrazy k nahrazování (a právě v tom je jejich největší síla), je tato informace velmi důležitá.

Základní princip srovnávání je následující: začne se od začátku řetězce. Každému prvku regulárního výrazu se snaží přiřadit vždy co nejdelší posloupnost znaků ze zkoumaného textu a teprve pak pokračuje srovnáváním dalších částí. Pokud to později nevyjde, vrátí se zpět a zkusí přidělený řetězec o jeden znak zkrátit. Jestliže již zkrátil na minimum vše, co zkrátit šlo, a přesto se nepodařilo najít shodu, posune se na další znak zkoumaného textu a vše se rozjede znovu.

Příklad:
Podívejme se, jak by vypadalo srovnávání regulárního výrazu r.*[0-9]*o s řetězcem "Brambory jsou na poli". Při hledání by postupoval takto:

1. 

2. 

3. 

4. 

5. 

Z příkladu je vidět, že díky své hladovosti regulární výraz zabere co největší část řetězce - od prvního "r" až po poslední "o". Výrazu .* je nakonec přiřazen řetězec "ambory jsou na p". Výrazu [0-9]* srovnávání přidělí prázdný řetězec. Zdánlivě proto, že zkoumaný text neobsahuje žádné číslice. Ve skutečnosti však řetězec odpovídající tomuto výrazu zůstane prázdný vždy, protože je umístěn nesmyslně. Předchází mu totiž obecnější regulární výraz s opakováním. Jakýkoli znak, který by mohl vyhovovat [0-9]* vyhovuje také předchozímu .*, které jej díky své hladovosti sežere a na [0-9]* nezbyde nic.

Ze stejného důvodu když libovolný řetězec znaků srovnáte s regulárním výrazem .*.*, bude prvnímu .* přiřazen celý zkoumaný řetězec a druhému .* prázdný řetězec.

Příliš hladové opakování

Na hladovost opakování je třeba si dávat pozor. Díky ní se snadno může stát, že opakující se výraz pohltí i ty znaky, se kterými jste nepočítali. Klasickým příkladem tohoto chování je regulární výraz pro řetězec znaků v uvozovkách.

Začátečníci mají často tendenci uvažovat následovně: řetězec v uvozovkách, to jsou otevírací uvozovky, pak cokoli a na konci druhé uvozovky. To vyjádříme regulárním výrazem ".*". Problém je, že díky hladovosti hvězdičky se tento regulární výraz roztáhne od prvních uvozovek ve zkoumaném řetězci až po poslední. Takže například když jej vypustíte na řetězec 'Volali "Ahój" a "Nazdár".', dopadne to takto:

Řešením je nepřipouštět v uzavřeném řetězci libovolné znaky, ale pouze znaky jiné než koncový. V našem případě cokoli kromě uvozovek, takže tím správným regulárním výrazem bude "[^"]*":

Mimochodem - kdybyste na řetězec aplikovali výraz .*".*", roztáhne se první .* na 'Volali "Ahój" a ' a druhé .* na 'Nazdár'. Jelikož jsou v regulárním výrazu povinné uvozovky, nemůže první .* schramstnout všechno. Ukousne si však co nejvíc, čímž druhé .* omezí na minimum.

(c) Pavel Satrapa, 2000