正則表達式匹配解析過程探討分析(正則表達式匹配原理)

2020-03-22 17:06:01

字體：大中小

來源：轉載

供稿：網友

已經有多篇關于html' target='_blank'>正則表達式介紹的文章，隨著我們越來越多使用正則表達式，想對性能做優化、減少我們正則表達式書寫匹配Bug。我們不得不進一步深入了解正則表達式執行過程了。下面我們一起學習，分析下正則表達式執行過程。我們會用regexbuddy測試工具分解執行過程，具體工具使用，可以看：正則表達式性能測試工具推薦、優化工具推薦(regexbuddy推薦)。要了解正則表達式解析過程前，我們先來熟悉幾個概念。常見正則表達式引擎
引擎決定了正則表達式匹配方法及內部搜索過程，了解它至關重要的。目前主要流行引擎有：DFA,NFA兩種引擎，我們比較區分下。
確定型有窮自動機 DFA引擎它們不要求回溯（并因此它們永遠不測試相同的字符兩次），所以匹配速度快！DFA引擎還可以匹配最長的可能的字符串。不過DFA引擎只包含有限的狀態，所以它不能匹配具有反向引用的模式，還不可以捕獲子表達式。代表性有：awk,egrep,flex,lex,MySQL,Procmail
NFA
Non-deterministic finite automaton 非確定型有窮自動機，又分為傳統NFA,Posix NFA 傳統的NFA引擎運行所謂的“貪婪的”匹配回溯算法（longest-leftmost），以指定順序測試正則表達式的所有可能的擴展并接受第一個匹配項。傳統的NFA回溯可以訪問完全相同的狀態多次，在最壞情況下，它的執行速度可能非常慢，但它支持子匹配。代表性有：GNU Emacs,Java,ergp,less,more,.NET語言,
PCRE library,Perl,PHP,Python,Ruby,sed,vi等，一般高級語言都采用該模式。
DFA以字符串字符，逐個在正則表達式匹配查找，而NFA以正則表達式為主，在字符串中逐一查找。盡管速度慢，但是對操作者來說更簡單，因此應用更廣泛！下面所有以NFA引擎舉例說明，解析過程！解析引擎眼中的字符串組成
對于字符串“DEF”而言，包括D、E、F三個字符和 0、1、2、3 四個數字位置：0D1E2F3，對于正則表達式而言所有源字符串，都有字符和位置。正則表達式會從0號位置，逐個去匹配的。占有字符和零寬度
正則表達式匹配過程中，如果子表達式匹配到的是字符內容，而非位置，并被保存到最終的匹配結果中，那么就認為這個子表達式是占有字符的；如果子表達式匹配的僅僅是位置，或者匹配的內容并不保存到最終的匹配結果中，那么就認為這個子表達式是零寬度的。占有字符是互斥的，零寬度是非互斥的。也就是一個字符，同一時間只能由一個子表達式匹配，而一個位置，卻可以同時由多個零寬度的子表達式匹配。常見零寬字符有：^，( =)等正則表達式匹配過程詳解實例
我們掌握了上面幾個概念，我們接下來分析下幾個常見的解析過程。結合使用軟件regexBuddy來分析。Demo1: 源字符DEF,對應標記是：0D1E2F3，匹配正則表達式是：/DEF/過程可以理解為：首先由正則表達式字符 /D/ 取得控制權，從位置0開始匹配，由 /D/ 來匹配“D”，匹配成功，控制權交給字符 /E/ ；由于“D”已被 /D/ 匹配，所以 /E/ 從位置1開始嘗試匹配，由 /E/ 來匹配“E”，匹配成功，控制權交給 /F/ ；由 /F/ 來匹配“F”，匹配成功。Demo2:源字符DEF,對應標記是：0D1E2F3，匹配正則表達式是：/D/w+F/過程可以理解為：首先由正則表達式字符 /D/ 取得控制權，從位置0開始匹配，由 /D/ 來匹配“D”，匹配成功，控制權交給字符 //w+/ ；由于“D”已被 /D/ 匹配，所以 //w+/ 從位置1開始嘗試匹配，/w+貪婪模式，會記錄一個備選狀態，默認會匹配最長字符，直接匹配到EF，并且匹配成功，當前位置3了。并且把控制權交給 /F/ ；由 /F/ 匹配失敗，/w+匹配會回溯一位，當前位置變成2。并把控制權交個/F/，由/F/匹配字符F成功。因此/w+這里匹配E字符,匹配完成！Demo3:源字符DEF,對應標記是：0D1E2F3，匹配正則表達式是：/^( =D)[D-F]+$/過程可以理解為：元字符 /^/ 和 /$/ 匹配的只是位置，順序環視 /( =D)/ （匹配當前位置，右邊是否有字符“D”字符出現）只進行匹配，并不占有字符，也不將匹配的內容保存到最終的匹配結果，所以都是零寬度的。首先由元字符 /^/ 取得控制權，從位置0開始匹配， /^/ 匹配的就是開始位置“位置0”，匹配成功，控制權交給順序環視 /( =D)/；/( =D])/ 要求它所在位置右側必須是字母”D”才能匹配成功，零寬度的子表達式之間是不互斥的，即同一個位置可以同時由多個零寬度子表達式匹配，所以它也是從位置0嘗試進行匹配，位置0的右側是字符“D”，符合要求，匹配成功，控制權交給 /[D-F]+/ ；因為 /( =D)/ 只進行匹配，并不將匹配到的內容保存到最后結果，并且 /( =D)/ 匹配成功的位置是位置0，所以 /[D-F]+/ 也是從位置0開始嘗試匹配的， /[D-F]+/ 首先嘗試匹配“D”，匹配成功，繼續嘗試匹配，直到匹配完”EF”，這時已經匹配到位置3，位置3的右側已沒有字符，這時會把控制權交給 /$/，元字符 /$/ 從位置3開始嘗試匹配，它匹配的是結束位置，也就是“位置3”，匹配成功。此時正則表達式匹配完成，報告匹配成功。匹配結果為“DEF”，開始位置為0，結束位置為3。其中 /^/ 匹配位置0， /( =D)/ 匹配位置0， /[D-F]+/ 匹配字符串“DEF”， /$/ 匹配位置3。后記：上面這幾個例子，我們分析了正則表達式普通匹配，還有回溯過程，然后零寬度字符，匹配過程。當然，給出的例子比較簡單，實際過程中會遇到更長，更復雜的正則表達式。但是，思想是類似的。只要我們把我解析原理，都可以逐一分解的。好了，就到這里，歡迎交流！PHP教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。

上一篇：淺析正則表達式

下一篇：JAVA中正則表達式小總結(整理)