個人理解正則表達式——懶惰匹配

2019-11-15 01:57:43

字體：大中小

來源：轉載

供稿：網(wǎng)友

個人理解正則表達式——懶惰匹配問題描述

本文鏈接：http://www.hcoding.com/?p=130

初學正則表達式的時候都有一個疑問，例如：需要匹配串 "_abc_123_" 中第一對"_"之間的字符，剛開始學習正則表達式的時候會寫成 "/_/w*_/"，匹配的結果就是"abc_123" 而不是"abc"了；大神說加上一個問號，"/_/w*?_/"，這時候匹配的結果就是"abc"。

我們知道'？'單獨使用的時候表示：重復零次或一次，而當'？'出現(xiàn)在重復限定符后面的，起的作用就是懶惰匹配，也就是匹配盡可能少的字符。懶惰限定符說明：

*?：重復任意次，但盡可能少重復
+?：重復1次或更多次，但盡可能少重復
??：重復0次或1次，但盡可能少重復
{n,m}?：重復n到m次，但盡可能少重復
{n,}?：重復n次以上，但盡可能少重復

對的，“盡可能少重復”，這就是對懶惰匹配的粗暴直白的解說。

那么怎么理解“盡可能少重復”呢？我們可以從正則表達式的忽略優(yōu)先量詞來解釋了。

忽略優(yōu)先量詞

量詞"*?"、"+?"、"??"、"{n,m}?"、"{n,}?"都屬于忽略優(yōu)先量詞，忽略優(yōu)先量詞使用的是在?、+、*、{}后面添加?組成的，忽略優(yōu)先在匹配的時候首先會嘗試忽略，如果失敗后回溯才會選擇嘗試。比如`ab??`匹配“abb”會得到‘a’而不是“ab”。當引擎匹配成功a后，由于是忽略優(yōu)先，引擎首先選擇不匹配b，繼續(xù)查看表達式，發(fā)現(xiàn)表達式結束了，那么引擎就直接上報匹配成功。具體我們通過下面的例子一步一步說明忽略優(yōu)先量詞工作原理。

例子

還是上面的例子，用"/_/w*?_/"匹配"_abc_123_" 中第一對"_"之間的字符。

開始匹配第一個'_'之后，‘/w*?’首先決定不需要匹配任何字符，因為它是忽略優(yōu)先量詞，這時候就拿表達式'/_/w*?_/'中的第二個'_'（'/w*?'后面的'_'）和目標串'_abc_123_'中的'a'匹配，匹配失敗，這時候才會拿'/w*?'去嘗試未匹配的分支（使用/w匹配a，嘗試匹配a成功）

下一步，是嘗試匹配，還是忽略呢？因為'/w*?'是忽略優(yōu)先量詞，會選擇忽略，那么就是重復上一步，'_'匹配b失敗，'/w*?'去嘗試未匹配的分支ab，以上步驟總共重復了3次后（直到表達式'/w*?'后面的'_'和目標串第二個'_'匹配），最終匹配出'abc'。

過程（開始匹配第一個'_'之后）：

表達式/_/w*?_/'中的第二個'_'和目標串'_abc_123_'中的'a'匹配，匹配失敗，'/w*?'嘗試匹配目標串'_abc_123_'中的'a'，匹配成功。
表達式/_/w*?_/'中的第二個'_'和目標串'_abc_123_'中的'b'匹配，匹配失敗，'/w*?'嘗試匹配目標串'_abc_123_'中的'ab'，匹配成功。
表達式/_/w*?_/'中的第二個'_'和目標串'_abc_123_'中的'c'匹配，匹配失敗，'/w*?'嘗試匹配目標串'_abc_123_'中的'abc'，匹配成功。
表達式/_/w*?_/'中的第二個'_'和目標串'_abc_123_'中的'_'匹配，匹配成功，匹配結束。結果為abc。