Invisible wrote:
>>> 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.

I even expressed it in Haskell-ish syntax.

"Zero or more A's, followed by zero or more A's, followed by zero or more 
A's, followed by three A's."

The fact that you can't read the link I provided is screaming out that you 
need to learn how to read that link. Not knowing even the basics of regular 
expressions is like not knowing even the basics of TCP.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message