From mboxrd@z Thu Jan  1 00:00:00 1970
From: John Stalker <stalker@maths.tcd.ie>
To: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net>
In-reply-to: <a560a5d00810241041w798aa12clb4e425eb74360408@mail.gmail.com>
References: <a560a5d00810240108q62854ec1w16614c90c7071436@mail.gmail.com>
	<765ef13a653652d5fcef9001ff70f814@quanstro.net>
	<a560a5d00810240911gee79793h966c6f325ce19f97@mail.gmail.com>
	<20081024170237.68ED28DE7@okapi.maths.tcd.ie>
	<a560a5d00810241041w798aa12clb4e425eb74360408@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <3854.1224871346.1@maths.tcd.ie>
Date: Fri, 24 Oct 2008 19:02:26 +0100
Message-Id: <20081024180226.2A51E869A@okapi.maths.tcd.ie>
Subject: Re: [9fans] non greedy regular expressions
Topicbox-Message-UUID: 26570e60-ead4-11e9-9d60-3106f5b1d025

> 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