> Is it really so? R. Cox (Regular Expression Matching Can Be Simple And
> Fast), I think, shows, that repetition can be first expanded and then
> used even by the nice (non-backtracking) algorithms, like this:
>
> e{3} --> eee
> e{3,5} --> eeee?e?
> e{3,} --> eee+
>
> where would the problem arise?
The problem arises mainly not in this construct
but in the tremendous number of other
constructs that regexp libraries with counted
repetition usually throw in along with it.
That said, even counted repetition is not free.
Even if sam/acme had counted repetition,
it would not handle x{1000} particularly well,
since the expansion you give above would
end up being a very long regular expression
for non-trivial x.
R. Cox
