Chamtivé a líné kvantifikátory

Kvantifikátory jsou na první pohled velmi jednoduché, ale ve skutečnosti mohou být složité.

Měli bychom velmi dobře rozumět tomu, jak vyhledávání funguje, pokud plánujeme hledat něco složitějšího než /\d+/ .

Vezměme si následující úlohu jako příklad.

Máme text a potřebujeme nahradit všechny uvozovky "..." se značkami guillemet:«...» . V mnoha zemích jsou preferovány pro typografii.

Například:"Hello, world" by měl být «Hello, world» . Existují další uvozovky, například „Witam, świat!” (polština) nebo 「你好，世界」 (čínština), ale pro náš úkol zvolíme «...» .

První věc, kterou musíte udělat, je najít řetězce v uvozovkách a pak je můžeme nahradit.

Regulární výraz jako /".+"/g (citát, pak něco, pak druhý citát) se může zdát jako dobrá volba, ale není!

Zkusme to:

let regexp = /".+"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // "witch" and her "broom"

…Vidíme, že to nefunguje tak, jak bylo zamýšleno!

Místo hledání dvou shod "witch" a "broom" , najde jednu:"witch" and her "broom" .

To lze popsat jako „chamtivost je příčinou všeho zla“.

Hamtivé vyhledávání

K nalezení shody používá modul regulárních výrazů následující algoritmus:

• Pro každou pozici v řetězci
  • Snažte se najít vzor v dané pozici.
  • Pokud není shoda, přejděte na další pozici.

Z těchto běžných slov není zřejmé, proč regulární výraz selže, pojďme si tedy vysvětlit, jak funguje vyhledávání vzoru ".+" .

1. Prvním znakem vzoru je citace " .

   Modul regulárního výrazu se jej pokusí najít na nulové pozici zdrojového řetězce a "witch" and her "broom" is one , ale je tam a tam, takže okamžitě neexistuje žádná shoda.

   Pak postupuje:přejde na další pozice ve zdrojovém řetězci a pokusí se tam najít první znak vzoru, znovu selže a nakonec najde citaci na 3. pozici:

2. Citace je detekována a poté se engine pokusí najít shodu pro zbytek vzoru. Pokusí se zjistit, zda zbytek řetězce předmětu odpovídá .+" .

   V našem případě je dalším znakem vzoru . (tečka). Označuje „libovolný znak kromě nového řádku“, tedy písmeno dalšího řetězce 'w' sedí:

3. Poté se tečka opakuje kvůli kvantifikátoru .+ . Modul regulárních výrazů přidává do shody jeden znak za druhým.

   …Dokud? Všechny znaky odpovídají tečce, takže se zastaví pouze tehdy, když dosáhne konce řetězce:

4. Nyní motor dokončil opakování .+ a pokusí se najít další znak vzoru. Je to citace " . Ale je tu problém:řetězec skončil, nejsou tam žádné další znaky!

   Modul regulárních výrazů chápe, že to trvalo příliš mnoho .+ a začne couvat .

   Jinými slovy, zkrátí shodu pro kvantifikátor o jeden znak:

   Nyní předpokládá, že .+ končí jeden znak před koncem řetězce a pokusí se porovnat zbytek vzoru z této pozice.

   Pokud by tam byla uvozovka, hledání by skončilo, ale poslední znak je 'e' , takže neexistuje žádná shoda.

5. ...Takže engine sníží počet opakování .+ o jeden znak navíc:

   Citace '"' neodpovídá 'n' .

6. Motor neustále ustupuje:snižuje počet opakování pro '.' až do zbytku vzoru (v našem případě '"' ) odpovídá:

7. Zápas je dokončen.

8. První shoda je tedy "witch" and her "broom" . Pokud má regulární výraz příznak g , pak bude vyhledávání pokračovat od místa, kde končí první shoda. Ve zbytku řetězce is one již nejsou žádné uvozovky , takže žádné další výsledky.

To jsme pravděpodobně nečekali, ale tak to funguje.

V režimu hrabivosti (ve výchozím nastavení) se kvantifikovaný znak opakuje tolikrát, kolikrát je to možné.

Modul regulárních výrazů přidá do shody tolik znaků, kolik může pro .+ a poté je zkracuje jeden po druhém, pokud se zbytek vzoru neshoduje.

Pro náš úkol chceme něco jiného. V tom může pomoci líný režim.

Líný režim

Líný režim kvantifikátorů je opakem chamtivého režimu. To znamená:„opakujte minimální počet opakování“.

Můžeme to povolit vložením otazníku '?' za kvantifikátorem, takže se stane *? nebo +? nebo dokonce ?? pro '?' .

Aby bylo jasno:obvykle otazník ? je kvantifikátor sám o sobě (nula nebo jedna), ale pokud je přidán za jiný kvantifikátor (nebo dokonce sám za sebe) dostává jiný význam – přepíná režim shody z chamtivého na líný.

Regulární výraz /".+?"/g funguje tak, jak má:najde "witch" a "broom" :

let regexp = /".+?"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // "witch", "broom"

Abychom jasně porozuměli změně, pojďme sledovat vyhledávání krok za krokem.

1. První krok je stejný:najde vzor start '"' na 3. pozici:

2. Další krok je také podobný:engine najde shodu pro tečku '.' :

3. A teď jde hledání jinak. Protože máme líný režim pro +? , motor se nepokusí najít shodu s tečkou ještě jednou, ale zastaví se a pokusí se najít shodu se zbytkem vzoru '"' právě teď:

   Pokud by tam byla citace, vyhledávání by skončilo, ale je tam 'i' , takže neexistuje žádná shoda.

4. Poté modul regulárních výrazů zvýší počet opakování pro tečku a zkusí to ještě jednou:

   Opět neúspěch. Poté se počet opakování znovu a znovu zvyšuje…

5. …Dokud nebude nalezena shoda pro zbytek vzoru:

6. Další hledání začne od konce aktuální shody a přinese další výsledek:

V tomto příkladu jsme viděli, jak funguje líný režim pro +? . Kvantifikátory *? a ?? fungovat podobně – regulární výraz zvyšuje počet opakování pouze v případě, že se zbytek vzoru nemůže shodovat na dané pozici.

Lenost je povolena pouze pro kvantifikátor s ? .

Ostatní kvantifikátory zůstávají chamtivé.

Například:

alert( "123 456".match(/\d+ \d+?/) ); // 123 4

1. Vzor \d+ pokusí se najít shodu s co největším počtem číslic (režim nenasytnosti), takže najde 123 a zastaví se, protože dalším znakem je mezera ' ' .

2. Pak je ve vzoru mezera, která se shoduje.

3. Pak je tu \d+? . Kvantifikátor je v pomalém režimu, takže najde jednu číslici 4 a pokusí se zkontrolovat, zda se zbytek vzoru shoduje.

   …Ale ve vzoru po \d+? není nic .

   Líný režim neopakuje nic bez potřeby. Vzor je hotový, takže máme hotovo. Máme shodu 123 4 .

Moderní motory regulárních výrazů mohou optimalizovat interní algoritmy, aby fungovaly rychleji. Mohou tedy fungovat trochu jinak než popsaný algoritmus.

Ale abychom porozuměli tomu, jak regulární výrazy fungují, a vytvořili regulární výrazy, nepotřebujeme o tom vědět. Používají se pouze interně k optimalizaci věcí.

Složité regulární výrazy je obtížné optimalizovat, takže vyhledávání může také fungovat přesně tak, jak je popsáno.

Alternativní přístup

U regulárních výrazů často existuje více než jeden způsob, jak udělat stejnou věc.

V našem případě můžeme najít řetězce v uvozovkách bez líného režimu pomocí regulárního výrazu "[^"]+" :

let regexp = /"[^"]+"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // "witch", "broom"

Regulární výraz "[^"]+" dává správné výsledky, protože hledá uvozovku '"' následuje jeden nebo více bez uvozovek [^"] a poté závěrečnou uvozovku.

Když motor regulárních výrazů hledá [^"]+ zastaví opakování, když dosáhne závěrečné nabídky, a máme hotovo.

Vezměte prosím na vědomí, že tato logika nenahrazuje líné kvantifikátory!

Je to prostě jiné. Jsou chvíle, kdy potřebujeme jedno nebo druhé.

Podívejme se na příklad, kdy líné kvantifikátory selhávají a tato varianta funguje správně.

Chceme například najít odkazy ve tvaru <a href="..." class="doc"> , s libovolným href .

Jaký regulární výraz použít?

První nápad by mohl být:/<a href=".*" class="doc">/g .

Pojďme to zkontrolovat:

let str = '...<a href="link" class="doc">...';
let regexp = /<a href=".*" class="doc">/g;

// Works!
alert( str.match(regexp) ); // <a href="link" class="doc">

Fungovalo to. Ale podívejme se, co se stane, když je v textu mnoho odkazů?

let str = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href=".*" class="doc">/g;

// Whoops! Two links in one match!
alert( str.match(regexp) ); // <a href="link1" class="doc">... <a href="link2" class="doc">

Nyní je výsledek špatný ze stejného důvodu jako náš příklad „čarodějnic“. Kvantifikátor .* zabralo příliš mnoho znaků.

Zápas vypadá takto:

<a href="....................................." class="doc">
<a href="link1" class="doc">... <a href="link2" class="doc">

Upravme vzor vytvořením kvantifikátoru .*? líný:

let str = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href=".*?" class="doc">/g;

// Works!
alert( str.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

Nyní se zdá, že to funguje, existují dvě shody:

<a href="....." class="doc">    <a href="....." class="doc">
<a href="link1" class="doc">... <a href="link2" class="doc">

…Ale pojďme to otestovat na jednom dalším zadávání textu:

let str = '...<a href="link1" class="wrong">... <p style="" class="doc">...';
let regexp = /<a href=".*?" class="doc">/g;

// Wrong match!
alert( str.match(regexp) ); // <a href="link1" class="wrong">... <p style="" class="doc">

Teď se to nedaří. Shoda obsahuje nejen odkaz, ale také spoustu textu za ním, včetně <p...> .

Proč?

To je to, co se děje:

1. Nejprve regulární výraz najde odkaz začínající <a href=" .
2. Pak hledá .*? :zabere jeden znak (líně!), zkontrolujte, zda existuje shoda pro " class="doc"> (žádné).
3. Pak vezme další znak do .*? , a tak dále... až nakonec dosáhne " class="doc"> .

Ale problém je:to už je za odkazem <a...> , v jiném tagu <p> . Ne to, co chceme.

Zde je obrázek zápasu zarovnaný s textem:

<a href="..................................." class="doc">
<a href="link1" class="wrong">... <p style="" class="doc">

Potřebujeme tedy vzor hledat <a href="...something..." class="doc"> , ale jak chamtivé, tak líné varianty mají problémy.

Správná varianta může být:href="[^"]*" . Vezme všechny znaky uvnitř href atribut až do nejbližší nabídky, přesně to, co potřebujeme.

Funkční příklad:

let str1 = '...<a href="link1" class="wrong">... <p style="" class="doc">...';
let str2 = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href="[^"]*" class="doc">/g;

// Works!
alert( str1.match(regexp) ); // null, no matches, that's correct
alert( str2.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

Shrnutí

Kvantifikátory mají dva režimy práce:

Hamtivý

Ve výchozím nastavení se modul regulárních výrazů snaží opakovat kvantifikovaný znak tolikrát, kolikrát je to možné. Například \d+ spotřebovává všechny možné číslice. Když se stane nemožné spotřebovat více (žádné další číslice nebo konec řetězce), pak bude nadále odpovídat zbytku vzoru. Pokud nedojde ke shodě, sníží se počet opakování (backtracků) a pokusí se znovu.

Líný

Povoleno otazníkem ? za kvantifikátorem. Modul regulárních výrazů se před každým opakováním kvantifikovaného znaku snaží porovnat zbytek vzoru.

Jak jsme viděli, líný režim není „všelékem“ z chamtivého hledání. Alternativou je „vyladěné“ chamtivé vyhledávání s vyloučením, jako ve vzoru "[^"]+" .