>> Do you have a concrete example?
>
> http://swtch.com/~rsc/regexp/regexp1.html
>
> Or, in your language
> many (char 'a')
> many (char 'a')
> many (char 'a')
> char 'a'
> char 'a'
> char 'a'
> Now match that against "aaaaaa".
>
> The problem is the first "many (char 'a')" eats the whole string.
>
> Without backtracking, you claim the string fails to match.
> *With* backtracking, you're now taking an exponential amount of time to
> match something you could match in six comparisons.

I don't understand the specification.

Post a reply to this message