正則表達式匹配原理之逆序環視的示例分析

這篇文章主要為大家展示了“正則表達式匹配原理之逆序環視的示例分析”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“正則表達式匹配原理之逆序環視的示例分析”這篇文章吧。

說明：部分內容有待進一步研究和修正，因為最近工作太忙，暫時抽不出時間來，未研究過的可以跳過這一篇，想研究的不要被我的思路所左右了，有研究清楚的還請指正1 問題引出

前幾天在CSDN論壇遇到這樣一個問題：
var str="8912341253789";
需要將這個字符串中的重復的數字給去掉，也就是結果89123457。
首先需要說明的是，這種需求并不適合用正則來實現，至少，正則不是最好的實現方式。
這個問題本身不是本文討論的重點，本文所要討論的，主要是由這一問題的解決方案而引出的另一個正則匹配原理問題。
先看一下針對這一問題本身給出的解決方案。

代碼如下:

string str = "8912341253789";
Regex reg = new Regex(@"((\d)\d*?)\2");
while (str != (str = reg.Replace(str, "$1"))) { }
richTextBox2.Text = str;
/*--------輸出--------
89123457
*/

基于此有朋友提出另一個疑問，為什么使用下面的正則沒有效果
“(?<=(?<value>\d).*?)\k<value>”
由此也引出本文所要討論的逆序環視更深入的一些細節，涉及到逆序環視的匹配原理和匹配過程。前面的兩篇博客中雖然也有介紹，但還不夠深入，參考 正則基礎之——環視 和 正則應用之——逆序環視探索 。本文將以逆序環視和反向引用結合這種復雜應用場景，對逆序環視進行深入探討。
先把問題簡化和抽象一下，上面的正則中用到了命名捕獲組和命名捕捉組的反向引用，這在一定程度上增加了問題的復雜度，寫成普通捕獲組，并且用“\d”代替范圍過大的“.”，如下
“(?<=(\d)\d*?)\1”
需要匹配的字符串，抽象一下，取兩種典型字符串如下。
源字符串一：878
源字符串二：9878
與上面正則表達式類似，正則表達式相應的也有四種形式
正則表達式一：(?<=(\d)\d*)\1
正則表達式二：(?<=(\d)\d*?)\1
正則表達式三：(?<=(\d))\d*\1
正則表達式四：(?<=(\d))\d*?\1
先看一下匹配結果：

string[] source = new string[] {"878", "9878" };
List<Regex> regs = new List<Regex>();
regs.Add(new Regex(@"(?<=(\d)\d*)\1"));
regs.Add(new Regex(@"(?<=(\d)\d*?)\1"));
regs.Add(new Regex(@"(?<=(\d))\d*\1"));
regs.Add(new Regex(@"(?<=(\d))\d*?\1"));
foreach (string s in source)
{
foreach (Regex r in regs)
{
richTextBox2.Text += "源字符串： " + s.PadRight(8, ' ');
richTextBox2.Text += "正則表達式： " + r.ToString().PadRight(18, ' ');
richTextBox2.Text += "匹配結果： " + r.Match(s).Value + "\n------------------------\n";
}
richTextBox2.Text += "------------------------\n";
}

/*--------輸出--------
源字符串： 878 正則表達式： (?<=(\d)\d*)\1 匹配結果： 8
------------------------
源字符串： 878 正則表達式： (?<=(\d)\d*?)\1 匹配結果：
------------------------
源字符串： 878 正則表達式： (?<=(\d))\d*\1 匹配結果： 78
------------------------
源字符串： 878 正則表達式： (?<=(\d))\d*?\1 匹配結果： 78
------------------------
------------------------
源字符串： 9878 正則表達式： (?<=(\d)\d*)\1 匹配結果：
------------------------
源字符串： 9878 正則表達式： (?<=(\d)\d*?)\1 匹配結果：
------------------------
源字符串： 9878 正則表達式： (?<=(\d))\d*\1 匹配結果： 78
------------------------
源字符串： 9878 正則表達式： (?<=(\d))\d*?\1 匹配結果： 78
------------------------
------------------------
*/
這個結果也許會出乎很多人的意料之外，剛開始接觸這個問題時，我也一樣感到迷惑，放了兩天后，才靈機一觸，想通了問題的關鍵所在，下面將展開討論。
在此之前，可能還需要做兩點說明：
1、 下面討論的話題已經與本文開始提到的問題沒有多大關聯了，最初的問題主要是為了引出本文的話題，問題本身不在討論范圍之內，而本文也主要是純理論的探討。
2、 本文適合有一定正則基礎的讀者。如果您對上面幾個正則的匹配結果和匹配過程感到費解，沒關系，下面就將為您解惑；但是如果您對上面幾個正則中元字符和語法代表的意義都不清楚的話，還是先從基礎看起吧。
2 逆序環視匹配原理深入

正則表達式一：(?<=(\d)\d*)\1
正則表達式二：(?<=(\d)\d*?)\1
正則表達式三：(?<=(\d))\d*\1
正則表達式四：(?<=(\d))\d*?\1

上面的幾個正則表達式，可以最終抽象為“(?<=SubExp1)SubExp2”這樣的表達式，在做逆序環視原理分析時，根據“SubExp1”的特點，可以歸納為三類：

1、 逆序環視中的子表達式“SubExp1”長度固定，正則表達式三和四屬于這一類，當然，這一類里是包括“?”這一量詞的，但也僅限于這一個量詞。
2、 逆序環視中的子表達式“SubExp1”長度不固定，其中包含忽略優先量詞，如“*?”、“+?”、“{m,}?”等，也就是通常所說的非貪婪模式，正則表達式二屬于這一類。
3、 逆序環視中的子表達式“SubExp1”長度不固定，其中包含匹配優先量詞，“*”、“+”、“{m,}”等，也就是通常所說的貪婪模式，正則表達式一屬于這一類。

下面針對這三類正則表達式進行匹配過程的分析。

2.1 固定長度子表達式匹配過程分析
2.1.1 源字符串一 + 正則表達式三匹配過程

源字符串一：878
正則表達式三：(?<=(\d))\d*\1
首先在位置0處開始嘗試匹配，由“(?<=(\d))”取得控制權，長度固定，只有一位，由位置0處向左查找一位，失敗，“(?<=(\d))”匹配失敗，導致第一輪匹配嘗試失敗。
正則引擎傳動裝置向前傳動，由位置1處嘗試匹配，控制權交給“(?<=(\d))”，向左查找一位，接著將控制權交給“(\d)”，更進一步的將控制權交給“\d”。“\d”取得控制權后，向右嘗試匹配，匹配“8”成功，此時“(?<=(\d))”匹配成功，匹配結果為位置1，捕獲組1匹配到的內容就是“8”，控制權交給“\d*”。由于“\d*”為貪婪模式，會優先嘗試匹配位置1后面的“7”和“8”，匹配成功，記錄回溯狀態，控制權交給“\1”。由于前面捕獲組1捕獲到的內容是“8”，所以“\1”要匹配到“8”才能匹配成功，而此時已到達字符串結尾處，匹配失敗，“\d*”回溯，讓出最后的字符“8”，再將控制權交給“\1”， 由“\1”匹配最后的“8”成功，此時整個表達式匹配成功。由于“(?<=(\d))”只匹配位置，不占有字符，所以整個表達式匹配到的結果為“78”，其中“\d*”匹配到的是“7”，“\1”匹配到的是“8”。
2.1.2 源字符串二 + 正則表達式三匹配過程

源字符串二：9878
正則表達式三：(?<=(\d))\d*\1
這一組合的匹配過程，與2.1.1節的匹配過程基本類似，只不過多了一輪匹配嘗試而已，這里不再贅述。
2.1.3 源字符串一 + 正則表達式四匹配過程
源字符串一：878
正則表達式四：(?<=(\d))\d*?\1
首先在位置0處開始嘗試匹配，由“(?<=(\d))”取得控制權，長度固定，只有一位，由位置0處向左查找一位，失敗，“(?<=(\d))”匹配失敗，導致第一輪匹配嘗試失敗。
正則引擎傳動裝置向前傳動，由位置1處嘗試匹配，控制權交給“(?<=(\d))”，向左查找一位，接著將控制權交給“(\d)”，更進一步的將控制權交給“\d”。“\d”取得控制權后，向右嘗試匹配，匹配“8”成功，此時“(?<=(\d))”匹配成功，匹配結是果為位置1，捕獲組1匹配到的內容就是“8”，控制權交給“\d*?”。由于“\d*?”為非貪婪模式，會優先嘗試忽略匹配，記錄回溯狀態，控制權交給“\1”。由于前面捕獲組1捕獲到的內容是“8”，所以“\1”要匹配到“8”才能匹配成功，而此時位置1后面的字符是“7”，匹配失敗，“\d*?”回溯，嘗試匹配位置1后面的字符“7”，再將控制權交給“\1”， 由“\1”匹配最后的“8”成功，此時整個表達式匹配成功。由于“(?<=(\d))”只匹配位置，不占有字符，所以整個表達式匹配到的結果為“78”，其中“\d*?”匹配到的是“7”，“\1”匹配到的是最后的“8”。
這與2.1.1節組合的匹配過程基本一致，只不過就是“\d*”和“\d*?”匹配與回溯過程有所區別而已。
2.1.4 源字符串二 + 正則表達式四匹配過程
源字符串二：9878
正則表達式四：(?<=(\d))\d*?\1
這一組合的匹配過程，與2.1.3節的匹配過程基本類似，這里不再贅述。
2.2 非貪婪模式子表達式匹配過程分析
2.2.1 源字符串一 + 正則表達式二匹配過程
源字符串一：878
正則表達式二：(?<=(\d)\d*?)\1
首先在位置0處開始嘗試匹配，由“(?<=(\d)\d*?)”取得控制權，長度不固定，至少一位，由位置0處向左查找一位，失敗，“(?<=(\d)\d*?)”匹配失敗，導致第一輪匹配嘗試失敗。
正則引擎傳動裝置向前傳動，由位置1處嘗試匹配，控制權交給“(?<=(\d)\d*?)”，向左查找一位，接著將控制權交給“(\d)”，更進一步的將控制權交給“\d”。“\d”取得控制權后，向右嘗試匹配，匹配“8”成功，將控制權交給“\d*?”，由于“\d*?”為非貪婪模式，會優先嘗試忽略匹配，即不匹配任何內容，并記錄回溯狀態，此時“(\d)\d*?”匹配成功，那么“(?<=(\d)\d*?)”也就匹配成功，匹配結果為位置1，由于此處的子表達式“(\d)\d*?”為非貪婪模式，取得一個成功匹配項后，即交出控制權，同時丟棄所有回溯狀態。由于前面捕獲組1捕獲到的內容是“8”，所以“\1”要匹配到“8”才能匹配成功，而此時位置1后面的字符是“7”，此時已無可供回溯的狀態，整個表達式在位置1處匹配失敗。
正則引擎傳動裝置向前傳動，由位置2處嘗試匹配，控制權交給“(?<=(\d)\d*?)”，向左查找一位，接著將控制權交給“(\d)”，更進一步的將控制權交給“\d”。“\d”取得控制權后，向右嘗試匹配，匹配“7”成功，將控制權交給“\d*?”，由于“\d*?”為非貪婪模式，會優先嘗試忽略匹配，即不匹配任何內容，并記錄回溯狀態，此時“(\d)\d*?”匹配成功，那么“(?<=(\d)\d*?)”也就匹配成功，匹配結果為位置2，由于此處的子表達式“(\d)\d*?”為非貪婪模式，取得一個成功匹配項后，即交出控制權，同時丟棄所有回溯狀態。由于前面捕獲組1捕獲到的內容是“7”，所以“\1”要匹配到“7”才能匹配成功，而此時位置2后面的字符是“7”，此時已無可供回溯的狀態，整個表達式在位置2處匹配失敗。
位置3處的匹配過程也同樣道理，最后“\1”因無字符可匹配，導致整個表達式匹配失敗。
此時已嘗試了字符串所有位置，均匹配失敗，所以整個表達式匹配失敗，未取得任何有效匹配結果。
2.2.2 源字符串二 + 正則表達式二匹配過程
源字符串一：9878
正則表達式二：(?<=(\d)\d*?)\1
這一組合的匹配過程，與2.2.1節的匹配過程基本類似，這里不再贅述。
2.3 貪婪模式子表達式匹配過程分析
2.3.1 源字符串一 + 正則表達式一匹配過程
源字符串一：878
正則表達式二：(?<=(\d)\d*)\1
首先在位置0處開始嘗試匹配，由“(?<=(\d)\d*)”取得控制權，長度不固定，至少一位，由位置0處向左查找一位，失敗，“(?<=(\d)\d*)”匹配失敗，導致第一輪匹配嘗試失敗。
正則引擎傳動裝置向前傳動，由位置1處嘗試匹配，控制權交給“(?<=(\d)\d*)”，向左查找一位，接著將控制權交給“(\d)”，更進一步的將控制權交給“\d”。“\d”取得控制權后，向右嘗試匹配，匹配“8”成功，將控制權交給“\d*”，由于“\d*”為貪婪模式，會優先嘗試匹配，并記錄回溯狀態，但此時已沒有可用于匹配的字符，所以匹配失敗，回溯，不匹配任何內容，丟棄回溯狀態，此時“(\d)\d*”匹配成功，匹配內容為“8”，那么“(?<=(\d)\d*)”也就匹配成功，匹配結果是位置1，由于此處的子表達式為貪婪模式，“(\d)\d*”取得一個成功匹配項后，需要查找是否還有更長匹配，找到最長匹配后，才會交出控制權。再向左查找，已沒有字符，“8”已是最長匹配，此時交出控制權，同時丟棄所有回溯狀態。由于前面捕獲組1捕獲到的內容是“8”，所以“\1”要匹配到“8”才能匹配成功，而此時位置1后面的字符是“7”，此時已無可供回溯的狀態，整個表達式在位置1處匹配失敗。
正則引擎傳動裝置向前傳動，由位置2處嘗試匹配，控制權交給“(?<=(\d)\d*)”，向左查找一位，接著將控制權交給“(\d)”，更進一步的將控制權交給“\d”。“\d”取得控制權后，向右嘗試匹配，匹配“7”成功，將控制權交給“\d*”，由于“\d*”為貪婪模式，會優先嘗試匹配，并記錄回溯狀態，但此時已沒有可用于匹配的字符，所以匹配失敗，回溯，不匹配任何內容，丟棄回溯狀態，此時“(\d)\d*”匹配成功，匹配內容為“7”，那么“(?<=(\d)\d*)”也就匹配成功，匹配結果是位置2，由于此處的子表達式為貪婪模式，“(\d)\d*”取得一個成功匹配項后，需要查找是否還有更長匹配，找到最長匹配后，才會交出控制權。再向左查找，由位置0處向右嘗試匹配，“\d”取得控制權后，匹配位置0處的“8”成功，將控制權交給“\d*”，由于“\d*”為貪婪模式，會優先嘗試匹配，并記錄回溯狀態，匹配位置1處的“7”成功，此時“(\d)\d*”匹配成功，那么“(\d)\d*”又找到了一個成功匹配項，匹配內容為“87”，其中捕獲組1匹配到的是“8”。再向左查找，已沒有字符，“87”已是最長匹配，此時交出控制權，同時丟棄所有回溯狀態。由于前面捕獲組1捕獲到的內容是“8”，所以“\1”匹配位置2處的“8”匹配成功，此時整個有達式匹配成功。
演示例程中用的是Match，只取一次匹配項，事實上如果用的是Matches，正則表達式是需要嘗試所有位置的，對于這一組合，同樣道理，在位置3處，由于“\1”沒有字符可供匹配，所以匹配一定是失敗的。
至此，這一組合的匹配完成，有一個成功匹配項，匹配結果為“8”，匹配開始位置為位置2，也就是匹配到的內容為第二個“8”。
2.3.2 源字符串二 + 正則表達式一匹配過程
源字符串二：9878
正則表達式二：(?<=(\d)\d*)\1
首先在位置0處開始嘗試匹配，由“(?<=(\d)\d*)”取得控制權，長度不固定，至少一位，由位置0處向左查找一位，失敗，“(?<=(\d)\d*)”匹配失敗，導致第一輪匹配嘗試失敗。
正則引擎傳動裝置向前傳動，由位置1處嘗試匹配，這一輪的匹配過程與2.3.1節的組合在位置1處的匹配過程類似，只不過“(\d)\d*”匹配到的是“9”，捕獲組1匹配到的也是“9”，因此“\1”匹配失敗，導致整個表達式在位置1處匹配失敗。
正則引擎傳動裝置向前傳動，由位置2處嘗試匹配，這一輪的匹配過程與2.3.1節的組合在位置2處的匹配過程類似。首先“(\d)\d*”找到一個成功匹配項，匹配到的內容是“8”，捕捉組1匹配到的內容也是“8”，此時再向左嘗試匹配，又找到一個成功匹配項，匹配到的內容是“98”，捕捉組1匹配到的內容也是“9”，再向左查找時，已無字符，所以“98”就是最長匹配項，“(?<=(\d)\d*)”匹配成功，匹配結果是位置2。由于此時捕獲組1匹配的內容是“9”，所以“\1”在位置2處匹配失敗，導致整個表達式在位置2處匹配失敗。
正則引擎傳動裝置向前傳動，由位置3處嘗試匹配，這一輪的匹配過程與上一輪在位置2處的匹配過程類似。首先“(\d)\d*”找到一個成功匹配項“7”，繼續向左嘗試，又找到一個成功匹配項“87”，再向左嘗試，又找到一個成功匹配項“987”，此時已為最長匹配，交出控制權，并丟棄所有回溯狀態。此時捕獲組1匹配的內容是“9” 所以“\1”在位置3處匹配失敗，導致整個表達式在位置3處匹配失敗。
位置4處最終由于“\1”沒有字符可供匹配，所以匹配一定是失敗的。
至此在源字符串所有位置的匹配嘗試都已完成，整個表達式匹配失敗，未找到成功匹配項。

2.4 小結

以上匹配過程分析，看似繁復，其實把握以下幾點就可以了。
1、 逆序環視中子表達式為固定長度時，要么匹配成功，要么匹配失敗，沒什么好說的。
2、 逆序環視中子表達式為非貪婪模式時，只要找到一個匹配成功項，即交出控制權，并丟棄所有可供回溯的狀態。
3、 逆序環視中子表達式為貪婪模式時，只有找到最長匹配成功項時，才會即交出控制權，并丟棄所有可供回溯的狀態。
也就是說，對于正則表達式“(?<=SubExp1)SubExp2”，一旦“(?<=SubExp1)”交出控制權，那么它所匹配的位置就已固定，“SubExp1”所匹配的內容也已固定，并且沒有可供回溯的狀態了。
3 逆序環視匹配原理總結
再來總結一下正則表達式“(?<=SubExp1)SubExp2”的匹配過程吧。逆序環視的匹配原理圖如下圖所示。

圖3-1 逆序環視匹配原理圖

正則表達式“(?<=SubExp1)SubExp2”的匹配過程，可分為主匹配流程和子匹配流程兩個流程，主匹配流程如下圖所示。

圖3-2 主匹配流程圖

主匹配流程：

1、 由位置0處向右嘗試匹配，在找到滿足“(?<=SubExp1)”最小長度要求的位置前，匹配一定是失敗的，直到找到這樣一個的位置x，x滿足“(?<=SubExp1)”最小長度要求；
2、 從位置x處向左查找滿足“SubExp1”最小長度要求的位置y；
3、 由“SubExp1”從位置y開始向右嘗試匹配，此時進入一個獨立的子匹配過程；
4、 如果“SubExp1”在位置y處子匹配還需要下一輪子匹配，則再向左查找一個y'，也就是y-1重新進入獨立的子匹配過程，如此循環，直到不再需要下一輪子匹配，子匹配成功則進入步驟5，最終匹配失敗則報告整個表達式匹配失敗；
5、 “(?<=SubExp1)”成功匹配后，控制權交給后面的子表達式“SubExp2”，繼續嘗試匹配，直到整個表達式匹配成功或失敗，報告在位置x處整個表達式匹配成功或失敗；
6、 如有必要，繼續查找下一位置x'，并開始新一輪嘗試匹配。
子匹配流程如下圖所示。

圖3-3 子匹配流程圖

子匹配過程：

1、 進入子匹配后，源字符串即已確定，也就是位置y和位置x之間的子字符串，而此時的正則表達式則變成了“^SubExp1$”，因為在這一輪子匹配當中，一旦匹配成功，則匹配開始位置一定是y，匹配結束位置一定是x；
2、 子表達式長度固定時，要么匹配成功，要么匹配失敗，返回匹配結果，并且不需要下一輪子匹配；
3、 子表達式長度不固定時，區分是非貪婪模式還是貪婪模式；
4、 如果是非貪婪模式，匹配失敗，報告失敗，并且要求進行下一輪子匹配；匹配成功，丟棄所有回溯狀態，報告成功，并且不再需要嘗試下一輪子匹配；
5、 如果是貪婪模式，匹配失敗，報告失敗，并且要求進行下一輪子匹配；匹配成功，丟棄所有回溯狀態，報告成功，記錄本次匹配成功內容，并且要求嘗試下一輪子匹配，直到取得最長匹配為止；
在特定的一輪匹配中，x的位置是固定的，而逆序環視中的子表達式“SubExp1”，在報告最終的匹配結果前，匹配開始的位置是不可預知的，需要經過一輪以上的子匹配才能確定，但匹配結束的位置一定是位置x。
當然，這只是針對特定的一輪匹配而言的，當這輪匹配失敗，正則引擎傳動裝置會向前傳動，使x=x+1，再進入下一輪匹配嘗試，直到整個表達式報告匹配成功或失敗為止。
至此逆序環視的匹配原理已基本上分析完了，當然，還有更復雜的，如“SubExp1”中既包含貪婪模式子表達式，又包含非貪婪模式子表達式，但無論怎樣復雜，都是要遵循以上匹配原理的，所以只要理解了以上匹配原理，逆序環視也就沒什么秘密可言了。

以上是“正則表達式匹配原理之逆序環視的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！