正則表達式組合

Question

要求：兩個表達式，exp1和exp2，我們需要匹配兩者中的一個或多個。所以，我想出了，

(exp1 | exp2)* 

然而，在一些地方，我看到了下面的被使用，

(exp1 * (exp2 exp1*)*) 

兩者有什麼區別？你什麼時候使用一個？

希望一個fiddle將使這一更清晰，

var regex1 = /^"([\x00-!#-[\]-\x7f]|\\")*"$/; 
var regex2 = /^"([\x00-!#-[\]-\x7f]*(\\"[\x00-!#-[\]-\x7f]*)*)"$/; 

var str = '"foo \\"bar\\" baz"'; 
var r1 = regex1.exec(str); 
var r2 = regex2.exec(str); 

編輯：它看起來像有是，當我們拍攝組兩個apporaches之間的行爲差​​異。第二種方法捕獲整個字符串，而第一種方法僅捕獲最後一個匹配組。查看更新的fiddle。

Answer 1

兩個圖案之間的差異是潛在效率。

的(exp1 | exp2)*圖案包含自動禁用一些內部正則表達式匹配優化的交替。此外，這個正則表達式試圖匹配字符串中每個位置的模式。

(exp1 * (exp2 exp1*)*)的表達被寫入累計。到unroll-the-loop原理：

該優化技術用於優化表格(expr1|expr2|...)*的重複交替。這些表達並不少見，並且在交替內使用另一種重複也可能導致超線性匹配。超線性匹配來自不確定性表達(a*)*。

的展開循環技術是基於這樣的假設，在大多數情況下，你kown在repeteated交替，這種情況下應該是最常用的，哪一個是例外。我們將稱第一個，正常情況和第二個，特例。在展開循環技術的一般語法然後可以寫爲：

normal* (special normal*)*

所以，在您的示例exp1是正常一部分是最常見和exp2預期不太頻繁。在這種情況下，展開模式的效率可能會比其他正則表達式的效率高很多，因爲normal*部分將抓取整個輸入塊，而不需要停止並檢查每個位置的。

讓我們來看看一個簡單的"([^"\\]|\\.)*" regex test against "some text here"：有涉及35步：

展開它作爲"[^"\\]*(\\.[^"\\]*)*"給出了一個升壓至6個步驟有回溯要少得多。

注即在regex101.com步驟的數量不直接意味着一個正則表達式是比另一種更有效的，然而，調試表示出回溯時，和回溯是消耗資源的。然後讓我們用JS基準測試模式效率。JS：

var suite = new Benchmark.Suite(); 
 
Benchmark = window.Benchmark; 
 
suite 
 
    .add('Regular RegExp test', function() { 
 
     '"some text here"'.match(/"([^"\\]|\\.)*"/); 
 
    }) 
 
    .add('Unrolled RegExp test', function() { 
 
     '"some text here"'.match(/"[^"\\]*(\\.[^"\\]*)*"/); 
 
    }) 
 
    .on('cycle', function(event) { 
 
    console.log(String(event.target)); 
 
    }) 
 
    .on('complete', function() { 
 
    console.log('Fastest is ' + this.filter('fastest').map('name')); 
 
    }) 
 
    .run({ 'async': true });

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.13.1/lodash.js"></script> 
 
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.1/platform.js"></script> 
 
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.0/benchmark.js"></script>

結果：

Regular RegExp test x 9,295,393 ops/sec ±0.69% (64 runs sampled) 
Unrolled RegExp test x 12,176,227 ops/sec ±1.17% (64 runs sampled) 
Fastest is Unrolled RegExp test 

另外，由於展開循環概念不是語言特定，這裏是一個online PHP test（規則圖案產生〜0.45 ，並展開一個產生結果的〜0.22）。

另見Unroll Loop, when to use。

Answer 2

兩者有什麼區別？

它們之間的區別在於它們如何完全匹配特定的給定輸入。如果你認爲這些是輸入和輸出的兩個函數，它們是等價的，但函數如何產生輸出（匹配）是不同的。這兩個正則表達式(exp1 | exp2)*和(exp1 * (exp2 exp1*)*)將匹配完全相同的輸入。換句話說，你可以說它們在給定的輸入和匹配（輸出）方面在語義上是等價的。

什麼時候你會用另一個？

編輯

第二正則表達式(exp1 * (exp2 exp1*)*)是更理想的，由於循環展開技術。見@WiktorStribiżew的回答。證明

---

證明

的一種方式，如果兩個正則表達式是等效的，看看他們是否有相同的DFA。使用this converter，這裏是正則表達式的以下DFA。

（注：a = exp1和b = exp2）

(a*(ba*)*) 

(a|b)* 

注意，第一DFA是一樣的第二個？唯一的區別是第一個沒有最小化。這裏是一個污物修復，以顯示所述第一DFA的最小化：