From: Wilson Bilkovich <wilsonb@...>
Date: 2006-12-22T01:53:29+09:00
Subject: Re: Regexp Question: Checking for pairs

On 12/21/06, Joe Peck <joe@notsleepy.com> wrote:
> > Regular expressions can be used to test whether a string belongs to a
> > certain regular language, which is a subset of all possible languages
> > (where a language is a set of strings). Regular expressions are
> > equivalent to finite state automata in this respect. Since a finite
> > state automata can only be in a finite number of states. You'd like to
> > match a possibly infinitely large number of [joe][/joe] pairs. The FSA
> > would need a new state for every extra [joe] it reads to remember it
> > still needs to consume a matching [/joe] for it.
> >
> > If this sounds like Chinese, just remember regexpes aren't keen on
> > matching this sort of stuff. Stacks on the other hand seem to be custom
> > designed for these purposes.
> >
> > A.
> It doesn't sound like Chinese :)
>
> If wouldn't have to be an infinite amount of states.  Let's say these
> are the states:
>
> State 1 - no [joe] yet.  If finds [joe], goes to state 2.  If finds
> [/joe], fails.
> State 2 - [joe] found but not matching [/joe].  If it finds [joe] again
> in this state, then fails.  If it finds [/joe], increments count by 1
> and moves to state 1.
>
> If count goes above 3, fails.
>
> But maybe I'll use something besides a regexp, although I thought there
> would be a pretty easy way to do it.
>

To my knowledge, you can't do this with Ruby's current regexp engine,
though it is possible with Perl and .NET.  Both of those languages
support something roughly analogous to a stack, within the expression.
I don't think Ruby 1.8's regexp engine is powerful enough to handle
this, but I would be happy to be proven wrong.

It's worth remembering that what we call 'regular expressions' these
days don't actually match the formal definition of that term, and are
much more powerful in some ways.