9fans archive / 2008 / 10 / 349 /    prev next

From: John Stalker <stalker@mat...>
Subject: Re: [9fans] non greedy regular expressions
Date: Fri, 24 Oct 2008 19:02:26 +0100

> you probably mean NON-greedy ops.

Yes, my mistake.  I'll risk making a very minor correction to
Rob's post as well:

> Backreferences within the pattern (such as in /(.*)\1/) make the
> matcher non-regular and exponentially hard.

They do change the class of the grammar and nobody knows how to
implement them in subexponential time, but it hasn't been proved
to be impossible.

-- 
John Stalker
School of Mathematics
Trinity College Dublin
tel +353 1 896 1983
fax +353 1 896 2282