閱讀(765) 書簽贊(0) 我要糾錯(cuò)

Javascript 貪婪量詞和惰性量詞

2023-02-17 11:01 更新

量詞乍一看非常簡(jiǎn)單，但實(shí)際上它們可能很棘手。

如果我們打算尋找比 /\d+/ 更復(fù)雜的東西，就需要理解搜索的工作原理。

以接下來(lái)的任務(wù)為例。

有一個(gè)文本，我們需要用書名號(hào)：?...? 來(lái)代替所有的引號(hào) "..."。在許多國(guó)家，書名號(hào)是排版的首選。

例如："Hello, world" 應(yīng)該變成 ?Hello, world?。還有其他引用，例如 ?Witam, ?wiat!”（波蘭語(yǔ)）或 「你好，世界」（中文），但對(duì)于我們的任務(wù)，讓我們選擇 ?...? 吧。

首先要做的是定位帶引號(hào)的字符串，然后替換它們。

像 /".+"/g（一個(gè)引號(hào)，然后是一些內(nèi)容，然后是另一個(gè)引號(hào)）這樣的正則表達(dá)式看起來(lái)可能很合適，但事實(shí)并非如此！

讓我們?cè)囈幌拢?

let regexp = /".+"/g;

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

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

……可以看出來(lái)它的運(yùn)行結(jié)果與預(yù)期不同！

它沒(méi)有找到匹配項(xiàng) "witch" 和 "broom"，而是找到："witch" and her "broom"。

這可被稱為“貪婪是萬(wàn)惡之源”。

貪婪搜索

為了查找到一個(gè)匹配項(xiàng)，正則表達(dá)式引擎采用了以下算法：

對(duì)于字符串中的每一個(gè)位置
- 嘗試匹配該位置的模式。
- 如果未匹配，則轉(zhuǎn)到下一個(gè)位置。

這樣簡(jiǎn)單的描述并不能說(shuō)清楚這個(gè)正則表達(dá)式匹配失敗的原因，所以讓我們?cè)敿?xì)說(shuō)明一下模式 ".+" 是如何進(jìn)行搜索的。

該模式的第一個(gè)字符是一個(gè)引號(hào) ?"?。

正則表達(dá)式引擎嘗試在源字符串 a "witch" and her "broom" is one 的位置 0 找到它，但那里有 a，所以匹配失敗。

然后繼續(xù)前進(jìn)：移至源字符串中的下一個(gè)位置，并嘗試匹配模式中的第一個(gè)字符，再次失敗，最終在第三個(gè)位置匹配到了引號(hào)：

找到引號(hào)后，引擎就嘗試去匹配模式中的剩余字符。它嘗試查看剩余的字符串是否符合 .+"。

在我們的用例中，模式中的下一個(gè)字符為 .（一個(gè)點(diǎn)）。它表示匹配除了換行符之外的任意字符，所以將會(huì)匹配下一個(gè)字符 'w'：

然后由于量詞 .+，點(diǎn)會(huì)重復(fù)。正則表達(dá)式引擎一個(gè)接一個(gè)字符地進(jìn)行匹配。

……什么時(shí)候會(huì)不匹配？點(diǎn)（.）能夠匹配所有字符，所以只有在移至字符串末尾時(shí)才停止匹配：

現(xiàn)在引擎完成了對(duì)重復(fù)模式 .+ 的搜索，并且試圖尋找模式中的下一個(gè)字符。是引號(hào) "。但是有一個(gè)問(wèn)題：對(duì)字符串的遍歷已經(jīng)結(jié)束，沒(méi)有更多字符了！

正則表達(dá)式引擎知道它為 .+ 匹配太多項(xiàng)了，所以開(kāi)始回溯。

換句話說(shuō)，它去掉了量詞匹配項(xiàng)的最后一個(gè)字符：

現(xiàn)在它假設(shè) .+ 的匹配在字符串的倒數(shù)第一個(gè)字符前的位置結(jié)束，并嘗試從該位置匹配模式的剩余部分。

如果那里有引號(hào)，則搜索將結(jié)束，但最后一個(gè)字符是 'e'，所以不匹配。

……所以引擎會(huì)將 .+ 的重復(fù)次數(shù)減少一個(gè)字符：

引號(hào) '"' 與 'n' 不匹配。

引擎不斷進(jìn)行回溯：它減少 '.' 的重復(fù)次數(shù)，直到模式的其余部分（在我們的用例中是 '"'）匹配到結(jié)果：

匹配完成。
所以，第一次匹配項(xiàng)是 ?"witch" and her "broom"?。如果正則表達(dá)式具有修飾符 ?g?，則搜索將從第一個(gè)匹配結(jié)束的地方繼續(xù)。字符串 ?is one? 的剩余部分不再有引號(hào)，因此沒(méi)有更多匹配項(xiàng)。

這可能不是我們所期望的，但這就是它的工作方式。

在貪婪模式下（默認(rèn)情況），量詞都會(huì)盡可能多地重復(fù)。

正則表達(dá)式引擎嘗試用 .+ 去匹配盡可能多的字符，然后在模式的其余部分不匹配時(shí)再將其逐一縮短。

對(duì)于這個(gè)任務(wù)，我們想要得是另一種結(jié)果。這也就是惰性量詞模式的用途。

惰性模式

惰性模式中的量詞與貪婪模式中的是相反的。它表示：“重復(fù)最少的次數(shù)”。

我們可以通過(guò)在量詞后面添加一個(gè)問(wèn)號(hào) '?' 來(lái)啟用它，這樣匹配模式就變成了 *? 或 +?，甚至將 '?' 變成 ??。

這么說(shuō)吧：通常問(wèn)號(hào) ? 本身就是一個(gè)量詞（0 或 1），但如果將其放到 另一個(gè)量詞（甚至是它自己）后面，就會(huì)有不同的含義 —— 它將匹配的模式從貪婪轉(zhuǎn)為惰性。

正則表達(dá)式 /".+?"/g 能夠按預(yù)期工作了：它找到了 "witch" 和 "broom"：

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

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

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

為了更清楚地理解這個(gè)變化，我們來(lái)一步步解析這個(gè)搜索過(guò)程。

第一步是一樣的：它在第三個(gè)字符的位置找到了模式的開(kāi)頭 '"'：

下一步也是類似的：引擎為 '.' 找到了一個(gè)匹配項(xiàng)：

接下來(lái)的搜索就有些不同了。因?yàn)槲覀儗?duì) +? 啟用了惰性模式，引擎不會(huì)去嘗試多匹配一個(gè)點(diǎn)的匹配字符，而會(huì)停止并立即嘗試對(duì)剩余的模式 '"' 進(jìn)行匹配：

如果這里有一個(gè)引號(hào)，搜索就會(huì)停止，但這里是一個(gè) 'i'，所以沒(méi)有匹配到引號(hào)。

接著，正則表達(dá)式引擎增加對(duì)點(diǎn)的重復(fù)搜索次數(shù)，并且再次嘗試：

又失敗了。然后重復(fù)次數(shù)一次又一次的增加……

……直到找到了模式中的剩余部分的匹配項(xiàng)：

接下來(lái)的搜索從當(dāng)前匹配的結(jié)尾開(kāi)始，并產(chǎn)生了下一個(gè)匹配項(xiàng)：

在這個(gè)例子中，我們看到了惰性模式的 +? 是怎樣工作的。量詞 *? 和 ?? 的工作方式類似 —— 正則表達(dá)式引擎僅在模式的其余部分無(wú)法在給定位置匹配時(shí)增加重復(fù)次數(shù)。

惰性模式僅對(duì)帶有 ? 的量詞啟用

其它量詞依舊保持貪婪模式。

例如：

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

模式 \d+ 嘗試匹配盡可能多的數(shù)字（貪婪模式），因此在它找到 123 時(shí)停止，因?yàn)橄乱粋€(gè)字符為空格 ' '。
然后模式中有一個(gè)空格，正好匹配。
然后是 \d+?。此量詞處于惰性模式，所以它匹配一個(gè)數(shù)字 4 后開(kāi)始嘗試去檢查模式的剩余部分是否匹配。

……但是在 \d+? 之后沒(méi)有其它內(nèi)容了。

惰性模式在不必要的情況下不會(huì)重復(fù)任何東西。模式結(jié)束，我們找到了匹配項(xiàng) 123 4。

優(yōu)化

現(xiàn)在正則表達(dá)式引擎會(huì)通過(guò)優(yōu)化內(nèi)部算法來(lái)提升效率。所以它們的工作方式和所描述的算法可能略有不同。

但如果只是為了了解正則表達(dá)式的工作原理和如何構(gòu)建正則表達(dá)式我們不需要知道這些。它們僅用于內(nèi)部算法優(yōu)化。

復(fù)雜的正則表達(dá)式是很難優(yōu)化的，因此搜索的過(guò)程也可以完全按照描述的方式進(jìn)行。

替代方法

使用正則表達(dá)式，通常有不止一種方式可以做相同的事。

在我們的例子中，我們可以在不啟用惰性模式的情況下使用正則表達(dá)式 "[^"]+" 找到帶引號(hào)的字符串：

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

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

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

正則表達(dá)式 "[^"]+" 給出了正確答案，因?yàn)樗檎乙粋€(gè)引號(hào) '"' 后跟一個(gè)或更多非引號(hào) [^"] 的字符，然后是結(jié)束的引號(hào)。

當(dāng)引擎尋找 [^"]+ 時(shí)，它會(huì)在匹配到結(jié)束的引號(hào)時(shí)停止重復(fù)，這樣就完成了。

請(qǐng)注意，這個(gè)邏輯并不能取代惰性量詞！

它們是不同的。我們?cè)诓煌闆r下可能會(huì)需要使用到其中的一個(gè)或另一個(gè)。

讓我們?cè)賮?lái)看一個(gè)使用惰性量詞失敗而使用這種變體能獲得預(yù)期結(jié)果的例子。

例如，我們想要找到 <a href="..." class="doc"> 形式的帶有任意 href 的鏈接。

該使用哪個(gè)正則表達(dá)式呢？

首先可能會(huì)想到：/<a href=".*" class="doc">/g。

驗(yàn)證一下：

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

// 有效！
alert( str.match(regexp) ); // <a href="link" class="doc">

……但如果文本中有多個(gè)鏈接呢？

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

// 蛤！一個(gè)匹配項(xiàng)中有兩個(gè)鏈接！
alert( str.match(regexp) ); // <a href="link1" class="doc">... <a href="link2" class="doc">

現(xiàn)在這個(gè)結(jié)果是錯(cuò)的，原因與我們的 “witches” 示例相同。量詞 .* 占用了太多字符。

匹配結(jié)果如下：

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

讓我們啟用惰性量詞 .*? 來(lái)修改模式：

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

// 正確了！
alert( str.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

現(xiàn)在能成功了，有兩個(gè)匹配項(xiàng)：

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

……但是讓我們用另外一個(gè)文本來(lái)測(cè)試看看：

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

// 錯(cuò)誤的匹配！
alert( str.match(regexp) ); // <a href="link1" class="wrong">... <p style="" class="doc">

現(xiàn)在它匹配錯(cuò)了。匹配項(xiàng)不僅包括了一個(gè)鏈接，還包括了它后面的很多文本，包括 <p...>。

為什么？

原因如下：

首先，正則表達(dá)式尋找鏈接的開(kāi)始：<a href="。
然后它尋找 .*?，取一個(gè)字符（惰性的?。?，然后檢查字符串的剩余部分是否與模式的剩余部分匹配（未匹配）。
然后再取一個(gè)字符到 .*? 中，以此類推……直到最終到達(dá) " class="doc">。

但問(wèn)題是：這已經(jīng)超出了鏈接 <a...>，已經(jīng)在另一個(gè)標(biāo)簽 <p> 中了。這不是我們想要的。

這是與匹配項(xiàng)在文本上對(duì)齊的示例：

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

所以，我們需要模式尋找 <a href="...something..." class="doc">，但貪婪模式和惰性模式都有問(wèn)題。

正確的變體可以是這樣的：href="[^"]*"。它會(huì)獲取 href 特性中的所有字符直到最近的引號(hào)，正好符合我們的需求。

舉個(gè)例子：

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;

// 有效！
alert( str1.match(regexp) ); // null，無(wú)匹配項(xiàng)，這是對(duì)的
alert( str2.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

總結(jié)

量詞有兩種工作模式：

貪婪模式

默認(rèn)情況下，正則表達(dá)式引擎會(huì)嘗試盡可能多地重復(fù)量詞字符。例如，\d+ 會(huì)消耗所有可能的字符。當(dāng)無(wú)法消耗更多（在尾端沒(méi)有更多的數(shù)字或字符串）時(shí)，然后它再匹配模式的剩余部分。如果沒(méi)有匹配，則減少重復(fù)的次數(shù)（回溯），并再次嘗試。

惰性模式

通過(guò)在量詞后添加問(wèn)號(hào) ? 來(lái)啟用。正則表達(dá)式引擎嘗試在每次重復(fù)量化字符之前匹配模式的其余部分。

正如我們所見(jiàn)，惰性模式并不是貪婪搜索的“靈丹妙藥”。另一種方式是使用排除項(xiàng)“微調(diào)”貪婪搜索，如模式 "[^"]+"。

任務(wù)

/d+? d+?/ 的匹配項(xiàng)

匹配的結(jié)果是什么？

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

解決方案

結(jié)果是：123 4。

首先，惰性模式 \d+? 嘗試去獲取盡可能少的數(shù)字，但它必須到達(dá)空格，因此需要匹配到 123。

然后，第二個(gè) \d+? 就只獲取一個(gè)數(shù)字，因?yàn)檫@就已經(jīng)足夠了。

查找 HTML 注釋

找出文本中的所有 HTML 注釋：

let regexp = /你的正則表達(dá)式/g;

let str = `... <!-- My -- comment
 test --> ..  <!----> ..
`;

alert( str.match(regexp) ); // '<!-- My -- comment \n test -->', '<!---->'

解決方案

我們需要找到注釋的起始位置 。

行得通的表達(dá)式可以是  —— 惰性量詞使得點(diǎn)在 --> 之前停止。我們還需要為點(diǎn)添加修飾符 s 以包含換行符。

否則找不到多行注釋：

let regexp = /<!--.*?-->/gs;

let str = `... <!-- My -- comment
 test --> ..  <!----> ..
`;

alert( str.match(regexp) ); // '<!-- My -- comment \n test -->', '<!---->'

尋找 HTML 標(biāo)簽

創(chuàng)建一個(gè)正則表達(dá)式來(lái)尋找所有（開(kāi)始和結(jié)束）HTML 標(biāo)簽及其特性。

用例：

let regexp = /你的正則表達(dá)式/g;

let str = '<> <a href="/"> <input type="radio" checked> <b>';

alert( str.match(regexp) ); // '<a href="/">', '<input type="radio" checked>', '<b>'

這里我們假設(shè)標(biāo)簽特征中不包含 < 和 >（包括被引號(hào)包裹的內(nèi)容），這樣就簡(jiǎn)單多了。

解決方案

答案是 <[^<>]+>。

let regexp = /<[^<>]+>/g;

let str = '<> <a href="/"> <input type="radio" checked> <b>';

alert( str.match(regexp) ); // '<a href="/">', '<input type="radio" checked>', '<b>'

以上內(nèi)容是否對(duì)您有幫助：

← Javascript 量詞 +, *, ? 和 {n}

Javascript 捕獲組 →

寫筆記

我要補(bǔ)充