From: Eivind Eklund <eeklund@...>
Date: 2004-11-05T17:19:27+09:00
Subject: Re: recursive brace matching with Ruby regexp

On Fri, 5 Nov 2004 12:17:01 +0900, James Edward Gray II
<james@grayproductions.net> wrote:
> On Nov 4, 2004, at 8:04 PM, Mark Hubbart wrote:
> 
> > 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?

Yes.

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.

The true regular expressions consists of  ^, $, characters, *, and (|)
(alternation).  Most of the "original" extensions compile cleanly to
this, and can still be considered regular.  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 - unless
you've got exponential amounts of RAM, of course ;-)

http://en.wikipedia.org/wiki/Regular_expression gives a bit more background.

Eivind.
-- 
Hazzle free packages for Ruby?
RPA is available from http://www.rubyarchive.org/