regular expression - exponential complexity

[Ivan Glushkov]

Hi.

I'm almost sure that you know this, so JFYI.
I found regexp that has exponential complexity while in perl the same
regexp seems to grow linearily.

So the question is, are you going to move to re2 or any other  DFA
regexp library?

details:

cat test.erl
-module(test).
-export([
        str/1,
        f/1,
        fc/1
    ]).

str(Len) -> "exmample." ++ string:chars($c,Len) ++ "?a".

f(Len) ->
    re:run(str(Len),"^([a-z0-9\\-\\_]+\\.)*[a-z0-9]([a-z0-9\\-]*[a-z0-9])?\\.[a-z]([a-z0-9\\-]*[a-z0-9])+$",
[{capture, none}]).

fc(Len) ->
    {ok, Re} = re:compile("^([a-z0-9\\-\\_]+\\.)*[a-z0-9]([a-z0-9\\-]*[a-z0-9])?\\.[a-z]([a-z0-9\\-]*[a-z0-9])+$"),
    re:run(str(Len), Re, [{capture, none}]).


Some results (f and fc give the same result).

string length / frequency (run cycles per second)
3	50000
5	30000
10	1455
11	1136
12	586
13	292
14	146
15	73
16	37


Ivan.