From: Nikolai Weibull <ruby-talk@...>
Date: 2004-11-06T22:43:05+09:00
Subject: Re: recursive brace matching with Ruby regexp

* Eivind Eklund <eeklund@gmail.com> [Nov 05, 2004 16:11]:
> > > Regular expressions, by all standard definitions, aren't
> > > recursive.  Perl's regexen have been extended to allow it, but it
> > > really isn't considered a standard regex feature.

> > Of course, you are correct.  However, recursive "Regular
> > Expressions" are becoming fairly common place now.  Ruby's next
> > regex engine will support them as well.

> > Regular Expression has evolved considerably from the original
> > definition, with recursive capabilities being just another change in
> > a long line of added usefulness.  Does that really means they cease
> > to be Regular Expressions?

> It very specifically mean that they stop being regular expressions,
> because the "regular" actually has a specific meaning (coming from
> regular sets/context free language theory), and has the nice property
> of compiling to a Deterministic Finite Automation with only linear
> increase in size of the DFA compared to the regular expression.

Well, that's not quite true.  They compile to NFAs that are linear in
size of the input regular expression.  The DFA constructed from the
resulting NFA can be exponential in the size of that input.  This is, of
course, only the case for pathological cases, but DFAs are considerably
larger than NFAs, even after minimizing them.

> The true regular expressions consists of  ^, $, characters, *, and (|)
> (alternation).

Well, not really true either.  True regular expressions don't include
zero-width assertions, such as ^ and $.  They include characters from
some alphabet, * - Kleene closure, . - concatenation (which is implicit
in most syntaxes), and | - alternation.

> Most of the "original" extensions compile cleanly to this, and can
> still be considered regular.

Yes.

> When you start using backrefs in matching or recursion, the expression
> is no longer regular (which, among other things, will almost certainly
> force your poor regexp engine into Non-deterministic Finite Automation
> mode -

And backtracking mode as well.  Regular Expressions With Backreferences
are an NP-complete problem and have none of the nice properties of
regular expressions.

> unless you've got exponential amounts of RAM, of course ;-)

?

All in all, backreferencing is an addition that doesn't really add very
much yet ruins a lot of the whole deal with regular expressions.  When
people now start to try to add recursion to regular expressions (which
would have been nice if they could have easily been included - but they
can't) one has to shiver a bit.  If you wan't recursion, use something
suitable - like context-free languages; don't expect to solve everything
with only one tool.
	nikolai

--
::: name: Nikolai Weibull    :: aliases: pcp / lone-star / aka :::
::: born: Chicago, IL USA    :: loc atm: Gothenburg, Sweden    :::
::: page: www.pcppopper.org  :: fun atm: gf,lps,ruby,lisp,war3 :::
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}