正则表达式组合

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的最小化：