深入正則表達式(3):正則表達式工作引擎流程分析與原理釋義

作為正則的使用者也一樣，不懂正則引擎原理的情況下，同樣可以寫出滿足需求的正則，但是不知道原理，卻很難寫出高效且沒有隱患的正則。所以對於經常使用正則，或是有興趣深入學習正則的人，還是有必要了解一下正則引擎的匹配原理的。

有興趣可以回顧《深入正則表達式(0):正則表達式概述》

正則引擎類型

正則引擎主要可以分為兩大類：一種是DFA(Deterministic Finite Automatons/確定性有限自動機—)，一種是NFA(Nondeterministic Finite Automatons/非確定性有限自動機)。總的來說，

• DFA可以稱為文本主導的正則引擎

• NFA可以稱為表達式主導的正則引擎

NFA與DFA工作的區別：

我們常常說用正則去匹配文本，這是NFA的思路，DFA本質上其實是用文本去匹配正則。

'for tonight's'.match(/to(nite|knite|night)/);

• 如果是NFA引擎，表達式佔主導地位。在字符串先查找字符串中的t，然後依次匹配，如果是o，則繼續(以此循環)。匹配到to后，到n，就面臨三種選擇，每一種都去嘗試匹配一下（它也不嫌累），第一個分支也是依次匹配，到t這裏停止(nite分到t這裏直接被淘汰)；同理，接着第二個分支在k這裏也停止了；終於在第三個分支柳暗花明，找到了自己的歸宿。 NFA 工作方式是以正則表達式為標準，反覆測試字符串，這樣同樣一個字符串有可能被反覆測試了很多次！

• 如果是DFA引擎呢，文本佔主導地位。從整個字符串第一個字符開始f開始查找t，查找到t后，定位到t，以知其後為o，則去查看正則表達式其相應位置后是否為o，如果是，則繼續（以此循環)，再去查正則表達式o后是否為n（此時淘汰knite分支），再后是否為g(淘汰nite分支)，這個時候只剩一個分支，直接匹配到終止即可。

只有正則表達式才有分支和範圍，文本僅僅是一個字符流。這帶來什麼樣的後果？就是NFA引擎在匹配失敗的時候，如果有其他的分支或者範圍，它會返回，記住，返回，去嘗試其他的分支。而DFA引擎一旦匹配失敗，就結束了，它沒有退路。

這就是它們之間的本質區別。其他的不同都是這個特性衍生出來的。

NFA VS DFA

首先，正則表達式在計算機看來只是一串符號，正則引擎首先肯定要解析它。NFA引擎只需要編譯就好了；而DFA引擎則比較繁瑣，編譯完還不算，還要遍歷出表達式中所有的可能。因為對DFA引擎來說機會只有一次，它必須得提前知道所有的可能，才能匹配出最優的結果。

所以，在編譯階段，NFA引擎比DFA引擎快。

 

其次，DFA引擎在匹配途中一遍過，溜得飛起。相反NFA引擎就比較苦逼了，它得不厭其煩的去嘗試每一種可能性，可能一段文本它得不停返回又匹配，重複好多次。當然運氣好的話也是可以一遍過的。

所以，在運行階段，NFA引擎比DFA引擎慢。

 

最後，因為NFA引擎是表達式佔主導地位，所以它的表達能力更強，開發者的控制度更高，也就是說開發者更容易寫出性能好又強大的正則來，當然也更容易造成性能的浪費甚至撐爆CPU。DFA引擎下的表達式，只要可能性是一樣的，任何一種寫法都是沒有差別(可能對編譯有細微的差別)的，因為對DFA引擎來說，表達式其實是死的。而NFA引擎下的表達式，高手寫的正則和新手寫的正則，性能可能相差10倍甚至更多。

也正是因為主導權的不同，正則中的很多概念，比如非貪婪模式、反向引用、零寬斷言等只有NFA引擎才有。

所以，在表達能力上，NFA引擎秒殺DFA引擎。

 

但是NFA以表達式為主導，因而NFA更容易操縱，因此一般程序員更偏愛NFA引擎！

當今市面上大多數正則引擎都是NFA引擎，應該就是勝在表達能力上。

 

總體來說，兩種引擎的工作方式完全不同，一個(NFA)以表達式為主導，一個(DFA)以文本為主導！兩種引擎各有所長，而真正的引用則取決與你的需要以及所使用的語言。

這兩種引擎都有了很久的歷史(至今二十多年)，當中也由這兩種引擎產生了很多變體！

因為NFA引擎比較靈活，很多語言在實現上有細微的差別。所以後來大家弄了一個標準，符合這個標準的正則引擎就叫做POSIX NFA引擎，其餘的就只能叫做傳統型NFA引擎咯。

Deterministic finite automaton,Non-deterministic finite automaton,Traditional NFA,Portable Operating System Interface for uniX NFA

於是POSIX的出台規避了不必要變體的繼續產生。這樣一來，主流的正則引擎又分為3類：DFA，傳統型NFA，POSIX NFA。

正則引擎三國

DFA引擎

DFA引擎在線性時狀態下執行，因為它們不要求回溯（並因此它們永遠不測試相同的字符兩次）。

DFA引擎還可以確保匹配最長的可能的字符串。但是，因為 DFA 引擎只包含有限的狀態，所以它不能匹配具有反向引用的模式；並且因為它不構造显示擴展，所以它不可以捕獲子表達式。

DFN不回溯，所以匹配快速，因而不支持捕獲組，支持反向引用和$number引用

傳統的 NFA引擎

傳統的 NFA 引擎運行所謂的“貪婪的”匹配回溯算法，以指定順序測試正則表達式的所有可能的擴展並接受第一個匹配項。因為傳統的 NFA 構造正則表達式的特定擴展以獲得成功的匹配，所以它可以捕獲子表達式匹配和匹配的反向引用。但是，因為傳統的 NFA 回溯，所以它可以訪問完全相同的狀態多次（如果通過不同的路徑到達該狀態）。因此，在最壞情況下，它的執行速度可能非常慢。因為傳統的 NFA 接受它找到的第一個匹配，所以它還可能會導致其他（可能更長）匹配未被發現。

大多數編程語言和工具使用的是傳統型的NFA引擎，它有一些DFA不支持的特性：

• 捕獲組、反向引用和$number引用方式；

• 環視(Lookaround，(?<=…)、(?<!…)、(?=…)、(?!…))，或者有的有文章叫做預搜索；

• 忽略優化量詞（??、*?、+?、{m,n}?、{m,}?），或者有的文章叫做非貪婪模式；

• 佔有優先量詞（?+、*+、++、{m,n}+、{m,}+，目前僅Java和PCRE支持），固化分組(?>…)。

POSIX NFA引擎

POSIX NFA引擎主要指符合POSIX標準的NFA引擎，與傳統的 NFA 引擎類似，不同的一點在於：提供longest-leftmost匹配，也就是在找到最左側最長匹配之前，它將繼續回溯（可以確保已找到了可能的最長的匹配之前它們將繼續回溯）。因此，POSIX NFA 引擎的速度慢於傳統的 NFA 引擎；並且在使用 POSIX NFA 時，您恐怕不會願意在更改回溯搜索的順序的情況下來支持較短的匹配搜索，而非較長的匹配搜索。

同DFA一樣，非貪婪模式或者說忽略優先量詞對於POSIX NFA同樣是沒有意義的。

三種引擎的使用情況

• 使用傳統型NFA引擎的程序主要有(主流)：

• Java、Emacs(JavaScript/actionScript)、Perl、PHP、Python、Ruby、.NET語言

• VI,GNU Emacs,PCRE library,sed；

• 使用POSIX NFA引擎的程序主要有：mawk,Mortice Kern Systems’ utilities,GNU Emacs(使用時可以明確指定)；

• 使用DFA引擎的程序主要有：awk,egrep,flex,lex,MySQL,Procmail等；

• 也有使用DFA/NFA混合的引擎：GNU awk,GNU grep/egrep,Tcl。

 

《精通正則表達式》書中說POSIX NFA引擎不支持非貪婪模式，很明顯JavaScript不是POSIX NFA引擎。

'123456'.match(/\d{3,6}/);
// ["123456", index: 0, input: "123456", groups: undefined]
'123456'.match(/\d{3,6}?/);
// ["123", index: 0, input: "123456", groups: undefined]

JavaScript的正則引擎是傳統型NFA引擎。

為什麼POSIX NFA引擎不支持也沒有必要支持非貪婪模式？

回溯

現在我們知道，NFA引擎是用表達式去匹配文本，而表達式又有若干分支和範圍，一個分支或者範圍匹配失敗並不意味着最終匹配失敗，正則引擎會去嘗試下一個分支或者範圍。

正是因為這樣的機制，引申出了NFA引擎的核心特點——回溯。

首先我們要區分備選狀態和回溯。

什麼是備選狀態？就是說這一個分支不行，那我就換一個分支，這個範圍不行，那我就換一個範圍。正則表達式中可以商榷的部分就叫做備選狀態。

備選狀態可以實現模糊匹配，是正則表達能力的一方面。

回溯可不是個好東西。想象一下，面前有兩條路，你選擇了一條，走到盡頭髮現是條死路，你只好原路返回嘗試另一條路。這個原路返回的過程就叫回溯，它在正則中的含義是吐出已經匹配過的文本。

我們來看兩個例子：

'abbbc'.match(/ab{1,3}c/);
// ["abbbc", index: 0, input: "abbbc", groups: undefined]
'abc'.match(/ab{1,3}c/);
// ["abc", index: 0, input: "abc", groups: undefined]

第一個例子，第一次a匹配a成功，接着碰到貪婪匹配，不巧正好是三個b貪婪得逞，最後用c匹配c成功。

正則	文本
/a/	a
/ab{1,3}/	ab
/ab{1,3}/	abb
/ab{1,3}/	abbb
/ab{1,3}c/	abbbc

第二個例子的區別在於文本只有一個b。所以表達式在匹配第一個b成功後繼續嘗試匹配b，然而它見到的只有黃臉婆c。不得已將c吐出來，委屈一下，畢竟貪婪匹配也只是盡量匹配更多嘛，還是要臣服於匹配成功這個目標。最後不負眾望用c匹配c成功。

正則	文本
/a/	a
/ab{1,3}/	ab
/ab{1,3}/	abc
/ab{1,3}/	ab
/ab{1,3}c/	abc

請問，第二個例子發生回溯了嗎？

並沒有。

誒，你這樣就不講道理了。不是把c吐出來了嘛，怎麼就不叫回溯了？

回溯是吐出已經匹配過的文本。匹配過程中造成的匹配失敗不算回溯。

為了讓大家更好的理解，我舉一個例子：

你和一個女孩子(或者男孩子)談戀愛，接觸了半個月後發現實在不合適，於是提出分手。這不叫回溯，僅僅是不合適而已。

你和一個女孩子(或者男孩子)談戀愛，這段關係維持了兩年，並且已經同居。但由於某些不可描述的原因，疲憊掙扎之後，兩人最終還是和平分手。這才叫回溯。

雖然都是分手，但你們應該能理解它們的區別吧。

為了讓大家更好的理解，我舉一個例子：

你和一個女孩子(或者男孩子)談戀愛，接觸了半個月後發現實在不合適，於是提出分手。這不叫回溯，僅僅是不合適而已。

你和一個女孩子(或者男孩子)談戀愛，這段關係維持了兩年，並且已經同居。但由於某些不可描述的原因，疲憊掙扎之後，兩人最終還是和平分手。這才叫回溯。

雖然都是分手，但你們應該能理解它們的區別吧。

網絡上有很多文章都認為上面第二個例子發生了回溯。至少根據我查閱的資料，第二個例子發生的情況不能被稱為回溯。當然也有可能我([馬蹄疾]是錯的，歡迎討論。

我們再來看一個真正的回溯例子：

'ababc'.match(/ab{1,3}c/);
// ["abc", index: 2, input: "ababc", groups: undefined]

匹配文本到ab為止，都沒什麼問題。後面既匹配不到b，也匹配不到c。引擎只好將文本ab吐出來，從下一個位置開始匹配。因為上一次是從第一個字符a開始匹配，所以下一個位置當然就是從第二個字符b開始咯。

正則	文本
/a/	a
/ab{1,3}/	ab
/ab{1,3}/	aba
/ab{1,3}/	ab
/ab{1,3}c/	aba
/a/	ab
/a/	aba
/ab{1,3}/	abab
/ab{1,3}/	ababc
/ab{1,3}/	abab
/ab{1,3}c/	ababc

一開始引擎是以為會和最早的ab走完餘生的，然而命運弄人，從此天涯。

這他媽才叫回溯！

還有一個細節。上面例子中的回溯並沒有往回吐呀，吐出來之後不應該往回走嘛，怎麼往後走了？

我們再來看一個例子：

'"abc"def'.match(/".*"/);
// [""abc"", index: 0, input: ""abc"def", groups: undefined]

因為.*是貪婪匹配，所以它把後面的字符都吞進去了。直到發現目標完不成，不得已往回吐，吐到第二個”為止，終於匹配成功。這就好比結了婚還在外面養小三，幾經折騰才發現家庭才是最重要的，自己的行為背離了初衷，於是幡然悔悟。

正則	文本
/”/	“
/”.*/	“a
/”.*/	“ab
/”.*/	“abc
/”.*/	“abc”
/”.*/	“abc”d
/”.*/	“abc”de
/”.*/	“abc”def
/”.*”/	“abc”def
/”.*”/	“abc”de
/”.*”/	“abc”d
/”.*”/	“abc”

我想說的是，不要被回溯的回字迷惑了。它的本質是把已經吞進去的字符吐出來。至於吐出來之後是往回走還是往後走，是要根據情況而定的。

優化正則表達式

現在我們知道了控制回溯是控制正則表達式性能的關鍵。

控制回溯又可以拆分成兩部分：第一是控製備選狀態的數量，第二是控製備選狀態的順序。

備選狀態的數量當然是核心，然而如果備選狀態雖然多，卻早早的匹配成功了，早匹配早下班，也就沒那麼多糟心事了。

傳統NFA工作流程

許多因素影響正則表達式的效率，首先，正則表達式適配的文本千差萬別，部分匹配時比完全不匹配所用的時間要長。上面提到過，JavaScript是傳統NFA引擎，當然每種瀏覽器的正則表達式引擎也有不同的內部優化。

為了有效地使用正則表達式，重要的是理解它們的工作原理。下面是一個正則表達式處理的基本步驟：

第一步：編譯

當你創建了一個正則表達式對象之後（使用一個正則表達式直接量或者RegExp構造器），瀏覽器檢查你的模板有沒有錯誤，然後將它轉換成一個本機代碼例程，用於執行匹配工作。如果你將正則表達式賦給一個變量，你可以避免重複執行此步驟。

第二步：設置起始位置

當一個正則表達式投入使用時，首先要確定目標字符串中開始搜索的位置。它是字符串的起始位置，或由正則表達式的lastIndex屬性指定，但是當它從第四步返回到這裏的時候（因為嘗試匹配失敗），此位置將位於最後一次嘗試起始位置推后一個字符的位置上。

      瀏覽器優化正則表達式引擎的辦法是，在這一階段中通過早期預測跳過一些不必要的工作。例如，如果一個正則表達式以^開頭，IE 和Chrome通常判斷在字符串起始位置上是否能夠匹配，然後可避免愚蠢地搜索後續位置。另一個例子是匹配第三個字母是x的字符串，一個聰明的辦法是先找到x，然後再將起始位置回溯兩個字符。

第三步：匹配每個正則表達式的字元

      正則表達式一旦找好起始位置，它將一個一個地掃描目標文本和正則表達式模板。當一個特定字元匹配失敗時，正則表達式將試圖回溯到掃描之前的位置上，然後進入正則表達式其他可能的路徑上。

      第四步：匹配成功或失敗

      如果在字符串的當前位置上發現一個完全匹配，那麼正則表達式宣布成功。如果正則表達式的所有可能路徑都嘗試過了，但是沒有成功地匹配，那麼正則表達式引擎回到第二步，從字符串的下一個字符重新嘗試。只有字符串中的每個字符（以及最後一個字符後面的位置）都經歷了這樣的過程之後，還沒有成功匹配，那麼正則表達式就宣布徹底失敗。

      牢記這一過程將有助於您明智地判別那些影響正則表達式性能問題的類型。

 

工具

[ regex101 ]是一個很多人推薦過的工具，可以拆分解釋正則的含義，還可以查看匹配過程，幫助理解正則引擎。如果只能要一個正則工具，那就是它了。

[ regexper ]是一個能讓正則的備選狀態可視化的工具，也有助於理解複雜的正則語法。

 

參考文章：

 https://baike.baidu.com/item/正則表達式

正則表達式工作原理 https://www.cnblogs.com/aaronjs/archive/2012/06/30/2570800.html

一次性搞懂JavaScript正則表達式之引擎 https://juejin.im/post/5becc2aef265da6110369c93

 

轉載本站文章《深入正則表達式(3):正則表達式工作引擎流程分析與原理釋義》,
請註明出處：https://www.zhoulujun.cn/html/theory/algorithm/IntroductionAlgorithms/8430.html

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※教你寫出一流的銷售文案?

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※回頭車貨運收費標準

※別再煩惱如何寫文案,掌握八大原則!

※超省錢租車方案

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※推薦台中搬家公司優質服務,可到府估價