Rekurze regulárních výrazů

Školení, která pořádám

Když někdo říká, že umí dobře regulární výrazy, tak mu obvykle položím tuto otázku: „Jaký je rozdíl mezi once-only subpattern a possessive quantifier a kdy je použiješ?“ Schválně si na tuhle otázku teď zkuste odpovědět.

Once-only subpattern (?>) se vyznačuje tím, že zkonzumuje, co se dá, a nikdy se nevrací. Pokud tedy za zkonzumovanou částí nenajde text odpovídající zbytku regulárního výrazu, tak skončí chybou. Jindy se v takových situacích pokusí regulární stroj vrátit a hledat shodu dřív.

Possessive quantifier se zapisuje jako plus za kvantifikátorem, např. *+. Tento výraz je velmi podobný – sežere, co jde, a nikdy se nevrací. Jediný rozdíl je tedy v tom, že possessive quantifier je trochu stručnější, pokud chceme vyjádřit opakování. a*+ se dá zapsat jako (?>a*). Naopak to jde taky, i když trochu krkolomněji – (?>ab) se dá zapsat jako (?:ab){1}+. Odpověď na první část otázky tedy je, že rozdíl mezi těmito výrazy není žádný a používají se ve stejných situacích.

Používají se tehdy, když potřebujeme zabránit rekurzi, kterou regulární stroj používá při hledání shody. Na její limit (pcre.recursion_limit) můžeme narazit především při použití opakování uvnitř opakování, např. (\d+,)*.

Alternativou k regulárním strojům používajícím rekurzi nabízí knihovna RE2, která zaručuje běh v lineárním čase. Je trochu omezenější než Perlové regulární výrazy, např. nepodporuje lookahead aserce. Existuje i verze pro PHP, nicméně kvůli její nedostatečné rozšířenosti ji nepoužívám.

Jakub Vrána, Seznámení s oblastí, 25.6.2014, diskuse: 1 (nové: 0)

Diskuse

Jan Tvrdík:

ad „zkonzumuje, co se dá, a nikdy se nevrací“:
To je podle mě zavádějící, protože rozhodě neplatí, že zkonzumuje vždy nejdelší možnou část. Naopak si vždy vybere první přípustnou část.

Proto např. regulárnímu výrazu ^(?>a|ab)$ nevyhoví řetězec ab a regulárnímu výrazu ^(?>a*?)$ nevyhoví řetězec aa

Vložit příspěvek

Používejte diakritiku. Vstup se chápe jako čistý text, ale URL budou převedeny na odkazy a PHP kód uzavřený do <?php ?> bude zvýrazněn. Pokud máte dotaz, který nesouvisí s článkem, zkuste raději diskusi o PHP, zde se odpovědi pravděpodobně nedočkáte.

Jméno: URL:

avatar © 2005-2016 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.