Invisible wrote:
>>> If there are more than three digits, the above parser fails, and no
>>> other alternatives are tried (i.e., no backtracking).
>>
>> Then you aren't doing what regular expressions can do.
> 
> I don't see how that is the case.

You really should learn the essential basics of an entire heirarchy of 
formal language theory.


>> In order to *get* the power of regexp, *your* parser has to backtrack.
>> So if you turn backtracking off, there are trivial regular expressions
>> you can't match. If you turn backtracking on, you're using more time and
>> space than a regular expression engine.
> 
> 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.

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

Post a reply to this message