主頁 > 知識庫 > 循序漸進(jìn)掌握遞歸正則表達(dá)式【推薦】

循序漸進(jìn)掌握遞歸正則表達(dá)式【推薦】

熱門標(biāo)簽:西藏智能外呼系統(tǒng)代理商 ai電話機(jī)器人搭建 外呼系統(tǒng)無呼出路由是什么原因 甘肅醫(yī)療外呼系統(tǒng)排名 呼叫系統(tǒng)外呼只能兩次 400電話辦理電話辦理 梅縣地圖標(biāo)注 貴港公司如何申請400電話 地圖標(biāo)注教學(xué)點(diǎn)

一般來說,遞歸的正則表達(dá)式用來匹配任意嵌套層次的結(jié)構(gòu)或左右對稱的結(jié)構(gòu)。例如匹配:

((((()))))
(hello (world) good (boy) bye)
p>hello world strong>hello world/strong> /p>
abc.def.ghij...stu.vwx.yz
abcdcba
123454321

遞歸正則在正則表達(dá)式里算是比較靈活的部分,換句話說就是可能會比較難。下面這個(gè)正則表達(dá)式是在網(wǎng)上流傳的非常廣泛的遞歸正則的示例,它用來匹配嵌套任意次數(shù)的括號,括號內(nèi)可以有其它字符,比如可以匹配(a(bc)de)、(abc(bc(def)c)de)。

# 使用了x修飾符,忽略正則表達(dá)式內(nèi)的空白符號
/\( ( (?>[^()]+) | (\g0>) )* \)/x

這似乎看不怎么懂?其實(shí)即使知道了正則遞歸的方式,也還是很難看懂(至少,我分析了很久)。

難懂的原因大概是因?yàn)檫@里使用的固化分組在多選分支|中屬于一個(gè)技巧性的寫法,而且分組外還使用了量詞*,這些結(jié)合起來就太難懂了。

正因?yàn)榫W(wǎng)上到處流傳這個(gè)例子,曾使我多次對遞歸正則的學(xué)習(xí)望而卻步。這里我也不去解釋這個(gè)遞歸正則的含義,因?yàn)?太學(xué)術(shù)化"或者說"太裝xyx逼",而一般遞歸正則完全可以寫的很簡單但卻能實(shí)現(xiàn)目標(biāo)。

如何寫出簡單易懂版本的遞歸正則并且理解遞歸正則的匹配方式,正是本文的目標(biāo)。在后文,我介紹了一個(gè)更加簡單、更加容易理解的版本,同樣能實(shí)現(xiàn)這個(gè)遞歸匹配的需求。

為了解釋清楚遞歸正則,本文會以循序漸進(jìn)的方式逐步深入到遞歸正則的方方面面。所以,篇幅可能稍大,其中大量篇幅都用在了解釋分析遞歸正則是如何遞歸匹配上。

注:
本文以Ruby的正則表達(dá)式來介紹遞歸正則,但對其它支持遞歸正則的語言也是能通用的。例如Perl、PHP、Python(自帶的re不提供,但第三方庫regex提供遞歸正則)等。

理解反向引用\N和\g

首先通過正則表達(dá)式的反向引用的用法來逐步引入遞歸正則表達(dá)式的用法。

正則表達(dá)式(abc|def) and \1xyz可以匹配字符串"abc and abcxyz"或"def and defxyz",但是不能匹配"abc and defxyz"或def and abcxyz。這是因?yàn)椋聪蛞迷谝玫臅r(shí)候,只能引用之前分組捕獲成功后的那個(gè)結(jié)果。

reg = /(abc|def) and \1xyz/
reg =~ "abc and abcxyz" #=>0
reg =~ "def and defxyz" #=>0
reg =~ "def and abcxyz" #=>nil
reg =~ "abc and defxyz" #=>nil

但是,如果使用\g1>來代替\1,那么就能匹配這四種情形的字符串(Perl中使用(?1)對應(yīng)這里的\g1>):

reg = /(abc|def) and \g1>xyz/

reg =~ "abc and abcxyz" #=>0
reg =~ "def and defxyz" #=>0
reg =~ "def and abcxyz" #=>0
reg =~ "abc and defxyz" #=>0

\g1>和\1的區(qū)別在于:\1在反向引用的時(shí)候,引用的是該分組捕獲到的結(jié)果值,\g1>則不是反向引用,而是直接將索引號為1的分組捕獲重新執(zhí)行捕獲分組的匹配操作。相當(dāng)于是/(abc|def) and (abc|def)xyz/。

所以,\1相當(dāng)于是在引用的位置插入索引號為1的分組捕獲的結(jié)果,\g1>相當(dāng)于是在此處插入索引號為1的分組捕獲表達(dá)式,讓其能再次進(jìn)行分組表達(dá)式這部分的匹配操作。

如果把分組捕獲表達(dá)式看作是函數(shù)的定義,那么開始匹配時(shí)表示調(diào)用該函數(shù)進(jìn)行分組捕獲。而反向引用\N則是在引用位置處插入該函數(shù)的返回值,\gname>則表示在此處再次調(diào)用該函數(shù)進(jìn)行匹配。

\gname>的name可以是數(shù)值型的分組索引號,也可以是命名捕獲的名稱索引,還可以是0表示整個(gè)正則表達(dá)式自身。

/(abc|def) and \g1>xyz/
/(?var>abc|def) and \gvar>xyz/
/(abc|def) and \g0>xyz/ # 錯(cuò)誤正則,稍后分析

=begin
# Perl、Python(regex,非re)、PHP與之對應(yīng)的方式:
\g0> -> (?R)或(?0)
\gN> -> (?N)
\gname> -> (?P>name)或(?name)
=end

前面兩種好理解,第三種使用\g0>就不太能理解了,繼續(xù)向下看。

初探遞歸正則:遞歸正則匹配什么

\g0>表示正則表達(dá)式自身,所以這相當(dāng)于是遞歸正則表達(dá)式,假如進(jìn)行第一輪正則表達(dá)式替換的話,相當(dāng)于:

/(abc|def) and (abc|def) and \g0>xyzxyz/

當(dāng)然,這里只是為了幫助理解才將\g0>替換成正則表達(dá)式,但它不會真的直接替換正則表達(dá)式的定義。就像函數(shù)調(diào)用時(shí),不會在調(diào)用函數(shù)的地方替換成函數(shù)定義里的代碼再去執(zhí)行,函數(shù)定義了就能多次復(fù)用。

不管怎樣,不難發(fā)現(xiàn)這里已經(jīng)出現(xiàn)了無限遞歸的可能性,因?yàn)樘鎿Q一輪后的正則表達(dá)式中再次包含了\g0>,它可以再次進(jìn)行第二輪替換、第三輪替換......

那么,對于/(abc|def) and \g0>xyz/這個(gè)遞歸的正則表達(dá)式來說,它能匹配什么樣的字符串呢?這才是理解正則遞歸時(shí)最需要關(guān)心的。

可以將上面的\g0>看作是一個(gè)占位符,首先它可以匹配"abc and _xyz"或者def and _xyz這種格式的字符串,這里我用了_表示\g0>占位符。遞歸一輪的話,它可以匹配"abc and def and _xyzxyz",這里又會繼續(xù)遞歸下去,將沒完沒了。所以這里先將該正則匹配什么字符串的問題保留,稍后再回頭分析。

事實(shí)上,/(abc|def) and \g0>xyz/是錯(cuò)誤的正則表達(dá)式,它會提示我們,遞歸沒有終點(diǎn):


/(abc|def) and \g0>xyz/
#=>SyntaxError: never ending recursion

所以,使用遞歸正則必須要保證遞歸能夠有終點(diǎn)。

保證正則遞歸的終點(diǎn)

怎么保證遞歸正則的終點(diǎn)呢?只要給\g>這部分做一個(gè)量詞的限定即可,比如:

\g0>+  # 錯(cuò)誤正則
\g0>{3}  # 錯(cuò)誤正則
\g0>{,3}  # 錯(cuò)誤正則

\g0>*  # 正確正則
\g0>?  # 正確正則
\g0>{0}  # 正確正則
pat|\g0>  # 正確正則
(\g0>)*  # 正確正則
(\g0>)?  # 正確正則
...

\g0>+表示遞歸至少1輪,但是這里已經(jīng)錯(cuò)了,因?yàn)檫f歸多次的時(shí)候,\g0>這個(gè)占位符及其量詞+將始終保留在最后一輪的結(jié)果中,于是導(dǎo)致無限遞歸。同理\g0>{3}這種表示嚴(yán)格遞歸三次的方式也是錯(cuò)誤的,因?yàn)檫f歸第三次后仍然保留了\g0>{3}占位符及其量詞{3},這也將無限遞歸。

所以,只有\(zhòng)g0>*和\g0>?和\g0>{0}和pat|\g0>等這種能在量詞數(shù)量選擇意義上表示遞歸0次的方式才是正確的正則表達(dá)式語法,因?yàn)闊o論遞歸多少次,最后一次的占位符的量詞都可以是0次,從而達(dá)到遞歸的終點(diǎn),即停止遞歸。

所以,修改前面的正則表達(dá)式,假如使用?量詞修飾\g>:

/(abc|def) and \g0>?xyz/

再探遞歸正則:遞歸正則匹配什么

回到之前遺留的問題,現(xiàn)在這個(gè)正確的遞歸正則表達(dá)式/(abc|def) and \g0>?xyz/能匹配什么樣的字符串呢?

按照之前的分析,它能匹配的字符串的模式類似于abc and _?xyz或者def and _?xyz。

如果量詞?取0次,那么該遞歸正則匹配的是"abc and xyz"或"def and xyz":

reg = /(abc|def) and \g0>?xyz/
reg =~ "abc and xyz" #=> 0
reg =~ "def and xyz" #=> 0

如果量詞?取1次,那么該遞歸一輪后的正則模式為abc and abc and _?xyzxyz,其中任何一個(gè)"abc"替換成"def"都是滿足條件的。那么這里又有了\g>量詞的次數(shù)選擇問題。

假如這里量詞?取0次,也就是從開始到現(xiàn)在總體遞歸了一輪。那么該遞歸正則匹配到是:

reg = /(abc|def) and \g0>?xyz/
reg =~ "abc and abc and xyzxyz" #=> 0
reg =~ "abc and def and xyzxyz" #=> 0
reg =~ "def and def and xyzxyz" #=> 0
reg =~ "def and abc and xyzxyz" #=> 0

如果遞歸一輪后的量詞?繼續(xù)取1次呢?那么下一輪遞歸仍將會有量詞次數(shù)選擇的問題。

至此,應(yīng)該理解了遞歸正則的基本匹配方式。不過這里使用的\g0>遞歸還很基礎(chǔ),下面將繼續(xù)逐步深入。

深入遞歸(1):括號分組內(nèi)的\g

前面的遞歸示例中是將能表示遞歸的表達(dá)式\g0>部分放在分組的外面,這種情況下,只有\(zhòng)g0>這種形式才能算是遞歸,如果是\g1>或\gname>,就算不上是遞歸,充其量也就是個(gè)表達(dá)式的調(diào)用。

但是,當(dāng)需要使用遞歸正則來解決問題的時(shí)候,遞歸表達(dá)式往往是在分組內(nèi)部而不是在分組外部的。所以,前面解釋的遞歸方式其實(shí)非常少見。于是,要使用遞歸正則,還得繼續(xù)深入探索。

首先看一個(gè)非常簡單的組內(nèi)遞歸正則表達(dá)式:

/(abc\g1>?xyz)+/

這個(gè)表達(dá)式中,進(jìn)行了一個(gè)分組捕獲,這個(gè)分組首先匹配abc字符,然后在分組捕獲內(nèi)使用了表達(dá)式\g1>?(注意這個(gè)?是不能少的,當(dāng)然?也可以換成其它的前面解釋過的量詞),緊隨其后的是匹配字符xyz。由于這里的\g1>?放在1號索引對應(yīng)的分組捕獲的內(nèi)部,所以就形成了一個(gè)遞歸的正則表達(dá)式。

問題是,這個(gè)正則表達(dá)式能匹配什么樣的字符串呢?要學(xué)會遞歸正則表達(dá)式,必須會分析它能夠匹配什么類型的字符串。

仍然,以占位符的方式來表示\g1>,那么該遞歸正則表達(dá)式匹配的字符串模式為:"abc_?xyz" * N,這個(gè)* N表示重復(fù)N次,因?yàn)檫@種表達(dá)式的括號分組外面有一個(gè)+符號。

如果量詞?選擇為0次,也就是不進(jìn)行遞歸,則匹配字符串"abcxyz" * N:

/(abc\g1>?xyz)+/ =~ "abcxyz" #=> 0

/(abc\g1>?xyz)+/ =~ "abcxyzabcxyz"
#=> 0

/(abc\g1>?xyz)+/ =~ "abcxyzabcxyzabcxyz"
#=> 0

/(abc\g1>?xyz)+/ =~ "abcxyz" * 10
#=> 0

如果量詞?選擇為1次,那么進(jìn)行一輪遞歸后,匹配的字符串模式為:"abcabc_?xyzxyz" * N。再次進(jìn)行?量詞的次數(shù)選擇,假如選0次,那么匹配的字符串是"abcabcxyzxyz" * N:

/(abc\g1>?xyz)+/ =~ "abcabcxyzxyz" #=> 0
/(abc\g1>?xyz)+/ =~ "abcabcxyzxyzabcabcxyzxyz"
#=> 0
/(abc\g1>?xyz)+/ =~ "abcabcxyzxyz" * 3
#=> 0

再繼續(xù)分析一輪遞歸。假設(shè)這是?量詞選擇1次,那么進(jìn)行第二輪的遞歸,匹配的字符串模式為:"abcabcabc_?xyzxyzxyz" * N。

至此,應(yīng)該不難推測出遞歸正則表達(dá)式/(abc\g1>?xyz)+/匹配的字符串的模式:

"abcxyz" * N
"abcabcxyzxyz" * N
"abcabcabcxyzxyzxyz" * N
# 歸納后,即匹配如下通用模式:n和N均大于等于1
("abc" * n + "xyz" * n) * N

將目光集中于剛才的遞歸正則表達(dá)式/(abc\g1>?xyz)+/,如果能通過這個(gè)正則表達(dá)式直接推測匹配何種類型字符串呢?

量詞+或其它可能的量詞先不看,先將焦點(diǎn)放在分組捕獲。這個(gè)分組捕獲匹配的是abc_?xyz,如果要進(jìn)行遞歸N輪,那么每一輪都是abc_?xyz這種模式,直接將其替換到該正則中去觀察:abc(abc_?xyz)*xyz,其中(abc_?xyz)*表示這部分重復(fù)0或N次。當(dāng)然替換后的這部分不是標(biāo)準(zhǔn)的正則,只是為了有助于理解才將不同地方的概念混在一起,我想并不會對你的理解造成歧義。

這樣理解起來就不難了。當(dāng)然這個(gè)遞歸正則比較簡單,如果把上面的\g1>?換成\g1>*,看上去又會更復(fù)雜一點(diǎn)。那么它匹配什么樣的字符串呢?

同樣的分析方式,將/(abc\g1>*xyz)+/看作是"abc_*xyz" * N的結(jié)構(gòu),然后對*取值,假設(shè)取值3次,所以遞歸后的結(jié)果看上去類似于:

"abc(abc_*xyz)(abc_*xyz)(abc_*xyz)xyz" * N

上面的每個(gè)括號里都可以對量詞*做選擇,但要到達(dá)遞歸的終點(diǎn),最后(可能是遞歸了好多輪后)每一個(gè)遞歸里的*都必須取值0次才能終結(jié)這個(gè)遞歸。

所以,假如現(xiàn)在這3個(gè)括號里的每個(gè)*都選擇0次,那么匹配的字符串模式類似于:

"abc(abcxyz)(abcxyz)(abcxyz)xyz" * N

# 即等價(jià)于:n和N均大于等于1
( "abc" + "abcxyz" * n + "xyz" ) * N

例如:

/(abc\g1>*xyz)+/ =~ ( "abc" + "abcxyz" * 1 + "xyz" ) * 1
#=> 0
/(abc\g1>*xyz)+/ =~ ( "abc" + "abcxyz" * 1 + "xyz" ) * 2
#=> 0
/(abc\g1>*xyz)+/ =~ ( "abc" + "abcxyz" * 4 + "xyz" ) * 2
#=> 0

假如上面三個(gè)括號里第一個(gè)括號里的*取值1次,后面兩個(gè)括號里的*取值0次,那么再次遞歸后,匹配的字符串模式類似于:

"abc(abc(abc_*xyz)xyz)(abcxyz)(abcxyz)xyz" * N

沒錯(cuò),又要做量詞的次數(shù)選擇。假如這次*取0次,那么將終結(jié)本次遞歸匹配,它匹配的字符串模式為:

"abc(abc(abcxyz)xyz)(abcxyz)(abcxyz)xyz" * N

那么如果*不是按照上面的次數(shù)進(jìn)行選擇的,那么匹配的字符串模式是怎樣的?

沒有答案,唯一準(zhǔn)確的答案就是回歸這個(gè)正則表達(dá)式的含義:它匹配的字符串模式為(abc\g1>*xyz)+。

深入遞歸(2):寫遞歸正則(入門)

前面一直都是根據(jù)給定的遞歸正則表達(dá)式去分析能匹配什么樣的字符串,這對于理解遞歸正則有所幫助。但是我們更想要掌握的是如何根據(jù)字符串寫出遞歸的正則表達(dá)式。

一般來說,要使用遞歸正則去匹配,往往是要匹配嵌套的一些東西,如果不是匹配嵌套內(nèi)容,很可能不會想到要去用遞歸正則。這里,假設(shè)也要去匹配嵌套的東西。

先從簡單的嵌套開始。比如,如何匹配無限嵌套的空括號()、(())、((())),即"(" * n + ")" * n?

分析一下。如果不遞歸的話,那就是匹配一對小括號(),所以這兩小括號字符必須要在分組內(nèi),即(\(\))。(如果使用\g0>來遞歸的話,則可以不用在分組內(nèi),不過這里先不考慮這種情況。)

按照前文多次對遞歸正則表達(dá)式匹配何種字符串的分析,用占位符替代要遞歸的話,要匹配的嵌套括號的字符串模式大概是這樣的:(_)。所以遞歸表達(dá)式\g1>要在\(和\)的中間,即(\(\g1>\))。

這里還少了個(gè)量詞來保證遞歸的終點(diǎn)。那么使用什么樣的量詞呢?

使用\g1>*肯定沒問題,只要*號每次遞歸都只選擇量詞1次,并且最后一輪遞歸選擇0次終結(jié)遞歸即可,那么匹配的模式是((_*))、(((_*)))等等,這正好符合嵌套匹配。

/(\(\g1>*\))/ =~ "(" * 1 + ")" * 1
#=> 0
/(\(\g1>*\))/ =~ "(" * 3 + ")" * 3
#=> 0
/(\(\g1>*\))/ =~ "(" * 10 + ")" * 10
#=> 0

看別人寫的遞歸正則,往往會在分組后加上*號量詞,即(\(\g1>*\))*,針對于這種模式的嵌套,其實(shí)這個(gè)*是多余的,它要匹配成功,這個(gè)量詞必須只能選0或1次。如果選擇多于1次,那么匹配的字符串模式就變成了"((_*))" * N,更標(biāo)準(zhǔn)一點(diǎn)的表示方式是( "(" * n + ")" * n ) * N,當(dāng)然,前面也說了,這還有無數(shù)種其他的匹配可能。

所以,在這里我不在分組的后面加*或+這樣的量詞。要繼續(xù)剛才的討論。

使用\g1>?這種量詞方式可以嗎?當(dāng)然可以,上面分析\g1>*的時(shí)候,是說當(dāng)每一輪遞歸時(shí)的*次數(shù)選擇都是1次或0次,就能匹配無限嵌套的小括號。對于\g1>?來說當(dāng)然也可以,因?yàn)?#63;也可以表示0或1次。

/(\(\g1>?\))/ =~ "(" * 1 + ")" * 1
#=> 0
/(\(\g1>?\))/ =~ "(" * 3 + ")" * 3
#=> 0
/(\(\g1>?\))/ =~ "(" * 10 + ")" * 10
#=> 0

這兩種遞歸正則表達(dá)式,都是符合要求的,都能匹配無限嵌套的小括號。

下面是命名捕獲版本的:

/(?var>\(\gvar>?\))/ =~ "(" * 3 + ")" * 3
#=> 0

也能直接使用\g0>作為嵌套表達(dá)式,這時(shí)甚至可以去掉分組:

/(?var>\(\g0>?\))/ =~ "(" * 3 + ")" * 3
#=> 0

# 去掉分組,直接遞歸這種本身
/\(\g0>?\)/ =~ "(" * 3 + ")" * 3
#=> 0

這樣看上去,寫遞歸正則好像也不難。其實(shí)嵌套模式簡單的遞歸正則確實(shí)不難,只要理解遞歸的含義基本上就能寫出來。再看另一個(gè)示例。

深入遞歸(3):寫遞歸正則(進(jìn)階)

假設(shè)要匹配的字符串模式為:(abc(d(xy)e)fgh),其中每個(gè)括號內(nèi)的字符長度任意。這似乎正是本文開頭所舉的例子。

這一個(gè)遞歸寫起來其實(shí)非常非常簡單:

# 為了可讀性,使用了x修飾符忽略表達(dá)式內(nèi)的空白符號
/\( [^()]* \g0>* [^()]* \)/x

# 匹配:
reg = /\( [^()]* \g0>* [^()]* \)/x
reg =~ "(abc(d(xy)e)fgh)" #=> 0
reg =~ "(abc(d(xy)))"  #=> 0
reg =~ "((()e)fgh)"  #=> 0
reg =~ "((()))"   #=> 0

其中\(zhòng)([^()]*和[^()]*\)是頭和尾,中間使用\g0>來無限嵌套頭和尾。邏輯其實(shí)很簡單。

相比于網(wǎng)上流傳的版本/\( ( (?>[^()]+) | (\g0>) )* \)/x,此處所給出的寫法應(yīng)該容易理解的多。

再回頭擴(kuò)充剛才的遞歸匹配需求,如果需要匹配的字符串是ab(abc(d(xy)e)fgh)df這種模式呢?另一個(gè)問題,這種字符串模式和(abc(d(xy)e)fgh)有什么區(qū)別呢?

仔細(xì)比對一下,(abc(d(xy)e)fgh)按左右括號劃分配對的話,它左右剛好能夠成對數(shù):(abc (d (xy ) e) fgh)(這里用一個(gè)空格分隔,從內(nèi)向外互相成對)。但ab(abc(d(xy)e)fgh)df按左右括號劃分配對的話,得到的是ab( abc( d( xy )e )fgh )df,顯然,它中間多了一層無法成對的內(nèi)容xy。

為了寫出按照這種成對劃分的遞歸表達(dá)式,先不考慮多出來無法成對的xy這一層。那么對應(yīng)的遞歸正則表達(dá)式為:

/[^()]* \( \g0>* \) [^()]*/x

其中[^()]*\(是頭部,\)[^()]*是尾部,中間用\g0>*實(shí)現(xiàn)頭尾成對的無限嵌套。

再來考慮中間多出來的無法成對的xy這部分。其實(shí)直接將這部分放在\g0>*的左邊或右邊都無所謂。例如:

# 放\g0>*的左邊
/[^()]* \( [^()]* \g0>* \) [^()]*/x

# 放\g0>*的右邊
/[^()]* \( \g0>* [^()]* \) [^()]*/x

沒錯(cuò),寫遞歸的正則表達(dá)式就是這么簡單粗暴。

只是,現(xiàn)實(shí)并不這么美好,上面將多余的無法配對的部分放在了遞歸表達(dá)式的左邊或右邊,但有時(shí)候這樣是不行的。

解決多余無法成對內(nèi)容的更通用方法是使用二選一的分支結(jié)構(gòu),即|結(jié)合遞歸表達(dá)式一起使用,參見下一小節(jié)。

深入遞歸(4):遞歸結(jié)合二選一分支

要處理上面多出的無法成對的數(shù)據(jù),可以通過二選一結(jié)構(gòu)|改寫成如下更通用的方式:

/[^()]* \( \g0>* \) [^()]* |./x

進(jìn)行匹配測試:

reg = /[^()]* \( \g0>* \) [^()]* |./xreg =~ "ab(abc(d(xy)e)fgh)df"#=> 0

當(dāng)遞歸正則表達(dá)式結(jié)合了|提供的二選一分支功能時(shí),|左邊或右邊(和\g>相反的那一邊)都可以用來提供這些"孤兒"數(shù)據(jù)。

例如,上面示例中,當(dāng)遞歸進(jìn)行到發(fā)現(xiàn)xy這部分是多余的時(shí)候?qū)o法繼續(xù)匹配,這時(shí)候?qū)⒖梢詮亩x一的另一個(gè)分支來匹配這個(gè)多余的數(shù)據(jù)。

但是這個(gè)二選一分支帶來了一個(gè)新的問題:只要有無法匹配的,都可以去另一個(gè)分支匹配。假如右邊的分支是個(gè).,這就相當(dāng)于多了一個(gè)萬能箱,什么都可以從這里匹配。

但如果無法匹配的多余字符是右括號或左括號這個(gè)必須的字符呢?少了任何一個(gè)括號,都不再算是成對的嵌套結(jié)構(gòu),但卻因?yàn)槎x一分支而匹配成功。

如何解決這個(gè)問題?第一,需要保證另一分支不是萬能的.;第二,需將整個(gè)結(jié)構(gòu)做位置錨定。例如:

/\A ( [^()]* \( \g1>* \) [^()]* | [^()] ) \Z/x

注意,上面加了括號分組,所以\g0>隨之改變成\g1>,因?yàn)檫f歸的時(shí)候并不需要將錨定也包含進(jìn)來。

當(dāng)然,上面示例中二選一分支的另一個(gè)分支所使用的是單字符匹配[^()],如果有多個(gè)連續(xù)的多余字符,這會導(dǎo)致多次選中該分支。為了減少匹配的測試次數(shù),可以將其直接寫成[^()]*。

/\A ( [^()]* \( \g1>* \) [^()]* | [^()]* ) \Z/x

但這有可能會在匹配失敗的時(shí)候?qū)е麓罅康幕厮荩瑥亩阅鼙┙?。例如,如下失敗的匹配?/p>

reg = /\A([^()]* \( \g1>* \) [^()]* | [^()]* )\Z/x

# 匹配失敗性能暴降
(st=Time.now) ; (reg =~ "ab(abc(d(xy)e)fghdf") ; (Time.now - st)
#=> 1.7730072
(st=Time.now) ; (reg =~ "ab(abc(d(xy)e)fghdffds") ; (Time.now - st)
#=> 47.5858051

# 匹配成功則無影響
(st=Time.now) ; (reg =~ "ab(abc(d(xy)e)fgh)df") ; (Time.now - st)
#=> 5.9e-06

從結(jié)果發(fā)現(xiàn),就這么短的字符串,第一個(gè)匹配失敗竟需要花費(fèi)1.8秒,第二個(gè)字符串更夸張,僅僅只是多了3個(gè)字符,耗費(fèi)的時(shí)間飆升到47秒。

解決方法有很多種,這里提供兩種:一種是將*號直接移到分組外,這雖然并不等價(jià),但并不影響最終的匹配結(jié)果;另一種是將該多選分支使用固化分組或占有優(yōu)先的模式。

reg1 = /\A([^()]* \( \g1>* \) [^()]* | [^()] )*\Z/x
reg2 = /\A([^()]* \( \g1>* \) [^()]* | (?>[^()]*) )\Z/x

# 匹配成功
(st=Time.now) ; (reg1 =~ "ab(abc(d(xy)e)fgh)df") ; (Time.now - st)
#=> 6.1e-06
(st=Time.now) ; (reg2 =~ "ab(abc(d(xy)e)fgh)df") ; (Time.now - st)
#=> 5.8e-06

# 匹配失敗
(st=Time.now) ; (reg1 =~ "ab(abc(d(xy)e)fghdf") ; (Time.now - st)
#=> 8.46e-05
(st=Time.now) ; (reg2 =~ "ab(abc(d(xy)e)fghdf") ; (Time.now - st)
#=> 0.0004223

深入遞歸(5):小心遞歸中的分組捕獲

在介紹示例之前,先驗(yàn)證一下結(jié)論。

在遞歸過程中,可能也會有分組捕獲的表達(dá)式,所以,遞歸正則設(shè)置的相關(guān)變量值是最后一次分組捕獲對應(yīng)的狀態(tài)。例如:

reg = /(abc|def) and \g0>?xyz/

# 只遞歸一輪
reg =~ "abc and def and xyzxyz" #=> 0

# $~表示本次所匹配到的所有字符串
$~
#=> #MatchData "abc and def and xyzxyz" 1:"def">

# $1表示第一個(gè)分組捕獲所對應(yīng)的內(nèi)容
$1  #=> "def"

上面結(jié)果可以看出,在遞歸過程中,最后一輪的遞歸操作(此處示例即第一輪遞歸)設(shè)置了一些正則匹配時(shí)的變量,它會覆蓋在它之前的遞歸設(shè)置的結(jié)果。

再來看一個(gè)示例?,F(xiàn)在有個(gè)需求:匹配任何長度的回文字符串(palindrome),比如1234321、abcba、好不好、abccba、好、好好、123321,該示例只能使用二選一的分支來實(shí)現(xiàn)。

這里簡單分析一下,如何通過遞歸正則來實(shí)現(xiàn)該需求。

假設(shè)要匹配的這個(gè)字符串是abcdcba,先把多余的字符d去掉,那么要匹配的是abccba,這也是我們想要匹配的一種字符串模式。首先,左右配對的部分必須是完全一致的數(shù)據(jù),這個(gè)遞歸正則其實(shí)很容易實(shí)現(xiàn),用占位符來描述,大概模式為:(.)_*\1。將其替換成遞歸正則表達(dá)式:

/(.) \g0>* \1/x

再來考慮多余的那個(gè)字符,直接將其放在二選一分支的另一分支即可:因?yàn)槎x一分支,所以這里的\g0>就可以不用量詞修飾來保證遞歸的終點(diǎn)

/(.) \g0> \1 |./x

最后,加上位置錨定。

/\A ( (.) \g1> \2|.) \Z/x

似乎已經(jīng)沒問題了,去測試匹配下:

/\A ( (.) \g1> \2|.) \Z/x =~ "abcba"
#=> nil

結(jié)果卻并不如想象中那樣成功。

不過,這個(gè)正則表達(dá)式的邏輯確實(shí)是沒有問題的。例如,使用grep -P(使用PCRE)執(zhí)行等價(jià)的正則去匹配回文字符串。

$ grep -P "^((.)(?1)\2|.)$" "abcdcba"
abcdcba

# 下面的則失敗
$ grep -P "^((.)(?1)\2|.)$" "abcdcbad"

但是這個(gè)"正確的"正則表達(dá)式在Ruby中卻無法達(dá)到目標(biāo)。這是因?yàn)镽uby中的遞歸也會設(shè)置分組捕獲,每個(gè)\2所反向引用的就不再是每輪遞歸中同層次的分組捕獲(.)的內(nèi)容了,而是真正的從左向右的第二個(gè)分組捕獲括號所捕獲的內(nèi)容。

好在,Ruby提供了更加靈活的分組捕獲的引用控制。除了\N這種方式的反向引用,也可以通過\kN>或\kname>來引用,靈活之處在于\k>支持遞歸層次的偏移,例如\kname+0>表示取當(dāng)前遞歸層次里的name分組捕獲,\kname+1>和\kname-1>分別表示取當(dāng)前遞歸層的下一層和上一層里的name分組捕獲。

所以,在Ruby中改一下這個(gè)正則表達(dá)式就能正常工作:

/\A ( (.) \g1> \k2+0>|.) \Z/x =~ "abcba"
#=> 0
/\A ( (.) \g1> \k2+0>|.) \Z/x =~ "abcbaa"
#=> nil

當(dāng)然,用命名捕獲也是可以的:

/\A (?i> (?j>.) \gi> \kj+0>|.) \Z/x

最后,可以將上面的正則表達(dá)式改動(dòng)一番。上面正則中,多選分支的.一直都是放在尾部的(放頭部也沒問題),但下面這種將多選分支和遞歸表達(dá)式嵌在一個(gè)分組內(nèi)也是很常見的用法。下面這兩種遞歸正則表達(dá)式是等價(jià)的。

/\A (?i> (?j>.) \gi>    \kj+0>|.) \Z/x
/\A (?i> (?j>.) (?:\gi>|.) \kj+0> ) \Z/x

(?:\gi>|.)進(jìn)行了分捕獲的分組,分組將它們兩綁定在一個(gè)組內(nèi),如果不分組將會出錯(cuò),因?yàn)閨的優(yōu)先級太低。

不要濫用遞歸正則

雖然遞歸正則確實(shí)能解決一些特殊需求,但是能不用盡量不用,因?yàn)檫f歸正則要配合量詞來修飾遞歸表達(dá)式,這本身不是問題,但是遞歸表達(dá)式很多時(shí)候在分組內(nèi),而分組本身可能也會用量詞去修飾,這樣兩個(gè)量詞一結(jié)合,一不小心可能就出現(xiàn)大量的回溯,導(dǎo)致匹配效率瘋狂下降。

前文已經(jīng)演示過一個(gè)這樣的現(xiàn)象,僅僅只是多了3個(gè)字符,匹配失敗竟然需要多花費(fèi)40多秒,而且隨著字符的增多,匹配失敗所需時(shí)間飆升的更快。這絕對是我們要去避免的。

所以,當(dāng)寫出來的遞歸正則表達(dá)式里又是分組、又是量詞,看上去還"亂七八糟"的結(jié)合在一起,很可能會出現(xiàn)性能不佳的問題。這時(shí)候可能需要去調(diào)試優(yōu)化,以便寫出高性能的遞歸正則,但這可能會耗去大量的時(shí)間。

所以,盡量想其它方法來解決遞歸正則想要實(shí)現(xiàn)的匹配需求,或者只寫看上去就很簡單的遞歸正則。

總結(jié)

以上所述是小編給大家介紹的循序漸進(jìn)掌握遞歸正則表達(dá)式,希望對大家有所幫助,如果大家有任何疑問請給我留言,小編會及時(shí)回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持!
如果你覺得本文對你有幫助,歡迎轉(zhuǎn)載,煩請注明出處,謝謝!

您可能感興趣的文章:
  • JavaScript正則表達(dá)式校驗(yàn)與遞歸函數(shù)實(shí)際應(yīng)用實(shí)例解析
  • C#正則表達(dá)式的遞歸匹配分析
  • PHP中的遞歸正則表達(dá)式用法分享

標(biāo)簽:涼山 常州 大興安嶺 本溪 湖州 哈密 泰安 ???/a>

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《循序漸進(jìn)掌握遞歸正則表達(dá)式【推薦】》,本文關(guān)鍵詞  循序漸進(jìn),掌握,遞歸,正則,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《循序漸進(jìn)掌握遞歸正則表達(dá)式【推薦】》相關(guān)的同類信息!
  • 本頁收集關(guān)于循序漸進(jìn)掌握遞歸正則表達(dá)式【推薦】的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章