On Tue, Jul 16, 2013 at 8:00 AM, MRAB <python@mrabarnett.plus.com> wrote:

On 16/07/2013 04:10, Eli Bendersky wrote:

...

Since the 'regex' module is a candidate for inclusion into the stdlib, I figured this would be a good place to ask.

While discussing something related in pss (https://github.com/eliben/pss**), Ben Hoyt brought to my attention that the implementation of alternation (foo|bar) in Python's default regex module (the SRE implementation) is very inefficient. And indeed, looking there it seems that | gets translated to an opcode that simply means going over all the alternatives in a loop trying to match each. This is not how a proper regex engine should implement alternation!

A common advice given to Python programmers is to combine their regexes into a single one with |. This makes code faster, but it turns out that it's far from its full potential because the combination doesn't go full way to the DFA as it's supposed to.

A question about 'regex' - is it implemented properly there?

There are 2 ways of implementing regex: DFA and NFA.

DFA is faster, but those using NFA do so because the implementation offers additional features that make DFA tricky or impossible, such as backreferences.

Of course, you could use DFA when it's possible, NFA when it isn't, at the cost of yet more code.

The regex module uses NFA, just like re.

If you want to improve regex, making it use DFA when possible, well, the source code is open, and your contributions are welcome. Good luck! :-)

You can use NFA without backtracking, though, by keeping track of the set of possible states. I believe (but am not 100% sure) this is the way re2 works, for example. In the particular case of alternations, such approach is vastly superior because the "possible states" set never grows large (assuming the alternatives are not mostly the same). Whereas with backtracking you always have to iterate over all of them. That said, I think you have answered my question - regex also uses a backtracking implementation of NFA and iterates in case of alternations. OK :-) Eli