anoopelias anoopelias - 1 year ago 101
Javascript Question

Regular Expression composition

Requirement : Two expressions,

, we need to match one or more of both. So I came up with,

(exp1 | exp2)*

However in some places, I see the below being used,

(exp1 * (exp2 exp1*)*)

What is the difference between the two? When would you use one over the other?

Hopefully a fiddle will make this more clear,

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);

EDIT: It looks like there is a difference in behavior between the two apporaches when we capture the groups. The second approach captures the entire string while the first approach captures only the last matching group. See updated fiddle.

Answer Source

The difference between the two patterns is potential efficiency.

The (exp1 | exp2)* pattern contains an alternation that automatically disables some internal regex matching optimization. Also, this regex tries to match the pattern at each location in the string.

The (exp1 * (exp2 exp1*)*) expression is written acc. to the unroll-the-loop principle:

This optimisation thechnique is used to optimize repeated alternation of the form (expr1|expr2|...)*. These expression are not uncommon, and the use of another repetition inside an alternation may also leads to super-linear match. Super-linear match arise from the underterministic expression (a*)*.

The unrolling the loop technique is based on the hypothesis that in most case, you kown in a repeteated alternation, which case should be the most usual and which one is exceptional. We will called the first one, the normal case and the second one, the special case. The general syntax of the unrolling the loop technique could then be written as:

normal* ( special normal* )*

So, the exp1 in your example is normal part that is most common, and exp2 is expected to be less frequent. In that case, the efficiency of the unrolled pattern can be really, much higher than that of the other regex since the normal* part will grab the whole chunks of input without any need to stop and check each location.

Let's see a simple "([^"\\]|\\.)*" regex test against "some text here": there are 35 steps involved:

enter image description here

Unrolling it as "[^"\\]*(\\.[^"\\]*)*" gives a boost to 6 steps as there is much less backtracking.

enter image description here

NOTE that the number of steps at does not directly mean one regex is more efficient than another, however, the debug table shows where backtracking occurs, and backtracking is resource consuming.

Let's then test the pattern efficiency with JS benchmark.js:

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

Also, since unroll the loop concept is not language specific, here is an online PHP test (regular pattern yielding ~0.45, and unrolled one yielding ~0.22 results).

Also see Unroll Loop, when to use.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download