Regex trouble

[andrew cooke]

more exactly, my guess is perl has a special case for this that avoids
doing a search over all possible matchers via the pushdown stack.

andrew cooke wrote:
>
> ".*?" is a "not greedy" match, which is significantly more difficult to
> handle than a normal ".*".  so the performance will depend on quite
> complex details of how the regular expression engine is implemented.  it
> wouldn't surprise me if perl was better here, because it comes from a
> background with a much stronger emphasis on regular expressions.
>
> i know that not an exact answer, but unless you find the author of the re
> library i am not sure you will get a much better explanation.  it comes
> down to whether the regular expression can be implemented using a
> deterministic finite automaton (rather than an indeterministic one).  if
> you look at the table at the bottom of
> http://en.wikipedia.org/wiki/Finite_state_machine then i believe (i am not
> 100% sure) that the ".*?" match requires at least a pushdown automota,
> while ".*" can be handled with a simple finite automaton.
>
> disclaimer: this is all fairly new to me as i just recently implemented a
> regular expression matcher myself, and i may be wrong on some of the
> details.
>
> andrew
>
>
> akshat agarwal wrote:
>> Hi,
>>
>> I am trying to use the following snippet of code to print a regex match.
>>
>> s = '01234567890123456789x012'
>>
>> pat = r'(.*?x|[^a]+)*y'
>>
>> mo = re.search(pat, s)
>> if mo is not None:
>>     print mo.group(0)
>>
>> By adding one character before the 'x' in the input string, the time
>> taken
>> to print the match doubles. This behaviour is not observed in perl. I am
>> curious to know about the difference the in regex implementations of
>> perl
>> and python which causes this.
>>
>> Thanks
>> --
>> http://mail.python.org/mailman/listinfo/python-list
>>
>
>