Mastering Regular Expressions (2nd Edition) [Electronic resources] نسخه متنی

6.9 Quize Answers

6.9.1 Effects of a Simple Change

Answers to the questions in Section 6.1.1.

Effect for which type of engine? The change has virtually no effect whatsoever
for a POSIX NFA engine. Since it must eventually try every permutation
of the regex anyway, the order in which the alternatives are tried is irrelevant.
For a Traditional NFA, however, ordering the alternatives in such a way
that quickly leads to a match is a benefit because the engine stops once the
first match is found.

Effect during which kind of result? The change results in a faster match only
when there is a match. An NFA can fail only after trying all possible permutations
of the match (and again, the POSIX NFA tries them all anyway). So if
indeed it ends up failing, every permutation must have been attempted, so
the order does not matter.

The following table shows the number of tests ("tests") and backtracks ("b.t.")
for several cases (smaller numbers are better):

As you can see, the POSIX NFA results are the same with both expressions,
while the Traditional NFA's performance increases (backtracks decrease) with
the new expression. Indeed, in a non-match situation (the last example in
the table), since both engine types must evaluate all possible permutations,
all results are the same.