淺談?wù)齽t表達(dá)式原理

作者：騰訊AlloyTeam 2019-07-17 15:45:47

開發(fā) 前端

正則表達(dá)式可能大部分人都用過，但是大家在使用的時(shí)候，有沒有想過正則表達(dá)式背后的原理，又或者當(dāng)我告訴你正則表達(dá)式可能存在性能問題導(dǎo)致線上掛掉，你會(huì)不會(huì)覺得特別吃驚？

[[270927]]

我們先來看看7月初，因?yàn)橐粋€(gè)正則表達(dá)式，導(dǎo)致線上事故的例子。

https://blog.cloudflare.com/d...

簡單來說就是一個(gè)有性能問題的正則表達(dá)式，引起了災(zāi)難性回溯，導(dǎo)致cpu滿載。

性能問題的正則

先看看出問題的正則

引起性能問題的關(guān)鍵部分是 .*(?:.*=.*) ，這里我們先不管那個(gè)非捕獲組，將性能問題的正則看做 .*.*=.* 。

其中 . 表示匹配除了換行以外的任意字符（很多人把這里搞錯(cuò)，容易出bug）， .* 表示貪婪匹配任意字符任意次。

什么是回溯

在使用貪婪匹配或者惰性匹配或者或匹配進(jìn)入到匹配路徑選擇的時(shí)候，遇到失敗的匹配路徑，嘗試走另外一個(gè)匹配路徑的這種行為，稱作回溯。

可以理解為走迷宮，一條路走到底，發(fā)現(xiàn)無路可走就回到上一個(gè)三岔口選擇另外的路。

回溯現(xiàn)象

// 性能問題正則  
// 將下面代碼粘貼到瀏覽器控制臺(tái)運(yùn)行試試  
const regexp = `[A-Z]+\\d+(.*):(.*)+[A-Z]+\\d+`;  
const str = `A1:B$1,C$1:D$1,E$1:F$1,G$1:H$1`  
const reg = new RegExp(regexp);  
start = Date.now();  
const res = reg.test(str);  
end = Date.now();  
console.log('常規(guī)正則執(zhí)行耗時(shí):' + (end - start))

現(xiàn)在來看看回溯究竟是怎么一回事

假設(shè)我們有一段正則 (.*)+\d ，這個(gè)時(shí)候輸入字符串為 abcd ，注意這個(gè)時(shí)候僅僅輸入了一個(gè)長度為4的字符串，我們來分析一下匹配回溯的過程：

上面展示了一個(gè)回溯的匹配過程，大概描述一下前三輪匹配。

注意 (.*)+ 這里可以先暫且看成多次執(zhí)行 .* 。 (.*){1,}

***次匹配，因?yàn)?.* 可以匹配任意個(gè)字符任意次，那么這里可以選擇匹配空、a、ab、abc、abcd，因?yàn)?* 的貪婪特性，所以 .* 直接匹配了 abcd 4個(gè)字符， + 因?yàn)楹竺鏇]有其他字符了，所以只看著 .* 吃掉 abcd 后就不匹配了，這里記錄 + 的值為1，然后 \d 沒有東西能夠匹配，所以匹配失敗，進(jìn)行***次回溯。

第二次匹配，因?yàn)檫M(jìn)行了回溯，所以回到上一個(gè)匹配路徑選擇的時(shí)候，上次 .* 匹配的是 abcd ，并且路不通，那么這次只能嘗試匹配 abc ，這個(gè)時(shí)候末尾還有一個(gè) d ，那么可以理解為 .* ***次匹配了 abc ，然后因?yàn)?(.*)+ 的原因， .* 可以進(jìn)行第二次匹配，這里 .* 可以匹配 d ，這里記錄 + 的值為2，然后 \d 沒有東西能夠匹配，所以匹配失敗，進(jìn)行第二次回溯。

第三次匹配，因?yàn)檫M(jìn)行了回溯，所以回到上一個(gè)匹配路徑選擇的時(shí)候，上次***個(gè) .* 匹配的是 abc ，第二個(gè) .* 匹配的是 d ，并且路不通，所以這里第二次的 .* 不進(jìn)行匹配，這個(gè)時(shí)候末尾還有一個(gè) d ， \d 和 d 匹配失敗，進(jìn)行第三次回溯。

如何減少或避免回溯

優(yōu)化正則表達(dá)式：時(shí)刻注意回溯造成的性能影響。
使用DFA正則引擎的正則表達(dá)式

什么是DFA正則引擎

傳統(tǒng)正則引擎分為NFA（非確定性有限狀態(tài)自動(dòng)機(jī)），和DFA（確定性有限狀態(tài)自動(dòng)機(jī)）。

DFA

對(duì)于給定的任意一個(gè)狀態(tài)和輸入字符，DFA只會(huì)轉(zhuǎn)移到一個(gè)確定的狀態(tài)。并且DFA不允許出現(xiàn)沒有輸入字符的狀態(tài)轉(zhuǎn)移。

比如狀態(tài)0，在輸入字符A的時(shí)候，終點(diǎn)只有1個(gè)，只能到狀態(tài)1。

NFA

對(duì)于任意一個(gè)狀態(tài)和輸入字符，NFA所能轉(zhuǎn)移的狀態(tài)是一個(gè)非空集合。

比如狀態(tài)0，在輸入字符A的時(shí)候，終點(diǎn)可以是多個(gè)，即能到狀態(tài)1，也能到狀態(tài)0。

DFA和NFA的正則引擎的區(qū)別

那么講了這么多之后，DFA和NFA正則引擎究竟有什么區(qū)別呢？或者說DFA和NFA是如何實(shí)現(xiàn)正則引擎的呢？

DFA

正則里面的DFA引擎實(shí)際上就是把正則表達(dá)式轉(zhuǎn)換成一個(gè)圖的鄰接表，然后通過跳表的形式判斷一個(gè)字符串是否匹配該正則。

// 大概模擬一下  
function machine(input) {  
    if (typeof input !== 'string') {  
        console.log('輸入有誤');  
        return;  
    }  
    // 比如正則：/abc/ 轉(zhuǎn)換成DFA之后  
    // 這里我們定義了4種狀態(tài)，分別是0,1,2,3，初始狀態(tài)為0  
    const reg = {  
        0: {  
            a: 1,  
        },  
        1: {  
            b: 3,  
        },  
        2: {  
            isEnd: true,  
        },  
        3: {  
            c: 2,  
        },  
    };  
    let status = 0;  
    for (let i = 0; i < input.length; i++) {  
        const inputinputChar = input[i];  
        status = reg[status][inputChar];  
        if (typeof status === 'undefined') {  
            console.log('匹配失敗');  
            return false;  
        }  
    }  
    const end = reg[status];  
    if (end && end.isEnd === true) {  
        console.log('匹配成功');  
        return true;  
    } else {  
        console.log('匹配失敗');  
        return false;  
    }  
}  
const input = 'abc';  
machine(input);